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 imposing restrictions on paths and flows. We then study how these modifications 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 traditional queuing delays, queuing is treated indirectly using penalty terms for “effective” capacity constraints; and 3) high- and low-priority flows—because of higher grade-of-service requirements for high-priority flows, additional capacity constraints are imposed on 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 number of routes used between node pairs and then analyze numerically how many distinct routes are typically used by the final solution from the flow-deviation algorithm when no route limits exist between node pairs.