计算机网络层最短路径

Ⅰ 计算机网络(四)网络层

主要任务是把分组从源端传到目的端，为分组交换网上的不同主机提供通信服务。网络层传输单位是数据报。

链路层数据帧可封装数据的上限称为最大传送单元MTU

标识：同一数据报的分片使用同一标识。

中间位DF（Don’t Fragment）：

最低位MF（More Fragment）：

片偏移：指出较长分组分片后，某片在原分组中的相对位置。以8B为单位。除了最后一个分片，每个分片长度一定是8B的整数倍。

IP地址：全世界唯一的32位/4字节标识符，标识路由器主机的接口。IP地址::={<网络号>,<主机号>}

有一些IP地址是不能用的，有其特殊的作用，如：

网络地址转换NAT（Network Address Translation）：在专用网连接到因特网的路由器上安装NAT软件，安装了NAT软件的路由器叫NAT路由器，它至少有一个有效的外部全球IP地址。

此外，为了网络安全，划分出了部分IP地址和私有IP地址，私有IP地址网段如下：

路由器对目的地址是私有IP地址的数据报一律不进行转发。

分类的IP地址的弱点：

某单位划分子网后，对外仍表现为一个网络，即本单位外的网络看不见本单位内子网的划分。

路由器转发分组的算法：

无分类域间路由选择CIDR：

CIDR记法：IP地址后加上“/”，然后写上网络前缀（可以任意长度）的位数。e.g. 128.14.32.0/20

CIDR把网络前缀都相同的连续的IP地址组成一个“CIDR地址块”。

使用CIDR时，查找路由表可能得到几个匹配结果（跟网络掩码按位相与），应选择具有最长网络前缀的路由。前缀越长，地址块越小，路由越具体。

将多个子网聚合成一个较大的子网，叫做构成超网，或路由聚合。方法：将网络前缀缩短（所有网络地址取交集）。

由于在实际网络的链路上传送数据帧时，最终必须使用MAC地址。

ARP协议：完成主机或路由器IP地址到MAC地址的映射。

ARP协议使用过程：

ARP协议4种典型情况：

动态主机配置协议DHCP是 应用层 协议，使用 客户/服务器 方式，客户端和服务端通过 广播 方式进行交互，基于 UDP 。

DHCP提供即插即用联网的机制，主机可以从服务器动态获取IP地址、子网掩码、默认网关、DNS服务器名称与IP地址，允许地址重用，支持移动用户加入网络，支持在用地址续租。

DHCP工作流程如下：

ICMP协议支持主机或路由器：包括差错（或异常）报告和网络探询，分部发送特定ICMP报文

ICMP差错报告报文（5种）：

不应发送ICMP差错报文的情况：

ICMP询问报文:

ICMP的应用：

32位IPv4地址空间已分配殆尽，这时，可以采用更大地址空间的新版本的IPv6，从根本上解决地址耗尽问题

IPv6数据报格式如下图

IPv6的主要特点如下：

IPv6地址表示形式：

零压缩：一连串连续的0可以被一对冒号取代。双冒号表示法在一个地址中仅可出现一次。

IPv6基本地址类型：

IPv6向IPv4过渡的策略：

R1的路由表/转发表如下：

最佳路由：“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。

路由算法可分为

由于因特网规模很大且许多单位不想让外界知道自己的路由选择协议，但还想连入因特网，可以采用自治系统来解决

自治系统AS：在单一的技术管理下的一组路由器，而这些路由器使用一种AS内部的路由选择协议和共同的度量以确定分组在该AS内的路由，同时还使用一种AS之间的路由协议以确定在AS之间的路由。

一个AS内的所有网络都属于一个行政单位来管辖，一个自治系统的所有路由器在本自治系统内都必须连通。

路由选择协议

RIP是一种分布式的基于距离向量的路由选择协议，是因特网的协议标准，最大优点是简单。

RIP协议要求网络中每一个路由器都维护从它自己到其他每一个目的网络的唯一最佳距离 [1] 记录（即一组距离）。 RIP协议只适用于小互联网。

RIP是应用层协议，使用 UDP 传送数据。一个RIP报文最多可包括25个路由，如超过，必须再用一个RIP报文传送。

RIP协议的交换

路由器刚开始工作时，只知道直接连接的网络的距离（距离为1），接着每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。

经过若干次更新后，所有路由器最终都会知道到达本自治系统任何一个网络的最短距离和下一跳路由器的地址，即“收敛”。

RIP的特点：当网络出现故障时，要经过比较长的时间(例如数分钟) 才能将此信息传送到所有的路由器，“慢收敛”。

