工程硕士班《通信网理论基础》(2)ppt课件

1、12l图 G(V,E) 由两个集合加以定义: 顶点 (或节点) 集合 V= v1,v2,v3.vn ; 边集合 E=e1,e2,e3em ; G=V, E l边由一对直接关连的顶点的组合定义 如果: (i,j) E,则顶点i和 j称为相邻的 顶点的数目称为图的“阶”;边的数目称为图的“尺寸”; 许多图的算法的运行时间与图的“阶”和“尺寸”相关34l邻接矩阵是用数学方式来表示图l顶点编号: 1,2,3,|V|l|V| x |V| 邻接矩阵 A=(ai,j) 定义为: ai,j = 1 if (i,j) E (ij是图的一条边) 0 otherwisel对于边没有方向性的图(即边的两顶点的顺序不影

2、响边的性质),邻接矩阵A是对称矩阵.56l关联同一对顶点的边称为: 平行边l关联同一顶点的边称为: 环l既无平行边,又无环的图称为: 简单图l顶点 i 到顶点 j的路径是: 顶点和边的交替序列起于i,止于j; 每条边只与序列中直接在它前面和直接在它后面的顶点相连 简单路径 : 顶点和边在序列中只出现一次的路径 l在简单图中,简单路径可以由顶点序列来定义 每个顶点与序列中在其前面和后面的顶点相邻 序列中没有重复的顶点7l由V1 到 V6 (不完全) V1,V2,V3,V4,V5,V6 V1,V2,V3,V5,V6 V1,V2,V3,V6 V1,V2,V4,V3,V5,V6 V1,V2,V4,V5

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

4、联的数(权值w)-便于说明路由算法l邻接矩阵定义为: ai,j = wi,j if (i,j) E 0 otherwisewi,j 是与边( i, j )关联的权值l路径长度是权值之和l最短距离路径不一定是长度最短路径(见下面两张PPT)1112路径 距离 长度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,V63413l树是图的子集l以下几项定义是等效的: * 树是一种简单图,顶点i 和 j

5、 之间只有一条简单路径 * N个顶点的简单图如果只有N-1 条边,没有回路 * N个顶点的简单图如果只有N-1条边,而且是连通的l可以指定一个顶点为“根” 根通常画在上部 与根邻接的顶点画在下一层l这些顶点可以到达树根,路径距离为114l每个顶点(除根外)有一个父顶点 靠根一边的邻接顶点l每个顶点有0个或几个子顶点 离根远的邻接顶点 没有子顶点的顶点称为叶l层次等级 直接在根下面的顶点是第一层 第一层顶点的子顶点是第二层1516l从图G中选择一些边和顶点构成G的子图 每条被选上的边的两个关联顶点必须同时选上l图 G(E,V) 是图G(E,V) 的子图,如果: V V , E E 并且对每一条E

6、中的边e.如果 e 关联 v and w, 则 v, w V17l图G的子图T是一颗生成树,如果: T 是树 包含G的所有顶点l从图G中删去一些边,使所有的回路不复存在,但保持图的连通性:l图G的生成树通常并不唯一1819l将顶点划分成不同的层次l在处理下一层之前,先处理完本层的所有顶点l从任一顶点x 开始l指定它为0层 所有它的邻接顶点属于1层 设 Vi1, Vi2, Vi3, Vij,是 i层的顶点 所有Vi1 的邻接顶点中不属于1,2,i层的顶点指定为(i+1)层 所有Vi2的邻接顶点中不属于1,2,3,i, (i+1)层的顶点也指定为(i+1)层 直到所有顶点被处理完毕20l选择顶点顺

7、序 如: V1,V2,V3,V4,V5,V6l选择“根” 例如 V1l现在树T只包含一个顶点V1 ,不含边l在树上增加边(V1,x) 和顶点x, 但不要形成回路:将边 (V1,V2), (V1,V3), (V1,V4) 和顶点 V1,V2, V3加入到树中,这是第一层l在第一层的顶点上按序重复上述过程,得到第二层 是否所有顶点都处理完? 如果没有,在第二层的顶点上重复处理过程,得到第三层.2122LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)23LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)24lSelect a root bridge amon

8、g all the bridges. root bridge = the lowest bridge ID.lDetermine the root port for each bridge except the root bridge root port = port with the least-cost path to the root bridgelSelect a designated bridge for each LAN designated bridge = bridge has least-cost path from the LAN to the root bridge. d

