计算机网络自顶向下：第四章-网络层

发表于 | 分类于 | 阅读次数:

网络层

概述

转发和选路

网络层的主要功能是什么？

  • 转发：当分组到达路由器时，如何将分组转发出去。
  • 路由：计算分组从发送端到接口端最合适的路径。

选路/转发

选路算法决定了转发表中的表项

转发分组的设备叫做分组交换机，分为两种：

  1. 链路层分组交换机：从输入链路接口道输出链路接口
  2. 网络层分组交换机（路由）

除了转发和路由，网络层也有建立连接的功能。

网络服务模型

网络层可以提供的服务有哪些？

  • 确保交付：确保分组到达目的地
  • 具有时延上界的确保交付：确保分组的到达将在一定的时间内
  • 有序：确保按发送的顺序到达目的地
  • 最小带宽：确保分组的传输在一定的带宽内
  • 最大时延抖动：确保发送两个连续分组的间隔和接受两个连续分组的间隔在一定的变化范围内
  • 安全性：使用只有源和主机知道的密钥

不同的网络体系会提供不同的网络服务：

Intelnet的网络提供最小服务（也叫做尽力而为的服务），也有其他网络：

不同的网络体系

虚电路和数据报电路

和传输层一样，网络层也提供有连接服务（虚电路）和无连接服务（数据报）
Intelnet是数据报网络

和传输层的连接有什么区别？

  1. 传输层是向应用层提供进程到进程的服务，网络层是向传输层提供主机到主机的服务。
  2. 网络层除了在端系统中实现，也再网络核心的路由器中实现。

虚电路网络

虚电路的组成:

  1. 源和目的之间的路径
  2. VC号：路径上的每段链路的一个标识，在每次虚电路建立连接的时候分配。
  3. 路由器中的转发表，在每次虚电路建立连接的时候生成。分组的首部会携带VC号，每次进过一个路由器，就会去查表并且更新为下一个链路的VC号。

虚电路转发表

为什么同一个连接路径上的每个链路维护不同的VC号？维护同一个不行么？

如果是同一个VC号，必然要求所有路由之间的信息交换更频繁，以避免出现重复的VC号，这样加大的维护的成本，并且必然使得VC号的长度大大增加。

虚电路工作过程：

虚电路建立

  1. 虚电路建立阶段：计算分组转发的路径，确定链路VC号，增加路由表项，预留虚电路上的资源。
  2. 数据传输阶段
  3. 虚电路拆除阶段

虚电路中传递的报文称为信令报文，用来交换这些报文的协议称为信令协议。

数据报网络

数据报网络

数据报网络在报文发出前给报文加上目的的IP地址，之后就再也不维护任何的状态信息。
每个路由器都有一个将分组输出的路由表，确定从哪一个链路发出。

在理想的情况下，所有的路由器都有一份所有精确IP地址的转发表，可能是万亿级别的，显然这是不可能的。

如何缩小转发表存储IP的量？

考虑到IP地址的位数是有限的（32,64,128），因此可以采用前缀风格（范围）的转发方式，逐层定位到精确IP。

前缀风格

当有一个IP匹配到转发表中的两个前缀时，采用最长前缀匹配规则。

虚电路的转发表在建立连接的时候（连接建立阶段会计算转发路径）生成，那对于无连接的数据报网络，转发表如何生成？

根据网络层的选路协议和选路算法，后面会讲到。
数据报网络的转发表可以在任意时间变化，所有分组很难以有序到达。

虚电路和数据报电路的由来

虚电路来源于电话
数据网来源于终端

路由器工作原理

路由器实现了网络层的转发功能

路由器的体系结构

路由器的体系结构：

  • 输入端口：执行物理层功能，链路层功能，和查表转发到正确的输出端口的功能。
  • 交换结构：路由器中的网络，将分组从输出端口转发到输出端口。
  • 输出端口：执行输入端口相反的操作。
  • 选路处理器：执行选路协议，维护选路信息和转发表。

输入端口

输入端口

