rhb_blog

rao的博客

0%

网络层

发表于 更新于 分类于 ，

网络层

第一部分：网络层概述

网络层是整个协议栈中最复杂的层次。它能够被分为两个相互作用的部分：数据平面和控制平面。

1、网络层的目标：

是实现主机到主机的通信。

2、网络层在计算机网络的作用是：

  • 为运输层提供支持。
  • 为实现从源主机到目标主机成功的移动数据分组，整个路径上的每一台分组交换机上均需实现网络层。

网络层属于网络核心的功能，从运输层到网络层就从网络边缘进入到了网络核心。

3、网络层的核心功能：选路和转发。

转发是指在路由器内部将输入端口的分组转移到正确的输出端口；而路由是指路由器决定从源到目的地的路径

在全局范畴为主机之间的通信进行选路，选路的结果反映为分组交换机上的转发表

分组交换机上的网络层根据转发表以及分组头部信息，将分组向适当链路进行转发

对于面向连接的网络层服务，提供连接建立的功能

分组交换机的分类：

根据链路层首部信息进行转发的——链路层节点交换机

根据网络层首部信息进行转发的——路由器

4、网路层可以提供的服务：

  • 确保交付
  • 具有时延上界的确保交付
  • 有序分组交付
  • 确保最小带宽
  • 确保最大时延抖动

面向连接的服务——虚电路，需事先握手

面向无连接的服务——数据报，无需握手

5、几种实际使用的网络层服务模型：

6、网络层和运输层相应服务的区别

网络层只向运输层提供主机到主机的服务；运输层是向应用层提供进程到进程的服务。

值得一提的是运输层同时提供上述两种服务。

此外，运输层的服务是在网络边缘的端系统实现的（端到端系统）。而网络层的服务则是在整个网络中实现的，包含路由器。

第二部分：路由器的工作原理

路由器的结构

整个路由器结构可划分为两大部分：

1、路由选择部分。

路由选择部分：也叫做控制部分，其核心构件是路由选择处理机。 路由选择处理机的任务是根据所选定的路由选择协议构 造出路由表，同时经常或定期地和相邻路由器交换路由信息而不断地更新和维护路由表。

2、分组转发部分。

分组转发部分由三部分组成：

​ 1、交换结构(switching fabric)：又称为交换组织，其作用是根据转发表(forwarding table) 对分组进行处理。

​ 2、一组输入端口

​ 3、一组输出端口 （请注意：这里的端口就是硬件接口）

  • 输入端口：线路端接→数据链路处理（协议、拆封）→查找、转发、排队（→交换结构）

分散式交换:

按照给出的目的地址,使用输入端口的内存中存储的路由选择表，查找输出端口（注意每个输入端口都有一份转发表的拷贝），

目标:以“线路速度”完成输入端口的处理

排队：如果数据报到达的速度超过了输入端口将数据报转交给交换结构的速度，则后到的分组会暂时阻塞

​ 输入端口排队：输入的分组太多，就会对其进行缓存。会产生线头阻塞现象（大家都想吃麦当劳，即使肯德基没人排队）。输入缓冲区溢出可导致排队时延和丢包。

  • 输出端口：排队（缓存管理）→数据链路处理（协议、封装）→线路端接→

​ 输出端口里面装有物理层、数据链路层和网络层的处理模块。输出端口从交换结构接收分组，然后把它们发送 到路由器外面的线路上。

​ 在网络层的处理模块中设有一个缓冲区（队列）。 当交换结构传送过来的分组的速率超过输出链路的发送速率 时，来不及发送的分组就必须暂时存放在这个队列中。

​ 数据链路层处理模块将分组加上链路层的首部和尾部，交给物理层后发送到外部线路。

​ 输出端口排队：来不及输出的分组就对其进行缓存，输出缓冲区溢出会导致分组的排队和丢失。

  • 交换结构：三种交换技术（经内存交换、经总线交换、经互联网交换）

    通过内存：当路由器的某个输入端口收到一个分组时，就用中断方式通知路由选择处理机。然后分组就从输入端口复制到内存中。 路由器处理机从分组首部提取目的地址，查找路由表， 再将分组复制到合适的输出端口的缓存中。

    问题：若存储器的带宽（读或写）为每秒M个分组，那么路由器的交换速率（即分组从输入端口传送到输出端口的速 率）一定小于M/2。【转发速度受限于内存的带宽（每个分组走两次总线）】

    通过总线 ：数据报从输入端口通过共享的总线直接传送到合适的输出端口，而不需要路由选择处理机的干预。

    问题：因为每一个要转发的分组都要通过这一条总线，因此路由器的转发带宽就受总线速率的限制。

    现代的技术已经可以将总线的带宽提高到每秒吉比特的速率，因此许多的路由器产品都采用这种通过总线的交换方式。

    通过纵横交换结构(crossbar switch fabric)：这种交换结构常称为互连网络(interconnection network)。 它有2N条总线，可以使N个输入端口和N个输出端口相连接。当输入端口收到一个分组时，就将它发送到与该输入端口相连的水平总线上。

    若通向所要转发的输出端口的垂直总线是空闲的，则在这个结点将垂直总线与水平总线接通，然后将该分组转发到这个输出 端口。但若该垂直总线已被占用（有另一个分组正在转发到同一个输出端口），则后到达的分组就被阻塞，必须在输入端口排队。

