source routing and scheduling in packet networks

《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