首页网络设计正文

计算机网络基础笔记手写（计算机应用基础笔记怎么写）

网络设计 2年前(02-07) 337

本篇文章给大家谈谈计算机网络基础笔记手写，以及计算机应用基础笔记怎么写对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。本文目录一览： 1、计算机网络自学笔记:TCP

本篇文章给大家谈谈计算机网络基础笔记手写，以及计算机应用基础笔记怎么写对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

1、计算机网络自学笔记:TCP
2、计算机网络（3）
3、计算机网络自学笔记：选路算法

计算机网络自学笔记:TCP

如果你在学习这门课程，仅仅为了理解网络工作原理，那么只要了解TCP是可靠传输，数据传输丢失时会重传就可以了。如果你还要参加研究生考试或者公司面试等，那么下面内容很有可能成为考查的知识点，主要的重点是序号/确认号的编码、超时定时器的设置、可靠传输和连接的管理。

1 TCP连接

TCP面向连接，在一个应用进程开始向另一个应用进程发送数据之前，这两个进程必须先相互“握手”，即它们必须相互发送某些预备报文段，以建立连接。连接的实质是双方都初始化与连接相关的发送/接收缓冲区，以及许多TCP状态变量。

这种“连接”不是一条如电话网络中端到端的电路，因为它们的状态完全保留在两个端系统中。

TCP连接提供的是全双工服务，应用层数据就可在从进程B流向进程A的同时，也从进程A流向进程B。

TCP连接也总是点对点的，即在单个发送方与单个接收方之间建立连接。

一个客户机进程向服务器进程发送数据时，客户机进程通过套接字传递数据流。

客户机操作系统中运行的 TCP软件模块首先将这些数据放到该连接的发送缓存里，然后会不时地从发送缓存里取出一块数据发送。

TCP可从缓存中取出并放入报文段中发送的数据量受限于最大报文段长MSS，通常由最大链路层帧长度来决定(也就是底层的通信链路决定)。例如一个链路层帧的最大长度1500字节，除去数据报头部长度20字节，TCP报文段的头部长度20字节，MSS为1460字节。

报文段被往下传给网络层，网络层将其封装在网络层IP数据报中。然后这些数据报被发送到网络中。

当TCP在另一端接收到一个报文段后，该报文段的数据就被放人该连接的接收缓存中。应用程序从接收缓存中读取数据流(注意是应用程序来读，不是操作系统推送)。

TCP连接的每一端都有各自的发送缓存和接收缓存。

因此TCP连接的组成包括:主机上的缓存、控制变量和与一个进程连接的套接字变量名，以及另一台主机上的一套缓存、控制变量和与一个进程连接的套接字。

在这两台主机之间的路由器、交换机中，没有为该连接分配任何缓存和控制变量。

2报文段结构

TCP报文段由首部字段和一个数据字段组成。数据字段包含有应用层数据。

由于MSS限制了报文段数据字段的最大长度。当TCP发送一个大文件时，TCP通常是将文件划分成长度为MSS的若干块。

TCP报文段的结构。

首部包括源端口号和目的端口号，它用于多路复用/多路分解来自或送至上层应用的数据。另外，TCP首部也包括校验和字段。报文段首部还包含下列字段:

32比特的序号字段和32比特的确认号字段。这些字段被TCP发送方和接收方用来实现可靠数据传输服务。

16比特的接收窗口字段，该字段用于流量控制。该字段用于指示接收方能够接受的字节数量。

4比特的首部长度字段,该字段指示以32比特的字为单位的TCP首部长度。一般TCP首部的长度就是20字节。

可选与变长的选项字段,该字段用于当发送方与接收方协商最大报文段长度，或在高速网络环境下用作窗口调节因子时使用。

标志字段ACK比特用于指示确认字段中的ACK值的有效性，即该报文段包括一个对已被成功接收报文段的确认。 SYN和FIN比特用于连接建立和拆除。 PSH、URG和紧急指针字段通常没有使用。

•序号和确认号

TCP报文段首部两个最重要的字段是序号字段和确认号字段。

