工程硕士班《通信网理论基础》

通信网理论基础

第三部分图论基础与应用1.基本概念图G(V,E)

由两个集合加以定义:顶点(或节点)集合

V={v1,v2,v3….vn};边集合

E={e1,e2,e3……em};G={V,E}边由一对直接关连的顶点的组合定义如果:(i,j)E,则顶点i和j称为相邻的顶点的数目称为图的“阶”;边的数目称为图的“尺寸”;许多图的算法的运行时间与图的“阶”和“尺寸”相关2.图的一个例子3.图的邻接矩阵邻接矩阵是用数学方式来表示图顶点编号:1,2,3,…,|V||V|x|V|邻接矩阵

A=(ai,j)定义为:ai,j=1if(i,j)E(ij是图的一条边)0otherwise对于边没有方向性的图(即边的两顶点的顺序不影响边的性质),邻接矩阵A是对称矩阵.4.邻接矩阵一例5.Terminology关联同一对顶点的边称为:平行边关联同一顶点的边称为:环既无平行边,又无环的图称为:简单图顶点i到顶点j的路径是:

顶点和边的交替序列起于i,止于j;每条边只与序列中直接在它前面和直接在它后面的顶点相连简单路径:顶点和边在序列中只出现一次的路径

在简单图中,简单路径可以由顶点序列来定义每个顶点与序列中在其前面和后面的顶点相邻序列中没有重复的顶点6.简单路径(1)由V1到

V6(不完全)V1,V2,V3,V4,V5,V6V1,V2,V3,V5,V6V1,V2,V3,V6V1,V2,V4,V3,V5,V6V1,V2,V4,V5,V6V1,V3,V2,V4,V5,V6V1,V3,V6V1,V4,V3,V6总共14条(其余的请自行列出)7.简单图(2)两顶点间的所有路径中有一条最短路径,如:V1,V3,V6顶点间的距离是所有路径中边数最少的路径的边的数目回路是起于和止于同一顶点的路径例如:.V1,V3,V4,V18.有向图边有方向性的图有向图G(V,E)的边由一对顶点的有序组合来定义代表边的线段用箭头表示其方向允许存在平行边,只要它们的方向相反便于用图表示通信网络每条有向边表达一个方向上的数据流仍然可用邻接矩阵表示除非每对相邻的顶点用平行边连接,否则邻接矩阵是不对称的9.加权图或加权有向图每条边有一与之关联的数(权值w)-------便于说明路由算法邻接矩阵定义为:

ai,j=

wi,jif(i,j)E0otherwisewi,j是与边(i,j)关联的权值路径长度是权值之和最短距离路径不一定是长度最短路径(见下面两张PPT)10.加权图与邻接矩阵11.V1

至V6

的路径距离和路径长度路径 距离长度V1,V2,V3,V4,V5,V6 5 11V1,V2,V3,V5,V6 4 8V1,V2,V3,V6 3 10V1,V2,V4,V3,V5,V6 5 10V1,V2,V4,V5,V6 4 7V1,V3,V2,V4,V5,V6 5 16V1,V3,V6 2 10V1,V4,V5,V6 3 412.树树是图的子集以下几项定义是等效的:*树是一种简单图,顶点i

和j之间只有一条简单路径*N个顶点的简单图如果只有N-1条边,没有回路*N个顶点的简单图如果只有N-1条边,而且是连通的可以指定一个顶点为“根”根通常画在上部与根邻接的顶点画在下一层这些顶点可以到达树根,路径距离为113.树中顶点的等级关系每个顶点(除根外)有一个父顶点靠根一边的邻接顶点每个顶点有0个或几个子顶点离根远的邻接顶点没有子顶点的顶点称为叶层次等级直接在根下面的顶点是第一层第一层顶点的子顶点是第二层14.

树的例15.子图从图G中选择一些边和顶点构成G的子图每条被选上的边的两个关联顶点必须同时选上图G’(E’,V’)是图G(E,V)的子图,如果:V’V,

E’E

并且对每一条E’中的边e’.如果e’

关联v’andw’,

则v’,w’V’16.生成树图G的子图T是一颗生成树,如果:T

是树

包含G的所有顶点从图G中删去一些边,使所有的回路不复存在,但保持图的连通性:图G的生成树通常并不唯一17.生成树的例子18.生成树的“先广搜索”算法将顶点划分成不同的层次在处理下一层之前,先处理完本层的所有顶点从任一顶点x开始指定它为0层所有它的邻接顶点属于1层设Vi1,Vi2,

