计算机网络中的ls算法

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

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

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

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

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

图 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 算法中一个不正确的计算结果也会扩散到整个网络。

四.层次选路

两个原因导致层次的选路策略：

•规模： 随着路由器数目增长，选路信息的计算、存储及通信的开销逐渐增高。

•管理自治： 一般来说，一个单位都会要求按自己的意愿运行路由器(如运行其选择的某 种选路算法)，或对外部隐藏其内部网络的细节。

层次的选路策略是通过将路由器划分成自治系统 AS 来实施的。

每个 AS 由一组通常在相同管理控制下的路由器组成(例如由相同的 ISP 运营或属于相同 的公司网络)。在相同的 AS 内的路由器都全部运行同样的选路算法。

在一个自治系统内运行的选路算法叫做自治系统内部选路协议。 在一个 AS 边缘的一台 或多台路由器，来负责向本 AS 之外的目的地转发分组，这些路由器被称为网关路由器

在各 AS 之间，AS 运行相同的自治系统间选路协议。

2. 在网络图中什么是ES、EF、LS、LF、TF、FF并解释它们的含义

在网络图中ES、EF、LS、LF、TF、FF是网络图中标注时间参数，含义如下：

ES = Earliest Start time（最早开始时间）。

EF = Earliest Finish time（最早结束时间）。

LS = Latest Start time（最晚开始时间）。

LF = Latest Finish time（最晚结束时间）。

TF = Total Float time（总浮动时间，总时差）。

FF = Free Float time（自由浮动时间，自由时差）。

相关资料

在网络图中标注时间参数（es、ef、ls、lf、tf、lf及其组合）CCProject除显示这些参数外，我们还根据客户需求，添加了一些其他的显示方式。

如果网络图比较复杂，可以拖动一下工作名称、工期数字或者参数的位置，尽量避免重叠。

3. 《计算机网络-自顶向下方法》第四章-网络层 要点

网络层的作用：实现主机到主机的通信服务，将分组从一台发送主机移动到一台接收主机。

1、转发涉及分组在单一的路由器中从一条入链路到一条出链路的传送。
2、路由选择涉及一个网络的所有路由器，它们经路由选择协议共同交互，以决定分组从源到目的地结点所采用的路径。计算这些路径的算法称为路由选择算法。

每台路由器都有一张转发表，路由器通过检查到达分组首部字段的值来转发分组，然后使用该值在该路由器的转发表中索引查找。路由选择算法决定了插入路由器转发表中的值。

路由选择算法可能是集中式的，或者是分布式的。但在这两种情况下，都是路由器接收路由选择协议报文，该信息被用于配置其转发表。

网络层也能在两台主机之间提供无连接服务或连接服务。同在运输层的面向连接服务和无连接服务类似，连接服务需要握手步骤，无连接服务不需要握手。但它们之间也有差异：
1、 在网络层中，这些服务是由网络层向运输层提供的主机到主机的服务。在运输层中，这些服务则是运输层向应用层提供的进程到进程的服务。
2、 在网络层提供无连接服务的计算机网络称为数据报网络；在网络层提供连接服务的计算机网络称为虚电路网络。
3、 在运输层实现面向连接的服务与在网络层实现连接服务是根本不同的。运输层面向连接服务是在位于网络边缘的端系统中实现的；网络层连接服务除了在端系统中，也在位于网络核心的路由器中实现。（原因很简单：端系统和路由器都有网络层）

虚电路网络和数据报网络是计算机网络的两种基本类型。在作出转发决定时，它们使用了非常不同的信息。

IP地址有32比特，如果路由器转发表采用“蛮力实现”将对每个可能的目的地址有一个表项。因为有超过40亿个可能的地址，这种选择完全不可能（即使用二分查找也十分慢）。
我们转发表的表项可以设计为几个表项，每个表项匹配一定范围的目的地址，比如有四个表项

（你可能也会考虑到，IP地址有32比特，如果每个路由器设计为只有2个表项，那么也只需要有32个路由器就可以唯一确定这40亿个地址中的一个。）

