第5章网络层(部编)课件

第5章网络层5.1网络层主要功能和服务5.2电路交换和分组交换

5.3虚电路和数据报5.4路由选择5.5流量控制和拥塞控制5.6Internet的网际协议IP5.7路由器思考题与习题5.1网络层主要功能和服务网络层是OSI参考模型中的第三层，介于传输层和数据链路层之间。它的主要任务是把网络协议数据单元或分组从源计算机经过适当的路径发送到目的地计算机。从源计算机到目的计算机可能要经过若干个中间节点，这需要在通信子网中进行路由选择。网络层与数据链路层有很大的差别，数据链路层仅把数据帧从线缆或信道的一端传送到另一端(即在相邻节点间进行数据传送)，而网络层向运输层提供最基本的端到端的数据传送服务。网络层关心的是通信子网的运行控制，解决如何使数据分组跨越通信子网的问题，体现了网络应用环境中资源子网访问通信子网的方式。为避免通信子网中出现过多的分组而造成网络阻塞，需要对流入的分组数量进行控制。另外，当分组要跨越多个通信子网才能到达目的地时，网络层还要解决网际互连的问题。因此，网络层的目的是实现两个端系统之间的数据透明传送，具体功能包括路由选择、阻塞控制和网际互连等。网络层在其与运输层的接口上为运输层提供服务。这一接口是相当重要的，因为它往往是公共载体网络(如电信网络)与用户的接口，也就是说，它是通信子网的边界。载体网络通常规定了从物理层直到网络层的各种协议和接口，传输由其用户提供的分组。基于这种原因，对接口的定义必须十分明确和完善。网络层的服务设计应该按照下列原则：(1)服务应与通信子网无关。(2)通信子网的数量、类型和拓扑结构对于运输层来说是隐蔽的。(3)运输层所能获得的网络地址应采用统一的编号方式，即使跨越多个局域网和广域网也应如此。基于上述原则，网络层的设计者有较大的自由度来编写提供给运输层的服务的技术规范。端系统之间的通信是靠通信子网中间节点间的通信完成的，体现了通信子网向端系统所提供的网络服务。通信子网向端系统提供的网络服务有面向连接的(虚电路)和无连接(数据报)两种，也即端系统的网络层向端系统的运输层提供的服务。而通信子网内部的工作方式可以是面向连接的，也可以是无连接的。也就是说，通信子网提供的网络服务与通信子网内部选择的工作方式无关。5.2电路交换和分组交换局域网是广播通信网络，所有网络节点共享通信介质，不需要中间节点的介入。对于广域网一般都采用点到点信道，而点到点信道使用存储转发的方式传送数据，也就是说从源节点到目的节点的数据通信需要经过若干个中间节点的转接，这涉及到数据交换技术。数据交换技术主要有：电路交换、报文交换和分组交换。分组交换是对报文交换的改良。5.2.1电路交换交换的概念最早来自于电话系统。当用户进行拨号时，电话系统中的交换机在呼叫者的电话与接收者的电话之间建立了一条实际的物理线路，通话便建立起来，此后两端的电话拥有该专用线路，直到通话结束。这里所谓的交换是在电话交换机内部。当交换机从一条输入线上接到呼叫请求时，它首先根据被呼叫者的电话号码寻找一条合适的输出线，然后通过硬件开关(如继电器)将二者连通。假如一次电话呼叫要经过若干交换机，则所有的交换机都要完成同样的工作。电话系统的这种交换方式叫做电路交换。从上面我们可以知道，在电路交换网中，一旦通话建立，在两部电话之间就有一条物理通路存在，直到这次通话结束，才拆除物理通路。因此，采用电路交换技术进行数据传输需要经历以下三个过程：(1)电路建立：在传输任何数据之前，要先经过呼叫过程建立一条端到端的电路。(2)数据传输：电路建立后，数据就可以通过网络从一端发送到另一端。在整个数据传输过程中，所建立的电路必须始终保持连接状态。(3)电路拆除：数据传输结束后，由一端发出拆除请求，然后逐个节点拆除直到对方节点。电路交换传输延迟小，惟一的延迟是物理信号的传播延迟；一旦线路建立，便不会发生冲突。传输延迟小是因为电路建立后，就不再需要交换开销；不发生冲突是因为独享物理线路。因此，电路交换具有数据传输可靠、迅速且数据不会丢失的优点。电路交换的缺点首先是建立连接所需的时间比较长。在数据开始传输之前，呼叫信号必须经过若干个交换机，得到各交换机的认可，并最终传到被呼叫方。这个过程常常需要10s甚至更长的时间。对于许多很短时间数据传输的应用，电路建立和拆除所用的时间过长是不合适的。另外，在电路交换系统中，物理线路的带宽是预先分配好的。对于已经预先分配好的线路，即使通信双方都没有数据要交换，线路带宽也不能为其他用户所使用，从而造成带宽的浪费。当然，这种浪费也有好处，对于占用信道的用户来说，其可靠性和实时响应能力都得到保证。因此，电路交换比较适用于系统间要求高质量的大量数据的传输。5.2.2分组交换分组交换是报文交换的一种改进，它将报文分成若干个分组，分组从源点传送到目的地采用存储转发方式。分组的大小有严格的上限，有限长度的分组使得对每个中间节点所要求的存储能力降低了，分组可以被存储在交换设备的内存而不是磁盘中，这样提高了交换速度。同时由于分组交换网能够保证任何用户都不能长时间独占某传输线路，因而它非常适合于交互式通信，如终端与主机通信等。电路交换和分组交换技术有许多不同之处。其中一个是电路交换中信道带宽是静态分配的，而分组交换中信道带宽是动态分配和释放的。在电路交换中已分配的信道带宽未使用时都被浪费掉，而在分组交换中，这些未使用的信道带宽可以被其他分组所利用，因为在分组交换中信道不是为某对节点所专用的，从而提高了信道利用率，相对来说每个用户信道的费用也就降低了。但是，正是因为信道不是专用的，突发的大量输入数据可能会耗尽交换设备的存储空间，造成分组丢失。另一个不同之处是电路交换是完全透明的，发送方和接收方可以使用任何速率(在物理线路支持的范围内)、任意帧格式来进行数据通信。而在分组交换中，发送方和接收方必须按一定的数据速率和分组格式进行通信。电路交换和分组交换的另一个区别是计费方法的不同。它们所采用的技术决定了它们的计费方法是不同的。在电路交换中，通信费用取决于通话时间和距离，而与通话量无关，原因是在电路交换中，通信双方是独占信道带宽的。而在分组交换中，通信费用主要按通信流量(如字节数或分组)来计算，适当考虑通话时间和距离。

