实现了网络层从主机到主机的通信服务，与传输层和应用层不同，网络中的每个主机和路由器都有一个网络层。网络层是协议栈中最复杂的层次。

世界上有数百万的网络，因为没有统一的标准，很难实现这些网络的连接。每个人都不可能使用同一个网络，因为用户的需求是多样化的，不可能有一个单一的网络来适应所有的用户。虽然网络不可能是一样的，但你可以找到一种方法使用协议使路由器连接的网络遵守协议，在这种情况下，互联网络可以被视为虚拟互联网。

虚拟互联网也是逻辑互联网网络，这意味着各种物理网络的异构性最初是客观存在的，但协议可以使这些不同性能的网络看起来像一个统一的网络。该协议是网络层的重点IP。

连接网络必须需要一些中间设备（也称为中间系统或中继系统）。根据中继系统的水平，可以有以下四种不同的中继系统。

物理层中继系统：中继器或集线器。

2)数据链路层中继系统:网桥或交换机。

网络层中继系统：路由器。

4)网络层以上中继系统:网关。

当中继系统是中继器或网桥时，一般不称为网络互连，因为它只是扩展了一个网络，仍然是一个网络。互联网是指用路由器连接的网络。

但要注意，IP 第一部数据报中有一个第一部检验和。当它被检查出来时IP当数据报告的第一部分出现错误时，数据报告被丢弃。因此，所有交付给目的主机的人都将被丢弃。IP数据报都是IP数据报的首 没有错误，或者没有检测到错误。也就是说，在传输过程中出现错误IP所有的数据报告都被丢弃了。

网络层的作用是将分组(包)从发送主机移动到接收主机，因此需要两个重要的网络层功能:路由选择(确定哪条路径)和分组转发(分组到达时使用的动作)，这也是路由器的主要功能

根据所需的性能要求，可以使用适当的路由算法构建路由表进行路由选择。不仅如此，路由表还会根据相邻路由器获得的整个网络的拓扑变化拓扑变化，以获得最佳路由。

1??路由选择: 它是指确定从源到目的地采用的端到端路径的网络范围处理过程。路由选择的时间尺度更长（通常是几秒钟），因此通常使用软件来实现。如果子网内部使用数据报，那么对每一个进来的分组都要重新选择路径。如果子网内部使用虚电路，那么只有当创建一个新的虚电路时，才需要确定路由路径。

2?? 分组转发：是指将分组从输入链接口转移到适当输出链接接口的路由器的本地动作。转发时间规模很短（通常是几纳秒），因此通常使用硬件实现。-路由器的核心功能

?? 用驾驶的例子进行类比，考虑旅行者所历经的从宾夕法尼亚州到佛罗里达州的行程。在这个行程中，那位驾驶员在到佛罗里达州的途中经过许多立交桥。我们能够认为转发就像单个立交桥的过程：一辆汽车从它的道路进入立交桥的入口，并决定离开立交桥应该走哪条路。我们可以路由选择被视为从宾夕法尼亚州到佛罗里达州旅行的过程：在开始行程之前，司机已经查阅了地图，并在许多可行的路径中选择了一条，每条路径都由一系列通过立交桥连接的路段组成。

?? 路由表是算法是根据路由选择的转发表来自路由表。转发表的结构应优化搜索过程，路由表需要优化网络拓扑变化的计算。在讨论路由选择的原理时，通常不区分转发表和路由表，而是使用路由表这个词。

某些网络架构中（如ATM网络架构）的第三个重要功能——连接建立

在数据报流动之前，两端主机和中间路由器建立虚拟连接：路由器参与

通过拨号建立逻辑上的连接，中间的交换设备参与连接建立，维护一些中间信息：有多少连接，带宽资源是多少。当一些数据包到达交换设备时方便直接转发。排队时间短。

也不会出现乱序的问题：路径固定

网络与传输层连接服务:

网络:在两台主机之间(在VCs的情况下可能会涉及到中间路由器)

传输:两个进程之间，不涉及路由器

从源到目的t路径的行为很像电话线路。

在数据通信之前建立虚电路,通信结束后撤销(teardown)该虚电路;

每个包包含一个虚电路ID (VC identifier)

每个在源-目的之间的路由器维持连接状态; 需要预留资源.

通信之前就知道通信质量如何.

一个虚电路包括

1️⃣ 从发送端到接受端的路径;