9、esignated port connects the LAN and the designated bridge lAll 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.25LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2

10、)(2)(2)(3)26LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)Bridge 1 selected as root bridge27LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)Root port selected for every bridge except root portRRRR28lBFS算法可以得到从根顶点s到所有其他顶点的最短距离路径和距离 (s,v) l任何从s 到v 的路径中BFS给出的路径是距离最短的,即该路径边数之和最小。

11、29l分组交换,帧中继,ATM等网络可以看作一张图 每个节点是图中一顶点 每一链路是一对平行边l对于互联网(Internet 或 intranet) 每个路由器是一个顶点 如路由器直接相连,双向连接相当于一对平行边 如多于两个路由器,则由多对平行边构成表示网络的图 一对边连接一对路由器l为将分组由源送到目的,需要路由决策 等效于在图上找出路径30l基于最小代价 最少跳数( hop )l每条边(一跳)的权重为1 l相当于最短距离路径 或者, 每跳有一相关联的代价(见下一PPT) 路径的代价是路径中各链路的代价之和 需要找出最小代价路径l相当于加权图中的最小长度路径31l反比于路径的容量l正比于当

12、前的负荷l链路的货币价值l几种因素的组合l在不同方向上的代价可能不同32lN = 网络顶点的集合ls = 源顶点 ( 起始点 )lT = 到目前为止算法已经用到的顶点的临时集合lTree = T中顶点组成的生成树,它包括从s到T中每个顶点的最小代价路径上的边lw(i,j) = 从顶点i 到顶点 j的链路代价, w(i,i) = 0 w(i,j) = if i, j 不直接连接 w(i,j) 0 if i,j 直接连接lL(n) = 当前知道的从s到n的最小代价路径的代价cost 运算结束是它就是从s到n的最小代价路径的代价33l初始化T = Tree = s 临时顶点集合中暂时只含源顶点L(n

13、) = w(s,n) for n s ; 到邻点的初始路径代价就是链路代价l取下一个顶点找 x T 使 L(x) = min L(j), j T将 x 加入到 T 和 Tree 中将关联x,且使L(x) 成为最小代价的边加入到Tree中l它是路径的最后一跳l更新最小代价路径L(n) = minL(n), L(x) + w(x,n) n Tl如果后一项最小,从s到n的路径就是从s到x的路径与从x到n的边的连接Chapter 14 Overview of Graph Theory and Least-Cost Paths34TSNXnw(x, n)L(n)L(x)已算出最短路径的点的集合找 x T

14、 使 L(x) = min L(j), j Tl x TL(n) = minL(n), L(x) + w(x,n) n T所以，S需要知道w(x,n)-各点与其邻点间直接相连链路的代价因而需要与所有其他各点交换路由信息某点（s) 已知网络中其他各点到其邻点的链路的代价值w(x,n), 计算S到其他各点的最短路径35l当所有顶点都加入到T以后,算法结束l需要 |V| 次迭代l结束时 L(x) 是s 到 x 的最小代价路径的代价值 Tree 是原图的一颗最小生成树l定义了从s到其他顶点的最小代价路径l每次迭代有一个新的顶点加入到T中,运行时间是 |V|2 量级3637ls = 源顶点(起始点)lw

15、(i,j) = 从顶点i 到顶点 j 的链路的代价值 w(i,i) = 0 w(i,j) = 如 i, j 不直接相连 w(i,j) 0 如 i,j 直接连接lh = 在算法的当前步骤中路径的最大链路数lLh(n) = 从顶点s 到 n 的最小代价路径的代价,限制条件是路径的链路数不超过h38l初始化L0(n) = n sLh(s) = 0 h更新对每个相继的 h 0l对每个n s, 计算: Lh+1 (n) = minLh(j)+ w(j,n), jl找到实现最小值的顶点jl,将n与该前趋顶点j相连,l删除n与此前计算得到与j不同的前趋顶点的连接,l从s到n的路径以j到n的链路结束39l结果

16、与 Dijkstra 算法的结果相同l运行时间是 |V| x |E| 的量级Chapter 14 Overview of Graph Theory and Least-Cost Paths40Sn已知 n 与其邻点间链路的代价值w(j,n); j 到s 的最短路径的代价值L(j); 找n 到s的最短路径；jl对每个n s, 计算: Lh+1 (n) = minLh(j)+ w(j,n), jw(j,n)（已知，因为与n直连）L(n)L(j)n点在计算时需知其邻接点的L(j)当前估计的到S的最短路径的长度，和它到自己的邻点的链路的代价值，所以为了求出到所有点的最短路径，每点需与其邻接点交换各自到

