Optimal routing by hose model with bound of link traffic

This study presents an optimal routing strategy based on the hose model with bounds of link traffic (HLT-m), which the authors introduce. HLT is specified by the total traffic passing through each link in addition to the traffic bounds described in the hose model. The pipe model, which is specified by the exact traffic matrix, provides the best routing performance, but the traffic matrix is difficult to measure and predict accurately. Although the hose model employs only the total outgoing/incoming traffic from/to each node, it offers lower routing performance than the pipe model, because of insufficient traffic information. The hose model with bounds of source-destination traffic (HSDT-m), where the upper and lower bounds of traffic demands for source-destination pairs are added as constraints, is a construction that lies between the pipe and hose models, but determining additional bounds is not easy for the network operators to specify. HLT-m, which lightens the difficulty of the pipe model, but narrows the range of traffic conditions specified by the hose model, offers better routing performance than the hose model. In addition, HLT-m resolves the difficulty of HSDT-m with regard to determining appropriate additional bounds. An optimal-routing formulation extended from the pipe model to HLT-m cannot be solved as a regular linear programming problem. Our solution, the introduction of a duality theorem, turns this problem into an LP formulation that can be easily solved. Numerical results through simulations show that for the examined network, HLT-m offers 20-35% lower network congestion ratios than the hose model. In addition, the congestion ratios of the pipe and HLT models differ by less than 0.1. With upper-bound and lower-bound margins of 25 and 20%, respectively, HLT-m offers almost the same performance as HSDT-m.