问题：缓冲区设置多少合适呢？

a：$B=RTT x R$

输出端口分组调度策略

1、先来先服务FCFS/FIFO

2、加权公平排队WFQ。类似与OS中的优先级优先策略。

第三部分：网际协议:因特网中的转发和编址

因特网网络层的内部视图：

网络层主体是什么，它又是如何提供上述服务呢？

网络层具有三个主要组件：IP协议、因特网控制报文协议、因特网路由选择协议。通过这些
组件，网络层可以复杂的网络网中寻找到最合适的路径，将分组从源主机移动到目的主机。
下面将通过具体介绍这三大组件，来介绍网络层。

路由器转发表只有目标地址和链路接口。

IP数据报格式

目前正在使用的IP协议有两个版本，一个是广泛部署的IPv4，另一个是被提议用来代替IPv4
的IPv6。对于不同版本的IP协议，对应着不同的数据报格式。

一个IP数据报由首部和数据两部分组成。首部的前一部分长度是20字节，后一部分为可变长度。

（1）IP数据报首部固定部分中的各字段

版本：4bit，指IP协议的版本。通信双方使用的版本必须保持一致，目前使用的是IPV4。

首部长度：4bit。以4字节为一个单位。

服务类型：8bit，用来获取更好的服务。前3bit表示优先级，第4bit表示要求更低时延，第5比特表示要求更高吞吐量，第6比特表示要求更高可靠性，第7比特表示要求选择费用更低廉的路由，第8比特未用。

总长度：这是整个IP数据报的长度，即首部加数据，使用字节计算。该字段长为16比特，因
此，IPv4数据报的理论最大长度为65535字节。

标识、标志位、片偏移：它们与IP分片有关，标识号用于确定哪些数据报其实是同一个较大
数据报的片，最后一个片的标志位被设为0， 而其他片的标志位被设为1， 偏移字用于指定
该片应该存放在数据报的哪个位置。以8个字节为偏移单位。

TTL： 用于确保数据报不会长时间在网络中循环，每当数据报由一台路由器处理时，该字段
的值减一，当TTL为0时，数据报将会被丢弃。

协议：该字段标识数据报的数据部分将会交给哪个特定的运输层协议

首部校验和：用于帮助路由器检测收到的IP数据报中的比特错误，路由器一般会丢弃检测出
错误的数据报，

源和目的IP地址：顾名思义，就是发出此数据报和接收此数据报的主机地址。

（2）IP首部的可变部分：

选项：选项允许IP首部被扩展，但很少使用。选项使得数据报首部长度可变，故无法预先确
定数据字段从何开始。而且使得处理每个数据报的时间不定、也增加了开销

数据：数据报的有效载荷，被用来交给上一层

IPv6数据报中的字段：

版本：用于标识IP协议的版本号

流量类型：与IPv4中的TOS相似

流标签：该20比特用于标识一条数据报的流

有效载荷长度：该16比特值给出了在IPv6数据报的定长的40字节的数据报首部后的字节数量

下一个首部：标识数据报中的数据字段被交给哪个运输层协议

源和目的地地址

数据：数据报的有效载荷

IP分片和重组

为什么IP要分片？

因为网络链路具有MTU（最大传输单元）属性—–是由链路层最大帧的限制决定的。不同类型的链路具有不同的MTU。

于是大的IP数据报就会在网络中被分成小的分片：

  • 一个数据报变成了几个数据报，每片开头都要带上IP报头。
  • 重组只在目的主机中进行
  • 数据报头部的标识、标志以及片偏移字段用于目的主机对接收的分片进行分组。

e.g.:

IP地址结构

点分十进制（dotted decimal）

一个IP地址可以划分为两个部分：网络号（network numbers）和主机号（host identifier）。

网络号也称为网络前缀（nerwork prefix）、网络标识（network ID）。它是用于确定拥有该IP地址的主机位于哪个网络。

主机号用于确定属于该网络的哪台主机。

问题:

