路由选择和拥塞控制.ppt

第六章 路由选择和拥塞控制（2）,拥塞控制（congestion),一、拥塞控制的意义,1.网络拥塞产生的原因： 当某个结点缓冲区的容量太小时，到达该结点的分组无空间暂存而不得不被丢弃； 处理机处理的速率太慢，可能引起网络的拥塞。 总之：若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏，这种情况称为（拥塞）即: 对资源的需求可用资源 资源包括网络中的链路容量，交换结点中的缓冲区和处理机 等。,拥塞分析： 问题1：某结点缓冲区小，到达该结点的分组因无空间而被丢弃 解决：将缓冲区扩大，使所有分组可以暂存 但：链路容量和CPU速度未变,分组在很长时间内排队未发 因超时分组重发 拥塞加剧 只是转移了瓶颈,问题2：发送端在未收到确认前，保留分组副本。接收端产生的拥塞导致发送端缓冲区的拥塞。 问题在于系统各部分之间的不平衡造成的,交换结点,A,A,B,B,C=1,C=1,C=1,C=10,A,B,初始：链路容量：C 平均速率： A B0.8 整个网络吞吐量：1.6,当主机A和B到交换结点的两条链路都饱和时（ A1 B10），结点缓冲区有限，导致主机A或B到交换结点的分组被丢弃。 主机B到交换结点的分组到达率是主机A到交换结点的分组到达率的10倍， 因此主机B和A，其占有输入缓冲区的机会为10:1。 最终从交换结点输出到主机B的数据率不超过1，按上述10:1关系，最终从交换结点输出到主机A的数据率不超过0.1。 整个网络吞吐量：1.1,拥塞控制和流量控制区别： 拥塞控制：全局性 流量控制：局部的，给定的发送端和接收端之间的点对点 通信量；使发送端发送的速度不要高于接收端 接收的速度 流量控制是防止网络拥塞的一种机制,轻度拥塞,拥塞, 理想的流量控制,实际流量控制,无流量控制,死锁,输入负载,0,2. 拥塞与流量控制的关系,吞吐量,拥塞控制的关键： 1）关键：合理、动态分配资源 2）应具备的功能： a) 防止网络因过载而导致吞吐率下降和时延增加； b) 防止死锁；,3.“死锁”的现象 死锁：当网络负载达到某一数值时，网络的吞吐量就下降到零，网络无法工作，这就是所谓死锁。 1）直接死锁：由互相占用对方需要的资源而造成的死锁 2）重装死锁：由于路由器的缓冲区的拥塞而引起的。,假设有三个报文A、B、C经过三个路由器P、Q、R送往主机H，每个报文由4个分组组成：, 每个路由器的缓冲能容纳4个分组； 路由器R为报文A预留了4个分组的缓冲区； 由于A3还暂留在路由P中，无法转发到Q，因为Q缓冲区已满 路由器Q也无法送往R，这样，从PQ R的链路的任何一个分组都不能转发，形成了由于缓冲区的拥塞而引起的重装死锁。,二、拥塞控制的一般原理,开环控制:在设计网络中事先将有关发生拥塞的因素考虑周到，力求工作时不产生拥塞。 缺点:一旦整个系统运行起来，就不再中途进行改正。 闭环控制:基于反馈环路原理，有几种措施： 监测网络系统以便检测到拥塞在何时、何处发生； 将拥塞发生的信息传送到可采取行动的地方； 调整网络系统的运行以解决出现的问题。,通信量控制策略：,问题： 拥塞发生的主要原因在于通信量常常是突发性的。如果主机能以一个恒定的速率发送分组，拥塞将会少得多。对于子网而言，子网强迫分组以某种预定的速率的传送。 1、漏桶算法（leaky bucket algorithm） 思路: 用户通过一个流规范（flow specification）说明自已的通信量模式，并经过协商过程来与通信子网和接收者达成一致。 通过调整分组传输的速率，从而减少可能发生的拥塞。,漏桶算法：,说明： 有一小孔的桶，不管水注入桶的速率如何，水从桶中往外漏的速率是恒定的，一旦桶空，外漏的速率为0。 在桶满之后，再注入桶中的水都会从桶边溢出。 该漏桶空实际上是一个有限的内部队列。 当队列满之后，如果有新的分组要进入队列，该分组就被丢弃。,2、令牌桶算法（token bucket）,思路： 每隔T秒生成一个令牌，且漏桶可以保留这些令牌。 如果要发送分组，必须首先抓住一个令牌，在发送分组后令牌被销毁。 有三个令牌，发送了三个分组。,三、X.25建议书,X.25建议书是CCITT在1976年制定的一个著名标准。广泛应用于：数据分组交换网.即提供虚电路服务，也提供数据报服务。1984年的版本中，取消了数据报服务 适用于：低中速线路（9600bps， 64Kbps，或TI1.44Mbps线路）。 X.25分组交换网现已成为WAN，MAN，或LAN互连常用的通信子网。 1.X.25与OSI/RM的对应点 X.25并不是严格定义下的网络层协议，是一组协议集合，包括含物理层、Data link和Network，所定义的功能被划分到下面三级中。,1,2,3,7,x.25,第三级,第二级,第一级,：分组,：帧,传输单位：比特,x.25接口,DTE：终端设备 DCE：数据电路终接设备,物理层,定义了DTE和 DCE之间的电气接口 定义了建立物理的信息传输通路的过程 可以看成一条输送信息的管道，不执行控制功能 控制功能主要由链路层和分组层来完成 接口规程 X.21、X.21bis（与V.24 或RS-232接口标准兼容） V系列建议（RS-232-C、V.35）,数据链路层,对实施信息传输的控制 规定了在DTE和DCE之间的线路上交换分组的过程 链路层的主要功能如下： 在 DTE和DCE之间有效地传输数据 确保接收器和发送器之间信息的同步 检测和纠正传输中产生的差错 识别并向高层协议报告规程性错误 向分组层通知链路层的状态,链路层帧结构,采用了HDLC的帧(Frame)结构 HDLC是ISO开发的一种面向比特的同步通信规程 LAP(链路访问规程） LAPB(平衡型链路访问规程） LAPD(ISDN的D信道链路访问规程）,分组层功能,在X.25接口为每个用户呼叫提供一个逻辑信道 通过逻辑信道号(LCN)来区分同每个用户呼叫有关的分组。 为每个用户的呼叫连接提供有效的分组传输，包括顺序编号，分组的确认和流量控制 提供交换虚电路(SVC)和永久虚电路(PVC)的连接 提供建立和清除交换虚电路连接的方法 检测和恢复分组层的差错,x.25分组层：规定由本地DTE发给PDN（公共数据网）的分组格式，共17种，6大类。 1）呼叫建立分组：用于建立DTE间虚电路 2）数据和中断分组：传输信息 3）流控制和复位分组：为虚电路提供控制机制 4）重启动分组：出错后重新初始化DTE-DCE接口 5）诊断分组：显示出错情况 6）登记分组：请求或获得用户特定参数,一个x.25分组基本格式,分组头,数据域,x.25分组分类,数据 控制,作用：虚电路的建立，数据传送时流量控制、中断、数据传送完毕后的虚电路释放。,GFI：定义通用功能，如顺序编号是按模8/模128工作等。 LCGN和LCN：逻辑信道标识符。共12bit，可提供4096条逻辑子通道。,分组头, ,GFI,LCGN,LCN,TYPE,呼叫请求/入呼叫分组,0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1,主叫地址长度,被叫地址长度,被叫地址,主叫地址,可选业务功能长度,可选业务功能数据,数据,DTE1,DTE2,本地DCE,远程DCE,X.25,X.25,网络规程,呼叫请求LCN/200,入呼叫LCN/10,建立,呼叫接受LCN/10,呼叫接通LCN/200,当数据传送完后，主叫和被叫中任意一方都可以发起拆除虚电路请求。,二、x.25的虚电路服务过程：,DTC1,DCE,DCE,DCE,DTC2,DTC3,VC1,VC2,1.DTC1可以同时与DTC2、DTC3建立二条虚电路VC1，VC2，VC(Virtual Call) 虚电路： 很像电话通信，先拨号建立电路，然后再通话，完毕后挂机，仍采用的分组一转发的方法，断续地占用一段一段的物理电路。（电路自始至终占用一条电路） 2.过程： 第一阶段：呼叫建立 第二阶段：数据传送 第三阶段；呼叫断开,分组层,数链层,物理层,分组层,数链层,物理层,x.21接口,LAPB接口 （HDLC),分组,可建立多个逻辑信道（04095个）,x.21是基于数字信道，但目前大多数用户是 电话线（模拟）物理层：还是RS-232标准。,三、x.25接口的层次关系（虚电路）,x.25相关协议：,使用x.25规程与分组交换网接口的DTE必须有相应的硬件和软件支持x.25规程，具有这种能力的终端称为x.25终端或分组终端 对于非x.25终端，不能直接与x.25网络相连，必须有PAD(packet assembly disassembly)(