Vi3,…

Vij,是i层的顶点所有Vi1的邻接顶点中不属于1,2,…,i层的顶点指定为(i+1)层所有Vi2的邻接顶点中不属于1,2,3,…,i,(i+1)层的顶点也指定为(i+1)层直到所有顶点被处理完毕19.例选择顶点顺序如:V1,V2,V3,V4,V5,V6选择“根”例如V1现在树T只包含一个顶点V1,不含边在树上增加边(V1,x)和顶点x,但不要形成回路:将边(V1,V2),(V1,V3),(V1,V4)和顶点V1,V2,V3加入到树中,这是第一层在第一层的顶点上按序重复上述过程,得到第二层是否所有顶点都处理完?如果没有,在第二层的顶点上重复处理过程,得到第三层….…20.上例的图示21.AvoidingLoopsLAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)22.AvoidingLoopsLAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)23.SpanningTreeAlgorithmSelectarootbridgeamongallthebridges.rootbridge=thelowestbridgeID.Determinetherootportforeachbridgeexcepttherootbridgerootport=portwiththeleast-costpathtotherootbridgeSelectadesignatedbridgeforeachLANdesignatedbridge=bridgehasleast-costpathfromtheLANtotherootbridge.designatedportconnectstheLANandthedesignatedbridgeAllrootportsandalldesignatedportsareplacedintoa“forwarding”state.Thesearetheonlyportsthatareallowedtoforwardframes.Theotherportsareplacedintoa“blocking”state.24.LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)25.LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)Bridge1selectedasrootbridge26.LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)RootportselectedforeverybridgeexceptrootportRRRR27.最短距离路径的距离BFS算法可以得到从根顶点s到所有其他顶点的最短距离路径和距离δ(s,v)

任何从s

到v的路径中BFS给出的路径是距离最短的,即该路径边数之和最小。28.最短长度路径分组交换,帧中继,ATM等网络可以看作一张图每个节点是图中一顶点每一链路是一对平行边对于互联网(Internet或intranet)每个路由器是一个顶点如路由器直接相连,双向连接相当于一对平行边如多于两个路由器,则由多对平行边构成表示网络的图一对边连接一对路由器为将分组由源送到目的,需要路由决策等效于在图上找出路径29.路由决策基于最小代价最少跳数(hop)每条边(一跳)的权重为1相当于最短距离路径或者,每跳有一相关联的代价(见下一PPT)路径的代价是路径中各链路的代价之和需要找出最小代价路径相当于加权图中的最小长度路径30.一跳的代价反比于路径的容量正比于当前的负荷链路的货币价值几种因素的组合在不同方向上的代价可能不同31.Dijkstra算法(1)–定义

N=网络顶点的集合s=源顶点(起始点)T=到目前为止算法已经用到的顶点的临时集合Tree=T中顶点组成的生成树,它包括从s到T中每个顶点的最小代价路径上的边w(i,j)=从顶点i到顶点j的链路代价,w(i,i)=0w(i,j)=ifi,j不直接连接w(i,j)0ifi,j直接连接L(n)=当前知道的从s到n的最小代价路径的代价cost运算结束是它就是从s到n的最小代价路径的代价32.Dijkstra算法(2)–步骤初始化T=Tree={s}–临时顶点集合中暂时只含源顶点L(n)=w(s,n)forns;到邻点的初始路径代价就是链路代价取下一个顶点找xT使L(x)=minL(j),jT将x加入到T和Tree中将关联x,且使L(x)成为最小代价的边加入到Tree中它是路径的最后一跳更新最小代价路径L(n)=min[L(n),L(x)+w(x,n)]nT如果后一项最小,从s到n的路径就是从s到x的路径与从x到n的边的连接33.Dijkstra算法原理图示TSNXnw(x,n)L(n)L(x)已算出最短路径的点的集合找xT使

L(x)=minL(j),jT

