班《通信网理论基础》.ppt

通信网理论基础 第三部分 图论基础 与 应用,基本概念,图 G(V,E)由两个集合加以定义:顶点(或节点)集合 V=v1,v2,v3.vn;边集合 E=e1,e2,e3em;G=V,E 边由一对直接关连的顶点的组合定义如果:(i,j)E,则顶点i和 j称为相邻的顶点的数目称为图的“阶”;边的数目称为图的“尺寸”;许多图的算法的运行时间与图的“阶”和“尺寸”相关,图的一个例子,图的邻接矩阵,邻接矩阵是用数学方式来表示图顶点编号:1,2,3,|V|V|x|V|邻接矩阵 A=(ai,j)定义为:ai,j=1 if(i,j)E(ij是图的一条边)0 otherwise对于边没有方向性的图(即边的两顶点的顺序不影响边的性质),邻接矩阵A是对称矩阵.,邻接矩阵一例,Terminology,关联同一对顶点的边称为:平行边关联同一顶点的边称为:环既无平行边,又无环的图称为:简单图顶点 i 到顶点 j的路径是:顶点和边的交替序列起于i,止于j;每条边只与序列中直接在它前面和直接在它后面的顶点相连简单路径:顶点和边在序列中只出现一次的路径 在简单图中,简单路径可以由顶点序列来定义每个顶点与序列中在其前面和后面的顶点相邻序列中没有重复的顶点,简单路径(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条(其余的请自行列出),简单图(2),两顶点间的所有路径中有一条最短路径,如:V1,V3,V6顶点间的距离是所有路径中边数最少的路径的边的数目回路是起于和止于同一顶点的路径例如:.V1,V3,V4,V1,有向图,边有方向性的图有向图 G(V,E)的边由一对顶点的有序组合来定义代表边的线段用箭头表示其方向允许存在平行边,只要它们的方向相反便于用图表示通信网络每条有向边表达一个方向上的数据流仍然可用邻接矩阵表示除非每对相邻的顶点用平行边连接,否则邻接矩阵是不对称的,加权图,或加权有向图每条边有一与之关联的数(权值w)-便于说明路由算法邻接矩阵定义为:ai,j=wi,j if(i,j)E 0 otherwisewi,j 是与边(i,j)关联的权值路径长度是权值之和最短距离路径不一定是长度最短路径(见下面两张PPT),加权图与邻接矩阵,V1 至 V6 的路径距离 和 路径长度,路径 距离 长度V1,V2,V3,V4,V5,V6511V1,V2,V3,V5,V648V1,V2,V3,V6310V1,V2,V4,V3,V5,V6510V1,V2,V4,V5,V647V1,V3,V2,V4,V5,V6516V1,V3,V6210V1,V4,V5,V634,树,树是图的子集以下几项定义是等效的:*树是一种简单图,顶点i 和 j 之间只有一条简单路径*N个顶点的简单图如果只有N-1 条边,没有回路*N个顶点的简单图如果只有N-1条边,而且是连通的可以指定一个顶点为“根”根通常画在上部与根邻接的顶点画在下一层这些顶点可以到达树根,路径距离为1,树中顶点的等级关系,每个顶点(除根外)有一个父顶点靠根一边的邻接顶点每个顶点有0个或几个子顶点离根远的邻接顶点没有子顶点的顶点称为叶层次等级直接在根下面的顶点是第一层第一层顶点的子顶点是第二层,树的例,子图,从图G中选择一些边和顶点构成G的子图每条被选上的边的两个关联顶点必须同时选上图 G(E,V)是图G(E,V)的子图,如果:V V,E E 并且对每一条E中的边e.如果 e 关联 v and w,则 v,w V,生成树,图G的子图T是一颗生成树,如果:T 是树 包含G的所有顶点从图G中删去一些边,使所有的回路不复存在,但保持图的连通性:图G的生成树通常并不唯一,生成树的例子,生成树的“先广搜索”算法,将顶点划分成不同的层次在处理下一层之前,先处理完本层的所有顶点从任一顶点x 开始指定它为0层所有它的邻接顶点属于1层设 Vi1,Vi2,Vi3,Vij,是 i层的顶点所有Vi1 的邻接顶点中不属于1,2,i层的顶点指定为(i+1)层所有Vi2的邻接顶点中不属于1,2,3,i,(i+1)层的顶点也指定为(i+1)层直到所有顶点被处理完毕,例,选择顶点顺序如:V1,V2,V3,V4,V5,V6选择“根”例如 V1现在树T只包含一个顶点V1,不含边在树上增加边(V1,x)和顶点x,但不要形成回路:将边(V1,V2),(V1,V3),(V1,V4)和顶点 V1,V2,V3加入到树中,这是第一层在第一层的顶点上按序重复上述过程,得到第二层是否所有顶点都处理完?如果没有,在第二层的顶点上重复处理过程,得到第三层.,上例的图示,Avoiding Loops,Avoiding Loops,Spanning Tree Algorithm,Select a root bridge among all the bridges.root bridge=the lowest bridge ID.Determine the root port for each bridge except the root bridgeroot port=port with the least-cost path to the root bridgeSelect a designated bridge for each LANdesignated bridge=bridge has least-cost path from the LAN to the root bridge.designated port connects the LAN and the designated bridge All root ports and all designated ports are placed into a“forwarding”state.These are the only ports that are allowed to forward frames.The other ports are placed into a“blocking”state.,LAN1,LAN2,LAN3,B1,B2,B3,B4,B5,LAN4,(1),(2),(1),(1),(1),(1),(2),(2),(2),(2),(3),LAN1,LAN2,LAN3,B1,B2,B3,B4,B5,LAN4,(1),(2),(1),(1),(1),(1),(2),(2),(2),(2),(3),Bridge 1 selected as root bridge,LAN1,LAN2,LAN3,B1,B2,B3,B4,B5,LAN4,(1),(2),(1),(1),(1),(1),(2),(2),(2),(2),(3),Root port selected for every bridge except root port,R,R,R,R,最短距离路径的距离,BFS算法可以得到从根顶点s到所有其他顶点的最短距离路径和距离(s,v)任何从s 到v 的路径中BFS给出的路径是距离最短的,即该路径边数之和最小。,最短长度路径,分组交换,帧中继,ATM等网络可以看作一张图每个节点是图中一顶点每一链路是一对平行边对于互联网(Internet 或 intranet)每个路由器是一个顶点如路由器直接相连,双向连接相当于一对平行边如多于两个路由器,则由多对平行边构成表示网络的图一对边连接一对路由器为将分组由源送到目的,需要路由决策等效于在图上找出路径,路由决策,基于最小代价最少跳数(hop)每条边(一跳)的权重为1 相当于最短距离路径或者,每跳有一相关联的代价(见下一PPT)路径的代价是路径中各链路的代价之和需要找出最小代价路径相当于加权图中的最小长度路径,一跳的代价,反比于路径的容量正比于当前的负荷链路的货币价值几种因素的组合在不同方向上的代价可能不同,Dijkstra 算法(1)定义,N=网络顶点的集合s=源顶点(起始点)T=到目前为止算法已经用到的顶点的临时集合Tree=T中顶点组成的生成树,它包括从s到T中每个顶点的最小代价路径上的边w(i,j)=从顶点i 到顶点 j的链路代价,w(i,i)=0w(i,j)=if i,j 不直接连接w(i,j)0 if i,j 直接连接L(n)=当前知道的从s到n的最小代价路径的代价cost 运算结束是它就是从s到n的最小代价路径的代价,Dijkstra 算法(2)步骤,初始化T=Tree=s 临时顶点集合中暂时只含源顶点L(n)=w(s,n)for n s;到邻点的初始路径代价就是链路代价取下一个顶点找 x T 使 L(x)=min L(j),j T将 x 加入到 T 和 Tree 中将关联x,且使L(x)成为最小代价的边加入到Tree中它是路径的最后一跳更新最小代价路径L(n)=minL(n),L(x)+w(x,n)n T如果后一项最小,从s到n的路径就是从s到x的路径与从x到n的边的连接,Chapter 14 Overview of Graph Theory and Least-Cost Paths,34,Dijkstra 算法原理图示,T,S,N,X,n,w(x,n),L(n),L(x),已算出最短路径的点的集合,找 x T 使 L(x)=min L(j),j T x T,L(n)=minL(n),L(x)+w(x,n)n T,所以，S需要知道w(x,n)-各点与其邻点间直接相连链路的代价因而需要与所有其他各点交换路由信息,某点（s)已知网络中其他各点到其邻点的链路的代价值w(x,n),计算S到其他各点的最短路径,Dijkstras 算法(3)说明,当所有顶点都加入到T以后,算法结束需要|V|次迭代结束时L(x)是s 到 x 的最小代价路径的代价值Tree 是原图的一颗最小生成树定义了从s到其他顶点的最小代价路径每次迭代有一个新的顶点加入到T中,运行时间是|V|2 量级,Dijkstra 算法 用于例图,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 的最小代价路径的代价,限制条件是路径的链路数不超过h,Bellman-Ford 算法(2)步骤,初始化L0(n)=n sLh(s)=0 h更新对每个相继的 h 0对每个n s,计算:Lh+1(n)=minLh(j)+w(j,n),j找到实现最小值的顶点j,将n与该前趋顶点j相连,删除n与此前计算得到与j不同的前趋顶点的连接,从s到n的路径以j到n的链路结束,Bellman-Ford Algorithm(3)说明,结果与 Dijkstra 算法的结果相同运行时间是|V|x|E|的量级,Chapter 14 Overview of Graph Theory and Least-Cost Paths,40,Bellmin-Ford 算法原理图示,S,n,已知 n 与其邻点间链路的代价值w(j,n);j 到s 的最短路径的代价值L(j);找n 到s的最短路径；,j,对每个n s,计算:Lh+1(n)=minLh(j)+w(j,n),j,w(j,n)（已知，因为与n直连）,L(n),L(j),n点在计算时需知其邻接点的L(j)当前估计的到S的最短路径的长度，和它到自己的邻点的链路的代价值，所以为了求出到所有点的最短路径，每点需与其邻接点交换各自到所有其他点的最短路径长度的当前估计值,Bellman-Ford 算法用于例图,Dijkstra 和 Bellman-Ford 算法 的运算结果,比较所需要的信息 Bellman-Ford 算法,顶点n处的计算需要知道到所有邻接点的链路的代价,以及从源点到这些点的路径的总代价e每个顶点需要维持一个到网络中所有其他顶点的路径及其代价的表与其直接邻接顶点交换上述信息每个顶点都用Bellman-Ford 算法步骤 2 中的表达式更新其路径与代价表,比较两种算法所需要的信息-Dijkstra 算法,步骤 3 要求每个顶点知道网络拓扑的完整信息,因而:必须知道网络中所有链路的代价值每个顶点必须与所有其他顶点交换信息究竟哪个算法好,需要考虑算法的运行时间等其他因素,其他事项,当网络拓扑和链路代价处于准静态时,两种算法都收敛给出相同的结果如果链路代价变化,算法会企图跟上这种变化如果链路代价与通信流量有关,而后者又与路由选择有关,则:存在反馈可能产生不稳定,Autonomous Systems,Global Internet viewed as collection of autonomous systems.Autonomous system(AS)is a set of routers or networks administered by a single organization Same routing protocol need not be run within the ASBut,to the outside world,an AS should present a consistent picture of what ASs are reachable through itStub AS:has only a single connection to the outside world.Multihomed AS:has multiple connections to the outside world,but refuses to carry transit trafficTransit AS:has multiple connections to the outside world,and can carry transit and local traffic.,AS Number,For exterior routing,an AS needs a globally unique AS 16-bit integer numberCurrently,there are about 11,000 registered ASs in Internet(and growing)Stub AS,which is the most common type,does not need an AS number since the prefixes are placed at the providers routing tableTransit AS needs an AS numberRequest an AS number from the ARIN,RIPE and APNIC,Inter and Intra Domain Routing,R,R,R,R,R,R,R,R,AS A,AS B,AS C,IGP,EGP,IGP,IGP,Interior Gateway Protocol(IGP):routing within AS RIP,OSPFExterior Gateway Protocol(EGP):routing between ASs BGPv4Border Gateways perform IGP&EGP routing,Outline,Basic RoutingRouting Information Protocol(RIP)Open Shortest Path First(OSPF)Border Gateway Protocol(BGP),RFC 1058RIP based on routed,“route d”,distributed in BSD UNIXUses the distance-vector algorithmRuns on top of UDP,port number 520Metric:number of hopsMax limited to 15suitable for small networks(local area environments)value of 16 is reserved to represent infinitysmall number limits the count-to-infinity problem,Routing Information Protocol(RIP),RIP Operation,Router sends update message to neighbors every 30 secA router expects to receive an update message from each of its neighbors within 180 seconds in the worst caseIf router does not receive update message from neighbor X within this limit,it assumes the link to X has failed and sets the corresponding minimum cost to 16(infinity)Uses split horizon with poisoned reverse Convergence speeded up by triggered updatesneighbors notified immediately of changes in distance vector table,RIP Protocol,Routers run RIP in active mode(advertise distance vector tables)Hosts can run RIP in passive mode(update distance vector tables,but do not advertise)RIP datagrams broadcast over LANs triggered,RIP Message Format,Request/Response,1/2,2 for IP,RIPentry,Up to 25 RIP entries per message,Command:request or responseVersion:v1 or v2One or more of:Address Family:2 for IPIP Address:network or host destinationMetric:number of hops to destinationDoes not have access to subnet mask informationCannot work with variable-length subnet masksRIP v2(RFC 2453):Subnet mask,next hop,routing domaincan work with CIDRstill uses max cost of 16,RIP Message Format,Outline,Basic RoutingRouting Information Protocol(RIP)Open Shortest Path First(OSPF)Border Gateway Protocol(BGP),Used in OSPF to distribute link state(LS)informationForward incoming packet to all ports except where packet came inPacket eventually reaches destination as long as there is a path between the source and destinationGenerates exponential number of packet transmissionsApproaches to limit#of transmissions:Use a TTL at each packet;wont flood if TTL is reachedEach router adds its identifier to header of packet before it floods the packet;wont flood if its identifier is detectedEach packet from a given source is identified with a unique sequence number;wont flood if sequence number is same,Flooding,Example OSPF Topology,At steady state:All routers have same LS databaseKnow how many routers in networkInterfaces&links between routersCost of each linkOccasional Hello messages(10 sec)&LS updates sent(30 min),To improve scalability,AS may be partitioned into areasArea is identified by 32-bit Area IDRouter in area only knows complete topology inside area&limits the flooding of link-state information to areaArea border routers summarize info from other areasEach area must be connected to backbone area(0.0.0.0)Distributes routing info between areasInternal router has all links to nets within the same areaArea border router has links to more than one areabackbone router has links connected to the backboneAutonomous system boundary(ASB)router has links to another autonomous system.,OSPF Network,ASB:4ABR:3,6,and 8IR:1,2,7BBR:3,4,5,6,8,R1,R2,R4,R5,R7,N1,N2,N3,N4,N5,N6,N7,To another AS,R=router N=network,R8,R3,R6,OSPF Areas,Neighbor routers:two routers that have interfaces to a common networkNeighbors are discovered dynamically by Hello protocolEach neighbor of a router described by a statedown,attempt,init,2-way,Ex-Start,Exchange,Loading,FullAdjacent router:neighbor routers become adjacent when they synchronize topology databases by exchange of link state informationNeighbors on point-to-point links become adjacentRouters on multiaccess nets become adjacent only to designated&backup designated routersReduces size of topological database&routing traffic,Neighbor,Adjacent&Designated Routers,Reduces number of adjacenciesElected by each multiaccess network after neighbor discovery by hello protocolElection based on priority&id fieldsGenerates link advertisements that list routers attached to a multi-access networkForms adjacencies with routers on multi-access networkBackup prepared to take over if designated router fails,Designated Routers,Link state info exchanged by adjacent routers to allow area topology databases to be maintainedinter-area 2.routes to ASB routersAS external link ad:generated by ASB routersdescribes routes to destinations outside the OSPF netflooded in all areas in the OSPF net,Link State Advertisements,OSPF packets transmitted directly on IP datagrams;Protocol ID 89TOS 0,IP precedence field set to internetwork control to get precedence over normal trafficOSPF packets sent to multicast address 224.0.0.5(allSPFRouters on pt-2-pt and broadcast nets)OSPF packets sent on specific IP addresses on non-broadcast netsFive OSPF packet types:HelloDatabase descriptionLink state request;Link state update;Link state ack,OSPF Protocol,OSPF Header,Type:Hello,Database description,Link state request,Link state update,Link state acknowledgements,OSPF Stages,Discover neighbors by sending Hello packets(every 10 sec)and designated router elected in multiaccess networksAdjacencies are established&link state databases are synchronizedLink state information is propagated&routing tables are calculatedWe elaborate on OSPF stages in following,Stage 1:OSPF Hello Packet,Hello interval:number of seconds between Hello packetsPriority:used to elect designated router&backupDead interval:#sec before declaring a non-responding neighbor down.Neighbor:the Router ID of each neighbor from whom Hello packets have recently been received,Send Hello packets to establish&maintain neighbor relationship,Stage 2:OSPF Database Description,Init bit 1 if pkt is first in sequence of database description packetsMore bit 1 if there are more database description packets to followMaster/Slave bit indicates that the router is the master.Link state ad(LSA)header describes state of router or network;contains info to uniquely identify entry in LSA(type,ID,and advertising router).Can have multiple LSA headers,Once neighbor routers become adjacent,they exchange database description packets to synchronize their link-state databases.,LSA Header,LS type:Router LSAs generated by all OSPF routers;Network LSAs generated by designated routers;Summary LSAs by area border routers;AS-external LSAs by ASBRsLS id:identifies piece of routing domain being described by LSALS Seq.Number:numbers LSAs to detect old/duplicate LSAsLS checksum:covers contents of LSA except link state age,Database Synchronization,LS Database(LSDB):collection of the Link State Advertisements(LSAs)accepted at a node.This is the“map”for Dijkstra algorithmWhen the connection between two neighbors comes up,the routers must wait for their LSDBs to be synchronized.Else routing loops and black holes due to inconsistencyOSPF technique:Source sends only LSA headers,thenNeighbor requests LSAs that are more recentThose LSAs are sent overAfter sync,the neighbors are said to be“fully adjacent”,Router sends a LS request packet to neighbor to update part of its link-state databaseEach LSA request is specified by the link state type,link state ID,and the advertising router.,Stage 3:OSPF Link State Request,OSPF Link State Update,In response to LS request or trigger,router will send new LS info using the LS update message Contents are composed of link state advertisements(LSAs)LS update message is acknowledged using LS ack pkt to ensure that the flooding algorithm is reliable;Link state acknowledgement packets consist of a list of LSA headers.,Outline,Basic RoutingRouting Information Protocol(RIP)Open Shortest Path First(OSPF)Border Gateway Protocol(BGP),