计算机网络课件：ch5 网络层1

1、1,第五章 网络层,两节点间可靠的数据传输,Ethernet, X.25, ATM, ,1. 传输0/1,2.,回顾,3,两端点间可靠的透明数据传输 （应用进程间的逻辑通信）,通信子网,沿两主机间的最佳路由传输数据 （主机间的逻辑通信）,Ethernet, X.25, ATM, ,4.,3.,回顾,4,OSI/RM,OSI/RM的体系结构分为7层,应用层Application,表示层Presentation,会话层Session,传输层Transport,物理层Physical,数据链路层Data Link,网络层Network,7 6 5 4 3 2 1,为网络应用提供服务 数据表示 在用户

2、间建立会话关系 不同主机进程间的通信 在主机间传输分组 在节点间可靠地传输帧 位流的透明传输,5,主要内容,网络层设计要点 路由算法 拥塞控制算法 服务质量 网络互连 Internet上的网络层,6,5.1 网络层设计要点,存储-转发分组交换 向传输层提供的服务 无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较,7,5.1.1 存储-转发分组交换,一台主机要发送一个分组，它会将分组发送给最近路由器 该分组将被存储在路由器上，路由器根据分组的头部信息和路由表，选择路由 根据所选路由，将该分组转发到下一跳路由器，直到到达目的主机为止 在目的主机上它被交给相应的进程,网络层协议运行

3、环境,8,5.1.2 向传输层提供的服务,设计网络层服务时需要考虑问题 所提供的服务应该独立于路由器技术 路由器的数量、类型和拓扑结构对传输层不可见 网络地址应该有统一的编制方案，甚至可跨越多个LAN和WAN,9,提供服务的类型 无连接服务 Internet社团的观点：通信子网不可靠的，主机应该接受“网络是不可靠的”这样的事实，且自己来完成错误控制和流控。网络层只需提供无连接服务,而将复杂的功能放在传输层 例：Internet提供了无连接的网络层服务 面向连接服务 电话公司的观点：通信子网应该提供可靠的、面向连接的服务。服务质量是最主要的因素 例：ATM网络提供了面向连接的网络层服务,5.1.

4、2 向传输层提供的服务,10,5.1.3 无连接服务的实现,网络层内部的工作方式 数据报 提供无连接的服务，每个分组携带完整的目的地址，独立进行路由选择 虚电路 提供面向连接的服务，在发送数据分组之前，必须先建立起一条从源路由器到目的路由器之间的路径，这个连接称为虚电路（VC） 通信结束后，释放虚电路,11,无连接服务的实现,数据报子网的工作过程,数据报子网内的路由,发送3个分组后， ACE线路拥塞， A路由表更新,12,5.1.4 面向连接服务的实现,虚电路的工作过程 建立虚电路，每个随后的分组都包含一个标示符，指明该分组属于哪个虚电路 使用该虚电路进行通信 通信结束后，终止虚电路,连接 标

5、识符,2,2,13,5.1.5 虚电路子网和数据报子网的比较,14,虚电路子网和数据报子网的比较,路由器内存空间与带宽的权衡 虚电路方式，分组只要包含电路号，不用包含完整的目的地址，但路由器需要维护虚电路的状态信息 数据报方式，每个数据报都携带完整的目的/源地址，但路由器不需要维护虚电路的状态信息 连接建立时间与地址查找时间的权衡 虚电路需要在建立连接时，花费时间 数据报则在每次路由时，查找过程复杂,15,虚电路子网和数据报子网的比较,服务质量QoS（Quality of Service） 虚电路方式很容易保证QoS，可以提前预留资源，适用于实时操作，但比较脆弱 数据报不太容易保证QoS，但是

6、对于通信线路的故障，适应性很强,16,5.2 路由算法,路由器内部有两个进程 根据路由表查找进来的分组所对应的输出线路，这个进程即为转发 负责填充和更新路由表，这是路由算法起作用的地方,17,路由算法,路由算法应具有的特性 正确性（correctness） 简单性（simplicity） 健壮性（robustness） 稳定性（stability） 公平性（fairness） 最优性（optimality）,18,路由算法,路由算法分类 非自适应算法（静态路由算法） 不能根据流量和拓扑结构的变化更新路由表，使用静态路由表 特点 简单，开销少 但灵活性差,19,路由算法,自适应算法（动态路由算法

7、） 可根据网络流量和拓扑结构的变化更新路由表 不同动态路由算法在多个方面有所不同 获取信息的来源不同：来自本地、来自相邻、来自所有的路由器 改变路径的时间不同：每隔t秒，当负载变化的时候、当拓扑结构改变的时候 用于优化的度量不同：距离、跳数、传输时间等 特点 健壮性和灵活性好 但开销大,20,5.2.1 最优化原则,最优化原则（optimality principle） 如果路由器J在从路由器I到K的最优路径上，那么从J到K的最优路径必定沿着同样的路由路径,路由器I,路由器J,路由器K,21,5.2.1 最优化原则,汇集树（sink tree） 从所有的源节点到一个给定的目的节点的最优路径的集