TCP把数据看成一个无结构的但是有序的字节流。TCP序号是建立在传送的字节流之上，而不是建立在传送的报文段的序列之上。

一个报文段的序号是该报文段首字节在字节流中的编号。

例如，***设主机A上的一个进程想通过一条TCP连接向主机B上的一个进程发送一个数据流。主机A中的TCP将对数据流中的每一个字节进行编号。***定数据流由一个包含4500字节的文件组成(可以理解为应用程序调用send函数传递过来的数据长度)，MSS为1000字节(链路层一次能够传输的字节数)，如果主机决定数据流的首字节编号是7。TCP模块将为该数据流构建5个报文段(也就是分5个IP数据报)。第一个报文段的序号被赋为7;第二个报文段的序号被赋为1007,第三个报文段的序号被赋为2007，以此类推。前面4个报文段的长度是1000，最后一个是500。

确认号要比序号难理解一些。前面讲过，TCP是全双工的，因此主机A在向主机B发送数据的同时，也可能接收来自主机B的数据。从主机B到达的每个报文段中的序号字段包含了从B流向A的数据的起始位置。因此主机B填充进报文段的确认号是主机B期望从主机A收到的下一报文段首字节的序号。

***设主机B已收到了来自主机A编号为7-1006的所有字节，同时***设它要发送一个报文段给主机A。主机B等待主机A的数据流中字节1007及后续所有字节。所以，主机B会在它发往主机A的报文段的确认号字段中填上1007。

再举一个例子，***设主机B已收到一个来自主机A的包含字节7-1006的报文段，以及另一个包含字节2007-3006的报文段。由于某种原因，主机A还没有收到字节1007-2006的报文段。

在这个例子中，主机A为了重组主机B的数据流，仍在等待字节1007。因此，A在收到包含字节2007-3006的报文段时，将会又一次在确认号字段中包含1007。因为TCP只确认数据流中至第一个丢失报文段之前的字节数据，所以TCP被称为是***用累积确认。

TCP的实现有两个基本的选择:

1接收方立即丢弃失序报文段;

2接收方保留失序的字节，并等待缺少的字节以填补该间隔。

一条TCP连接的双方均可随机地选择初始序号。这样做可以减少将那些仍在网络中的来自两台主机之间先前连接的报文段，误认为是新建连接所产生的有效报文段的可能性。

•例子telnet

Telnet由是一个用于远程登录的应用层协议。它运行在TCP之上，被设计成可在任意一对主机之间工作。

***设主机A发起一个与主机B的Telnet会话。因为是主机A发起该会话，因此主机A被标记为客户机，主机B被标记为服务器。用户键入的每个字符(在客户机端)都会被发送至远程主机。远程主机收到后会***一个相同的字符发回客户机，并显示在Telnet用户的屏幕上。这种“回显”用于确保由用户发送的字符已经被远程主机收到并处理。因此，在从用户击键到字符显示在用户屏幕上之间的这段时间内，每个字符在网络中传输了两次。

现在***设用户输入了一个字符“C”，***设客户机和服务器的起始序号分别是42和79。前面讲过，一个报文段的序号就是该报文段数据字段首字节的序号。因此，客户机发送的第一个报文段的序号为42，服务器发送的第一个报文段的序号为79。前面讲过，确认号就是主机期待的数据的下一个字节序号。在TCP连接建立后但没有发送任何数据之前，客户机等待字节79，而服务器等待字节42。

如图所示，共发了3个报文段。第一个报文段是由客户机发往服务器，其数据字段里包含一字节的字符“C”的ASCII码，其序号字段里是42。另外，由于客户机还没有接收到来自服务器的任何数据，因此该报文段中的确认号字段里是79。

第二个报文段是由服务器发往客户机。它有两个目的:第一个目的是为服务器所收到的数据提供确认。服务器通过在确认号字段中填入43，告诉客户机它已经成功地收到字节42及以前的所有字节，现在正等待着字节43的出现。第二个目的是回显字符“C”。因此，在第二个报文段的数据字段里填入的是字符“C”的ASCII码，第二个报文段的序号为79，它是该TCP连接上从服务器到客户机的数据流的起始序号，也是服务器要发送的第一个字节的数据。

