第5章 络层.ppt

1、第5章 网络层,网络层主要解决的问题 路由选择 网络互连 拥塞控制 为上层提供服务,第5章 网络层,网络层设计的相关问题 路由算法 拥塞控制 服务质量 网络互联 因特网中的网络层,网络层的设计,存储转发的数据包交换 为传输层提供的服务 数据包子网的实现 虚电路子网的实现 虚电路子网和数据报子网的比较,网络层协议环境,Tnbm P344 Fig. 5-1 网络层协议环境,网络层的设计,存储转发的数据包交换 为传输层提供的服务 数据报网络的实现 虚电路子网的实现 虚电路子网和数据报子网的比较,为传输层提供的服务,服务应与路由器技术无关 路由器的数量、类型和拓扑结构对于传输层来说应是不可见的 传输层

2、所能获得的网络地址应采用统一的编址方式，并允许跨越多个LAN和WAN,网络层提供的服务类型,数据报网络：网络是不可靠的，网络服务不应面向连接，分组的排序和流控制应不属于网络层，每个分组都单独寻径，所以必须携带完整的目的地址 如Internet 虚电路网络：网络应该提供可靠的、面向连接的服务，否则服务质量将无从谈起，尤其对于多媒体应用 如 ATM,对于网络层提供的服务有两种观点：,网络层的设计,存储转发的数据包交换 为传输层提供的服务 数据报网络的实现 虚电路网络的实现 虚电路子网和数据报子网的比较,面向无连接服务的实现（数据报子网）,路由器A按左边的路由表运行，后来发现如到E和F应该走B才更好

3、，于是更新路由表,A的路由表,E的路由表,C的路由表,Tnbm P346 Fig. 5-2 数据报子网中分组的寻径,网络层的设计,存储转发的数据包交换 为传输层提供的服务 面向无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较,面向连接服务的实现（虚电路子网）,H1和H2已建立了1#连接 H3要和H2建立连接只能是2#,A的路由表,Tnbm P348 Fig. 5-3 虚电路子网中分组的寻径,C的路由表,E的路由表,网络层的设计,存储转发的数据包交换 为传输层提供的服务 面向无连接服务的实现 面向连接服务的实现 虚电路子网和数据报子网的比较,虚电路子网和数据报子网的比较,Tnb

4、m P349 Fig. 5-4虚电路子网和数据报子网的比较,虚电路子网/数据报子网的比较(续),虚电路子网 通过路径选择后建立连接 分组按序传输 服务质量能得到保证 通信后撤销连接 适合于实时传输 数据报子网 每个分组分别选择最佳路径，健壮性较好 整个网络系统的信道利用率高，成本低 差错控制和排序工作由协议高层（主机）完成 适合于非实时传输,第5章 网络层,网络层设计的相关问题 路由算法 拥塞控制 服务质量 网络互联 因特网中的网络层,路由算法,路由算法是网络层软件的一个重要部分，它决定进入的分组应从哪一根输出线传输 如果是数据报子网，将在每一个分组到达时作此决定 如果是虚电路子网，是在虚电路

5、建立时决定，该连接上所有分组都将沿此线路传输 路由与转发：路由是寻径，转发是当一个分组到达时发生的动作,路由算法（续）,路由算法设计必须考虑的问题正确性 简单性 健壮性 稳定性 公平性 最优性 路由算法中的度量标准 路径长度 hop数 延迟时间,路由算法的分类,静态算法 自适应算法 拓扑相关的路由算法 移动节点的路由 Ad-hoc网络的路由,静态算法（static routing）,最短路径算法（Dijkstra） 扩散法（flooding）,为路由器配置一张最优的路由表,最短路由选择（Dijkstra）,Dijkstra算法（1959）：通过用边的权值作为距离的度量来计算最短路径，有最少边数

6、的路径不一定是最短路径,如下图： 5和4之间边数最少的路径是5234但最短路径是523674,采用的数据结构,集合S：尚未找到最短路径的节点 的集合 数组R：Ri为从指定源点去节点i 的路径上，节点i的前一个 节点 数组D：Di为从指定源点到节点i 的最短距离,算法的初始化,初始化集合S为除源节点外的所有节点 初始化数组D：如果从源节点到节点v的边存在，则D(v)为该边的权值，否则为无穷大 初始化数组R：如果从源节点到节点v的边存在，则R(v)为源节点，否则为0,算法,WHILE（集合S非空） 从S中选一节点u，使Du最小；如果（Du为无穷大）错误！无路径存在，退出把u从S中删去；对(u,v)

