COMPARATIVE EVALUATIONS OF RANDOMIZED AND DYNAMIC ROUTING STRATEGIES FOR CIRCUIT-SWITCHED NETWORKS

The theory and practice of circuit switching on networks has recently been rapidly evolving. We investigate two fundamentally separate classes of routing algorithms-randomized and deterministic. The main randomized algorithm is Gibbens' and Kelly's recently introduced Dynamic Alternate Routing. In the contrasting deterministic algorithm, attempts to carry a call are made in a specific precomputed order. The design of these routing sequences given here is new and depends upon i) analytic approximations based on fixed-point equations to evaluate network performance, and ii) heuristics for the rather complicated problem of network revenue maximization. In all cases, an important role is played by the control mechanism of trunk reservations. Our test bed is a network of six nodes which is fully connected, except when we study the effects of various link failures. The network data are quite nonuniform and extracted from a realistic network. Our primary tool in this study is discrete-event simulation. We give results for each of the following goals: i) to evaluate and compare performance, primarily in terms of revenue generated; ii) to evaluate performance in the event of link failures; iii) to develop innovative design tools, iv) to develop an appreciation of the time constants of the various algorithms; and v) to propose new algorithms, especially hybrids.