Ph.D Thesis

Ph.D StudentFelstaine Eyal
SubjectScalable Routing in Hierarchical ATM Networks
DepartmentDepartment of Computer Science
Supervisor PROF. Reuven Cohen


It is predicted that future global networks will use a hierarchical model that will be designed to scale to the largest topology possible thus encompassing billions of nodes. A typical hierarchical network consists of a hierarchy of subnetworks called domains or clusters. To allow scalability, domains do not reveal details of their internal structure to nodes in external domains. Instead, every domain advertises only a summary or aggregated view of its internal structure. The inherent difficulty in this ultra-scalable hierarchical network model is that wrong or non-optimal routing decisions are constantly being made as a result of topology aggregation which inevitably leads to the advertisement of inaccurate information.

In this work, we study the potentials and limitations of hierarchical networks in the context of ATM PNNI, which is the most comprehensive model for hierarchical routing. Our research focuses on several properties of hierarchical networks: (a) The data structures that are used for representing the clusters are generally succinct but inaccurate; if this were not the case, a huge communication and storage burden would be imposed on the network. (b) Changes in resources availability within the network are not advertised frequently. (c) Different nodes have distinct, partial and insufficient knowledge of the global network routing information. Hence, routing decisions are performed as

collaborative tasks done by several nodes.

We show how the above properties affect the efficiency of hierarchical networks and suggest several mechanisms to improve efficiency. We concentrate on: (a) Computation of unicast paths and multicast trees, and their optimality with respect to similar paths or trees in non-hierarchical networks. (b) The resources (computation, signaling and setup time) required to set up aconnection. (c) The distribution of the routing computation burden among the network nodes.

We investigate the route computation load imposed by the PNNI routing scheme, and show that this load is unevenly distributed among the network nodes. More specifically, the routing computation load associated with the setup of a single VC grows exponentially with the hierarchy level, some of the network nodes -- mainly those that function as border nodes of high levels clusters -- may be  overloaded with route computation, while other nodes rarely get involved in this process. We also propose a scheme for spreading the route computation burden more evenly. According to this scheme, heavily loaded nodes transfer route computation tasks to lightly loaded nodes.

We propose a novel scheme, referred to as crankback prediction, which addresses the fact that PNNI has high crankback overhead. The main idea behind the proposed mechanism is to allocate a “`quota”' to the clusters along the message path, and then to sub-allocate this quota to the child clusters. If the quota is exhausted before crossing a cluster, a crankback is triggered before valuable resources are wasted. We show that the scheme lowers the setup delay and the processing and communication load

imposed by signaling messages that establish unused portions of virtual channels.

Finally, we suggest a framework for the creation and maintenance of efficient QoS-enabled multicast trees in hierarchical networks. Here, the main objective is to distribute the tree topology information among a set of hierarchical Multicast Group Servers (MGSs) nominated for each multicast tree, while keeping regions that do not have a member in the multicast group unaware of the tree. The framework can be employed with any multicast routing algorithm designed for non-hierarchical networks.

The ideas presented in this dissertation are in the context of ATM PNNI, which is the most comprehensive model for hierarchical routing. However, they can be adopted to other hierarchical routing protocols in packet-switched or circuit-switched models. Though IP rarely uses hierarchical routing protocols, researchers in the Internet Engineering Task Force routing area working group, believe that eventually (10 years from now ?) IP routing will collapse unless topology aggregation mechanisms are used. A notable move towards a topology aggregation-based framework is the Multicast Source Discovery protocol (MSDP) , where multicast sources are aggregated to lists by domain leaders. The emerging inter-domain routing protocols and the IPv6 aggregatable global unicast address format are other steps that have been taken to advance the IP network model towards a hierarchical model.