x→TL(n)=min[L(n),L(x)+w(x,n)]nT所以，S需要知道w(x,n)-----各点与其邻点间直接相连链路的代价因而需要与所有其他各点交换路由信息某点（s)已知网络中其他各点到其邻点的链路的代价值w(x,n),计算S到其他各点的最短路径34.Dijkstra’s算法(3)–说明当所有顶点都加入到T以后,算法结束需要|V|次迭代结束时L(x)是s到x的最小代价路径的代价值Tree是原图的一颗最小生成树定义了从s到其他顶点的最小代价路径每次迭代有一个新的顶点加入到T中,运行时间是|V|2量级35.Dijkstra算法用于例图36.Bellman-Ford算法(1)–定义

s=源顶点(起始点)w(i,j)=从顶点i到顶点j的链路的代价值w(i,i)=0w(i,j)=如i,j不直接相连w(i,j)0如i,j直接连接h=在算法的当前步骤中路径的最大链路数Lh(n)=从顶点s到n的最小代价路径的代价,限制条件是路径的链路数不超过h37.Bellman-Ford算法(2)–步骤初始化L0(n)=nsLh(s)=0h更新对每个相继的h0对每个ns,计算:Lh+1(n)

=min[Lh(j)+w(j,n)],j找到实现最小值的顶点j,将n与该前趋顶点j相连,删除n与此前计算得到与j不同的前趋顶点的连接,从s到n的路径以j到n的链路结束38.Bellman-FordAlgorithm(3)–

说明结果与Dijkstra算法的结果相同运行时间是|V|x|E|的量级39.Bellmin-Ford算法原理图示Sn已知n与其邻点间链路的代价值w(j,n);j到s的最短路径的代价值L(j);找n到s的最短路径；j对每个ns,计算:Lh+1(n)

=min[Lh(j)+w(j,n)],jw(j,n)（已知，因为与n直连）L(n)L(j)n点在计算时需知其邻接点的L(j)—当前估计的到S的最短路径的长度，和它到自己的邻点的链路的代价值，所以为了求出到所有点的最短路径，每点需与其邻接点交换各自到所有其他点的最短路径长度的当前估计值40.Bellman-Ford算法用于例图41.Dijkstra和Bellman-Ford

算法的运算结果42.比较所需要的信息

–Bellman-Ford算法顶点n处的计算需要知道到所有邻接点的链路的代价,以及从源点到这些点的路径的总代价e每个顶点需要维持一个到网络中所有其他顶点的路径及其代价的表与其直接邻接顶点交换上述信息每个顶点都用Bellman-Ford算法步骤2中的表达式更新其路径与代价表43.比较两种算法所需要的信息-------------Dijkstra算法步骤3要求每个顶点知道网络拓扑的完整信息,因而:必须知道网络中所有链路的代价值每个顶点必须与所有其他顶点交换信息究竟哪个算法好,需要考虑算法的运行时间等其他因素44.其他事项当网络拓扑和链路代价处于准静态时,两种算法都收敛给出相同的结果如果链路代价变化,算法会企图跟上这种变化如果链路代价与通信流量有关,而后者又与路由选择有关,则:存在反馈可能产生不稳定45.46.AutonomousSystemsGlobalInternetviewedascollectionofautonomoussystems.Autonomoussystem(AS)isasetofroutersornetworksadministeredbyasingleorganizationSameroutingprotocolneednotberunwithintheASBut,totheoutsideworld,anASshouldpresentaconsistentpictureofwhatASsarereachablethroughitStubAS:hasonlyasingleconnectiontotheoutsideworld.MultihomedAS:hasmultipleconnectionstotheoutsideworld,butrefusestocarrytransittrafficTransitAS:hasmultipleconnectionstotheoutsideworld,andcancarrytransitandlocaltraffic.47.ASNumberForexteriorrouting,anASneedsagloballyuniqueAS16-bitintegernumberCurrently,thereareabout11,000registeredASsinInternet(andgrowing)StubAS,whichisthemostcommontype,doesnotneedanASnumbersincetheprefixesareplacedattheprovider’sroutingtableTransitASneedsanASnumberRequestanASnumberfromtheARIN,RIPEandAPNIC48.InterandIntraDomainRoutingRRRRRRRRASAASBASCIGPEGPIGPIGPInteriorGatewayProtocol(IGP):routingwithinASRIP,OSPFExteriorGatewayProtocol(EGP):routingbetweenAS’sBGPv4BorderGatewaysperformIGP&EGProuting49.OutlineBasicRoutingRoutingInformationProtocol(RIP)OpenShortestPathFirst(OSPF)BorderGatewayProtocol(BGP)50.RFC1058RIPbasedonrouted,“routed”,distributedinBSDUNIXUsesthedistance-vectoralgorithmRunsontopofUDP,portnumber520Metric:numberofhopsMaxlimitedto15suitableforsmallnetworks(localareaenvironments)valueof16isreservedtorepresentinfinitysmallnumberlimitsthecount-to-infinityproblemRoutingInformationProtocol(RIP)51.RIPOperationRoutersendsupdatemessagetoneighborsevery30secArouterexpectstoreceiveanupdatemessagefromeachofitsneighborswithin180secondsintheworstcaseIfrouterdoesnotreceiveupdatemessagefromneighborXwithinthislimit,itassumesthelinktoXhasfailedandsetsthecorrespondingminimumcostto16(infinity)Usessplithorizonwithpoisonedreverse