2️⃣ 虚电路号，每条路径对应一个数字

3️⃣ 沿路路由的转发表项

每经过一个交换机,虚电路号就会改变一次;

每个交换设备都会维护一个交换表,该表是事先确定好的。该表存储如下一个虚电路号等数据.

上图的转发表如下

路由器维护连接状态信息

用于建立,维护,撤销(teardown)虚电路(VC);

应用于: ATM, frame-relay, X.25, IPv6 ;

IPv4 中没有应用.

路由器的结构分为两大类：路由选择部分和分组转发部分

分组转发部分由三部分组成：一组输入端口、交换结构和一组输出端口

交换结构从输入端口接收到分组后，根据转发表对分组进行处理，然后从一个合适的输出端口转发出去。

路由器的两个功能

1️⃣ 运行路由算法/协议：RIP、OSPF、BGP：只有边界网关路由器才会运行BGP

2️⃣ 将数据包从输入链路转发到输出链路

最左边物理层、中间链路层、最右边网络层

1️⃣ 通过存储器进行交换：输入端口将数据包放到内存里,输出端口将其从内存中读走;

早期路由器采用这种方式,在CPU 的直接控制之下进行交换;

两次访问内存,两次使用总线,效率低;

速度被内存带宽所限制(每个数据包需要经过2 个总线交叉口)\

2️⃣ 通过总线进行交换：任意输入端口的数据放到总线上,输出端口从总线上读取数据;

不涉及访问内存,数据发送到总线后直接发送到输出端口;

路由器性能多快取决于总线的带宽

可达32Gbps

当数据报从交换结构到达的速度快于传输速率时，需要缓冲

调度原则：选择在队列中的数据报进行传输

行头阻塞Head-of-the-Line (HOL) blocking：多个输入端口同时转发到同一个输出端口,不能同时发送,因此只能错开转发.因为只能有一个数据包发送,其他数据包需要在队列里等待,因此阻塞了队列,使队列变长.可能会导致队列满,从而导致丢包.

CMP : 控制报文协议.用于差错报告,连通性检查.

IP : Internet Protocol

网络层可以分为两个子层,其中路由协议与ICMP 协议位于上面的子层, IP 协议位于下面的子层。部分路由信息与ICMP 报文可以直接封装在IP 包中传输.

1️⃣ 有数据直接发送,不需要在网络层建立链接.

2️⃣ 不需要路由器维护状态.

3️⃣ 当路由器收到数据报时,会将其中的网络部分取出,查路由表,对应哪个出口就转到哪个出口.

4️⃣ 可以走不同的路径,因此可能后发的数据包比先发的数据包更早到达,可能出现乱序.

采用最长前缀匹配原则

第二个目的地址(DA)可以匹配接口2 (0011)和接口1(0011000),根据最长前缀原则,选择接口1

IP的首部也是20个字节（20B)，跟TCP段头一样

1️⃣ version：区别是IPv4还是IPv6，通信双方的版本必须一致

2️⃣ head len：首部长

3️⃣ type of service：服务类型，IPv6才有区别，IPv4未启用

4️⃣ flags : 切片包时用的

5️⃣ fragmentation : 将包切片时用的.

切片: 将IP 包切分成若干个比较小的片,使之能够放到信元中.

网络链路层有MTU (最大传输单元),不同的链路有不同的MTU.

对于较大的数据包,如果MTU 装不下包,则会将其切分.

被切分的数据包,只有在接收端才会进行装配.

6️⃣ checksum：没用，链路层已经检查过01跳变了

7️⃣ 源IP地址、目的IP地址

IP地址跟网络接口，主机对应，路由器有许多接口也就有许多IP地址

同一网段，网络部分相同；不同网段，网络部分不同

IP地址由主机部分和网络部分组成

IP 地址具有以下一些重要特点。

1️⃣ IP地址是一种分等级的地址结构。分等级的两个好处如下:

IP地址管理机构在分配IP地址时只分配网络号，而剩下的主机号则由得到该络号的单位自行分配。这样就方便了IP 地址的管理。

路由器仅根据目的主机所连接的网络号来转发分组(而不考虑目的主机号),就可以使路由表中的项目数大幅度减少，从而减小了路由表所占的存储空间。

2️⃣ 实际上IP地址是标志一个主机(或路由器)和一条链路的接口。当一个主机同时连接到两个网络上时，该主机就必须同时具有两个相应的IP地址，其网络号必须是不同的。这种主机称为多接口主机，例如，路由器的每个接口都有一个不同网络号的IP地址。

