Packet routing in telecommunication networks with path and flow restrictions

We address packet-switched telecommunication networks, including ATM, SMDS, and X.25 services. We analyze important extensions of routing models by im posing restrictions on paths and flows. We then study how these modificatio ns affect the computational requirements for solution. The restricted cases we examine are: 1) hop limits-the flow between each pair of nodes can take a maximum of h hops; 2) node and link capacity constraints-instead of trad itional queuing delays, queuing is treated indirectly using penalty terms f or "effective" capacity constraints; and 3) high- and low-priority flows-be cause of higher grade-of-service requirements for high-priority flows, addi tional capacity constraints are imposed an them. We discuss the importance of these restrictions and report results of computational testing using the flow-deviation algorithm. We also discuss the importance of limiting the n umber of routes used between node pairs and then analyze numerically how ma ny distinct routes are typically used by the final solution from the flow-d eviation algorithm when no route limits exist between node pairs.