8、合构成了一个以目的节点为根的树，称为汇集树 路由算法的目的 为所有路由器找出并使用汇集树,（a）一个子网； （b）路由器B的汇集树,22,5.2.2 最短路径路由,基本思想 构建子网的拓扑图，图中的每个节点代表一个路由器，每条弧代表一条通信线路 为了选择两个路由器间的路由，路由算法在图中找出最短路径 测量路径长度的方法 节点数量 物理长度 传输延迟 距离、带宽、平均流量、通信开销、平均队列长度、测量延迟和其他因素的一个函数,23,最短路径路由,Dijkstra算法 每个节点用从源节点沿已知最佳路径到该节点的距离来标注，标注分为临时性标注和永久性标注 初始时，所有节点都为临时性标注，标注为无穷大

9、 将源节点标注为0，且为永久性标注，并令其为工作节点 检查与工作节点相邻的临时性节点，若该节点到工作节点的距离与工作节点的标注之和小于该节点的标注，则用新计算得到的和重新标注该节点 在整个图中查找具有最小值的临时性标注节点，将其变为永久性节点，并成为下一轮检查的工作节点 重复第四、五步，直到目的节点成为工作节点,24,计算从A到D的最短距离的前5步，图中的箭头表明的是工作节点,最短路径路由,25,5.2.3 扩散法(Flooding),扩散法属于静态算法 基本思想 每个进来的分组将被发送到除了它进来的那条线路外的其它输出线路上 主要问题 扩散要产生大量重复包,26,扩散法,两种解决措施 每个分

10、组的头中包含一个跳计数器，每经过一跳后该计数器减1，为0时则丢弃该分组 记录哪些分组已经被扩散了，从而避免再次发送这些分组。方法： 源路由器在它接收到的来自其主机的每个分组中放上一个序号，在每个路由器上，针对每个源路由器需要一个列表，记录那些已经见到过的、来自该源路由器的序列号。如果一个进来的分组已经位于该表中，就不再扩散了,27,扩散法,扩散法的一种改进-选择性扩散（selective flooding） 将进来的每个分组仅发送到与正确方向接近的线路上 扩散法应用情况 扩散法的高度健壮性，可用于军事应用 分布式数据库应用中，可用于同时更新所有的数据库 可用于无线网络中 扩散法作为衡量标准，用

11、来比较其它的路由算法,28,5.2.4 距离矢量路由,属于动态路由算法，也称Bellman-Ford路由算法和Ford-Fulkerson算法 最初是ARPANET使用的路由算法，也被用于Internet的RIP协议 基本思想 每个路由器维护一张表，表中给出了当前已知的到每个目的地的最佳距离，以及所使用的线路， 通过与相邻路由器交换距离信息来更新表,29,距离矢量路由,原理 每个路由器维护一张路由表(见右图) 路由表以子网中每个路由器为索引，且每个路由器对应一个表项 表项包括两部分：到达该目的路由器的时间估计或距离估计，和到达目的路由器的首选使用的输出线路 每隔一段时间，路由器向所有邻居路由器

12、发送它到每个目的节点的路由表， 同时它也接收每个邻居路由器发来的路由表,New estimated delay from J,30,距离矢量路由,一个路由器接收到来自相邻路由器X发来的表，其中Xi为路由器X到路由器i的距离， 若该路由器到X的距离为m， 则该路由器经过X到i的距离为Xi+m。 根据不同邻居发来的信息，计算Xi+m， 并取最小值，更新本路由器的路由表,31,距离矢量路由,（a）一个子网； （b）J从A、I、H、K收到的表，以及J的新路由表,注意：J路由器中的老路由表在计算中不被使用,A到B的延迟(AB),I到B的延迟(IB),被使用?,J到B的最小延迟 = MinJA+AB,JI

13、+IB,JH+HB,JK+KB =8+12,10+36,12+31,6+28=20,32,无穷计算问题 算法的缺陷：对好消息反应迅速，对坏消息反应迟钝 问题的核心：当X告诉Y它有一条路径的时候，Y无从知道他自己是否在这条路径上,距离矢量路由,（a）A启动时,第一次交换时，B没有收到来自A的消息， C说：我有一条通向A的长度为2的路径， B认为通过C可到达A，且路径长度为3。 第一次交换后，D和E不更新它们的A表项,第一次交换时，B知道它左边的邻居到A的延迟为0，B建立一表项，说明A在它左边的一跳上，其他路由器仍认为A是停机的,（b）A停机时,无穷计算问题,x,33,5.2.5 链路状态路由算法

14、,距离向量路由算法的主要问题 选择路由时，没有考虑线路带宽（不同线路的带宽不同） 路由收敛速度慢（无穷计算问题）,34,链路状态路由算法,链路状态路由算法 发现邻居节点，并知道其网络地址 路由器启动后，通过发送HELLO分组发现邻居节点 测量到每个邻居节点的延迟或开销 一种直接的方法是：发送一个的ECHO分组，另一端立即送回一个应答，往返时间除以2即为延迟 有时需要考虑负载,35,链路状态路由算法,创建链路状态分组 分组构成 发送方的标识符 序号 年龄 邻居列表。表项包括路由器的邻居，和到这个邻居的延迟 何时创建链路状态分组 定期创建或发生重大事件时创建,（a）一个子网； （b）该子网的链路状