7、是边的每个节点v 如果（v仍在S中）C=Du+weight(u,v);如果 （CDv） /*v找到了一条更短的路径*/Rv= u; /*替换v的最短路径及长度*/Dv=C;,从5出发到各个节点的最短路径,静态算法（static routing）,最短路径算法（Dijkstra） 扩散法（flooding）,为路由器配置一张最优的路由表,扩散法（flooding）,不计算路径，有路就走,如从5出发到4： 数据包从51,2；23,6；36,4；63,7；74,要解决的问题：数据包重复到达某一节点，如3，6,扩散法（续）,解决方法 在数据包头设一计数器初值，每经过一个节点自动减1，计数值为0 时，丢

8、弃该数据包 在每个节点上建立登记表，则数据包再次经过时丢弃,缺点：重复数据包多，浪费带宽 优点：可靠性高，路径最短，常用于军事,路由算法的分类,静态算法 自适应算法 拓扑相关的路由算法 移动节点的路由 Ad-hoc网络的路由,自适应算法是动态的、分布式的算法 实现分布式算法的三要素： The measurement process（测量） The update protocol（更新协议） The calculation（计算）,自适应算法（adaptive algorithm）,自适应算法（adaptive algorithm）,距离矢量算法（D-V） 链路状态算法（L-S）,路由器动态建立

9、和维护一张最优的路由表,D-V算法的工作原理,每个路由器用两个向量Di和Si来表示该点到网上所有节点的路径距离及其下一个节点 相邻路由器之间交换路径信息 各节点根据路径信息更新路由表,其中：,n 网络中的节点数 Di节点i的时延向量 dij节点i到j的最小时延的当前估计值 Si节点i的后继节点向量 sij从节点i到j的最小时延路径上的下一节点,路由表的更新,dij = min(dix + dxj) ( x A ) （从i到j的时延取途经每个节点时的时延的最小值） Sij = x（从i到j途经的下一个节点为x）,其中：,A 与i相邻的所有节点的集合 diji到j 的最短距离 dixi到x的最短距

10、离 dxjx到j 的最短距离,注意：AI为21；IA为24 因为：往和返的信道流量不一定相同，节点A和I也并非在同一时刻测得，且线路状态是动态变化的,所谓节点即路由器当前节点为J,Tnbm P358 Fig. 5-9 D-V算法的路由表更新,D-V算法的缺点,交换的路径信息量大 路径信息不一致 收敛速度慢（坏消息） 不适合大型网络,无穷计算问题,好消息传播得快，坏消息传播得慢,A下网了,Tnbm P359 Fig. 5-10 无穷计算问题,克服收敛速度慢的方法,水平分裂 同距离矢量法，只是到X的距离并不是真正的距离，对下方点通知真正的距离，对上方点，给出无穷大 如上图中的C点，它向D通知到A的

11、是真正距离，而向B通知到A的距离是无穷大 Holddown 当发现不通时，不重新选路径，而是把它设成无穷大 这些方法尚在研究之中,自适应算法（adaptive algorithm）,距离矢量算法（D-V） 链路状态算法（L-S）,路由器动态建立和维护一张最优的路由表,链路状态算法（ L-S ） （Link State Routing）,基本思想： 发现它的邻接节点，并得到其网络地址 测量它到各邻接节点的延迟或开销 组装一个分组以告知它刚知道的所有信息 将这个分组发给所有其他路由器 计算到每个其他路由器的最短路径,发现邻接节点,当一个路由器启动后，向每个点到点线路发送HELLO分组（携带自己的网

12、络地址），另一端的路由器发送回来一个应答来说明它是谁，即通报其网络地址,链路状态算法（ L-S ） （Link State Routing）,基本思想： 发现它的邻接节点，并得到其网络地址 测量它到各邻接节点的延迟或开销 组装一个分组以告知它刚知道的所有信息 将这个分组发给所有其他路由器 计算到每个其他路由器的最短路径,测量线路开销,发送一个ECHO分组要求对方立即响应，通过测量一个来回时间再除以2，发送方就可以得到一个延迟估计值，想要更精确些，可以重复这一过程，取其平均值 如果链路状态发生过变化，则进入下一步骤,链路状态算法（ L-S ） （Link State Routing）,基本思想：

