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
间接型存储转发死锁 拥塞造成的吞吐量下降 c=1 存队列 缓存队列 入2 当每个结点的缓存器都被待发至下一结点的分组所 λ:数据传输速率 c:链路容量 占满,因此,各结点的分组都因为后续结点无法提 供空闲缓存器而不能发至下一结点,因而产生死 若λ1-λ2-1,结点3的转发速率λ1-1,λ=1;整个网络 为:λ+2=2 克服存儲转发死锁,一般采用结点间的流量控制方 若λ1=1,2=10,结点1和结点2占用结点3的缓存空间的 法,即调整发送结点的发送速率,使接收结点能够 比率为10:1,因此,结点3的转发速率λn=0.1 及时处理分组存储转发过程。 入2=1;整个网络为:λ1+2=11 拥塞控制的基本原理 衡量网络是否拥塞的参数 根据控制论,拥塞控制方法分为两类 开环控制 缺乏缓冲空间所造成的分组丢失率 事先考虑发生拥塞的因素,进行拥塞控制设计; 平均队列长度 在网络运行时,不在考虑网络的状态而改变 一超时重传的分组的数; 闭环控制 平均分组时延; 基于反馈机制 分组时延的变化率 工作过程 监测网络系統,发现何时何地发生拥塞 把发生拥塞的消息传给能采取动作的站点 上迷指标越高,拥塞度越大, 调整网絡系统的运行,解决拥塞问题。 拥塞控制策略一许可证法 一全局性控制方法; 拥塞控制策略一反馈法 在子网中设置一定数量的许可证分组,在网中随机巡游 向负載发生源发送一个告警分组; 任何一个主机发送到子网的分组必须获得一个许可证; 分组结构中保留一个位或域用来表示发生拥塞,一 当传送到目的结点后,许可证归还给子网;以供其它欲 进入子网的分组捕获。 旦发生拥塞,路由器将所有的输出分组置位,向邻 局限性 居告警 增加了子网负荷(许可证分组在子网中的流动 主机或路由器主动地、周期性地发送探报,查询是 改进:每个结点设置一个小容量的许可证池,一方面在 减少进场时延,一方面减少许可证在子网中的数量,堤 否发生拥塞 高子网的性能
6 及时处理分组存储转发过程
5.4X.25网 X.25规定了 DTE-DCE的接口 X25 X25分组交换网,它是在二十多 根据 CCITT(即现在的ITUT)的X25建议 书实现的计算机网络 X25只是一个对公用分组交换网接口的规约。 X25接口 X25所讨论的都是以面向连接的虚电路服务为 OrE OCE 25公用分组交换 X.25的层次关系 X.25的层次关系 砻繼后,靚粼委筹 隼甓锓規曾P。.的一个子集 在分组层DTE与DCE 分组层(网络层) X25首部 用户数据 数路后[AP首邮5 LAPB尾部 X25 信笔 以及分 组序号等控制信息都写在X25分组的首部中 X.25网与|P网 X.25网退出了历史舞台 基于旧P协议的因特网是无连接的,只提供尽最 到了20世纪90年代,情况 大努力交付的数据报服务,无服务质量可言 化。通信 输质量大大提高使得误码率降低好几个数量级 X25网是面向连接的,能够提供可靠交付的虚 X25十分复杂的数据链路层协议和分组层协 路服务,能保证服务质量 已成为多余的 正因为X25网能保证服务质量,在二十多年前 PC机的价格急剧下降使得无硬盘的哑终端退出 它曾经是颇受欢迎的一种计算机网络 了通信市场。这正好符合因特网当初的设计思 量简单而智能
7 5.4 X.25 网 • X.25 网就是 X.25 分组交换网,它是在二十多年 前根据 CCITT(即现在的 ITU-T)的 X.25 建议 书实现的计算机网络。 • X.25 只是一个对公用分组交换网接口的规约。 X.25 所讨论的都是以面向连接的虚电路服务为 基础。 X.25 规定了 DTE-DCE 的接口 X.25 接口 X.25 接口 X.25 公用分组交换网 VC2 VC1 DTE DTE DCE DCE DTE DCE X.25 接口 X.25 的层次关系 •用户数据在 X.25 的分组层(相当于网络层)加 上 X.25 的首部控制信息后,就组装成为 X.25 分组。 •在数据链路层使用的是HDLC 的一个子集— — 平衡型链路接入规程 LAPB。 •在分组层DTE 与 DCE 之间可建立多条逻辑信 道(0~4095 号) ,使一个DTE 同时和网上其他多 个 DTE 建立虚电路并进行通信。 • X.25 还规定了在经常需要进行通信的两个 DTE 之间可以建立永久虚电路。这些虚电路号以及分 组序号等控制信息都写在 X.25 分组的首部中。 X.25 的层次关系 LAPB 帧 X.25 分组 分组层(网络层) 数据链路层 用户数据 X.25首部 用户数据 LAPB首部 LAPB尾部 X.25 网与 IP 网 •基于 IP 协议的因特网是无连接的,只提供尽最 大努力交付的数据报服务,无服务质量可言。 • X.25 网是面向连接的,能够提供可靠交付的虚 电路服务,能保证服务质量。 •正因为 X.25 网能保证服务质量,在二十多年前 它曾经是颇受欢迎的一种计算机网络。 X.25 网退出了历史舞台 •到了 20 世纪 90 年代,情况就发生了很大的变 化。通信主干线路已大量使用光纤技术,数据传 输质量大大提高使得误码率降低好几个数量级, 而 X.25 十分复杂的数据链路层协议和分组层协 议已成为多余的。 • PC 机的价格急剧下降使得无硬盘的哑终端退出 了通信市场。这正好符合因特网当初的设计思 想:网络应尽量简单而智能应尽可能放在网络以 外的用户端
5.5帧中继FR 551帧中继的工作原理 帧中继减少结点处理时间 在20世纪80年代后期,许多应用都迫切要求 ·帧中继不使用差错恢复和流量控制机制。 增加分组交换服务的速率 帧中继FR( Frame Relay)就是一种支持高速交 当帧中继交换机收到一个帧的首部时,只 换的网络体系结构。 要一查出帧的目的地址就立即进行转发 ·帧中继在许多方面非常类似于X25,被称为第 二代的X25 因此在帧中继网络 个帧的处理时间 比X25网约减少一个数量级。这样,帧 今天的数字光纤网比早期的电话网具有低得多的 的处理时间 中继网络的吞吐量要比X25网络的提高 个数量级以上 分组的处理能力也就增大了。 帧中继对差错的处理 帧中继使用虚电路 帧中继的逻辑连接的复用和交换都在第二层处 当检测到有误码时,结点要立即中止这次传输。 理,而不是像X25在第三层处理 当中止传输的指示到达下个结点后,下个结点也 ·帧中继网络向上提供面向连接的虚电路服务。虚 立即中止该帧的传输,并丢弃该帧 电路一般分为交换虚电路Svc和永久虚电路 ·如果需要重传出错的帧,则由源站使用高层协议 PvC两种。 (而不是帧中继协议)请求重传该帧 帧中继网络通常为相隔较远的一些局域网提供链 ·因此,仅当帧中继网络本身的误码率非常低时 路层的永久虚电路服务,它的 帧中继技术才是可行的 省去建立连接的过程。 如果有N个路由器需要用帧中继网络进行连接 那么就一共需要有NN-1)/2条永久虚电路 帧中继提供虚电路服务 帧中继的控制信令 帧中继交 ·帧中继的呼叫控制信令是在与用户数据分开的 帧中继网 局域网 另一个逻辑连接上传送的(即共路信令或带外 信令) 这点和X25很不相同。X25使用带内信令 即呼叫控制分组与用户数据分组都在同一条虚 虚电路像一条专用电路 电路上传送 用户看不见帧中继网络内的帧中继交换机 虚电路 帧中继网
8 5.5 帧中继 FR 5.5.1 帧中继的工作原理 •在 20 世纪 80 年代后期,许多应用都迫切要求 增加分组交换服务的速率。 •帧中继 FR (Frame Relay)就是一种支持高速交 换的网络体系结构。 •帧中继在许多方面非常类似于 X.25,被称为第 二代的 X.25。 •今天的数字光纤网比早期的电话网具有低得多的 误码率,如果减少结点对每个分组的处理时间, 则各分组通过网络的时延亦可减少,同时结点对 分组的处理能力也就增大了。 帧中继减少结点处理时间 •帧中继不使用差错恢复和流量控制机制。 •当帧中继交换机收到一个帧的首部时,只 要一查出帧的目的地址就立即进行转发。 •因此在帧中继网络中,一个帧的处理时间 比 X.25 网约减少一个数量级。这样,帧 中继网络的吞吐量要比 X.25 网络的提高 一个数量级以上。 帧中继对差错的处理 •当检测到有误码时,结点要立即中止这次传输。 •当中止传输的指示到达下个结点后,下个结点也 立即中止该帧的传输,并丢弃该帧。 •如果需要重传出错的帧,则由源站使用高层协议 (而不是帧中继协议)请求重传该帧。 •因此,仅当帧中继网络本身的误码率非常低时, 帧中继技术才是可行的。 帧中继使用虚电路 • 帧中继的逻辑连接的复用和交换都在第二层处 理,而不是像 X.25 在第三层处理。 • 帧中继网络向上提供面向连接的虚电路服务。虚 电路一般分为交换虚电路 SVC和永久虚电路 PVC两种。 • 帧中继网络通常为相隔较远的一些局域网提供链 路层的永久虚电路服务,它的好处是在通信时可 省去建立连接的过程。 • 如果有 N 个路由器需要用帧中继网络进行连接, 那么就一共需要有 N(N –1)/2 条永久虚电路。 帧中继的控制信令 •帧中继的呼叫控制信令是在与用户数据分开的 另一个逻辑连接上传送的(即共路信令或带外 信令)。 •这点和 X.25 很不相同。X.25 使用带内信令, 即呼叫控制分组与用户数据分组都在同一条虚 电路上传送。 帧中继网 帧中继交换机 路由器 局域网 局域网 虚电路 路由器 帧中继提供虚电路服务 帧中继网 路由器 局域网 局域网 虚电路 路由器 虚电路像一条专用电路 用户看不见帧中继网络内的帧中继交换机
帧中继网络的工作过程 帧中继网络的工作过程 用户在局域网上传送的MAC帧传到与帧中继 路由器就剥去MAC帧的首部,将|P数据报交 络相连接的路由器。 给路由器的网络层 网络层再将|P数据报传给帧中继接口卡 帧中继网 叵白×嫩网 帧中继接口卡把IP数据报封装到帧中继帧的信 息字段 帧中继网络的工作过程 加上帧中继帧的首部(包括帧中继的标志字段和 地址字段,帧中继帧的标志字段和PPP帧的一 样),进行CRC检验后,加上帧中继帧的尾部 ·为了区分开不同的永久虚电路PV (包含帧检验序列字段和标志字段),就构成了 C的两个端点都各有一个数据链路连接标识 帧中继 符DLcl DCLI E Data Link Connection Identifier. 帧检验序列标志 帧中继网 帧中继帧 发送在前 帧中继网络的工作过程 帧中继网络的工作过程 帧中继接口卡将封装好的帧通过向电信公司租来 ·当帧中继帧被转发到虛电路的终点路由器时,终 专线发送给帧中继网络中的帧中继交换机。 点路由器就剥去帧中继帧的首部和尾部,加上局 帧中继交换机收到帧中继帧就按地址字段中的虛 域网的首部和尾部,交付给连接在此局域网上的 电路号转发帧(若检查出有差错则丢弃) 目的主机 局域网 帧中继网 帧中继网
9 帧中继网 路由器 局域网 局域网 虚电路 路由器 帧中继网络的工作过程 •用户在局域网上传送的 MAC 帧传到与帧中继 网络相连接的路由器。 帧中继网 路由器 局域网 局域网 虚电路 路由器 帧中继网络的工作过程 •路由器就剥去 MAC 帧的首部,将 IP 数据报交 给路由器的网络层。 •网络层再将 IP 数据报传给帧中继接口卡。 帧中继帧 发送在前 标 志 地 址 信 息 帧检验序列 标 志 字节 1 2~4 可 变 2 1 首部 尾部 •帧中继接口卡把 IP 数据报封装到帧中继帧的信 息字段。 •加上帧中继帧的首部(包括帧中继的标志字段和 地址字段,帧中继帧的标志字段和 PPP 帧的一 样),进行 CRC 检验后,加上帧中继帧的尾部 (包含帧检验序列字段和标志字段),就构成了 帧中继帧。 IP 数据报 帧中继网 路由器 局域网 局域网 虚电路 路由器 帧中继网络的工作过程 •为了区分开不同的永久虚电路 PVC,每一条 PVC 的两个端点都各有一个数据链路连接标识 符 DLCI。 • DCLI 是 Data Link Connection Identifier。 帧中继网 路由器 局域网 局域网 虚电路 路由器 帧中继网络的工作过程 •帧中继接口卡将封装好的帧通过向电信公司租来 的专线发送给帧中继网络中的帧中继交换机。 •帧中继交换机收到帧中继帧就按地址字段中的虚 电路号转发帧(若检查出有差错则丢弃)。 帧中继网 路由器 局域网 局域网 虚电路 路由器 帧中继网络的工作过程 •当帧中继帧被转发到虚电路的终点路由器时,终 点路由器就剥去帧中继帧的首部和尾部,加上局 域网的首部和尾部,交付给连接在此局域网上的 目的主机
帧中继网络的工作过程 5.5.2帧中继的帧格式 目的主机若发现有差错,则报告上层的TCP协 即使TCP协议对有错误的数据进行了重传,帧 1帧检验序列标志 中继网也仍然当作是新的帧中继帧来传送,而并 不知道这是重传的数据 发送在前 标志字段是一个01111110的比特序列 用于指示帧中继帧的起始和结束 它的惟一性是通过比特填充法来确保的。 帧中继的帧格式 帧中继的帧格式 P数据报 标志地址 帧检验序列标志 陈验序列 中继帧 帧中继帧 发送在前 信息学段是长度可变的用户数据。 帧检验序列字段是2字节的CRC检验。 当检测出差错时,就将此帧丢弃。 帧中继的帧格式 地址字段中的几个重要部分 P数据报 数据链路连接标识符DLc|DLc字段的长度 默认值2字节地址字段) 也可扩展为16bit(用3字节地址字段),或23 帧检验序列标志 t(用4字节地址字段),这取决于扩展地址字 DLcI的值用于标识永久虚电路(PvC)、呼叫控制 或管理信息 地址字段一般为2字节 ·数据链路连接标识符DLC只具有本地意义。 但也可扩展为3或4字节
10 帧中继网络的工作过程 •目的主机若发现有差错,则报告上层的 TCP 协 议处理。 •即使 TCP 协议对有错误的数据进行了重传,帧 中继网也仍然当作是新的帧中继帧来传送,而并 不知道这是重传的数据。 5.5.2 帧中继的帧格式 帧中继帧 发送在前 标 志 地 址 信 息 帧检验序列 标 志 字节 1 2~4 可 变 2 1 首部 尾部 IP 数据报 标志字段是一个01111110 的比特序列, 用于指示帧中继帧的起始和结束。 它的惟一性是通过比特填充法来确保的。 帧中继的帧格式 帧中继帧 发送在前 标 志 地 址 信 息 帧检验序列 标 志 字节 1 2~4 可 变 2 1 首部 尾部 IP 数据报 信息字段是长度可变的用户数据。 帧中继的帧格式 帧中继帧 发送在前 标 志 地 址 信 息 帧检验序列 标 志 字节 1 2~4 可 变 2 1 首部 尾部 IP 数据报 帧检验序列字段是 2 字节的 CRC 检验。 当检测出差错时,就将此帧丢弃。 帧中继的帧格式 帧中继帧 发送在前 标 志 地 址 信 息 帧检验序列 标 志 字节 1 2~4 可 变 2 1 首部 尾部 IP 数据报 地址字段一般为2 字节, 但也可扩展为 3 或4 字节。 地址字段中的几个重要部分 •数据链路连接标识符 DLCI DLCI 字段的长度一 般为10 bit(采用默认值 2 字节地址字段),但 也可扩展为 16 bit(用 3字节地址字段),或 23 bit(用4 字节地址字段),这取决于扩展地址字 段的值。 • DLCI 的值用于标识永久虚电路(PVC)、呼叫控制 或管理信息。 •数据链路连接标识符 DLCI 只具有本地意义