复习课件-网络层运行机制

第五单元网络层运行机制网络层的任务是把源计算机发出的信息分组经过适当的路径送到目的地计算机，从源端到目的端可能要经过若干中间结点。这能与数据链路层有很大的差别，数据链路层仅把数据帧从线缆或信道的一端传到另一端。因此，网络层是处理计算机网络中端到端数据传输的最低层。网络层在其与传输层的接口上为传输层提供服务。这一接口是相当重要的，因为它往往是公共载体网络与用户的接口，也就是说，它是通信子网的边界。载体网络通常规定了从物理层直到网络层的各种协议和接口，它的工作是传输由其用户提供的分组。基于这种原因，对接口的定义必须十分明确和完善。1大学授课教师：鲁士文2014.10.17第五单元网络层运行机制网络层的服务设计应该遵从三个原则。第一，服务与通信子网技术无关。第二，通信子网的数目、类型和拓扑结构对于传输层是遮蔽的。最后，传输层所能获得的网络地址应采用的方式，即使多个LAN和WAN也应如此。基于上述原则，网络层的设计者有相当大的度来编写提供给传输层的服务的技术规范。网络层的操作可以是面向连接的，也可以是无连接的。2大学授课教师：鲁士文2014.10.17第五单元网络层运行机制为了实现网络层的功能，网络层必须知晓通信子网的拓扑结构(即所有路由器的位置)，并通过子网选择适当的路径。选择路径时应该避免超载一部分通信链路和路由器，而另一些链路和结点却很空闲的现象发生。最后，当源端和目的端处在不同的网络中时，也应该由网络层来处理它们之间的差异，并解决由此带来的问题。本单元先介绍传统的通信子网的概念，接着在数据通信中常用的交换技术，进而阐述网络层设计中的路由选择算法。3大学授课教师：鲁士文2014.10.175.2

交换技术在广域范围内，数据通信典型地是把数据从源端点经过中间交换结点的网络传送到目的地的。这些交换结点不关心数据的内容，它们的目的是提供在端点间移动数据的交换设施，直到它们到达目的地。图5-2示出了一个简单的网络。进行通信的端点设备可以被称作站。站可以是计算机、终端、或其它通信设备，

把其目的是提供通信的交换设备称作结点，它们通过传输链路互相连接成一定的拓扑结构。每个站都附接到一个结点，所有结点的集合就称作一个通信网络。4大学授课教师：鲁士文2014.10.175.2

交换技术5大学授课教师：鲁士文2014.10.175.2

交换技术在交换型通信网络中，从一个站进入网络的数据通过从结点到结点的交换，被选径送往目的地。从图5-2可以看出：*某些结点仅仅连接到其它结点(例如结点5和7)。这些结点唯一的任务是数据的

(对该网络而言)交换。其它的结点连接了一个或多个站;除了它们的交换功能，这些结点还从附接站接收数据，以及把数据投递给附接站。*结点到结点的链路通常是多路复用的，可以使用频分多路复用(FDM)，也可以使用时分多路复用（TDM）。网络一般都不是全连接，也就是说，并非在每一个可能的结点对之间都有一条直接链路。然而在网络的每一对站点之间总是希望有多于一条可能的通路，这样可以增加网络的可靠性。6大学授课教师：鲁士文2014.10.175.2

交换技术在计算机网络中使用三种相当不同的技术:电路交换、报文交换和分组交换。这三种技术在沿着从源到目的地的通

结点把信息从一条链路交换到另一条链路的方式有明显的差异。使用电路交换的通信意味着在通信的两个站之间有一条的通信通路。该通路是连接在一起的一个网络结点间链路的序列。在能够进行通信以前先要建立一条通路。7大学授课教师：鲁士文2014.10.175.2.3

