2.4 网络层

数据链路层主要研究和解决的是相邻两节点间的通信问题，实现的任务是两节点间透明地传输信息帧。数据链路层不能解决由多条链路组成的两主机之间通路的数据传输问题，因为两主机间的通路多由多条链路组成，涉及路由选择和流量控制问题；跨网传输时还会出现网络互联问题，而这些问题在网络层可以得到解决。

2.4.1 网络层的功能

网络层是OSI参考模型的第3层，介于传输层和数据链路层之间。网络层又称为通信子网层，是通信子网的最高层，其主要功能是控制通信子网的工作，实现网络节点之间穿越通信子网的数据传输。网络层数据的传输单位是分组。网络层主要的任务是选择合适的路径，把分组从源端传送到目的端，提供的是端到端的服务。

网络层的主要功能有以下几项。

①建立、维持和拆除网络连接两终端用户之间的通路是由一个或多个通信子网的多条链路串联而成，还涉及虚电路连接的建立、维持和拆除。

②组包／拆包。它规定分组的类型和具体格式。在发送系统中将传输层传递过来的长的数据信息拆分为若干个分组，在接收系统端将各分组原来加上的分组头／尾等控制信息拆掉（即拆包），组合成报文送至上层。

③路由选择。它又叫路径选择，是根据一定的原则和路由选择算法，在多节点的通信子网中选择一条从源节点到目的节点的最佳路径。最佳路径是相对而言的，一般是选择时延小、路径短、中间节点少的路径作为最佳路径。

④拥塞控制。网络层的拥塞控制是对整个通信子网内的流量进行控制，对进入分组交换网的流量进行控制。

网络层向上层可提供两类服务，即无连接的网络服务和面向连接的网络服务。无连接的网络服务是不可靠的，而面向连接的网络服务是可靠的。在网络层中，这两种服务的具体实现是数据报服务和虚电路服务。

典型的网络层协议是CCITT X.25，它是用于公用数据网的分组交换（包交换）协议，另一个常用的网络层协议是TCP/IP中的IP协议。

2.4.2 路由选择算法

任何IP网络最重要的一项功能就是路由。路由是发现、比较、选择通过网络到达任何目的IP地址的路径的过程。在一个通信子网中，网络源节点到目的节点可有多条传输路径。网络节点在收到一个分组后，要确定向下一节点传送的路径，这就是路由选择。路由的核心是路由协议。路由协议的核心是路由算法。路由算法是指确定路由选择的策略。

路由算法的目的就是找出源节点到目的节点的最佳路径。最佳路径就是两个节点所有可能路由中具有最小度量值的那条路径。常用的度量值包括路径长度、可靠性或可用性、传输时延、带宽、负载、通信成本。如果一个站点想与另一个并未与之直接连接的站点通信，网络协议必须找出一条路径来连接它们。通常根据通过每条路径发送信息所需的费用和时间的比较来最终确定哪条路径。这种比较是相当复杂的。小型网络中可通过人工计算完成，但对于大型网络则必须用软件来计算完成。

路由算法分为以下两种。

（1）静态路由算法。路由器只在启动时计算和设置路由，此后路由不再改变或者路由改变很慢，通常只有在人的干涉下才能发生改变，即由管理员手动改变路由表。

①静态路由选择策略：静态路由选择策略不用测量也无须利用网络信息，这种策略按某种固定规则进行路由选择，其中还可分为泛射路由选择、固定路由选择和随机路由选择3种算法。

②静态路由的优点：可以使网络更安全，只有一条流进和流出网络的路径（除非定义多条静态路由）；可以更有效地利用资源，它几乎不占用传输带宽，不使用路由器上的CPU来计算路由，需要的存储器也很少。

③静态路由的缺点：在网络发生问题或拓扑结构发生变化时，网络管理员负责手动适应这种变化。只适用于小型网络。

（2）动态路由算法。路由器在启动时只建立一个初始路由，当网络变化时随时更新，路由动态地发生改变。除了网络发生改变外，当发生路由循环或是路由振动时，路由也会随之发生改变。动态路由也称为自适应路由。

动态路由选择策略：节点的路由选择要依靠网络当前的状态信息来决定的策略称为动态路由选择策略，这种策略能较好地适应网络流量、拓扑结构的变化，有利于改善网络的性能。

根据算法是全局的还是分散的，又将动态路由算法分为全局路由算法（Global Routing Algorithm）和分散路由算法（Decentralized Routing Algorithm）。

①全局路由算法要求每一个节点都必须获悉网络中所有连接情况以及每条链路的信息、权值和开销等。通常情况下，全局路由算法是指链路状态算法（Link State Algorithms），在这种算法中，初始输入值必须包括网络中所有链路的信息。