15、态分组,36,链路状态路由算法,将这个分组发送给所有其它路由器 基本思想 使用扩散法发布链路状态分组 为控制扩散，每个分组头一个序号，每次发送新分组时加1 每个路由器记录下它所看到的所有（源路由器，序号）对 当一个链路状态分组到达时，路由器检查这个分组 若是新的，则除了它到来的那条线路外，在其他线路上全部转发该分组 若是重复的，则丢弃 若是过时的，则丢弃 若序号比当前所看到过的来自该路由器的最大序号小，则认为过时,37,链路状态路由算法,改进 序号回转可能产生混淆。解决办法：使用32位序号 路由器崩溃后，如果它再从0开始，则下一个分组被作为重复分组而丢弃。解决办法：分组中增加年龄（age）域，

16、每秒钟年龄减1，为零则丢弃 序号被破坏。解决办法：分组中增加年龄域 链路状态分组到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态分组比较序号，丢弃重复包，保留新分组； 所有的链路状态分组需要应答，见图5.14,38,链路状态路由算法,发送标志为1：需要向此方向转发， 确认标志为1：必须在此方向上被确认 来自A的链路状态分组可以直接到达，B必须将它发给C、F，向A送回确认 从E发来的链路状态包有两个，一个经过EAB，另一个经过EFB 从D发来的链路状态包有两个，一个经过DCB，另一个经过DFB,图5.14 路由器B的分组缓冲区,1：B须将它发给C,1：B须向A送回确认,39,链路状

17、态路由算法,将这个分组发送给所有其它路由器 分组构成 发送方的标识符 序号 年龄 邻居列表。表项包括路由器的邻居，和到这个邻居的延迟,（a）一个子网； （b）该子网的链路状态分组,40,计算从A到D的最短距离的前5步，图中的箭头表明的是工作节点,最短路径路由（复习）,41,链路状态路由算法,发现邻居节点，并知道其网络地址 测量到每个邻居节点的延迟或开销 创建链路状态分组 将这个分组发送给所有其它路由器 计算到每个其它路由器的最短路径 根据Dijkstra算法计算最短路径 实用协议 OSPF（开放最短路径优先） IS-IS（中间系统对中间系统）,42,5.3 拥塞控制算法,拥塞（congesti

18、on） 网络中出现太多的分组时，网络的性能开始下降，这种情况称为拥塞,当流量太大时，拥塞就会发生，性能急剧降低,43,拥塞控制算法,拥塞产生的原因 慢速处理器，难以完成必要的维护工作 低带宽线路 多个输入对应一个输出 解决办法 针对某个因素的解决方案，通常不会有明显的效果，甚至仅仅是转移了瓶颈 需要全面考虑各个因素,44,拥塞控制算法,拥塞控制与流量控制的差别 举例 在一个传输容量为1000Gbps的光纤网络上，一台超级计算机试图以1Gbps的速率给一台PC传送一个文件。 这里没有拥塞，但需要流量控制 一个1Mbps的存储-转发网络中，有1000台大型的计算机，其中的一半正试图给另一半机器以1

19、00kbps速率传送文件。 这里需要拥塞控制,45,拥塞控制算法,拥塞控制与流量控制的差别 流量控制（flow control） 只与特定的发送方和特定的接收方间的点到点流量有关 主要解决快速发送方与慢速接收方的问题，是局部问题，一般都是基于反馈进行控制的 拥塞控制（congestion control） 确保子网能够承载所到达的流量 是一个全局性问题，涉及各方面的行为，包括 所有的主机 所有的路由器内部的存储-转发处理过程 所有可能会消弱子网承载容量的其它因素,46,5.3.1 拥塞控制的通用原则,根据控制论，拥塞控制方法分为两类 开环控制 通过良好的设计来解决问题，避免拥塞发生 手段 确定

20、何时接收新的流量 确定何时丢弃分组及丢弃哪些分组 在网上的不同点执行调度决策 注：这些手段在做出决定时不考虑网络当前状态,47,拥塞控制的通用原则,闭环控制 基于反馈机制 工作过程 监控系统，发现何时何地发生拥塞 把发生拥塞的消息传给能采取动作的站点 调整系统的运行，以改正问题,48,拥塞控制的通用原则,衡量网络是否拥塞的参数 缺乏缓冲区空间而丢弃的分组所占的百分比 平均队列长度 超时重传的分组的数量 平均分组延迟 分组延迟的标准方差,49,拥塞控制的通用原则,反馈方法 向负载发生源发送一个告警分组 分组结构中保留一个位或一个域，用来表示发生拥塞，一旦发生拥塞，路由器在所有的输出分组中填充该位