17、所有其他点的最短路径长度的当前估计值414243l顶点n处的计算需要知道到所有邻接点的链路的代价,以及从源点到这些点的路径的总代价el每个顶点需要维持一个到网络中所有其他顶点的路径及其代价的表l与其直接邻接顶点交换上述信息l每个顶点都用Bellman-Ford 算法步骤 2 中的表达式更新其路径与代价表44l步骤 3 要求每个顶点知道网络拓扑的完整信息,因而: 必须知道网络中所有链路的代价值 每个顶点必须与所有其他顶点交换信息l究竟哪个算法好,需要考虑算法的运行时间等其他因素45l当网络拓扑和链路代价处于准静态时,两种算法都收敛l给出相同的结果l如果链路代价变化,算法会企图跟上这种变化l如果链

18、路代价与通信流量有关,而后者又与路由选择有关,则: 存在反馈 可能产生不稳定4647lGlobal Internet viewed as collection of autonomous systems. lAutonomous system (AS) is a set of routers or networks administered by a single organization lSame routing protocol need not be run within the ASlBut, to the outside world, an AS should present a

19、consistent picture of what ASs are reachable through itlStub AS: has only a single connection to the outside world. lMultihomed AS: has multiple connections to the outside world, but refuses to carry transit trafficlTransit AS: has multiple connections to the outside world, and can carry transit and

20、 local traffic.48lFor exterior routing, an AS needs a globally unique AS 16-bit integer numberlCurrently, there are about 11,000 registered ASs in Internet (and growing)lStub AS, which is the most common type, does not need an AS number since the prefixes are placed at the providers routing tablelTr

21、ansit AS needs an AS numberlRequest an AS number from the ARIN, RIPE and APNIC49RRRRRRRRAS AAS BAS CIGPEGPIGPIGPInterior Gateway Protocol (IGP): routing within AS RIP, OSPFExterior Gateway Protocol (EGP): routing between ASs BGPv4Border Gateways perform IGP & EGP routing50lBasic RoutinglRouting

22、Information Protocol (RIP)lOpen Shortest Path First (OSPF)lBorder Gateway Protocol (BGP)51lRFC 1058lRIP based on routed, “route d”, distributed in BSD UNIXlUses the distance-vector algorithmlRuns on top of UDP, port number 520lMetric: number of hopslMax limited to 15 suitable for small networks (loc

23、al area environments) value of 16 is reserved to represent infinity small number limits the count-to-infinity problem 52lRouter sends update message to neighbors every 30 seclA router expects to receive an update message from each of its neighbors within 180 seconds in the worst caselIf router does

24、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)lUses split horizon with poisoned reverse lConvergence speeded up by triggered updates neighbors notified immediately of changes in distance vecto

25、r table 53lRouters run RIP in active mode (advertise distance vector tables)lHosts can run RIP in passive mode (update distance vector tables, but do not advertise)lRIP datagrams broadcast over LANs & specifically addressed on pt-pt or multi-access non-broadcast netslTwo RIP packet types:request

26、 to ask neighbor for distance vector tableresponse to advertise distance vector tablelperiodically; in response to request; triggered54Command Version ZeroAddress family identifier ZeroIP addressZeroZeroMetric0 8 16 31. . .Request/Response1/22 for IPRIPentryUp to 25 RIP entries per message55lCommand

27、: request or responselVersion: v1 or v2lOne or more of: Address Family: 2 for IP IP Address: network or host destination Metric: number of hops to destinationlDoes not have access to subnet mask informationlCannot work with variable-length subnet masksRIP v2 (RFC 2453):lSubnet mask, next hop, routin

28、g domainlcan work with CIDRlstill uses max cost of 1656lBasic RoutinglRouting Information Protocol (RIP)lOpen Shortest Path First (OSPF)lBorder Gateway Protocol (BGP)57lUsed in OSPF to distribute link state (LS) informationlForward incoming packet to all ports except where packet came inlPacket even

29、tually reaches destination as long as there is a path between the source and destinationlGenerates exponential number of packet transmissionslApproaches to limit # of transmissions: Use a TTL at each packet; wont flood if TTL is reached Each router adds its identifier to header of packet before it f

