Load-Balanced Non-split Shortest-Path-Based Routing with Hose Model and Its Demonstration

Shunichi TSUNODA  Abu Hena Al MUKTADIR  Eiji OKI  

IEICE TRANSACTIONS on Communications   Vol.E96-B   No.5   pp.1130-1140
Publication Date: 2013/05/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E96.B.1130
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Internet
routing,  load balancing,  OSPF,  hose model,  

Full Text: PDF(1MB)>>
Buy this Article

Smart OSPF (S-OSPF), a load balancing, shortest-path-based routing scheme, was introduced to improve the routing performances of networks running on OSPF assuming that exact traffic demands are known. 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 the distribution of unequal traffic to multiple neighbor nodes requires complex functionalities at the source. This paper investigates non-split S-OSPF with the hose model, in which only the total amount of traffic that each node injects into the network and the total amount of traffic each node receives from the network are known, for the first time, with the goal of minimizing the network congestion ratio (maximum link utilization over all links). In non-split S-OSPF, 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 with the hose model is formulated as an integer linear programming (ILP) problem. Since the ILP problem is difficult to solve in a 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 the total amount of injected traffic by one node and total amount of received traffic by the other node in the pair, where both traffic volumes are specified in the hose model, and enables a source node to select the neighbor node that minimizes network congestion ratio for the worst case traffic condition specified by the hose model. The non-split S-OSPF scheme's network congestion ratios are compared with those of the split S-OSPF and classical shortest path routing (SPR) schemes. Numerical results show that the non-split S-OSPF scheme offers lower network congestion ratios than the classical SPR scheme, and achieves network congestion ratios comparable to the split S-OSPF scheme for larger networks. To validate the non-split S-OSPF scheme, using a testbed network experimentally, we develop prototypes of the non-split S-OSPF path computation server and the non-split S-OSPF router. The functionalities of these prototypes are demonstrated in a non-split S-OSPF network.