21、或该域，以警告邻居 主机或路由器主动地、周期性地发送探询分组，显式地询问有关拥塞情况,50,拥塞控制的通用原则,拥塞的解决方案 增加资源 增加带宽（启动备用电路） 启动空闲的备用路由器等 分散流量 降低负载 拒绝为某用户提供服务 给某些用户或全部用户降低服务等级等,51,5.3.2 拥塞预防策略,开环控制 可能影响到拥塞的数据链路层、网络层、传输层策略,52,虚电路子网的动态拥塞控制方法 准入控制（admission control） 基本思想 一旦发生拥塞，在问题解决之前，不允许建立新的虚电路 允许建立新的虚电路，但要绕开发生拥塞的区域 资源预留 建立虚电路时，主机与子网达成协议，子网根据协

22、议在虚电路上为该连接预留资源,5.3.3 虚电路子网中的拥塞控制,53,5.3.4 数据报子网中的拥塞控制,路由器监控输出线路及其它资源的使用情况，超过某个阈值，则此资源进入警戒状态，就需要采取措施 警告位 每个新分组到来，检查它的输出线路是否处于警戒状态 若是，路由器在分组的头中设置一个特殊的位来指示警告状态， 当分组到达目标端时，传输层实体发送确认分组，告知源主机，源主机就可以消减流量,54,数据报子网中的拥塞控制,抑制分组（Choke Packets） 路由器监控输出线路及其它资源的利用情况，超过某个阈值，则此资源进入警戒状态 每个新分组到来，检查它的输出线路是否处于警戒状态 若是，则向

23、源主机发送抑制分组，分组中指出发生拥塞的目的地址。同时将原分组打上标记（为了以后不再产生抑制包），正常转发,55,数据报子网中的拥塞控制,源主机收到抑制分组后，按一定比例减少发向特定目的地的流量，并在固定时间间隔内忽略指示同一目的地的抑制包。然后开始监听 若此线路仍然拥塞，则主机在固定时间内减轻负载、忽略抑制分组；若在监听周期内没有收到抑制分组，则增加负载 通常采用的流量增减策略 减少时，按一定比例减少，保证快速解除拥塞 增加时，以常量增加，防止很快导致拥塞,56,（a）一个只影响源主机的抑制分组,拥塞,57,（a）一个只影响源主机的抑制分组,（b）一个影响沿途每一跳的抑制分组,拥塞,拥塞,5

24、8,数据报子网中的拥塞控制,逐跳的抑制分组（Hop-by-Hop Choke Packets） 在高速或长距离的网络中，源主机响应太慢， 抑制分组算法对拥塞控制的效果并不好，可采用逐跳抑制分组算法； 基本思想 抑制分组对它经过的每个路由器都起作用 能够迅速缓解发生拥塞处的拥塞， 但要求上游路由器有更多的缓冲区,59,5.3.5 负载丢弃,当任何一种方法都不能消除拥塞的时候，路由器可以丢掉来不及处理的分组 针对不同服务，可采取不同丢弃策略 文件传输，优先丢弃新分组，wine策略 多媒体服务，优先丢弃旧分组，milk策略 智能丢弃策略：分组中标明优先级 允许用户超越在建立虚电路时协商的限制值，但要

25、服从所有超出部分的流量必须被标记为低优先级 早期丢弃包，在缓冲区未用完之前开始丢弃分组，会减少拥塞发生的概率，提高网络性能,?,?,60,5.3.6 抖动控制,抖动(Jitter) 分组到达的时间变化量（即标准偏差） 有些应用需要很低的抖动 例：音频流和视频流,61,5.4 服务质量（QoS）,需求 获得好的服务质量所使用的技术 综合服务 区分服务 标签交换和MPLS,62,5.4.1 需求,流 从一个源到一个目标的分组流 流的需求特征 可靠性 延迟 抖动 带宽 这4个特征合起来决定一个流所要求的服务质量（QoS）,63,需求,服务质量需求的严格程度,64,5.4.2 获得好的QoS所使用的技

26、术,过度提供资源 提供足够的路由器容量、缓冲区空间和带宽 缓冲能力 在接收方，数据流在被递交之前可以先缓存起来 会增加延迟、但可以消除抖动,通过缓存分组的方法来平滑输出流,65,获得好的QoS所使用的技术,流量整形 在服务器端而不是客户端对流量进行平滑处理，调节数据传输的平均速率 流量整形技术可以减少拥塞，也有助于运营商兑现它的承诺 流量监管 对一个业务流进行监视,66,获得好的QoS所使用的技术,漏桶算法（The Leaky Bucket Algorithm） 算法思想 主机每过一个时钟滴答才允许把一个分组放到网络上 如果在一台主机上，队列中的分组数目达到了最大值，这时又有一个或多个进程要发

27、送分组，则该分组被丢弃 将用户发出的不平滑的数据分组流转变成网络中平滑的数据包流,（a）一个盛水的漏桶； （b）一个装分组的漏桶,67,漏桶算法举例,一台计算机能以25MB/s的速率生成数据，且网络也能以该速率运行。但路由器仅能在很短的时间内以该速率工作，其他时间的最佳工作速率不超过2MB/s。现设数据以突发式输入，每次1MB（时间为40ms）的突发数据。 为了将平均速率降到2MB/s，用一个恒定速率=2MB/s，容积为1MB的漏桶。这意味着每次输入高达1MB的数据也不会丢失，而且这些突发数据在500ms（=1/2s）内被传出去，而不管它们进来时多快,（a）进入到漏桶的输入数据； （b）漏桶的