这里客户机到服务器的数据的确认被装载在一个服务器到客户机的数据的报文段中，这种确认被称为是捎带确认.

第三个报文段是从客户机发往服务器的。它的唯一目的是确认已从服务器收到的数据。

3往返时延的估计与超时

TCP如同前面所讲的rdt协议一样，***用超时/重传机制来处理报文段的丢失问题。最重要的一个问题就是超时间隔长度的设置。显然，超时间隔必须大于TCP连接的往返时延RTT，即从一个报文段发出到收到其确认时。否则会造成不必要的重传。

•估计往返时延

TCP估计发送方与接收方之间的往返时延是通过***集报文段的样本RTT来实现的，就是从某报文段被发出到对该报文段的确认被收到之间的时间长度。

也就是说TCP为一个已发送的但目前尚未被确认的报文段估计sampleRTT，从而产生一个接近每个RTT的***样值。但是，TCP不会为重传的报文段计算RTT。

为了估计一个典型的RTT，***取了某种对RTT取平均值的办法。TCP据下列公式来更新

EstimatedRTT=(1-)*EstimatedRTT+*SampleRTT

即估计RTT的新值是由以前估计的RTT值与sampleRTT新值加权组合而成的。

参考值是a=0.125，因此是一个加权平均值。显然这个加权平均对最新样本赋予的权值

要大于对老样本赋予的权值。因为越新的样本能更好地反映出网络当前的拥塞情况。从统计学观点来讲，这种平均被称为指数加权移动平均

除了估算RTT外，还需要测量RTT的变化，RTT偏差的程度，因为直接使用平均值设置计时器会有问题(太灵敏)。

DevRTT=(1-β)*DevRTT+β*|SampleRTT-EstimatedRTT|

RTT偏差也使用了指数加权移动平均。B取值0.25.

•设置和管理重传超时间隔

***设已经得到了估计RTT值和RTT偏差值，那么TCP超时间隔应该用什么值呢?TCP将超时间隔设置成大于等于估计RTT值和4倍的RTT偏差值,否则将造成不必要的重传。但是超时间隔也不应该比估计RTT值大太多，否则当报文段丢失时，TCP不能很快地重传该报文段，从而将给上层应用带来很大的数据传输时延。因此，要求将超时间隔设为估计RTT值加上一定余量。当估计RTT值波动较大时，这个余最应该大些;当波动比较小时，这个余量应该小些。因此使用4倍的偏差值来设置重传时间。

TimeoutInterval=EstimatedRTT+4*DevRTT

4可信数据传输

因特网的网络层服务是不可靠的。IP不保证数据报的交付，不保证数据报的按序交付，也不保证数据报中数据的完整性。

TCP在IP不可靠的尽力而为服务基础上建立了一种可靠数据传输服务。

TCP提供可靠数据传输的方法涉及前面学过的许多原理。

TCP***用流水线协议、累计确认。

TCP推荐的定时器管理过程使用单一的重传定时器，即使有多个已发送但还未被确认的报文段也一样。重传由超时和多个ACK触发。

在TCP发送方有3种与发送和重传有关的主要***:从上层应用程序接收数据，定时器超时和收到确认ACK。

从上层应用程序接收数据。一旦这个***发生，TCP就从应用程序接收数据，将数据封装在一个报文段中，并将该报文段交给IP。注意到每一个报文段都包含一个序号，这个序号就是该报文段第一个数据字节的字节流编号。如果定时器还没有计时，则当报文段被传给IP时，TCP就启动一个该定时器。

第二个***是超时。TCP通过重传引起超时的报文段来响应超时***。然后TCP重启定时器。

第三个***是一个来自接收方的确认报文段(ACK)。当该***发生时，TCP将ACK的值y与变量SendBase(发送窗口的基地址)进行比较。TCP状态变量SendBase是最早未被确认的字节的序号。就是指接收方已正确按序接收到数据的最后一个字节的序号。TCP***用累积确认，所以y确认了字节编号在y之前的所有字节都已经收到。如果YSendBase,则该ACK是在确认一个或多个先前未被确认的报文段。因此发送方更新其SendBase变量，相当于发送窗口向前移动。

