欢迎来到天天文库
浏览记录
ID:33584188
大小:237.18 KB
页数:10页
时间:2019-02-27
《source routing and scheduling in packet networks》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、SourceRoutingandSchedulinginPacketNetworksMatthewAndrewsyAntonioFern´andezzAshishGoelxLisaZhang{Abstract1IntroductionWestudyroutingandschedulinginpacket-switchednet-Twoofthemostimportantproblemsinthecontrolofworks.Weassumeanadversarythatcontrolsthei
2、njectionpacket-switchednetworksareroutingandscheduling.Thetime,source,anddestinationforeachpacketinjected.Asetgoalofroutingistoassignapathtoapacketfromitssourceofpathsforthesepacketsisadmissibleifnolinkinthenet-toitsdestination.Thegoalofschedulingist
3、odealwiththeworkisoverloaded.Wepresentthefirston-lineroutingal-contentionthatoccurswhentwoormorepacketswishtogorithmthatfindsasetofadmissiblepathswheneverthisiscrossalinksimultaneously.Eachlinkmusthaveasched-feasible.Ouralgorithmcalculatesapathforeachp
4、acketulerthatresolvesthiscontentionbydecidingwhichpacketassoonasitisinjectedatitssourceusingasimpleshortesttoadvance.pathcomputation.ThelengthofalinkreflectsitscurrentTheschedulingproblemtypicallyassumesthatthepathscongestion.Wealsoshowhowouralgorithm
5、canbeimple-ofthepacketsaregivenaspartoftheinput.Thegoalisthenmentedundertoday’sInternetroutingparadigms.toschedulethepacketsalongtheirpathsinsuchawaythatWhenthepathsareknown(eithergivenbytheadversarytheyallreachtheirdestinationsinashorttime.Muchre-or
6、computedasabove)ourgoalistoschedulethepacketscentworkhasfocusedontheAdversarialQueueingModel,alongthegivenpathssothatthepacketsexperiencesmalle.g.[7,2,8].Wefollowtheirconventionandassumethatend-to-enddelays.Thebestpreviousdelayboundsforde-allpacketsa
7、reunitsizeandeachlinkprocessesonepacketterministicanddistributedschedulingprotocolswereexpo-pertimestep.InthisAdversarialQueueingModel,thead-nentialinthepathlength.Inthispaperwepresentthefirstversarychoosestheinjectiontime,source,destination,anddeterm
8、inisticanddistributedschedulingprotocolthatguar-routeforeachpacketinjected.Asequenceofinjectionsisanteesapolynomialend-to-enddelayforeverypacket.calledFinally,wediscusstheeffectsofcombiningroutingwith(w;r)-admissibleforawindowsizewandinjectionrater<1
此文档下载收益归作者所有