IP电话就是使用分组交换技术的一种新型电话，它的通话费远远低于传统电话，原因就在这里。当然分组交换也有许多问题，比如拥塞、报文分片和重组等。对这些问题的不同处理方法将导致分组交换的不同实现。分组交换有虚电路分组交换和数据报分组交换两种。分组交换是计算机网络中使用最广泛的一种交换技术，如X.25、帧中继和ATM等都属于分组交换网。5.3虚电路和数据报端系统间的通信是依靠通信子网中节点间的通信来实现的。在分组交换方式中，通信子网向端系统提供虚电路和数据报两种网络服务，而通信子网内部的操作也有虚电路和数据报两种方式。5.3.1虚电路在虚电路操作方式中，为了进行数据传输，要在网络的源节点和目的节点之间先建一条逻辑通路。每个分组除了包含数据之外还包含一个虚电路标识符。该标识符使在预先建好的路径上的每个节点都知道把这些分组传送到哪里去，无需进行路由选择。最后，由任何一个端节点发出清除请求分组来结束这次连接。它之所以是"虚"的，是因为这条通路不像电路交换时建立的物理通路那样，它不是专用的。分组在每个节点处被存储，并在线路上排队等待转发。每个节点到其他任一节点之间可能同时有若干条虚电路。每条虚电路支持特定的两个端系统之间的数据传输，两个端系统之间也可能有多条虚电路为不同的进程服务，这些虚电路的实际路径可能相同也可能不同。节点间的物理信道在逻辑上均可看作由多条逻辑信道组成，这些逻辑信道实际上是由节点内部的分组缓冲器来实现的。所谓占用某条逻辑信道，实质上是指占用节点分配的分组缓冲器。不同的逻辑信道在节点内部通过虚电路号加以区分，各条逻辑信道异步时分复用同一条物理信道。一条虚电路可能要经过多个中间节点，在节点间的各段物理信道上都要占用一条逻辑信道用以传送分组。由于各节点均独立地为通过的虚电路分配逻辑信道，也就是说同一条虚电路通过各段物理信道时获取的逻辑信道可能是不相同的，所以各节点内部必须建立一张虚电路表，用以记录该点的各条虚电路所占用的各个逻辑信道。为使节点能区分一个分组属于哪条虚电路，每个分组必须携带一个虚电路号。同样，同一条虚电路的分组在各段逻辑信道上的虚电路号可能也不相同。传输中，当一个分组到达节点时，节点根据其携带的虚电路号查找虚电路表(每个节点必须保持一张虚电路表)，以确定该分组应发往的下一个节点及其在下一段信道上所占用的虚电路号。用该虚电路号替换分组中原先的虚电路号后，再将该分组发往下一个节点。各节点的虚电路表是在虚电路建立过程中建立的。比如，与A节点相连的源端系统要经中间节点B、C跟与D节点相连的目的端系统建立一条虚电路，源端系统可发出一个呼叫请求分组，该分组除了包含目的地址外，还包含源端系统选取的当前未用的最小虚电路号N。例如，A节点收到请求分组后，在A节点与下一节点B间所有已使用的虚电路号之外选取一个最小编号NA，并将请求分组中的逻辑信道N替换成该虚电路号NA，再将分组发送给节点B。此后的各节点依次逐个根据自身实际情况选取新的虚电路号(如NB、NC、ND等)来替换收到的分组中的虚电路号。最后，目的节点D将请求分组传送给与它连接的端系统。在此过程中，每个节点的虚电路表中要记录两个逻辑信道：前一个节点所选取的虚电路号和本节点所选取的虚电路号。这样便使得虚电路所跨越的每一节点上的虚电路号都是惟一的。图5-1给出了一个虚电路表建立的示例。这里假设建立了6条虚电路。由于虚电路上的数据是双向传输的，为保证两节点之间正、反两个方向的虚电路不相混淆，在一个节点选取虚电路号来替换其前一节点的虚电路号时，不仅要考虑与该节点下一节点之间的虚电路号不相同，还要考虑与下一节点作为另一条反向虚电路时前一节点所选取的虚电路号相区别。例如，在建立虚电路1-BAE时(这里1-BAE表示源节点为B，建立虚电路时选取1为虚电路号，并经A传送到E)，

图5-1虚电路建立示例在节点B中，尽管A节点是第一次作为B节点的下一节点，但由于虚电路0-ABCD中A到B间已使用了虚电路号0，因此在出路一栏选B到A间的虚电路号为1。这样，当从节点A发来一个分组时，若它所携带的虚电路号为0，则说明是虚电路ABCD上的正向分组；若为1，则说明是虚电路BAE上的反向分组。对于虚电路2-BFE的建立也是同样情况。各节点的虚电路表空间和虚电路号都是网络资源，当虚电路拆除时必须回收。这可通过任何一个端系统发出一个拆链请求分组，告知虚电路中各节点删除虚电路表中的有关表项来实现。虚电路服务是网络层向运输层提供的一种让所有分组按顺序到达目的端系统的可靠的数据传送方式。进行数据交换的两个端系统之间存在着一条为它们服务的虚电路。为了建立端系统之间的虚电路，源端系统的传输层首先向网络层发出连接请求，网络层则通过虚电路网络访问协议向网络节点发出呼叫分组；在目的端，网络节点向端系统的网络层传送呼叫分组，网络层再向运输层发出连接指示；最后，接收方运输层向发起方发回连接响应，从而使虚电路建立起来。此后，两个端系统之间就可以传送数据。数据由网络层拆成若干个分组送给通信子网，由通信子网将分组传送到数据接收方。上述虚电路的服务是网络层向运输层提供的服务，也是通信子网向端系统提供的网络服务。但是，提供这种虚电路服务的通信子网内部的实际操作既可是虚电路方式，也可以是数据报方式。以虚电路操作方式的网络，一般总是提供虚电路服务。OSI中面向连接的网络服务就是虚电路服务。在虚电路操作方式中，端系统的网络层同通信子网节点的操作是一致的。