28、输出,68,获得好的QoS所使用的技术,漏桶算法适用于 可用于固定分组长的协议，如ATM 可用于可变分组长的协议，如IP，但要使用字节计数 漏桶算法缺点 无论负载突发性如何，漏桶算法强迫输出按平均速率进行，不灵活,69,获得好的QoS所使用的技术,令牌桶算法（Token Bucket Algorithm） 当大的通信量到来时，输出也能加速,最大到桶的大小n 基本思想 漏桶存放令牌，每T秒产生一个令牌，令牌累积到超过漏桶上界n时就不再增加 分组传输之前必须获得一个令牌，传输之后删除该令牌 在桶满时，会丢失令牌，但绝不丢弃分组,令牌桶算法 （a）桶内有3个令牌，同时有5个待传分组 ； （b）3分组

29、传送出去后,70,令牌桶算法,基本令牌桶算法 用一个令牌可以发送一个分组 有一个令牌计数器 加：每t，加1 当令牌桶满时，不再加 减：每发送一个分组，减1 计数器为0时，不能发送数据,71,令牌桶算法,字节计数方式 用一个令牌可以发送k个字节 令牌计数器 加：每t， 加k(字节) 令牌桶满时不再加 减：每发送一个分组，减其字节长度 为0时不再发送数据 假设有足够的数据 若令牌桶内有令牌数，则以最大输出速率输出数据 若令牌桶内无令牌，则以令牌到达速率输出数据,72,令牌桶算法最大速率突发时间长度S,令牌桶的容量 + S秒的令牌到达的量 = S秒的最大速率突发过程中输出的字节数量, 即 C+S=M

30、S 最大速率突发时间长度 S=C/(M-)秒,?,73,令牌桶算法举例,有一个容量为250kB的令牌桶,令牌到达的速率为2MB/s。设当1MB突发数据到达时,令牌桶已满,则其以25MB/s的全速向网络输出数据,求允许其用全速向网络传输的时间是多少？之后还需要多长的时间传输完？ 允许其用全速向网络传输的时间为 S=C/(M-)=250kB/(25MB/s- 2MB/s) 11 ms 传送完还需要的时间 （1MB-25MB/s*11ms）/（2MB/s） 364ms 即1MB数据经过11ms全速传输之后,仍以2MB/s的速率向网络输出,再用364ms传送完,(a)进入到漏桶的输入数据；(b)漏桶的

31、输出； (c)-(e)当容量分别为250KB、500KB和750KB时漏桶的输出 (f)一个500KB的令牌桶接一个10Mbps漏桶的输出,75,令牌桶算法,令牌桶又造成大量的突发数据，最大突发间隔可以通过选择和M进行控制 使通信量更平滑的一个办法 在令牌桶之后再加一个漏桶； 漏桶的速率应该比令牌桶的大，但比网络的最高速率小 如上图（f）中，一个500KB的令牌桶后连一个10MB/s的漏桶,76,5.5 网络互联,互联网（internet） 将两个或多个网络连接起来构成互联网 多种不同网络长期存在的原因 历史原因 有些网络已经有了非常大的安装基数 技术原因 不同网络采用不同技术、不同硬件、不同

32、协议 价格原因 计算机和网络变得越来越便宜，更多的人有权决定使用何种网络,77,网络互联,一组相互连接的网络,78,5.5.1 网络的不同之处,网络层上可能出现一些差异,79,网络的不同之处,当一个分组在到达目的网络前必须经过一个或多个外部网络时，在网络接口处会出现很多问题。例 面向连接的网络经过无连接的网络时，这些分组可能要被重新排序，这是发送方不期望的，而接收方也不准备处理顺序问题 如何通过一个最大分组为1500字节的网络传递一个8000子节的分组 对于不同的网络，差错控制、流控制和拥塞控制通常也是不一样,80,5.5.2 网络如何连接起来,物理层 中继器和集线器 只是简单将数据为从一个网

33、络搬移到另一个网络。它们只不过重新生成模拟信号，并不理解有关数字协议方面的内容 数据链路层 网桥和交换机 可以接收帧，检查MAC地址，并且将帧转发到另一个不同的网络中,81,网络如何连接起来,网络层 路由器（router） 在网络之间存储-转发分组，能够转换分组格式 能够处理多种协议的路由器称为多协议路由器 传输层 传输网关（transport gateway） 两个传输层连接之间的接口 应用层 应用网关（application gateway） 可以翻译消息的语义,82,网络如何连接起来,交换机和 路由器的区别,（a）通过交换机连接起来的两个以太网,交换机整个帧是以MAC地址为基础进行传输的

