第六章 广域网网络层20051.doc

第六章 广域网 网络层·提供的服务6径：数据报、虚电路等·路由选择：确定将数据从源节点传到目的节点的路径·拥塞控制：保证网络资源能够承受现有负荷6.1 广域网概述6.1.1 广域网WAN构成几十～几千公里通过点点链路将结点交换机连接成网络，站点与结点交换机相连结点交换机：分组存储转发功能·未采用LAN的多点接入技术；·局域网主要协议在数据链路层；·广域网主要协议在网络层，进行路由选择6.1.2网络层所提供的服务 ·面向连接的网络服务：虚电路服务·无连接的网络服务： 数据报服务1、数据报服务·不需建立专门通路，分组独立选择路由；·不可靠服务，分组可能丢失，到达目的机的顺序可与发送顺序不同；·目的站先将分组缓存，再按顺序交给主机；·网络中可有多个主机同时发送数据报例：主机H1和主机H5通信：A→B→E、A→C→E、A→C→B→E主机H2和主机H6通信：B→E、A→C→E、A→C→B→E2、虚电路服务·双方先建立一条虚电路，所有分组沿虚电路传送，传完释放；·物理线路未独占，可同时建多条虚电路；·服务可靠，到达顺序与发送顺序一致。

例：主机H1和主机H5通信：建立虚电路VC1，A→B→E主机H2和主机H6通信：建立虚电路VC2，B→E3、两者比较6.2 路由选择机制路由选择：确定分组在交换机中如何转发方法：在结点交换机（分组交换机）中设置一个路由表，通过查路由表确定转发路径即收到分组时，根据目的地址，查找路由表，找出应从结点的哪一个端口将该分组发送出去6.2.1 结点交换机的路由表1、广域网编址方法层次法，把一个地址分两部分： ·交换机号：主机所连接的交换机的编号 ·接入端口号：主机所连接的端口的编号每台计算机的地址在整个网络中唯一用一个二进制表示：交换机号接入端口号例：2、路由表结构： ·目的站：目的站地址； ·下一站（跳）：分组要经过的下一站（交换机）没有源站地址，是因为下一站只取决目的地址，与源站无关例：交换机2的路由表可以看出：·路由表中的项目数，与交换机、交换机所连的计算机数有关·交换机及连接的计算机数多，路由表项数多·表越大、查表越慢·下一跳根据目的站的交换机号确定目的交换机下一站112本机33路由表简化：将路由表中的目的站地址改为目的交换机号例：交换机2的路由表3、分组寻址分组在网络中传输时，根据地址第一部分（目的交换机号）来确定所转发的下一跳（交换机），直到目的交换机。

再通过地址第二部分，确定端口号，通过该端口交给目的机6.2.2 广域网的图表示广域网的路由实际是确定分组在各交换机中如何转发可采用“图”来表示整个网络的结构：·结点：结点交换机；·边：交换机间的链路例：有4个结点交换机的网络每个结点的路由表：默认路由* ：表示所有具有相同“下一站”的项目即将“下一站”相同的项合并为一项，目的站用“*”表示 优先级最低，转发分组时，当找不到对应项目时，才使用默认路由6.3 路由选择原理6.3.1 理想的路由算法·正确、简单；·自适应性：能适应网络拓扑和通信量等的变化；·稳定性、公平性、最佳等等路由选择和流量控制与网络性能关系：·吞吐量：服务的数量，好的流量控制可以加大吞吐量；·平均时延：服务的质量，好的路由选择可以降低网络的平均时延路由算法分类：·非自适应路由选择（静态路由选择）·自适应路由选择策略（动态路由选择）6.3.2 非自适应路由选择 不能及时适应网络状态变化简单、开销小1、固定路由法 ·每个结点一个路由表，标明到每一个目的地址的转发路径 ·分组传送时，根据路由表，确定要转发的下一点（后继结点） ·路由表在系统配置时生成，此后相当一段时间保持不变。

路由表产生： ·求出网络中任意两个结点之间的最短通路；·根据最短通路生成路由表，存放在各个结点Dijkstra最短通路算法：已知网络拓扑和各链路的长度（加权值），寻找从某结点（源结点）到网络中其他各结点的最短通路定义几个参数：·D(v)：源结点到结点v的距离，即从源点到点v的链路长度之和；·l(i，j)：结点i到结点j的距离；·N：网络结点集合基本思想：以某点为源结点，每次找出一个到源结点的路径最短的结点，直到把所有的结点都找到为止算法： （1）初始化 N={源结点}；对所有不在N中的结点v，写出其D(v)值： ·D(v) = l(源点，v) ，结点v与源结点直接相连 ·D(v) = ∞ ， 结点v与源结点不直接相连（2）找出一个到源结点的通路最短的结点从不在N中的结点中找出一个到源结点的距离最短的结点w，其D(w)值最小，把w加入到N中‚对不在N中的结点v，用新的值更新将结点v原值与结点v现经结点w到源结点的值比较，取小值 D(v)←min[D(v)，D(w)+l(w,v)]（3）重复步骤（2）直到所有的网络结点都在N中为止 例，求图6-9网络中结点1的路由表先求出结点1到其他结点的最短通路，由此得出路由表。