另外，如果当前有未被确认的报文段，TCP还要重新启动定时器。

快速重传

超时触发重传存在的另一个问题是超时周期可能相对较长。当一个报文段丢失时，这种长超时周期迫使发送方等待很长时间才重传丢失的分组，因而增加了端到端时延。所以通常发送方可在超时***发生之前通过观察冗余ACK来检测丢包情况。

冗余ACK就是接收方再次确认某个报文段的ACK，而发送方先前已经收到对该报文段的确认。

当TCP接收方收到一个序号比所期望的序号大的报文段时，它认为检测到了数据流中的一个间隔，即有报文段丢失。这个间隔可能是由于在网络中报文段丢失或重新排序造成的。因为TCP使用累计确认，所以接收方不向发送方发回否定确认，而是对最后一个正确接收报文段进行重复确认(即产生一个冗余ACK)

如果TCP发送方接收到对相同报文段的3个冗余ACK.它就认为跟在这个已被确认过3次的报文段之后的报文段已经丢失。一旦收到3个冗余ACK，TCP就执行快速重传，

即在该报文段的定时器过期之前重传丢失的报文段。

5流量控制

前面讲过，一条TCP连接双方的主机都为该连接设置了接收缓存。当该TCP连接收到正确、按序的字节后，它就将数据放入接收缓存。相关联的应用进程会从该缓存中读取数据，但没必要数据刚一到达就立即读取。事实上，接收方应用也许正忙于其他任务，甚至要过很长时间后才去读取该数据。如果应用程序读取数据时相当缓慢，而发送方发送数据太多、太快，会很容易使这个连接的接收缓存溢出。

TCP为应用程序提供了流量控制服务以消除发送方导致接收方缓存溢出的可能性。因此，可以说流量控制是一个速度匹配服务，即发送方的发送速率与接收方应用程序的读速率相匹配。

前面提到过，TCP发送方也可能因为IP网络的拥塞而被限制，这种形式的发送方的控制被称为拥塞控制(congestioncontrol)。

TCP通过让接收方维护一个称为接收窗口的变量来提供流量控制。接收窗口用于告诉发送方，该接收方还有多少可用的缓存空间。因为TCP是全双工通信，在连接两端的发送方都各自维护一个接收窗口变量。主机把当前的空闲接收缓存大小值放入它发给对方主机的报文段接收窗口字段中，通知对方它在该连接的缓存中还有多少可用空间。

6 TCP连接管理

客户机中的TCP会用以下方式与服务器建立一条TCP连接:

第一步: 客户机端首先向服务器发送一个SNY比特被置为1报文段。该报文段中不包含应用层数据，这个特殊报文段被称为SYN报文段。另外，客户机会选择一个起始序号，并将其放置到报文段的序号字段中。为了避免某些安全性攻击，这里一般随机选择序号。

第二步: 一旦包含TCP报文段的用户数据报到达服务器主机，服务器会从该数据报中提取出TCPSYN报文段，为该TCP连接分配TCP缓存和控制变量，并向客户机TCP发送允许连接的报文段。这个允许连接的报文段还是不包含应用层数据。但是，在报文段的首部却包含3个重要的信息。

首先，SYN比特被置为1。其次，该 TCP报文段首部的确认号字段被置为客户端序号+1最后，服务器选择自己的初始序号，并将其放置到TCP报文段首部的序号字段中。这个允许连接的报文段实际上表明了:“我收到了你要求建立连接的、带有初始序号的分组。我同意建立该连接，我自己的初始序号是XX”。这个同意连接的报文段通常被称为SYN+ACK报文段。

第三步: 在收到SYN+ACK报文段后，客户机也要给该连接分配缓存和控制变量。客户机主机还会向服务器发送另外一个报文段，这个报文段对服务器允许连接的报文段进行了确认。因为连接已经建立了，所以该ACK比特被置为1，称为ACK报文段，可以携带数据。

