Routing for interconnected networks and high-speed wide area networks

In interconnected heterogeneous networks, a site is considered as a single autonomous system that has a complex set of networks and gateways. Each system generally has a different type of technology that is best suited to the geographical area that is being covered and the traffic characteristics of the applications using the network. The interconnected networks naturally form a hierarchy which consists of a nation-wide backbone, a set of regional networks, and a set of local area networks. The backbone generally consists of leased lines and channels interconnecting the regional networks. A typical regional network interconnects several autonomous environments that are clustered in a geographic area. The purpose of this dissertation is to propose ways of providing the routing schemes that are suitable for different networking environments at the regional and backbone level. A simple area routing algorithm for a two level network is proposed where autonomous areas are interconnected to each other via gateways and high speed links. Its main features consist of a decentralized inter area routing algorithm, with centralized routing functions within areas for inter area routing only. Routing within areas is assumed to be totally independent of the algorithm. A routing protocol for the communication between two adjacent autonomous networks which are connected to each other via a high speed hierarchical backbone network and a direct low speed local transmission facility (i.e. a non-strict hierarchy) is also proposed. By defining a proper objective function, the local transmission facility which is less expensive than the backbone transmission facility can be used efficiently. A dynamic multi-path routing scheme is proposed for a homogeneous high speed backbone network. The proposed scheme works as a shortest path first algorithm under light traffic conditions. However as the shortest path becomes congested, the source node uses multiple paths when and if available in order to distribute the load. It is able to bridge the gap between routing and congestion control as the network becomes congested. We then compare its performance to that of the other competitive routing algorithms, such as Alternate path routing, Trunk reservation, Random routing, and Shortest Path Only routing. In general, for most loading scenarios Multi-path routing displays lower cell losses which is an important consideration in Asynchronous Transfer Mode (ATM) networks that use the best effort delivery strategy and end-to-end packet loss recovery mechanisms