. 下面哪些关于两个IP地址的说法是正确的?
A.如果它们在不同的网络，则它们的网络号必须不同.
B.如果它们在不同的网络，则它们的主机号必须不同.
C.如果它们在相同的网络，则它们的主机号必须相同.
D.如果它们在相同的网络，则它们的网络号必须相同.
E.如果它们在相同的网络，则它们的主机号必须不同.
答案：ADE

IP地址的分类

A类网、B类网、C类网个数是主机号的数量-2

问题：

下面的IP地址中A类、B类、C类地址分别有几个?
92.168.1.100
129.32.123.54
223.89.201.145
220.18.255.254
124.254.200.254
191.64.220.8
66.254.1.100
192.1.100.1

202.15.200.12

答案：

A类：第一位确定为0，范围为：0~127，所以：92.168.1.100 124.254.200.254 66.254.1.100三个属于A类网

B类：前两位确定为10，范围为：128~191，所以：129.32.123.54 191.64.220.8两个属于B类网

C类：前三位确定为110，范围为:192~223，所以：223.89.201.145 220.18.255.254 192.1.100.1 202.15.200.12四个属于C类网

问题：有类地址191.168.1.2的网络号和主机号分别是什么？

答：因为为191开头，所以为B类地址，前16位为网络号，后16位为主机号，所以网络号为191.168.0.0，主机号为0.0.1.2

问题；一个C类网可用的IP地址有多少个？
答：根据问题，可知是一个确定的C类网，IP地址为可用主机个数，2^8-2=254个。

子网划分

一个有类网可以划分为多个相同大小的子网（subnet）。

子网的意义：在实际的运用中，我们不可能直接将一个有类网络管理，需要将其分割成不同的块来细分管理，这些块就是子网。

子网划分的方法：从主机号中借用一部分位数作为子网号

子网掩码

上述的子网划分有一个问题：我们怎么知道子网到底借了主机号多少位作为子网号？

A：通过子网掩码我们就能得知。

子网掩码的记法：223.1.1.0/24中的/24就是子网掩码的记法，表示的是该网络号223.1.1（c类网络）的子网掩码的位数为24位。

首先，我们弄清楚子网掩码位数、IP位数、网络位数、主机位数的关系。

IP地址位数=网络位数+主机位数=32位。子网掩码就是网络地址的位数【子网掩码的1的个数表示网络位的个数，子网掩码中0的个数表示主机号的位数】。简单地来说，网络位是不属于你控制的，是上级主管给你的，给你多少就是多少。但是主机位是你可以控制的，你可以把它缩短，把缩短出来的位数加到网络位中，这样网络位就长了，子网数就多了，相应地每个子网的IP数量就少了（相当于IP认了山头）。

A类网络的网络位数是8位，默认子网掩码就是11111111.00000000.00000000.00000000，换算成二进制表示为255.0.0.0。即255.0.0.0的子网掩码表示A类网络中的子网没有借用主机号，就一个子网。

B类网络的网络位数是16位，默认子网掩码就是11111111.11111111.00000000.00000000，换算成十进制表示为255.255.0.0。

C类网络的网络位数是24位，默认子网掩码就是11111111.11111111.11111111.00000000，换算成十进制表示为255.255.255.0。

A类网络加长子网掩码到16位就把一个A类网络划分为256个B类网络同样大小的网络，再加长到24位就又把每个B类大小的子网划分为256个C类网络大小的子网。就是这个道理。一个大的网络，通过把子网掩码加长，使网络位多了，也就是网络数目多了，子网就多了。

一个B类网络的默认子网掩码为255.255.0.0，你如果想把它划分为2个子网，网络位数就成立17位，也就是说子网掩码就变成了255.255.128.0；想划分为16个子网，因为16是2的4次方，所以网络位数加4变成了20位，也就是说子网掩码加长，成了20位，就是255.255.240.0。依此类推。

一个C类网络的默认子网掩码为24位的，那么主机位=32-24=8位，2的8次方等于256，所以一个C类网络的IP地址数量（包括网络地址和广播地址）为256个。

总结：

  • IP地址位数=32
  • 网络位+主机位=32
  • 子网掩码加长n位，则在当前子网基础上划分为2的n次方个子网。每个子网的IP地址数量=2^(32-划分前子网掩码位数-n)

第二个问题：如何根据子网划分的目标计算子网掩码？

A：核心抓住子网掩码的位数等于该有类网现在网络号的位数。知道了这个道理，计算子网掩码的方法就是：已知子网内IP数的多少，求出主机位的位数，用32减去主机位数就等于网络位数，也就是子网掩码。

同一个网段的中的计算机子网掩码相同，计算机的网关就就是到其他网段的出口，也就是路由器接口地址。路由器接口使用的地址可以是本网段中任何一个地址，不过通常使用该网段的第一个可用的地址或最后一个可用的地址，这是为了尽可能避免和网络中的计算机地址冲突。（参见下文的层次路由部分）

