写点什么

【计算机网络】网络层——路由器与路由选择协议

发布于: 2020 年 07 月 11 日
【计算机网络】网络层——路由器与路由选择协议

转发和路由选择

  在网络中的每一台主机和路由器中都有一个网络层部分。网络层为了将分组从一台发送主机移动到另外一台接收主机,需要两个重要功能:

  • 转发:当一个分组到达路由器的一条输入链路时,路由器必须将该分组移动到适当的输出链路。

  • 路由选择:当分组从发送方流向接收方时,网络层必须决定这些分组所采取的路由或路径。计算这些路径的算法被称为路由选择算法

转发是指将分组从一个输入链路接口转移到适当的输出链路接口的路由器本地动作。路由选择是指网络范围的过程,以决定分组从源到目的地所采取的的端对端路径,是一种宏观上的策略。



每台路由器都有一张转发表。路由器通过检查到达分组首部字段的值来转发分组,然后使用该值在转发表索引查询该分组的输出链路接口。



假设路由器有4条链路,编号0-3,分组以以下方式转发到链路接口:

| 目的地址范围 | 链路接口 |

| - | - |

|11001000 0001011 00010000 00000000 到 11001000 0001011 00010111 11111111 | 0 |

|11001000 0001011 00011000 00000000 到 11001000 0001011 00011000 11111111 | 1 |

|11001000 0001011 00011001 00000000 到 11001000 0001011 00011111 11111111 | 2 |

| 其他 | 3 |



  显然对于这个例子,在路由器的转发表中就没有必要有40亿表项。我们能够用下列转发表:



| 前缀匹配 | 链路接口 |

| - | - |

|11001000 0001011 00010 | 0 |

|11001000 0001011 00011000 | 1 |

|11001000 0001011 00011 | 2 |

| 其他 | 3 |



  使用这种风格的转发表,路由器使用分组的目的地址的前缀与该表中的表项进行匹配,如果存在一个匹配项,则由路由器向匹配的链路接口转发该分组。当有多个匹配时,路由器使用最长前缀匹配规则,在表中寻找最长的匹配项,并向相关联的链路接口转发该分组。

  因为转发表能够在任何时刻修改,从一个端系统到另外一个端系统发送的一系列分组可能在通过网络时走不通的路径,并可能无序到达。



路由器工作原理

  一个路由器有四个组成部分

输入端口

  输入端口执行几项关键功能。它要执行将一条输入的物理链路与路由器相连接的物理层功能。它还要数据链路层功能,如处理协议、拆封数据。它还要完成查找功能,通过查询转发表决定路由器的输出端口。

  转发表是由路由选择处理器计算和更新的,但转发表的一份影子副本通常会被存在每个输入端口。有了影子副本,转发决策能在每个输入端口本地做出,无需调用中央路由选择处理器,因此避免了集中式处理的瓶颈。

  一旦通过查找确定了某分组的输出端口,该分组就能发送至交换结构。在某些设计中,如果有其他输入端口的分组正在使用该交换结构,一个分组基本可能会在进入交换结构时被暂时阻塞。因此,一个被阻塞的分组必须要在输入端口处排队,并等待稍后被及时调度以通过交换结构

交换结构

  交换结构位于一台路由器的核心地位,它将路由器的输入端口与输出端口相连接。交换可以用很多种方式完成。

###### 经内存交换

  最简单、最早的路由器是传统的计算机,交换是在CPU(路由选择处理器)的直接控制下完成的。输入端口与输出端口的功能就像在传统操作系统中的I/O设备一样。当一个分组到达一个输入端口时,该端口会通过终端方式向CPU发出信号,该分组从输入端口处被复制到处理器内存中,CPU从首部中提取出目的地址,在转发表中查找合适的输出端口,并将该分组复制到输出端口的缓存中。不能同时转发两个分组,即使有不同的端口号,因为经过共享系统总线一次仅能执行一个内存读/写