以数据报方式操作的网络，也可以提供虚电路服务，即通信子网内部节点按数据报方式交换数据，而与端系统相连的网络节点则向端系统提供虚电路服务。对于端系统来说，它的网络层与节点间通信仍像虚电路操作方式的网络节点间一样，先建立虚电路，再交换数据分组，最后拆除电路。但实际上每个报文被网络节点分成若干个数据报，附加上地址、序号、逻辑信道等信息分送到目的网络节点。目的网络节点再将数据报进行排序，拼成原来的分组，送给目的端系统。因此，源端系统和源网络节点之间、目的网络节点和目的端系统之间的网络层按虚电路操作方式交换分组，而目的网络节点和源网络节点之间则按数据报方式完成分组的交换。尽管通信子网的数据报交换是不可靠的，但是与两端(源端和目的端)紧邻的网络节点做了许多诸如排序、重发等额外工作，从而满足了虚电路服务的要求。例如，在ARPANET中，其内部使用数据报操作方式，但可以向端系统提供数据报和虚电路两种服务。5.3.2数据报在数据报操作方式中，每个分组的传送是被单独处理的。每个分组称为一个数据报，每个数据报自身携带足够的地址信息。一个节点收到一个数据报后，根据数据报中的地址信息和节点所储存的路由信息，找出一个合适的出路，把数据报原样地发送到下一节点。由于各数据报所走的路径不一定相同，并且各个节点是根据当时网络的流量、故障等情况进行路由选择的，因此不能保证各个数据报按顺序依次到达目的地，有的数据报甚至会中途丢失。整个过程中，没有虚电路建立，但是要为每个数据报做路由选择。数据报服务一般仅由数据报交换网来提供。端系统的网络层同网络节点中的网络层之间，一致地按照数据报操作方式交换数据。当端系统要发送数据时，网络层给该数据附加上地址、序号等信息，然后作为数据报发送给网络节点；目的端系统收到的数据报可能是不按序到达的，也可能有数据报的丢失。例如，在ARPANET、DNA等网络中，就提供了数据报服务。数据报服务与OSI的无连接网络服务类似。由虚电路交换网提供数据报服务的组合方式并不常见。可以想象有这么一种特殊情况：一个端系统的网络层已经构造好了用于处理数据报的服务，而当它要接入以虚电路方式操作的网络时，网络节点就需要做一些转换工作。当端系统向网络节点发送一个携带有完整地址信息的数据报时，如果发向同一地址的数据报数量足够大，则网络节点可以为这些数据报从源网络节点到目的网络节点间建立一条虚电路，所有具有相同目的地址的数据报在这条虚电路上传送完时，这条虚电路便可以拆除。所以，这种数据报服务具有了虚电路服务的通信质量，但这样做不经济且效率不高。最明显的例子是在ATM子网上运行IP。5.3.3虚电路子网和数据报子网的比较如果两个端系统间要长时间进行数据传输，特别是在交互式应用中每次传输的数据很短的情况下，使用虚电路方式可能更加合适些。虚电路方式允许数据分组只含位数较少的虚电路号，而并不需要完整的目的地址，从而节省路由器和输入/输出线路的带宽。虚电路方式的代价是，在中间节点占用用于存放虚电路表的内存空间。另外，虚电路的建立需要一定的时间，这个时间主要是用于各个路由器寻找输出线路和填写虚电路表。但在数据传输过程中，分组的路由选择却比较简单，仅仅查找虚电路表即可。数据报方式不需要连接建立过程，它传输少数几个分组时的速度比使用虚电路时要简便灵活得多，每个数据报根据当时网络的流量等情况来选择路由。每个节点没有额外的开销，只是每个分组在每个节点都要进行路由选择，这样会增加分组传输延迟。在通信子网内部，虚电路方式比数据报方式更容易避免拥塞。这是因为，在虚电路建立好后，可以预约所需的网络资源。当分组到来时，所需的带宽和网络节点的存储空间已经预留，可以立即转发。而对于数据报子网，避免拥塞会更困难些，原因是数据报方式中的中间节点不存储网络状态信息。虚电路子网一般提供可靠的通信功能，它保证每个分组按序正确到达。但是，虚电路有它的脆弱性，当某个网络节点出现故障而崩溃且丢失存储的数据后，所有经过它的虚电路就会断掉而没法正常工作。网络节点或通信线路的故障，对于用到它的虚电路来讲是致命的，但在数据报方式中，这种故障带来的影响要小得多，只有暂存在该节点上的分组才可能丢失，而其他分组可以绕过故障到达目的端系统，因此从这点来说，数据报方式比虚电路方式更健壮些。5.4路由选择通信子网为网络源节点和目的节点提供了多条传输路径的可能性。网络节点在收到一个分组后，要确定向下一节点传送的路径，这就是路由选择。在数据报方式中，网络节点要为每个分组路由做出选择；而在虚电路方式中，只需在建立连接时选择一次路由。确定路由选择的策略称为路由算法。路由选择算法是网络层软件的一部分。它在路由协议中起着至关重要的作用，使用何种算法往往决定了最终的路由结果，因此选择路由算法一定要小心。不管是数据报方式还是虚电路方式，都希望路由选择算法具有以下特征：(1)正确性：指算法本身是正确的并能满足用户业务需求所要求的数据通信目标。(2)简单性：要求路由算法设计简单，利用最少的软件和开销，提供最有效的功能。(3)健壮性：路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或路由器配置错误时，都能正确运行，而不会使所有主机中的任务都终止，也不必重新启动该网络。这要求路由选择算法能妥善处理各种变化。由于路由器分布在网络连接点上，所以在它们出故障时会产生严重后果。最好的路由器算法通常能经受时间的考验，并在各种网络环境下被证实是可靠的。(4)公平性：指每个节点发送和接收的机会均等，这与最优性之间存在矛盾。(5)最优性：指路由算法从所有可能的路由中选择最佳路径的能力，“最优”是相对的。对某种算法采用不同的标准所获得的最优路由是不一样的。(6)灵活性：路由算法可以快速、准确地适应各种网络环境。例如，某个网段发生故障，路由算法要能很快地发现故障，并为使用该网段的所有路由选择另一条最佳路径。(7)快速收敛：收敛是指，在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。设计路由算法时要考虑的技术要素有：(1)选择最短路由还是选择最佳路由。(2)通信子网是采用虚电路操作方式还是数据报的操作方式。(3)采用分布式路由算法(网络中所有节点通过相互交换路由信息，独立地为到达的分组选择下一步的路由)，还是采用集中式路由算法(由中央节点或始发节点周期性收集各链路状态，经过计算后周期性地向各网络节点提供路由表，由它来决定整个网络的路由)。(4)关于网络拓扑、流量和延迟等网络信息的来源。(5)是采用静态路由选择策略(也称非自适应算法，即只在节点或链路故障时才改变网络路由的算法)，还是采用动态路由选择策略(也称自适应算法，即根据网络拥塞和拓扑结构变化情况，频繁改变路由选择的算法)。路由选择按不同的算法可以分为许多类型：静态路由和动态路由、集中路由和分布路由、层次路由和非层次路由、单路路由和多路路由、域内路由和域间路由、链路状态路由和距离向量路由等等。目前最常用的路由协议有：路由信息选择协议RIP(RoutingInformationProtocol)、内部网关路由协议IGRP(InteriorGatewayRoutingProtocol)。外部网关协议EGP(ExternalGatewayProtocol)、边界网关协议BGP(BorderGatewayProtocol)、开放式最短路径优先协议OSPF(OpenShortestPathFirst)和距离矢量组播路由协议DVMRP(DistanceVectorMulticastRouting)等。5.4.1静态路由选择静态路由选择算法不检测也不考虑当前的网络拓扑结构和流量信息，而是按照某种固定规则进行路由选择。这种策略也称为非自适应算法。路由表是在路由器加电启动时加载到路由器中的。当一个分组到达某网络节点(即路由器)时，节点只根据分组上的地址信息从固定路由表中找出对应的目的地节点和应选择的下一节点。所以，静态路由的路由表信息是手工管理的。最初是由网络管理员将它输入到路由器的配置中，当网络拓扑结构等发生改变而需要更新路由时，还需由网络管理员手工更新路由信息。在静态路由算法中，有最短路由选择算法、扩散法和基于流量的路由选择算法等。1.最短路由选择法最短路由选择法是一种使用较多的简单算法。在每个网络节点都存储一张表格，表格中每一项记录着对应某个目的节点的下一节点或链路。当一个分组到达某节点时，该节点只要根据分组上的地址信息，便可从固定的路由表中查出对应的目的节点及所应选择的下一节点。网络中一般都有一个网络控制中心，由它按照最佳路由算法求出每对源—目的节点的最佳路由，然后为每一节点构造一个固定路由表并分发给各个节点。计算最短路径的算法有多种，如Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法等。下面将简单介绍一下Dijkstra算法。