对地址为X的相邻路由器发来的RIP报文，修改此报文中的所有项目：把“下一跳”字段中的地址改为X，并把所有的“距离”字段+1。

开放最短路径优先OSPF协议：“开放”标明OSPF协议不是受某一家厂商控制，而是公开发表的；“最短路径优先”是因为使用了Dijkstra提出的最短路径算法SPF。OSPF最主要的特征就是使用分布式的链路状态协议。 OSPF直接用IP数据报传送。

OSPF的特点：

为了使OSPF 能够用于规模很大的网络，OSPF 将一个自治系统再划分为若干个更小的范围，叫做区域。每一个区域都有一个32 位的区域标识符（用点分十进制表示）。区域也不能太大，在一个区域内的路由器最好不超过200 个。

BGP 所交换的网络可达性的信息就是要到达某个网络所要经过的一系列AS。当BGP 发言人互相交换了网络可达性的信息后，各BGP 发言人就根据所采用的策略从收到的路由信息中找出到达各AS 的较好路由。

一个BGP 发言人与其他自治系统中的BGP 发言人要交换路由信息，就要先建立TCP 连接，即通过TCP传送，然后在此连接上交换BGP 报文以建立BGP 会话(session)，利用BGP 会话交换路由信息。 BGP是应用层协议，借助TCP传送。

BGP协议特点:

BGP-4的四种报文

组播提高了数据传送效率。减少了主干网出现拥塞的可能性。组播组中的主机可以是在同一个物理网络，也可以来自不同的物理网络（如果有组播路由器的支持）。

IP组播地址让源设备能够将分组发送给一组设备。属于多播组的设备将被分配一个组播组IP地址（一群共同需求主机的相同标识）。

组播地址范围为224.0.0.0～239.255.255.255（D类地址），一个D类地址表示一个组播组。只能用作分组的目标地址。源地址总是为单播地址。

同单播地址一样，组播IP地址也需要相应的组播MAC地址在本地网络中实际传送帧。组播MAC地址以十六进制值01-00-5E打头，余下的6个十六进制位是根据IP组播组地址的最后23位转换得到的。

TCP/IP 协议使用的以太网多播地址的范围是:从01-00-5E-00-00-00到01-00-5E-7F-FF-FF .

收到多播数据报的主机，还要在IP 层利用软件进行过滤，把不是本主机要接收的数据报丢弃。

ICMP和IGMP都使用IP数据报传递报文。组播路由器知道的成员关系只是所连接的局域网中有无组播组的成员。

IGMP工作的两个阶段：

只要有一个主机对某个组响应，那么组播路由器就认为这个组是活跃的；如果经过几次探询后没有一个主机响应，组播路由器就认为本网络上的没有此组播组的主机，因此就不再把这组的成员关系发给其他的组播路由器。

组播路由协议目的是找出以源主机为根节点的组播转发树。构造树可以避免在路由器之间兜圈子。对不同的多播组对应于不同的多播转发树；同一个多播组，对不同的源点也会有不同的多播转发树。

组播路由选择协议常使用的三种算法：

移动IP技术是移动结点(计算机/服务器等)以 固定的网络IP地址 ，实现跨越不同网段的 漫游 功能，并保证了基于网络IP的网络权限在漫游过程中不发生任何改变。

路由器是一种具有多个输入端口和多个输出端口的专用计算机，其任务是转发分组。

若路由器处理分组的速率赶不上分组进入队列的速率，则队列的存储空间最终必定减少到零，这就使后面再进入队列的分组由于没有存储空间而只能被丢弃。 路由器中的输入或输出队列产生溢出是造成分组丢失的重要原因。

路由器(网络层)可以互联两个不同网络层协议的网段。
网桥(链路层)可以互联两个物理层和链路层不同的网段。
集线器(物理层)不能互联两个物理层不同的网段。

路由表根据路由选择算法得出的，主要用途是路由选择，总用软件来实现。

转发表由路由表得来，可以用软件实现，也可以用特殊的硬件来实现。转发表必须包含完成转发功能所必需的信息，在转发表的每一行必须包含从要到达的目的网络到输出端口和某些MAC地址信息的映射。

Ⅱ Dijkstrath算法是什么如何用Dijkstrath算法求计算机网络拓扑图的最短路径

Dijkstra算法是典型 的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。
迪杰斯特拉(Dijkstra)算法思想
按路径长度递增次序产生最短路径算法：

把V分成两组：

（1）S：已求出最短路径的顶点的集合

（2）V-S=T：尚未确定最短路径的顶点集合

将T中顶点按最短路径递增的次序加入到S中，

保证：（1）从源点V0到S中各顶点的最短路径长度都不大于