最长前缀匹配规则，是在转发表中寻找最长的匹配项，并向与最长前缀匹配相关联的链路接口转发分组。这种规则是为了与因特网的编址规则相适应。

1、输入端口
“使用转发表查找输出端口”是输入端口最重要的操作（当然还有其他一些操作）。输入端口执行完这些所需的操作后，就把该分组发送进入交换结构。如果来自其他输入端口的分组当前正在使用交换结构，一个分组可能会在进入交换结构时被暂时阻塞，在输入端口处排队，并等待稍后被及时调度以通过交换结构。
2、交换结构
交换结构的三种实现方式

3、输出端口
分组调度程序 处理在输出端口中排队的分组
4、路由选择处理器

</br>

</br>

IP协议版本4，简称为IPv4；IP协议版本6，简称为IPv6。

如上图所示，网络层有三个主要的组件
1、IP协议
2、路由选择协议
3、ICMP协议 (Internet Control Message Protocol, 因特网控制报文协议)

</br>

不是所有链路层协议都能承载相同长度的网络层分组。有的协议能承载大数据报，而有的协议只能承载小分组。例如，以太网帧能够承载不超过1500字节的数据，而某些广域网链路的帧可承载不超过576字节的数据。

一个链路层帧能承载的最大数据量叫做最大传送单元(Maximun Transmission Unit, MTU)

所以链路层协议的MTU严格限制着IP数据报的长度。这也还不是主要的问题，问题在于发送方与目的地路径上的每段链路可能使用不同的链路层协议，且每种协议可能具有不同的MTU。

举个例子：假定从某条链路收到一个IP数据报，通过检查转发表确定出链路，并且该出链路的MTU比该IP数据报的长度要小。那么如何将这个过大的IP分组压缩进链路层帧的有效载荷字段呢？

解决办法是，将IP数据报中的数据分片成两个或更多个较小的IP数据报，用单独的链路层帧封装这些较小的IP数据报；然后向输出链路上发送这些帧。每个这些较小的数据报都被称为片(fragment)。

路由器完成分片任务。同时，为了使得网络内核保持简单，IPv4设计者把数据报的重组工作放到端系统中，而非放到网络路由器中。

前提：一个4000字节的数据报(20字节IP首部加上3980字节IP有效载荷)到达一台路由器，且必须被转发到一条MTU为1500字节的链路上。假定初始数据报贴上的标识号为777。

这意味着初始数据报中3980字节数据必须被分配到3个独立的片(其中的每个片也是一个IP数据报)

IP分片：

IP地址有32比特，分为网络号和主机号。
IP地址的网络部分（即网络号）被限制为长度为8、16或24比特，这是一种称为分类编址的编址方案。具有8、16和24比特子网地址的子网分别被称为A、B和C类网络。

但是它在支持数量迅速增加的具有小规模或中等规模子网的组织方面出现了问题。一个C类(/24)子网仅能容纳多大2^8 - 2 = 254台主机(2^8 = 256, 其中的两个地址预留用于特殊用途)，这对许多组织来说太小了。然而一个B类(/16)子网可支持多达65534台主机，又太大了。这导致B类地址空间的迅速损耗以及所分配的地址空间的利用率低。

广播地址255.255.255.255。当一台主机发出一个目的地址为255.255.255.255的数据报时，该报文会交付给同一个网络中的所有主机。

某组织一旦获得了一块地址，它就可以为本组织内的主机与路由器接口逐个分配IP地址。既可手工配置IP地址，也可以使用动态主机配置协议(Dynamic Host Configuration Protocol, DHCP)自动配置。DHCP还允许一台主机得知其他信息，如它的子网掩码、它的第一跳路由器地址(常称为默认网关)与它的本地DNS服务器的地址。

由于DHCP具有能将主机连接进一个网络相关方面的自动能力，它又被称为即插即用协议。

DHCP是客户-服务器协议。客户通常是新达到的主机，它要活的包括自身使用的IP地址在内的网络配置信息。在最简单的场合下，每个子网将具有一台DHCP服务器。如果在某子网中没有服务器，则需要一个DHCP中继代理(通常是一台路由器)，这个代理知道用于该网络的DHCP服务器的地址。

