STATE-DEPENDENT ROUTING ON SYMMETRIC LOSS NETWORKS WITH TRUNK RESERVATIONS: ANALYSIS, ASYMPTOTICS, OPTIMAL DESIGN.

We investigate a distributed, state-dependent, dynamic routing strategy, called here Aggregated-Least-Busy-Alternative (ALBA), for circuit-switched loss networks. The major impetus for our investigation is the proposed deployment in the AT&T Switched Network of Real Time Network Routing (RTNR) which is state-dependent and employs aggregation. The networks considered are symmetric and fully connected, the offered calls form Poisson streams and routes have at most 2 links. In ALBA(K) the states of each link are lumped into K (K>=2) aggregates and the route each call is determined by local information on the aggregate-states of the links of the alternate routes at the time of that call's arrival. The last aggregate is always the set of states reserved for direct traffic and defined by the trunk reservation parameter. We give a Fixed Point Model for ALBA(K) for general K. The particular case of ALBA in which there is no aggregation is Least-Busy-Alternative (LBA). LBA and ALBA(2), which represent the two extremes of aggregation, are examined thoroughly in the paper. We compare simulation and analytic results for LBA and find the agreement surprisingly good. The structure of solutions computed here for LBA imply that with just a few properly designed aggregates it is possible to closely approximate the solution (and thus performance) of LBA. This is confirmed by results presented here on the comparative performances of LBA and ALBA(2). We also consider two separate asymptotic scalings based on the Fixed Point Models. The first shows that there is a dichotomy in network behavior: if the offered traffic is below a threshold then the network loss probability decreases exponentially with increasing network size, and above the threshold performance is poor. Hence the threshold approximately dilineates ``engineered'' designs. In the second asymptotic scaling the asymptotically optimum trunk reservation parameter is obtained as the solution of a simple equation. Such asymptotically optimal designs are compared with the outputs of exhaustive numerical searches for some realistically sized networks and the differences are found to be small.