资源描述：
《云物流实例资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、RoutingPrinciplesInordertotransferpacketsfromasendinghosttothedestinationhost,thenetworklayermustdeterminethepathorroutethatthepacketsaretofollow.Whetherthenetworklayerprovidesadatagramservice(inwhichcasedifferentpacketsbetweenagivenhost-destinationpairmaytakedifferentroutes)o
2、ravirtualcircuitservice(inwhichcaseallpacketsbetweenagivensourceanddestinationwilltakethesamepath),thenetworklayermustnonethelessdeterminethepathforapacket.Thisisthejobofthenetworklayerroutingprotocol.Attheheartofanyroutingprotocolisthealgorithm(the"routingalgorithm")thatdeter
3、minesthepathforapacket.Thepurposeofaroutingalgorithmissimple:givenasetofrouters,withlinksconnectingtherouters,aroutingalgorithmfindsa"good"pathfromsourcetodestination.Typically,a"good"pathisonewhichhas"leastcost,"butwewillseethatinpractice,"real-world"concernssuchaspolicyissue
4、s(e.g.,arulesuchas"routerX,belongingtoorganizationYshouldnotforwardanypacketsoriginatingfromthenetworkownedbyorganizationZ")alsocomeintoplaytocomplicatetheconceptuallysimpleandelegantalgorithmswhosetheoryunderliesthepracticeofroutingintoday'snetworks.Figure4.2-1:Abstractmodelo
5、fanetworkThegraphabstractionusedtoformulateroutingalgorithmsisshowninFigure4.2-1.(Toviewsomegraphsrepresentingrealnetworkmaps,see[Dodge1999];foradiscussionofhowwelldifferentgraph-basedmodelsmodeltheInternet,see[Zegura1997]).Here,nodesinthegraphrepresentrouters-thepointsatwhich
6、packetroutingdecisionsaremade-andthelines("edges"ingraphtheoryterminology)connectingthesenodesrepresentthephysicallinksbetweentheserouters.Alinkalsohasavaluerepresentingthe"cost"ofsendingapacketacrossthelink.Thecostmayreflectthelevelofcongestiononthatlink(e.g.,thecurrentaverag
7、edelayforapacketacrossthatlink)orthephysicaldistancetraversedbythatlink(e.g.,atransoceaniclinkmighthaveahighercostthanaterrestriallink).Forourcurrentpurposes,wewillsimplytakethelinkcostsasagivenandwon'tworryabouthowtheyaredetermined.Giventhegraphabstraction,theproblemoffinding
8、theleastcostpathfromasourcetoadestinationrequiresidentifyinga
