计算机网络 第五章网络层.ppt
《计算机网络 第五章网络层.ppt》由会员分享,可在线阅读,更多相关《计算机网络 第五章网络层.ppt(85页珍藏版)》请在三一文库上搜索。
1、第五章 网络层,网络层设计的有关问题 路由选择算法 拥塞控制算法 网络互联 因特网上的网络层,网络层端到端数据传输的最低层,网络层负责把源计算机发出的信息分组经过适当的路径送到目的计算机。 网络层需要了解通信子网的拓扑结构,选择合适的传输路径。 网络层要预防和控制通信子网中超量的信息分组造成的拥塞。 网络层还要处理不同网络中源端和目的端之间的差异。,5.1 网络层设计的有关问题,对网络层所提供的服务存在着两种观点: 面向连接的服务,复杂的功能放在通信子网中。 无连接服务,复杂的功能放在两端主机中。,网络层的内部结构,网络层提供的服务是否可靠与有无连接并没有关系。理论上存在四种组合,但最重要的只
2、是其中的两种组合: 可靠的面向连接服务。 不可靠的无连接服务。 针对两种服务,网络层有两种不同的工作方式: 虚电路(virtual circuit)方式。当建立连接时,从信源到信宿的路由就作为连接建立的一部分加以保存,此路由用于传输连接上的所有数据,当释放连接时,虚电路也随之撤消。 数据报(datagrams)方式。不预先选择路由,发出的每个分组所选择的路由独立于其前面发出的分组,后续的分组可以走不同的路由,比虚电路方式更健壮,更容易处理传送失败和拥塞。,虚电路与数据报的比较,5.2 路由选择算法,路由选择是网络层的主要功能,负责为分组选择合适的转发路径。 路由选择算法应具有以下几种特征:正确
3、性(correctness)、简单性(simplicity)、健壮性(robustness)、稳定性(stability)、公平性(fairness)和最优性(optimality)。 一个好的路由选择算法是兼顾某几种重要的性能指标。,路由选择算法的分类,分为两大类: 非自适应算法(non-adaptive algorithm):也叫静态路由选择(static routing),预先离线计算好路由表,在网络启动时装入到路由器中,在网络运行过程中不会根据网络流量和拓扑结构的变化而改变。简单。 自适应算法(adaptive algorithm):也叫动态路由选择(dynamic routing),
4、根据当前网络流量和拓扑结构的变化,动态在线地计算网络的路由。复杂、健壮,网络负担重。,最佳原理和接收树,当计算两点之间的最佳路由时,存在一个最佳原理(optimality principle):如果J位于I到K的最佳路由上,则J到K的最佳路由也必定落在该路由上。可通过反证求得。 根据最佳原理可以推出,所有源节点到一个给定目的节点的最佳路由的集合组成一棵以该目的节点为根的树,称为该目的节点的接收树(sink tree)。接收树并不是唯一的。所有的路由算法都是要试图找出各个目的节点的接收树,并利用这些接收树来转发数据。,最短通路路由选择算法,最短通路(shortest path)路由选择算法属于自
5、适应路由算法。它将一个通信子网抽象成一张图,图中的顶点代表网络节点(路由器),弧线代表通信线路,弧线上的权代表相邻顶点间的“距离”(可为物理上的距离,或指分组在其间的传输时间,也可指线路上的通信费用等)。任意一对顶点之间的最小权值即为它们的最短通路。 求任意一对顶点之间的最短通路可有很多方法,其中迪杰斯特拉(Dijkstra)提出了按通路长度递增的次序产生最短通路的算法,基本思想为: 首先从起始点出发,找出距起始点最近的结点,然后以此结点为基础找出距起始点次近的结点,如此每次都找出比前一次短的通路,直至某个通路到达给定的目的,这时所得到的通路就是源到目的的最短通路。 具体可采用标记方法。,利用
6、Dijkstra算法求A到D的最短通路,扩散法(flooding),扩散法为静态算法,也称洪泛式。基本思想:路由器将收到的每个分组,从除了分组到来的线路外的所有输出线路上发出。 可靠性高,但容易造成网络拥塞,改进办法有: 在每个分组头中增加一个站点计数器(hop counter):每经过一个站点,计数器减1,当计数器减为0时,就扔掉分组。计数器的值可设置为源到目的的长度或子网的直径。 记下分组扩散的路径,确保分组只转发一次。可以让源路由器对来自主机的每个分组设置一个序号,每个路由器对应于每个源路由器都有一张表,用来记录已转发过的分组(源路由器和序号)。 选择扩散法(flood selectiv
7、ely):只转发到与正确方向接近的那些线路上。 适用于负荷轻的小规模网络以及特别强调健壮性的网络。,基于流量(flow-based)的路由选择,一种既考虑拓扑结构又兼顾载荷的静态路由选择算法。 基本思想:利用已知的载荷平均流量,计算出该线路上的平均分组延迟;由所有线路的平均延迟,计算出整个网络的平均分组延迟,从而找出具有网络最小延迟的最优路由选择算法。 采用这种技术必须预知的几种信息: 网络的拓扑结构 给出通信量矩阵Fij 各线路容量的矩阵Cij 选定一种路由选择算法,从源端 i 到目的端 j 的项表示从 I 到 j的通信路由和从 i 送到 j 每秒钟的分组数量。,基于流量路由选择的示例,线上
8、的数值表示各方向的容量Ci,单位为bps。,通信量的 数学分析,计算每条线路总通信量i ,例: 1=AB=9+4+1=14。 设分组平均长度为1/(在这里假定为800位),则每条线路上分组的容量为Ci,单位为分组/s。例:C1=20kbps,则C1=20k/800=25分组/s。 由队列原理导出每条线路的平均延迟(包括排队时间和服务时间): Ti=(Ci-i)-1 如:T1=(25-14 )-1=91ms 设每条线路的权值i= i/i ,即在总通信量中使用该线路的比例。如: 1= 14/(14+12+6+11+13+8+10+8)=14/82=0.171 则整个网络的平均延迟时间为iTi,即所
9、有线路的加权延迟和。本例中为86ms。,距离矢量路由选择,距离矢量路由选择(distance vector routing)算法是现代计算机网络两个最常使用的动态路由选择算法之一。 最初用于ARPAnet;DECnet、Novell的IPX以及Internet的一种内部网关协议(IGP,Interior Gateway Protocol)都使用了称作RIP(Route Information Protocol)的距离矢量路由选择算法;Cisco则开发了一种改进的协议,叫作IGRP(Interior Gateway Routing Protocol)。 基本思想:每个路由器维护一张(矢量)表,表
10、中给出到每个目的节点已知的最佳距离和路径;每个路由器还不断测试到达相邻路由器的距离;相邻的路由器之间也不断地相互交换矢量信息;这样每个路由器将测试出的到达相邻路由器的距离加上相邻路由器给出的矢量信息,就可得知通过相邻路由器到达每个目的节点的距离,选择最佳路径更新表的信息。,距离矢量路由选择示例,无穷计算(count-to-infinity)的问题,DVR算法收敛慢,其时间复杂度为O(n3)。特别是它对好消息的反应迅速,但对坏消息却反应迟钝。 其对坏消息的反应迟钝,会造成相互交换的矢量信息错误,最终导致无穷计算的后果。 在实际使用中,可通过设置距离的最大值(如设置为网络最长路由加1)来扼制这种无
11、限的增长。,X,链路状态路由选择,链路状态路由选择(link state routing)算法1979年出现在ARPAnet上,作为一种用来取代DVR的动态路由选择算法,之后得到了广泛的应用。 基本思想:通过各个节点之间的路由信息交换,每个节点都可获得关于全网的拓扑信息,即所有的节点、各节点间的链路连接和链路的代价(时延或费用等),可将这些拓扑信息抽象成一张带权无向图,然后利用最短通路路由选择算法计算出到各个目的节点的最短通路。,链路状态路由选择算法的步骤,找出所有可达的相邻节点及它们的网络地址; 测定到这些相邻节点的代价; 将以上信息构成链路状态分组(link state packet);
12、向网上所有节点发送链路状态分组; 利用收到的链路状态分组计算到各目的节点的最短通路。,1. 了解相邻节点 每个路由器启动后,首先在所有与之相连的点-点线路上发送一个特殊的询问分组(HELLO分组),线路另一端的路由器收到后必须发回一个响应来告知它是谁(其网络地址)。 2. 测量线路代价(cost) 路由器在链路上发送一个要求对方立即响应的特殊回声(ECHO)分组,将回声分组的来回时间除以2即得到该链路的延迟时间(代价)。一般重复若干次,取平均值。,3. 构造链路状态分组 每个链路状态分组包括源节点的网络地址、分组的序号和寿命,然后是一系列相邻节点的网络地址和去往该节点的链路代价。 决定何时创建
13、链路状态分组一般有两种方法: 定期创建链路状态分组。 探测到网络连接发生变化时再创建链路状态分组。,4. 发送链路状态分组 通过改进的扩散法(记录分组扩散路径:每个路由器维护一张带有源节点和最大分组序号的表,对来自于同一个源节点的重复分组(分组序号表中序号)不转发)向网上所有其它节点发送链路状态分组。 所有的链路状态分组都要应答。当线路空闲时,从缓冲区中选择发送一个分组或应答。 为了保证高效可靠地发送链路状态分组,需采取如下一些措施: 将分组序号长度设为32位可防止序号重叠太快,若每隔1秒发送一个分组,可发137年不重复。 为每个分组规定一个寿命,分组在路由器中时,其寿命每隔1秒就减1,直到减
14、为0被抛弃。可解决路由器崩溃及分组序号传输出错等造成新旧分组不分的问题。,前图中路由器B的分组缓冲区,包含新近到达还未处理完毕的分组。,5. 计算新的路由 当一个路由器收集齐了所有的链路状态分组后,便可构造出整个网络的拓扑带权图; 通过最短通路路由选择算法就可确定到达所有其它节点的最短路径; 将此结果存入路由选择表中达到更新目的。,链路状态路由选择算法的总结,优点: 可靠性极高:因为构造网络拓扑的信息来自于各个节点亲自的探测。 最佳的路由:根据当前整网的拓扑信息计算出的。 缺点: 每个节点需要大的存储空间来存放其它所有节点发来的链路状态分组。 路由计算时间较长。 以上两点特别在网络规模很大时更
15、加突出。 链路状态路由选择算法在实际网络中运行得很好,使用非常广泛 Internet上广泛使用的OSPF(Open Shortest Path First)协议 为DECnet设计的,后被ISO采纳的IS-IS(Intermediate System to Intermediate System)协议,分级路由选择(hierarchical routing),将网络分成一些区域,每个区域内的路由器只负责本区域内的分组转发,而不管其它区域的情况,目的地址不在本区域内的分组都发给指定的区域路由器去处理。 当网络规模很大时,往往需要分成多级。 路由信息的交换只在本区域内进行,路由器内部需存储的路由信
16、息大大减少。节省了路由器的存储空间和网络带宽。 缺点是选择的路由可能不是最佳的。,分级路由示例,移动主机(mobile host)的路由选择,移动用户(mobile user)都有一个不变的永久性主方位(home location),用一个永久性的主地址(如手机号码)来确定。 用主地址作为动态用户在系统中的路由选择目标,在找到用户后,再将分组发送到用户所在的任何地方。,移动主机的定位,世界按地理位置被分成许多小单元(通常是一个LAN或无线单元),称作区域,包含有: 一个或多个外地代理(foreign agent),用来管理所有来到当地的动态用户。 一个本地代理(home agent),用来管理
17、原本属本区域,但当时正在外地的用户。 当一个移动用户进入某区域时: 移动主机和外地代理通过广播分组取得联系,移动主机向外地代理登记注册,给出其原来所在地的地址、当前数据链路层地址以及一些安全性信息。 外地代理与移动主机的本地代理取得联系,发出诸如外地代理的网络地址、安全信息等信息。 本地代理检查安全信息,验证通过后应答外地代理。 外地代理得到本地代理确认后,在其表中开设一个表项,通知移动主机已经登录注册。 当一个移动用户离开某区域时,应退出登录,移动主机的分组路由传递,广播(broadcast)路由选择,将分组同时发往所有节点称作广播(broadcasting)。有多种方法实现广播发送: 发送
18、站给每个目的站点都单独发送一个分组,浪费带宽。 采用扩散法,产生太多的分组,消耗太大的带宽。 多目的路由选择算法,每个分组携带一个欲去往的目的地址列表,每个路由器根据目的地址列表确定一组输出线路,修改目的地址列表转发分组副本。在一条输出线路上只有一个分组,节省带宽。 使用以发送站为根的生成树来转发分组。分组副本最少,占用带宽最小。但需每个路由器了解全网的拓扑结构并构造出生成树。,逆向路径转发的广播路由,逆向路径转发(reverse path forwarding)的思想:当一个广播分组到达时,路由器检查其源地址和输入线路,若输入线路是从该路由器去往源地址的最佳路径,则将该分组在除输入线路以外的
19、所有输出线路上转发出去;否则将其丢弃。 相比前四种方法,既合理有效,又易于实现。,多点播送(multicast)路由选择,向处于网络中不同位置的一组(部分)用户广播,称为多点播送或组播。 需要路由器知道哪些用户加入哪些组以及用户何时加入或离开这个组。 路由器通过计算得到覆盖整个子网的生成树,再根据组的成员修剪出各组的生成树,多点播送分组仅沿相应生成树转发。,(a) 一个子网 (b) 最左边路由器的生成树 (c) 小组1的多点播送树 (d) 小组2的多点播送树,5.3 拥塞控制,拥塞 当大量分组进入通信子网,超出了网络的处理能力时,就会引起网络局部或整体性能下降,这种现象称为拥塞。 拥塞不加控制
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机网络 第五章网络层 第五 网络
链接地址:https://www.31doc.com/p-4132992.html