分组交换在分组交换网络中，数据以短的分组形式传送。典型的分组长度的上限是1000个字节。如果一个源站有一个长的报文要发送，该报文就会被分割成一系列的分组(参见图5-3)。每个分组包含用户数据的一部分(或一个短的报文的全部)加上一些控制信息。控制信息至少要包括网络为了把分组送到目的地做路由选择所需要的信息。在路径上的每个结点，分组被接收，短时间

，然而传递给下一结点。8大学授课教师：鲁士文2014.10.175.2.3

分组交换9大学授课教师：鲁士文2014.10.175.2.3

分组交换跟电路交换相比，分组交换具有下列优点：*

线路效率高。单个结点到结点链路可以由许多分组动态共享。分组被排成队列，并且尽可能快地在链

发送出去。而在电路交换中，结点到结点链 的时间是使用同步的时分多路复用方法预先分配的，分配给一条连接的时隙即使空闲也不能让其它连接使用。*分组交换网络可以执行数据速率转换。两个以不同数据速率传输的站可以交换分组，因为每一个站都以它自己的速度连接到它的通信网结点。而在电路交换中，电路所连接的两个站必须以同样的速率发送和接收。10大学授课教师：鲁士文2014.10.175.2.3

分组交换跟电路交换相比，分组交换具有下列优点（续）：

在电路交换网络中，当流量负载很重时，一些呼叫会被阻塞，即在网络上的负载减少之前网络新的连接请求。而在分组交换网络中，分组仍然会被接受，但投递延迟增加了。

分组交换通常都不是发送用户的整个报文，取而代之的是将一个报文划分成若干个可以存放在内存中的分组，从而提高了交换速度，适用于交互式数据传输。11大学授课教师：鲁士文2014.10.175.2.3

分组交换分组交换根据其通信子网向端点系统提供的服务还可以进一步分成数据报和虚电路两种交换类型。在数据报分组交换中，每个分组的传送被单独处理，就像报文交换中的报文一样，但是若干个分组才构成一个报文，每个分组称为一个数据报。每个分组都有一个头，头中包含目标结点的地址，内层头中还包括顺序号，表明分组在报文中的位置。一个结点接收到一个数据报后，根据数据报中的地址信息和结点所的路由信息，找出一个合适的出路，把数据报原样地发送到下一结点。12大学授课教师：鲁士文2014.10.175.2.3

分组交换----数据报分组交换当端系统的通信子网用户要发送一个报文时，先把报文拆成若干个带有序号和地址信息的分组，将分组传输给网络中的第1个交换结点，该结点保持分组一个很短的时间，它利用提供的最佳路由尽快传递每一分组，当分组被另一结点成功接收后，就删除在内存中的这个分组。该过程在所需要经过的多个交换结点重复进行，直到所有的分组都抵达它们的目的地。分组可以走不同的路由，也可以按不同顺序到达目的地。目的地端系统利用分组(即数据报)中的顺序号(通常包含在

头中，例如TCP头)，以正确的顺序重组成报文。在整个过程中没有虚电路的建立，但要为每个数据报作路由选择。图5-4示出了源端系统发出3个数据报经过通信子网的3个不同路径到达同一目的地端系统。13大学授课教师：鲁士文2014.10.175.2.3

分组交换----数据报分组交换14大学授课教师：鲁士文2014.10.175.2.3

分组交换----虚电路分组交换在虚电路分组交换中，第1个分组决定随后所有分组都要遵从的路由。为了进行数据传输，网络的源结点与目的结点之间先建立一条逻辑通路，源端系统先向源结点发出呼叫请求，要求与目的端系统建立连接。源结点将该请求借助路由选择经过通信子网的中间结点送往目的地结点，目的地结点最后将请求送给目的地端系统。该呼叫请求是作为一个特殊的分组从源结点传送到目的地结点的。在虚电路建立起来之后，源端系统就可以向目的地端系统发送若干个数据分组。最后由源或目的地端系统发出折除连接的请求分组，这样整个连接就一段一段断开了。呼叫请求和拆除连接请求可能需要对方发回应答分组。15大学授课教师：鲁士文2014.10.175.2.3