从V0到T中任何顶点的最短路径长度

（2）每个顶点对应一个距离值

S中顶点：从V0到此顶点的最短路径长度

T中顶点：从V0到此顶点的只包括S中顶点作中间

顶点的最短路径长度

依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的

直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和

（反证法可证）

求最短路径步骤
算法步骤如下：

1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值

若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值

若不存在<V0,Vi>，d(V0,Vi)为∝

2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S

3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的

距离值缩短，则修改此距离值

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

Ⅲ 计算机网络（三）——网络层

网络层的 目的 是实现在任意结点间进行数据报传输，它的目的与链路层、物理层不是一样的吗？但是通过它数据可以在更大的网络中传输。

为了能使数据更好地在更大的网络中传输，网络层主要实现三个功能： 异构网络互联 、 路由与转发 和 拥塞控制 。

我们知道，在物理层、链路层，可以使用不同的传输介质和拓扑结构将几台、十几台主机连接在一起形成一个小型的局域网，把这些组成结构不完全相同的局域网称为异构网，因此将它们连接扩大成更大的网络，需要一个类似转接头的设备——路由器，路由器不仅仅可以连接异构网，还能隔离冲突域和广播域，依照IP地址转发。

下图对集线器、网桥、交换机和路由器能否隔离冲突域和广播域进行比较：

路由器作为连接多个网络的结点，不仅需要完成对数据的分组转发，还要选择传输路径，因此路由器主要由 路由选择 和 分组转发 组成。

网络层最重要的功能是 路由与转发 功能。路由也就是选择一条合适的路，转发则是在这条路上遵守协议。这有点像从某个多个国家的交界城市自驾，选其中一条路，那么就遵守这个国家的交通协议。

数据通过一个又一个路由器到达目的地址，路由器怎么知道数据应该从哪个端口出发才能到达目的地呢？这就需要构造路由表。
路由表有两种构造方式： 静态 和 动态 。

一个个小网络可以构成一个区域，足够多的区域互连成一个网络，多个网络又形成巨大的互联网。要想让数据高效在网络中传输，采用“分而治之”的理念。
将互联网分为许多较小的自治系统，系统有权决定自己内部采用什么路由协议，这便是层次路由。通过层次路由便可以采用灵活的协议传输数据。数据在自治系统内传输采用 内部网关协议 而自治系统之间则采用 外部网关协议 。

内部网关协议有两种协议： 路由信息协议（RIP） 和 开放最短路径优先协议（OSPF）

外部网关协议则是边界网关协议（BGP）。内部网关协议服务某个自治系统，范围较小，所以尽可能有效地从源站送到目的站，也就是找到一条最佳路径。而外部网关协议需要面对更大的网络范围和网络环境，因此更关注的找到比较好的路径，也就是不能兜圈子。

BGP工作原理：

将三种路由协议进行比较：

构建大规模、异构网络的互联网除了硬件的支持外，还需要建立协议以实现数据报传输服务——IP协议。
目前IP协议有两个版本：IPv4和IPv6。

现在主流的IP协议版本还是IPv4。

IP数据报主要由首部和数据部分组成，由TCP报文段封装到数据部分，再在前端加上一些描述信息的首部，其格式如下图：

IP协议使用分组转发，当报文过大时需要分片。分片的思路如下：

如果把IP数据报看作是信，那么首部中的源地址与目的地址则分别是发信地址和邮件地址。为了方便路由计算这些地址，并且使IP地址足够使用，因此将IP地址进行分类。

IP地址的格式 ： {<网络号>,<主机号>}，网络号标志主机所连接的网络，主机号标志该主机，每个IP地址都是唯一的。

IP地址分类 如下：

通过分类，可以计算每个网络中最大的主机数：

网络地址转换（NAT）是一种转换机制，将专用网络地址转换为公用地址，目的是为了对外隐藏内部管理的IP地址，这样不仅可以保证网络安全，还可以解决IP地址不足问题。
当路由器接收到的目的地址是私有地址则一律不进行转发，而如果是公用地址，则是用NAT转换表将源IP及端口号映射成全球IP号，然后从WAN端口发送到因特网上。

IP地址有A、B、C类网络号，如果把A类网络号分给一个广播域，那么这个广播域可以接入16,777,212台主机，然而一个广播域不可能融入这么多台主机，因为这样会导致广播域过饱和而瘫痪，而只给其分配一定数量的网络号，则会浪费大量的IP地址。因此在IP地址中增加一个“子网号字段”，将IP地址划分为三级，即IP地址={<网络号>,<子网号>,<主机号>}，也就是从主机号中借用几个比特号作为子网号，这个子网号是对内划分的，对外仍旧表现为二级IP地址。