一旦以上3步完成，客户机和服务器就可以相互发送含有数据的报文段了。

为了建立连接，在两台主机之间发送了3个分组，这种连接建立过程通常被称为三次握手(SNY、SYN+ACK、ACK，ACK报文段可以携带数据) 。这个过程发生在客户机connect()服务器，服务器accept()客户连接的阶段。

***设客户机应用程序决定要关闭该连接。(注意，服务器也能选择关闭该连接)客户机发送一个FIN比特被置为1的TCP报文段，并进人FINWAIT1状态。

当处在FINWAIT1状态时，客户机TCP等待一个来自服务器的带有ACK确认信息的TCP报文段。当它收到该报文段时，客户机TCP进入FINWAIT2状态。

当处在FINWAIT2状态时，客户机等待来自服务器的FIN比特被置为1的另一个报文段，

收到该报文段后，客户机TCP对服务器的报文段进行ACK确认，并进入TIME_WAIT状态。TIME_WAIT状态使得TCP客户机重传最终确认报文，以防该ACK丢失。在TIME_WAIT状态中所消耗的时间是与具体实现有关的，一般是30秒或更多时间。

经过等待后，连接正式关闭，客户机端所有与连接有关的***将被释放。因此TCP连接的关闭需要客户端和服务器端互相交换连接关闭的FIN、ACK置位报文段。

计算机网络基础笔记手写（计算机应用基础笔记怎么写）

计算机网络（3）

课程笔记，笔记主要来源于《计算机网络（第7版）》，侵删

简述/引言：

信道是链路的一个抽象，并非实际的描述。

数据链路层有两种类型：

链路：一个结点到相邻接待您的一段物理线路（有限或无线），中间没有其他的交换结点。

数据链路：实现协议的硬件和软件 + 链路 = 数据链路

网络适配器：一般都包括了数据链路层和物理层这两层的功能

*规程：早期的数据通信协议

帧：点对点信道的数据链路层的协议数据单元

IP数据报：网路层协议数据单元（数据报、分组、包）

三个基本问题：封装成帧、透明传输、差错检测

目前点对点链路中，使用最广泛的数据链路层协议就是PPP协议

PPP协议：用户计算机和ISP进行通信时所使用的数据链路层协议

PPP协议应满足的需求（主要部分）：

PPP协议的三个组成部分：

首部和尾部分别为四个字段和两个字段

首部：

局域网的主要特点：网络为一个单位所拥有，且地理范围和站点数目均有限

*局域网具有的优点：

局域网按网络拓扑进行分类有：星形网、环线网、总线网（现使用最多）

共享信道的方法：

以太网的两个标准：DIX Ethernet V2 和 IEEE的802.3标准

802.3标准把局域网的数据链路层拆成两个子层：逻辑链路控制LLC子层（偏网络层）、媒体接入控制MAC子层（偏物理层）

适配器（网络接口卡/网卡）的作用：连接计算机与外界局域网

早期的以太网是多个计算机连接在一条总线上的

总线的特点：广播通信方式，实现一对一通信

为了通信的简便，以太网***取了两种措施：

CSMA/CD协议（载波监听多点接入/碰撞检测）：

CSMA/CD协议特性：

关于碰撞：

集线器：在星型拓扑网络的中心增加的一种可靠性非常高的设备

集线器的特点：

令，为单程端到端时延，为帧的发送时间

则越小，以太网的信道利用率就越高

极限信道率

只有当参数远小于1才能得到尽可能的信道利用率

MAC地址：48位（IEEE 802标准），是局域网中的硬件地址/物理地址，是每个站的“名字”或标识符（固化在适配器的ROM中的地址，一般不可更改）

IP地址：32位，代表了一台计算机，是终端地址（可更改）

MAC帧之间传送要有一定的时间间隔

适配器对接收到的MAC帧的处理：先检查MAC帧中的目的地址，若是本站的则收下再进行其它处理，否则直接丢弃

接收到的MAC帧有三种：

MAC帧的格式

两种MAC帧格式标准：DIX Ethernet V2标准（以太网V2标准）、IEEE的802.3标准