分组交换----虚电路分组交换上述传输数据的逻辑通路称虚电路。它之所以是虚的，是因为这条电路不是 的，每个结点到其它结点之间可能同时有若干条虚电路通过，也可能同时与多个结点之间具有虚电路。每条虚电路支持特定的两个端系统之间的数据传输，两个端系统之间也可以有多条虚电路为不同的进程服务，这些虚电路的实际路由可能相同也可能不同。16大学授课教师：鲁士文2014.10.175.2.3

分组交换----虚电路分组交换在图5-5所示的交换通信网中，一个端系统每次建立虚电路时，选择一个没用过的虚电路号分配给该虚电路，以便区别于本系统中的其它虚电路。在传送数据时，每个数据分组上不仅要有分组号、检验和等控制信息，还要有它要通过的虚电路的号码，以区别于其它虚电的分组。在每个结点上都维持一张虚电路表，它的每一项记录了一个打开的虚电路的信息，包括虚电路号、前一结点和下一结点的标识。数据的传输是双向进行的，上述信息是在虚电路的建立过程中确定的。17大学授课教师：鲁士文2014.10.175.2.3

分组交换----虚电路分组交换18大学授课教师：鲁士文2014.10.175.2.3

分组交换----虚电路分组交换由于各个端系统各自独立地选取虚电路号，不可避免地会造成虚电路号的重复。如果两条号码相同的虚电路经过了同一结点，那么就会产生二义性。解决的办法是使用“动态”的虚电路号。当结点A所连的端系统发出呼叫请求时，请求分组中已经包含由端系统所选取的(最低的)未用过的虚电路号N1。A接收到请求分组后并不直接把它送给下一结点C，而是，从在A和C之间所有正在使用的虚电路号之外选取一个最低号码NA，并将请求分组中的虚电路号N替换成NA，然后再把分组送到下一结点C。以后的结点亦依次逐个替换分组中的虚电路号，直到目的地结点D，把从C送来的请求分组中的虚电路号NC替换成与目的端系统之间的虚电路号ND，再把请求分组发送给端系统。这样，在虚电路所

的每段连接上的虚电路号就是唯一的了。19大学授课教师：鲁士文2014.10.175.2.3

分组交换----虚电路分组交换在建立虚电路的同时，每个结点(例如结点A)的虚电路表中的每一项要记录两个虚电路号：由端系统或前一结点所选取的虚电路号(例如N1)和本结点所选取的虚电路号(例如NA)。这样，的问题基本上解决了。在面提出来的有关虚电路分辨给出的例子中，由结点A所连的端系统向D所连的端系统发送分组，从源端系统来看，它总是用它所选取的虚电路号N1来发送和接收分组，而目的端系统也总是在虚电路ND上发送与接收分组。20大学授课教师：鲁士文2014.10.175.3路由选择算法网络层的实质性功能是将信息分组从源端计算机选择路径送往目的地计算机。在绝大多数子网中，分组的整个旅程需要经过多个站段。路由选择算法(routing

algorithm)是网络层

的一部份，它负责确定所收到分组应转发的外出链路。如果通信子网