13、 发现它的邻接节点，并得到其网络地址 测量它到各邻接节点的延迟或开销 组装一个分组以告知它刚知道的所有信息 将这个分组发给所有其他路由器 计算到每个其他路由器的最短路径,构造分组,子网及其节点到其邻节点（路由器）的线路开销测量值（即延时，假设以ms计）,子网的链路、状态及分组情况：,节点A仅与节点B和E相邻 A B的时延为4ms A E的时延为5ms,Tnbm P363 Fig. 5-13 L-S算法的路由表更新,链路状态算法（ L-S ） （Link State Routing）,基本思想： 发现它的邻接节点，并得到其网络地址 测量它到各邻接节点的延迟或开销 组装一个分组以告知它刚知道的所有

14、信息 将这个分组发给所有其他路由器 计算到每个其他路由器的最短路径,发布链路状态分组,用扩散法（向邻接的节点）发布链路状态分组 （以B为例，B的邻接点有A、C、F）,源节点E的链路状态分组经A和F到节点B，节点B必须再将E的状态分组转送到C，并向A和F发ACK,发送标志,ACK标志,Tnbm P365 Fig. 5-14 链路状态分组的转发和确认,存在的问题,状态分组的重复到达 如果序号循环使用，就会发生重复 如果一个路由器被重起，序号将从0开始重新计数，但这些分组会被当成过时分组 如果序号发生错误（如序号用32位表示，4被看成65540，第16位的0被误传成了1），则很多分组将被看成过时分组

15、（此时565539均为过时分组，因为当前的分组序号是65540）,解决办法,使用一个32位序号，即使每秒钟发送一个分组，137年才会循环一次 在每个分组中加一年龄字段（如初值为60），每秒钟将年龄减1，为0后该分组将被丢弃 ，否则不会被认为是过时分组,链路状态算法（ L-S ） （Link State Routing）,基本思想： 发现它的邻接节点，并得到其网络地址 测量它到各邻接节点的延迟或开销 组装一个分组以告知它刚知道的所有信息 将这个分组发给所有其他路由器 计算到每个其他路由器的最短路径,计算新路由,用Dijkstra算法计算到每个节点的路由 得到该节点到每个节点的最短路径,L-S路由

16、算法的优缺点,LSR的优点 路由信息的一致性好，坏消息也一样传播得快 状态分组的长度较短，仅包含到邻接点的距离、序号和年龄等，与网络规模关系不大，传输所耗用的网络带宽不大，此外，状态分组的扩散，由于年龄参数的设定，不会无限制扩散，所以可适用于大型网络 LSR的缺点 每个路由器需要有较大的存储空间，用以存储所收到的每一个节点的链路状态分组 计算工作量大，每次都必须计算最短路径,路由算法的分类,静态算法 自适应算法 拓扑相关的路由算法 移动节点的路由 Ad-hoc网络的路由,拓扑相关的路由算法,分层路由 广播路由 多址传输路由选择 Peer-to-Peer网的节点查找,分层路由,随着网络规模的增长

17、，存储和处理路由表所需的资源也急剧增长，从拓扑上分层是解决问题的一个方法 分层的概念：将路由器分成组，每一路由器知道到组内任何一台路由器的路由，以及到其他组的路由，因此可把其他组中所有的路由器抽象成一个，以减少路由表的长度,分层实例,不分层时1A的路由表,分层时1A的路由表,Tnbm P367 Fig. 5-15 分层路由,分层的层数,Kamoun和Kleinrock发现：N个路由器的最优层次数是lnN，每个路由器需要elnN个路由表项,拓扑相关的路由算法,分层路由 广播路由 多址传输路由选择 Peer-to-Peer网的节点查找,广播路由,逐个向所有节点分别发送报文 缺点：发送量大需知道网上

18、所有节点的地址 扩散法 缺点：流量大，消耗大量带宽某些节点还可能收到重复的报文,广播路由算法,多目的地路由 生成树算法 逆向路径传送,多目的地路由,分组中包含需到达的多个目的地的地址表 到一个节点时，路由器检查所有的目的地址表，确定输出线路集合，路由器为每一条输出线路复制一个新的分组，每个分组中仅含有要用此线路的目的地址表 优点：流量小，节约带宽 缺点：费用承担不公平,广播路由算法,多目的地路由 生成树算法 逆向路径传送,生成树算法,路由器将分组沿生成树发送（除进入线路之外） 优点：带宽得到最佳利用 缺点：每个路由器必须知道其可用生成树 如链路状态路由算法可得到生成树，距离矢量路由算法却不能得

