Improving the Efficiency and Obtaining Optimality in Link State Routing.

Efforts are being made since decades to improve the efficiency of routing, particularly link state routing. Our paper aims in making the routing optimal by reducing the cost of carrying traffic through packet switched networks. Link state routing protocols like OSPF and IS-IS converge more quickly than the distance vector routing protocols such as RIPv1, RIPv2, EIGRP and others. This is achieved using flooding and triggered update techniques. In link state protocols the updates are flooded immediately and computed in parallel. Triggered updates improve convergence time by making routers send update messages immediately upon learning of a route change. These updates are triggered by events such as new link becoming available for the failure of existing link. Main drawbacks are CPU overhead and memory requirements. Our technique iteratively and independently updates the fraction of traffic destined to the node that leaves the source node on each of its outgoing links. For every iteration the updates are calculated based on shortest on each destination as determined by the marginal cost of the networks links. These costs are obtained by link state updates which are flooded through the network after each iteration. The technique is adaptive which automatically converges to the new optimal routing assignment for apparently static network changes. Main aim is to eliminate the tradeoff between optimality and ease of implementation and routing.