3️⃣ 用中继器或网桥连接起来的若干个局域网仍为一个网络，因此这些局域网都具有相同的网络号

4️⃣ 所有分配到网络号的网络，不管是局域网还是广域网，地位都是平等的。

把整个因特网看作一个单一的，抽象的网络，IP地址就是给每个连接在网络上的主机（或路由器）分配一个在全世界范围内是唯一的32位的标识符。一般将IP地址分为A,B,C,D,E类地址（E类地址不使用）。

1️⃣ A类地址高一位字段是网络部分，低三位字段是主机部分，最高位固定为0

可以指派的网络数为 2 7 − 1 2^7-1 27−1：网络地址全0为保留地址，“本网络”，网络号为01111111保留为环回地址

主机数最多为 2 24 − 2 2^{24}-2 224−2

2️⃣ B类地址高两位字段是网络部分，低两位字段是主机部分，最高位固定为10

网路地址128.0.0.0实际上不指派，所以最少从128.1.0.0开始，可以指派的网络数为 2 14 − 1 2^{14}-1 214−1

主机数最多为 2 16 − 2 2^{16}-2 216−2

3️⃣ C类地址高三位字段是网络部分，低一位字段是主机部分，最高位固定为110

网路地址192.0.0.0实际上不指派，所以最少从192.1.0.0开始，可以指派的网络数为 2 21 − 1 2^{21}-1 221−1

主机数最多为 2 8 − 2 2^{8}-2 28−2

4️⃣ D类地址高四位字段是网络部分，最高位固定为1110

多播通信时作为目的地址

多播：类似于微信的群聊

1️⃣ 直接广播地址：主机号全1，路由器使用这个地址把一个分组发送到一个特定的网络上的所有主机，所有主机都会收到具有这种类型的目的地址的分组.

2️⃣ 受限广播地址：IP为255.255.255.255，用于定义在当前网络（不是整个互联网）。会向本地局域网中的其他主机发送分组，路由器会阻拦其传播到局域网外。

3️⃣ 这个网络上的这个主机：IP为0.0.0.0，不知道自己的IP地址时的主机发送一个报文给引导服务器，使用0.0.0.0作为源地址，使用255.255.255.255作为目的地址

4️⃣ 这个网络上的特定主机：属于A类地址，用于向同一网络上的某个主机发送报文。

5️⃣ 环回地址：用于自我测试，属于A类地址

NAT：network address translation 网络地址变换

其实某些机构并不需要连接到因特网，只需要与内部的主机通信，这样如果还是按照全球IP地址去分配，则会大大浪费IP地址。

例如，100个机构各有100台主机，假设现在100个机构都分配全球IP 地址，就需要1000个全球IP地址，但是现在从所有的全球IP地址里面划分出100 个IP地址专门用作一些只需内部通信的机构使用，即100个机构都使用这100个地址，只需要100个IP地址就解决问题了。这100个IP地址在计算机网络中被称为专用地址，且路由器看到专用地址时不转发，所以说专用地址作为目的地址是不可能在因特网上传送的。因特网已经规定了以下地址作为专用地址。

10.0.0.0~10.255.255.255 (相当于一个A类网络)。

172.16.0.0~172.31.255.255 (相当于16个连续的B类网络)。

192.168.0.0~192.168.255.255 (相当于256个连续的C类网络)。

这种采用专用IP地址的互联网络称为专用互联网或本地互联网,或直接称为专用网。专用IP地址也叫作可重用地址。问题出现了，如果专用网的主机想和因特网的主机通信，怎么办?这时NAT就诞生了。NAT就是将专用网内部使用的本地IP地址转换成有效的外部全球IP地址，使得整个专用网只需要一个全球IP地址就可以与因特网连通。

由于这些本地IP地址是可重用的，因此NAT技术可大大节省IP地址的消耗。使用NAT技术，需要在专用网连接到因特网的路由器上安装NAT软件。装有NAT软件的路由器叫作NAT路由器，它至少有-一个有效的外部全球IP地址。但是NAT并不能从根本上解决IP地址的耗尽问题,因为NAT并没有增加IP地址的个数。而真正解决IP地址耗尽问题的是IPv6

