前一节学习了运输层依赖于网络层的主机到主机的通信服务，提供各种形式的进程到进程的通信。了解这种主机到主机通信服务的真实情况，是什么使得它工作起来的。
在本章和下一章，将学习网络层实际是怎样实现主机到主机的通信服务。与运输层和应用层不同的是，在网络中的每一台主机和路由器中都有一个网络层部分。
网络层在协议栈中是最复杂的层次。网络层可以被分为解为两个相互作用的部分，即数据平面和控制平面。第四章将学习网络层的数据平面功能，即网络层中每台路由器的功能，该数据平面功能决定到达路由器输入链路之一的数据报（网络层的分组）如何转发到该路由器输出链路之一。 将涉及传统的 IP 转发（转发基于数据报的目的地址）和通用的转发（可以使用数据报首部中的几个不同域的值执行转发和其他功能）。详细学习 IPv4 和 IPv6 协议及其寻址。第五章中，涉及网络层的控制平面功能，即网络范围的逻辑，控制数据报沿着从源主机到目的主机的端到端路径中路由器之间的路由方式。将学习路由选择算法，以及 OSPF 和 BGP 等路由选择协议。传统上，这些控制平面由路由选择协议和数据平面转发功能已经实现一个整体，位于一台路由器中。软件定义网络（SDN）通过将这些控制平面功能作为一项单独服务，明确地分离数据平面和控制平面，控制平面功能通常制与一台远程“ 控制器 ” 中。
4.1 网络层概述
图4-1 显示了一个简单网络，其中有 H1 和 H2 两台主机，在 H1 与 H2 之间的路径上有几台路由器。假设 Hl 正在向 H2 发送信息，考虑这些主机与中间路由器的网络层所起的作用。H1 中的网络层取得来自于 H1 运输层的报文段，将每个报文段封装成一个数据报，然后向相邻路由器 R1 发送该数据报。在接收方主机 H2，网络层接收来自相邻路由器R2 的数据报，提取出运输层报文段，并将其向上交付给 H2 的运输层。每台路由器的数据平面的主要作用是从其输入链路向其输出链路转发数据报；控制平面的主要作用是协调这些本地的每路由器转发动作，使得数据报沿着源和目的地主机之间的路由器路径最终进行端到端传送。注意到图 4-1 中所示路由器具有截断的协议栈、即没有网络层以上的部分，因为路由器不运行在应用层和运输层协议。
4.1.1 转发和路由选择：数据平面和控制平面
网络层的作用从表面上看极为简单，即将分组从一台发送主机移动到一台接收主机。需要使用两种重要的网络层功能：
转发。当一个分组到达某路由器的一条输入链路时，该路由器必须将该分组移动到适当的输出链路。例如，在图4-1 中来自主机 H1 到路由器 R1 的一个分组，必须向到达 H2 的路径上的下一台路由器转发。如将看到的那样，转发是在数据平面中实现的唯一功能（尽管是最为常见和重要的功能）。在最为常见的场合(我们将在 4.4 节中讨论) ，分组也可能被现有的路由器阻挡（例如，该分组来源于一个已知的恶意主机，或者该分组发向一个被禁止的目的主机） ，或者可能是冗余的并经过多条出链路发送。
路由选择。当分组从发送方流向接收方时，网络层必须决定这些分组所采用的路由或路径。计算这些路径的算法被称为路由选择算法 (routing algorithnl)。例如，在图 4-1 中一个路由选择算法将决定分组从 H1 到 H2 流动所遵循的路径。路由选择在网络层的控制平面中实现。
转发（forwarding）是指将分组从一个输入链路接口转移到只当的输出链路接口的路由器本地动作。转发发生的时间尺度很短（通常为几纳秒），因此通常用硬件来实现。路由选择（routing）是指确定分组从源到目的地所采取的端到端路径的网络范围处理过程。路由选择发生的时间尺度长的多（通常为几秒），常通过软件实现。
每台网络路由器中有一个关键元素是它的转发表 (fonvarding table)。路由器检查到达分组首部的一个或多个字段值，进而使用这些首部值在其转发表中索引，通过这种方法来转发分组。这些值对应存储在转发表项中的值，指出了该分组将被转发的路由器的输出链路接口。例如在图 4-2 中， 一个首部字段值为 0111 的分组到达路由器。该路由器在它的转发表中索引，并确定该分组的输出链路接口是接口 2。该路由器则在内部将该分组转发到接口 2。在 4.2 节中，深入路由器内部，更为详细地研究这种转发功能转发是由网络层的数据平面执行的主要功能。
1.控制平面：传统方法
路由器的转发表一开始是如何配置的。它揭示了路由选择和转发间的重要相互作用关系。如图 4-2 所示，路由选择算法决定了插入该路由器转发表的内容。在这个例子中，路由选择算法运行在每台路由器中，并且在每台路由器中都包含转发和路由选择两种功能。将在 5.3 节和 5.4 节中所见，在一台路由器中的路由选择算法与在其他路由器中的路由选择算法通信，以计算出它的转发表的值。这种通信是如何执行的呢？通过根据路由选择协议交换包含路由选择信息的路由选择报文。
通过考虑网络中的假想情况（不真实的，但技术上是可行的） ，也就是说路由器中物理上存在的所有转发表的内容是由人类网络操作员直接配置的，进一步说明转发和路由选择功能的区别和不同目的。在这种情况下，不需要任何路由选择协议！当然，这些人类操作员将需要彼此交互，以确保该转发表的配置能使分组到达它们想要到达的目的地。出现下列现象也很可能：人工配置更容易出错，并且对于网络拓扑变化的响应比起路由选择协议来更慢。
2.控制平面：SDN 方法
图4-2 中显示的实现路由选择功能的方法，是路由选择厂商在其产品中采用的传统方法。使用该方法，每台路由器都有一个与其他路由器的路由选择组件通信的路由选择组件。然而，对人类能够手动配置转发表的观察启发我们， 对于控制平面功能来说，也许存在其他方式来确定数据平面转发表的内容。
图4-3 显示了从路由器物理上分离的另一种方法，远程控制器计算和分发转发表以供每台路由器所使用。注意到图 4-2 和图 4-3 的数据平面组件是相同的。而在图 4-3 中，控制平面路由选择功能与物理的路由器是分离的，即路由选择设备仅执行转发，而远程控制器计算并分发转发表。程控制器可能实现在具有高可靠性和冗余的远程数据中心中，并可能由 ISP 或某些第三方管理。路由器和远程控制器是如何通信的呢？通过交换包含转发表和其他路由选择信息的报文。显示在图 4-3 中的控制平面方法是软件定义网络( Software-Defined N etworking , SDN) 的本质，因为计算转发表并与路由器交互的控制器是用软件实现的，故网络是"软件定义"的。将在 5.5 节中讨论 SDN 控制平面。
4.1.2 网络服务模型
当位于发送主机的运输层向网络传输分组时（在发送主机中将分组向下交给网络层），运输层能够指望网络层将该分组交付给目的地吗？ 当发送多个分组时，它们会按发送顺序按序交付给接收主机的运输层吗？发送两个连续分组的时间间隔与接收到这两个分组的时间间隔相同吗？网络层会提供关于网络中拥塞的反馈信息吗？在发送主机与接收主机中连接运输层通道的抽象视图(特性)是什么?对这些问题和其他问题的答案由网络层提供的服务模型所决定。网络服务模型 (networ servíce model) 定义了分组在发送与接收端系统之间的端到端运输特性。
考虑网络层能提供的某些可能的服务。这些服务包括：
确保交付。该服务确保分组将最终到达目的地。
具有时延上界的确保交付。该服务不仅确保分组的交付，而且在特定的主机到主机时延上界内（例如在 100ms 内）交付。
有序分组交付。该服务确保分组以他们发送的顺序到达目的地。
确保最小带宽。这种网络层服务模仿在发送和接受主机之间一条特定比特率（例如 1Mbps）的传输链路行为。只要发送主机以低于特定比特率的速率传输比特（作为分组的组成成分），则所有分组最终会交付到目的主机。
安全性。网络层能够在源加密所有数据报并在目的地解密这些分组，从而对所有运输层报文段提供机密性。
因特网的网络层提供了单一的服务，称为尽力而为服务( best-effort service)。使用尽力而为服务，传送的分组既不能保证以它们发送的顺序被接收，也不能保证它们最终交付；既不能保证端到端时延，也不能保证有最小的带宽。尽力而为服务是根本无服务的一种委婉说法，即一个没有向目的地交付分组的网络也符合尽力而为交付服务的定义。其他的网络体系结构已定义和实现了超过因特网尽力而为服务的服务模型。例如，ATM 网络体系结构提供了确保按序时延、有界时延和确保最小带宽。还有提议的对因特网体系结构的服务模型扩展 ，例如，集成服务体系结构的目标是提供端到端时延保证以及无拥塞通信。令人感兴趣的是，尽管有这些研发良好的供选方案，但因特网的基本尽力而为服务模型与适当带宽供给相结合已被证明超过"足够好"，能够用于大量的应用，包括诸如 Netfix、IP 语音和视频等流式视频服务，以及诸如 Skype Facetime 等实时会议应用。
第 4 章概述
4.2 节中，将深入探讨路由器的内部硬件操作，包括输入和输出分组处理、路由器的内部交换机制以及分组排队和调度。4.3 节中，学习传统的 IP 转发，其中分组基于它们的目的 IP 地址转发到输出端口。 IP 寻址、IPv4 和 IPv6协议等。 4.4 节中，将涉及更为一般的转发，此时分组可以基于大量首部值（即不仅基于目的 IP 地址）转发到输出端口。分组可能在路由器中受阻或冗余，或者可能让某些首部字段重写，即所有都在软件控制之下完成。这种分组转发的更为一般的形式是现代网络数据平面的关键组件， 包括软件定义网络 (SDN) 中的数据平面。
约定术语分组交换机是指一台通用分组交换设备，它根据分组首部字段中的值，从输入链路接口到输出链路接口转移分组。某些分组交换机称为链路层交换机，基于链路层帧中的字段值做出转发决定，这些交换机因此称为链路层设备。其他分组交换机叫做路由器，基于网络层数据报中的首部字段值做出转发决定。路由器因此是网络层设备。这里关注网络层，主要使用术语路由器来替代交换机。
4.2 路由器工作原理
网络层的转发功能，即实际将分组从一台路由器的入链路传送到适当的出链路。
图4-4 显示了一个通用路由器体系结构的总体视图，其中标识了一台路由器的 4 个组件。
输入端口。输入端口 (input port）的执行几项重要功能。它在路由器中执行终结入物理链路的物理层功能，这显示了 4-4 中输入端口部分最左侧的方框与输出端口部分最右侧的方框中 。它还要与位于入链路远端的数据链路层交互来执行数据链路层功能，这显示在输入与输出端口部分中间的方框中。也许更为重要的是，在输入端口还要执行查找功能，这显示在输入端口最右侧的方框正是在这里，通过查询转发表决定路由器的输出端口，到达的分组通过路由器的交换结构转发到输出端口。控制分组（如携带路由选择协议信息的分组）从输入端口转发到路由选择处理器。注意这里的"端口"一词，指的是路由器的物理输入和输出接口。在实践中，一台路由器所支持的端口数量范围较大，从企业路由器具有数量相对少的端口，到位于某 ISP 边缘的路由器具有数以百计 10Gbps 端口（其中入线路的数量趋于最大）。
交换结构。交换结构将路由器的输入端口连接到输出端口。这种交换结构完全包含在路由器中，即它是一个网络路由器中的网络。
输出端口。输出端口存储从交换结构接受的分组，并通过执行必要的链路层和物理层功能在输出链路上传输这些分组。当一条链路是双向时（即承载两个方向的流量），输出端口通常与该链路的输入端口成对出现在同一线路卡上。
路由选择处理器。路由选择处理器执行控制平面功能。在传统的路由器中，它执行路由选择协议，维护路由选择表与关联链路状态信息，并为该路由器计算转发表。在 SDN 路由器中，路由选择处理器(在其他活动中)负责与远程控制器通信，目的是接收由远程控制器计算的转发表项，并在该路由器的输入端口安装这些表项。路由选择处理器还执行网络管理功能。
路由器的输入端口、输出端口和交换结构几乎总是用硬件实现，如图 4-4 所示。为了理解为何需要用硬件实现，考虑具有 10Gbps 输入链路和 64 字节的 IP 数据报 ，其输入端口在另一个数据报到达前仅有 51.2ns 来处理数据报。如果 N 个端口结合在一块线路卡上（因为实践中常常这样做) ，数据报处理流水线必须以 N 倍速率运行，这远快过软件实现的速率。转发硬件既能够使用路由器厂商自己的硬件设计来实现，也能够使用购买的商用硅片的硬件设计来实现。
当数据平面以纳秒时间尺度运行时，路由器的控制功能以毫秒或秒时间尺度运行，这些控制功能包括执行路由选择协议、对上线或下线的连接链路进行响应、与远程控制器通信（在SDN场合）和执行管理功能。因而这些控制平面的功能常用软件实现并在路由选择处理器（一种传统的CPU）上执行。
在深入探讨路由器的内部细节之前，转向本章开头的那个类比，其中分组转发好比汽车进入和离开立交桥，假定该立交桥是环状交叉路，在汽车进入该环状交叉路前需要做一点处理。考虑一下对于这种处理需要什么信息。
基于目的地转发。假设汽车停在一个入口站上并指示它的最终目的地（并非在本地环状交叉路，而是其旅途的最终目的地）入口站的一名服务人员查找最终目的地.决定通向最后目的地的环状交叉路的出口，并告诉驾驶员要走哪个出口。
通用转发。除了目的地之外，服务人员也能够基于许多其他因素确定汽车的出口匝道。例如，所选择的出口匝道可能与该汽车的起点如发行该车牌照的州有关。来自某些州的汽车可能被引导使用某个出口应道(经过一条慢速道路通向目的地) ，而来自其他州的汽车可能被引导使用一个不同的出口匝道(经过一条高速路通向目的地) 基于汽车的模型、品牌和寿命，可能做出相同的决定。或者认为不适合上路的汽车可能被阻止并且不允许通过环状交叉路。就通用转发来说，许多因素都会对服务人员为给定汽车选择出口匝道产生影响。
4.2.1 输入端口处理和基于目的地转发
图 4-5 中显示了一个更详细的输入处理的视图。如前面讨论的那样，输入端口的线路端接功能与链路层处理实现了用于各个输入链路的物理层和链路层。在输入端口中执行的查找对于路由器运行是至关重要的。正是在这个地方，路由器使用转发表来查找输出端口，使得到达的分组能经过交换结构转发到该输出端口。转发表是由路由选择处理器计算和更新的（使用路由选择协议与其他网络路由器中的路由选择处理器进行交互），或者转发表接收来自远程 SDN 控制器的内容。转发表从路由选择处理器经过独立总线（例如一个 PCI 总线）复制到线路卡， 在图 4-4 中该总线由从路由选择处理器到输入线路卡的虚线所指示。使用在每个输入端口的影子副本， 转发决策能在每个输入端口本地做出，无须基于每个分组调用集中式路由选择处理器，因此避免了集中式处理的瓶颈。
来考虑 “ 最简单 ” 的情况，一个入分组基于该分组的目的地址交换到输出端口。在 32 比特 IP 地址的情况下，转发表的蛮力实现将针对每个目的地址有一个表项。因为有超过 40 亿个可能的地址，选择这种方法总体上是不可行的。
使用这种风格的转发表，路由器用分组目的地址的前缀( prefix ) 与该表中的表项进行匹配；如果存在一个匹配项，则路由器向与该匹配项相关联的链路转发分组。例如，假设分组的目的地址是 11001000 00010111 00010110 10100001 因为该地址的 21 比特前缀匹配该表的第一项， 所以路由器向链路接口 0 转发该分组。如果一个前缀不匹配前 3 项中的任何一项，则路由器向链路接口3 转发该分组。尽管听起来足够简单，但这里还是有重要的微妙之处。你可能已经注意到一个目的地址可能与不止一个表项相匹配。例如，地址1100100000010111 00011000 10101010 的前 24 比特与表中的第二项匹配， 而该地址的前21 比特与表中的第三项匹配。当有多个匹配时，该路由器使用最长前缀匹配规则( longesl prefIx malching rule) ；即在该表中寻找最长的匹配项 ，并向与最长前缀匹配相关联的链路接口转发分组。当在 4.3 节中详细学习因特网编址时，我们将完全明白使用这种最长前匹配规则的理由。
假定转发表已经存在，从概念上讲表查找是简单的，硬件逻辑只是搜索转发表查找最长前缀匹配。但在几比特速率下，这种查找必须在纳秒级执行（回想前面 10Gbps路和一个 64 字节 IP 数据报的例子）。因此，不仅必须要用硬件执行查找，而且需要对大型转发表使用超出简单线性搜索的技术。同时必须对内存访问时间给予特别关注，这导致用嵌入式片上 DRAM 和更快的 SRAM（用作一种 DRAM 缓存）内存来设计。实践中也经常使用三态内容可寻址存储器(TenruγContent Address Memory , TCAM) 来查找。使用 TCAM，一个 32 比特 IP 地址被放入内存， TCAM 在基本常数时间内返回对该地址的转发表项的内容。
一且通过查找确定了某分组的输出端口 ，则该分组就能够发送进入交换结构。在某些设计中，如果来自其他输入端口的分组当前正在使用该交换结构，一个分组可能会在进入交换结构时被暂时阻塞。因此，一个被阻塞的分组必须要在输入端口处排队，并等待稍后被及时调度以通过交换结构。稍后将仔细观察分组（位于输入端口与输出端口中）的阻塞、排队与调度。尽管" 查找 "在输入端口处理中可认为是最为重要的动作，但必须采取许多其他动作：① 必须出现物理层和链路层处理，如前面所讨论的那样；② 必须检查分组的版本号、检验和以及寿命字段，并且重写后两个字段；③ 必须更新用于网络管理的计数器(如接收到的 IP 数据报的数目)。
在结束输入端口处理的讨论之前，注意到输入端口查找目的 IP 地址 (" 匹配 " ) ，然后发送该分组进入交换结构( "动作）的步骤是一种更为一般的" 匹配加动作 " 抽象的特定情况，这种抽象在许多网络设备中执行，而不仅在路由器中。在链路层交换机中，除了发送帧进入交换结构去往输端口外，还要查找链路层目的地址，并采取几个动作。在防火墙中，首部匹配给定准则（例如源/目的 IP 地址和运输层端口号的某种组合）的入分组可能被阻止转发，而防火墙是一种过滤所选择的入分组的设备。在网络地址转换器（NAT ，在 4. 节讨论）中，一个运输层端口号匹配某给定值的入分组，在转发（动作）前其端口号将被重写。的确，"匹配加动作" 抽象不仅作用大， 而且在网络设备中无所不在，并且对于我们将在 4.4 节中学习的通用转发是至关重要的。
4.2.2 交换
交换结构位于一台路由器的核心部位，正是通过这种交换结构，分组才能实际地从一个输入端口交换（即转发）到一个输出端口。交换可以通过许多方式完成，如图 4-6 所示。
① 经内存交换
最简单、 最早的路由器是传统的计算机，在输入端口与输出端口之间的交换是在 CPU ( 路由选择处理器 ) 的直接控制下完成的。输入与输出端口的功能就像在传统操作系统中的 I/O 设备 。一个分组到达一个输入端口时，该端口会先通过中断方式向路由选择处理器发出信号。于是，该分组从输入端口处被复制到处理器内存中。路由选择处理器则从其首都中提取目的地址、在转发表中找出适当的输出端口，并将该分组复制到输出端口的缓存中。在这种情况下，如果内存带宽为每秒可写进内存或从内存读出最多 B 个分组，则总的转发吞吐量（分组从输入端口被传送到输出端口的总速率）必然小于 B/2。也要注意到不能同时转发两个分组，即使它们有不同的目的端口，因为经过共享系统总线一次仅能执行一个内存读/写。
许多现代路由器通过内存进行交换。然而，与早期路由器的一个主要差别是，目的地址的查找和将分组存储（交换）进适当的内存存储位置是由输入线路卡来处理的。在某些方面，经内存交换的路由器看起来很像共享内存的多处理器，用一个线路卡上的处理将分组交换（写）进适当的输出端口的内存中。
② 经总线交换
在这种方法中，输入端口经一根共享总线将分组直接传送到输出端口，不需要路由选择处理器的干预。通常按以下方式完成该任务：让输入端口为分组预先计划一个交换机内部标签(首部) ，指示本地输出端口，使分组在总线上传送和传输到输出端口。该分组能由所有输出端口收到，但只有与该标答匹配的端口才能保存该分组。然后标签在输出端口被去除，因为其仅用于交换机内部来跨越总线。如果多个分组同时到达路由器，每个位于不同的输出端口，除了一个分组外所有其他分组必须等待，因为一次只有一个分组能够跨越总线。因为每个分组必须跨过单一总线，故路由器的交换带宽受总线速率的限制；在环状交叉路的类比中，这相当于环状交叉路一次仅包含一辆汽车。尽管如此，对于运行在小型局域网和企业网中的路由器来说，通过总线交换通常足够用了。
③ 经互联网络交换
克服单一、共享式总线带宽限制的一种方法是，使用一个更复杂的互联网络，例如过去在多处理器计算机体系结构中用来互联多个处理器的网络。纵横式交换机就是一种由 2N 条总线组成的互联网络。它连接 N 个输入端口与 N 个输出端口，如图 4-6 所示，每条垂直的总线在交叉点与每条水平的总线交叉，交叉点通过交换结构控制器（其逻辑是交换结构自身的一部分）能够在任何时候开启和闭合。当某分组到达端口 A，需要转发到端口 Y 时，交换机控制器闭合总线 A 和 Y 交叉部位的交叉点，然后端口 A 在其总线上发送该分组，该分组仅由总线 Y 接收。注意到来自端口 B的一个分组在同一时间能够转发到端口 X，因为 A到Y 和 B到X 的分组使用不同的输入和输出总线。因此，与前面两种交换方法不同，纵横式网络能够并行转发多个分组。纵横式交换机是非阻塞的，即只要没有其他分组当前被转发到该输出端口，转发到输出端口的分组将不会被到达输出端口的分组阻塞。然而，如果来自两个不同输入端口的两个分组其目的地为相同的输出端口，则一个分组必须在输入端等待，因为在某个时刻经给定总线仅能够发送一个分组。
更为复杂的互联网络使用多级交换元素，以使来自不同输入端口的分组通过交换结构同时朝着相同的输出端口前行。Cisco CRS 利用一种三级非阻塞交换策略，路由器的交换能力也能够通过并行运行多种交换结构进行扩展。在这种方法中，输入端口和输出端口被连接到并行运行的 N 个交换结构。一个输入端口将一个分组分成 K 个较小的块，并且通过 N 个交换结构中的 K个发送这些块到所选择的输出端口，输出端口再将 K 个块装配还原成初始的分组。
4.2.3 输出端口处理
如图4-7 所示，输出端口处理取出已经存放在输出端口内存中的分组并将其发送到输出链路上。这包括选择和取出排队的分组进行传输，执行所需的链路层和物理层传输功能。
4.2.4 何处出现排队
考虑显式在图 4-6 中的输入和输出端口功能及其配置，下列情况是一目了然的：在输入端口和输出端口处都可以形成分组队列，就像在环状交叉路的类比中讨论过的情况，即汽车可能等待在流量交叉点的入口和出口。排队的位置和程度（或在输入端口排队，或者输出端口排队）将取决于流量负载、交换结构的相对速率和线路速率。在更为详细一点考虑这些队列，因为随着队列的增长，路由器的缓存空间最终会耗尽，并且当无内存可用于存储到达的分组时将会出现丢包。分组“ 在网络中丢失 ” 或 “被路由器丢弃”。正是在一台路由器的这些队列中，这些分组被实际丢弃或丢失。
假定输入线路速度与输出线路速度（传输速率）是相同的，均为 Rline（单位为每秒分组数），并且有 N 个输入端口和 N个输出端口。为进一步简化讨论，假设所有分组具有相同的固定长度，分组以同步的方式到达输入端口。这就是说，在任何链路发送分组的时间等于在任何链路接收分组的时间，在这样的时间间隔内，在以一个输入链路上能够到达 0 或 1 个分组。定义交换结构传送速率 Rswitch 为从输入端口到输出端口能够移动分组的速率。如果 Rswitch 比 Rline 快 N 倍，则在输入端口处仅会出现微不足道的排队。这是因为即使在最坏情况下，所有 N 条输入线路都在接收分组，并且所有的分组将被转发到相同的输出端口，每批 N 个分组（每个输入端口一个分组）也能够在下一批到达前通过交换结构处理完毕。
1. 输入排队
如果交换结构不能快得（相对于输入线路速度而言）使所有到达分组无时延地通过它传送，会发生什么情况？这种情况下，在输入端口也将出现分组排队，因为到达的分组必须加入输入端口队列中，以等待通过交换结构传送到输出端口。举例说明这种排队的重要后果，考虑纵横式交换结构，并假定：① 所有链路速度相同 ② 一个分组能够以一条输入链路接受一个分组所用的相同的时间量，从任意一个输入端口传送到给定的输出端口。③ 分组按照 FCFS 方式，从一指定输入队列移动到其要求的输出队列中。只要其输出端口不同，多个分组可以被并行传送。然而，如果位于两个输入队列前端的两个分组是发往同一输出队列的，则其中的一个分组将被阻塞，且必须在输入队列中等待，因为交换结构一次只能传送一个分组到某指定端口。
图4-8 显示了一个例子 ，其中在输入队列前端的两个分组（带深色阴影）要发往同一个右上角输出端口。假定该交换结构决定发送左上角队列前端的分组。在这种情况下，左下角队列中的深色阴影分组必须等待。但不仅该分组要等待，左下角队列中排在该分组后面的浅色阴影分组也要等待。即使右中侧输出端口（浅色阴影分组的目的地）中无竞争。这种现象叫作输入排队交换机中
的线路前部（HOL）阻塞，即在一个输入队列中排队的分组必须等待通过交换结构发送（即使输出端口是空闲的），因为它被位于线路前部的另一个分组所阻塞。由于 HOL 阻塞，只要输入链路上的分组到达速率达到其容量的 58%，在某些假设前提下，输入队列长度就将无限制地增大。（不严格的讲，等同于说将出现大量的丢包）。
2.输出排队
我们接下来考虑在交换机的输出端口是否会出现排队。再次假定 Rswitçh 比 Rline 快 N 倍，并且到达 N 个输入端口的每个端口的分组，其目的地是相同的输出端口。在这种情况下，在向输出链路发送一个分组的时间内，将有 N 个新分组到达该输出端口 (N 个输入端口的每个都到达1 个）。因为输出端口在一个单位时间（该分组的传输时间）内仅能传输一个分组，这 N 个到达分组必须排队（等待）经输出链路传输。在正好传输 N 个分组(这些分组是前面正在排队的)之一的时间中，可能又到达 N 个分组， 等等。所以，分组队列能够在输出端口形成，即使交换结构比端口线路速率快 N 倍，最终，排队的分组数量能够变得足够大，耗尽输出端口的可用内存。
当没有足够的内存来缓存一个入分组时，就必须做出决定：要么丢弃到达的分组（采用一种称为弃尾( drop-tail) 的策略），要么删除一个或多个已排队的分组为新来的分组腾出空间。在某些情况下，在缓存填满之前便丢弃一个分组（或在其首部加上标记）的做法是有利的，这可以向发送方提供一个拥塞信号。已经提出和分析了许多分组丢弃与标记策略，这些策略统称为主动队列管理 (Active Queue Management , AQM) 算法。随机早期检测（RED）是得到最广泛研究和实现的 AQM 算法之一。
图 4-9 中图示了输出端口的排队情况。在时刻 t，每个入端输入端口都到达了一个分组，每个分组都是发往最上侧的输出端口。假定线路速度相同，交换机以 3 倍于线路速度的速度运行，一个时间单位（即接受或发送一个分组所需的时间）以后，所有三个初始分组都被传送到输出端口，并排队等待传输。在下一个时间单位中，这三个分组中的一个将通过输出链路发送出去。这个例子中，又有两个新分组已到达交换机的入端；这些分组之一要发往最上侧的输出端口。后果是，输出端口的分组调度在这些排队分组中选择一个分组来传输。
假定需要路由器缓存来吸收流量负载的波动，一个自然而然的问题是需要多少缓存。多年以来，用于缓存长度的经验方法是，缓存数量（B）应当等于平均往返时延（RTT）乘以链路的容量（C）。这个结果是基于相对少量的 TCP 流的排队动态性分析得到的。因此，一条具有 250ms RTT 的 10Gbps 链路需要的缓存量 等于 B=RTT*C=2.5Gb。然而，最近的理论表明，当有大量的 TCP 流（N条）流过一条链路时，缓存所需要的数量是 B=RTT*C/根号N。
4.2.5 分组调度
现在转而讨论确定次序的问题，即排队的分组如何经输出链路传输的问题。 有一种是先来先服务( FCFS ，也称之为先进先出(FIFO)。) 有些国家基于优先权运转，即给一类等待客户超越其他等待客户的优先权服务，也有循环排队，其中客户也被划分为类别(与在优先权队列一样) ，但每类用户 、依次序提供服务。
1. 先进先出
图 4-10 显示了对于先进先出( First-In-First-Out , FIFO) 链路调度规则的排队模型的抽象。如果链路当前正忙于传输另一个分组，到达链路输出队列的分组要排队等待传输。如果没有足够的缓存空间来容纳到达的分组，队列的分组丢弃策略则确定该分组是否将被丢弃(丢失)或者从队列中去除其他分组以便为到达的分组腾出空间，如前所述。在下面讨论中，忽视分组丢弃，当一个分组通过输出链路完全传输（接收服务）时，从队列中去除它。
FIFO（也称为先来先服务，FCFS）调度规则按照分组到达输出链路队列的相同次序来选择分组在链路上传输。我们都很熟悉服务中心的 FIFO 排队，在那里到达的顾客加入单一等待队列的最后，保持次序，然后当他们到达队伍的前面时就接受服务。
图 4-11 显示了运行中的 FIFO 队列。分组的到达由上部时间线上带编号的箭头来指示，用编号指示了分组到达的次序。各个分组的离开表示在下部时间线的下面。分组在服务中（被传输）花费的时间是通过这两个时间线之间的阴影矩形来指示的。假定在这个例子中传输每个分组用去 3 个单位时间。利用 FIFO 规则，分组按照到达的相同次序离开。注意在分组4 离开之后，在分组5 到达之前链路保持空闲（因为分组1~4 已经被传输并从队列中去除）.
2.优先权排队
在优先权排队( priority queuing ) 规则下，到达输出链路的分组被分类放入输出队列中的优先权类，如图 4-12 所示。在实践中，网络操作员可以配置一个队列，这样携带网络管理信息的分组（例如，由源或目的 TCP/UDP 端口号所标识）获得超过用户流量的优先权；此外，基于 IP 的实时话音分组可能获得超过非实时流量(如 SMTP 或 IMAP 电子邮件分组）的优先权。每个优先权类通常都有自己的队列。当选择一个分组传输时，优先权排队规则将从队列为非空（也就是有分组等待传输）的最高优先权类中传输一个分组。在同一优先权类的分组之间的选择通常以 FIFO 方式完成。
图4-13 描述了有两个优先权类的一个优先权队列的操作。分组1、3 和 4 属于高优先权类，分组 2和5 属于低优先权类。分组1 到达并发现链路是空闲的，就开始传输。在分组1 的传输过程中，分组2和分组3 到达，并分别在低优先权和高优先权队列中排队。在传输完分组1 后，分组3 (一个高优先权的分组)被选择在分组2 (尽管它到达得较早，但它是一个低优先权分组)之前传输。在分组3 的传输结束后，分组2开始传输。分组4 (一个高优先权分组)在分组2 (一个低优先权分组)的传输过程中到达。在非抢占式优先权排队( non-pree ltive priority queuing) 规则下，一旦分组开始传输，就不能打断。在这情况下，分组 4 排队等待传输，并在分组2 传输完成后开始传输。
3. 循环和加权公平排队
在循环排队规则 (round robin queuing discipline) 下，分组像使用优先权排队那样被分类。然而，在类之间不存在严格的服务优先权，循环调度器在这些类之间轮流提供服务。在最简单形式的循环调度中，类1 的分组被传输，接着是类2 的分组，接着又是类1的分组、再接着又是类2 的分组，等等。一个所谓的保持工作排队（work - conserving queuing) 规则在有(任何类的)分组排队等待传输时，不允许链路保持空闲。当寻找给定类的分组但是没有找到时，保持工作的循环规则将立即检查循环序列中的下一个类。
图4-14 描述了一个两类循环队列的操作。在这个例子中，分组1 2 和4 属于第一类，分组 3和5 属于第二类。分组1 一到达输出队列就立即开始传输。分组2 和3 在分组1的传输过程中到达，因此排队等待传输。在分组1 传输后，链路调度器查找类2 分组，因此传输分组3。在分组3 传输完成后，调度器在找类1 的分组，因此传输分组2 。在分组2传输完成后，分组4 是唯一排队的分组，因此在分组2 后立刻传输分组4。
一种通用形式的循环排队已经广泛地实现在路由器中 ，它就是所谓的加权公平排队( Weighted Fair Queuing , WFQ) 规则图 4-15 对 WFQ 进行了描述。其中，到达的分组被分类并在合适的每个类的等待区域排队。与使用循环调度一样， WFQ 调度器也以循环的方式为各个类提供服务，即首先服务第 1 类，然后服务第2 类，接着再服务第3 类，然后（假设有3个类别）重复这种服务模式。WFQ 也是一种保持工作排队规则，因此在发现一个空的类队列时，它立即移向服务序列中的下一个类。
WFQ 和循环排队的不同之处在于，每个类在任何时间间隔内可能收到不同数量的服务。具体而言，每个类i 被分配一个权wi。使用 WFQ 方式，在类i 有分组要发送的任何时间间隔中，第 i 类将确保接收到的服务部分等于wi/w总，式中分母中的和是计算所有有分组排队等待传输的类别得到的。在最坏的情况下，即使所有的类都有分组排队，第i类仍然保证分配到带宽的 wi/w总 部分。因此，对于一条传输速率为 R 的链路，第 i 类总能获得至少为 R*wi/w总 的吞吐量。我们对 WFQ 的描述理想化了，因为没有考虑这样的事实：分组是离散的数据单元，并且不能打断一个分组的传输来开始传输另一个分组。