网关实质上是一个网络通向其他网络的IP地址(此处也说明了IP地址是路由器的接口地址)。比如有网络A和网络B，网络A的IP地址范围为“192.168.1.1192. 168.1.254”，子网掩码为255.255.255.0；网络B的IP地址范围为“192.168.2.1192.168.2.254”，子网掩码为255.255.255.0。在没有路由器的情况下，两个网络之间是不能进行TCP/IP通信的，即使是两个网络连接在同一台交换机(或集线器)上，TCP/IP协议也会根据子网掩码(255.255.255.0)判定两个网络中的主机处在不同的网络里。而要实现这两个网络之间的通信，则必须通过网关。如果网络A中的主机发现数据包的目的主机不在本地网络中，就把数据包转发给它自己的网关，再由网关转发给网络B的网关，网络B的网关再转发给网络B的某个主机(如附图所示)。网络B向网络A转发数据包的过程。

对默认网关，其意思是一台主机如果找不到可用的网关，就把数据包发给默认指定的网关，由这个网关来处理数据包。现在主机使用的网关，一般指的是默认网关。

CIDR

即上述说的子网掩码的记法：地址格式: a.b.c.d/x, 这里的 x表示地址中网络部分的位数 #

转发

最长前缀匹配：

使用 CIDR 时，路由表中的每个项目由“网络前缀”和“下一跳地址”组成。在查找路由表时可能会得到不止一个匹配结果。

应当从匹配结果中选择具有最长网络前缀的路由：最长前缀匹配(longest-prefix matching)。

网络前缀越长，其地址块就越小，因而路由就越具体。

最长前缀匹配又称为最长匹配或最佳匹配。

e.g

C4.5E.0.0/12的网络前缀为11000100 0101
C4.5E.10.0/20的网络前缀为11000100 01011110 0000
C4.60.0.0/12的网络前缀为11000100 0110
C4.68.0.0/14的网络前缀为11000100 011010
80.0.0.0/1的网络前缀为1
40.0.0.0/2的网络前缀为01
0.0.0.0/2的网络前缀为00

a中为11000100 01011110 00001101 87符合B；b中为11000100 01011110 0001xxxx 09和B不符合，退而求其次选择A。其他同理。

获取网络地址和IP地址（主机部分）

Q：一个网络如何获取一个地址？
A：从ISP的地址空间中获得。（找上级组织）

Q：ISP如何获得整块地址？
A： ICANN: Internet Corporation for Assigned Names and Numbers（因特网名字与号码分配团体）

分配IP地址

管理 DNS

分配域名, 解决域名纠纷

Q：主机如何获得IP地址？(主机部分)
1.A：手动配置。DHCP 动态主机配置协议:从服务器上动态获取IP地址

DHCP协议

用于主机在加入网络时动态租用IP地址。

问：在一个以太网中，哪个DHCP数据包可以让该网络中的每个DHCP服务器知道DHCP客户端是否选用了它提供的IP地址?
A.DHCP discover
B.DHCP offer
C.DHCP request
D.DHCP ack
解析；如上图，DHCP request可以告知每个DHCP服务器这个客户端选择的是否是服务器提供的IP地址。

DHCP协议的步骤：

主机广播 “DHCP discover” 报文

DHCP服务器响应“DHCP offer” 报文

主机请求IP地址： “DHCP request” 报文

DHCP 服务器确认： “DHCP ack” 报文

从移动性角度看，DHCP存在问题:当一个节点连接到新的子网中时，要从DHCP中获取新的IP地址。所以在移动的过程中就不能维持TCP的连接。

网络地址转换NAT(Network Address Translation)

NAT能使路由器对于外部世界看起来像一个单一IP的单一设备， 使路由器对外界隐藏内部网络的细节。所有离开此内部网络的报文与进入此网络的报文都有一个相同的源地址与目的地址，NAT路由器通过使用一张NAT转换表来区分内部网络中的各个主机，转换表包含端口号与其IP地址。NAT转换表与某台主机中端口号与进程ID号对照表类似。（NAT就好似一个班级，本地IP地址就是班级的同学，其他人访问这个班级的一个IP地址时，只需要访问到班级，由班级自己转达到该IP地址。此外，为了保护班级同学的隐私，班级对外展示的都是班级同学的外号，其他人找人也只能通过班级+外号来找人。）

把原本的本地IP地址映射成为源端口号

例如外网需要远程连接内网的192.168.1.9的主机，在NAT中把远程访问的端口3389影射为内网的192.168.1.9:3389，当外网输入外网Ip做远程访问时，路由检测到3389的端口号，就自动转到内网192.168.1.9，这时候外网就直接可以和内网的192.168.1.9通过端口影射直接访问了

NAT转换表

