OPTIMAL VIRTUAL PATH LAYOUT IN ATM NETWORKS WITH SHARED ROUTING TABLESWITCHES

In this paper we present a new model for routing that occurs in high-s peed ATM networks. Within this model we define a general routing probl em, called a virtual path layout. Given a network of nodes (switches) and links, one must find a set of paths in the network, termed the vir tual path layout, whereby each pair of nodes may connect using a route that is a concatenation of a small number of virtual paths and is als o short in terms of the network links it traverses. Each such layout i mplies a utilization of the routing tables in the network's nodes. Our goal is to find a layout that minimizes this utilization, assuming th at each such node has a central routing table. We prove that this prob lem is NP-complete, and consequently focus on a simpler problem, in wh ich it is required to connect all nodes to a single switch. Next, we p rove that even this problem is NP-complete, and restrict some of the a ssumptions to yield a practical subproblem, for which we present a pol ynomial-time greedy algorithm that produces an optimal solution. Final ly, we use this restricted problem as a building block in finding a su boptimal solution to the original problem. The results exhibit a trade off between the performance of a routing scheme and its resource utili zation.