在哪儿查表？

  • 转发表由选路处理器计算出，但通常转发表都会拷贝一份存放到输出端口中，这样就无须每次都转发到选路处理器，避免了单点瓶颈。
  • 在一些特殊的情况下（比如工作站/服务器作为路由器），这时候由于输入端口处理能力有限，无法保存路由表，这时候输入端口就会把分组转发给选路处理器

查表的效率？

希望输入端口的处理性能达到线路速度，即执行一次查找的时间应少于从输入端口接口一个分组的时间

  • 线性查找是不可能的
  • 二分查找可以在32步之内完成，可这依然不够快
  • 内容可寻址内存和高速缓存等等更多的技术

得到输出端口的分组将会进入交换结构。

交换结构

功能是把分组从输入端口转发到输出端口

交换结构

三种交换的技术是：经内存交换，经一根总线交换，经一个互联网交换（2n条总线）。

输出端口

输出端口

何时出现排队

排队的影响是可能会出现丢包

何时会出现排队现象？

考虑一般情况：假设N个输入端，N个输出端，交换结构的速率是输入线路速度的N倍。
这种情况下，输入端口是不会出现排队现象的，但是在输出端口，当N个分组都到达同一个输出端口，就会有排队现象：如下图：

输出端口排队

合适的处理排队方式？

  1. 足够的缓存：经验表明，缓存长度B = RTT * C（链路容量）
  2. 适当的分组调度程序：先来先到、加权公平排队（WFQ）
  3. 适当丢包策略：主動隊列管理，随机早期检查

如果交换结构不是足够快，则在输入端口也会出现分组排队

网络协议：Inetrnet中的转发和编址

Inetrnet分为三个部分：

  1. IP协议：约定了数据报格式，编址的规则，分组转发规则。
  2. 选路组件：选路算法，决定转发表
  3. ICMP数据报错误和信息报告协议

Intelnet组成

本节讨论IP协议：Inetrnet数据交流的格式net是如何进行数据交流、编址以及转发的。

Inetrnet数据交流的格式？

也成为数据报格式，如图：

IP数据报格式

  • 版本号：决定如何解析剩余部分
  • 首部长度：决定实际的数据部分从哪里开始
  • 服务类型TOS：好像没什么用
  • 数据报长度：首部+数据长度
  • 标识号，标志，偏移量：和IP分片相关（稍后会讨论）
  • 寿命TTL(Time To Life)：每经过一个路由器-1,TTL=0就会被丢弃。
  • 协议：指明封装了哪一种传输层协议，是和传输层进行交流的一个方式。
  • 首部校验和：用于校验IP数据报中的比特错误。
  • 源和目的IP地址：指明发送端和接收端
  • 选项：扩展
  • 有效数据

IP分片是什么东西?

受不同的链路层协议上链路的数据帧最大数据量不同（最大传输单元）的影响，一个较大的IP数据报，必不可完整的经多个不同的链路进行传输，为了解决这个问题，就有了IP分片的技术。
IP分片可以理解为将一个较大的数据报，分成多个较小的数据报片进行传输。

如何分片？又如何整合？

网络层的每个路由都有分片功能
但是重组的功能被放到端系统中，因为重组是一个稍复杂的功能，这样做是为了保持网络内核内核简单的原则。

这就是IP报中标识号，标志和偏移量的作用
标识号：结合IP地址确定唯一的数据报
标志：最后一个片被置为0，其余置为1，作用是用来判断是否有片丢失
偏移量：指定片应放在IP数据报的哪个位置

IP分片和重组

IP分片表

IPV4编址

一个IP的映射是主机或者路由吗？

不是，一个IP对应的是一个接口。
所谓接口就是主机/路由器和物理链路的一个接入点
因此，一个路由器可以拥有多个接口，也就是说可以拥有多个IP地址。
而主机往往一般只有一个接口接入到网络中

什么是子网和子网掩码？

子网是描述接口的集合：处于同一个网中，不经过任何路由器或主机而相连的接口集合，叫做子网
子网所具有的共通的前缀，称为子网掩码

子网掩码的意义是什么？