（相当于班级外号表，将班级内的同学的姓名转化成外号传输给外人)

记录的是源IP地址,端口号 -> NAT IP 地址,新的端口的转换对。

假设一个私有地址为10.1.0.2的主机想访问互联网服务器162.105.192.12，那么首先它首先把消息发出给NAT路由器。路由器记录了它的内网地址和端口，并且给它分配一个全局地址和全局端口。这个地址关系记录在NAT路由表中。之后按照目的地址发给服务器。一段时间之后，服务器回应了请求给NAT路由器，那么路由器根据目的地址和端口（此时是全局的,就是班级号+外号）按照NAT路由表转换为对应的主机地址，再发送给主机，这样主机就收到了服务器的回应。

NAT的优点：

1.不需要从 ISP处获得大批IP地址: 所有设备可以使用同一个 IP地址
2.可以在不通知外部网络的情况下改变内网主机的IP地址
3.即使改变了ISP也无须改变内网主机的IP地址
4.内网主机对外网主机而言是不可见的、不可寻址的。
(这也算是一项安全措施).
5.由上述的分析可知NAT可以扩展IP的数量（每一个路由器都可以分配很多私有地址，并且不同路由器的私有地址可以重复。不同班级的二狗子表示不同的人，但是二狗子）

NAT虽然得到广泛应用，但很多人反对NAT，原因如下：
1.端口号是用于进程编址，而不是主机编址
2.路由器通常仅应当处理高达第三层的分组
3.主机应彼此直接对话，结点不应该介入修改IP地址与端口号
4.应该使用IPv6来解决IP地址不足的问题

NAT的另一个问题是妨碍了P2P应用程序， 使得在某个NAT下的主机无法与另一个主机建立对等方发起的一条TCP连接。

UPnP：允许外部主机使用TCP或UDP向NAT化的主机发起通信会话。（告诉对方我的真实IP地址和应用的端口号）

内部主机通过IGD（ Internet Gateway Device ）协议

  • 了解公共IP地址
  • 向路由器注册/移除映射记录
    （内部IP地址，内部端口号）–>（公共IP地址，公共端口号）

内部主机通过某种渠道向外部应用程序公开（公共IP地址，公共端口号）

适用于P2P应用

ICMP：因特网控制报文协议

因特网控制消息协议（Internet Control Message Protocol）用于主机或路由器发布网络级别的控制消息。
【错误报告: 如主机、网络、端口、协议不可达等。
回声请求/回答 (用于ping应用程序)】

1、从体系结构而言，位于IP层之上 :

  • ICMP 报文封装在IP分组中

2、ICMP 消息: 包括一个类型字段和一个编码字段

3、ICMP 报文的种类有两种，即 ICMP 差错报告报文和 ICMP 询问报文

4、ICMP消息的一般格式：

ICMP消息的常见类型：

IPv6

IPv6的数据报格式

·版本号。这 4 比特字段用于标识 IP 版本号。 IPv6 将该字段值设为 6。

·流量类型。与IPv4的TOS相似

·流标签。 该 20 比特字段用于标识一个数据报的流。

·有效载荷长度。 给出了 IPv6 数据报中跟在定长的 40 字节数据报首部后面的字节数 量。

·下一个首部。该字段标识该数据报中的内容(数据字段)需要交付给哪个协议(如 TCP 或 UDP)该字段使用与 IPv4 首部中协议字段相同的值。

·跳限制。转发数据报的每台路由器将对该字段内容减 1。如果跳限制计数到达 0，则 该数据报将被丢弃。

·源和目的地址。

·数据。 几个字段在 IPv6 数据报中已废弃:

·分片相关字段。IPv6 不允许在中间路由器上进行分片与重新组装。

·首部校验和。

·选项字段。

几个字段在 IPv6 数据报中已废弃:

·分片相关字段。IPv6 不允许在中间路由器上进行分片与重新组装。

·首部校验和。

·选项字段。

ipv4到ipv6的迁移

双栈技术：

1、如果源和目标都支持IPv6的话，就使用Ipv6进行通信。

2、如果任何一方不支持IPv6的话，则使用IPv4进行通信。

第四部分：选路算法

目的是：给定一组路由器以及连接路由器的链路，从中找到一条从源路由器到目标路由器“好的”路径。

  • 根据信息是全局性还是分散式的进行分类：

全局选路算法

要求：

1、所有路由器都知道整个网络拓扑图以及链路的费用信息
2、链路状态算法

分散式选路算法

要求：

1、每个路由器仅有与其相连链路的费用信息
2、通过迭代计算过程与相邻节点交换信息
3、距离向量算法

  • 根据信息是静态还是动态的进行分类

静态选路算法

要求：

1、随着时间的流逝，路由的变化非常缓慢