30、loods the packet; wont flood if its identifier is detected Each packet from a given source is identified with a unique sequence number; wont flood if sequence number is same5810.5.1.110.5.1.310.5.1.510.5.1.210.5.1.410.5.1.6At steady state: lAll routers have same LS databaselKnow how many routers in

31、networklInterfaces & links between routerslCost of each linklOccasional Hello messages (10 sec) & LS updates sent (30 min)59lTo improve scalability, AS may be partitioned into areas Area is identified by 32-bit Area ID Router in area only knows complete topology inside area & limits the

32、flooding of link-state information to area Area border routers summarize info from other areaslEach area must be connected to backbone area (0.0.0.0) Distributes routing info between areaslInternal router has all links to nets within the same arealArea border router has links to more than one arealb

33、ackbone router has links connected to the backbonelAutonomous system boundary (ASB) router has links to another autonomous system. 60ASB: 4ABR: 3, 6, and 8IR: 1,2,7BBR: 3,4,5,6,8Area 0.0.0.1Area 0.0.0.2Area 0.0.0.3R1R2R4R5R7N1N2N3N4N5N6N7To another ASArea 0.0.0.0R = router N = networkR8R3R661lNeighb

34、or routers: two routers that have interfaces to a common network Neighbors are discovered dynamically by Hello protocollEach neighbor of a router described by a state down, attempt, init, 2-way, Ex-Start, Exchange, Loading, FulllAdjacent router: neighbor routers become adjacent when they synchronize

35、 topology databases by exchange of link state information Neighbors on point-to-point links become adjacent Routers on multiaccess nets become adjacent only to designated & backup designated routerslReduces size of topological database & routing traffic62lReduces number of adjacencieslElecte

36、d by each multiaccess network after neighbor discovery by hello protocollElection based on priority & id fieldslGenerates link advertisements that list routers attached to a multi-access networklForms adjacencies with routers on multi-access networklBackup prepared to take over if designated rou

37、ter fails63lLink state info exchanged by adjacent routers to allow area topology databases to be maintained inter-area & inter-AS routes to be advertisedlRouter link ad: generated by all OSPF routers state of router links within area; flooded within area onlylNet link ad: generated by the design

38、ated router lists routers connected to net: flooded within area onlylSummary link ad: generated by area border routers 1. routes to dest in other areas; 2. routes to ASB routerslAS external link ad: generated by ASB routers describes routes to destinations outside the OSPF net flooded in all areas i

39、n the OSPF net64lOSPF packets transmitted directly on IP datagrams; Protocol ID 89lTOS 0, IP precedence field set to internetwork control to get precedence over normal trafficlOSPF packets sent to multicast address 224.0.0.5 (allSPFRouters on pt-2-pt and broadcast nets)lOSPF packets sent on specific

40、 IP addresses on non-broadcast netslFive OSPF packet types: Hello Database description Link state request; Link state update; Link state ack65lType: Hello, Database description, Link state request, Link state update, Link state acknowledgements Version Type Packet lengthRouter IDArea IDChecksum Auth

41、entication typeAuthenticationAuthentication0 8 16 31OSPFcommonheaderOSPFpacketbodyData66lDiscover neighbors by sending Hello packets (every 10 sec) and designated router elected in multiaccess networkslAdjacencies are established & link state databases are synchronizedlLink state information is

42、propagated & routing tables are calculatedWe elaborate on OSPF stages in following67lHello interval: number of seconds between Hello packetslPriority: used to elect designated router & backuplDead interval: # sec before declaring a non-responding neighbor down.lNeighbor: the Router ID of eac

43、h neighbor from whom Hello packets have recently been receivedlSend Hello packets to establish & maintain neighbor relationship Network maskHello interval Options Priority0 16 24 31Dead intervalDesignated routerBackup designated routerNeighbor 1Neighbor n. . .68lInit bit 1 if pkt is first in seq

44、uence of database description packetslMore bit 1 if there are more database description packets to followlMaster/Slave bit indicates that the router is the master. lLink state ad (LSA) header describes state of router or network; contains info to uniquely identify entry in LSA (type, ID, and adverti

45、sing router).lCan have multiple LSA headers lOnce neighbor routers become adjacent, they exchange database description packets to synchronize their link-state databases. Interface MTU Options Zero I MDatabase Description Sequence Number0 16 24 29 31LSA HeaderMS69lLS type: Router LSAs generated by all OSPF routers; Network LSAs generated by designated routers; Summary LSAs by area border routers; AS-external LSAs by A