###### 经总线交换

  在这种方法中,输入端口经过一根共享总线将分组直接传送到输出端口,不需要路由选择处理器的干预。输入端口会为分组预先计划一个交换机内部标签(首部),指示本地输出端口。改分组能由所有输出端口收到,但只有与该标签匹配的端口才能保存该分组,然后标签在输出端口被去除,因为其仅用于交换机内部来跨越总线。不能同时转发两个分组,其余分组必须等待,还是因为一次只有一个分组能跨越总线

###### 经互联网络交换

  克服单一、共享式总线带宽限制的一种方式是使用一个更复杂的互联网络。纵横式交换机就是由一种由2N条总线组成的互联网络,它连接N个输入端口与N个输出端口,只要分组来自两个不同的输入端口并且目的输出端口也是不一样的,那么就能并行转发多个分组。

输出端口

  输出端口功能和输入端口类似。当一条链路是双向的(即承载两个方向上的流量)时,输出端口通常是与该链路的输入端口在同一线路卡上成对出现的。

路由选择处理器

  用于执行路由选择协议,维护路由选择表及其连接的链路状态信息,并为路由器计算转发表。它还执行网络管理功能。



IPv4报格式

  首先讨论其数据报格式:



  • 版本:4比特,规定了IP协议版本,IPv4将值设为4

  • 首部长度:因为包含了一些可变数量的选项字段。所以需要4比特来确定IP数据报中数据部分实际从哪开始。大部分IP数据报不包含选项,所以一般的IP数据报具有20字节的首部。

  • 数据报长度:IP数据报的总长度(首部加上数据)。因为该字段长16比特,所以IP数据报的理论最大长度为65535字节,然而很少有超过1500字节的。

  • 标识、标志、片偏移:这三个字段与所谓的IP分片有关,而IPv6不允许分片

  • 寿命:即TTL,确保数据报不会永远在网络中循环。每当数据报由一个路由器处理时,该字段值减一,若减为0,该数据报必须被丢弃

  • 上层协议:该字段仅在一个IP数据报到达其最终目的地才会有用,该字段指示了IP数据报的数据部分应该交付给哪个特定的运输层协议。例如,值为6表明数据部分交给 TCP,值为17表明交给 UDP,也可以交给ICMP。



IPv4编址

  主机与物理链路之间的边界叫做接口,路由器与它的任意一条链路直接的边界也叫接口。一台路由器有多个接口,每个接口有其链路。IP要求每台主机和路由器接口拥有自己的IP地址。因此,一个IP地址技术上是与一个接口相关联的,而不是与包括该接口的主机或路由器相关联的,一个路由器有多少个接口,就有多少个IP

  每个IP地址长度为32比特。在全球因特网中每台主机和路由器上的每个接口都必须有一个全球唯一的IP地址(NAT的接口除外)。

无类别域间路由策略(CIDR)

  因特网的地址分类策略被称为无类别域间路由策略(CIDR)。CIDR将子网寻址的概念一般化了,32比特的IP地址被划分为两部分,网络地址和主机地址。如 a.b.c.d/x,其中 x 指示了地址的第一部分中的比特数,/x 记法,有时候也叫子网掩码。形式为 a.b.c.d/x 的地址的 x 最高比特构成了IP地址的网络部分,并且经常被称为该地址的前缀。一个组织通常被分配一块连续的内存,即具有相同前缀的一段地址。网络地址相同的IP属于同一个网段。



  这是一个ISP将8个组织连接到因特网的例子。该ISP向往通告,它接收所有地址的前20比特与200.23.16.0/20相符的数据报。外接的其它部分不需要知道在地址块200.23.16.0/20内实际还存在8个其它组织,每个组织有自己的子网。这种使用单个网络前缀通告多个网络的能力通常被称为地址聚合,也称为路由聚合或路由摘要。





  在CIDR被采用之前,IP地址的网络部分长度被限制为8、16或24比特,这种被称为分类编址

  • 第一位为0的是A类地址,其网络地址长度为8,第一字节的范围是0-127

  • 前两位为10的是B类地址,其网络地址长度为16,第一字节的范围是128-191

  • 前三位为110的是C类地址,其网络地址长度为24,第一字节的范围是192-223

  • 前四位为1110的是D类地址,其网络地址长度为32,第一字节的范围是224-239,D类地址用于多播使用

  • 前四位是1111的为E类地址,保留未用。