动态选路算法

要求：

1、路由信息可以更快地发生变化
2、周期性的跟新
3、可以响应拓扑或链路费用的变化

  • 根据是否对负载敏感进行分类

负载敏感算法

要求：

1、链路费用会动态地变化以反映出链路的当前状况

负载迟钝算法

要求：

1、链路费用不明显地反映链路的当前状况

链路状态选路算法LS

选择的是迪克斯拉特算法（SPF）—–最低费用算法。具体算法实现不介绍。（Dijkstra算法可参考如下：点击打开链接 点击打开链接）

利用这些最短路径上的下一个节点作为下一跳得到源节点的转发表（路由表）。所以路由器的下一跳地址是直接得出的，不需要修改。

可能会遇到的问题：

距离向量选路算法DV

是基于迭代的算法。每个结点当DV变化时将自身DV估计通告给邻居；邻居在必要时（其DV更新后发生改变）才通告它们的邻居

当结点检测到本地链路费用改变或者接收到来自邻居的新DV估计更新时，即依据B-F方程更新自身的距离向量估计Dx(y)将最终收敛于实际的最小费用dx(y)

思想：

  1. $B-F公式：dx(y)=minv{c(x,v)+dv(y)}$

    • dx(y):节点x到y的当前最低费用
  • v是对于x的所有直接邻居
    • 我到目的地的最小距离，等于 我到邻居距离与邻居到目的地最小距离之和（存在一个或多个邻居） 的最小值。

  1. 每个路由器中都有一张路由表，包含三个内容：目的网络号、经过的邻居路由器、到目的网络的距离（<目的网络 N，跳数，下一跳地址>）

  2. 路由器定期向其邻居路由器传送路由表的拷贝

算法执行步骤

参考文章

  1. 从相邻的 X 路由器接收发送过来的 RIP（Routing Information Protocol） 报文
  2. 将该 RIP 报文中的下一跳地址修改为 X，且跳数增加 1
  3. 对每个项目执行如下步骤
    a.若原路由表没有 RIP 中的目的网络 N，直接添加到原路由表中
    b.若原路由表中有 RIP 中的目的网络 N，但下一跳地址不是 X ，选择跳数少的替换。如果两者跳数一样，则保留原路由表的项。
    c.若原路由表中有 RIP 中的目的网络 N，且下一跳地址是 X，使用收到的项替换
  4. 若超过 180s （RIP 默认 180s）还没有收到相邻路由器的更新路由表，则相邻路由器置为不可达，跳数为 16
    路由器的下一跳的地址是不断修改的

链路状态改变时的特点

1、好消息（链路费用变小）传的快：起到收缩的作用，让DV趋于最小的值

在 t0 时刻, y 检测到链路费用变化, 更新自己的距离向量, 同时将这个变化通知给它的邻居
在 t1时刻, z 收到来自 y 的更新报文并更新了自己的距离向量表，计算出到x的新的最低费用，并向邻居发送它的新距离向量
在 t2时刻，y 收到自z的更新并更新其距离向量表，Y的最低费用未变，因此y不发送任何报文给z

2、坏消息传播的慢

解决方案：

针对只有3个节点的环路可以采用毒性逆转

毒性逆转：如果一个结点Z到达某目的X的最小费用路径是通过某个邻居Y，则Z告知邻居结点Y到达该目的X的距离为无穷大。

针对有多个节点的环路没有很好的办法，但是可以定义最大度量(maximum metric):一个最大的有效费用值，如16跳步表示费用为∞

LS算法和DS算法的比较：

  • 报文复杂性

LS 算法要求每个结点都知道网络中每条链路的费用，要发送O(|N|*|E|)个报文。而且无论何时一条链路的费用改变时，必须向所有结点发送新的链路费用。

DV算法要求在每次迭代时，在两个直接相连邻居之间交换报文。当链路费用改变时,DV 算法仅当在新的链路费用导致与该链路相连结点的最低费用路径发生改变时，才传播已改变的链路费用。

  • 收敛速度

LS算法的实现是一个要求O(|N|*|E|)个报文的O(|N|^2)算法。但是可能会有震荡的情况发生。

DV 算法收敛较慢，且在收敛时会遇到路由选择环路，还会遭遇无穷计数的问题。

  • 健壮性。

如果一台路由器发生故障、行为错乱或受到破坏时

LS算法：路由器能够向其连接的一条链路广播不正确费用。作为LS广播的一部分，一个结点也可损坏或丢弃它收到的任何LS广播分组。但是每个LS结点都仅计算自己的转发表。因此路由计算在某种程度上是分离的，提供了一定程度的健壮性。

DV算法：一个结点可向任意或所有目的结点通告其不正确的最低费用路径。因此一个不正确的结点计算值会扩散到整个网络。