②采用分散路由算法的每个路由仅仅知道与它相连的链路信息，而不是像全局路由算法那样，每个节点都必须获悉网络中所有的连接情况以及每条链路的权值。通常情况下，分散的路由算法是指距离矢量算法。

下面介绍几种典型的动态路由算法。

1．Dijkstra算法

Dijkstra算法把网络看成一张图。该算法从图中一个源点出发，计算沿最短路径到图中其他各点的距离，在计算最短路径的过程中构造下一站路由表。对每个路由表都必须用算法计算一次。

2．距离矢量路由算法

距离矢量路由算法（Distance Vector Routing Algorithm）是著名的分布式路由计算算法。路由器周期性地通过网络向邻居发送路由信息，每条信息包括目的地、距离等。当信息从邻居到达包交换机时，路由器就检查信息中的每一项，如果邻居到某目的地有比原来更短的路径，就更新路由表。算法会周期性地把自己的路由表复制传给与其直接相连的网络邻居。每一个接收者加上一个距离向量或它自己的距离“值”到表上，并把它转发给它的直接邻居。这个过程在所有直接相连的路由器之间进行。这样一步一步做下去，最后每一个路由器都得到了其他路由器的信息，最终形成一个网络“距离”的积累视图。

3．链路状态路由

链接状态路由也可称为最短路径优先（Shortest Path First, SPF）或SPF路由（SPF Routing）。与距离矢量算法一样，SPF算法也能适应硬件故障的情况。而且SPF是所有计算同时进行，在链接状态改变之后，所有路由器都收到该状态信息，每个交换机都开始计算自己的路由表。SPF通过和网络中的其他路由器交换链路状态通告（LSA）来形成和维护网络路由器的全部信息。LSA交换由网络中的事件驱动，而不是周期性地进行。

SPF算法的思想是：如果要求节点1～5之间的最短路径，节点1和5之间经过了节点2、3、4、5。如用minC（x,y）来表示节点x到y之间的最短路径，则minC（1,5）=minC（1，2）+minC（2,3）+minC（3,4）+minC（4,5）。

算法描述如下。

（1）置N={A}，对于每个节点V∈M.A，置D（V）=C（A,V）。

（2）找出D（V）中最小值的节点W，将W加入到N。对于每一个节点V∈M.N，置D（V）=min（D（V），D（W）+C（W,V））。如果D（W）+C（W,V）<D（V），则从A到V的路径就变成了A到W的路径再加上W到V的链路的路径。

（3）重复执行（2），直到N中包括所有的节点，即N=M。

整个搜索算法中的符号定义如下。

●N=已知其与源节点的最优路径的节点的集合。

●A=源节点。

●M=所有的节点的集合。

●V=宿节点。

●D（v）=算法求得的当前从源节点A到宿节点V的最优路径的代价。

●C（i,j）=节点i与j之间邻接的链路的权值；若两个节点之间无直接相连的链路，则等于∞。

●P（v）=算法求得的当前从源节点A到宿节点V的最优路径的宿节点的前一个节点。

4．分级路由

将路由器分成自治系统（Autonomy System, AS），在AS内部，路由器运行同一个路由算法（如LS或DV算法），本AS的路由器相互拥有彼此的信息，这个在AS内部运行的路由算法称为Inter-AS路由协议（即内部路由协议IGP）。当然，这些AS之间还必须能够相互连接，这样在每个AS之内就有一个或多个路由器除完成内部路由运算以外，还要承担额外的将一些数据包送到本AS之外的目的地的任务，在AS内具有这种功能的路由器称为网关路由器。为了使网关路由器能够将一个数据包从一个AS路由到另一个AS（这中间可能经过很多个AS），网关路由器必须知道怎样在AS之间进行路由。网关路由器用来实现在各个AS之间寻路的路由算法叫Intra-AS路由协议（即外部路由协议EGP）。

将网络分为一个一个自治系统，自治系统内和自治系统间采取不同的路由算法，称此为层次路由算法。在层次路由算法中将每个自治系统称为一个域。

层次路由算法具有以下特点。

①所有节点被都划分到不同的称为域（Domain）的组中，可将域视为是分离的、独立的网络。

②同一个域中的两个节点的路由根据此域或网络的协议决定。

③每个域都有一个或多个特定的节点，称为路由器（有时也称为网关），它们决定了域间的路径。实际上，这些路由器本身也构成了一个网络。

④如果一个域很大，它可以再由多个子域构成。每个子域含有它自己的路由器。它们决定了在同一个域中各子域的路径。