Dijkstra算法有时也称为最短路径算法(SPA，ShortestPathAlgorithm)或正向搜索算法(ForwardSearchAlgorithm)。通常使用Dijkstra算法计算从源节点到其他各节点的最短路径，它是利用边的权值来计算的。权值又可以用路径长度、传输延迟、信道带宽、负载和通信开销等项计算出来。为了在计算最短路径的过程中构造路由表，对每个节点上的每个路由表都要用Dijkstra算法计算一次。另外，Dijkstra算法既可作为静态路由算法，也可作为动态路由算法。用来计算路由表项的软件把网络看成一张图。Dijkstra算法由于能用来计算各种意义的最短路径而得到广泛应用。特别是它不要求图中的边代表地理距离，允许为每条边赋予一个非负值，称之为权值(Weight)，并将两站点之间的距离定义为沿该两点间路径的权值之和。值得注意的是：Dijkstra算法利用边的权值作为距离度量来计算图中的最短路径，边数最少的路径不一定有最小权值。图5-2通过一条最短路径的例子来说明这个概念。Dijkstra算法的基本原理并不复杂。算法建立一个站点的集合S，最短距离和下一站尚未计算。最初S包含有除源点外的所有站点，算法开始循环。每次循环时都从S中取出并删除一个与源点之间有最短路径的站点。当它删除站点u时，检查从源点到集合中剩下的每个与u相邻的站点的距离。如果从源点通过u到某站点的权值和比当前的数值小，则更新该值。当所有站点都从S中删去后，就能计算出到每个站点的最短距离，一张正确的下一站路由表就建成了。图5-2节点5，4之间的最短路径用粗线表示

Dijkstra算法的实现是很直观的。除了用来存储图信息的数据结构外，算法还需要三种数据结构：到每个站点的当前距离，最短路径的下一站，有关剩余站点的信息。如图5-2中所示，以数字1～n来表示站点，这样使得算法的实现比较高效，因为表示站点的数字可用来作为数据结构的索引。特别是算法使用两个数组D和R，每个站点都各有一项，使用站点数作为索引。数组D的第i项存储从源点到站点i的当前最短距离，数组R的第i项存储沿所计算路径可到站点i的下中跳。集合S保存有站点数的双重链接，用以搜索整个集合或删除一个项。下面的算法用weight(i，j)函数返回站点i到站点j的边的权值，如果从站点i到站点j没有边，则weight函数返回一个保留值infinity。实际上可用图中大于任何路径权值和的数值来表示无穷大(infinity)，得到无穷大值的一个方法是把所有边的权值相加后再加1。

给定：一张指定了源点并为每条边赋以一个非负权值的图。计算：从源点到其他每个站点的最短距离和下一站路由表。方法：初始化集合S，包含除源点外的所有站点；初始化数组D，如果从源点到v有边存在，则D[v]为该边的权值，否则为infinity；初始化数组R，如果从源点到v有边存在，则R[v]为源点，否则为0；While(集合S非空)｛从S中选择一站点u，此D[u]是最小的；如果(D[u]是infinity)｛错误：S中无路径存在；退出；｝把u从S中删去；对(u，v)是边的每个站点v｛如果(v仍在S中)｛c＝D〔u〕+weight(u，v)；如果(c＜D[v])｛

R[v]＝u；

D[v]＝c；｝｝｝｝上面曾经提到，边的权值可以是根据距离、信道带宽、平均通信量、通信开销、队列平均长度、测量到的延迟和其他一些因素计算出来的值。例如，一些广域网技术以路径上的交换机的数目来表示距离，对这种技术，算法为图中每边均取权值为1。其他广域网技术中权值可用连接的容量来表示等。2.扩散法扩散法是一种最简单的路由算法。一个网络节点从某条线路收到一个分组后，再向除该线路外的所有线路重复发送收到的分组。结果最先到达目的节点的一个或若干个分组肯定经过了最短的路径，而且所有可能的路径都被尝试过。显然扩散法会产生大量的重复分组，如果不采取一些措施来抑制这种过程，有可能会产生无穷多个分组。一种措施是让每个分组的头部包含站点计数器，每经过一个站点，计数器减1，当计数器为0时，就扔掉分组。理想的情况是计数器的初值为从源端到目的端的路径长度。如果发送者不知道该路径的长度，可以按最坏的情况，即子网的直径来设置初值。另一种措施是记录下分组扩散的路径，防止它第二次再扩散到已扩散过的路径中。为了达到这个目的，可以让连接源端系统的节点给它所接收的来自端系统的每一个分组一个序号，每个节点对源端网络节点有一张表，用来指明已见到的是源端生成的那个序号，这样就很容易知道后来接收的分组是不是重复的，若是就丢弃，否则记录该分组序号，再转发到所有其他节点。为了防止该表无限制地增长，每个表应加一个计数器K作为参数，表示直到K的序号都已记录下来了，这样小于K的表项就可以不再需要了。另一种较为实际的措施称为选择性扩散法。在这种算法中，网络节点并不将每一个发送来的分组从每一条线路上发出，而是仅发送到与正确方向接近的那些线路上。不太可能将一个物理上应该向西传送的分组传送到向东的线路上去，除非网络拓扑结构特别奇特。在实际网络中，扩散法很少被使用，但可用于一些特殊的场合。例如军事网络等健壮性要求很高的场合。即使有的网络节点遭到破坏，只要源端、目的端系统间有一条信道存在，则扩散法路由选择仍能保证数据的可靠传送。另外，这种方法也可用于将一个分组数据源传送到所有其他节点的广播式数据交换中。它还可被用来进行网络的最短路径及最短传输延迟的测定。3.基于流量的路由选择以上算法计算最短路径时，只考虑了网络的拓扑结构，而没有考虑到网络的负载。在有的时候，路径不是最短，但可能是最好的路由选择。基于流量的路由选择算法是一种既考虑拓扑结构又兼顾网络负载的静态路由算法。在有些网络中，每对节点间的通信流量是相对稳定和可以预测的。在预先知道节点间平均通信量的情况下，可以对流量进行数学分析，以优化路由选择。也就是说，对某一给定的线路，如果已知网络负载量与平均流量，那么可以根据排队论计算出该线路上的平均分组延迟。由所有的线路平均延迟，可直接计算出流量的加权平均值，从而得到整个网络的平均分组延迟。因此，路由选择问题就归结为如何找出产生网络最小延迟的路由选择算法。要采用这种技术，有些信息必须是提前知道的。首先，必须知道网络拓扑结构；其次，必须知道各节点间平均通信流量；第三，必须知道各条线路的容量；最后，采用适当的路由选择算法。为了说明这种方法，考虑图5-3(a)所示的全双工通信子网。线上的数值表示各方向的线路容量Cij(以“b/s”为单位)。图5-3(b)的矩阵的每一项表示从源节点到目的节点平均通信流量Fij(以“分组/秒”为单位)。例如，从B到D的平均通信流量是3分组/秒，使用路由BFD。注意，矩阵中给出的路由是采用某种路由选择算法计算出来的。图5-3基于流量的路由选择已知这些信息后，就可以直接计算某一线路中的通信总量。例如，B～D的通信量在BF线路上是3分组/秒，在FD线路上也是3分组/秒。类似地，A～D通信量在线路AB、BF、FD上分别为1分组/秒。每条伸向右端线路的总通信量如表5-1中λi列所示。在这个例子中，所有的通信量是对称的，即对所有X和Y，XY的通信量与YX的通信量是等同的。该表也给出了每条线路每秒的平均分组数量，其中μCi是假定分组平均长度为1/μ=800b求得的。表中Ti列给出了由排队论原理推导出的各条线路的平均延迟：其中1/μ是以“b”为单位的分组平均长度，C是以“b/s”为单位的线路容量，λ是以“分组/秒”为单位的平均流量。例如，如果容量μC=25分组/秒，且实际流量λ=14分组/秒，那么平均延迟为91ms。注意：当λ=0时，其平均延迟仍为40ms，对应于容量为25分组/秒。也就是说，“延迟”包括排队时间和服务时间。表5-1每段线路的通信量i线路λi(分组/秒)Ci(kb/s)μCi(分组/秒)Ti(ms)权值1AB142025910.1712BC122025770.1463CD61012.51540.0734AE112025710.1345EF135062.5200.1596FD81012.52220.0987BF102025670.1228EC82025590.098为了计算出整个网络的平均延迟时间，取所有8条线路的加权和，其中权值是总通信量使用该线路的比例。在本例中，平均延迟时间为86ms。