由此可以看出这种分类编址的缺点的,网络部分的长度被限制为8、16或24比特,要么网络号太少,要么主机号太少,不够自由灵活,利用率也非常低下。



DHCP

  为了获取一个一块IP地址用于一个组织的子网,某网络管理员也许首先会与他的ISP联系,该ISP可能会从已分配给它的更大地址块中提供一些地址。如果ISP需要得到一块IP地址,他需要向因特网名字和编号分配机构(ICANN) 申请。

  一旦某组织获得了一块IP地址,它就可以为本组织内的主机和路由器逐个分配IP地址。能手工配置路由器的IP地址,但更多的是使用动态主机配置协议(DHCP),允许主机自动获取一个IP地址。

DHCP分为下面几个步骤

  1. 一台新加入的主机客户首先要发现一个DHCP服务器,并获取一个IP地址。客户在UDP分组中向端口67发送一个DHCP发送报文,目的是广播地址 255.255.255.255,源地址是 0.0.0.0。因为它不知道 DHCP服务器在哪,因此只能广播。

  2. DHCP服务器收到一个DHCP发送报文时,用一个DHCP提供报文做出响应,该报文含有IP地址、子网掩码、租用期等信息。其目的仍是广播地址 255.255.255.255。一个子网中可能有多个DHCP服务器都收到了DHCP发送报文并回复DHCP提供报文。

  3. 客户从一个或多个DHCP提供报文中选择一个最优的,并向选中的服务发送一个DHCP请求报文进行响应,回显配置参数。

4.DHCP服务器回复DHCP ACK报文,证实所需参数。

5.客户收到DHCP ACK 报文,交互完成。



网络地址转换(NAT)

  有一些地址叫私有网段地址,这些地域是指仅对该网络中的设备有意义的网络。这样的地址空间有三个:10.0.0.0/8(一个A类地址)、172.16.0.0/12(16个连续B类地址)、192.168.0.0/16(256个连续C类地址)。这些地址你都可以任意分配而不会干扰到因特网的正常运行,但如果使用这些地址的终端想和网关外的主机通信,必须使用NAT。



  NAT路由器对外界的行为就如同一个具有单一IP地址的单一设备。所有离开家庭路由器流向因特网的报文都拥有一个源IP地址,即NAT路由器通向因特网的接口地址,所有流向家庭的报文的目的IP地址也是这个。从本质上讲,NAT能使路由器对外隐藏家庭网络的细节。



  NAT路由器维护了一张NAT转换表。当家庭网络向外发送报文时,NAT会修改器源地址为NAT路由器的出口地址,修改其源端口为一个NAT中未使用的端口号。当收到一个来自其他路由器的报文时,也会根据转换表修改其目的地址。



因特网控制报文协议(ICMP)

   ICMP被主机和路由器用来彼此沟通网络层的信息。ICMP通常被认为是IP的一部分,但从结构体系上讲它是位于IP之上的,因为ICMP报文时作为IP有效载荷承载的。

|ICMP类型|编码|描述|

|-|-|-|

| 0|0|回显回答(对ping的回答) |

| 3| 0|目的网络不可达 |

| 3|1 | 目的主机不可达|

| 3|2 |目的协议不可达 |

| 3|3 |目的端口不可达 |

| 3| 6|目的网络未知 |

| 3| 7| 目的主机未知|

| 4|0 |源抑制(拥塞控制) |

| 8| 0| 回显请求|

| 9|0 |路由器通告 |

|10 |0 |路由器发现 |

|11 | 0|TTL过期 |

|12 |0 |IP首部损坏 |

  众所周知的ping程序发送一个ICMP类型8编码0的报文到指定主机,目的主机发回一个类型0编码0的ICMP回显回答。