之前说过，为了减少路由器转发表的负担，转发表中都会使用前缀风格的形式。
越靠近网络核心部分的路由器，前缀所表示的范围就越大。
而相同子网掩码往往意味着同一个组织
当组织之外的路由器转发到组织内的数据报，仅需要考虑子网掩码即可
这样处理的意义也是为了减少转发表的负担

这些IP地址是如何被网络分配的？

  1. 获取子网网段：向IP管理单位申请获得IP子网网段，入组织可以向ISP（电信，联通）申请获取子网网段，而ISP则是向全球性的权威机构ICANN申请获取IP地网段。
  2. 在子网中获取主机IP地址——动态主机配置协议（DHCP）：自动的给接入分配IP

DHCP如何实现自动分配？

DHCP是一个客户端/服务器协议
一般情况下，每个子网都拥有一个DHCP服务器，如果没有，则需要一个DHCP中继代理（通常是一台路由器）

DHCP

DHCP使用UDP报文
DCHP的4步：

  1. DHCP服务发现：发送DHCP发现报文，使用广播的方式试图请求到附近的DHCP服务器，
  2. DHCP服务提供：DHCP接受到发现报文，回复提供报文，同样使用广播的方式向客户机提供IP地址。
  3. DHCP请求：客户端从来自多个DCHP服务器的提供报文中选择一个IP地址，并使用DHCP请求报文对选中的服务器进行相应。
  4. DHCP ACK：服务器使用DHCP ACK报文进行回应

DHCP的问题是：每到一个新的子网，就会获得一个新的IP，因此也就无法维持连接。

移动IP是一种解决方案

子网拓展的问题？

如果组织已向ISP申请了一个子网网段，随着组织规模的增大，很有可能子网网段不够用，怎么办？
继续向ISP申请总有一天会迎来IPV4地址的枯竭
这时候就使用网络地址转换（Nerwork Address Translation, NAT）

NAT具体的工作原理？

本质上就是组织内多个主机共享同一个IP，而主机之间采用独立的IP来区分。
这些IP可以使用私有地址:
如192.168.0.0 到192.168.255.255;
172.16.0.0到172.31.255.255;
10.0.0.0到10.255.255.255

NAT路由器作为连接内网和外网的一个节点，一端接口连接外网，一端接口连接内网。
数据分组在NAT中会被替换IP和端口，也就是说，NAT路由器会处理传输层的数据。
NAT路由器从ISP的DHCP服务器获取地址，然后它本身再运行一个DHCP服务，为NAT-DHCP路由器控制的组织网络分配地址

DHCP

外网数据报文如何定位内网主机？

NAT维护一张转发表：
NAT路由器的端口号—映射—内网主机IP+端口号

传统的NAT映射只包括内网IP，不包括内网端口，这样会导致连接是单向的，也就是说只能从内网向外网发起连接，无法从外网向内网发起连接

NAT技术招到各界反对，原因是：

  1. 端口号应该面对进程，而不是面对主机
  2. 路由器应当只处理第三层的分组（比如不应该修改端口号）
  3. 应该使用IPV6来解决IP地址短缺的问题

NAT根据外网访问内网的权限又分成几种类型，可自行百度

ICMP:互联网控制报文协议

本节的主题是Internet的第二个主要组件

ICMP是什么？有什么用？

之前说过，IP数据报是网络层中主机和路由器、路由器和路由器之间交流的一种方式。
但是，IP数据报携带的有效数据一定是UDP、TCP段吗？显然不是
网络层中还有一种特殊的交流数据报，不携带来自传输层的数据，称为ICMP报文。
ICMP协议作为网络层协议，具有传输层无关的交流方式。
常用的ICMP功能是错误反馈，除此之外也具有很多其他的功能。比如ping，Traceroute（路由跟踪）。

ICMP交流的语言定义是什么？

ICMP中有类型和编码两个字段，可以表明这个ICMP报文说的是什么东西：

ICMP协议类型

