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

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

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

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

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

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

6、 v, w Vl图G的子图T是一颗生成树,如果: T 是树 包含G的所有顶点l从图G中删去一些边,使所有的回路不复存在,但保持图的连通性:l图G的生成树通常并不唯一l将顶点划分成不同的层次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)层 直到所有顶点被处理完毕l选择顶点顺序 如: V1,V2,V3,V4,V5,V6l选择“根” 例如

7、 V1l现在树T只包含一个顶点V1 ,不含边l在树上增加边(V1,x) 和顶点x, 但不要形成回路:将边 (V1,V2), (V1,V3), (V1,V4) 和顶点 V1,V2, V3加入到树中,这是第一层l在第一层的顶点上按序重复上述过程,得到第二层 是否所有顶点都处理完? 如果没有,在第二层的顶点上重复处理过程,得到第三层.LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)Select a root bridge among all the bridges. root bridge = the low

8、est bridge ID.Determine the root port for each bridge except the root bridge root port = port with the least-cost path to the root bridgeSelect a designated bridge for each LAN designated bridge = bridge has least-cost path from the LAN to the root bridge. designated port connects the LAN and the de

9、signated 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.LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)LAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)

10、(1)(1)(1)(2)(2)(2)(2)(3)Bridge 1 selected as root bridgeLAN1LAN2LAN3B1B2B3B4B5LAN4(1)(2)(1)(1)(1)(1)(2)(2)(2)(2)(3)Root port selected for every bridge except root portRRRRlBFS算法可以得到从根顶点s到所有其他顶点的最短距离路径和距离 (s,v) l任何从s 到v 的路径中BFS给出的路径是距离最短的,即该路径边数之和最小。l分组交换,帧中继,ATM等网络可以看作一张图 每个节点是图中一顶点 每一链路是一对平行边l对于互联网

11、(Internet 或 intranet) 每个路由器是一个顶点 如路由器直接相连,双向连接相当于一对平行边 如多于两个路由器,则由多对平行边构成表示网络的图 一对边连接一对路由器l为将分组由源送到目的,需要路由决策 等效于在图上找出路径l基于最小代价 最少跳数( hop )l每条边(一跳)的权重为1 l相当于最短距离路径 或者, 每跳有一相关联的代价(见下一PPT) 路径的代价是路径中各链路的代价之和 需要找出最小代价路径l相当于加权图中的最小长度路径l反比于路径的容量l正比于当前的负荷l链路的货币价值l几种因素的组合l在不同方向上的代价可能不同lN = 网络顶点的集合ls = 源顶点 (

12、起始点 )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的最小代价路径的代价l初始化lT = Tree = s 临时顶点集合中暂时只含源顶点lL(n) = w(s,n) for n s ; 到邻点的初始路径代价就是链路代价l取下一个顶点l找 x T 使 L(x) =

13、 min L(j), j Tl将 x 加入到 T 和 Tree 中l将关联x,且使L(x) 成为最小代价的边加入到Tree中l它是路径的最后一跳l更新最小代价路径lL(n) = minL(n), L(x) + w(x,n) n Tl如果后一项最小,从s到n的路径就是从s到x的路径与从x到n的边的连接整理ppt34TSNXnw(x, n)L(n)L(x)已算出最短路径的点的集合找 x T 使 L(x) = min L(j), j Tl x TL(n) = minL(n), L(x) + w(x,n) n T所以，S需要知道w(x,n)-各点与其邻点间直接相连链路的代价因而需要与所有其他各点交换路

14、由信息某点（s) 已知网络中其他各点到其邻点的链路的代价值w(x,n), 计算S到其他各点的最短路径l当所有顶点都加入到T以后,算法结束l需要 |V| 次迭代l结束时 L(x) 是s 到 x 的最小代价路径的代价值 Tree 是原图的一颗最小生成树l定义了从s到其他顶点的最小代价路径l每次迭代有一个新的顶点加入到T中,运行时间是 |V|2 量级ls = 源顶点(起始点)lw(i,j) = 从顶点i 到顶点 j 的链路的代价值 w(i,i) = 0 w(i,j) = 如 i, j 不直接相连 w(i,j) 0 如 i,j 直接连接lh = 在算法的当前步骤中路径的最大链路数lLh(n) = 从顶

15、点s 到 n 的最小代价路径的代价,限制条件是路径的链路数不超过hl初始化lL0(n) = n slLh(s) = 0 hl更新l对每个相继的 h 0l对每个n s, 计算: Lh+1 (n) = minLh(j)+ w(j,n), jl找到实现最小值的顶点jl,将n与该前趋顶点j相连,l删除n与此前计算得到与j不同的前趋顶点的连接,l从s到n的路径以j到n的链路结束l结果与 Dijkstra 算法的结果相同l运行时间是 |V| x |E| 的量级整理ppt40Sn已知 n 与其邻点间链路的代价值w(j,n); j 到s 的最短路径的代价值L(j); 找n 到s的最短路径；jl对每个n s,

16、计算: Lh+1 (n) = minLh(j)+ w(j,n), jw(j,n)（已知，因为与n直连）L(n)L(j)n点在计算时需知其邻接点的L(j)当前估计的到S的最短路径的长度，和它到自己的邻点的链路的代价值，所以为了求出到所有点的最短路径，每点需与其邻接点交换各自到所有其他点的最短路径长度的当前估计值l顶点n处的计算需要知道到所有邻接点的链路的代价,以及从源点到这些点的路径的总代价el每个顶点需要维持一个到网络中所有其他顶点的路径及其代价的表l与其直接邻接顶点交换上述信息l每个顶点都用Bellman-Ford 算法步骤 2 中的表达式更新其路径与代价表l步骤 3 要求每个顶点知道网络拓