为了评价一个不同的路由选择算法，可以重复整个过程，仅用不同的流量就可以得到一个新的平均延迟。如果限定用一种路由选择算法，那么，就只有有限制地为分组选择从源到目的地的路由的方法。可以非常简单地编写一个适用于全部算法的程序，找出哪种算法的平均延迟最小。因为这些计算可以预先脱机进行，费用可能不是个大问题。那么这一算法就是最好的路由选择算法。5.4.2动态路由选择对于静态路由选择算法，只能在网络业务量或拓扑结构变化不大的情况下，才能获得较好的网络性能。对于网络突发性的流量，静态路由选择算法的表现很差，这样只能使用动态路由选择算法。动态路由选择算法是指路由器能够根据网络的当前状态信息，如流量和拓扑结构变化等情况，作出相应的路由选择。也就是说，网络管理员通过配置命令启动动态路由之后，路由进程就能自动地从网络上获取信息以更新自己的路由表。当路由表发生变化，就会在相邻或所有的路由器之间进行信息传递。动态路由选择算法也称为自适应路由算法。现代计算机网络系统通常采用动态路由选择算法。根据网络状态信息的来源，可以简单地把动态路由选择分为三类，即孤立路由选择、集中路由选择和分布路由选择，它们分别对应着网络状态信息的三种来源：本地、所有节点和相邻节点。孤立路由选择算法中，节点只根据自己搜集到的有关信息做出路由选择的决定，不与其他节点交换路由选择信息。这种算法虽然不能正确确定距离本节点较远的路由选择，但还是能较好地适应网络流量和拓扑结构的变化。一种简单的孤立路由选择算法是Baran在1964年提出的热土豆(HotPotato)算法：当一个分组到来时，节点必须尽快脱手，将其放入输出队列最短的方向上排队，而不管该方向通向何方。集中路由选择算法中，在每个节点上存储一张路由表。集中路由选择算法中的节点路由表由路由控制中心RCC(RoutingControlCenter)定时根据网络状态计算、生成并分送到各相应节点。由于RCC利用了整个网络的信息，所以得到的路由选择是完美的，同时也减轻了各节点计算路由选择的负担。孤立路由算法和集中路由算法都不是非常完善的。在采用分布路由选择算法的网络中，所有节点定期地与每个相邻节点交换路由选择信息。分布路由选择根据来自相邻节点的信息，通过一个最短花费路由算法计算出到每个目的地的路由。相比之下，分布路由选择算法得到了广泛的应用。在分布路由选择算法中最常用的是距离矢量路由选择算法(DistanceVectorRouting，DVR)和链路状态路由选择算法(LinkStateRouting，LSR)。

1.距离矢量路由选择算法

Dijkstra算法是从给定源节点出发向前产生最短路径的。另一种方法是Bellman-Ford算法，有时也称为反向搜索算法(BackwardSearchAlgorithm)，它是从目的节点出发反向计算最短路径的。距离矢量路由算法是Bellman-Ford算法的具体实现。在距离矢量路由算法中，要求每个节点定期发送其路由表全部信息到相邻节点上。显然，在每个节点上均存储一张以网络中其他节点为索引的路由选择表，网络中每个节点占用表中一项，每一项又分为两个部分，一部分是希望使用的到目的节点的输出线路，另一部分是估计到目的地节点所需要的延迟或距离。度量标准可以是传输延迟或链路段数、等待的分组数、剩余的线路和带宽等。如果采用传输延迟作为度量标准，各节点可以发送一个特别“响应”分组来测出延迟，接收者收到后加上时间标记就立即送回。因此各节点可以知道至其各相邻节点的分组传输延迟。每一个节点每隔时间T就向其相邻节点送一张它至其余各目的节点的估计延迟清单。各节点同时也能收到来自各相邻节点的类似清单。假如某节点刚收到一张来自相邻节点X的延迟清单，其中Xi表示X节点到节点I的传输延迟，那么，如果该节点同时也知道它至节点X的延迟是m，则它经过X到节点I的传输延迟就是Xi+m。只要各相邻节点均作类似计算，那么各节点就可以估计出最短延迟的路由，从而得到一张新的路由表。这种更新过程如图5-4所示。5-4(a)表示一个子网。5-4(b)的前4列表示节点J从相邻节点收到的延迟清单。例如，节点A认为到节点B的延迟为12ms，到节点C的延迟为25ms等等。图5-4基于距离矢量的路由选择假定节点J已估计它到其相邻节点A、I、H和K的延迟分别是8ms、10ms、12ms和6ms，新的路由表是如何生成的呢？先考察一下怎样计算从节点J到节点G的新路由。如果经过节点A转发分组到节点G的话，需要26ms。经过节点I、H和K到G分别需要41ms、18ms和37ms。这些值中最小的是经过节点H到G的18ms，因此，就在路由选择表中填上到G的延迟为18ms，所用的路由经过节点H。对所有其他目的地做相同的计算，得到的路由表如图5-4(b)中最后一列所示。距离矢量路由算法在理论上能有效地工作，但在实际运用中却有很大的缺陷：尽管它可以收敛到正确的路由，但收敛的时间可能太慢。特别是它对好消息的反应迅速，但对坏消息却反应迟钝。当一条路由改变，例如一条新的连接出现或一条老的连接出现故障时，相关信息将缓慢地从一个节点传送到另一个节点，也就是说，在这期间，有些节点中的路由选择信息可能是不正确的。这样将导致网络中各节点的路由表信息不一致，将会产生路由环路问题(RoutingLoops)，也即无穷计算问题。为了解决这个问题，可以采用定义一个最大数、水平分割(SplitHorizon)或抑制定时器(Hold-DownTimer)等方法。2.链路状态路由选择算法链路状态路由选择算法也称为最短路径优先(ShortestPathFirst，SPF)算法，它最初是在1979年用来替代ARPANET中的距离矢量路由算法。主要原因是：首先，延迟度量主要考虑队列长度，不考虑链路的带宽；其次，距离矢量路由算法的可扩展性不好，除了前面讲的无穷计算问题外，还有就是算法交换的数据很多。在每个节点(路由器)中运行的LSR算法包括五个部分：发现它的相邻节点并获得它们的网络地址；测量到它各相邻节点的延迟或花费；构造一个分组来通告它所知道的所有路由信息；将该分组发送到所有其他节点；计算到每个其他节点的最短路径。事实上，通过上述过程可以测得完整拓扑信息和所有延迟，并将它发送到每一个节点。然后，就可以采用Dijkstra算法求得到每一节点的最短路径。上述五部分具体内容如下：