IPv6

  再来看下IPv6的数据报格式

  • 版本:4比特,IPv6将该值设为6

  • 流量类型:类似于IPv4的服务类型

  • 流标签:20比特,用于标识一条数据报的流

  • 有效载荷长度:16比特,给出了IPv6数据报中跟在定长的40字节数据报首部后面的字节数量。

  • 下一个首部:标识数据报中的内容需要交付给哪个协议,如TCP、UDP、ICMP。

  • 跳限制:转发数据报的每台路由器对该字段的内容减1,计数到达0时,丢弃该报文段。



IPv6的变化

不难看出IPv6有以下变化:

  1. 扩大的地址容量。IP地址由32比特扩大到128比特,将取之不尽用之不竭。

  2. 简化高效的40字节首部。40字节定长首部允许更快地处理IP数据报

  3. 不再允许分片/重新组装。如果收到的IPv6数据报过大而不能转发出链路的话,路由器丢弃该数据,并返回一个“分组太大”的ICMP报文。

  4. 取消首部校验和。运输层(TCP、UDP)与数据链路层协议执行了这项操作,IP设计者大概觉得在网络层也有该功能实属多余,所以也去掉了。IPv4首部中包含一个TTL字段(类似于跳限制字段),因此,每台路由器都要重新计算IPv4首部校验和,这在IPv4中是一件耗时的操作。

  5. 选项。不再是标准IP首部的一部分了,但它并没有消失,可能出现在下一个首部指出的位置上。



IPv4 到 IPv6的迁移

  基于IPv4的公共因特网如何迁移到IPv6呢?有两种方式。

  双栈:使用该方法的IPv6结点还需要具有完整的IPv4实现,它有发送两种数据报的能力。当与IPv4结点互操作时,IPv6/IPv4结点可以使用IPv4数据报,当与IPv6结点互操作时,它又能使用IPv6.IPv6/IPv4结点必须具有IPv4余IPv6两种地址。然而,在执行IPv6到IPv4的转换时,IPv6中一些特定的字段将丢失。

  建隧道:如果两个IPv6结点要使用IPv6数据报交互,但它们是经由中间IPv4路由器互联的。我们将两台IPv6路由器之间的中间IPv4路由器的集合称为一个隧道。在隧道发送端的IPv6结点可将整个IPv6数据报放到一个IPv4数据报的数据(有效载荷)字段中,再发给隧道的第一个IPv4结点。隧道中的IPv4路由器为该数据报提供路由,像对待其他数据报一样,根本不知道该IPv4数据报本身就含有一个完整的IPv6数据报。隧道接收端的IPv6结点最终收到该IPv4数据报,并确认其数据报含有一个IPv6数据报,于是从中取出IPv6数据报,然后再为该IPv6数据报提供路由。



路由选择算法

  主机通常直接与一台路由器相连,该路由器即为主机的默认路由器,又称为该主机的第一跳路由器。我们将源主机的默认路由器称作源路由器,把目的主机的默认路由器称作目的路由器。路由选择问题可归结为从源路由器到目的路由器的选择问题。对路由选择算法的一种广义分类方式是根据该算法是全局式的还是分散式的来加以区分。

  • 全局式路由选择算法用完整的、全局性的网络知识计算出从源到目的地之间的对地费用路径。该算法以所有结点的连通性及所有链路的费用为输入,这就要求该算法在真正开始计算之前,要以某种方式获取这些信息。实践中,该算法常备称作链路状态(LS)算法

  • 分散式路由选择算法以迭代、分布式的计算方式计算出最低费用路径。没有结点拥有关于所有网络链路费用的完整信息,每个结点仅与其直接相连链路的费用知识即可开始工作,然后通过迭代计算过程并与相邻结点交换信息,一个结点逐渐计算出到达某个结点或一组目的结点的最低费用路径。



链路状态路由选择算法(LS算法)

  链路算法中,网络拓扑和所有的链路费用都是已知的。这其实就是最短路径问题,有两个常用的算法,分别是 Dijkstra算法、Prim算法。当LS算法终止时,对于每一个结点,我们都得到从源结点到其它任何结点的最低费用的路径。



距离向量路由选择算法(DV算法)

  DV算法是一种分散式的路由选择算法。该算法会涉及到著名的Bellman-Ford方程:

>$d_x(y)$是结点x到结点y的最低费用路径的费用,$c(x,v)$表示结点x和y之间的费用

