Broadband Networks

Optimization of static routing approaches in special graph classes

All routing approaches that have been published to date differ in their respective approach to adapt to the actual state of the communication network. While using adaptive routing approaches (also known as dynamic approaches) changes in the actual network state are taken into consideration in the routing tables (e.g. link failures). Contrary to static approaches where these changes are not taken into consideration in the routing tables. Although in the past years static routing approaches were substituted by dynamic approaches, users prefer and will probably continue to prefer static approaches when time critical applications are in use. By applications such as the Signaling System Nr. 7 Protocol used for signaling issues in telecommunication networks, the delay, before nodes which are far away can adapt their routing tables to take the link failure into account, is not acceptable.

However, algorithms which are very powerful can only use their strength to their fullest potential if the configuration of network nodes and related links is adequate. Therefore attempts were made to design algorithms which even in case of link failure would always find the shortest path from the sender to the receiver.

There are no static routing approaches for arbitrary graphs, which are optimal with regard to cycle-freedom and shortest path even when link failures occur. Based on this fact, special graph classes were looked at, which allowed optimal routing based on selected criteria. Furthermore practice relevant criteria were defined for suboptimal graph classes. An attempt was made to reduce the link complexity of fully connected graphs, without eliminating their positive characteristics. For such suboptimal graphs the efficiency which was defined as “the percentage of all routing processes, for which the routing tables of graphs even if a link failure occurs contain the shortest paths” was analyzed.

In addition, approaches were looked at to determine if an arbitrary graph G´ is isomorphic to an optimal graph Go or suboptimal graph Gs. Algorithms were developed and implemented for practical use which provide a structure conserving mapping or  link conserving mapping for a subgraph Gt of Gs.


Prof. Firoz Kaderali Print