1)发现相邻节点当一个节点(路由器)启动以后，它首先要知道它的相邻节点是谁，这是通过向每条链路发送特殊的HELLO分组来实现的。在这些链路另一端的节点将会发送回来一个应答来说明它是谁。这个名字必须是全局惟一的。2)测量链路延迟或花费链路状态路由算法要求每个节点知道它的相邻节点的延迟，至少有个合理的估计值。取得延迟的最直接方式就是发送一个要求相邻节点立即响应的ECHO分组。通过测量一个来回的时间再除以2，发送方节点就可以得到一个可靠的延迟估计值。要想更精确的结果，可以重复这一过程多次，再取平均值。在测量延迟时，既可以把负载考虑进去，也可以忽略。如果要考虑负载因素，往返时间应该从ECHO分组进入队列时开始计时；如果忽略负载，计时器就得从ECHO分组排到队列第一位时开始计时。在延迟测量时引入流量因素意味着当一个节点在两条具有相同带宽的链路间进行选择时，如果一条链路总是很繁忙，而另一条相比要好得多，那么后者将被认为是一条更短的路径。这样将获得较好的性能。但不幸的是，它也可能会引起路由的振荡，导致不稳定的路由选择和很多潜在的问题。3)构造链路状态分组(LinkStatePacket)

每个节点都构造自己的一个链路状态分组，它包括发送节点的标号、该分组的序号和年龄，以及发送节点的相邻节点列表以及发送节点到这些相邻节点的传输延迟。构造这些分组很容易，难的是决定何时构造分组。一种方法是周期性地构造这些分组，即每隔一定时间间隔就依次构造；另一种方法是在链路状态发生变化时才构造这些分组，像链路或相邻节点的增删、故障或特性改变等情况发生时。4)发布链路状态分组该算法中最具技巧性的部分就是如何可靠地发布链路状态分组。当分组被发布和使用后，首先得到分组的节点将改变其路由选择，但是，其他的节点可能还在使用不同版本的拓扑结构，这样将会导致不一致、死循环、不可达和其他问题。链路状态分组发布的最基本方法是采用扩散法。为了防止每个节点处理和传送过时的分组，在分组中引入了序号。每个节点仅传送序号大于已记录的最大序号的分组。为了防止序号出错，在分组中还引入了年龄，年龄每秒递减一次，如果年龄为0，则该分组将被丢弃。为了防止节点间线路出问题，所有链路状态分组都需要应答，以提高传输的可靠性。另外，为了处理链路状态分组在扩散法中需要发送到哪些相邻节点、需要对哪条链路的分组进行应答的问题，每个节点需要构造一个分组的存储数据结构。5)计算新路由当每个节点获得所有的链路状态分组后，就可以构造一个完整的网络拓扑，此时每个节点就可以运行Dijkstra算法来构造到达所有目的节点的最短路由。链路状态路由算法已广泛应用于多种实际网络中，例如，Internet中的OSPF(OpenShortestPathFirst)采用了该算法，ISO的无连接网络层协议(CLNP)使用的中间系统至中间系统IS-IS(intermediatesystem-intermediatesystem)协议也采用了该算法。距离矢量算法和链路状态算法的主要区别在于：前者传送的路由信息包含整个网络拓扑结构的信息，然而它是不可靠的，因为它包含有一个节点从其他节点获得的信息；链路状态算法的路由选择信息仅包含一个节点直接相连链路的状态，然而这个消息是可靠的，因为发送节点本身可以验证它。在链路状态路由选择算法中，每个节点都知道所有的节点分布在哪里，以及哪些链路将它们互连。每个节点都拥有关于整个网络的同样的拓扑信息。而且，路由更新分组相当短，因为它们仅包含直接链路的状态。由于链路状态算法收敛更快，因此它在一定程度上比距离矢量算法更不易产生路由环路问题。但另一方面，在大多数情况下，链路状态算法要求比距离矢量算法有更强的CPU处理能力和更多的内存空间，这是因为存储空间必须能够保存来自不同数据库、拓扑结构和路由表的信息，另外，使用Dijkstra算法计算最短路径需要执行一个处理任务，这个处理任务与网络中的链接数量和节点数量的乘积成正比。因此链路状态算法将会在实现时显得更昂贵一些。5.5流量控制和拥塞控制5.5.1流量控制由于收发双方各自使用的设备工作速率和缓冲存储空间的差异，可能出现发送方发送能力大于接收方接收能力的现象，若此时不对发送方的发送速率进行适当的限制，前面来不及接收的分组将被后面不断发送来的分组淹没，从而造成分组的丢失而出错。因此，流量控制实际上是对发送方数据流量的控制，使其发送速率不致超过接收方所能处理的速率。在这个过程中，需要通过某种反馈机制使发送方知道接收方是否能跟得上。要有一些规则使得发送方知道在什么情况下可以接着发送下一帧，而在什么情况下必须暂停发送，以等待收到某种反馈信息后再继续发送。流量控制并不是哪一层所特有的功能，许多高层协议中也提供流量控制功能，只不过流量控制的对象不同而已。比如，对于数据链路层来说，控制的是相邻两节点之间数据链路上的流量，而对于运输层来说，控制的则是从源到最终目标之间端对端的流量。流量控制只与某个发送者和某个接收者之间的点到点通信有关。有时候，拥塞控制与流量控制容易混淆，其原因在于某些拥塞控制算法会发送反馈给发送者，以要求它们减慢发送速度。这样，一个主机在收到一个要求减慢速度的消息时，可能是因为接收者跟不上输入，也可能是因为网络承受能力有限。5.5.2拥塞控制拥塞是指到达通信子网中某一部分的分组数量太多，超出了网络所能承受的处理能力，使得该部分网络几乎不能够正确地传送任何分组，以致引起这部分乃至整个网络性能下降的现象。严重时甚至会导致所有的信息缓冲区全部占满而无法空出，使得网络通信停止，即出现所谓的死锁现象(或称为拥塞崩溃)。这种现象跟公路网中经常遇见的交通拥挤一样，当节假日公路网中车辆大量增加时，各种走向的车流相互干扰，使每辆车到达目的地的时间都相对增加(即延迟增加)，甚至有时在某段公路上车辆因堵塞而无法开动(即发生局部死锁)。造成拥塞的原因有很多。如果突然之间，分组流同时从多个输入线到达，并且要求输出到同一线路，这就将建立起队列。如果没有足够的空间来保存这些分组，有些分组就会丢失。节点(路由器)的处理器速度慢也能导致拥塞。在路由器互连形成的网络中，如果路由器的处理器的处理速度太慢，以至于不能及时地执行缓冲区排队、更新路由表等任务，那么，即使有多余的线路容量，也可能使队列饱和。类似的低带宽线路也会导致拥塞。如果节点(路由器)没有空闲缓冲区，它必须丢弃新到来的分组。当有一个分组被丢弃时，发送方可能会因为超时而重传此分组，或许要重发多次。由于发送方在未收到确认之前必须在缓冲区中保存该分组，故拥塞迫使发送方不能释放在通常情况下会释放的缓冲区。这样便形成恶性循环，使拥塞加重。拥塞控制与流量控制不同。拥塞控制主要用于保证网络能够传送待传送的数据，将涉及网络中所有与之相关的主机、路由器、路由器存储转发处理的行为，是一种全局性的控制措施。流量控制只涉及发送方和接收方之间的点到点的流量控制行为，主要用于确保发送方的发送速率与接收方的缓冲区容量相匹配，以防止在接收方缓冲区不足时发生数据丢失。1.拥塞控制的基本原理从控制论的角度来看拥塞控制，可以把拥塞控制算法分成开环控制和闭环控制两大类。开环控制算法通过良好的网络系统设计来避免拥塞问题的发生。在网络运行过程中，何时接受新分组，何时丢弃分组以及丢弃哪些分组都是事先规划好的，并不考虑当前的网络流量状况。闭环控制算法通过反馈机制来调整当前网络流量，使网络流量与网络可用资源相协调，从而使网络拥塞问题得到解决。由于闭环控制算法能够根据当前网络状况对流量进行动态控制，具有较高的效率。因此，现代网络系统大都采用闭环控制算法来解决网络拥塞问题。在闭环控制算法中，关键措施在于：监视机制，以便检测网络何时何地发生了拥塞；反馈机制，将发生拥塞的信息传送到可能采取行动的地方(如控制点)；调整机制，调整网络的运行以解决出现的问题。监视机制将根据当前网络状况来监视网络是否发生了拥塞，判断的依据主要有：因缺少缓冲区空间而丢弃的分组数量、平均分组队列长度、超时重发分组的数量、平均分组延迟时间等。如果检测数据超过了临界值，则意味着可能发生了网络拥塞。反馈机制将发生拥塞的信息从拥塞点传送到控制点。反馈方式有显示反馈和隐式反馈两种。显示反馈采用由拥塞点向控制点反馈一个警告分组的方式来通告网络已发生拥塞；隐式反馈通过发送端(控制点)观察应答分组返回所用时间的方式来判断网络是否发生了拥塞。调整机制通过拥塞点和控制点(或发送方)相互协调来解决拥塞问题。控制点通过降低负载，即降低分组发送速率来缓解拥塞；拥塞点通过负载脱落(LoadShedding)，即丢弃一些分组来疏导通信，或者通过启用备份的空闲系统资源来提高通信容量。2.拥塞预防策略流量控制和拥塞控制可以出现在所有协议层次上，不过主要还是在数据链路层、网络层和传输层。拥塞控制主要是网络层的功能。在网络层，是选择虚电路还是数据报数据交换方式将对拥塞产生影响。因为很多拥塞控制算法只用于虚电路子网。分组排队和服务策略关系到是否为每条线路建立一个队列，每条输出线一个队列，或者兼而有之。它还关系到分组的处理顺序(如基于优先级等)。丢弃策略说明当没有剩余空间时，哪些分组被丢弃。好的策略能减缓拥塞，坏的策略只能使它更糟。路由选择算法通过将通信量分散到所有线路上来避免拥塞，而坏的路由算法会将过多的通信量发送到本来已经拥塞的线路上。最后，分组生存期策略管理决定一个分组在丢弃前能存活多长时间。如果生存期太长，丢弃的分组可能会长时间地妨碍正常工作；但如果太短，又可能在分组到达目的地之前就超时，由此导致重传。3.通信量控制策略拥塞发生的主要原因在于通信量常常是突发性的，如果主机能以一个恒定的速率发送分组，拥塞将会少很多。而对于子网来说，子网强迫分组以某种预定的速率传送。这种方法被广泛应用到ATM网络中，称为通信量整形(TrafficShaping)。