主机或路由器如何判断一个网络是否进行子网划分了呢？——利用子网掩码。

CIDR是 无分类 域间路由器选择，目的是消除A、B、C类网络划分，这样可以大幅度提高IP地址空间利用率。相比较子网掩码划分，它更加灵活。

上图中，如果R1收到前缀为206.1的IP地址，它只需要转发给R2，具体发往网络1还是网络2，则由R2计算得出。

通过IP地址，可以将数据从某个网络传输到目的网络，但是把信息发送给哪台主机呢？由于路由器的隔离，IP网路没办法使用广播方式查找MAC地址，只有通过链路层的MAC地址以广播方式寻址。
因此，IP协议还包括三个协议—— ARP、DHCP和ICMP ，共同配合完成数据转发。

IPv6是解决IP地址耗尽的根本手段。它与IPv4的报文形式差别如下图：

IPv6与IPv4地址通信示意图：

在通信过程中，如果分组过量而导致网路性能下降，会产生拥塞。

拥塞的控制方式：

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

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

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

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

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

图 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 运行相同的自治系统间选路协议。

Ⅳ 网络理论的最短路径问题

一般提法是：寻找网络中两点间的最短路径,即寻找连接这两点的边的总权数(可以是距离、时间、费用等)为最小的通路。图4为最短路径问题的一个例子。最短路径问题有两种算法。戴克斯特拉法1959年提出。其计算方法是：从始点vs,标以零值,并记在vs旁的方括号内。然后依节点序号顺序找出到达各点的最短距离,并说明来自何方,例如在节点v3处标上【v2,4】,即表示来自节点v2，距离累计为4。戴克斯特拉法可以通过编制计算程序,在计算机上运算。

Ⅵ 计算机网络-网络层-多协议标记交换MPLS

多协议标记交换MPLS (MultiProtocol Label Switching)：“多协议”表示在MPLS的上层可以采用多种协议。 MPLS采用了面向连接的工作方式（或者说是利用面向连接技术） ，使每个分组携带一个叫做标记(label)的小整数（这叫做打上标记)。当分组到达交换机（即标记交换路由器）时，交换机读取分组的标记，并用标记值来检索分组转发表。这样就比查找路由表来转发分组要快得多。

MPLS具有以下三个方面的特点：(1)支持面向连接的服务质量。(2)支持流量工程，平衡网络负载。(3)有效地支持虚拟专用网VPN。

在传统的P网络中，分组每到达一个路由器，都必须查找路由表，并按照“最长前缀匹配”的原则找到下一跳的P地址（请注意，前缀的长度是不确定的）。当网络很大时，查找含有大量项目的路由表要花费很多的时间。在出现突发性的通信量时，往往还会使缓存溢出，这就会引起分组丢失、传输时延增大和服务质量下降。

MPLS的一个重要特点就是在MPLS域的入口处，给每一个IP数据报打上固定长度 “标记” ，然后对打上 标记的IP数据报用硬件进行转发 ，这就使得IP数据报转发的过程大大地加快了”。 采用硬件技术对打上标记的P数据报进行转发就称为标记交换。 “交换”也表示在转发时不再上升到第三层查找转发表，而是根据标记在第二层（链路层）用硬件进行转发。MPLS可使用多种链路层协议，如PPP、以太网、ATM以及帧中继等。

MPLS域(MPLS domain)是指该域中有许多彼此相邻的路由器，并且所有的路由器都是支持MPLS技术的 标记交换路由器LSR (Label Switching Router)。 LSR同时具有标记交换和路由选择这两种功能 ，标记交换功能是为了快速转发，但在这之前LSR需要使用路由选择功能构造转发表。

MPLS的基本工作过程：

(I)MPLS域中的各LSR使用专门的 标记分配协议LDP (Label Distribution Protocol)交换报文，并找出和特定标记相对应的路径，即 标记交换路径LSP (Label Switched Path)。例如在图中的路径A→B→C→D。各 LSR根据这些路径构造出转发表 。这个过程和路由器构造自己的路由表相似。但应注意的是，MPLS是面向连接的，因为在标记交换路径LSP上的第一个LSR就根据IP数据报的初始标记确定了整个的标记交换路径，就像一条虚连接一样。

(2)当一个IP数据报进入到MPLS域时， MPLS入口结点(ingress node)就给它打上标记(实际上是插入一个MPLS首部)，并按照转发表把它转发给下一个LSR。 以后的所有LSR都按照标记进行转发。