17、扑的完整信息,因而: 必须知道网络中所有链路的代价值 每个顶点必须与所有其他顶点交换信息l究竟哪个算法好,需要考虑算法的运行时间等其他因素l当网络拓扑和链路代价处于准静态时,两种算法都收敛l给出相同的结果l如果链路代价变化,算法会企图跟上这种变化l如果链路代价与通信流量有关,而后者又与路由选择有关,则: 存在反馈 可能产生不稳定lGlobal Internet viewed as collection of autonomous systems. lAutonomous system (AS) is a set of routers or networks administered by a

18、single organization lSame routing protocol need not be run within the ASlBut, to the outside world, an AS should present a 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

19、, but refuses to carry transit trafficlTransit AS: has multiple connections to the outside world, and can carry transit and local traffic.lFor 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,

20、which is the most common type, does not need an AS number since the prefixes are placed at the providers routing tablelTransit AS needs an AS numberlRequest an AS number from the ARIN, RIPE and APNICRRRRRRRRAS AAS BAS CIGPEGPIGPIGPInterior Gateway Protocol (IGP): routing within AS RIP, OSPFExterior

21、Gateway Protocol (EGP): routing between ASs BGPv4Border Gateways perform IGP & EGP routinglBasic RoutinglRouting Information Protocol (RIP)lOpen Shortest Path First (OSPF)lBorder Gateway Protocol (BGP)lRFC 1058lRIP based on routed, “route d”, distributed in BSD UNIXlUses the distance-vector algo

22、rithmlRuns on top of UDP, port number 520lMetric: number of hopslMax limited to 15 suitable for small networks (local area environments) value of 16 is reserved to represent infinity small number limits the count-to-infinity problem lRouter sends update message to neighbors every 30 seclA router exp

23、ects to receive an update message from each of its neighbors within 180 seconds in the worst caselIf 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)lUses split horizon with poisoned

24、 reverse lConvergence speeded up by triggered updates neighbors notified immediately of changes in distance vector table lRouters 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

25、over LANs & specifically addressed on pt-pt or multi-access non-broadcast netslTwo RIP packet types: request to ask neighbor for distance vector table response to advertise distance vector tablelperiodically; in response to request; triggeredCommand Version ZeroAddress family identifier ZeroIP a

26、ddressZeroZeroMetric0 8 16 31. . .Request/Response1/22 for IPRIPentryUp to 25 RIP entries per messagelCommand: 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 m

27、ask informationlCannot work with variable-length subnet masksRIP v2 (RFC 2453):lSubnet mask, next hop, routing domainlcan work with CIDRlstill uses max cost of 16lBasic RoutinglRouting Information Protocol (RIP)lOpen Shortest Path First (OSPF)lBorder Gateway Protocol (BGP)lUsed in OSPF to distribute

28、 link state (LS) informationlForward incoming packet to all ports except where packet came inlPacket eventually 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

29、each packet; wont flood if TTL is reached Each router adds its identifier to header of packet before it floods 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 same10.5.1.110.5.1.310.5.1

30、.510.5.1.210.5.1.410.5.1.6At steady state: lAll routers have same LS databaselKnow how many routers in networklInterfaces & links between routerslCost of each linklOccasional Hello messages (10 sec) & LS updates sent (30 min)lTo improve scalability, AS may be partitioned into areas Area is i

31、dentified by 32-bit Area ID Router in area only knows complete topology inside area & limits the 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 r

32、outer has all links to nets within the same arealArea border router has links to more than one arealbackbone router has links connected to the backbonelAutonomous system boundary (ASB) router has links to another autonomous system. ASB: 4ABR: 3, 6, and 8IR: 1,2,7BBR: 3,4,5,6,8Area 0.0.0.1Area 0.0.0.

33、2Area 0.0.0.3R1R2R4R5R7N1N2N3N4N5N6N7To another ASArea 0.0.0.0R = router N = networkR8R3R6lNeighbor 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

34、, Exchange, Loading, FulllAdjacent router: neighbor routers become adjacent when they synchronize 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 routersl

35、Reduces size of topological database & routing trafficlReduces number of adjacencieslElected 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

36、adjacencies with routers on multi-access networklBackup prepared to take over if designated router failslLink 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 sta

37、te of router links within area; flooded within area onlylNet link ad: generated by the designated 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: generate

38、d by ASB routers describes routes to destinations outside the OSPF net flooded in all areas in the OSPF netlOSPF 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 ad

39、dress 224.0.0.5 (allSPFRouters on pt-2-pt and broadcast nets)lOSPF packets sent on specific IP addresses on non-broadcast netslFive OSPF packet types: Hello Database description Link state request; Link state update; Link state acklType: Hello, Database description, Link state request, Link state up

40、date, Link state acknowledgements Version Type Packet lengthRouter IDArea IDChecksum Authentication typeAuthenticationAuthentication0 8 16 31OSPFcommonheaderOSPFpacketbodyDatalDiscover neighbors by sending Hello packets (every 10 sec) and designated router elected in multiaccess networkslAdjacencies

41、 are established & link state databases are synchronizedlLink state information is propagated & routing tables are calculatedWe elaborate on OSPF stages in followinglHello interval: number of seconds between Hello packetslPriority: used to elect designated router & backuplDead interval:

42、# sec before declaring a non-responding neighbor down.lNeighbor: the Router ID of each 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 router

43、Backup designated routerNeighbor 1Neighbor n. . .lInit bit 1 if pkt is first in sequence 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

44、 or network; contains info to uniquely identify entry in LSA (type, ID, and advertising 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 HeaderMSlLS type: Router LSAs generated by all OSPF routers; Network LSAs generated by designated routers; Summary LSAs by area border routers; AS-external LSAs by ASBRslLS id: i