NAT使能路由器对于外部世界来说甚至不像一台路由器。相反NAT路由器对外界的行为就如同一个具有单一P地址的单一设备。在图中，所有离开家庭路由器流向更大因特网的报文都拥有一个源P地址138.76.29.7，且所有进入家庭的报文都拥有同一个目的P地址138.76.29.7。从本质上讲，NAT使能路由器对外界隐藏了家庭网络的细节。

家庭网络计算机是从哪儿得到其地址，路由器又是从哪儿得到它的单一IP地址的。在通常的情况下，答案是相同的，即DHCP!路由器从ISP的DHCP服务器得到它的地址，并且路由器运行一个DHCP服务器，为位于NAT-DHCP路由器控制的家庭网络地址空间中的计算机提供地址。

如果从广域网到达NAT路由器的所有数据报都有相同的目的IP地址（特别是对NAT 路由器广域网一侧的接口)，那么该路由器怎样知道它应将某个分组转发给哪个内部主机呢？

使用NAT路由器上的一张NAT转换表(NAT translation table),并且在表项中包含了端口号及其IP地址。

考虑上图中的例子。

1️⃣ 静态配置NAT表(Statically Configure NAT)

每有一个新的应用，就需要往NAT表中加一条表项

由网络管理员配置.

2️⃣ 动态配置Universal Plug and Play (UPnP)

通过软件自动添加

这类软件核心协议是IGD 协议(Internet Gateway Device Protocol)

两级IP地址划分的不够合理

IP地址利用率很低

给每个物理网络分配一个网络号会使路由表变得太大而使网络性能变坏

两级的IP地址不够灵活

于是有子网划分，使两级的IP地址变为三级的IP地址。划分子网是一个单位内部的事情，单位对外仍然表现为没有划分子网的网络。

划分子网的思路：从主机号借用若干比特作为子网号，而主机号也就相应减少了若干个比特，网络号不变，于是IP地址可记作 IP地址 : : = { <网络号>，<子网号>，<主机号> } \text{IP地址}::=\{\text{<网络号>，<子网号>，<主机号>}\} IP地址::={ <网络号>，<子网号>，<主机号>} 凡是从其他网络发送给本单位某个主机的IP数据报，仍然根据IP分组的目的网络号先找到连接在本单位网络上的路由器。然后此路由器在收到IP数据报后，再按照目的网络号和子网号找到目的子网，最后将IP数据报交给目的主机

子网划分与否是看不出来的，如果要告诉主机或路由器是否对一个A类、B类、C类网络进行了子网划分，则需要子网掩码。

子网掩码是一个与IP地址相对应的32位的二进制串，它由一串1和0组成。其中，1对应于IP地址中的网络号和子网号，0对应于主机号。因为1对1进行与操作，结果为1；1对0进行与操作，结果为0。所以使用一串1对网络号和子网号进行与操作，就可以得到网络号。

🏷 不管网络有没有划分子网，只要将子网掩码和IP地址进行逐位的“与”运算，就一定能得到子网地址

如果没有给出子网掩码，则采用默认的：A：255.0.0.0、B：255.255.0.0、C：255.255.255.0

IP地址：32位地址

网络地址：32位地址，网络部分不变，后面为0

子网地址：32位地址，子网以前不变，后面为0

classless interdomain routing无类别域间路由选择

a.b.c.d/x 代表高x 位是子网部分.

Dynamic Host Configuration Protocol动态主机配置协议：给主机动态地分配IP地址

他是一个应用层协议，DHCP报文使用UDP传输

它提供了即插即用连网的机制，这种机制允许一台计算机加入新的网络和获取IP地址而不用手工参与。例如，现在有一台主机需要 IP地址。在该主机启动时就可以向DHCP服务器广播发送报文，将源地址设置为0.0.0.0,目的地址设置为255.255.255.255(特殊IP地址)。这时主机就成为DHICP 的客户，发送广播报文主要是因为现在该主机还不知道DHCP在哪，这样在本网络上的所有主机都能够收到该广播报文，但是只有DHCP服务器能够应答。DHCP服务器先在其数据库中查找该计算机的配置信息，若找到，则返回找到的信息，若找不到，则从服务器的IP地址池中取一个地址分配给该计算机。

DHCP服务器和DHCP客户端的交换过程如下（4路广播）

1️⃣ DHCP客户端广播“DHCP discover”报文，试图找到网络中的DHCP服务器，服务器获得一个IP地址