DHCP协议工作的4个步骤：

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

ICMP通常被认为是IP的一部分，但从体系结构上将它是位于IP之上的，因为ICMP报文是承载在IP分组中的。即ICMP报文是作为IP有效载荷承载的，就像TCP与UDP报文段作为IP有效载荷被承载那样。

众所周知的ping程序发送一个ICMP类型8编码0的报文到指定主机。看到该回显请求，目的主机发回一个类型0编码0的ICMP回显回答。大多数TCP/IP实现直接在操作系统中支持ping服务器，即该服务器不是一个进程。

新型IPv6系统可做成向后兼容，即能发送、路由和接收IPv4数据报，要使得已部署的IPv4系统能够处理IPv6数据报，最直接的方式是采用一种双栈方法。

1、链路状态(Link State, LS)算法：属于全局式路由选择算法，这种算法必须知道网络中每条链路的费用。费用可理解为链路的物理长度、链路速度，或与该链路相关的金融上的费用。链路状态算法采用的是Dijkstra算法。

2、距离向量(Distance-Vector, DV)算法：属于迭代的、异步的和分布式的路由选择算法。
“迭代的”，是因为此过程一直要持续到邻居之间无更多信息要交换为止。
“异步的”，是因为它不要求所有结点相互之间步伐一致地操作。
“分布式的”，是因为每个结点都要从一个或多个直接相连邻居接收某些信息，执行计算，然后将其计算结果分发给邻居。
DV算法的方程：

其中，dx(y)表示从结点x到结点y的最低费用路径的费用，c(x, v)是结点x到结点v的费用，结点v指的是所有x的相连结点，所以x的所有相连结点都会用minv方程计算。

（N是结点（路由器）的集合，E是边（链路）的集合）

为了减少公共因特网的路由选择计算的复杂性以及方便企业管理网络，我们将路由器组织进自治系统。

在相同AS中的路由器全都运行同样的路由选择算法，且拥有彼此的信息。在一个自治系统内运行的路由选择算法叫做自治系统内部路由选择协议。

当然，将AS彼此互联是必需的，因此在一个AS内的一台或多台路由器将有另外的任务，即负责向在本AS之外的目的地转发分组。这些路由器被称为网关路由器。

分为自治系统内部的路由选择和自治系统间的路由选择

1、因特网中自治系统内部的路由选择：路由选择信息协议(Routing Information Protocol, RIP)
2、因特网中自治系统内部的路由选择：开放最短路优先(Open Shortest Path First, OSPF)
3、自治系统间的路由选择：边界网关协议(Broder Gateway Protocol, BGP)

为什么要使用不同的AS间和AS内部路由选择协议？

实现广播的方法
1、无控制洪泛。该方法要求源结点向它的所有邻居发送分组的副本。当某结点接收了一个广播分组时，它复制该分组并向它的所有邻居（除了从其接收该分组的那个邻居）转发之。
致命缺点： 广播风暴 ，如果图具有圈，那么每个广播分组的一个或多个分组副本将无休止地循环。
2、受控洪泛。用于避免广播风暴，关键在于正确选择何时洪泛分组，何时不洪泛分组。受控洪泛有两种方法：序号控制洪泛、反向路径转发(Reverse Path Forwarding, RPF)
3、生成树广播。虽然序号控制洪泛和RPF能避免广播风暴，但是它们不能完全避免冗余广播分组的传输。

多播：将分组从一个或多个发送方交付到一组接收方

每台主机有一个唯一的IP单播地址，该单播地址完全独立于它所参与的多播组的地址。

因特网网络层多播由两个互补组件组成：因特网组管理协议(Internet Group Management Protocol, IGMP)和多播路由选择协议

IGMP只有三种报文类型：membership_query报文，membership_report报文，leave_group报文。

与ICMP类似，IGMP报文也是承载在一个IP数据报中。

因特网中使用的多播路由选择
1、距离向量多播路由选择协议
2、协议无关的多播路由选择协议