用户通过一个流规范(FlowSpecification)说明自己的通信量模式，并经过协商过程来与通信子网和接收者达成一致。然后通信子网通过一个通信量控制策略(TrafficPolicing)来进行控制，调整分组传输的速率，从而减少可能发生的拥塞。通信量控制策略容易在虚电路子网上实现，在数据报子网上实现，则比较困难。但是，对于数据报子网，可以在传输层连接中使用相同的方法。通信量控制策略主要采用两种算法：漏桶算法和它的改进版本——令牌桶算法。1)漏桶算法想象一个底部有一个小孔的桶，不管水注入桶的速率如何，只要桶中有水，水从桶中往外漏的速率是恒定的，一旦桶空了，往外漏的速率变为零。在桶满之后，再注入桶中的水都会从桶边溢出，不会通过桶底的小孔流出。把这种思想用在分组的传输上，就是漏桶算法(LeakyBucketAlgorithm)，这实际上是一个有恒定服务时间的单服务器排队系统。漏桶是一个有限内部队列，当分组到达时，如果队列未满，将其加到队尾；如果队列已满，分组被丢弃。如果队列非空，每个时钟节拍发送一个分组。上面说的是分组大小固定的情况，如果分组大小可变，最好采用字节计数的机制。字节计数漏桶的实现和原始的漏桶算法相类似。每个节拍开始时，计数器初始化为n(即每个节拍允许发送的字节数)。如果队列的第一个分组的字节数小于当前计数值，就将该分组发送出去，并把计数器减去该分组的字节数。只要计数器的值足够大，在同一节拍内还可以继续发送其他分组。如果计数器值小于队列中下一个分组的字节数，传输便停止，直到下一个节拍开始，计数器被重新设置，开始另一轮发送过程。2)令牌桶算法漏桶算法强迫输出保持一个固定的平均速率，而不管突发通信量的大小。对于很多应用，希望当大的突发通信量到来时，输出也相应加速一点，因此需要一个更有弹性的、更合适的决不会丢失数据的算法。令牌桶算法(TokenBucketAlgorithm)就是这样一种算法。在这个算法中，每隔t秒生成一个令牌，而漏桶可以保留这些令牌。如果要发送分组，必须首先抓住一个令牌，在发送分组后令牌被销毁。令牌桶算法提供了一种有别于漏桶算法的通信量整形方法。漏桶算法不允许主机把空闲时候的发送权保留下来，以备以后大的突发负载出现时使用。令牌桶算法则允许保留最多为桶的大小(n个分组)的发送权。这一特性意味着多达n个分组的突发负载可以马上被发送出去，从而允许输出的分组流有一些突发性，并且对那些输入流的突发性提供更快的响应。两种算法的另一区别是，令牌桶算法在桶满时会丢失令牌，但决不会丢弃分组。与之相比，漏桶算法会在桶满时丢弃分组。另外还有一些细小的不同之处，即每个令牌有可能代表的不是发送一个分组的权利，而是k个字节。只有当所有的令牌代表的字节长度超过分组长度时，该分组才能被发送，零碎令牌可以被保留起来供将来使用。5.6Internet的网际协议IP网络层中有四个重要的协议：互联网协议IP、互联网控制报文协议ICMP、地址转换协议ARP和反向地址转换协议RARP。

网络层的功能主要由IP来提供。除了提供端到端的分组发送功能外，IP还提供了很多扩充功能。例如，为了克服数据链路层对帧大小的限制，网络层提供了数据分块和重组功能，这使得很大的IP数据报能以较小的分组在网上传输。5.6.1IP地址

Internet上的主机和路由器都有一个IP地址，它包括网络号和主机号两部分。互联网上的每台网络设备的IP地址都是惟一的。IP地址由32位的二进制数来表示。通常，IP地址用点分十进制数的形式表示。把32位地址分成4个8位组，每个8位组的十进制数最大值为255。IP地址的网络号用来标明网络设备所连接的网络，主机号标明网络上的某个特定的网络设备。

IP地址分为以下几类：A、B、C、D、E类地址，格式如图5-5。图5-55类IP地址及其范围