19、到,广播路由算法,多目的地路由 生成树算法 逆向路径传送,逆向路径传送,基本原理：当某一广播分组到达路由器时，路由器对它进行检查，如该分组来自通常向广播源发送分组的线路，则将该分组转发到除进线以外的其它线路，否则丢弃,Tnbm P369 Fig. 5-16 逆向路径传送,逆向路径传送说明,在(a)的子网中，每个节点都已生成了一张路由表，假设当前每个节点的路由表中到节点I去的路径中的下一跳分别为：,逆向路径传送说明（续1）,根据上述逆向路径转发的原则，可构造如下一棵树,(c) 由逆向路径转发构造的树,逆向路径传送说明（续2）,如节点F收到一个从I来的分组，则立即向节点A和节点D转发 当节点D收到

20、一个经F来的节点I的分组，它意识到如它有分组要送给I的话，是走节点F的，所以立即向节点C和G转发 当节点G收到一个经D来的节点I的分组，它意识到如它有分组要送给I的话，是走节点J而不是走节点D的，所以它不再转发,所以：经过5个站点共24个分组的转发后，广播算法结束 优点：算法合理，容易实现 缺点：对大型网络不适用,拓扑相关的路由算法,分层路由 广播路由 多址传输路由选择 Peer-to-Peer网的节点查找,多址传输路由选择 (Multicast Routing),多址传输路由选择 使用IP的D类地址生成树法 核心树(core-based tree),A类 B类 C类 D类 E类,大规模网络

21、中规模网络 小规模网络,Tnbm P437 Fig. 5-55 IP地址格式,生成树法,组中的每个成员都必须以自己作为出发点建立一棵生成树，根据自己所在小组对生成树进行修剪，得到一棵本小组修剪过的生成树，并告诉同组的其他成员 多址传输时仅沿相应的生成树转发,缺点：存储量大 如一个网络有n个组，每个组平均有m个成员，则要存储m*n棵生成树,多址传输路由选择 (Multicast Routing),多址传输路由选择 使用IP的D类地址生成树法 核心树(core-based tree),A类 B类 C类 D类 E类,大规模网络 中规模网络 小规模网络,Tnbm P437 Fig. 5-55 IP地址

22、格式,核心树(core-based tree),每个组只有一棵生成树，它的树根靠近组的中心部位，要发送一个分组给这个组成员，则发给树根，由树根将该分组沿核心树发往各成员，这样，每组只有一棵核心树，节约了存储空间,拓扑相关的路由算法,分层路由 广播路由 多址传输路由选择 Peer-to-Peer网的节点查找,Peer-to-Peer网中节点的查找,对等网：每个站点既是客户器又是服务器 对等网种类： 中心化拓扑：用中心化的目录系统 全分布非结构化的P2P：采用随机洪泛发现 半分布结构：采用层次性的结构，用一些超级节点记录其他结点的信息 全分布结构化的P2P,结构化的P2P- Chord算法,假设：

23、 系统中有n个用户 每个用户都有可提供的信息资源，并且都已作了索引供其他用户使用 每个用户都有一个IP地址，并可被散列成m位的一个数字，称为节点标识符（Chord用SHA-1算法来散列），节点标识符为0 2m-1 所有2m个标识符按递增次序链接成一个环，而不管节点是否存在 定义函数successor(k)：找出节点k后面的第一个存在节点,Chord算法（续）,信息资源名称(name)同样被散列为一个m位的数字，称为键值key（key=hash(name)） 信息索引的存储：信息的索引在所有节点上是随机分布的，当一个节点要提供信息name时，它首先构造一个二元组（name, IP地址），然后调用

