TRUNK RESERVATION ANALYSIS OF TELUS' EDMONTON TELECOMMUNICATION NETWORK

INFOR, Aug 2003 by Sim, Thaddeus

We thus conclude that the Overflow Traffic Algorithm converges due to Properties 1, 2, and 3. In a preliminary test using data from TELUS' Edmonton network, the algorithm terminated after two iterations.

Finally, it is clear from the discussion above that the service rate of a trunk group ij, µ^sup ij^, is a function of [lambda]^sup ij^^sub 1^ and [lambda]^sup ij^^sub 2^ since trunk group ij can form either a direct path or part of a multi-link path. We will assume µ^sup ij^ to be the mean service rate of calls comprising of only first-routed traffic [lambda]^sup ij^^sub 1^. This assumption is valid since under typical demand loads, multi-link calls make up less than 2% of all connected calls in the network (Figure 2) and should not significantly impact the mean service rate µ^sup ij^.

4. SOLUTION METHODOLOGY

The resulting trunk reservation problem is an integer non-linear optimization problem. Since we want to explicitly incorporate the Overflow Traffic Algorithm into the solution procedure, we choose to solve the problem using a heuristic, specifically simulated annealing.

The simulated annealing idea originates from thermodynamics and metallurgy, where a molten material is cooled slowly into a solid with minimal energy (Pirlot, 1996). In its application to an optimization problem, if a proposed feasible solution reduces the objective function value (in a minimization problem), the proposed solution is accepted. If, however, the proposed solution worsens the objective function value, the probability of accepting the proposed solution is inversely proportional to the degradation of the objective function value.

The objective for our simulated annealing algorithm is to minimize the total expected overflow level in the network. We use as our initial solution the special case of no trunks reserved in the network. In simulated annealing, the neighbour to the current solution is generated randomly. In our study, we randomly choose a trunk group from the existing solution and randomly increase or decrease the number of reserved trunks in the selected trunk group, subject to non-negativity and capacity constraints. As stated in section 2, large numbers of reserved trunks are not necessary to observe its benefits in a network. Therefore, the marginal change in the number of reserved trunks is limited to one in the neighbour generation phase.

The loop length L determines how long the algorithm stays at a certain temperature. It is usually set to a multiple of the expected size of the neighbourhood (Kirkpatrick et al., 1983; Johnson et al., 1989; Pirlot, 1996). From our definition of a neighbour, the neighbourhood size is twice the number of variables in the problem. Johnson et al. (1989) also suggest modifying the loop length to include cutoffs: a mechanism to terminate the loop at its current temperature when a certain threshold of accepted moves has been achieved. This is to prevent unneeded trials at the beginning of the algorithm on the assumption that it is the number of moves accepted rather than the number of trials that is important. In our implementation, we set the cutoffs using a percentage 100[alpha]% of the loop length, i.e. [alpha]L, with L set to 132 (twice the number of trunk groups in the fully-connected 12-switch Edmonton network).