那么 $dx(y) = minv\{c(x,v) + d_v(y)\}$



  DV的思想如下。令$Dx=[dx(y) : y ∈ N]$,N是结点的集合,该向量是x到在N中的所有其它结点y的费用估计向量。使用DV算法,每个结点维护下列路由选择信息:

  • 对于每一个邻居v,从x到直接相连邻居v的费用为$c(x,v)$。

  • 结点x的距离向量,即$Dx=[dx(y) : y ∈ N]$,包括了x到N中所有目的地y的费用的估计值。

  • 它的每个邻居的距离向量,即对x的每个邻居v,有$Dv=[dv(y) : y ∈ N]$。



  在该分布式、异步算法中,每个结点不时地向它的每个邻居发送它的距离向量副本。当结点x从它的任何一个邻居v接收到一个新距离向量,他保存v的距离向量,然后使用Bellman-Ford方程来更新自己的距离向量:

$dx(y) = minv\{c(x,v) + d_v(y)\}$

  如果结点x的距离向量因为这个更新步骤而改变,结点x接下来将向它的每个邻居发送其更新后的距离向量。



###### 链路费用改变:无穷计数问题

  当某条链路费用增加时可能会出现问题,如下图所示,在链路费用变化之前,$dy(x) = 4,dy(z) = 1,d_z(x) = 5$。

  1. 在某时刻,x与y之间的路径费用变为60,y重新计算到x的的最低费用值为$dy(x) = min\{c(y,x) + dx(x) , c(y,z)+d_z(x)\} = min \{ 60+0, 1+5\} = 6$。当然以我们的上帝视角来看这当然是错误的,y不知道z到x的最低费用是经过y自己本身的,这就遇到了路由选择环路问题

  2. y结点算出了到x的新的最低费用,它将该新距离向量通知给z。

  3. z收到来自y的心的距离向量,它指示了y到x的新最低费用是6,于是z也更新自己到x的最低费用为$dz(x) = min\{c(z,y) + dy(x) , c(x,z)+d_z(z)\} = min \{ 1+6, 50+0\} = 7$,并通知y其到x的新费用。

  4. y收到z的新距离向量后,更新自己到x的费用为8并通知z其新距离向量。

  5. 就这样,y和z不停地反复通知,知道z最终算出它经由y的路径费用大于50为止,此时z确定它到x的最低费用路径是经过它到x的直接相连。这种情况,有时被称为无穷计数问题。



  当遇到这种问题的时候,可以通过一种称为毒性逆转的技术而加以避免。其思想较为简单,当z通过y路由选择到达目的地x,则z将通告y。它(z)到x的距离是无穷大,即z向y顺便通告$dz(x)=∞$,即使z知道$dz(x)=5$。因此,y会相信z没有到x的路径,y将永远不会试图经过z路由选择到x。

  但毒性逆转并没有解决一般性的无穷计数问题,涉及到三个或更多结点的环路将无法用毒性逆转计数检测到。



