A QOS-BASED ROUTING ALGORITHM FOR PNNI ATM NETWORKS

Abstract

Path selection in network routing has typically been formulated as a shortest path problem. Efficient shortest path algorithms, such as Dijkstra and Bellman-Ford, can determine a path of concatenated links connecting source to destination such that a predefined objective is optimised. As B-JSDN standards and ATM networks emerge, modern networks are expected to provide a wide range of services and guarantee various end-to-end quality of services (QoS). The QoS requirements and the complex trade-offs among them make it difficult to define a single routing metric. Besides, there is also the problem of routing in a dynamic environment clue to fluctuations in traffic load, link failures and topology changes. In response to the challenges in ATM network routing, the ATM Forum has proposed the Private Network-Network Interface (PNNI) Specification, which consists of a routing protocol and a signaling protocol. However, path selection or routing algorithms that guarantee a user's multiple QoS requirements remain an open issue since the PNNI protocol only provides a routing framework and does not standardize on a method of finding an appropriate path. In this thesis, we propose a heuristic routing algorithm called Backward Hierarchical Routing Algorithm (BHRA) for ATM networks, which is compliant with the PNNI protocol. BHRA uses an adaptive and iterative path search approach and takes advantage of the PNNI hierarchical network structure. It consists of three components: The first component is the path selection algorithm which is again divided into three steps. First, paths are pre-calculated inside each peer group at each hierarchical level. A path-tree algorithm has been designed for this step. When a connection setup request is received, candidate paths are selected in each peer group beginning from the logical group, which is an ancestor of both the source and destination nodes, all the way down the hierarchy to the lowest level peer group. The last step involves building a hierarchically complete source route that is mostly likely to meet the QoS requirements from the set of available paths. The rerouting mechanism is the second component to provide fast recovery in the source routing algorithm. The last part of BI-IRA is the multi-class routing, which spreads best effort traffic evenly in the network to allow dynamic sharing of the link bandwidth among multiple traffic classes. The BHRA has been simulated using a network simulation tool called BONeS. The simulation results show that the call setup time has been reduced significantly. Computational overhead and call blocking probability are lowered as well. Moreover, the network throughput has been improved by evenly distributing the traffic among as many links as possible. Extensions to BHRA and PNNI protocols to support multicast arc discussed as a future work item. The extended BI-IRA multicast routing algorithm is presented followed by suggestions on issues such as multicast group membership management, multicast DTLs forwarding and leaf-initiated joining.