文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 4 Basic routing theory II – Adaptive routing
侵权投诉

4 Basic routing theory II – Adaptive routing

In this section we look at adaptive routing, i.e. the path taken by a packet may not only depend on its source and destination but also on the current situation in the network. Adaptive routing has several advantages over oblivious routing: ? It is possibl

4BasicroutingtheoryII–Adaptiverouting

Inthissectionwelookatadaptiverouting,i.e.thepathtakenbyapacketmaynotonlydependonitssourceanddestinationbutalsoonthecurrentsituationinthenetwork.Adaptiveroutinghasseveraladvantagesoverobliviousrouting:

Itispossibletoachievegoodroutingresultswithdeterministicadaptiveroutingstrategies,whereasweknowfromtheBorodin-Hopcroftlowerboundthatdeterministicobliviousroutingstrategiesmayperformpoorlyincertainsituations.

Manyadaptiveroutingstrategiescanadaptquicklytofaultynodesoredgesinthenetwork,whereasinobliviousroutingfaultynodesoredgesmaydisconnectcertainsource-destinationpairsandthereforemayrequirethecomputationofnewpathsystem,whichmaybeexpensive. Thecongestionofadaptiveroutingstrategiescanbebetterthanwhatcanbeachievedbyobliv-

Piousroutingstrategies.(Notethelowerboundof (COPTlogn)forobliviousroutingonthe

mesh.)

However,adaptiveroutingusuallyalsohassomeweaknesses:

Ahighfreedomofchoosingapathforapacketmaycausehighdelaysforthepackets,sinceitmaytakeawhileuntilthealgorithmconvergestowardsgoodpaths.

Adaptiveroutingmaycreateadditionalcommunication(becausemanyofthemneedcontrolpackets)andmayhavemuchhigherdemandsonthehardwareandsoftwarethanobliviousrout-ing(seethealgorithmsbelow).

Theanalysisofadaptiveroutingisusuallymuchharderthanforobliviousrouting.Therefore,wewillmostlyrestrictourselvestopresentingalgorithmsinthissection.

Adaptiveroutingusuallyworksonapacket-basedscale,andeverypacketmayfollowadifferentpath.Therefore,itisoftennotpossibletosimplifytheproblemofroutinginformationwhenusinganadaptivealgorithmtoaproblemofshipping owthroughthenetworkaswediditforobliviousrouting.Instead,wewillassumeinthefollowingthatinformationissentintheformofunit-sizepackets.Everynodehasso-calledbuffersinwhichpacketsintransitcanbestored.Onceapacketreachesitsdestination,itisabsorbed.Tokeepourmodelssimple,weassumethateveryedgecantransmitonlyonepacketineachdirectioninatimestep.

Severaladaptiveroutingapproacheshavebeensuggestedinthepast.Someofthemare:

Adaptiveroutingbasedonpathsystems:Hereapathsystemsimilartoanobliviouspathsystemmaybegiven.However,insteadofrandomlyselectingapathforapacketfromitsoptions,apathmaybechosenbasedonthecurrentsituationinthenetwork.

Adaptiveroutingbasedonedgecosts:Inthiscaseeveryedgeisassociatedwithacost,andthegoalisusuallytoselectapathforapacketwithminimalcost.ThisisthestandardapproachofroutingprotocolsusedintheInternet(suchasRIPandOSPF).

第1页

你可能喜欢

热门文档

相关文档

  • Routing_basic

    4 Basic routing theory I... 8页 免费 Module 6 - Basic Routing... 暂无评价 31页 免费 1 Constraint-Based Routi... 暂无评价 15页 免费 A basic ...

  • 2.1 Basic theory...

    (II)Basic Circuit Theory 8页 2财富值 2.Basic Circuit Theory 高... 8页 免费 4 Basic routing theory I... 8页 免费 Chapter 2 signal analysi... ...

  • 我要MVC潜规则之配置Routing(4)

    我要MVC潜规则之配置Routing(4)_计算机软件及应用_IT/计算机_专业资料。Mvc3教程我要学 ASP.NET MVC 3.0(四) 我要 MVC 潜规则之配置 Routing : 概述使用...

  • ch4_data_routing

    ? Routing schemes can also divided into static or adaptive according to the...– Start by introducing some basic graph-theoretic notions. 2015-1-13 ...

  • Routing_Protocol_Basic

    Routing_Protocol_Basic_计算机硬件及网络_IT/计算机_专业资料。Routing Basic 黄永刚 CCIE 之路系列 Huang Yonggang 2011/9/9 Routing Basic 2011 年 9 月 9...

  • ...Theory with Applications to Adaptive Routing_免...

    Evolutionary Game Theory with Applications to Adaptive Routing? Simon Fischer...their routing strategies from time to time depending on the observed ...

  • NS2 routing

    NS2 routing_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 NS2 routing_IT/计算机_专业资料。NS2中添加新路由协议的一般方法【转】...

  • Adaptive Routing Using Expert Advice

    10.1093/comjnl/bxh000 Adaptive Routing Using ...Theory, Budapest University of Technology and ...information is combined to update the routing ...

  • Adaptive Routing Strategies for Modern High Perform...

    Then, we implement and evaluate basic dispersive routing mechanisms, before proposing an adaptive routing scheme that increases the effective bisection bandwidth...

  • Routing (4)

    5.1 RIPv1: Distance Vector, Classful Routing Protocol ? 5.2 Basic RIPv1 Configuration ? 5.3 Verification and Troubleshooting ? 5.4 Automatic ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email