层次路由选择——自治系统(AS)

  在LS和DV算法中,我们将所有因特网中的路由器看做一个整体,但在实践中很难执行下去,至少有以下两个原因:

  • 规模。随着路由器的数目变的很大,涉及路由选择信息的计算、存储及通信(例如LS更新或最低费用路径的变化)的开销将高得不可实现。LS算法将无法存储所有路由器链路的费用,且路由器广播LS更新所需的开销将导致没有剩余的带宽来发送数据。在如此大量的路由器中迭代的距离向量算法将永远无法收敛。

  • 管理自治。如某公司要求按照自己的意愿运行路由器(如选择某种路由选择算法),或对外隐藏其网络的内部组织面貌。在理想情况下,一个组织应当能够按照自己的愿望运行和管理其网络,还要能将其网络与其它外部网络相连接。

  这两个问题都可以通过将路由器组织进自治系统(Autonomous System,AS)来解决,每个AS由一组通常处在相同管理控制下的路由器组成,如ISP或公司网络。在相同的AS中的路由器全部运行相同的路由选择算法,在一个AS内运行的路由选择算法叫做自治系统内部路由选择协议。由于将AS彼此互联是必需的,因此在一个AS内的一台或多台路由器将有另外的任务,即负责向在本AS之外的目的地转发分组,这些路由器被称为网关路由器。每个AS都需要知道经过相邻的AS可以到达哪些目的地,并要向本AS内的路由器传播这些可达性信息,这两项功能由自治系统间路由选择协议处理。



  在上图中,假设AS1通过AS间路由选择协议知道了子网 x 从AS3可达,而从AS2不可达。AS1则向它的所有路由器传播这个信息。当路由器1d知道从AS3并因此可以从1c到达子网 x 时,它进而确定该路由器接口 I 位于从1d到达网关路由器1c的最低费用路径上,并将表项(x, *I*)放入其转发表中。

  还是在上图中,假设AS2和AS3与其它AS相连,这些AS并没有在该图上显示出来。假设AS1通过AS间路由选择协议知道了子网 x 是可达的:经1b到达AS2,或经1c到达AS3,那么 1d 需要选择通过哪个网关路由器来到达子网 x。实践中常用的方法是热土豆路由选择,AS尽可能快地(经济地)扔掉分组,1d会在1b和1c中选择具有最低费用的网关。



因特网中的路由选择

  AS内部路由选择协议用于确定在一个AS内执行路由选择的方式。AS内部路由选择协议又称为内部网关协议。历史上有两个广泛使用的内部网关协议:路由选择信息协议(Routing Information Protocol,RIP)与*开放最短路优先(Open Shortest Path First, OSPF)*。

因特网自治系统内部路由选择协议:RIP

  RIP是一种距离向量协议,类似于DV协议。RFC 1058定义的RIP使用跳数作为费用测度,即每条链路的费用都为1。且一条链路的最大费用被限制为15,因此RIP的使用限制在网络直径不超过15跳的自治系统内。

  相邻路由器之间使用RIP响应报文来更新路由选择数据。每台路由器维护一张称为路由选择表的RIP表,包括该路由器的距离向量和转发表。



下表是上图中路由器D的原本的RIP表:



|目的子网|下一台路由器|到目的地的跳数|

|-|-|-|

|w|A|2|

|y|B|2|

|z|B|7|

|x|-|1|

|...|...|...|



假设某一时刻收到了来自A的路由器RIP通告:



|目的子网|下一台路由器|到目的地的跳数|

|-|-|-|

|z|C|4|

|w|-|1|

|x|-|1|

|...|...|...|



那么,路由器D将会合并上面两张表,更新最短路径:



|目的子网|下一台路由器|到目的地的跳数|

|-|-|-|

|w|A|2|

|y|B|2|

|z|B|5|

|x|-|1|

|...|...|...|



  RIP路由器大约每30s交换一次通告,如果一台路由器超过180s没有从邻居和收到报文,要么邻居死机了,要么链路中断了。此时RIP修改本地路由选择表,然后向相邻可达路由器发送通告来传播该信息。



因特网自治系统内部路由选择协议:OSPF

  OSPF被设想是RIP的后继者,它有许多先进特性。它的核心就是一个使用洪泛链路状态信息的链路状态协议和一个Dijkstra最小路径算法。使用OSPF,一台路由器构建了一幅关于整个自治系统的完整拓扑图,各条链路费用由网络管理员配置的,也许会将所有费用设为1,从而实现最小跳数路由选择,也许会选择将链路权值与链路容量成反比来设置,从而不鼓励流量使用低带宽链路。

  使用OSPF时,路由器向AS内的所有其它路由器广播路由选择信息,而不仅仅是向相邻路由器广播。每当一条链路的状态发生变化时,路由器就会广播链路状态信息。即使链路状态未发生改变,它也要周期性(至少每隔30分钟)地广播链路状态。

  OSPF是一个相当复杂的协议,这里所说的都是十分肤浅的。