采用数据报，那么对收到的每个分组都要重新作路由选择。然而，如果子网采用虚电路，则当建立一条新的虚电路时，仅在开头作一次路由选择决策。以后，数据分组就通过这条已建立好的路由传送。后一种情形有时又称作会话路由选择(session

routing)，因为在整个用户会话(例如终端上进行的登录会话或文件传送会话)期内都存在着一条路径。21大学授课教师：鲁士文2014.10.175.3路由选择算法路由选择算法可以分为两大类：非自适应和自适应。非自适应算法不测量、不利用当前的网络拓扑结构和流量参数，而是按照某种固定规则选择路由。每个结点一张表格，每项记录对应某个目的地结点的下一结点或链路，并不记录到达目的地结点的所有中间结点。当一个分组到达某结点时，结点只要根据分组上的地址信息从固定路由表中找出对应的目的地结点及应选择的下一结点，并将分组转发给该下一结点。一般地，网络中有一个中心结点，它按照最佳路由算法求得每对结点间的最佳路由，然后为每个结点构造一个固定路由表，最多在网络拓扑改变时才有可能重新计算和重新装入路由表，或者由操作员在各个路由相关的结点上手工地修改路由表。22大学授课教师：鲁士文2014.10.175.3路由选择算法自适应算法则不同，它进行的路由选择要依靠网络当前状态信息来决定，以设法适应网络流量和拓扑的变化。在自适应路由选择中，关于当前可提供的路由的信息需要在网络结点之间传送，所有结点根据收到的路由选择信息定期地更新它们的路由表格。因此，新的路由、改变了的路由或不可再用的路由都能自动在它们的路由表中反映出来。为了实现自适应路由选择，需要有一个路由选择协议，以定义交换路由选择信息的方式和计算最短路径的方法，因为仅最短路径才被加到路由表格中。当前流行的路由选择协议基于两个重要的算法类型，即距离向量路由选择和链路状态路由选择。23大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.2

距离向量路由选择最早的也是相当简单的路由选择协议算法之一就是距离向量算法。在一个距离向量路由选择(Distance

Vector

Routing)协议中，所有的结点都定期地将它们的整个路由选择表传送给所有与之直接邻接的结点。这种路由选择表包含：每条路径的目的地(另－结点)路径的代价(也称距离)术语“距离向量”

于定期

，一个报文包含有成对的列表(V，D)，这里的V表示目的地(叫做向量)，D是到达那个目的地的距离。注意距离向量是以第一人称报告路由的，即把一个结点送来的通告看成它在说：“我可以到达距离为D的目的地V”。在这种设计中的所有的结点都必须参与距离向量交换，以保证路由的有效性和一致性。24大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.2

距离向量路由选择所有的结点都

从其它结点传送来的路由选择更新信息。并在下列情况下更新它们的路由选择表。*

被通告一条新的路径，该路由在本结点的路由表中不存在，此时本地系统加入这条新的路由。*通过发送来路由信息的结点有一条到达某个目的地的路由，该路由比当前使用的路由有较短的距离(较小的代价)。在这种情况下，就用经过发送路由信息的结点的新路由替换路由表中到达那目的地的现有路由。*在本结点的现有路由表中为了到达某一目的地首先应前往的下一结点如果通告了一个较高的代价，就要使用这一新的代价更新从本结点前往同一目的地的代价。25大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.2

距离向量路由选择

假定路由器知道它到每个相邻路由器的“距离”。如果度量标准是中继段数，距离就是1。如果度量标准是延迟时间，可以通过发送回送

(ECHO)分组来测得(接收方会对分组加上时间标记后尽快返回)。作为一个例子，现在假定用延迟来作为度量标准，且路由器知道到每个邻居的延迟。每隔T毫秒，路由器把它估计的到达各个目的地的延迟的列表发送给每个邻居。它也从各个邻居那里收到类似的列表。假定从邻居X刚刚收到一个表，说明X路由器到达i路由器估计的延时是Xi，如果本路由器知道它到X的延迟是m毫秒，那么它也就知道通过X到达i路由器需要化（Xi+m）毫秒的时间。通过对每个相邻路由器进行类似的计算，本路由器就可以知道哪一个估计值最优，并且在它的新的路由选择表中使用这个估计值和相应的线路。注意，在计算过程中并不使用旧的路由选择表。26大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.2

距离向量路由选择27大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.2

距离向量路由选择在图5-7中,(a)图表示一个子网，(b)图的前4列表示路由器J从相邻路由器收到的时间延迟向量。A认为它到B的延迟是12毫秒，到C的延迟是25毫秒，到D的延迟是40毫秒等。假定J测得它到相邻结点A、I、H、和K的延迟分别是8毫秒、10毫秒、12毫秒和6毫秒。现在

