1、,计算机通信网,Lecture 5: 网络层,第 5 章 网络层,5.1 网络层的设计问题5.2 路由算法 5.3 拥塞控制算法5.4 服务质量5.5 网络互联5.6 Internet的网络层,第 5 章 网络层,5.1 网络层的设计问题 5.1.1 存储转发数据包交换 5.1.2 提供给传输层的服务 5.1.3 无连接服务的实现 5.1.4 面向连接服务的实现 5.1.5 虚电路与数据报网络的比较,网络层的功能,网络层是OSI参考模型中的第三层 网络层关系到通信子网的运行控制，体现了网络应用环境中资源子网访问通信子网的方式，是OSI模型中面向数据通信的低三层(也即通信子网)中最为复杂、关键的
2、一层。 网络层的目的是实现两个端系统之间的数据透明传送，具体功能包括路由选择、阻塞控制和网际互连等 。,5.1.1 存储转发数据包交换,5.1.2.提供给传输层服务,端点之间的通信是依靠通信子网中的节点间的通信来实现的 在分组交换方式中，通信子网向端系统提供虚电路和数据报两种网络服务，而通信子网内部的操作也有虚电路和数据报两种方式。通信子网的操作方式：虚电路操作方式和数据报操作方式网络层提供的服务：虚电路服务和数据报服务,5.1.2 提供给传输层服务,在计算机网络领域，网络层应该向运输层提供怎样的服务（“面向连接”还是“无连接”）曾引起了长期的争论。争论焦点的实质就是：在计算机通信中，可靠交付
3、应当由谁来负责？是网络还是端系统？,电信网的成功经验让网络负责可靠交付,面向连接的通信方式，服务质量是最主要的因素 建立虚电路(Virtual Circuit)，以保证双方通信所需的一切网络资源。 如果再使用可靠传输的网络协议，就可使所发送的分组无差错按序到达终点。,因特网采用的设计思路,网络层向上只提供简单灵活的、无连接的、尽最大努力交付的数据报服务。网络在发送分组时不需要先建立连接。每一个分组（即 IP 数据报）独立发送，与其前后的分组无关（不进行编号）。网络层不提供服务质量的承诺。即所传送的分组可能出错、丢失、重复和失序（不按序到达终点），当然也不保证分组传送的时限。,第 5 章 网络层
4、,5.1 网络层的设计问题 5.1.1 存储转发数据包交换 5.1.2 提供给传输层的服务 5.1.3 无连接服务的实现 5.1.4 面向连接服务的实现 5.1.5 虚电路与数据报网络的比较,5.1.3无连接服务的实现,应用层运输层网络层数据链路层物理层,应用层运输层网络层数据链路层物理层,5.1.3无连接服务的实现,H1,H2,IP 数据报,丢失,H1 发送给 H2 的分组可能沿着不同路径传送,应用层运输层网络层数据链路层物理层,应用层运输层网络层数据链路层物理层,5.1.4 面向连接服务的实现,H1,H2,虚电路,H1 发送给 H2 的所有分组都沿着同一条虚电路传送,虚电路是逻辑连接,虚电
5、路表示这只是一条逻辑上的连接，分组都沿着这条逻辑连接按照存储转发方式传送，而并不是真正建立了一条物理连接。请注意，电路交换的电话通信是先建立了一条真正的连接。因此分组交换的虚连接和电路交换的连接只是类似，但并不完全一样。,虚电路建立实例,尽最大努力交付的好处,由于传输网络不提供端到端的可靠传输服务，这就使网络中的路由器可以做得比较简单，而且价格低廉（与电信网的交换机相比较）。如果主机（即端系统）中的进程之间的通信需要是可靠的，那么就由网络的主机中的运输层负责（包括差错处理、流量控制等）。采用这种设计思路的好处是：网络的造价大大降低，运行方式灵活，能够适应多种应用。因特网能够发展到今日的规模，充
6、分证明了当初采用这种设计思路的正确性。,5.1.5虚电路与数据报网络的对较,第 5 章 网络层,5.2 路由算法 5.2.1 优化原则 5.2.2 最短路径算法 5.2.3 泛洪算法 5.2.4 距离矢量算法 5.2.5 链路状态路由 5.2.6 层次路由 5.2.7 广播路由 5.2.8 组播路由 5.2.9 选播路由 5.2.10 移动主机路由 5.2.11 自组织网络路由,5.2 路由算法,通信子网为网络源节点和目的节点提供了多条传输路径的可能性。网络节点在收到一个分组后后，要确定向下一节点传送的路径，这就是路由选择，路由选择是网络层要实现的基本功能。在数据报方式中，网络节点要为每个分组
7、路由做出选择；而在虚电路方式中，只需在连接建立时确定路由。路由选择包括两个基本操作，即最佳路径的判定和网间信息包的传送。确定路由选择的策略称路由算法。,算法必须是正确的和完整的。 算法在计算上应简单。 算法应能适应通信量和网络拓扑的变化，这就是说，要有自适应性（鲁棒性）。 算法应具有稳定性。 算法应是公平的。 算法应是最佳的。,理想的路由算法,设计路由算法时要考虑诸多技术要素。,首先，考虑是选择最短路由还是选择最佳路由；其次，要考虑通信子网是采用虚电路的还是采用数据报的操作方式；其三，是采用分布式路由算法，即每节点均为到达的分组选择下一步的路由，还是采用集中式路由算法，即由中央节点或始发节点来
8、决定整个路由；其四，要考虑关于网络拓朴、流量和延迟等网络信息的来源；最后，确定是采用静态路由选择策略，还是动态路由选择策略。,第 5 章 网络层,5.2 路由算法 5.2.1 优化原则 5.2.2 最短路径算法 5.2.3 泛洪算法 5.2.4 距离矢量算法 5.2.5 链路状态路由 5.2.6 层次路由 5.2.7 广播路由 5.2.8 组播路由 5.2.9 选播路由 5.2.10 移动主机路由 5.2.11 自组织网络路由,5.2.1 最优化原则,在讨论某个特殊算法之前，有必要指出即使在不知道详细的通信子网拓扑结构和通信量的情况下，也可能对最优路由作出总体上的断言。 这种断言被称作最优化原
9、则， 它断言，如果路由器J在从路由器I到K的最佳路由上， 那么从J到K的最佳线路就会在同一路由之中。为理解这些，假设从I到J的路由为rl，而路由其余部分称为r2。如果J到K还有在一条比r2更好的路由，那么它可以同r1联系起来，以改进从I到K的路由，这与r1r2是最优路由的断言相悖。,5.2.1 最优化原则,作为最优化原则的一个直接结果，可知，从所有源端到目地端的最佳路由集合，形成了以目的地为根的树。这样一棵树称为汇集树， 如下图所示，其中距离度量单位是站点数。应当指出的是，汇集树并不惟一，共他具有相同的路由尺度的树也有可能存在。所有路由选择算法的目的就是为所有路由器找出并使用汇集树。,5.2.
10、1 最优化原则,(a) A network. (b) A sink tree for router B.,5.2.1 最优化原则,因为汇集树是一棵树，它不包含任何循环。因此每个分组可在有限的步长之内送达。实际上，现实并不那么简单，在操作过程中链路或路由器都有可能卸下或重新装上。而且，我们必须弄清，是否每个路由器都得单独地获取计算其汇集树的信息，或者用其他方法来获取信息。不管怎样，最优化原则和汇集树为路由选择算法提供了一个测量标准。,路由选择,路由算法有两类：,非自适应,自适应,静态路由,动态路由,路由表固定,路由表定时刷新,路由协议,简便、可靠、易行，适用于负荷稳定、拓扑结构变化不大的网络,算
11、法复杂，会增加网络负担，但能够改善网络的性能，并有利于流量控制,两类路由算法,非自适应算法离线时计算好，网络启动时下载到路由器中；静态路由自适应算法获取信息的来源不同 本地、相邻路由器、改变路由的时间不同 每隔t秒随负载变化路由优化的度量方法不同 距离、跳数、估计的传输时间动态路由,第 5 章 网络层,5.2 路由算法 5.2.1 优化原则 5.2.2 最短路径算法 5.2.3 泛洪算法 5.2.4 距离矢量算法 5.2.5 链路状态路由 5.2.6 层次路由 5.2.7 广播路由 5.2.8 组播路由 5.2.9 选播路由 5.2.10 移动主机路由 5.2.11 自组织网络路由,静态路由选
12、择算法,静态路由选择策略不用测量也不需利用网络信息，这种策略按某种固定规则进行路由选择；可分为最短路由选择法、扩散法和基于流量的路由选择法。,5.2.2.最短路由选择法,基本思想: 建立一个子网图,图中的每个节点代表一台路由器,每条弧线代表一条通信线路(链路),弧上的数字代表该线路的权重。为了在一对给定的路由器之间选择一条路由路径，路由算法只需在图中找到这对节点之间的最短路径即可。最著名的Dijkstra算法,Dijkstra算法,算法要求每个节点用从源节点沿已知最佳路径到本节点的距离来标注。1、开始所有节点标注为无穷大2、改变与源点相邻节点的标注3、找到新标注点中的最小的点M4、以M为新工作
13、点，标注其相邻节点（若某点曾经标记过，并且新标记小于老标记，则更新其标记）5、返回第3步,利用Dijkstra算法求A到D的最短通路,A,B(2,A),E(,-),G(6,A),C(,-),F(,-),H(,-),D(,-),A,B(2,A),E(4,B),G(6,A),C(9,B),F(,-),H(,-),D(,-),利用Dijkstra算法求A到D的最短通路,A,B(2,A),E(4,B),G(5,E),C(9,B),F(6,E),H(,-),D(,-),A,B(2,A),E(4,B),G(5,E),C(9,B),F(6,E),H(9,G),D(,-),A,B(2,A),E(4,B),G(
14、5,E),C(9,B),F(6,E),H(8,F),D(,-),A,B(2,A),E(4,B),G(5,E),C(9,B),F(6,E),H(8,F),D(10,H),A,B(2,A),E(4,B),G(5,E),C(9,B),F(6,E),H(8,F),D(10,H),A,B(2,A),E(4,B),G(5,E),C(9,B),F(6,E),H(8,F),D(10,H),最短通路为：A-B-E-F-H-D，权值为10,利用Dijkstra算法求A到D的最短通路,5.2.3.泛洪算法,又称为：泛射路由选择法一个网络节点从某条线路收到一个分组后，再向除该线路外的所有线路重复发送收到分组。结果，最
15、先到达目的的节点的一个或若干个分组肯定经过了最短的路径，而且所有可能的路径都被尝试过。 没有考虑网路负载 应用：强壮性要求很高的场合 ，只要源、目间有一条信道存在，仍能保证数据的可靠传送 。也可用于广播式数据交换中。 进行网络的最短路径及最短传输延迟的测试。无线网络中,泛洪算法,产生大量的重复分组，解决办法：每个分组头包含站计数器，每经过一个站点计数器减一。当计数器为0时就扔掉分组。记录下分组扩散的路径，防止第二次再扩散到已扩散的路径中改进成选择扩散法，仅发送到与正确方向接近的那些线路上。,第 5 章 网络层,5.2 路由算法 5.2.1 优化原则 5.2.2 最短路径算法 5.2.3 泛洪算
16、法 5.2.4 距离矢量算法 5.2.5 链路状态路由 5.2.6 层次路由 5.2.7 广播路由 5.2.8 组播路由 5.2.9 选播路由 5.2.10 移动主机路由 5.2.11 自组织网络路由,动态路由选择算法,静态路由选择算法不考虑网络的当前负载情况，现代计算机网络通常使用动态的路由算法。节点的路由选择要依靠网络当前的状态信息来决定的策略，称动态路由选择策略，也称为自适应路由选择算法。这种策略能较好地适应网络流量、拓扑结构的变化，有利于改善网络的性能。但由于算法复杂，会增加网络的负担。 距离矢量路由算法链路状态路由算法,5.2.5链路状态路由,1979年以前，ARPANET一直使用距
17、离矢量路由算法，而在此后，则被替换为链路状态路由算法。每个路由器需要完成以下工作：1发现它的邻居节点，并知道其网络地址2测量到它各邻居节点点的延迟或开销3组装一个分组以告之它刚知道的所有4将这个分组发送给所合其他路由器。5计算到每个其他路由器的最短路径。,发现邻居结点，并学习它们的网络地址；路由器启动后，通过发送HELLO包发现邻居结点；测量到每个邻居结点的延迟或开销；一种直接的方法是：发送一个要对方立即响应的ECHO包，来回时间除以2即为延迟。将所有学习到的内容封装成一个分组；分组以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；列表中对应每个邻居结点，都有发送方到它们的延迟或开销；
18、链路状态分组定期创建或发生重大事件时创建。,链路状态路由算法步骤,将这个分组发送给所有其它路由器；基本思想：扩散法发布状态分组，为控制洪泛，每个分组包含一个序号，每次发送新分组时加1。路由器记录信息对（源路由器，序号），当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃；计算到每个其它路由器的最短路径。根据Dijkstra算法计算最短路径；,(a) A network. (b) The link state packets for this network.,链路状态路由算法应用,链路状态路由算法被广泛应用于实际的网络中。在因特网中
19、被广泛适用的OSPF开放的最短路径优先协议，就用到了链路状态路由算法。,第 5 章 网络层,5.2 路由算法 5.2.1 优化原则 5.2.2 最短路径算法 5.2.3 泛洪算法 5.2.4 距离矢量算法 5.2.5 链路状态路由 5.2.6 分层路由 5.2.7 广播路由 5.2.8 组播路由 5.2.9 选播路由 5.2.10 移动主机路由 5.2.11 自组织网络路由,区域(region)簇(cluster)区(zone)群(group),Hierarchical routing.,5.2.7 广播路由,给所用的目标发送一个分组，这称为广播，为实现广播，提出以下方法：第一种，不要求子网既
20、有任何特别性的广播方法：让源主机简单地给每一个目标单独发送一个分组；第二种，多目标路由。使用这种方法，每个分组或者包含一组目标，或者包含一个位图，由该位图来指定所期望的目标；第四种，使用了以发起广播的路由器为根的汇集树，生成树是子网的一个子集，它包含所有的路由器，但是不包含任何环；最后一种是逆向路径转发：当路由器根本不知道任何关于生成树的信息时，也要试图达到前一种方法的近似效果。逆向路径转发的优点是：它的效率相对合理，而且容易实现。,逆向路径转发,基本思想：当广播分组到达一个路由器时，路由器对它进行检查，查看它到来的那条线路是否是通常用来给广播源发送分组的那条线路，如果是，该路由器将把这个广播
21、分组复制转发到除输入线路外的所有线路。如果不是，则这个分组将被废弃。优点：效率相对合理，而且容易实现,逆向路径转发,汇集树第一跳：F,H,N,J;第二跳：A,D,M,O,G；第三跳: C,E,K；第四跳:B,L 逆向路径转发第一跳：F,H,N,J;第二跳：A,D,E,K,G,O,M,O；第三跳: E,C,G,D.N,K；第四跳: H,B,L,H;第五跳：L,B,汇集树,H,广播算法,利用汇集树（sink tree）或生成树（spanning tree）生成树是通信子网的一个子集，能将所有路由器连接起来，并且没有回路；汇集树是最佳路由集合如果每个路由器知道它的哪些线路属于生成树，则将收到的广播包
22、拷贝到输入线路以外的所有其它生成树线路上；算法评价优点：最优利用带宽，产生最小数目的分组缺点：每个路由器都需要构造生成树链路状态路由算法可以使用距离矢量路由算法不可以使用,5.2.8 组播路由,能够给一些有明确定义的组发送消息，这些组的成员数量虽然很多，但是与整个网络规模相比很小，给这样一个组发送消息成为多点播送，简称多播，又称组播，它的路由算法称为多播路由选择。多播传送需要对组进行管理。,多播路由选择,1,2,1,2,2,2,2,1,1,1,1,2,1,2,2,2,2,1,1,1,1,1,1,1,1,2,2,2,2,2,一个子网,最左边路由器的生成树,小组1的多点播送树,小组2的多点播送树,
23、5.2.9 移动主机路由,1、永久不会移动的主机称为固定主机，它们通过铜线或者光纤连线到网络中。2、迁移主机，它们基本上也是固定的，但是经常会从一个固定的站点移动到另一个固定的站点，并且只有当它们物理上连接到网络的时候才使用网络。3、漫游主机，是在移动过程中执行计算，它们希望在移动的时候还能保持与网络的连接。我们使用术语移动主机来代表这类主机，也就是说，移动主机是指那些离开了原始站点还想继续连接网络的主机。,移动主机路由,移动后重新计算路由；网络层之上提供移动；家乡代理,Packet routing for mobile hosts.,5.2.9 移动主机路由,移动主机登录到外地代理的过程1. 外地代理定期广播一个分组，宣布自己的存在及其地址。2. 移动主机登录到外地代理，并给出其原来所在地的地址，当前数据链路层地址以及一些安全性信息。3.外地代理与移动主机的主代理联系，核实移动主机是否真的在那。4.主代理检查安全性信息，如果核实通过，则通知外地代理继续。5.当外地代理从主代理处得到确认后，在它的表中加入一个表项，并通知移动主机登录成功。,
