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

1、通信网理论基础 第三部分 图论基础 与 应用,基本概念,图 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是图的一条边

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

3、5,V6 V1,V2,V3,V5,V6 V1,V2,V3,V6 V1,V2,V4,V3,V5,V6 V1,V2,V4,V5,V6 V1,V3,V2,V4,V5,V6 V1,V3,V6 V1,V4,V3,V6 总共14条(其余的请自行列出),简单图 (2),两顶点间的所有路径中有一条最短路径,如:V1,V3,V6 顶点间的距离是所有路径中边数最少的路径的边的数目 回路是起于和止于同一顶点的路径 例如:. V1,V3,V4,V1,有向图,边有方向性的图 有向图 G(V,E) 的边由一对顶点的有序组合来定义 代表边的线段用箭头表示其方向 允许存在平行边,只要它们的方向相反 便于用图表示通信网络 每条

4、有向边表达一个方向上的数据流 仍然可用邻接矩阵表示 除非每对相邻的顶点用平行边连接,否则邻接矩阵是不对称的,加权图,或加权有向图 每条边有一与之关联的数(权值w) -便于说明路由算法 邻接矩阵定义为: ai,j = wi,j if (i,j) E 0 otherwise wi,j 是与边( i, j )关联的权值 路径长度是权值之和 最短距离路径不一定是长度最短路径(见下面两张PPT),加权图与邻接矩阵,V1 至 V6 的路径距离 和 路径长度,路径 距离 长度 V1,V2,V3,V4,V5,V6 5 11 V1,V2,V3,V5,V6 4 8 V1,V2,V3,V6 3 10 V1,V2,V

5、4,V3,V5,V6 5 10 V1,V2,V4,V5,V6 4 7 V1,V3,V2,V4,V5,V6 5 16 V1,V3,V6 2 10 V1,V4,V5,V6 3 4,树,树是图的子集 以下几项定义是等效的: * 树是一种简单图,顶点i 和 j 之间只有一条简单路径 * N个顶点的简单图如果只有N-1 条边,没有回路 * N个顶点的简单图如果只有N-1条边,而且是连通的 可以指定一个顶点为“根” 根通常画在上部 与根邻接的顶点画在下一层 这些顶点可以到达树根,路径距离为1,树中顶点的等级关系,每个顶点(除根外)有一个父顶点 靠根一边的邻接顶点 每个顶点有0个或几个子顶点 离根远的邻接顶

6、点 没有子顶点的顶点称为叶 层次等级 直接在根下面的顶点是第一层 第一层顶点的子顶点是第二层,树的例,子图,从图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的生成树通常并不唯一,生成树的例子,生成树的“先广搜索”算法,将顶点划分成不同的层次 在处理下一层之前,先处理完本层的所有顶点

7、 从任一顶点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加入到树中, 这是第一层 在第一层的顶点

8、上按序重复上述过程,得到第二层 是否所有顶点都处理完? 如果没有,在第二层的顶点上重复处理过程,得到第三层.,上例的图示,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 bridge root port = port with the least-cost path

9、to the root bridge Select 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 designated bridge All root ports and all designated ports are placed into a “forwarding” state. These are the only ports

10、 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

11、,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) 每个路由器是一个顶点 如路由

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

13、 = 到目前为止算法已经用到的顶点的临时集合 Tree = T中顶点组成的生成树,它包括从s到T中每个顶点的最小代价路径上的边 w(i,j) = 从顶点i 到顶点 j的链路代价, w(i,i) = 0 w(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

14、 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的边的连接,.,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

15、(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 到

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

17、n的链路结束,Bellman-Ford Algorithm (3) 说明,结果与 Dijkstra 算法的结果相同 运行时间是 |V| x |E| 的量级,.,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的最短路径的长度，和它到自己的邻点的链路的代价值， 所以为了求出到所有点的最短路

18、径，每点需与其邻接点交换各自到所有其他点的最短路径长度的当前估计值,Bellman-Ford 算法用于例图,Dijkstra 和 Bellman-Ford 算法 的运算结果,比较所需要的信息 Bellman-Ford 算法,顶点n处的计算需要知道到所有邻接点的链路的代价,以及从源点到这些点的路径的总代价e 每个顶点需要维持一个到网络中所有其他顶点的路径及其代价的表 与其直接邻接顶点交换上述信息 每个顶点都用Bellman-Ford 算法步骤 2 中的表达式更新其路径与代价表,比较两种算法所需要的信息 -Dijkstra 算法,步骤 3 要求每个顶点知道网络拓扑的完整信息,因而: 必须知道网络中

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

20、by a single organization Same routing protocol need not be run within the AS But, to the outside world, an AS should present a consistent picture of what ASs are reachable through it Stub AS: has only a single connection to the outside world. Multihomed AS: has multiple connections to the outside wo

21、rld, but refuses to carry transit traffic Transit 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 number Currently, there are about 11,000 registered ASs in Internet (and growi

22、ng) Stub AS, which is the most common type, does not need an AS number since the prefixes are placed at the providers routing table Transit AS needs an AS number Request 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

23、Gateway Protocol (IGP): routing within AS RIP, OSPF Exterior Gateway Protocol (EGP): routing between ASs BGPv4 Border Gateways perform IGP 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 packe

24、t 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 database Know how many routers in network Interfaces Protocol ID 89 TOS 0, IP precedence field set to internetwork control

25、 to get precedence over normal traffic OSPF 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 nets Five OSPF packet types: Hello Database description Link state request; Link state update; Link state

26、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 networks Adjacencies are established contains info t

27、o 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

28、generated by designated routers; Summary LSAs by area border routers; AS-external LSAs by ASBRs LS id: identifies piece of routing domain being described by LSA LS Seq. Number: numbers LSAs to detect old/duplicate LSAs LS 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 algorithm When the connection between two neighbors comes up, the routers must wai