34、；不必理解分组中所使用的网络层协议 路由器从帧中提取出分组，然后利用分组中的网络地址来决定他的目标去向，必须理解分组中所使用的网络层协议,（b）通过路由器连接起来的两个以太网,83,5.5.3 级联虚电路,级联虚电路工作过程与虚电路子网工作过程相似 级联虚电路工作过程 建立连接 当目的主机不在子网内时，则在子网内找一个离目的网络最近的路由器，与之建立一条虚电路 该路由器与外部网关建立虚电路 该网关与下一个子网中的一个路由器建立虚电路 重复上述操作，直到到达目的主机,84,级联虚电路,传输数据 相同连接的包沿同一虚电路按序号传输 网关根据需要转换包格式和虚电路号 拆除连接 问题 当中间网络不保证

35、可靠递交的话，虚电路也是不可靠的,85,级联虚电路,使用级联虚电路实现网络互联,86,5.5.4 无连接网络互连,工作过程 无连接网络互连的工作过程与数据报子网的工作过程相似 每个分组单独路由，提高网络利用率，但不能保证分组按顺序到达 根据需要，连接不同子网的多协议路由器做协议转换，包括分组格式转换和地址转换等,87,无连接网络互连,一个无连接的网络互联,88,无连接网络互连,问题 分组格式转换 编址问题 解决方法 设计全局通用的“互联网”，即IP网络,89,无连接网络互连,级联虚电路与无连接网络互连的比较 级联虚电路的优点 路由器预留缓冲区等资源，保证服务质量 分组按序号传输 短分组头等 级

36、联虚电路的缺点 路由器需要大量内存，存储虚电路信息 一旦发生拥塞，没有其它路由 健壮性差 如果网络中有一个不可靠的数据报子网，很难实现级连虚电路,90,无连接网络互连,无连接网络互连的优点 能够容忍拥塞，并能适应拥塞 健壮性好 可用于多种网络互连 无连接网络互连的缺点 长分组头 分组不能保证按序号到达 难以保证服务质量,91,5.5.5 隧道技术,隧道技术 源和目的主机所在网络类型相同，连接它们的是一个不同类型的网络，可以采用隧道技术相连,92,隧道技术,工作过程 主机1发送一个包，目的IP地址为主机2的IP，将包封装到局域网帧中，帧目的地址=路由器1的MAC 局域网传输 路由器1剥掉局域网帧

37、头、帧尾，将得到的IP包封装到广域网分组的净荷域中，分组目的地址=路由器的地址（网络层） 广域网传输（网络层） 路由器2剥掉广域网分组头，将得到的IP分组封装到局域网帧中，帧目的地址=主机2的MAC地址 局域网传输 主机2接收,93,5.5.6 互联网路由,互联网络的路由与单独子网的路由过程相似，只是复杂性增加,(a)一个互联网；(b)互联网的图表示,94,互联网路由,自治系统AS（Autonomous System） 一个互联网内部的每个网络都独立于所有其他的网络，每个网络称为一个AS 两级路由算法 内部网关协议（IGP: Interior Gateway Protocol） AS内部使用的

38、协议。如：RIP，OSPF 外部网关协议（EGP: Exterior Gateway Protocol） AS间使用的协议。如：BGP,95,互联网路由,内部路由和外部路由的区别 法律不同 收费不同 服务质量,96,每种网络都对最大分组长有限制的原因 硬件，如以太网帧的长度限制 操作系统，如所有的缓冲区都是512字节 协议，例如分组长度域的比特个数 遵从某一个国家（或国际）标准 期望将“因错误而引入的重传次数”减少到某种程度 希望避免一个分组占用信道时间过长 大分组经过小分组网络时，网关要将大分组分成若干段（fragment），每段作为独立的分组传输,5.5.7 分段（Fragmentatio

39、n）,97,把划分为段的分组重组为原来的分组的方法有两种策略 分段重组过程对沿途后续的其它网络透明 网关将大分组分段后，每段都要经过同一出口网关，并在那里重组，例：ATM网络 带来的问题 出口网关需要知道何时所有分组都到齐 所有分组必须从同一出口网关离开 大分组经过一系列小分组网络时，需要反复地分段重组，开销大,段重组策略,98,段重组策略,分段重组过程对其它网络不透明 中间网关不做重组，而由目的主机做 带来的问题 对主机要求高，能够重组 每个段都要有一个分组头，网络开销增大 对分组作划分时，分段必须按照能够重构原始数据流的方式编号,99,分段编号,编号方法 树型标记法 例，分组0分成三段，分

40、别标记为0.0, 0.1, 0.2，这些段又被分成三段，分别标记为0.0.0, 0.0.1, 0.0.2, 0.1.0, 0.1.1, 0.1.2, ； 存在的问题 段标记域要足够长 分段长度前后要一致,100,分段编号,偏移量法（较好的） 定义一个基本段长度，使得基本段能够通过所有网络 分组分段时，除最后一个段小于等于基本段长度外，所有段长度都等于基本段长度 一个分组可以含有若干个基本分段 分组头中包括：原始分组号、分段号、最后段指示位，其中 分段号：指当前分段在原始分组中的偏移量 最后段指示位：指示是否是最后一个分段,101,举例,图5.51 当基本数据长度为1个字节时的分段情况 (a)原

