路由器并行交换体系结构的研究

王海涛 田畅 郑少仁
    摘要：介绍高速路由器IP报文的处理流程和各处理单元的处理要求；对各处理单元采用的体系结构进行了详细分析和讨论；最后给出高速路由器报文输入、输出的并行处理实现方案。

    关键词：服务质量 虚拟输出队列 组合输入输出交换 异步转移模式 交换矩阵

    一、引言

    由于Internet采用TCP流控机制，数据传输的失序将对网络性能产生较大影响。尽管采用散列函数等方法可以保证TCP报文流按顺序传送，但只能从统计意义上保证并行交换系统的性能，并且对网络流量的分布依赖较大。因此，较好的方法是采用固定长度信元的并行处理机制，不仅系统控制易于实现，而且系统性能有绝对保证，不依赖于网络流量分布。然而，高速路由器处理的是不定长的IP分组，要在基于定长信元并行交换系统上实现IP报文的高速交换，首先要以线路速率将IP分组分成定长的信元流；同时，每个信元都必须带有相应的控制信息，以保证信元流的正确交换与目的端口 IP报文的重组。本文按照高速路由器的IP分组处理流程，较详细地分析了各处理模块的功能与性能要求，提出了一种IP分组并行处理与信元并行处理相结合的高速路由器体系结构。

    二、路由器的报文处理

    路由器要完成IP分组的交换，其处理过程通常应包括分组报头处理、路由查表、流量控制、缓存、队列调度、交换、输出缓存等过程。

    1．输入报文处理

    路由器输入报文处理过程主要包括分组报头处理、路由查表、流量控制、缓存、队列调度等。报头处理单元主要完成IP报文报头字段的处理，包括报头校验、TTL字段处理、错误检查、报头选项识别、报文分类等。不能直接转发的IP包被放入一个单独的队列，由系统处理机做相应的处理；对于需要转发的IP报文，根据系统配置，提取TOS域，映射成报文化先级。同时，生成路由查找模块需要的数据结构，交路由查找模块进行路由查找。路由查找单元根据系统维护的转发表，按报文中目的IP地址查找相应的输出端口。由于IP报文的队列管理与流量控制依赖于报文的流向与QOS要求的相关信息，因此要求路由器必须以线速率完成查表处理，保证报文在查表前不排队。按目前技术水平，采用大规模ASIC实现的查表引擎可达到40MPPS的平均处理能力（目前采用的查表技术可达到20MPPS的处理能力）。从平均意义上讲，采用这些硬件查表技术可以保证40GbPs和20Gbps的线速接口的处理要求。需要说明的是，上述转发引擎性能的测试都是在不考虑转发表更新的条件下进行的，而转发表的更新将占用较大的内存访问带宽，从而影响实际报文转发速率。这些查表技术不仅转发表占用内存较大，而且由于其数据结构组织复杂，转发表更新效率不高。据有关文献报道，由于因特网路由的不稳定性，干线路由器路由表更新的峰值速率可达每秒数百次。因此，如何在保证查表速率的前提下，提高转发表的更新速率是有待进一步研究的问题。

    队列管理与拥塞控制单元根据缓冲区状态及有关队列状态信息，根据IP报文分类和路由查找结果将报文送往队列缓冲区。在出现拥塞的情况下，流量控制单元将根据拥塞控制策略实施拥塞控制。为了实现基于区分服务体系结构IP QOS保证，报文丢弃将根据不同的业务类型和流向分别实施控制。通常，缓冲区的管理都采用定长数据块为单位申请和释放缓冲区，这样不仅管理方便、易于硬件实现，可以避免出现大量缓冲区“碎块”，而且便于实现以定长数据块为传送单位的交换网络的接口，实现IP报文的公平传送。由于IP报文为不定长的报文，因此在报文进入缓冲区之前必须分成固定长度的信元。为了保证各个信元可以独立地被调度和交换，并且在输出缓冲区重新组装成完整的IP报文，各个信元都必须带有相应的目的端口和控制信息。

    队列调度单元根据交换网络控制器的仲裁结构和调度策略，将相应队列中的信元通过交换网络送往目的端口。交换网络用于完成报文从源端口向目的端口的交换传送。用于高速路由器的交换网络通常采用模共享缓存交换或交换矩阵（Crossbar）两种方式。交换矩阵方式又以其良好的可扩展性而在目前高速路由器产品中得到越来越多的应用。

    2．输出报文处理

    输出端主要完成报文的重组、缓冲及输出链路接口控制。

    首先通过交换网络接口从交换网络得到定长的信元，将其重新组装成完整的IP报文。由于交换网络控制器以信元为传输单位控制各个源端口的数据传输，输出端将同时接收各个源端口的信元流。因此在逻辑上必须为每个源端口设置独立缓冲区，分别缓存各个IP报文的信元，完成整个IP报文的接收并将完整的IP分组送交输出缓冲区等待发送。

    对于采用输入缓冲（虚拟输出队列VOQ）的交换体系结构，交换网路的传送速率等于链路速率。这样，输出缓冲区可采用简单的FIFO管理机制，缓冲区大小为最大报文长度的N倍即可（N为路由器端口个数）。但是，输入缓冲交换无法保证输出链路的尽职工作，采用VOQ机制只能保证在输入流量为均匀分布的条件下达到100％的吞吐量。研究表明，因特网流量分布具有很强的不均匀性。因此，输入缓冲交换的加速问题成为交换技术研究的一个热点，其目的是使输入缓冲交换严格模仿输出缓冲交换。为此，交换网络的速率必须是链路速率的两倍。然而，交换网络的加速将导致交换网络输出速率大于输出链路速率，输出报文在输出缓冲区必须重新排队，甚至导致输出缓冲区的溢出。这样，必须在输出端另外再设置缓冲区管理、队列调度与拥塞控制机制。并且，系统拥塞控制策略的实现不仅与输入端的拥塞控制机制有关，而且与输出端的拥塞控制机制有关。无论是输入缓冲交换，还是输出缓冲交换，队列管理与拥塞控制都只需在交换网络的一侧实现，而加速后的输入缓冲交换，报文需要在输入和输出端分别缓存。有些文献称之为组合输入输出交换（CIOQ）。对于这种组合输入输出交换体系结构的队列调度与拥塞控制，目前尚未有理想的解决方案。

    一种简单的解决方案是借鉴ATM交换机中常用的反压机制。在输出端设置较小的缓冲区；采用简单的FIFO调度策略；当输出端缓冲区出现溢出时通过反压机制控制交换网络暂缓数据传输。对于这种方案的性能还有待于做进一步分析。

    由于输出端报文处理较简单，在目前技术水平下，对于2.5G的接口速率，完全可以采用单个处理模块实现。但是，对于10G以上的接口，由于内存访问速度及总线带宽的限制，必须采用多模块并行处理体系结构。

    三、报文并行处理与交换

    1．分组并行处理与信元并行处理

    基于信元的并行处理体系结构，不仅可以保证信元的按序传输，而且可以保证输出链路的尽职工作（100％吞吐量）。为此，必须将输入的IP报文拆成定长的信元，通过调度机制将信元送往各个不同的转发处理模块。

    为了将输入的IP分组拆成信元流，并保证在目的端口正确地组装成完整的IP分组，各个信元必须带有其所属IP分组的有关信息。为此，在拆分IP分组之前必须完成IP分组的报头处理及IP地址查表。这部分处理必须实时完成，以保证不会出现报文积压。如果单个处理模块无法以线路速率完成报文的处理，应以分组为调度单位实现多模块并行处理。首先这部分处理功能是为分组转发提供控制信息，在处理前系统缺少分组的相关信息，如业务类型、目的端口、校验是否正确等，无法得到各信元所需的控制信息；其次，这部分处理虽然是不定长的IP分组，但只是处理IP分组的报头，处理时间基本固定，与分组的长度无关，丢弃校验出错的分组也只需简单的硬件操作即可实现；再者，由于无需报文缓冲，硬件实现较简单，易于实现多处理模块的并行处理；最后，由于流量控制必须以分组为单位实施分组丢弃，在流量控制之前将分组拆成定长的信元将加大流量控制的实现难度。

    流量控制模块在出现拥塞时根据设定的分组丢弃策略丢弃部分分组，从而保证缓冲区不会出现溢出。如果在流量控制之前将分组拆成定长的信元，分组的丢弃必须保证将同一个IP分组的所有信元同时丢弃。因此，如果需要做并行处理，必须保证同一个IP分组的所有信元分配到同一个处理模块。同时，流量控制也只需要IP报文的报头信息和报文缓冲区状态，其处理时间基本为一定值，与IP报文的长度无关。所以，在流量控制之后实施IP分组的拆包更合适。

    综上所述，在流量控制以前的操作不需要大容量存储器，处理时间基本为定值，与IP报文长度无关，只需专用器件（ASIC或FGA）完成相应的处理即可。因此，对于需要并行处理的高速路由器，IP报文的报头处理、查表转发、流量控制应该采用以IP报文为基本处理单位的多模块并行处理结构。根据目前技术、工艺水平及国外高速路由器产品开发实践，单个处理模块难以胜任2.5G以上接口的 IP报文处理要求。尽管基于IP报文为基本处理单位的多模块并行处理结构的效率低于基于定长信元的多模块并行处理结构，对于未来高速路由器，它仍将是IP报文处理流程中必不可少的组成部分。

    报文缓冲区是用于缓存IP报文的海量存储器。对于一个10Gbps的接口，若数据线采用256比特宽度，则至少每12.8ns就要完成一次读或写操作。实现如此高速的海量存储器目前尚有一定困难，对于10G以上的接口，无法采用单模块实现。按目前的技术水平，只能采用多处理模块并行处理体系结构。从存储器管理机制的实现和存储器利用率方面考虑，目前缓冲区管理通常采用分区管理机制，将内存划分成定长的分区，根据请求的缓冲区长度分配一定数量的分区。这样，若要缓存一个IP报文，需要将不定长的报文按存储器分区大小分成多个定长的数据段。因此，可以首先将IP分组分成定长的信元，而将分区大小设置成信元长度，以信元为单位实施缓冲区管理。

    在输出端，同样由于存储器芯片访问速度的限制，对于10G以上的端口，必须采用并行处理结构。同时，链路输出必须以IP报文为基本传输单位，在多模块并行处理体系结构中必须以IP分组作为基本传输单元分配处理模块。然而同一个IP分组的各个信元是通过不同的交换单元传输的，交换网络与缓冲区的接口必须识别同一个IP分组的信元流送往相同的处理模块。

    综上所述，若要在高速路由器输入端实现IP报文的并行处理，在缓冲区管理之前应采用基于IP分组的并行处理结构；而缓冲区管理和交换网络应采用基于信元的并行处理结构；输出端则应采用基于IP分组的多模块并行处理结构。

    2．输入端报文并行处理

    根据上节的分析，输入端报文在报文缓冲之前采用基于IP分组的并行处理结构。我们将IP报头处理、查表、拥塞控制三项处理称为转发控制。这样，输入端处理包括线路接口、转发控制及报文缓冲。对于需要并行处理的高速路由器，转发控制部分采用基于IP分组的并行处理结构，而报文缓冲采用基于信元的并行处理结构。

    分组解复用器的作用是将从线路接口接收到的IP分组分配到各个处理模块。为了保证协议类型为TCP的IP分组的按序传送，对于属于TCP业务的IP分组按散列法分配转发控制单元，而其它类型的IP分组则按最短队列分配转发控制单元。

    其中，hp表示IP分组的报头信息；S表示缓冲区队列大小；HASH（hp）表示根据IP分组的报头信息做散列；而F（s）表示根据当前缓冲区队列大小S做调度（如选择具有最短队列的处理单元）。由于转发控制部件的输出是无阻塞、定速率的，根据输入流量的大小即可确定缓冲区中队列的大小。控制转发单元的输出经过分段处理，将报文分成定长的信元流。分配器用于实施信元调度，将信元送往不同的缓冲处理单元，经缓存送往交换网络。

    3．输出端报文并行处理

    在输出端，首先要将从交换网络接收的信元重组成完整的IP报文，以IP报文为基本单位送往发送缓冲区。通过输出队列调度，将发送缓冲区的IP报文送高速缓存（CACHE），高速缓存以线路速率向输出链路输出完整的IP报文。

    高速缓存的作用是为高速输出链路与低速报文缓冲区提供接口。由于缓冲区无法提供与高速链路相适应的访问速度，所以采用高速缓存：它接收发送缓冲区的报文，然后将完整的IP报文以线速率通过输出复用器向输出链路发送。输出复用器以完整的IP报文为基本传输单位，每次以一定的调度策略选择一个高速缓存输出报文。

    四、结论

    本文通过分析高速路由器IP报文的处理流程和各处理单元的处理要求，对基于分组的并行处理结构和基于信元的体系结构做了详细分析和讨论。我们认为信元转发控制和输出缓冲应采用以基于IP分组的并行处理，而输入端报文缓冲和交换网路应采用基于定长信元的并行处理结构。本文给出的高速路由器报文输入、输出的并行处理方案具有一定的实用价值和理论意义。

摘自《数据通信》2001.9