51广域网局的基本概念 第5章 接入方式:多点接入 主要任务:路由选择 广域网 主要协议层:网络层 广域网 5.1广域网局的基本概念 层提供的服务 网络层与数据链路层的区别 为传输层提供服务 ·网络层是将源端发出的分组经各种途径送到目的 无连接的服务 而数据链路层仅将数据帧从传输介质的一端送到 每个分组携带源地址和目的地址,被直接发送与 ·因此,网络层是处理端到端数据传输的最低层。 面向连接的服务 一网络层要解决的关键问 了解通信子网的拓扑结构,选择路由 每个分组只携带虚电路号沿着建立好的虚电路进 服务的实现 务的实现 数据报( datagram)服务 虚电路( virtual circui)服务 每个分组都有目的站全地址; 1.在连接建立阶段,各路由器就设置好路由标 路由器对每个分组的路由都进行独立选择 2.在传输阶段,各路由器依据每个分组的个虚电 3.在连接释险段 丘
1
5.2路由选择机制 路由选择机制 1.层次结构的编址方案 2.路由选择的实现-路由表 主机地址=主机接入的路由器号+主机接入的路由器低速端口号 [2 业以 路由器号[饭端口号 通信网络 路由器 路由器1的路由 路由器转发分组时只使用主机地址的21本路由 第一部分;只有分组到达目的主机相连的〖2习本由 路由器时,路由器才使用主机地址的第 142]路由器4 路由表与源站地址无关 路由器2中的路由表 路由表的简化一消除重复项目 路由选择算法 网络越大,重复项目越多 路由算法 使用默认路由代替所有的具有相同“下一站”的 就是产生路由表的算 项目 默认路由比其它项目的优先缀地。若转发分组 是网络层软件的一部分。 时找不到明确的项目对应,就使用默认路由 子网采用数据报方式,每个包都要做路由 曲些类2些本3个慢节 选择; 子网采用虛电路方式,只需在建立连接时 做一次路由选择 理想的路由算法 路由算法分类 正确性( correctness):算法必须正确; 简单性( simplicity):算法开销小,效率高; 健壮性( robustness):算法能适应网络负荷和拓朴的变 非自适应算法(静态路由算法) 简单、开销小,但不能适应网络状态变化 稳定性( stability):算法必须收敛,不能振荡发散 用离线方式求出路由表 振荡:算法得出的路由是在一些路由之间回荡 公平性( fairness):算法对所有用户必须是平等的; 自适应算法(动态路由算法); 最优性( optimality):算法应提供最佳路径选择 复杂、开销大,但能适应 最佳:链路长度、传输时延、数据速率、链路容量、链路 差错率、链路丢失車等
2 差错率 、链路丢失率等
最优化原则( optimality principle) 最短路径路由算法( Shortest Path Routing) 从所有的源结点到一个给定的目的结点的最优路由 的集合形成了一个以目的结点为根的树,称为汇集 属于静态路由算法 基本思想 路由算法的目的是找出并使用汇集树 构建子网的拓扑图,图中的每个结点代表一个路 由器,每条弧代表一条通信线路。为了选择两个 器间的路由,算法在图中找出最短路径 測量路径长度的方法 结点数量 距离、信道带宽等参数的加权函数 路由器B的汇集树 Dijkstra算法 采用标注的方式求出某一结点的汇集树和路由表 D(- ①每个结点用从源结点沿已知最佳路径到本结点的距离 来标注,标注分为临时性标注和永久性标注 ②初始时,所有结点都为临时性标注,标注为无穷 ③将源结点标注为0,且为永久性标注,并令其为工作 >0=+☆ (A. E) pD( ④检查与工作结点相邻的临时性结点,若该结点到工作 结点的距离与工作结点的标注之和小于该结点的标 注,则用新计算得到的和重新标注该结点 橙B ⑤在整个图中查找具有最小值的临时性标注结点,将其 变为永久性结点,并成为下一轮检查的工作结点 (B)pm)“(点m 重复第④、③步,直到所有鲒点成为工作结点 求结点A的汇集树 结点A的汇集树 距离矢量路由算法( Distance vector routing) 属于动态路由算 最初应用于 ARPANET,后来应用于因特网的RP协 议(路由信息协议) 同理,以结点E为源结点,采用m某法,日B 基本思想 求出结点E的汇集树和路由表 的路由表 每个结点通过测取与相邻结点的距离,再依据与其 相邻结点交换的距离信息,间接地求出路由表; 结点E的汇集树 各结点周期性地测取相邻结点的距离 向相邻结点发送它到每个目的结点的距离表 同时,它也接收每个邻居结点发来的距离表; 结点中的老路由表在计算中不被使用
3
网络拓料 结点1的路由表更新 结点1测取相来自相邻结点时延向量结点1的路由表一更新后 邻结点的时延 日的站延迟下一站 结点1测取相来自相邻结点时廷向量结点1的路由表一更新后 邻结点的时延 d1+d2=1+0=1←最小 d=4及3 d3+dx=404相等 d;+42=2+2 d4+d4 d1=1,sn=2 d3=4,s13=3或2或4 选取13=3,(最直接) 结点1测取相来自相邻蛄点时延向量结点1的路由 结点1测取相 相邻结点时延向量结点的路由表一更新后 邻结点的时延 及 251=4 求1和s 求15和s15 求d和S16 路由表一更新前 d2+d24=1+ d12+d26=1 d13+dx=4+2 d+ds=4+1+5 d14+d4=2+0-2←最 d1n+d=2+1-3←最小 结点J收到的相邻 New estimated 距离矢量路由算法一时延的测取 点的时延向量 方法1: ARPANET最初采用,更新周期为128ms 把在一个结点向某条链路发送的等待队列中的分 组数目作为时延 缺点:等待队列长度并不能准确反应时延,影响时 因素还有存储转发处理时间、链路的数据 率、分组长度 方法2: ARPANET后期采用,更新周期为10 子网拓朴图 采用实测方式。分组到达时,记录到达时刻T 当该分组转发完成时,记录完成时刻Te 结点J测取相年结2 即,时延Td=Te-Tr+物理链路时延 注:Te-Tr包含了分组存儲处理时间、等待队列时 间、分组转发用时等 (b)路由表
4
53拥塞控制 针对某个因素改善拥塞 拥塞( congestion) 网络资源上有太多的分组时,导致性能会下降 若结点缓存容量太小,到达结点的分组无空间暂存 ∑对资源的需求>可用资源 若增大结点缓存容量,而链路容量和处理机速度未 提高,分组排队会很长,导致时延增大,可能因超 资源:链路容量、交换结点中的缓存和处理机等 送端进行重发,拥塞更加恶化; 拥塞产生的原因 提高结点处理机速度,增大链路容量,固然可以改 结点缓存容量太小; 善拥塞,但可能瓶颈转移到其它地方。 结点处理机速度不高; 因此,针对某个因素的解决方案,只能对提高网 低带宽线路; 络性能起到一定的好处,甚至仅仅是转移了影响性能 多个输入对应一个输出; 的瓶颈 巨型机 拥塞控制与流量控制的差别 光纤网100Gb/s 拥塞控制( congestion control 发送速率可达1Gb/s 需要确保通信子网能够承载用户提交的通信量, 网络本身不存在拥塞,但流量控制是必须的 是一个全局性过程,涉及主机、路由器等很多因 发送速率1Mb/s 接收速率1Mb/s 流量控制( flow control 与点到点的通信量有关,主要解决快速发送方与 OMb/s 慢速接收方的问题,是局部过程,一般都是基于 反馈进行控制的 网络的输入负荷超过网络传输能力 B Perfect理想控制 直接型存储转发死锁 子网的最大传输容量 Desirable 实际控制 容量为N 当结点3的缓存器被欲输入到结点4的分组队列所添 轻度 无控制 满,同时,结点4的缓存器被欲输入到结点3的分组队 拥塞拥塞 列所添满时,两者都缺乏输入空间,后继分组被丢 弃,因而产生死锁 当中间结点的入、出链路数越多,产生死锁的可能性 发送的分组数 Packets sent 越大 拥塞控制所起的作用 一经验表明,当结点的链路多于11条时,易产生死锁
5