路由信息协议RIP（内部网关协议）

RIP协议是一种采用距离向量算法的路由协议。

  • 到目的网络的距离以跳为单位，最大距离为15，距离16表示无穷大，即目的网络不可达。（这一规定限制了RIP协议只能适用于中小网络，网络规模太大的话路由信息就无法到达远端路由器了）
  • 初始时每个RIP路由器只有到直连网的路由，距离为1；
  • 每30秒RIP路由器把它的整个路由表发给邻居（具体实现时每个邻居会错开发送，30秒的时间也会随机变化一点）

简述RIP协议的工作原理：路由器每30秒把自己的路由表发给邻居。路由器用邻居发来的路由表根据距离向量算法修改自己的路由表。初始时每个路由器只有到直连网距离为1的路由。

利用邻居的路由表建立自己的路由表：当收到邻居发来的路由表时，路由器将更新它的路由表<目的网络，开销，下一跳>：

首先将收到的路由的距离全加1（即一跳的距离）；

再利用收到的路由表修改自己的路由表：

  • 将收到的路由表中不存在的路由表项加入到自己的路由表；
  • 如果收到的路由表中某一项的距离比该路由器原路由表对应项的距离更小，则更新该路由表项，并将对应路径的下一跳设置为邻居；
  • 如果路由项存在，就要重置失效定时器；
  • 如果收到的路由表中存在某一项的目的网络也是该路由器的路由表中某一项的目的网络，且下一跳为发送路由表的路由，那无论如何该路由器都要更新对应的表项，将距离改为收到的表项中的距离+1；

因特网中的链路状态选路——OSPF协议（内部网关协议）

是分布式的链路状态协议。由于现在的网络的规模越来越大，自治就很重要，要让每个ISP管理自己的路由器。故我们最多的使用的是OSPF协议。使用的是洪泛链路和Dijkstra最低开销路径算法

协议的内容：

第一要点：洪泛法广播自己邻居的链路状态。

  1. 向本自治系统中所有路由器发送信息，使用的方法是洪泛法

  2. 发送的信息就是与本路由器相邻的所有路由器的链路状态（例如拥堵度）

    【每个链路获得与之相连的链路的标识和开销是由链路状态广播算法实现的。】

  3. 只要当链路状态发生变化时，路由器就用洪泛法向所有路由器发送此信息

  4. 即使链路状态没变化，也要周期性地发送链路状态信息

第二要点：所有路由器的链路状态库可及时更新。

  1. 由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库
  2. 这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的
  3. OSPF 的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。OSPF 的更新过程收敛得快是其重要优点

OSPF协议的特点

  1. 不强制如何设置链路权值的策略，但提供对给定链路权值集合确定最低费用路径的机制
  2. 即使链路状态未发生变化，每30分钟广播一次链路状态
  3. 链路状态以OSPF通告的形式封装在OSPF报文中，由IP分组承载（协议号：89）
  4. OSPF路由器之间的交换都是经过鉴别的（简单的、MD5的），以确认OSPF通告的真实性，防止伪造和篡改
  5. OSPF通告都是有序列号的，以防止重放攻击
  6. OSPF中支持多条具有相同费用的路径
  7. OSPF支持多播选路和层次路由
  8. OSPF使用IP数据报传输报文，是一个网络层协议

层次路由

上述讨论的情况都是基于路由器是相似的。但是实际中的网络是具有层次的。

层次路由解决了当前网络规模大导致路由器无法储存全部的路由器信息的问题。

让ISP自己管理自己的路由器。实现自治系统（AS）。

1、在相同AS内的路由器可全部运行同样的选路算法

  • 自治系统内部选路协议

【内部网关协议 IGP (Interior Gateway Protocol) 目前这类路由选择协议使用得最多，如 RIP 和 OSPF 协议。】

2、在不同AS内的路由器可以运行不同的自治系统内部选路协议

3、不同AS之间的选路：外部网关协议EGP

边界网关协议BGP（包括了外部BGP—eBGP，内部BGP—iBGP）

对于每个AS，每台路由器要么是一台网关路由器，要么是一台内部路由器。

网关路由器:（同上文中的网关一样）

通常位于AS的边缘

具有连接到其它AS的链路

BGP会话

分为内部会话和外部会话。

内部会话参见上文。外部会话如下：

因特网上的AS间路由—BGP4

因为因特网的规模太大，AS间的选择有很多，想要选择最佳路由往往不可实现或者代价很大。

所以，退而求其次。
BGP为每一个AS从相邻AS获取子网可达性信息，然后向内部的所有路由器传播这些消息。
基于该可达性信息和AS策略，决定到达子网的“好”路由
边界网关协议 BGP 只能是力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而并非要寻找一条最佳路由