Convergencespeededupbytriggeredupdatesneighborsnotifiedimmediatelyofchangesindistancevectortable52.RIPProtocolRoutersrunRIPinactivemode(advertisedistancevectortables)HostscanrunRIPinpassivemode(updatedistancevectortables,butdonotadvertise)RIPdatagramsbroadcastoverLANs&specificallyaddressedonpt-ptormulti-accessnon-broadcastnetsTwoRIPpackettypes:requesttoaskneighborfordistancevectortableresponsetoadvertisedistancevectortableperiodically;inresponsetorequest;triggered53.CommandVersion

ZeroAddressfamilyidentifierZeroIPaddressZeroZeroMetric081631...RIPMessageFormatRequest/Response1/22forIPRIPentryUpto25RIPentriespermessage54.Command:requestorresponseVersion:v1orv2Oneormoreof:AddressFamily:2forIPIPAddress:networkorhostdestinationMetric:numberofhopstodestinationDoesnothaveaccesstosubnetmaskinformationCannotworkwithvariable-lengthsubnetmasksRIPv2(RFC2453):Subnetmask,nexthop,routingdomaincanworkwithCIDRstillusesmaxcostof16RIPMessageFormat55.OutlineBasicRoutingRoutingInformationProtocol(RIP)OpenShortestPathFirst(OSPF)BorderGatewayProtocol(BGP)56.UsedinOSPFtodistributelinkstate(LS)informationForwardincomingpackettoallportsexceptwherepacketcameinPacketeventuallyreachesdestinationaslongasthereisapathbetweenthesourceanddestinationGeneratesexponentialnumberofpackettransmissionsApproachestolimit#oftransmissions:UseaTTLateachpacket;won’tfloodifTTLisreachedEachrouteraddsitsidentifiertoheaderofpacketbeforeitfloodsthepacket;won’tfloodifitsidentifierisdetectedEachpacketfromagivensourceisidentifiedwithauniquesequencenumber;won’tfloodifsequencenumberissameFlooding57.ExampleOSPFTopology10.5.1.110.5.1.310.5.1.510.5.1.210.5.1.410.5.1.6Atsteadystate:AllroutershavesameLSdatabaseKnowhowmanyroutersinnetworkInterfaces&linksbetweenroutersCostofeachlinkOccasionalHellomessages(10sec)&LSupdatessent(30min)58.Toimprovescalability,ASmaybepartitionedintoareasAreaisidentifiedby32-bitAreaIDRouterinareaonlyknowscompletetopologyinsidearea&limitsthefloodingoflink-stateinformationtoareaAreaborderrouterssummarizeinfofromotherareasEachareamustbeconnectedtobackbonearea(0.0.0.0)DistributesroutinginfobetweenareasInternalrouterhasalllinkstonetswithinthesameareaAreaborderrouterhaslinkstomorethanoneareabackbonerouterhaslinksconnectedtothebackboneAutonomoussystemboundary(ASB)routerhaslinkstoanotherautonomoussystem.OSPFNetwork59.ASB:4ABR:3,6,and8IR:1,2,7BBR:3,4,5,6,8Area0.0.0.1Area0.0.0.2Area0.0.0.3R1R2R4R5R7N1N2N3N4N5N6N7ToanotherASArea0.0.0.0R=routerN=networkR8R3R6OSPFAreas60.Neighborrouters:tworoutersthathaveinterfacestoacommonnetworkNeighborsarediscovereddynamicallybyHelloprotocolEachneighborofarouterdescribedbyastatedown,attempt,init,2-way,Ex-Start,Exchange,Loading,FullAdjacentrouter:neighborroutersbecomeadjacentwhentheysynchronizetopologydatabasesbyexchangeoflinkstateinformationNeighborsonpoint-to-pointlinksbecomeadjacentRoutersonmultiaccessnetsbecomeadjacentonlytodesignated&backupdesignatedroutersReducessizeoftopologicaldatabase&routingtrafficNeighbor,Adjacent&DesignatedRouters61.ReducesnumberofadjacenciesElectedbyeachmultiaccessnetworkafterneighbordiscoverybyhelloprotocolElectionbasedonpriority&idfieldsGenerateslinkadvertisementsthatlistroutersattachedtoamulti-accessnetworkFormsadjacencieswithroutersonmulti-accessnetworkBackuppreparedtotakeoverifdesignatedrouterfailsDesignatedRouters62.Linkstateinfoexchangedbyadjacentrouterstoallowareatopologydatabasestobemaintainedinter-area&inter-ASroutestobeadvertisedRouterlinkad:generatedbyallOSPFroutersstateofrouterlinkswithinarea;floodedwithinareaonlyNetlinkad:generatedbythedesignatedrouter