自治系统间的路由选择:BGP

  边界网关协议(Broder Gateway Protocol,BGP)版本4是当今因特网中AS间路由选择协议事实上的标准,也通常被称为BGP4。BGP为每个AS提供了进行以下工作的手段:

  1. 从相邻AS获得子网可达性信息。

  2. 向本AS内部的所有路由器传播这些可达性信息。

  3. 基于可达性信息和AS策略,决定到达子网的“好”路由。

  BGP使得每个AS知道经过其相邻AS可达哪些目的地。在BGP中,目的地不是主机而是CDIR化的前缀,每个前缀表示一个子网或一些子网的集合(路由聚合)。

  因为BGP是因特网中绝对至关重要的协议,即从本质上讲,正是这个协议将所有的东西粘合在一起了。



广播和多播路由选择

  以上讨论的都是支持单播(即点对点)通信的路由选择协议,单个源结点向单个目的结点发送分组。在广播路由选择中,网络层提供了从一个源结点到网络中的所有其它结点交付分组的服务。多播路由选择使单个源结点能香其它网络结点的一个子集发送分组的副本。



广播路由算法

###### N次单播

  广播的一种实现方式是用N次单播,一个缺点是效率低,二是N次单播需要知道广播的所有接收方及其地址,很难得到这些信息。

###### 无控制洪泛

  实现广播最简单的技术是洪泛方法,该方法要求源结点向它的所有邻居发送分组的副本。当某个节点接收到一个分组广播时,它复制该分组并向它的所有邻居(除了从其接收该分组的邻居)转发之。缺点也显而易见,如果一些结点都与两个以上结点相连,产生的广播风暴会无休止的广播分组的复制,最终使网络变得无用。

###### 受控洪泛

  避免广播风暴的关键是每个结点明智地选择何时洪泛分组,何时不洪泛分组。实践中,能够用以下方式实现。

  序号控制泛洪中,源结点将其地址(或其他唯一标识符)以及广播序号放入广播分组,再向它的所有邻居发送该分组。每个结点维护它已收到、复制和转发的源地址和分组的广播序号。当结点收到一个广播分组时,会先检查该分组是否已在列表里,在就丢弃,否则就洪泛该分组。

  反向路径转发(RPF),也称反向路径广播(RPB),其思想很简单,当一台路由器收到具有给定源地址的广播分组时,仅当该分组到达的链路正好是位于它自己的返回其源的最短单播路径上,它才向所有其它链路转发分组。缺点是,例如路由器A需要广播,那么要先生成各个接收方到A的最低费用路径,依照这个路径传播。如果B也需要广播,那么也需要重新生成一个最低路径,不能复用。

###### 生成树广播

  这是比较优秀的方案,只需在图中生成一棵费用最少的最小生成树。生成树不仅消除了冗余的广播分组,一旦合适,该生成树能被任何结点用于开始广播分组,这是反向路径转发做不到的。另外一个结点不需要知道整棵树,只需要知道哪些邻居是生成树的邻居即可。



多播

  使用多播服务,多播分组仅被交付给网络结点的一个子集。多播数据报使用间接地址来编址,就是用一个标识来表示一组接收方,这种表示一组接收方的单一地址就是一个D类多播地址。与一个D类地址相关联的接收方小组被称为一个多播组。 网络层多播是由两个互补的组件构成:IGMP与多播路由选择协议。



###### 因特网组管理协议

  IGMP版本3运行在一台主机与其第一跳路由器之间。IGMP为一台主机提供了手段,让它通知第一跳路由器:在本机上的运行的一个应用程序想加入一个特定的多播组。



###### 多播路由选择算法

  多播路由选择的目标就是发现一棵链路的树,这些链路连接了所有具有属于该多播组的相连主机的路由器。

  实践中,通常采用两种方法来去淡定多播路由选择树:



  • 使用一棵共享树的多播路由选择。所有源共享一棵多播树,该树包括了所有具有该多播子的相连主机的边缘路由器。

  • 使用一棵基于源的树的多播路由选择。为多播组的每个源构建一棵多播路由选择树,实践中使用RPF算法。



发布于: 2020 年 07 月 11 日阅读数: 65
用户头像

后端工程师 2019.03.20 加入

欢迎大家来交流。

评论

发布
暂无评论
【计算机网络】网络层——路由器与路由选择协议