41、始分组，包含10个数据字节； (b)当通过一个最大分组长度为8个净荷字节+头部的网络后的分段； (c)当通过一个最大分组长度为5的网关后的分段,102,5.6 Internet上的网络层协议,Internet是一组相互连接的子网络或者自治系统的集合 Internet 有一些大的骨干网络，骨干网络是由高带宽的线路和快速路由器构成 连接在骨干网络上的是区域网络 连接在区域网络上是许多大学、公司、ISP服务商,Internet是由许多网络相互连接之后构成的集合,103,Internet上的网络层协议,将整个Internet粘合在一起的是IP（Internet Protocol） IP协议设计之初就考

42、虑了网络互联的需求 IP的任务 提供一种尽力投递的（best-efforts,即不提供任何保证）方法将数据报从源端传输到目标端， 它不关心源机器和目标机器是否在同样的网络中，也不关心它们之间是否还有其他网络,104,5.6.1 IP协议,IPv4头部,105,版本域与头部长度,版本号（version） 4bits，IPv4协议填4，IPv6协议填6 头部长度（IHL） 4bits，单位为4字节，取值范围5-15（确省值为5，即标准头标长20字节），指示IP包头的长度,106,服务类型（TOS）域,可靠性：0-一般可靠；1-高可靠,吞吐量：0-一般；1-高吞吐,延时：0-一般；1-低延时,000

43、 Routine 001 Priority 010 Immediate 011 Flash 100 Flash override 101 Critical 110 Internetwork control 111 Network control,107,总长度域、标识域,总长度域 16bits ，单位字节，描述IP包的总长（包括头和数据），最大包长度为65535字节 标识域 16bits，用于唯一标识该包,108,标志域、分段偏移域,标志域 3bits。第1位未定义 第2位DF代表“不分段”，DF为0表示该包可分段，否则表示不可分段 第3位MF代表“更多的分段”，MF为0表示这是最后分段，否则

44、表示还有后续分段 分段偏移域 13bits，单位8字节。取值0-8191，标明当前报片在原包中的位置,109,生存时间域、协议域,生存时间（TTL）域 8bits，单位秒，表示包的生存时间。实际操作时，包每经过一个路由器，TTL值减一，当TTL值为0时，该包被丢弃 协议（Protocol）域 表示高层协议类型。协议的编号详见 0 Reserved 1 Internet Control Message Protocol (ICMP) 2 Internet Group Management Protocol (IGMP) 3 Gateway-to-Gateway

45、 Protocol (GGP) 4 IP (IP encapsulation) 5 Stream 6 Transmission Control (TCP) 8 Exterior Gateway Protocol (EGP) 9 Private Interior Routing Protocol 17 User Datagram (UDP),110,头部校验和域、源/目的地址域,头部校验和域 16bits，用来检验包头 源地址域 32bits，包的发送者的IP地址 目的地址域 32bits，包的接收者的IP地址 填充（padding） 包头长度必须为4字节的整数倍，如果选项的长度不是4字节的整数

46、倍，那么就要进行填充,111,选项（option）,安全性选项 指明包的机密性 严格的源路由选项 给出包经过的完整路由 宽松的源路由选项 给出包经过的某些路由器列表 记录路径选项 使每个路由器都附上它的IP地址 时间戳选项 使每个路由器都附上它的IP地址和时间戳,TLV格式,112,113,114,5.6.2 IP地址,IP地址 为了屏蔽物理网络地址的差异，IP采用一种全局通用的地址格式为全网的每个主机和路由器分配一个唯一的地址 实际上，IP地址引用的不是一台主机，而是一个网络接口。大多数主机只有一个网络接口，也就只有一个IP地址 IP地址是32位长，包含网络部分和主机部分,115,IP地址分

47、类,116,Class A（A类地址）,Class A - 0nnnnnnn hhhhhhhh hhhhhhhh hhhhhhhh 第一位为0；7位网络位；24位主机位 第一个字节：0-127 允许多达126个网络（0和127保留） 每个网络允许多达16，777，214（=224-2）台主机,117,B类地址,Class B - 10nnnnnn nnnnnnnn hhhhhhhh hhhhhhhh 前两位10； 14位网络位；16位主机位 第一个字节：128-191 允许多达16，384（=214）个网络 每个网络允许多达65，534（=216-2）台主机,118,C类地址,Class C

48、- 110nnnnn nnnnnnnn nnnnnnnn hhhhhhhh 前三位110；21位网络位；8位主机位 第一个字节：192 - 223 允许多达2，097，152网络 每个网络允许多达254台主机,119,D类地址,Class D - 1110mmmm mmmmmmmm mmmmmmmm mmmmmmmm 前四位1110；28位多播（ multicast）地址位 第一个字节：224 - 247 D类地址是多播地址 见RFC 1112,120,E类地址,Class E - 1111rrrr rrrrrrrr rrrrrrrr rrrrrrrr 前四位1111；28位保留地址位 第一个

