Load-Balanced Shortest-Path-Based Routing without Traffic Splitting in Hose Model
Shunichi Tsunoda, Abu Hena Al Muktadir, Eiji Oki · 2011
Smart OSPF (S-OSPF), a load balancing, shortest-path-based routing scheme, was introduced to improve the routing performances of legacy networks running OSPF with known traffic demands. S-OSPF distributes traffic from a source node to neighbor nodes, and, after reaching the neighbor nodes, traffic is routed according to the OSPF protocol. However, in practice, exact traffic demands are difficult to obtain, and most routers will not be able to handle the complexity of determining and implementing uneven traffic distributions with any form of precision. This paper investigates non-split S-OSPF with the hose model for the first time; its goal is to minimize the worst-case network congestion ratio. In this model, traffic from a source node to a destination node is not split over multiple routes, in other words, it goes via only one neighbor node to the destination node. The routing decision problem with the hose model is formulated as an integer linear programming (ILP) problem. Since it is difficult to solve the ILP problem in practical time, this paper proposes a heuristic algorithm. In the routing decision process, the proposed algorithm gives the highest priority to the node pair that has the highest product of ingress and egress traffic, and enables a source node to select the neighbor node that minimizes the maximum link utilization over all links for the worst case traffic condition specified by the hose model. We compare non-split S-OSPF to split S-OSPF and classical shortest path routing (SPR). Numerical results show that the non-split S-OSPF scheme improves routing performance versus classical SPR and is comparable to the split S-OSPF scheme for larger networks.