一下结点J怎样计算到路由器G的新路由。它知道如果经A转发分组到G的话，需要26(=18+8)毫秒。类似地，它能计算出经I、H和K到G分别需要41(31+10)毫秒、18(6+12)毫秒和37(31+6)毫秒。这些值中最好的是18，因此，它就在路由选择表中填上到G的延迟为18毫秒。所用的路由经过结点H，对所有其它目的地作类似的计算，得到的路由选择表如图中最后一列所示。28大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.2

距离向量路由选择在完全静态的环境里，距离向量算法将路由到所有目的地。然而当路由迅速改变时，计算是不可能平稳的。当一条路径改变，例如一条新的连接出现或一条老的连接出了故障时，有关信息将缓慢地从一个结点到另一个结点，在这期间，某些网关就可能拥有不正确的路由选择信息。事实上，如果路径变化了的信息不是很快地到所有的结点，就会产生所谓的慢聚合。在某些情况下，通信子网内路由选择信息的不一致会持续一个相当长的时间。下面的插图给出了一个慢聚合问题的例子。29大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.2

距离向量路由选择30大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.2

距离向量路由选择在上面的插图中，结点A直接连到一个以网络标示的广播型网络，它向邻接结点通告一条到达网络仅一个站段距离的路径。结点B向邻接结点通告一条到达网络有两个站段距离的路径。如果结点A和网络之间的链路失效。A将再次通告它到网络的距离为infinity(无穷大)，即不可达，并将这一信息传递到B。然而，在A再次通告之前，B已发布了一个现在过时了的路由信息，A将注意到它可以经过B以三站段的距离抵达网络，这是从B到网络的两个站段加上从A到B的一个站段计算出来的。这样一来，任何经过A送往网络的信息分组都被送到B，而到达B前往网络的任何分组都被送到A。正如插图下半部示出的那样在结点A和B之间形成了路由选择回路。下面的插表列出了本例中结点A和B路由选择表变化的步骤以及在慢聚合过程中所发生的不一致性。31大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.2

距离向量路由选择32大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.2

距离向量路由选择解决慢会聚问题的一个办法是水平

。水平通过

把在一个接口上接收到的关于一个目的地的路由信息再在同一接口上通告来

上述现象的发生。例如，假定结点A有B、C和D3个邻居结点(A到达它们的代价都等于1),它们通告给A的到达一个远方结点Z的代价分别是11、12和13。那么,由于A经过B、C和D前往Z的代价分别是12、13和14,因此A选择的前往目的地Z的通路经过邻居B。由于A所选择的前往目的地Z的路由是根据在连接到B的接口上收到的关于Z的路由信息,A就不要再把它自己到达Z的路由信息

通告给B。

在实际网络的实施中,示例中的结点A在往B发送的通告中会把它到达Z的代价表示成无穷大,尽管A实际上还可以经过C和D以有限代价到达Z。通常人们还把这种解决方案称作“毒性逆转”。33大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.2

距离向量路由选择距离向量算法的主要缺点是网络规模的伸展性差。它对链路状态变化的响应慢，需要大尺寸的路由信息报文交换，并且报文的长度与通信子网内结点的个数成正比。由于距离向量协议需要每个

转发的结点都参与路由信息的交换，因而交换信息的流量也可能非常大。距离向量算法的主要替代方案是一种叫“链路状态”(Link

State)的算法，也称作“最短路径优先”(Shortest

Path

)，简称SPF。SPF算法要求每个参与协议的结点都有完全的网络拓扑信息，这里拓扑信息可以想象成每个结点都有一张地图，地图上标示了所有其它的结点以及它们所连接的链路。在抽象的术语中，结点对应于图中的结点，而连接结点的链路对应于边。当且仅当对应的结点可以直接通信时，在这两个结点之间才有一条边

(链路)。34大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.3