MAC帧的类型字段用来标志上一层用的什么协议，以便把接收到的MAC帧的数据上交给上一层的这个协议

IEEE 802.3标准规定的无效MAC帧：

（原理不变，扩大距离）

使用光纤和一对光纤调节器

使用多个集线器

好处：

缺点：

最初使用网桥

网桥的传输不会改变MAC帧的源地址

网桥的作用：对MAC帧的目的地址进行转发和过滤

网桥的优点：

网桥的缺点：

后改用以太网交换机

以太网交换机 / 交换式集线器：工作在数据链路层，实质上就是一个多接口的网桥

以太网交换机特点：是一种透明网桥（一种即插即用设备），其内部的帧交换表（地址表）是通过自学习算法自动转建立起来的

以太网交换机可实现虚拟局域网（VLAN）

虚拟局域网：由一些局域网网段构成的与物理位置无关的逻辑组

计算机网络自学笔记：选路算法

网络层必须确定从发送方到接收方分组所经过的路径。选路就是在网络中的路由器里的给某个数据报确定好路径(即路由)。

一台主机通常直接与一台路由器相连接，该路由器即为该主机的默认路由器，又称为该主机的默认***。每当某主机向外部网络发送一个分组时，该分组都被传送给它的默认***。

如果将源主机的默认***称为源路由器,把目的主机的默认***称为目的路由器。为一个分组从源主机到目的主机选路的问题于是可归结为从源路由器到目的路由器的选路问题。

选路算法的目标很简单:给定一组路由器以及连接路由器的链路，选路算法要找到一条从源路由器到目的路由器的最好路径，通常一条好路径是指具有最低费用的路径。

图 G=(N，E)是一个 N 个节点和 E 条边的集合，其中每条边是来自 N 的一对节点。在网络选路的环境中，节点表示路由器，这是做出分组转发决定的节点，连接节点的边表示路由器之间的物理链路。

一条边有一个值表示它的费用。通常一条边的费用可反映出对应链路的物理长度、链路速度或与该链路相关的费用。

对于 E 中的任一条边(xy)可以用 c(xy )表示节点 x 和 y 间边的费用。一般考虑的都是无向图，因此边(xy)与边(y x)是相同的并且开销相等。节点 y 也被称为节点 x 的邻居。

在图中为各条边指派了费用后，选路算法的目标自然是找出从源到目的间的最低费用路径。图 G=(N，E)中的一条路径(Path)是一个节点的序列，使得每一对以(x1,x2)， (x2,x3)，…，是 E 中的边。路径的费用是沿着路径所有边费用的总和。

从广义上来说，我们对选路算法分类的一种方法就是根据该算法是全局性还是分布式来区分的。

.全局选路算法：用完整的、全局性的网络信息来计算从源到目的之间的最低费用路径。

实际上，具有全局状态信息的算法常被称作链路状态 LS 算法，因为该算法必须知道网络中每条链路的费用。

.分布式选路算法：以迭代的、分布式的方式计算出最低费用路径。通过迭代计算并与相邻节点交换信息，逐渐计算出到达某目的节点或一组目的节点的最低费用路径。

DV 算法是分布式选路算法，因为每个节点维护到网络中的所有其他节点的费用(距离)估计的矢量。

选路算法的第二种广义分类方法是根据算法是静态的还是动态的来分类。

一：链路状态选路算法 LS

在链路状态算法中，通过让每个节点向所有其他路由器广播链路状态分组，每个链路状态分组包含它所连接的链路的特征和费用，从而网络中每个节点都建立了关于整个网络的拓扑。

Dijkstra 算法计算从源节点到网络中所有其他节点的最低费用路径.

Dijkstra 算法是迭代算法，经算法的第 k 次迭代后，可知道到 k 个目的节点的最低费用路径。

定义下列记号:

D(V)随着算法进行本次迭代，从源节点到目的节点的最低费用路径的费用。

P(v)从源节点到目的节点 v 沿着当前最低费用路径的前一节点(，的邻居)。