案例：

  • ping程序：发送一个类型8编码0的ICMP报文到指定主机，主机接受到该回显请求报文，回复类型0编码0的回显回答ICMP报文
  • traceroute程序：源主机不断发送的IP数据报，每个数据报都携带了不可达的UDP数据段，这些IP数据报配置的TTL依次递增，比如第一个数据报TTL为1，第二个数据报TTL为2…当路由器接受到一个TTL为0的数据报，会丢弃该数据报兵发送一个ICMP报警报文给源主机（类型11编码0）。当目的主机接收到不可达的UDP报文，会返回一个端口不可达的ICMP报文。源主机接收到这个报文就会停止发送数据报。

IPV6

IPV4地址面临枯竭
IP设计者设计IPV6，对IPV4进行空间和功能的扩展。

数据报格式：

IPV6报文格式

  • 版本号： 同IPV4一样，表示如何解析数据报
  • 流量类型（traffic class）：和IPV4中的TOS一样
  • 流标签：给需要特殊服务的报文进行标签
  • 有效负载长度：有效数据的长度
  • 下一个首部：作用和IPV4中的协议字段相同。标识数据中的内容采用哪种协议。
  • 跳限制：类型TTL
  • 源和目的地址
  • 有效数据

和V4相比，有哪些变化？

  1. 更大的地址容量：由32位变为128位
  2. 简单高效的40字节首部：去掉了IPV4中可变的选项字段，实现40字节定长。选项采取更灵活的方式实现
  3. 流标签和优先级（flow label）：给需要特殊服务的报文进行标签

V4中不存在的字段在V6中如何实现？

  1. 标识号，标志，偏移量：不在进行分片操作，若“分组太大”，通过ICMP错误报文来让发送方重发长度更小的IP数据报。
  2. 首部校验和：校验在链路层和传输层都有，因此去掉进一步精简网络层服务
  3. 选项：“选项”可以也可以由下一个首部字段指出。

    ICMPV6针对IPV6增加了新的类型和编码：如“分组太大”和“未识别的IPV6选项”

有一个问题：配置IPV6的系统既可以处理IPV6，也可以处理IPV4。但是只配置了IPV4的系统，如何处理IPV6呢？

如何从IPV4迁移到IPV6？

  1. 宣布一个标志日，将所有机器都关机，从IPV4升级到IPV6，显然，这不现实。

  2. 双栈：配置了IPV6的系统在与IPV4交流的时候只发送IPV4，通过DNS来判断另一个节点是否支持IPV6。双栈的方式会把IPV6中的有效数据放到IPV4中进行发送，但是这样会丢失IPV6中的额外信息，如流标签和优先级，并且再无法找回。

双栈

  1. 另一种双栈——建隧道：建隧道的方式会把整个IPV6中的数据放到IPV4中进行发送，这样信息就不会丢失了。

建隧道

IP安全性概述

IPsec协议防止IP报文被截取、修改或者被伪装，提供了如下的服务：

  1. 密码技术协约：让两台主机加密算法和密钥一致
  2. 对IP数据报有效数据进行加密
  3. 保证数据是完整的，没有被修改
  4. 确保IP数据报的发送源未被伪装

关于实现的原理，在之后的学习中，有需要再去了解。

选路算法

前面已学Internet的两个主要部分：IP协议和ICMP协议
接下来学习第三个主要部分：选路协议
先学习一些选路算法

于主机相连的第一个路由器称为默认路由器或者第一跳路由器
选路算法解决的问题是：数据报从源路由器到目的路由器之间的最“好”的一条路径

理想情况：网络可以抽象成图

网络抽象图

算法的分类：

按全局性还是分布式来分类:

  1. 全局选路算法：需要每个节点了解所有的节点连通性和链路的费用
  2. 分布式选路算发：只需要每个节点了解相邻的节点连通性和链路费用

按静态还是动态来分类：

  1. 静态：变化缓慢，通常需要人为的干预
  2. 动态：在网络流量负载或者拓扑发生变化是改变选路路径

按链路负载敏感度来分类：

  1. 负载敏感：链路的费用反映链路当前的拥塞水平
  2. 负载迟钝：链路的费用不反映链路当前的拥塞水平