A类地址用来支持超大型的网络。A类地址的第1位总是0，第一个8位组用来标识地址的网络部分，其余的3个8位组用作地址的主机部分。每个使用A类IP地址的网络最多可以为224－2=16777214台连接到网络上的设备分配IP地址。减2是为网络和广播预留的地址，B、C、D类地址中减2的原因与此相同。

B类地址用来支持中大型网络的需求。B类地址的头两位总是10，IP地址的头16位用来标识地址的网络部分，剩余的2个8位组用作地址的主机部分。每个使用B类IP地址的网络最多可以为216－2=65534台连接到网络上的设备分配IP地址。

C类地址用来支持小型网络的需求。C类地址的头3位总是110，IP地址的头24位用来标识地址的网络部分，剩余的8位用作地址的主机部分。每个使用C类IP地址的网络最多可以为28－2=254台连接到网络上的设备分配IP地址。除了分配一个地址给每台主机外，地址还可以表示整个网络或某些计算机等。IP定义了一套特殊的地址格式，称为保留地址。特殊IP地址的分配见表5-2。表5-2特殊IP地址的分配网络部分主机部分地址类型用途全0全0本机启动时使用网络号全0网络标识一个网络网络号全1直接广播在特定网上广播全1全1有限广播在本地网上广播127任意回环(Loopback)测试

IP地址0.0.0.0用于启动以后不再使用的主机。以0作网络号的IP地址代表当前网络。全部由1组成的地址代表内部网络上的广播，通常是一个LAN。有一个正确的网络号，主机号全为1的地址可以用来向Internet上任意远程LAN发送广播分组。形如127.xx.yy.zz的地址都保留作回环测试。发送到这个地址的分组会回送给发送者，而不会通过网络或网络接口卡。通过向这个地址发送测试数据(如ping)，一台主机可以检查它的IP软件是否在工作。

D类地址是多播地址，主要是留给Internet体系结构委员会IAB(InternetArchitectureBoard)。E类地址保留在今后使用。目前大量使用的IP地址仅A～C类三种。现在能申请到的IP地址只有B类和C类两种。当某个单位向IAB申请到IP地址时，实际上只是获得一个网络号。具体的各主机号则由自己分配，只要做到所管辖的范围内无重复的主机号即可。对于多接口主机(如路由器)，即一个主机同时连接到两个或两个以上网络时，就必须同时具有两个或两个以上的IP地址，其中每一个IP地址对应一个网卡。5.6.2子网划分虽然基于分类的地址系统对Internet服务提供商来说工作得很好，但它不能在一个网络内部做任何路由，其目的是使用数据链路层(桥接/交换)来导引网络中的数据。在大型的A类网络中，这就成了个特殊的问题，因为在大型网络中仅使用桥接/交换使其非常难管理。其解决办法在逻辑上是把大网络分割成若干小的网络，但在基于分类的地址系统中这是不可能的。为了解决这个问题，出现了一个新的域：子网掩码。子网掩码不是一个地址，但子网掩码能够指出地址中哪些部分是网络地址，哪些是主机地址。在子网掩码中，二进制1表示网络地址位，二进制0表示主机地址位。传统的各类地址的子网掩码为

A类：255.0.0.0

B类：255.255.0.0

C类：255.255.255.0

如果想把一个B类网络的地址用作C类大小的地址，可以使用掩码255.255.255.0。用较长的子网掩码把一个网络分成多个网络就叫做划分子网。要注意的是，一些旧软件不支持子网，因为它们不理解子网掩码。例如UNIX的routed路由守护进程通常使用的路由协议是版本1的RIP，它是在子网掩码出现前设计的。上面只介绍了三种子网掩码：255.0.0.0、255.255.0.0和255.255.255.0，它们是字节对齐的子网掩码。但是也可以在字节中间对其进行划分。网络地址和子网地址的主机部分全为0。为了对一个分组进行路由选择，路由器首先必须使用目标主机的IP地址和子网掩码来执行一个“与”运算，从而确定目标网络/子网的地址。运算的结果就是网络/子网地址。子网使我们可以拥有新的规模的网络，包括很小的用于点到点连接的网络(如掩码255.255.255.252，30位的网络地址，2位的主机地址：2个主机的子网，2个主机是由4减去两个不可用地址得到)，或中型网络(如掩码255.255.240.0，20位网络地址，12位主机地址：4094个主机的子网，4094是由4096减去两个不可用地址得到)。注意DNS被设计为只允许字节对齐的IP网络。5.6.3IP分组格式一个IP数据报由一个头部和一个正文部分构成。头部有一个20字节的固定长度部分和一个可选任意长度部分。图5-6给出了一个IP数据报头部包含的各个字段，包括源IP地址(SourceIPAddress)和目的地IP地址(DestinationIPAddress)，源IP地址字段指明发送方的IP地址，目的地址字段指明接收方的IP地址。图5-6IP数据报格式数据报头部里的每个字段都有固定的大小。数据报以4位的协议版本号(当前版本号是4或6)和4位的头部长度开始。头部长度指出以32位字长为单位的头部长度。服务类型(ServiceType)字段包含的值指明发送方是否希望以一条低延迟的路径或是以一条高吞吐率的路径来传送该数据报，当一个路由器知道多条通往目的地的路径时，就可以靠这个字段对路径加以选择。总长(TotalLength)字段为16位的整数，说明以字节计的数据报总长度，包括头部长度和数据长度。最大长度是65535字节。标识(Identification)字段用来让目的主机判断新来的分段属于哪个分组，所有属于同一分组的分段包含同样的标识值。标志(Flags)字段的前一位未用，紧接着的一位表示不要分段，最后一位表示还有进一步的分段。除了最后一个分段的所有分段都设置了这一位，它是用来标志是否所有的分组都已到达。分段偏移(FragmentOffset)字段是13位，指明分段在当前数据报的什么位置。以64位为基本分段单位。生存时间(TimeToLive)字段用来阻止数据报在一条包含环路的路径上永远地传送。当软件发生故障或管理人员错误地配置路由器时，就会产生这样的路径。发送方负责初始化生存时间字段，这是一个1～255之间的整数。每个路由器处理数据报时，会将头部里的生存时间减1，另外，在一个路由器中排队时间过长时生存时间字段值会减少。如果达到0，数据报将被丢弃，一个出错消息被发回给源主机。协议(Protocal)字段指明将分组送给哪个传输进程，可能是TCR，也可能是VDP或其他。头部校验和(HeaderChecksum)字段确保头部在传送过程中不被改变。发送方对除了校验和字段的头部数据每16位对1求补，所有结果累加，并将和的补放入头部校验和字段中。接收方进行同样计算，但包括了校验和字段。如果校验和正确，则结果应该为0(数学上，1的求补是一个逆加，因此将一个值加到它自身的补上将得到零)。为了保证数据报不过大，IP定义了一套可选项(Options)。当一个IP数据报没携带可选项时，头部长度字段的值为5，头部以目的地址(DestinationAddress)字段作为结束。因为头部长度总是32位的倍数，如果可选项达不到32位的整数倍，全0的填充(Padding)字段会被加入以保证头部长度为32位的倍数。5.6.4IP路由选择路由选择是IP协议的最重要功能之一。一个TCP/IP网络是多个物理网络互连而成的，连接这些物理网络的路由器又常称为网关。每个网关都有两个或多个网络的直接连接。与网关不同，主机通常直接连到一个物理网上。把仅有一条线