给IP数据报打标记的过程叫做分类(classification)。严格的第三层（网络层）分类只使用了IP首部中的字段，如源P地址和目的P地址等。大多数运营商实现了第四层（运输层）分类（除了要检查P首部外，运输层还要检查TCP或UDP首部中的协议端口号），而有些运营商则实现了第五层（应用层）分类（更进一步地检查数据报的内部并考虑其有效载荷）。

(3)由于在全网内统一分配全局标记数值是非常困难的，因此一个标记仅仅在两个标记交换路由器LSR之间才有意义。分组每经过一个LSR,LSR就要做两件事：一是转发，二是更换新的标记，即把入标记更换成为出标记。这就叫做标记对换(label swapping)。做这两件事所需的数据都己清楚地写在转发表中。例如，图4-61中的标记交换路由器B从入接口0收到一个入标记为3的IP数据报，标记交换路由器B就知道应当把该P数据报从出接口1转发出去，同时把标记对换为1。当IP数据报进入下一个LSR时，这时的入标记就是刚才得到的出标记。因此，标记交换路由器C接着在转发该IP数据报时，又把入标记1对换为出标记2。

(4)当IP数据报离开MPLS域时， MPLS出口结点(egress node))就把MPLS的标记去除 ，把IP数据报交付非MPLS的主机或路由器，以后就按照普通的转发方法进行转发。

上述的这种“由入口LSR确定进入MPLS域以后的转发路径”称为显式路由选择(explicit routing),它和互联网中通常使用的“每一个路由器逐跳进行路由选择”有着很大的区别。

转发等价类FEC

MPLS有个很重要的概念就是转发等价类FEC(Forwarding Equivalence Class)。所谓“转发等价类”就是路由器按照同样方式对待的IP数据报的集合。这里“按照同样方式对待”表示从同样接口转发到同样的下一跳地址，并且具有同样服务类别和同样丢弃优先级等。FEC的例子是：

(I)目的IP地址与某一个特定IP地址的前缀匹配的IP数据报（这就相当于普通的IP路由器)：

(2)所有源地址与目的地址都相同的IP数据报；

(3)具有某种服务质量需求的IP数据报。

总之，划分FEC的方法不受什么限制，这都由网络管理员来控制，因此非常灵活。入口结点并不是给每一个IP数据报指派一个不同的标记，而是将属于同样FEC的IP数据报都指派同样的标记。FEC和标记是一一对应的关系。

图4-62给出一个把FEC用于负载平衡的例子。图4-62(a)的主机H1和H2分别向H3和H4发送大量数据。路由器A和C是数据传输必须经过的。但传统的路由选择协议只能选择最短路径A→B→C,这就可能导致这段 最短路径过载 。

图4-62(b)表示在MPLS的情况下， 入口结点A可设置两种FEC :“源地址为H1而目的地址为H3”和“源地址为H2而目的地址为H,”,把前一种FEC的路径设置为H1→A→B→C→H3,而后一种的路径设置为H2→A→D→E+C→H4。这样可使网络的负载较为平衡。网络管理员采用自定义的FEC就可以更好地管理网络的资源。这种均衡网络负载的做法也称为流量工程TE(Traffic Engineering)心或通信量工程。

MPLS并不要求下层的网络都使用面向连接的技术。因此一对MPLS路由器之间的物理连接，既可以由一个专用电路组成，如OC-48线路，也可以使用像以太网这样的网络。但是这些网络并不提供打标记的手段，而IPv4数据报首部也没有多余的位置存放MPLS标记。这就需要使用一种封装技术：在把IP数据报封装成以 太网帧 之前，先要插入一个MPLS首部。" 从层次的角度看，MPLS首部就处在数据链路层和网络层之间"。 在把加上MPLS首部的IP数据报封装成以太网帧时，以太网的类型字段在单播的情况下设置为 ,而在多播的情况下为 。这样， 接收方可以用帧的类型来判决这个帧是携带了MPLS标记还是一个常规的IP数据报。

“给IP数据报打上标记”其实就是在 以太网的帧首部和IP数据报的首部之间插入一个4字节的MPLS首部 。具体的标记就在“标记值”这个字段中。MPLS首部共包括以下四个字段：

(1)标记值  占20位。由于一个MPLS标记占20位，因此从理论上讲，在设置MPLS时可以使用标记的所有20位，因而可以同时容纳高达2^20个流（即1048576个流）。但是，实际上几乎没有哪个MPLS实例会使用很大数目的流，因为通常需要管理员人工管理和设置每条交换路径。

(2)试验  占3位，目前保留用于试验。

(3)栈S  占1位，在有“标记栈”时使用。

(4)生存时间TTL  占8位，用来防止MPLS分组在MPLS域中兜圈子。