2️⃣ DHCP服务器收到报文后，就向网络中广播“DHCP offer”报文，其中包括提供DHCP客户端的IP地址和相关配置信息

3️⃣ DHCP客户机收到“DHCP offer”报文，如果接受DHCP服务器所提供的相关参数，则通过广播“DHCP request”报文向DHCP服务器请求提供IP地址。

4️⃣ DHCP服务器广播“DHCP ack”报文，将IP地址分配给DHCP客户机。同时其他DHCP 服务器将其IP 地址收回。

DHCP允许网络上配置多台DHCP服务器，当DHCP客户发出DHCP请求时，就有可能收到多个应答报文。这时，DHCP客户只会挑选其中的一个，通常是挑选“最先到达的报文。

除了主机IP地址分配以外，DHCP还允许一台主机得到其他信息：

它的子网掩码

它的第一跳路由器地址（默认网关）

它的本地DNS服务器地址

Internet Control Message Protocol 网络控制报文协议

主机在发送数据报时，经常会由于各种原因发送错误，如路由器拥塞丢弃了或者传输计程中出现错误丢弃了(注意:如果是首部出错，当然可以发，但是一般都不发，因为首部中错很有可能是源IP地址都错了，所以即使发了源主机也不一定收到)。如果检测出错误的路由器或主机都能把这些错误报告通过一些控制消息告诉发送数据的主机，那么发送数据的主机就可根据ICMP报文确定发生错误的类型，并确定如何才能更好地重发失败的数据报(比如ICMP报文发过来的是改变路由，那么主机就不能继续按照这个路由线路发送了，需要用另外一条路由线路发送数据)。尽管这些控制消息并不传输用户数据，但是对于用户数据的传递起着重要的作用。

ICMP报文分为两种，即ICMP差错报告报文和ICMP询问报文。

1️⃣ ICMP差错报告报文的分类

1)终点不可达。当路由器或主机不能交付数据报时，就向源点发送终点不可达报文。

2)源站抑制。当路由器或主机由于拥塞而丢弃数据报时，就向源点发送源点抑制报文，使源点知道应当把数据报的发送速率放慢。

3)时间超过。当IP分组的TTL值被减为0后，路由器除了要丢弃该分组外，还要向源点发送时间超过报文。当终点在预先规定的时间内不能收到一个数据报的全部数据报片时，就把已收到的数据报片都丢弃，并向源点发送时间超过报文。

4)参数问题。当路由器或目的主机收到的数据报的首部中有字段的值不正确时，就丢弃该数据报，并向源点发送参数问题报文(现在一般都不发)。

5)改变路由(重定向)。路由器把改变路由报文发送给主机，让主机知道下次应将数措报发送给其他的路由器(比当前更好的路由)。

2️⃣ 询问报文的分类

1)有回送请求和回答报文。

2)时间戳请求和回答报文。

3)掩码地址请求和回答报文。

4)路由器询问和通告报文。

3️⃣ 不应发送ICMP差错报告报文的几种情况

1)对ICMP差错报告报文不再发送ICMP差错报告报文。

2)对第一个分片的数据报片的所有后续数据报片都不发送ICMP差错报告报文。

3)对具有组播地址的数据报都不发送ICMP差错报告报文。

4)对具有特殊地址(如127.0.0.0或0.0.0.0)的数据报不发送ICMP差错报告报文。

ICMP的两个典型应用，其实在日常生活中经常用，即ping和tracert.。

ping 用来测试两个主机之间的连通性。ping 使用了ICMP回送请求与回送回答报文。ping 是应用层直接使用网络层ICMP的例子，它没有通过传输层的TCP或UDP。

tracert（使用UDP）可以用来跟踪分组经过的路由，它工作在网络层。

由于IPv4地址即将耗尽，因此必须采取相应的办法去解决。前面已经介绍过采用网址转换（NAT)方法以节省全球IP地址和采用无分类编址（CIDR)使IP地址的分配更加理。这两种方法仅是优化了IPV4地址的使用方法，并没有从根本上解决IP地址的耗尽向题而采用具有更大地址空间的新版本的IPv6才能在真正意义上解决IPv4即将耗尽的问题。

总结IPv6的主要特点。

1)更大的地址空间。IPv6将地址从IPv4的32位增大到了128位。

2)扩展的地址层次结构。因为地址多了，所以可以划分更多的层次。

3)灵活的首部格式。

4)改进的选项。

5)允许协议继续扩充。

