资源描述：
《基于信源路由的时延受限点到点路由算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第4期电子学报Vol.29No.42001年4月ACTAELECTRONICASINICAApril2001基于信源路由的时延受限点到点路由算法张宝贤,刘越,陈常嘉(北方交通大学通信与信息工程系,北京100044)摘要:本文研究了网络路由中的一个NPC问题:时延受限最小代价路由问题.文中提出了一个理论框架,并给出了多个简单有效的启发式算法,在满足给定时延约束条件可行路径存在时,算法总能找到满足约束条件的代价优2化路径.文中提出的启发式算法复杂性为O(
2、V
3、)且在线复杂性为O(
4、V
5、).仿真显示算法取得了
6、良好的平均代价性能.最后将模型扩展到多QoS限制条件下的路由问题.关键词:时延受限;服务质量路由;信源路由中图分类号:TN9191文献标识码:A文章编号:03722112(2001)04051005SourceBasedDelayConstrainedUnicastRoutingAlgorithmsZHANGBaoxian,LIUYue,CHENChangjia(DepartmentofCommunicationandInformationEngineering,NorthernJiaotongU
7、niversity,Beijing100044,China)Abstract:Inthispaper,westudytheNPharddelayconstrainedleastcostroutingproblem.Weproposeanewframeworktosolvetheproblemandprovidesimpleandefficientsourceroutingheuristicsfromthemodel,throughwhichonecanalwaysfindadelay2constrainedpathifsu
8、chapathexists.ComputationcomplexityofourheuristicsisO(
9、V
10、)andonlinecomplexityisO(
11、V
12、).Simulationresultsshowthatourheuristicsachievegoodcostperformance.Finally,weextendthemodeltoroutingproblemundermultipleQoSconstraints.Keywords:delayconstrained;QoSbasedrouting;sou
13、rcerouting1引言C(P(s,d))=!eP(s,d)C(e)(1)许多新的实时应用的出现,如:多媒体业务,对网络路由类似,定义路径P(s,d)的端到端时延:算法产生了很大的影响.这些应用对时延敏感,并且占用大量D(P(s,d))=!eP(s,d)D(e)(2)网络资源.因此对路由机制提出了如下要求:(1)满足实时应[2]时延受限最小代价路由(DCLC)问题可以表述为:对于用的端到端时延要求;(2)有效地管理网络资源.当前Internet++有向图G=(V,E),给定链路时延函数,D:E∀R(R是除0上的路由机制主
14、要根据最短路径算法,它只能在给定的单个+以外的正实数集合),链路代价函数,C:E∀R,给定信源s,代价准则下找到基于最短时延或最多某种可用资源的路径.[1]信宿d和时延约束,寻找有向路径P(s,d),满足:寻找满足时延约束的最小代价路径是一个NPC问题.因此D(P(s,d))<(3)设计简单、有效、可扩展的启发式算法,不仅具有重要意义,而且最小化C(P(s,d)).这是一个NP问题.且有很大的挑战性.3理论框架2问题的形式化表示本文提出的模型在更高的层面上将网络看成由超级链路给定有向简单图G=(V,E),其中V是顶点
15、的集合,E是组成的超图,超级链路指网络中两点间的最短时延(LD)路径有向边的集合.对于任意有向边e=(u,v)E,定义两个重或最小代价(LC)路径,超图上路径(v1,,vm)是由所有从量函数C(e)和D(e).其中D(e)表示分组经过链路e时所经vi-1到vi的超级链路组成的.对于给定s和d,称由s、d确定历的时延的测度.C(e)可以是链路使用价格或链路某些网络n资源使用状态的测度.给定信源s和信宿d,链路集合e1=的n阶超图SGn(s,d)由顶点集合{s,d}#V组成(图1(d)).(s,v2),e2=(v2,v3),,ek=(
16、vk,d)构成了从s到d的有向超级链路的使用和仅考虑两个出行方向(最小代价和最短时路径P(s,d).路径P(s,d)的代价定义如下:延方向)分析问题均不是全新的概念,本文的主要贡献是将两收稿日期:20000103;修回日期:200
