Improved Fixed Point Methods for Loss Networks with Linear Structure

M.S. Bebbingtongif, P.K. Pollettgif and I. Ziedinsgif

Extended abstract

This paper is concerned with the performance evaluation of loss networks. For the simplest networks, there are explicit analytical formulae for the important measures of performance, but for networks which involve some level of dynamic control, such as routing schemes which make use of spare capacity, exact analytical methods have had only limited success. Under several regimes, the Erlang Fixed Point (EFP) method provides a good approximation for the blocking probabilities, but when these regimes are not operative, the method can perform badly because the key assumption of independent blocking may not hold. We propose several new models which specifically account for the dependencies between neighbouring links. We derive approximations for the blocking probabilities with errors typically tex2html_wrap_inline161 of that found using the EFP approximation. These are extended to cases where admission controls, such as trunk reservation, are used.

The assumption of independence between links which drives the EFP approximation holds under two limiting regimes. The first is one in which the topology of the network is held fixed, while capacities and arrival rates at links become large [4]; this has become known as the Kelly limiting regime, or (somewhat misleadingly) as the heavy traffic limit. Under the second limiting regime, called diverse routing, the number of links, and the number of routes which use these links, become large, while the capacities are held fixed and the arrival rate on any single route becomes small. Examples of this are star networks and fully-connected networks with alternate routing [2, 3, 5, 7, 8]. If neither regime is operative, the EFP method can perform badly: in particular, in highly linear networks and/or networks with low capacities. Further, adding controls to the network may destroy independence under otherwise favourable regimes. A particularly useful control is trunk reservation. Here, traffic streams are assigned priorities and calls are accepted only if the occupancies of links along their route are not above a given threshold, the size of which depends on the type of call. This widely used control mechanism is typically very robust to fluctuations in arrival rate and has the added advantage of eliminating pathological behaviour such as bistability [1]. With such a control operating in a network of reasonable size, links may be highly dependent and the equilibrium distribution will no longer have a product form, as it does for the corresponding uncontrolled network. Modelling dependencies in this context is thus critical.

We will focus attention on simple, highly linear networks, since here the EFP approximation is expected to perform poorly. To illustrate our methods, consider a loss network with K links forming a loop and each link has the same capacity, C. There are two types of traffic: 1-link routes (type-1 traffic) and 2-link routes comprising pairs of adjacent links (type-2 traffic). Type-t traffic is offered at rate tex2html_wrap_inline169 on each type-t route. If tex2html_wrap_inline173 is the common loss probability for type-t calls, then the EFP approximation is


where the Erlang Fixed Point B is the unique solution to


where tex2html_wrap_inline183 is Erlang's Formula.

A significant improvement in accuracy can be obtained by adapting methods of Pallant [6]. The network is decomposed into independent subnetworks and the stationary distribution is evaluated for each. Consider a two-link subnetwork consisting of say links 1 and 2. There are three routes: tex2html_wrap_inline185 , tex2html_wrap_inline187 and tex2html_wrap_inline189 . If tex2html_wrap_inline191 denotes the number of calls on route r, then tex2html_wrap_inline195 is the number of calls occupying capacity on link 1 but not on link 2, tex2html_wrap_inline197 is the number occupying capacity on link 2 but not on link 1, and, tex2html_wrap_inline199 is the number of calls occupying capacity on both links. The state space for the subnetwork is tex2html_wrap_inline201 and the stationary distribution is


where G is a normalizing constant; we estimate B, the probability that a link adjacent to the two-link subnetwork is fully occupied, by


These expressions are used iteratively to determine a fixed point B and then, as before, we set tex2html_wrap_inline213 and tex2html_wrap_inline215 .

Our second, and most accurate, approximation uses additional knowledge of the state of a given link in estimating the probability that the adjacent link is full. We use state-dependent arrival rates, tex2html_wrap_inline217 , tex2html_wrap_inline219 , where tex2html_wrap_inline221 is the probability that link K is fully occupied, conditional on tex2html_wrap_inline225 ( tex2html_wrap_inline221 is also the probability that link 3 is fully occupied, conditional on tex2html_wrap_inline231 ), so that


Once tex2html_wrap_inline221 is estimated and tex2html_wrap_inline237 determined, we set


Similarly, tex2html_wrap_inline241 can be expressed in terms of tex2html_wrap_inline237 . An estimate of tex2html_wrap_inline221 is found by assuming that tex2html_wrap_inline221 does not depend on tex2html_wrap_inline199 . For tex2html_wrap_inline251 , we set




The dependence of tex2html_wrap_inline257 on tex2html_wrap_inline199 is due to the cyclic nature of the network, but is expected to be slight for large networks.

Full details of all fixed point methods will be described in the paper, including extensions to networks with trunk reservation. Detailed comparisons and error analysis will be provided for all methods.