6)支持即插即用（自动配置）。

7)支持资源的预分配。

8)IPv6首部长度必须是8B的整数倍，而IPv4首部是4B的整数倍

虽然IPv6与IPv4不兼容，但总的来说它跟所有其他的因特网协议兼容，包括TCP、UDP、ICMP、DNS等，只是在少数地方做了必要的修改（大部分是为了处理长的地址）。IPv6相当好地满足了预定的目标，主要体现在以下3个方面。

1)IPv6第一个主要改进也是最重要的，即IPv6有比IPv4长得多的地址。

2)IPv6第二个主要改进是简化了IP分组的基本首部，它包含8个段（IPv4是12个段）。这一改变使得路由器能够更快地处理数据报，从而可以改善吞吐率。

3)IPv6第三个主要改进是IPv6更好地支持选项。这一改变对新的分组首部很重要，因为一些从前是必要的段现在变成可选的了。此外，表示选项的方式也有所不同，使得路由器能够简单地跳过与它们无关的选项。这一特征加快了数据报处理速度。

IPv6的首部格式如下（一共40B）：

优先级priority：确定流中数据报的优先级

流标号flow label：识别相同“流”的数据报。

下一个报头next header：识别数据的上层协议

IPv4和IPv6混合的网络将如何运行?

隧道技术Tunneling

双栈技术Dual-stack

1️⃣ 双栈技术Dual-stack

到达边缘路由器的时候将包进行转换（IPv4<->IPv6）

2️⃣ 隧道技术Tunneling

将IPv6(IPv4)的包整个封装到IPv4(IPv6)的包中

隧道技术不止这一种

路由器转发分组是通过路由表转发的，而路由表是通过各种算法得到的。如果从路由算法能否随网络的通信量或拓扑自适应地进行调整变化来划分，则只有两大类，即静态路由选择策略（又称为非自适应路由选择）与动态路由选择策略（又称为自适应路由选择）。静态路由选择的特点是简单和开销小，但不能及时适应网络状态的变化。对于很小的网络，完全可以采用静态路由选择，自己手动配置每一条路由。动态路由选择的特点是能较好地适应网络状态的变化，但实现起来比较复杂，开销也较大。因此，动态路由适用于较复杂的网络。

现代的计算机网络通常使用动态路由选择算法。动态路由算法又可分为两种基本类型：距离－向量路由算法和链路状态路由算法。

全局性的路由算法：链路状态路由算法，维护一个全局的拓扑图。

分散性的路由算法：距离－向量路由算法

不要求维护一个全局的拓扑图

距离向量(Distance-Vector,DV)算法是一种迭代的、异步的和分布式的算法，而LS算法是一种使用全局信息的算法。

1️⃣ 分布式的：因为每个节点都要从一个或多个直接相连邻居接收某些信息，执行计算，然后将其计算结果分发给邻居。

2️⃣ 迭代的：此过程一直要持续到邻居之间无更多信息要交换为止。此算法是自我终止的，即没有计算应该停止的信号，它就停止了。

3️⃣ 异步的：是因为它不要求所有节点相互之间步伐一致地操作。

4️⃣ 自终止性

令 d x ( y ) d_x(\text{y}) dx​(y)是从结点x到结点y的最低开销路径的开销，则该路径开销与Bellman-Ford方程相关 d x ( y ) = m i n v { c ( x , v ) + d v ( y ) } d_x(\text{y})=min_v\{c(x,v)+d_v(\text{y})\} dx​(y)=minv​{ c(x,v)+dv​(y)} 方程中的 m i n v min_v minv​是对于x的所有邻居的。Bellman-Ford方程是相当直观的。实际上，从x到v遍历之后，如果我们接下来取从v到y的最低开销路径，则该路径开销将是 c ( x , v ) + d v ( y ) c(x,v)+d_v(y) c(x,v)+dv​(y)。因此我们必须通过遍历某些邻居v开始，从x到y的最低开销是对所有邻居v的 c ( x , v ) + d v ( y ) c(x,v)+d_v(y) c(x,v)+dv​(y)的最小值。

令 D x = [ D x ( y ) : y ∈ N ] \pmb{D}_x=[\pmb{D}_x(y):y\in N] DDDx​=[DDDx​(y):y∈N]是节点x的距离向量，该向量是从x到在N中的所有其他节点y的开销估计向量，使用DV算法，每个结点x维护以下路由选择信息