listsroutersconnectedtonet:floodedwithinareaonlySummarylinkad:generatedbyareaborderrouters1.routestodestinotherareas;2.routestoASBroutersASexternallinkad:generatedbyASBroutersdescribesroutestodestinationsoutsidetheOSPFnetfloodedinallareasintheOSPFnetLinkStateAdvertisements63.OSPFpacketstransmitteddirectlyonIPdatagrams;ProtocolID89TOS0,IPprecedencefieldsettointernetworkcontroltogetprecedenceovernormaltrafficOSPFpacketssenttomulticastaddress224.0.0.5(allSPFRoutersonpt-2-ptandbroadcastnets)OSPFpacketssentonspecificIPaddressesonnon-broadcastnetsFiveOSPFpackettypes:HelloDatabasedescriptionLinkstaterequest;Linkstateupdate;LinkstateackOSPFProtocol64.OSPFHeaderType:Hello,Databasedescription,Linkstaterequest,Linkstateupdate,LinkstateacknowledgementsVersionTypePacketlengthRouterIDAreaIDChecksumAuthenticationtypeAuthenticationAuthentication081631OSPFcommonheaderOSPFpacketbodyData65.OSPFStagesDiscoverneighborsbysendingHellopackets(every10sec)anddesignatedrouterelectedinmultiaccessnetworksAdjacenciesareestablished&linkstatedatabasesaresynchronizedLinkstateinformationispropagated&routingtablesarecalculatedWeelaborateonOSPFstagesinfollowing66.Stage1:OSPFHelloPacketHellointerval:numberofsecondsbetweenHellopacketsPriority:usedtoelectdesignatedrouter&backupDeadinterval:#secbeforedeclaringanon-respondingneighbordown.Neighbor:theRouterIDofeachneighborfromwhomHellopacketshaverecentlybeenreceivedSendHellopacketstoestablish&maintainneighborrelationshipNetworkmaskHellointervalOptionsPriority0162431DeadintervalDesignatedrouterBackupdesignatedrouterNeighbor1Neighborn...67.Stage2:OSPFDatabaseDescriptionInitbit1ifpktisfirstinsequenceofdatabasedescriptionpacketsMorebit1iftherearemoredatabasedescriptionpacketstofollowMaster/Slavebitindicatesthattherouteristhemaster.Linkstatead(LSA)headerdescribesstateofrouterornetwork;containsinfotouniquelyidentifyentryinLSA(type,ID,andadvertisingrouter).CanhavemultipleLSAheadersOnceneighborroutersbecomeadjacent,theyexchangedatabasedescriptionpacketstosynchronizetheirlink-statedatabases.68.LSAHeaderLStype:RouterLSAsgeneratedbyallOSPFrouters;NetworkLSAsgeneratedbydesignatedrouters;SummaryLSAsbyareaborderrouters;AS-externalLSAsbyASBRsLSid:identifiespieceofroutingdomainbeingdescribedbyLSALSSeq.Number:numbersLSAstodetectold/duplicateLSAsLSchecksum:coverscontentsofLSAexceptlinkstateageLink-stateageOptions