属于全局选路算法，通过每个节点向网络中的所有其它路由器广播链路状态来实现。
下面讲的链路状态选路算法使用dijkstra算法实现

计算从源节点u到网络中其它每个节点的最短路径：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Initialization:
  N’ = {u}    
  for all nodes v      
    if v is a neighbor of u         
      then D(v) = c(u,v)     
    else D(v) = ∞
Loop    
  find w not in N’ such that D(w) is a minimum   
  add w to N’  
  update D(v) for each neighbor v of w and not in N’:
      D(v) = min( D(v), D(w) + c(w,v) )
   /* new cost to v is either old cost to v or known    
   least path cost to w plus cost from w to v */
until N’= N

  • N’：路径已确定的节点集合
  • D(v)：每次迭代，从源节点到目标节点v的最低费用
  • p(v)：最好路径的前一个节点

    算法时间复杂度O（n^2）

从p(v)我们可以确认转发表中的下一条链路

选路算法会周期性的执行
当有一条链路的费用发生变化，会通告给其他的路由器

考虑到这样一个现象：有两个排队通道，如果同一时间所有人从较长的队列移动到较短的队列，那么这并不会带来任何实质性的改善。
选路算法也存在这样的问题，叫做选路震荡

选路震荡

符合防止选路震荡？

  1. 强制链路费用不依赖于负载。这是一种不可接受的方案，因为选路的目标之一就是要避开高拥塞。
  2. 防止同时执行。即便是不同时开始，周期执行，由于网络的“自同步”性质，最终也会成一起执行的结果。因此最好的避免方式是随机执行。

距离向量选路算法（Distance-Vector,DV）

DV算法是异步的，分布式的算法。

DV算法的核心是一个方程式：dx(y)=minv{c(x,v)+ dv(y)}
v是一个变量，表示节点x所有的邻居
dx(y)表示x到y的最短距离

DV算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Initialization:

  for all destinations y in N:
    Dx(y) = c(x,y)   /* if y is not a neighbor then c(x,y) = ∞*/
  for each neighbor w
    Dw(y) = ? for all destinations y in N
  for each neighbor w
    send distance vector Dx= [Dx(y): y inN] to w

loop
  wait(until I see a link cost change to some neighbor w or
        until I receive a distance vector from some neighbor w)

  for each y in N:
    Dx(y) = minv{c(x,v) + Dv(y)}

  if Dx(y) changed for any destination y
  send distance vector Dx= [Dx(y): y in N] to all neighbors
forever

每次会把有更新的行发给邻居，邻居再根据接受到的数据来更新自己
DV算法

从算法中可以看到，两个循环触发的因素：

  1. 有链路费用发生变化
  2. 从邻居接收到距离向量变化的消息

接下来分析两种链路费用变化的案例：

链路费用变化

如图：

  1. a图中链路(x,y)费用减少，y检测到费用变化，触发更新，一系列迭代后，新的转发表生成
  2. b图中链路(x,y)费用减少，并通知x，x更新距离向量，同时通知y，y又更新后通知x…..出现选路环路，更新会在两个节点之间来回反复

如何处理选路环路？

增加毒性逆转：如果z 通过y 到x，那么z通告y，它（z）到x的距离是无穷大。
这样的操作显然可以防止环路的产生

LV算法和DV算法孰好孰坏？

  1. DV算法复杂度较小，获取费用的消耗较小，但是收敛速度受影响较多。
  2. LS算法的健壮性较好，所有节点都独立计算自己的转发表，而DV算法的一个错误会导致整个网络的错误。

层次选路

已经了解了相关的基础算法，但只是理论上可行的。
很显然，运用于实践中就会有诸多问题：

  1. 规模：现实中有上亿的计算机，LS算法要求存储惊人的链路信息，DV算法可能永不收敛。
  2. 企业化：总有组织不愿意加入这种公开性的全球性的算法计算中，而是愿意隐藏内部网络，控制自己的路由信息。