24、successor(hash(name)去存储该二元组，不同节点上的同名信息，其索引将被存在同一节点 信息的查找：当某个用户需要查找名称为name的信息时，向successor(key)发一个请求，要求返回拥有信息name的节点的IP地址,Chord算法优化,每个节点保存其直接前趋和直接后继，那么请求可以顺时针传递，也可以逆时针传递，可以在两者之间选择一条较短的路径 每个节点保存一张表，称为finger table，该表有m个表项，编号从0到m-1,Chord算法优化（续1）,finger table表的内容 每个表项指向一个实际存在的节点，每个表项有两个字段：start 和 successo

25、r(start)的IP地址，节点k中第i个表项的值为：Start i = k + 2i mod ( 2m ) i=0m-1Successor (start i ) 的IP地址,Chord算法实例,Tnbm P382 Fig. 5-24 Chord算法实例,Chord算法优化（续2）,在节点k上查找键值key的过程： 如果key = k，那么包含key信息的节点是k，查找结束。 如果k key successor (k)之间，那么包含key信息的节点是successor (k) ，查找结束 否则，查找finger表，找出小于key但最接近key的start值，并直接发一请求给successor(

26、start)的IP地址，请求它继续查找,Chord算法实例 （续）,例1：在节点1上查找key=3（key=hash(name)=3）对于节点1，successor(1)=4， key在(1,4)中，返回4，即资源名为name的索引在节点4上 例2：在节点1上查找key=14由于key不在(1,4)中，于是查节点1的finger table，小于14并最接近14的节点是9，successor(9)=12；于是到节点12查找，successor(12)=15，key在(12,15)中，于是返回15 例3：在节点1上查找key=16key不在(1,4)中，于是查节点1的finger table，小

27、于16并最接近16的节点是9， successor(9)=12，于是到节点12查找，successor(12)=15，key不在(12,15)中，于是查节点12的finger table，小于16并最接近16的节点是14， successor(14)=15，于是到节点15查找，successor(15)=20，key在(15,20)中， 于是返回20，即所查找的资源的索引在节点20上,节点的动态添加和删除,初始化：假设开始时节点很少，因此通过节点之间直接交换信息建立初始的环和finger表 添加节点r： 向任一节点询问successor(r)的地址s 向s询问它的直接前趋p 向s和p申请加入环

28、 节点s将p+1到r的信息转储到r上，添加即告结束 其他finger表中的问题由定时执行一个后台进程完成 删除节点r 将r的信息转储到后继s 通知前趋p，它的后继变为s,节点的动态添加举例,Chord算法实例中添加节点24,0,1,7,12,20,27,4,10,9,8,6,5,3,2,11,16,15,14,13,19,18,17,21,22,23,24,26,25,30,29,28,31,i=4,4,4,2,0,1,2,3,2,3,0,1,0,1,3,当前在线的节点,路由算法的分类,静态算法 自适应算法 拓扑相关的路由算法 移动节点的路由 Ad-hoc网络的路由,移动IPv4（rfc200

29、2）,移动IP技术，是移动用户在跨网络随意移动和漫游中，不用修改计算机配置的IP地址，享有原网络中一切权限。 支持主机移动或漫游的协议是Mobile IP协议 Mobile IP协议中定义了三种功能实体： 移动节点：一个移动的计算机，它改变位置时无需更改其IP设置，仍然可以通过其固定的IP地址进行通信。 主代理：一个移动节点本地网络的主机或路由器，它保存有移动节点的位置信息，当移动节点离开主网络时能够将发往移动节点的数据包传给移动节点。 客代理：移动节点当前所在的外地网络上的一个主机，它能够把由主代理送来的数据包转发给移动节点。,移动IP的工作机制,代理周期性地发送广播，宣告他们与链路之间的关

30、系 移动节点收到这些广播后，判断自己是在本地网还是在其他网。 如在其他网 移动节点向客代理注册，递交自己的IP地址，MAC地址和一些安全信息 客代理与主代理联系，报告自己的网络地址 主代理告诉客代理接收此消息 客代理保存此移动主机的信息,数据包的转发,首先，该包会路由到主网络 主代理查找到了移动主机的新住址，以及客代理的地址。 把此包再封装在一个IP包中，发给客代理 告诉发送者将包直接发给客代理 客代理解封装数据包，把此数据包用数据链路层协议传给移动主机,当有一个包发给移动主机时,安全问题,采用优化路由的主要障碍是安全问题。 当通信对端直接通过隧道与移动节点通信时，对端必须知道移动节点当前的优

31、化地址，这个问题与移动I P注册相似。移动I P注册的目的就是通知家乡代理移动节点当前的转交地址。一个“坏家伙”只需送一个伪造的注册给通信对端就可以中断移动节点和对端的通信，这对移动I P中任何试图优化路由的努力来说都是一个挑战。,移动IPv6,无客代理 同时支持隧道和源路由技术 主要内容 移动主机在外地网上获取一个转交地址 将转交地址通知主代理和他的通信伙伴 知道转交地址的伙伴和直接发送信息 不知道转交地址的伙伴可发送给主代理，由主代理再发送到转交地址,路由算法的分类,静态算法 自适应算法 拓扑相关的路由算法 移动节点的路由 Ad-hoc网络的路由,Ad-Hoc模式,早期的Ad-Hoc模式用

32、于多个移动主机（无线站点）之间的直接通信，毋需接到有线网络，每个站点必须“看”到其它所有站点 现在的Ad-Hoc，移动主机并不要求相互都能“看”到，但，源主机到目的主机之间至少存在一条通路，途中的站点（移动主机）同时也将兼作路由器用，也可以与有线网络连接,Ad-Hoc的路由,主动路由 （表驱动）：每个节点都周期性广播路由信息，主动地发现并维护路由表 DSDV（Destination Sequenced Distance Vector） 按需路由 （事件驱动）：只有在需要发送数据时，源站点才寻找路由 AODV （Ad Hoc On-demand Distance Vector） DSR（Dyna

33、mic Source Routing）,主动路由 DSDV,DSDV（Destination Sequenced Distance Vector）是一种采用距离矢量算法的路由协议 网络中每个节点都维护一张路由表，路由表包含所有可能的目的节点、距离信息以及下一跳等 每个节点都周期地广播其全部的路由信息（对于拓扑变化相对较慢的网络只需广播其更新的路由信息），每个节点都依据所收到的信息来维护它们的路由表 DSDV算法依赖于每个节点路由信息周期性的广播，在Ad-Hoc网络中，由于其网络拓扑是动态变化的，维护一张路由表意味着耗用大量的带宽和CPU资源,Ad-Hoc的路由,主动路由 （表驱动）：每个节点都

34、周期性广播路由信息，主动地发现并维护路由表 DSDV（Destination Sequenced Distance Vector） 按需路由 （事件驱动）：只有在需要发送数据时，源站点才寻找路由 AODV （Ad Hoc On-demand Distance Vector） DSR（Dynamic Source Routing）,按需路由AODV说明,AODV （Ad Hoc On-demand Distance Vector） AODV是DSDV算法的改进，与DSDV的区别在于只是在需要时（on-demand）才寻找路由，而不必如DSDV一样需随时维护一张包含全部节点的路由表 当源节点想发送

35、信息给某个目的节点时，如当前没有路径，则启动Path Discovery过程，广播一个Route Request（RREQ）路径请求分组给相邻节点，收到此请求分组的邻节点再转发给它的相邻节点并建立到源节点的反向路径，直到一个知道目的节点路由信息的中间节点或目的节点本身 ，然后回复Route Reply（RREP）路径应答包给源节点 AODV假设每一条链路都是双向对称的（Symmetric）,按需路由AODV算法,AODV的请求分组和应答分组 AODV的Path Discovery过程 AODV的路径维护,AODV中的请求分组和应答分组,AODV中的请求分组AODV中的应答分组,Tnbm P37

36、8 Fig. 5-22 Route Reply分组的格式,Tnbm P377 Fig. 5-21 Route Request分组的格式,按需路由AODV算法,AODV的请求分组和应答分组 AODV的Path Discovery过程 AODV的路径维护,AODV算法举例环境,Tnbm P376 Fig.5-20(a) A的广播范围,图中每个节点都是一台具有路由功能的移动主机 图为AI九个节点当前的位置及其相互的连接状态 节点A的广播范围覆盖了节点B和节点D，所以A和B以及A和D之间有连接，其它节点间的连接关系如图，并假设连接是双向的 当前A准备向I发送分组，并且当前没有到达I的表项 于是A发送一

37、个RREQ广播分组，分组中包含源和目的地址（A和I的IP地址）,路径发现过程Route Request1,Tnbm P376 Fig.5-20(b) B和C接收到A的广播信息之后,当B和D接收到A的RREQ广播分组，于是查各自的路由表，首先判断是否重复，然后查找是否有较新的到达目的端的路径信息 如果有，则向源节点回送一个RREP分组 如果没有，则继续广播该RREQ分组，并建立一逆向路由的表项，以备返回的RREP分组途经本节点时使用，同时启动一个定时器（届时如果不是逆向路径的途经节点，则丢弃）,可能的 逆向路径,路径发现过程Route Request2,Tnbm P376 Fig.5-20(c)

38、 C、F和G接收到A的广播信息之后,当B收到D继续广播的A的RREQ分组，经查是重复的，丢弃，当F、G收到A的RREQ分组，经查不是重复的，然后查自己的路由表，假设也都没有较新的到达I的路径信息 所以，F和G也继续广播该RREQ分组，并建立一逆向路由的表项，同时启动一个定时器 C和D收到B继续广播的分组，D丢弃，C的处理与F、G类似,可能的 逆向路径,路径发现过程Route Request3,Tnbm P376 Fig.5-20(d) E、H和I 接收到A的广播信息之后,当E和H收到A的RREQ分组，也同样检查是否重复，再查自己的路由表 E和H的处理与F和G等节点类似，即也继续广播，并建立一逆

39、向路由的表项，同时启动一个定时器等 I 在收到后，由于它是目的节点，所以立即创建一个RREP分组作为应答，其中源、目的地址从RREQ分组中copy，此外根据当前的计数值填写Dest.Seq#、清Hop count为0，并对Lifetime置一适当的初值 该RREP分组是一单播分组,可能的 逆向路径,路径发现过程Route Reply,I 所创建的RREP分组是一个单播的分组，将按逆向路径传送给源节点A 沿途的节点（本例中的G、D）都将免费得到一条到达 I 的路径（如果原来没有到达I的路径则添加，如果有则替代或更新） 非沿途的中间节点（本例中的B、C、E、F和H） ，在定时器TimeOut后，原

40、暂时保留的逆向路径将丢弃,路径发现过程的优化,AODV算法中的RREQ分组采用的是广播方式，所以会产生大量的广播分组 如果将RREQ分组的TTL（Time to Life）限定在一个有限的网络半径之内，将是有效的 如果发送方在生成RREQ分组时，先把TTL设为1，如在合理的时间内没有RREP分组返回，则再生成下一个RREQ分组，并把TTL逐次设为2、3、4 ，将有效地限制广播分组的传输范围,按需路由AODV算法,AODV的请求分组和应答分组 AODV的Path Discovery过程 AODV的路径维护,AODV的路径维护,每个节点都定期广播一个HELLO消息，并期待其邻居节点的应答，如果没有

41、应答，则说明该邻居节点已经不再有效 如果某个邻居节点无效，必须及时更新自己的路由表 如果无效的邻居节点是活动邻居节点，那么还必须检查路由表中与活动邻居节点相关的路径，并通知相关节点（递归） 活动邻居：在最近的T时间内曾经给它发送过到达该目的节点的分组,AODV的路径维护,以节点D的路由表为例,Tnbm P379 Fig.5-23(a) 在G停机之前D的路由表,AODV的路径维护,D发现其邻居节点G已不复存在 根据路由表得知，到目的节点E、G、I的下一跳是节点G，所以在D的路由表中删除目的地址为E、G、I 的表项 同时，D知道节点A和B的某些路径依赖节点G，所以立即通知节点A和B,Tnbm P3

42、79 Fig.5-23(b) 在G停机之后的拓扑图,Ad-Hoc的路由,主动路由 （表驱动）：每个节点都周期性广播路由信息，主动地发现并维护路由表 DSDV（Destination Sequenced Distance Vector） 按需路由 （事件驱动）：只有在需要发送数据时，源站点才寻找路由 AODV （Ad Hoc On-demand Distance Vector） DSR（Dynamic Source Routing）,按需路由DSR算法,DSR（Dynamic Source Routing） DSR也是一种按需（on-demand）的路由协议，是一种基于源路由的按需路由协议，它使

43、用源路由算法，每个节点都有一个Route Cache，记录路由的路径轨迹 当某源节点要发送数据给某一目的节点时，首先查看自己的Route Cache中是否存在现成的路径可以使用（有时甚至保存有多条），如果不存在，则启动Route Discovery过程，即广播一个RREQ请求分组，其中包含目的节点地址、源节点地址、Request ID和一个Route Record（用于按顺序逐个记录此RREQ所途经的节点地址）,DSR的Route Discovery过程1,Route Discovery过程中的Route Request,目的节点,源节点,Route Record中的路径记录,当节点收到Rou

44、te Request时,如果在此之前已收到过同一源节点、同一ID的RREQ（表示这是重复的），则该请求分组丢弃 如果在Route Cache中发现已经有到目的节点的路径（表示自己可提供到达目的节点的路径），则把此路径加入Route Record并创建 RREP应答分组，回复源节点并丢弃该请求分组 如果自己是目的节点，此时Route Record中记录的就是从源节点到目的节点的路径信息，把此路径加入RREP应答分组，回复给源节点，并丢弃该请求分组 否则，代表自己是中间节点，把自己的地址附加在Route Record中，然后再继续广播,DSR的Route Discovery过程2,Route Di

45、scovery过程中的Route Reply 过程,目的节点N8选择的返回源节点N1的一条路径,AODV和DSR算法的比较 1,AODV假设链路是双向的；而DSR支持单向链路，并且DSR是基于源路由的,AODV和DSR都有类似的Route Discovery过程，都有着按需建立路径的特性，都强调是在源节点需要的时候才会去建立到目的地节点的路径，但是两者仍然有相当的差别,在AODV中，目的节点生成的RREP分组是按原路径返回，所以链路必须是双向的，但未必所有的链路都是双向的；在DSR中，目的节点所创建的 RREP分组是单播的，如果链路是双向的，可以按原路径返回，也可以再启动一个Route Dis

46、covery过程，将先前所得到的路径附在新的RREQ分组中，所以DSR支持单向链路,AODV和DSR算法的比较 2,在AODV的路由表中，每个目的节点只有一条路径记录，而在DSR中，采用的是Route Cache，所以对每个目的节点都可能保留有多条路径记录,在AODV中，在处理源节点的RREQ分组时，只处理一笔路径信息，所以目的节点也只回应最先到的RREQ，其余的一律丢弃；在DSR中，因为是使用Route Cache，目的节点会回应所有的RREQ分组，即使是重复的，这就使源节点可以在Route Cache中保留多条到同一目的地的路径，所以当最短路径失效时，可能还有另一个选择，这种机制减少了启动

47、Route Discovery过程的机会，但是回应每一个RREP却也增加了网路流量,AODV和DSR算法的比较 3,在一次Route Discovery 过程中，与AODV相比较， DSR所得到的路径信息更多,DSR是基于源路由的，在RREQ请求分组中，除包含目的节点地址、源节点地址等以外，还包括一个Route Record域，用于按顺序逐个记录所途经的节点地址，所以在完成一次Route Discovery后，源节点可以获得目的节点和所有中间节点的路径信息，每一个中间节点也可以获得到达其他中间节点的路径信息；而AODV得到的路径信息则是有限的，只可得到相邻节点的路径信息，所以可能会造成节点常常

48、启动Route Discovery过程，而使得网路流量增大,AODV和DSR算法的比较 4,路径信息的更新，和由于某个节点失效而导致的路由信息的维护，两者所采用的机制和策略有所不同,在AODV中，路径的时效是由Sequence Number来决定，并根据所得到的消息随时更新，如果过一段时间后此路径没被用过，则将从Routing Table中删除，此外，一旦发现某邻节点失效，发现节点将维护自己的路由表，并根据路由表查看并通知与失效节点相关的路径中所涉及到的节点；在DSR中，则无法判断现有的路径信息是否有效，只有等到Route Error分组返回时，才会把Route Cache中无效的路径信息删除

49、，如果发现某邻节点失效，因为是基于源路由的，所以也只会通知唯一的上游节点，直到源节点为止，而不会通知不在此路径上的其它节点,第5章 网络层,网络层设计的相关问题 路由算法 拥塞控制 服务质量 网络互联 因特网中的网络层,拥塞控制,当通信子网中有太多的分组，导致其性能降低，这种情况叫拥塞 拥塞控制和流量控制的区别 全局性问题和局部性问题 造成拥塞的原因 节点存储容量（缓冲区）不够 处理机速度太低 线路容量（带宽）不够,拥塞示例,当通信量太大时，发生拥塞，性能显著降低,Tnbm P385 Fig. 5-25 吞吐量增大将发生拥塞,拥塞对延迟的影响,拥塞控制原理和一般方法,拥塞控制的基本原理 拥塞预防策略 虚电路子网中的拥塞控制 数据报子网的拥塞控制 载荷脱落 抖动控制,拥塞控制的基本原理,