49、字节：248 - 255 预留将来扩展,121,IP地址表示,二进制 10100001 00000000 01110100 11100001 十六进制 A10074E1 点分十进制 25,122,私有地址,RFC1918 - Address Allocation for Private Internets - 55 (10/8 prefix) - 55 (172.16/12 prefix) - 55 (192.168/16 prefix

50、) 仅用于实验或企业内部使用 Internet上不可路由,123,特殊IP地址,环回地址（Loopback） 每个IP协议栈都实现了 本地网络的广播地址和对一个指定网络的广播地址 FF.FF.FF.FF： 55 network.FF： 55， 55 网络地址 network.00： 本地网络中的主机地址 00.00.00.host： 88,一般来说，主机号部分为： 全“1 ”的IP地址保留用作广播地址； 全“0 ”的IP地址保留用作网络地址。,124,子网划分,分类地址

51、适用于设计之初的互联网 但是A类网络和B类网络太大，不易管理 解决方法 将网络分成若干供内部使用的子网，对外界，该网络还是一个单独的网络,125,子网划分举例,例如：C类网络，主机号部分的前三位用于标识子网号，即： 11000000 00001010 00000001 xxxyyyyy,网络号+子网号,新的主机号部分,子网地址分别为 11000000 00001010 00000001 00000000 - 11000000 00001010 00000001 00100000 - 2 11000000 00001010 00000

52、001 01000000 - 4 11000000 00001010 00000001 01100000 - 6 11000000 00001010 00000001 10000000 - 28 11000000 00001010 00000001 10100000 - 60 11000000 00001010 00000001 11000000 - 92 11000000 00001010 00000001 11100000 - 24,126,经过上述子网划分后存在的问题

53、如何知道一个IP地址中哪些位是网络号+子网号，哪些位是主机号呢？ 解决方法 引入子网掩码,子网掩码（Subnet Mask）,127,子网掩码,子网掩码格式 32比特 前一部分全1，1的个数表示相应IP地址中网络+子网部分的位数 后一部分全0，0的个数表示相应IP地址中主机部分的位数 注意 连接在同一个子网上的所有主机和路由器的子网掩码相同 两个IP地址和子网掩码相与结果相同，表示这两个IP地址的主机在同一个子网中,网络+子网部分,主机部分,11111111 11 00 . 00,128,子网掩码计算,例：网络部分24位，子网部分3位。求子网掩码 11111111 11111111 11111

54、111 11100000 即 255 . 255 . 255 . 224 为了和原来的IP地址分类兼容，使用默认的子网掩码： A类： B类： C类：,129,检查子网掩码命令,Windows XP ipconfig,130,检查子网掩码命令,Linux/Unix ifconfig,131,子网地址计算,子网掩码 IP地址，结果就是该 IP地址的网络地址 例如：IP地址07，子网掩码24 11001010 01110101 00000001 110 01111 11111111 11

55、111111 11111111 111 00000 11001010 01110101 00000001 110 00000,其网络地址为92 主机之间要能够直接通信，它们必须在同一子网内，否则需要使用路由器（或网关）实现互联,132,子网划分举例,网络分配了一个C类地址：。假设需要20个子网，每个子网有5台主机。试确定各子网地址和子网掩码。 1）对C类地址，要从最后8位中分出几位作为子网地址， 242025，选择5位作为子网地址，共可提供 32个子网地址 2）检查剩余的位数能否满足每个子网中主机台数的要求， 子网地址为5位，故还剩3位可以用作主机地

56、址。而 235+2，可以满足每子网5台主机的要求 3）子网掩码为48 （11111000B = 248 ） 4）子网地址可在、、 6、4、 48共32个地址中任意选择20个,133,无类别域间路由（CIDR）,分类地址存在的问题 A类、 B类地址太大 一个A类网络有16M个地址 一个B类网络有65536主机地址 C类地址太小 一个C类网络有256个地址 需要更灵活的方式!,134,CIDR,解决方法1：子网划分 将网络分成若干供内部使用的子网 但是还存在着问题

57、 C类地址太小 每个C类网络对应一个路由表项，造成路由表膨胀,135,CIDR: Classless Inter-Domain Routing,解决方法2：CIDR 在网络和主机间使用可变长度的划分方法，即无类别地址（CIDR），不需要子网 表示法 点分十进制表示法后跟“/”和网络部分长度，如：29/26 在64个主机的网络上，首地址28,136,CIDR,使用CIDR需要路由协议的支持（到目前所有路由器都支持） 每个路由表项进行扩展，增加了32位的掩码。路由表由所有网络的三元组（IP地址、子网掩码、输出线路）构成的 当一个分组到达时，路由器首先将它

58、的目标IP提取出来，和子网掩码去“与”，结果和表项中的网络号比较，是否匹配 最长匹配原则 路由查找时，若多个路由表项匹配成功，选择掩码长还是短的路由表项？ 选长的即1比特数多的,137,某试验网拓扑图,138,CIDR举例,Cambridge University 需要2048个地址， 55 : 11000010 00011000 00000000 00000000 55: 11000010 00011000 00000111 11111111 记作/21 Edinburgh University 需要1024个地址， 55，记作/22 Oxford University 需要4096个地址， 55，记作/20,139,CIDR举例,Cambridge Univ. 需要2048个地址， 55 : 11000010 00011000 00000000 00000000 55: 11000010 00011000 00000111 11111111 记作: /