Optimal routing by hose model with bound of link traffic
Optimal routing by hose model with bound of link traffic
复制标题
DOI：
10.1049/iet-net.2012.0063
复制
发表时间：
2012-10
期刊：
影响因子：
1.4
通讯作者：
E. Oki;Y. Kitahara;I. A. Ouédraogo
中科院分区：
文献类型：
--
作者：
E. Oki;Y. Kitahara;I. A. Ouédraogo
提出了一种基于带链路流量界限的软管模型的最优路由策略(HLT-m)。除了软管模型中描述的流量界限外，HLT还由通过每条链路的总流量指定。由准确的流量矩阵表示的管道模型提供了最佳的路由性能，但流量矩阵难以准确测量和预测。尽管软管模型仅使用进出每个节点的总传出/传入流量，但由于流量信息不足，它提供的路由性能低于管道模型。具有源-目的地流量界限(HSDT-m)的软管模型是介于管道和软管模型之间的结构，但对于网络运营商来说，确定附加界限并不容易，其中源-目的地对的流量需求的上界和下界被添加为约束。HLT-m减轻了管道模型的难度，但缩小了软管模型指定的交通条件范围，提供了比软管模型更好的布线性能。此外，HLT-m解决了HSDT-m在确定适当的附加界方面的困难。从管道模型扩展到HLT-m的最优布线公式不能作为常规的线性规划问题来求解。我们的解决方案，引入了对偶定理，将这个问题变成了一个容易求解的LP公式。仿真结果表明，对于所考察的网络，HLT-m比Hose模型的网络拥塞率低20%~35%。此外，PIPE和HLT模型的拥堵比相差不到0.1。HLT-m的上限和下限利润率分别为25%和20%，其性能几乎与HSDT-m相同。
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.