外部会话中，BGP边界路由器采取的是半永久的TCP连接交换路由选择的信息。

路径属性

前缀+属性（包含在前缀中）=路由 前缀表示一个子网或一个子网的集合（IP地址）。例如AS2向AS1通告它的前缀含义就是告诉AS1：你向这个前缀表示的子网或子网集合发送数据报，我一定帮你转发。

两个重要的属性：

1、AS-PATH（AS路径）包含前缀通告所经过的AS序列（如上述AS2告诉了AS1，那么AS2的AS-PATH中包含了AS1，只能在EBGP邻居之间传路由时进行改动，对IBGP邻居传来的路由改不了）

AS-PATH还可以防止环路的出现。当一个AS收到的路径列表中看到自己就可以拒绝接受该通告

2、NEXT-HOP（下一跳）开始一个AS-PATH的路由器节后，指向一个跳AS。(因为可能从当前AS到下一跳AS之间可能有多条链路)

特征：

①从EBGP邻居学习到的路由会传递给我的EBGP邻居，下一跳改变，为自己

②从EBGP邻居学习到的路由会传递给我的IBGP邻居，下一跳不变，还是EBGP邻居，需要使用next-hop-self改变

③从IBGP邻居学习到的路由不会再传递给我的IBGP邻居（水平分割）

④从IBGP邻居学习到的路由会传递给我的EBGP邻居，下一跳改变，为自己

作用：为BGP发言者指示了去往目的地的下一跳。

【BGP发言者往往是BGP边界路由器。两个BGP发言人通过一个共享网络连接在一起】

BGP 的下一跳属性和IGP 的有所不同，不一定就是邻居路由器的IP 地址。下一跳属性取值情况分为4种，如 图所示。

img

  • BGP发言者把自己产生的路由发给所有邻居时

将把该路由信息的下一跳属性设置为自己与对端连接的接口地址

  • BGP发言者把从EBGP邻居得到的路由发给IBGP邻居时

并不改变该路由信息的下一跳属性。将从EBGP得到的路由的NEXT_HOP直接传递给IBGP对等体。

上图中，RTA通过IBGP向RTF通告路由8.0.0.0/24时，NEXT_HOP为10.3.1.1。

  • BGP 发言者把接收到的路由发送给 EBGP 对等体 时

将把该路由信息的下一跳属性设置为自己与对端连接的接口地址；

上图中，RTB通过EBGP向RTA通告路由8.0.0.0/24时，NEXT_HOP为10.3.1.1。

  • 对于可以多路访问的网络（如以太网或帧中继）

如果通告路由器和源路由器的接口处于同一网段，则BGP会向邻居路由通告路由的实际的来源。

上图中，RTC向EBGP对等体RTB通告路由8.0.0.0/24时，则使用该路由的实际来源地址10.2.1.3作为NEXT_HOP。

如果配置了负载分担，等价路由被发给IBGP邻居时则会修改下一跳属性。关于“负载分担”的概念请参见“BGP的选路规则”。

当一台网关路由器接收到一个路由器通告时，它使用输入策略决定是否接收或过滤该路由

Q：路由器怎么确定自己下一跳的目的地呢？
A：转发表。路由器的转发表中储存下一跳信息。实现参见上述。

BGP路由选择

Q：从源到目标仅有一条路可选或者多条路的时候怎么办？
A：只有一条路的时候，就只在AS内广播寻找最低费用路径，反正AS间的路径只有一条。
有多条路径的时候，采取如下消除规则：

​ 1、本地偏好值：策略决定（由AS的网络管理员决定的决策）具有最高本地偏好值的路由将被选择。

​ 2、最短AS-PATH：在余下的路由中，具有最短AS-PATH的路由将被选择。（起码感受上这个就比其他的短）

​ 3、热土豆选路：从余下的路由中，选择具有最靠近NEXT-HOP路由器的路由

热土豆选路：选择具有最小的最低费用（AS内部的）的网关。意思就是希望尽快将分组送出其AS，而不担心其AS外部到目的地的余下部分的开销。

（使用AS内部协议的选路信息决定每个网关的最低费用路径的费用）不同网关的费用已经经过BGP的外部会话传到了源路由器。

一个简单的BGP图例：

子网x通过AS3和AS2均可到达

因特网上的AS内层次路由——层次OSPF

将自治系统再划分为若干小的范围。

划分区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统，这就减少了整个网络上的通信量。

OSPF 使用层次结构的区域划分。在上层的区域叫作主干区域(backbone area)。主干区域的标识符规定为0.0.0.0。主干区域的作用是用来连通其他在下层的区域。

补充路由选择策略

图示：

桩网路：所有进入该网络的流量必定以该网络为目的地；所有离开该网络的流量必定源于该网络

略

路由协议小结