《[文学]计算机网络基椽—第六章（广域网）》由会员分享，可在线阅读，更多相关《[文学]计算机网络基椽—第六章（广域网）（60页珍藏版）》请在金锄头文库上搜索。
1、第六章 网络层,网络层的功能与服务 路由选择 流量控制,拥塞控制,6.1 网络层的模型、功能与服务,主机A,主机B,结点 1,结点 2,结点 3,网络连接,数据链路连接,数据链路连接,传输层,数据链路层,网络层,网络层是通信子网的最高层，对上层用户屏蔽了子网通信的细节， 如子网类型、拓扑结构、子网数目，向上层提供一致的服务、 统一的地址,一、网络层模型,二、网络层的功能,基本功能：实现端到端的网络连接，屏蔽不同子网技术的差异， 向上层提供一致的服务,主要功能： 路由选择和转发 分组的分段与重组，差错控制、顺序化、流量控制,三、网络层的两种操作方式：虚电路和数据报,虚电路 ( Virtual C
2、ircuit ) 服务,在传送数据之前，首先通过虚呼叫建立一条虚电路 所有分组沿同一条路径传送，并且按发出顺序到达 类似电路交换 建立连接之后，分组中只需要携带连接标识 可以在建立连接时协商参数、QoS,数据报 ( Datagram ) 每个分组单独传送 网络为每个分组单独选路，路径可能不同 分组到达顺序可能与发出顺序不同 分组中需要携带完整的目的地址,虚电路,A,B,C,A,B,C,vc1,vc2,vc1: A-1-2-4-B vc2: A-1-3-5-C,数据报,A,B,C,A,B,C,虚电路与数据报的比较,虚电路,数据报,是否需要建立连接,需要,不需要,分组中的目的地址,完整地址,VC标
3、识,路由器中的路由表,只需一个很简单 的路由表,要为每个虚电路 保存一个路由表,选路,每个分组独立选路， 路由可能不同,在VC建立时选路， 所有分组路由相同,几乎不受影响,所有经过该路由器 的VC都将终止,拥塞控制,很难实现,易于实现,路由器故障的影响,差错控制和流量控制,由主机负责,由子网负责,虚电路的路由表（交换表）,路由表在建立虚电路（虚呼叫）时确定。 分组在传送时只需携带虚电路号，虚电路号只具有本地意义， 根据虚电路建立顺序由各主机、各结点自主排序， 入出口号不一定相同。,虚电路路由表建立过程示例,A,E,D,C,B,H2,H3,H1,H4,H5,依次建立5条VC： VC1：A-B-E
4、 VC2：A-B-D VC3：B-D-E VC4：C-E-D VC5：A-B-C-D,入口,出口,H1,H1,H1,1,2,5,0,1,2,B,0,1,2,B,B,入口,出口,A,A,H2,3,0,1,0,E,0,0,1,D,D,入口,出口,B,B,E,0,1,0,H4,0,0,1,E,H4,入口,出口,H3,B,4,0,0,0,E,0,0,2,D,入口,出口,B,D,C,0,0,0,H5,0,1,0,D,A,B,C,D,E,A,2,C,0,H5,C,H4,数据报的路由表,每个分组都需要携带完整的目的地址。 每个结点保存一个到网内其他结点的输出线选择表,虚电路与数据报的权衡： (1) 路由器内
5、存与带宽 (2) 虚呼叫时间与地址分析时间,子网提供的服务与子网结构无关,子网类型,数据报,虚电路,上 层 类 型,无连接,面向连接,IP之上的UDP,IP之上的TCP,X25之上的IP,ATM之上的AAL1,6.2 路由选择,正确、简单、能够自适应（健壮性：Robustness）、 稳定、公平、 最佳,路由选择算法的分类 分类原则：路由选择算法能否随着网络的通信量或 拓扑结构的变化而自适应地进行调整 分类： 非自适应路由算法（静态路由） 自适应路由算法,一、理想的路由选择算法的要求,路由技术,性能标准： hop,distance,delay,speed,cost 何时路由判断： sessio
6、n,packet 何地路由判断： distributed,centralized,source 策略：fixed,adaptive,random,flood 更新时间（ adaptive）：period,topology change,load change 网络信息的来源：all node ,adjacent, node along route,二、最短路径路由选择(固定路由法）：Dijkstra算法(SPF), 目的：求从源结点到网络中其他各结点的最短路径, 步骤： (1) 初始化：建立一个结点集合N，只包含源结点A；对其他各结点v， 与源结点的距离 D(v)= l(A,v)， 若A与v直
7、接相连 ， 若A与v不直接相连,(2) 找一个D(v)值最小的结点w，加入集合N，对所有不在N中的节点, 用D(v)和D(w)+l(w,v)中较小的值更新原有的D(v),(3) 重复步骤(2)，直到所有结点都加入集合,最短路径选择示例,初始化,N,D(B),D(C),D(D),D(E),D(F),D(G),D(H), A ,2 6 , A, B ,9 4 6 ,9 6 5 ,9 6 9,9 8,9 10, A, B, E , A, B, E, G , A, B, E, G, F , A, B, E, G, F, H , A, B, E, G, F, H, C ,10, A, B, E, G,
8、F, H, C, D ,最短路径选择示例,最短路径树,目的结点,后继结点,B,B,C,B,D,B,B,B,B,B,E,F,G,H,结点A的路由表,Example2 of SP,Initially,N,D(1),D(2),D(3),D(4), Vs,8 4 2 6, Vs, V3 ,8 3 5,6 5,6,Vs, V3 ,V2,Vs, V3 ,V2,V4,Example2 of SP(2),Dest.,Next-hop,1,V3,2,V3,3,V3,V3,4,Route Table of Node s,三、非自适应性路由选择策略,向除来端之外的所有端口转发,1. 洪泛法,适用情况：网络中通信量较
9、小时,优点：简单、健壮、可能是最佳路由,缺点：网络中分组数目剧增，极易导致拥塞,洪泛（Cont.),不需要网络信息 数据包发送到每个邻居 收到的数据包转发到所有的输出线路 多个副本到达目的端 问题：如何限制分组兜圈子？ 每个数据包需要单独标识；节点记录已经转发的包；使用Hop count,洪泛举例（Cont.),洪泛（Cont.),尝试所有可能的路由（健壮） 至少有一个数据包使用最短路径（建立VC) 遍历所有的节点（用于路由信息的分发）,2. 静态路由法,系统配置时生成路由表，查表选路 适用情况：网络拓扑固定，且通信量相对稳定 优点：简单 缺点：不健壮、不保证最佳路由,3. 随机走动法（ran
10、dom walk),随机选择一条链路 适用情况：可能发生结点或链路故障时 优点：健壮 缺点：不保证最佳路由,路由表中包含了多条输出链路极其概率，分组根据当前产生的 随机数，查表选择路由,A,C,B,D,E,P,M,N,L,K,目的地,经过,经过,经过,概率,概率,概率,A,M,结点K的路由表,0.50,0.40,0.10,M,M,M,M,L,L,N,N,N,N,N,P,P,P,B,C,D,E,0.35,0.35,0.30,0.65,0.25,0.10,0.55,0.30,0.15,0.45,0.30,0.25,4. 分散通信量法,优点：使网络通信量更加平衡；平均分组时延较小 缺点：路由表占用内
11、存,四、自适应路由选择策略,特点：尽快转发， 只根据结点本身的状态决定路由选择,1. 孤立的路由选择（Hot-potato算法）, 选择策略：Min ( 等待队列长度 + 到目的地址偏移值 ),来自X,P,N,M,L,结点K,L、M、N、P的 偏移分别为：0，3，6，9， K收到的分组应转发给,L,2. 分布式路由选择（距离矢量路由选择）, 特点：每个结点周期性地和邻居结点交换路由信息， 根据新的状态更新路由, 选择策略：每个结点i保持2个向量：时延向量Di、后继结点向量Si,Di = dij dij 表示结点i到结点j的最小时延的当前值,Sj = sij sij 表示结点i到结点j的当前最小
12、时延路由的后继结点,周期性修改向量值： dij = Min ( dik + dkj ),sij = k, 使( dik + dkj )最小的k,分布式路由选择示例,A,B,C,D,E,F,G,H,I,J,K,L,A,B,C,D,E,F,G,H,I,J,K,L,A,I,H,K,DJ,SJ,JA=8,JI=10,JH=12,JK=6,J 的路由表,0,12,25,40,14,23,18,17,21,9,24,29,0,24,36,18,27,7,20,31,20,11,22,33,0,0,20,31,19,8,30,19,6,14,7,22,9,21,28,36,24,22,40,31,19,22
13、,10,9,8,A,A,20,28,I,20,H,17,I,I,I,H,H,-,K,K,30,18,12,10,0,6,15,分布式路由选择示例(2),Dest. A B C D E F G H I J K L via A (8, 20, 33, 48, 22, 31, 26, 25, 29, -, 32, 37) I (34, 46, 28, 37, 17, 30, 41, 30, 10, -, 32, 43) H (32, 43, 31, 20, 42, 31, 18, 12, 26, -, 34, 21) K (27, 34, 42, 30, 28, 46, 37, 25, 28, -,
14、 6, 15) Taking the minimum for each destination: (8,20,28,20,17,30,18,12,10,0,6,15) Outgoing line: (A,A,I,H,I,I,H,H,I,-,K,K),分布式路由选择（距离矢量路由选择）, 优点：对网络负载和拓扑的变化适应性都很好, 问题：(1) 链路时延采用等待队列+常数偏移来计算， 没有考虑数据率或分组长度的不同，不够准确 (2) 分组进入结点时，要经过处理才进入等待队列 (3) 等待队列的瞬时值不能代表平均时延 (4) 无穷计算问题 (5) 周期性的状态信息交换极大地增加了网络中的业务开销,无穷计算问题, 对好消息（增加链路）传播很快， 对坏消息（链路失效）传播时间可 能无限,A,B,C,D,新增加结点A,开始, ,1次交换信息之后,1 ,1 2 ,2次交换信息之后,3次交换信息之后,1 2 3, 水平分割算法：不向最短路径上的后继结点报告到某结点的距离 （设置为 ）,无穷计算问题的解决,Distance Vector Routing,A,B,C,D