这些问题由Autonomous System（自治系统）来解决，每个AS系统由一组相同管理控制下的路由器（ISP或者公司），运行同一种选路算发（DV或者LS，但是为了区别，我们叫做自治系统内部选路算法）。
负责AS系统之间的路由器叫做网关。

如何处理AS系统之间的选路问题呢？

也就是说，某个要出去的分组应该经哪个网关路由器，发送到哪个外部AS系统呢？

较简单的方案是：通过AS间选路算法，计算所有外部AS系统的可达信息，把这些可达信息放到AS内所有路由器的转发表中
使用前缀风格的转发表，可大大减小转发表的量。

如果有多条可达路径，还可以根据约定的“策略”来选择。
常见的策略如热土豆选路（选择最低费用）

AS系统之间的选路

Internet网中的选路

上一节中我们学习了相关的原理，这一节就来了解这些理论在当今因特网中发挥了怎样的作用。

Internet网AS内部选路：RIP

数据距离向量协议，类似DV算法
使用跳数作为链路费用，每条链路的费用为1，如图：

跳数的定义

路径的最大费用为15，这也意味着，RIP协议适用的AS系统规模不会很大。
RIP每30秒发送一个RIP更新通告，通知邻居它到每个子网的最短距离。
180秒若没有收到邻居的通告，则可认为与该邻居的链路已中断。
邻居接受到转发表，更新转发表，通告给邻居，邻居再重新计算最短路径，更新转发表再通知，直至收敛。

RIP转发表

Internet网AS内部选路：OSPF

类似LS算法
链路费用可由管理员配置
每30分钟广播一次链路状态（无论是否有更新，这种设计增加了健壮性）
OSPF通告使用OSPF报文，和ICMP一样承载在IP分组中，协议值为89。
OSPF协议自身实现了可靠报文传输，链路状态广播等功能
更多优点：

  1. 安全：仅信任的路由器能参与一个AS内的OSPF协议。报文加入了鉴别的功能。
  2. 多条相同费用的路径：OSPF允许多条相同费用的路径同时传输
  3. 支持多路选路算法
  4. 支持在单个选路域内的层次结构

Internet网AS间选路：BGP

  • BGP处理的问题：

    1. 从相邻AS处获得子网可达性信息
    2. 向AS内部传达这些可达性信息
    3. 根据可达信息和AS策略决定路径

  • BGP如何传达消息？

    1. 建立半永久TCP连接，称为BGP会话，之间交流使用BGP报文
    2. 连接的两端路由器叫BGP对等方
    3. AS间的BGP会话称为eBGP（external BGP session）*
    4. AS内的BGP会话称为iBGP（internal BGP session）*
    5. 在BGP中，可达信息都是以前缀风格的IP来传达的，在BGP中也叫做路由

BGP会话

  • 在BGP会话中，增加额外的属性以控制可达信息的传输：

    1. AS自治号：每一个AS都有一个AS自治号（除了边缘AS，也就是只作为源AS或者目标AS，称为桩（stub）AS）
    2. AS-PATH：记录一个路由都经过了哪些AS，可防止环路，也可以作为选路策略。
    3. NEXT-HOP：记录路由从哪一个接口进入AS内部，用于在向AS内部传达这些可达性信息时，通过内部选路协议确定到NEXT-HOP的路径，从而确定到目的前缀的路径。

  • 路由选择：多条路由的情况下，选择那一条？

    1. 增加本地偏好值的属性，较高的本地偏好值会被选择
    2. 最短的AS-PATH被选择
    3. NEXT-HOP中指定的接口，最近的会被选择
    4. 等等

  • 通告策略：路由是否如何通告？

    1. 桩AS不应该通告给其他AS
    2. 不同的ISP之间往往由于利益问题具有不同的通告策略

广播和多播选路

  • 广播：一个源节点向网络中的其它所有节点发送分组
  • 多播：一个源节点有选择的向网络中的其它节点发送分组

之前都只有研究过单播的选路算法，这一节主要是学习广播和多选的选路算法

广播

