【摘要】 Qo S路由的 DCL C单播路由 (Delay- Constrained L east- Cost Unicast Routing)问题属于 NP—完全问题 .本文提出一种多项式复杂度的分布式启发算法 DCL C- DSF.DCL C- DSF基于简单的选择函数 ,每个网络结点只需维持本地的状态信息 :相邻链路的延时和代价度量 .该算法有以下优点 :1)简单性 ;2 )动态性 ;3)重路由功能 ;4)协商功能 .在最坏情况下 ,DCL C- DSF的消息复杂度为 O(e2 ) ,结点的计算复杂度为 O(n2 ) ;在稳定的网络环境下 ,消息复杂度为 O(e) .此外 ,本文还给出 DCL C- DSF算法的有限状态机模型 .仿真实验表明 :DCL C- DSF算法的平均代价不精确度是最佳算法的 5 - 8% ,证明它是一种简单、精确、健壮的启发式算法 .更多还原

【Abstract】 Delay-constrained least-cost unicast routing problem is NP-Complete. In this paper, we present a distributed heuristic algorithm, called the distributed DCLC unicast routing heuristic based on selection function (DCLC-DSF). DCLC-DSF, which is a dynamic routing algorithm with re-routing and negotiation mechanism, only requires the local information to be kept at each node: the delay and cost of neighbor links. In the worst case, Its message complexity of DCLC-DSF is O(e\+2), and the computation complexity of each node is O(n\+2). While for a stable network, the message complexity is O(e). The simulation results also show that, on the average, DCLC-DSF requires much fewer messages. Therefore, DCLC-DSF scales well to large-scale networks. We picture the protocol of DCLC-DSF by a finite state machine. We also use simulation to compare DCLC-DSF to the optimal DCLC algorithm CBF and the least-delay path algorithm LDP. The results show that DCLC-DSF path costs are within 5-8% from those of the optimal solution, which proves that DCLC-DSF is a simple, accurate and robust heuristic algorithm.更多还原