链路状态路由选择参与SPF算法的结点不是发送含有所有目的地信息列表的报文，而是执行下述两项任务。第一，它主动测试所有邻接结点的状态。在图上，两个共条的结点是相邻结点。在网络术语中，两个相邻结点连接到同一条链路，或者连接到同一广播型物理网络。第二，它定期地将链路状态给所有其它的结点(或称路由选择结点)。为了测试一个直接相连的结点的状态，一个结点定期地交换简短报文，询问该邻居是否是活动的和可达的，如果该邻居回答了，在它们之间的链路就称为是活动的。相反，如果收不到回答，就说它们之间的链路是不工作的。35大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.3

链路状态路由选择为了通知所有其它的结点，每个结点定期地发出通告报文，该报文列出它所连接的每条链路的状态。这种状态报文并不描述路径，它只是报告它与哪些结点可以通过直接相连的链路通信。结点中的协议负责将每一链路状态报文投递给全网上所有参与SPF算法的路由结点。如果基础网络不支持广播，那么投递就通过点到点地转发一个个报文拷贝而得以实现。简言之，在一个链路状态路由选择协议中，一个结点检查所有直接链路的状态，并将所得的状态给网上所有其它的结点，而不是仅仅送给那些直接相连的结点。以这种方式，每个结点从网上所有其它的结点接收包含直接链路状态的路由选择信息。36大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.3

链路状态路由选择每当链路状态报文到达时，路由结点便使用这些状态信息去更新自己的网络拓扑和状态“视野图”，把各个链路标为“up”或“down”。一旦链路状态发生了变化，结点对更新了的网络图利用Dijkstra最短通路搜索算法重新计算路由。Dijkstra算法是从单一的报源出发计算到达所有目的结点的最短路径。在链路状态路由选择算法中，每个结点都知道所有的结点分布在哪里，以及哪些链路将它们互连。每个结点都拥有关于整个网络的同样的视图。而且，路由更

文相当短，因为它们仅包含直接链路的状态。37大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.3

链路状态路由选择SPF算法的一个主要优点是，每个路由选择结点都使用同样的原始状态数据独立地计算路径；它们不依赖中间机器的计算。当一个结点从所有其它结点接收到了报文时，它可以在本地立即计算正确的通路，保证一步会聚。最后，由于链路状态报文仅运载来自单个结点关于直接链路的信息，其大小与网络中的路由结点数目无关；因此，SPF算距离向量算法有更好的规模可伸展性。距离向量算法和链路状态算法的主要区别在于，前者传送的路由报文包含与整个网络拓扑相关的信息，然而它是不可靠的，因为它包含有一个结点从其它系统获悉的信息。链路状态协议的路由选择报文仅包含一个结点直接链路的状态，然而这个消息是可靠的，因为发送者本身可以验证它。38大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.3

链路状态路由选择链路状态和距离向量算法之间的差别可以用这样的比喻来说明：距离向量向你的邻居通告整个世界的情况，而链路状态向整个世界通告你的邻居的情况。链路状态机制解决了距离向量算法产生的许多收剑问题，适用可伸缩的环境。然而，它们是非常强化计算的，需要消耗机器比较多的CPU

指令。在链路状态路由选择协议的操作过程中，每个路由器必须：发现它的邻居结点，并知道其网络地址。测量到它各邻居结点的延迟或代价。组装一个分组通告它刚获悉的所有信息。把这个分组发送给所有其它路由器。计算到其它每个路由器的最短路径。39大学授课教师：鲁士文2014.10.175.3路由选择算法5.3.3

链路状态路由选择链路状态分组以发送方的标识符开始，紧跟着是顺序号、存活时间和一个关于邻居的列表。对于每一个邻居，都给出到达那个邻居的延迟。图5-8(a)给出了一个示例子网，其延时已标，图5-8(b)示出了所有六个路由器的对应的链路状态分组。创建链路状态分组很容易，难的是决定何时创建分组。一种可能性是定期创建，即每隔一定时间就创建一次。另一种可能