2355123211154326目的点后继点1－2234445464步骤ND(2)D(3)D(4)D(5)D(6)初始化{1}251¥¥1{1,4}2[2,1+2]4[5,1+3]2[¥,1+1]¥2{1,4,5}23[4,2+1]－‚4[¥,2+2]3{1,4,5,2}‚3－－44{1,4,5,2,3}－ƒ－－45{1,4,5,2,3,6}－－－－„目的点后继点1－223444546421211154326目的点后继点1－22*42、洪泛法（扩散法）结点收到一个分组，判断：·到本点：收下；·不是：向该结点所有输出链路转发（除输入链路）多条并行发送的路由中，肯定有一条最佳问题：分组数迅速增加，造成拥塞解决方法：·分组首部设计数器字段：每到一个点减1（加1），值为0（达规定值），丢弃；·每经过一个结点登记，第二次经过时，丢弃改进方法：选择扩散法向满足某个条件的链路上转发分组如：向目的点的方向转发3、分散通信量法每个结点设置一个路由表，有几个可选的输出链路，分别赋予一个概率结点收到一个分组时，产生一个随机数，按此查表找出相应的输出链路4、随机走动法（随机徘徊）结点随机选择一条链路作为转发的路由。

6.3.3自适应路由选择 根据网络当前状态信息决定路由1、分布式路由选择策略 结点间周期性地交换网络状态信息，并根据网络当前新状态更新路由选择整个网络的路由选择经常处于一种动态变化的状况基本算法：距离向量法、链路状态法2、集中式路由选择策略由网控中心NCC定期收集全网状态信息，计算出每个结点的路由表并分发容易得到最佳路由离NCC近的结点通信开销大、可靠性低3、孤立路由选择 结点只根据本身的状态来决定路由选择，不和其他结点交换状态信息典型：热土豆、最短队列、零偏移等热土豆：收到一个分组时，不管目的地址，以最快速度转发出去选等待队列最短的输出链路转发；或给每个队列增加一个对目的地址的偏移，两者共同转发链路4、混合路由选择 将集中式和孤立路由选择结合集中式寻找稳定状态下的最佳路由；孤立路由选择用来对局部的拥塞和故障迅速响应 6.4 拥塞控制1、拥塞 网络资源有多种、有限的如：链路容量、结点缓存容量及处理机速度等在某一段时间，网络对某一资源的需求，超过了该资源所能提供的可用部分　 　　∑对资源的需求 > 可用资源 若网络中有许多资源同时产生拥塞，网络的性能就要明显变差，整个网络的吞吐量将随输入负载的增大而下降，甚至造成死锁。

典型的拥塞：缓存容量小、处理机速率慢等2、拥塞控制保证网络资源能够承受现有负荷流量控制：收发速率匹配，发方发送数据，收方来得及接收通过流量控制在一定程度上能避免拥塞出现3、死锁拥塞使网络的吞吐量下降到零，网络无法工作·直接死锁： 互相占用了对方需要的资源而造成的死锁AB 两个结点互相等待对方释放缓存·重装死锁：发生在目的结点在目的结点把到达的分组重新装配成报文时，可能出现由于结点缓存拥塞引起例：设三个报文A、B和C经过结点P®Q®R发往主机H 分别划分四个分组：A1～A4、B1～B4、C1～C4C3C4B4A3B3B2C1B1A4A2A1H 通过合理的拥塞控制，可避免拥塞和死锁4、拥塞控制原理 可增大网络可用资源、减少用户对资源的需求等 设计一个好的拥塞控制很难，有时，正是拥塞控制本身引起拥塞及死锁开环控制：在设计网络时，事先考虑发生拥塞的有关因素；闭环控制：反馈拥塞信息·监视是否发生拥塞；·将拥塞信息传递到能采取行动的地方：源发送端，或其他路由器； ·收到反馈的系统采取相应措施进行调整6.5 X.25建议书X.25是一个公用分组交换网与网络外部DTE的接口标准主要提供虚电路服务。

一个DTE可以同时和多个DTE进行通信 分别建立多条虚电路层次结构： ·物理层：X.21建议书，数字信道；·数据链路层：平衡型链路接入规程LAPB，HDLC一个子集；·分组层：DTE与DCE之间可以建立多条逻辑信道（0～4095号）一个DTE可通过多条逻辑信道同时与其他多个DTE建立虚电路，并进行通信6.6帧中继FR是一种快速分组交换技术，可以减少结点处理的时间，在X.25基础上发展起来，第二代的X.25X.25适于低速分组交换；FR适用于高速交换原理：当帧中继交换机收到一个帧的首部时，一查出帧的目的地址就立即开始转发该帧一个帧的处理时间比X.25减少约一个数量级6.7 ATM异步传递方式ATM： p268建立在电路交换和分组交换的基础上的一种面向连接的快速分组交换技术，采用定长分组，能够较好地对宽带信息进行交换各个终端之间没有一个共同。