广播分组的IP地址分为两种

  1. 受限广播：只在子网内传输，IP为255.255.255.255
  2. 直接广播：发送到专门网络上的每台主机了，主机字段（子网掩码意外的部分）通常全为1，如 192.168.10.255

假设需要广播到N个目的主机

最简单的广播选路算法

使用N次单播
缺陷：

  1. 相同的分组会在相同的路径上传播多次
  2. 单播方式要求知道知道每一个广播成员IP，需要额外的协议来维护广播成员

无控制洪泛

所有的节点都复制该分组并转发给所有的邻居（除来源）
缺陷：

  1. 会出现环，导致广播风暴

N次单播

如何防止广播风暴？

受控洪泛

  1. 序列控制洪泛：每个节点都维护已接收的分组源地址（或其他唯一标识）和广播序号的列表，防止重复接受。
  2. 反向路径转发（RPF）：只有当分组到达的链路正好是在到源的最短路径上（转发表中有记录），才转发给所有的邻居（除来源）。

    之所叫反转，是因为由源到目的的路径和由目的到源的路径可能是不一样的，这里使用的是后面一种。
    反向路径转发

上面的两种方案虽然都处理了重复的分组被丢弃，但是没有从根本上无法避免冗余分组的传输。

  1. 生成树广播：最小树能使路径不重复的到达所有节点，在所有广播成员内计算出最小生成树，然后把分组沿着这棵树的邻居广播（方向无所谓）。
    生成树算法的主要复杂点在于树的生成和节点维护：
    最简单的是基于中心方法，选择合适的中心节点，其他路由器向中心路由器发送加入树（tree-join）报文，加入树报文路过的路径也会加入到生成树中，做生成树。

    最小生成树虽然理论上很棒，但是在网络中实现起来却不简单

生成树广播

  1. 实践中的而广播算法：
    • Gnutella：使用序列控制洪泛，并使用TTL来控制洪泛的跳数，也称为范围受限洪泛
    • OSPF：也使用序列控制洪泛

多播

和广播最大的不同在于，多播需要维护多播成员信息

如何给多播分组编址？

多播地址也叫做组地址，采用D类IP地址（224.0.0.0~239.255.255.255）
首4位总是2进制1110开头

组如何形成？如何终结？
新主机如何加入组？如何退出组？
任何主机都可以自由加入吗？
多播分组如何交付给组成员？
以上这些问题终归于因特网组管理协议（IGMP3）

IGMP3

和ICMP协议类似，承载在IP数据报上，IP协议号为2
作用在第一跳路由器和主机之间
具有3种类型的报文：

  1. membership_query报文：路由器向主机发出，确认哪些主机加入了多播组
  2. membership_reprot报文：主机向路由器报告组信息
  3. level_group报文：主机向路由器报告离组，可选，可以通过不响应membership_reprot报文来实现。

如何确定多播分组的目的路由器？

由IGMP确认的组信息分离在不同的路由上，我们可以把这些多播路由器连接起来，使得重播分组只在这些路由上进行传播。

多播选路算法

多播选路算法的主要功能是让多播地址注册到路由器的转发表中。

  1. 基于共享树：在相同组的路由器中形成最小生成树（可能包含少数非组内路由器），生成的方法和之前说的一样，关键在于中心节点的选择。分组沿着树进行传播。
  2. 基于源的树：使用RPF对每一个源构建一棵多播选路树。RFP是广播算法，因此需要配合剪枝算法进：若第一跳路由器无加入组的主机，就向上游路由器发送剪枝报文。若一个路由器从它的所有下游路由器收到剪枝报文，就向上游路由器发送剪枝报文。
  3. 实践中的多播选路算法是距离向量多播选路协议（DVMRP），采用基于源的树算法那。

本文标题:计算机网络自顶向下：第四章-网络层

文章作者:Sun

发布时间:2019年04月25日 - 17:04

最后更新:2019年04月25日 - 17:04

原始链接:https://sunyi720.github.io/2019/04/25/cmpNet/计算机网络自顶向下：第四章-网络层/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。