N`节点子集；如果从源节点到目的节点 v 的最低费用路径已找到，那么 v 在 N`中。

Dijkstra 全局选路算法由一个初始化步骤和循环组成。循环执行的次数与网络中的节点个数相同。在结束时，算***计算出从源节点 u 到网络中每个其他节点的最短路径。

考虑图中的网络，计算从 u 到所有可能目的地的最低费用路径。

.在初始化阶段，从 u 到与其直接相连的邻居 v、x、w 的当前已知最低费用路径分别初始化为 2，1 和 5。到 y 与 z 的费用被设为无穷大，因为它们不直接与 u 连接。

.在第一次迭代时，需要检查那些还未加到集合 N`中的节点，找出在前一次迭代结束时具有最低费用的节点。那个节点是 x 其费用是 1，因此 x 被加到集合 N`中。然后更新所有节点的 D(v)，产生下表中第 2 行(步骤)所示的结果。到 v 的路径费用未变。经过节点 x 到 w 的路径的费用被确定为 4。因此沿从 u 开始的最短路径到 w 的前一个节点被设为 x。类似地，到 y 经过 x 的费用被计算为 2，且该表项也被更新。

.在第二次迭代时，节点 v 与 y 被发现具有最低费用路径 2。任意选择将 y 加到集合 N` 中，使得 N’中含有 u、x 和 y。通过更新，产生如表中第 3 行所示的结果。

.以此类推…

当 LS 算法结束时，对于每个节点都得到从源节点沿着它的最低费用路径的前继节点，对于每个前继节点，又有它的前继节点，按照此方式可以构建从源节点到所有目的节点的完整路径。

根据从 u 出发的最短路径，可以构建一个节点(如节点 u)的转发表。

二距离矢量选路算法 DV

LS 算法是一种使用全局信息的算法，而距离矢量算法是一种迭代的、异步的和分布式的算法。

Bellman-Ford 方程：

设 dx(y)是从节点 x 到节点 y 的最低费用路径的费用，则有 dx(y) = min {c(x,v) + dv(y) }

PS：方程中的 min，是指取遍 x 的所有邻居。

Bellman-Ford 方程含义相当直观，意思是从 x 节点出发到 y 的最低费用路径肯定经过 x 的某个邻居，而且 x 到这个邻居的费用加上这个邻居到达目的节点 y 费用之和在所有路径中其总费用是最小的。实际上，从 x 到 v 遍历之后，如果取从 v 到 y 的最低费用路径，该路径费用将是 c(x,v)+ dv(y)。因此必须从遍历某些邻居 v 开始，从 x 到 y 的最低费用是对所有邻居的 c(x,v)+dv(y)的最小值。

在该 DV 算法中，当节点 x 看到它的直接相连的链路费用变化，或从某个邻居接收到一个距离矢量的更新时，就根据 Bellman-Ford 方程更新其距离矢量表。

三 LS 与 DV 选路算法的比较

DV 和 LS 算法***用不同的方法来解决计算选路问题。

在 DV 算法中，每个节点仅与它的直接相连邻居交换信息，但它为它的邻居提供了从其自己到网络中(它所知道的)所有其他节点的最低费用估计。

在 LS 算法中，每个节点(经广播)与所有其他节点交换信息，但它仅告诉它们与它直接相连链路的费用。

·报文复杂性：

LS 算法要求每个节点都知道网络中每条链路的费用，需要发送 O(nE)个消息。

DV 算法要求在每次迭代时，在两个直接相连邻居之间交换报文，算法收敛所需的时间依赖于许多因素。当链路费用改变时，DV 算法仅当在会导致该节点的最低费用路径发生改变时，才传播已改变的链路费用。

·收效速度：

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

•健壮性：在 LS 算法中，如果一台路由器发生故障、或受到破坏，路由器会向其连接的链路广播不正确费用，导致整个网络的错误。

在 Dv 算法下，每次迭代时，其中一个节点的计算结果会传递给它的邻居，然后在下次迭代时再间接地传递给邻居的邻居。在这种情况下，DV 算法中一个不正确的计算结果也会扩散到整个网络。