一种高效自适应的CICQ交换机数据包切分机制

王晓婷，王忆文，李　平

（电子科技大学 电子薄膜与集成器件国家重点实验室，四川 成都 610054）

一种高效自适应的CICQ交换机数据包切分机制

王晓婷，王忆文，李平

（电子科技大学 电子薄膜与集成器件国家重点实验室，四川 成都 610054）

为了有效处理 CICQ （Combined Input Crosspoint Queued）交换机中的变长数据包，通常采用切分-重组（Segmentation and Reassembly，SAR）机制将变长包切分为定长信元进行交换。针对目前已有切分方法在不同网络流量下交换效率低、灵活性差的问题，设计了一种基于CICQ交换机的高效自适应数据包切分机制。新机制的主要思想是根据输入端的队列状态实时改变切片大小，并采用相邻数据包合并切分的方式进行切片，以自适应网络环境中的不同流量和数据包长度。仿真结果表明，提出的数据包切分机制较传统切分方法有显著优势，与已有方法中表现最好的变长多包切分相比，在不同的流量下能获得更优的时延性能和系统稳定性。

CICQ交换机；切分机制；自适应

0　引言

Crossbar交换结构由于具有简单及内部无阻塞的特性，成为现代交换机系统的核心组成部分[1]。传统的 crossbar内部无缓存，只在输入端或输出端设置缓存队列，各输入输出端口的数据传输应相互同步。因此，在处理变长包时需要使用切分-重组（SAR）机制，在输入端将数据包切割成定长信元进行交换，再在输出端将信元重组为原始的数据包。目前，一种内部带缓存的crossbar交换结构—CICQ（Combined Input Crosspoint Queued）通过在 crossbar内交叉点设置少量缓存来提高调度效率，已成为更具优势的交换结构[2]。CICQ的一个特点是能够直接交换变长数据包[3]，不需要SAR机制。然而，直接变长交换存在两方面限制：与定长交换相比，硬件实现相对复杂；交叉点缓存至少需要一个最大包长的空间来存放数据，限制交换机端口数的扩展。因此，对于CICQ中变长数据包的处理，仍然需要采用高效的数据包切分方法将其切分以便于交换。

目前已有的数据包切分方法包括：定长单包切分、定长多包切分[4]、变长单包切分[5]和变长多包切分(Variable-size Multipacket Segments，VMS)[6]。定长单包切分，对单个数据包进行处理，切分为定长信元。然而最后一个切片通常包含无用的填充字节，需要crossbar内部加速来补偿填充字节引起的带宽利用率损失。由于信元较小，需要较高的调度速率，对调度算法的要求也较高。定长多包切分属于同一数据流的数据包合并起来进行切分。切片长度增加，能够缓解调度速率，同时填充字节减少可以提高带宽利用率。缺点是队尾的部分数据需要保持在队列中直到能够填满一个切片，增加数据包的延迟。变长单包切分对单个数据包进行切分，最后一个切片不需要填充开销。但是，由于在单个数据包内进行切片，调度速率不会减小。变长多包切分对相邻的数据包合并起来进行切分，切片大小的增加缓解调度速率，而且不需要额外的填充字节，性能优于其他三种切分方法。然而，在对延迟性能要求较高的实时业务流量中，实时的小数据包会因为较大切片的阻挡而导致延迟增加，从而影响其交换效率及公平性。

针对传统切分方法的不足，本文在变长多包切分[7]的基础上进行改进，提出了一种新的基于CICQ交换机的高效自适应数据包切分机制(Adaptive Multipacket Segments，AMS)。该机制根据输入端的队列状态实时地调整切片长度，以适应动态变化的网络流量以及不同数据包长度。切片长度灵活可变，使得队列中的大型数据包和实时小数据包都能得到有效服务，不会影响实时小数据包的交换效率。CICQ结构采用新的数据包切分机制，在不同的网络流量模型下都表现有良好的时延性能，且明显优于变长多包切分机制。

图1　带切分-重组(SAR)机制的N×N CICQ交换结构

图2　基本数据包切分模型

1　CICQ交换结构和基本数据包切分模型

图1所示为带SAR机制的N×N CICQ交换结构，主要包括N个输入端、N个输出端、虚拟输出队列（VOQ）、带缓存的crossbar、输入切分机制以及输出重组机制。数据包到达输入端时，首先切分机制将变长数据包切割为定长信元，存入相应的VOQ队列中。然后，信元经过带缓存的crossbar进行交换。最后，在输出端通过重组机制将信元重组为原始的数据包并发送。为了分析切分机制，采用如图2所示的定长单包切分模型。假设数据包到达过程为服从参数为 λ的Poisson过程，令数据包的长度为X，以s为标准切片大小对数据包进行切分，则每个数据包切分为 ceil(X/s)个信元，其中 ceil为标准的上取整函数。若包长X不能被s整除，则剩下的数据添加填充字节构成标准信元。此外，每个信元还需要添加信元头，以指示该信元在数据包中的位置。令数据包切分成长度为s的信元个数为随机变量Y，则Y与X的关系为：

假设数据包长度X为服从参数为μ的指数分布，其累积分布函数F(x)为：

由式(4)可知，变量 Z服从参数 p为 e-μs，q为 1-e-μs的几何分布，P(Z=k)=qkp。Z的均值为：

切分过程中每个信元添加的无用填充字节会消耗系统带宽，为了保证CICQ结构能够以线速率交换经切分后的信元，crossbar内部需要一定的加速比f：

式中，E(X)为数据包长度X（服从指数分布）的均值为1/μ，h为每个信元头的大小。

将式(6)代入式(7)，可得

分析上式得出，平均包长 E(X)一定，切片长度 s为影响CICQ交换性能的主要因素。随着切片长度s的增加，CICQ所需的内部加速比f增大。这是因为填充字节在所有传输数据中所占的比例增加，交换填充字节引起的带宽利用率损失更严重，需要更大的加速比以线速转发数据。

图3　变长多包切分模型

2　自适应数据包切分

2.1变长多包切分模型

图3所示为变长多包切分模型，不同阴影部分代表输入VOQ队列中不同的数据包。相邻数据包合在一起进行切分，以s为标准切片大小。每个切片中可能包括一个或多个数据包，队列中最后剩余的数据若不能被s整除，则直接构成变长切片s′，无需用填充字节填满。对于这种方法，采用不同的切片长度s，系统的交换性能有显著差异。随着s的增大，信元头的整体开销减少，使得带宽利用率和时延性能都进一步提高。然而，若切片长度s太大，在实时性要求较高的网络业务流量中，小数据包会因大切片的阻挡而导致包延迟增加，其交换效率及公平性会大大降低。同时，切片过大会降低硬件电路的利用率。

2.2自适应数据包切分机制

在实际的网络流量中，进入交换机的数据包长度具有随机性，VMS机制采用固定切片长度灵活性较差，无法适应动态变化的流量。针对VMS机制灵活性差和交换效率低的问题，本节提出一种高效的自适应数据包切分机制（AMS）。其基本思想是根据输入VOQ队列的状态信息动态地调整切片长度，使其适应实时变化的流量和数据包长度，同时保证良好的交换性能。具体切分时将VOQ队列中相邻的数据包合并起来进行切片。完整的自适应数据包切分机制描述如下：

对于一个 N×N CICQ交换机，输入端有数据包到达时直接存放到对应VOQ队列中。假设LVij为输入 VOQij的队列长度，LCij为 crossbar交叉点缓存 CBij的队列长度，C表示交叉点缓存的最大容量，其中 1≤i≤N，1≤j≤N。有效 VOQij：VOQij满足一定的条件，即对应交叉点缓存CBij包括能够容纳一个切片大小的空间。每个输入端i，在每个调度周期按以下步骤执行：

(1)自适应切片长度Si生成。计算N个VOQ队列中所有数据包包长的平均值为 Si=(LVi1+LVi2+…+LViN)/N。

(2)确定 VOQij的实际切片长度 Sij。若 VOQij的队列长度 LVij大于 Si，则实际切片长度 Sij=Si；否则，Sij=LVij。

(3)输入调度。按照一定的调度规则从所有输入VOQ中选择一个有效 VOQik(Sik+LCik＜C)进行服务。

(4)数据包切分。对输入调度选中的 VOQik队列，按照步骤(2)确定的对应实际切片长度 Sik，相邻的数据包合并起来进行切分，并将切片发送到crossbar交叉点缓存。

自适应数据包切分机制的特点如下：实时跟踪当前调度周期内输入VOQ的状态，确定合适的切片长度。如果各VOQ队列长度之和较大，说明VOQ队列整体占用率较高，则选择较大的切片长度进行数据包切分，保证尽快服务滞留的数据包，以提高排队系统的性能和稳定性；相反，队列长度之和较小时，表示队列拥塞情况较轻，采用对应的小切片长度，以保证小数据包不被长期阻挡，能够得到有效服务，从而提高交换效率和公平性。

2.3自适应数据包切分机制的实现

自适应数据包切分机制的实现如图4所示，主要包括切片长度产生模块、输入调度器、信用值管理模块和切片传输控制模块。

切片长度产生模块根据每个 VOQij对应的计数器记录的队列长度信息，计算产生输入端i的自适应切片长度 Si，并按照步骤(2)确定每个 VOQij可能的实际切片长度 Sij。

输入调度器根据切片长度产生模块提供的切片长度信息Sij，以及信用值管理模块的当前crossbar交叉点队列信息 LCij，判断每个 VOQij是否为有效队列；按照一定的调度规则仲裁选择出一个队列VOQik进行服务。调度完成后将调度决策送到切片传输控制模块。

信用值管理模块接收 crossbar返回的交叉点信用值信息，并根据下一个将被服务队列 VOQik的切片长度信息，实时更新crossbar各交叉点的信用值，即交叉点缓存的占用情况，以防止交叉点队列溢出而导致数据丢失。切片传输控制模块，根据输入调度器的调度决策，控制对应VOQik中的切片数据发送到 crossbar交叉点缓存中。

图4　自适应数据包切分机制的实现框图

3　性能评估

3.1仿真环境和流量模型

本节对提出的自适应数据包切分机制（AMS）和已有变长多包切分（VMS）进行时延性能的仿真分析比较。变长多包切分机制主要考虑5种情况，切片长度分别为64 B、128 B、256 B、512 B和1 024 B。时延是指数据包从进入交换机的输入队列到发送至输出端的时间间隔，以微秒(μs)为单位。性能评估基于16×16的CICQ交换机，运行具有低复杂度、高性能的 RR-LQD调度算法[7]，端口线速率设为 1 Gb/s，crossbar交叉点缓存的最大容量为一个切片信元，仿真时间为1 s。仿真实验中采用Poisson和马尔科夫调制的 Poisson过程(MMPP)[8]两种典型的流量模型。

Poisson流量到达过程中，数据包的包间隔时间t服从指数分布。MMPP模型[8]能很好地模拟真实网络流量的突发特性。MMPP过程为ON和OFF两种状态交替进行，p为ON状态转换到OFF状态的概率，q为OFF跳转到 ON的概率。ON状态是包到达率为 λON的 Poisson过程，OFF状态时无数据包到达。

数据包长度为[40，1 500]B范围内的 IMIX[9]分布模型。IMIX混合模型是一种常用的模拟真实Internet流量的测试模型，包括 3种包长：40 B占 58.33%，576 B占33.33%，1 500 B占8.33%，数据包平均长度为340.26 B。数据包目的端口服从均匀分布，即到达所有输出端口的概率相同。

3.2不同负载下时延性能分析

图5所示为Poisson-IMIX流量模型下，基于不同切分方法的CICQ交换机的平均时延性能。仿真结果说明，对于变长多包切分机制，切片长度越小，平均时延性能越差。VMS-64B，即切片长度为64 B，在负载高于90%时就出现不稳定现象，这是由于高负载下随着队列中数据包的积聚，需要交换的内部信元头开销增加，导致带宽利用率大大降低。VMS-512B和VMS-1024B，当负载大于95%时平均延迟开始迅速增长。而AMS性能最优，在高负载情况下都能够保持良好的时延性能和稳定性。

图5　Poisson-IMIX流量下的平均时延

在MMPP-IMIX的突发流量模型下，平均时延性能如图6所示。由于突发特性的影响，各种切分方法的平均延迟都随着输入负载的增加而逐渐增大。VMS-64B表现最差，自适应数据包切分机制与其他变长多包切分性能接近，在不同负载下平均延迟都低于VMS-64B。

图6　MMPP-IMIX流量下的平均时延

图7表示在 Poisson-IMIX流量模型下所有 40 B大小的数据包的平均延迟，可以看出对于这种情况，AMS机制明显优于VMS机制，即使在99%的负载下都能够保持稳定，表现出理想的时延性能。而几种VMS机制在高负载下出现不同程度的不稳定现象。在负载大于90%时，VMS-64B机制下40 B包的平均延迟随输入负载增加而急剧恶化。变长多包切分中相对较好的VMS-1024B，平均延迟从负载95%就开始快速增长。

图8为MMPP-IMIX流量模型下40 B数据包的平均延迟结果。与图6显示的总体时延性能表现相似，由于MMPP过程的突发性，40 B包的平均延迟都随着输入负载的增加而增长。AMS表现最好，在不同负载下40 B包的平均延迟都低于其他变长多包切分机制。VMS-64B表现最差。

实验结果说明，提出的AMS机制能够有效发挥作用，在两种模拟真实 Internet流量的模型下都表现出良好的延迟性能。而且，根据输入端队列的状态实时调整切片长度，灵活适应动态变化的网络流量以及不同的数据包长度。通过分析40 B数据包的时延结果得到，与VMS相比，AMS机制能有效降低小数据包的延迟。原因在于切片长度随输入队列信息灵活改变的策略，保证队列中大型数据包和实时小数据包都能得到有效服务。在对时延要求较高的实时业务中，不会出现较大切片将小数据包长期阻挡而导致阻塞延迟，从而有效确保交换效率和公平性。因此，AMS比VMS更有优势。

图7　Poisson-IMIX流量下40 B数据包的平均时延

图8　MMPP-IMIX流量下40 B数据包的平均时延

4　结论

本文首先介绍了CICQ交换结构和基本的数据包切分模型，然后针对传统变长多包切分机制交换效率低、灵活性较差的问题，提出了一种新的CICQ交换机自适应数据包切分机制（AMS）。该机制基于实时可变的切片长度，采用相邻数据包结合的方式进行数据包切分，自适应动态变化的网络流量和数据包长度。通过仿真实验比较了采用AMS机制和传统VMS机制的CICQ结构的交换性能，结果表明提出的自适应数据包切分机制在不同流量下具有比VMS机制更优的时延性能，且能够更好地满足实时性业务流量的要求，是一种更高效的数据包切分方法，适用于高性能CICQ交换机的设计实现。

[1]CHAO H J，LIU B.High performance switches and routers[M]. Hoboken，New Jersey：Wiley-IEEE Press，2007.

[2]YOSHIGOE K，CHRISTENSEN K J.An evolution to crossbar switches with virtual output queuing and buffered cross points[J].IEEE Network，2003，17(5)：48-56.

[3]KATEVENIS M，PASSAS G，SIMOS D，et al.Variable packet size buffered crossbar(CICQ)switches[C].Proc of IEEE International Conference on Communications.Paris，France：IEEE，2004：1090-1096.

[4]CHRISTENSEN K，YOSHIGOE K，ROGINSKY A.Performance evaluation of packet-to-Cell segmentation schemes in input buffered packet switches[C].Proc of IEEE International Conference on Communications.Paris，France：IEEE，2004：1097-1102.

[5]STEPHENS D，ZHANG H.Implementing distributed packet fair queueing in a scalable switch qrchitecture[C].Proc of IEEE INFOCOM’98 Conference.San Francisco，CA：IEEE，1998：282-290.

[6]KATEVENIS M，PASSAS G.Variable-size multipacket segments in buffered crossbar(CICQ)architectures[C].Proc of IEEE International Conference on Communications，2005：999-1004.

[7]彭来献，恽姿，赵文栋，等.一种基于最长队列预测的 CICQ交换结构调度算法[J].电子与信息学报，2010，32（6）：1457-1462.

[8]PAN D，YANG Y.Localized independent packet scheduling for buffered crossbar switches[J].IEEE Transactions on Computers，2009，58(2)：260-274.

[9]Agilent Technologies，JTC 003：Mixed packet size throughput[EB/OL].The Journal of Internet Test Methodologies. Agilent Technologies，2007.

A novel efficient adaptive packet segmentation scheme in CICQ switches

Wang Xiaoting，Wang Yiwen，Li Ping
(School of Microelectronics and Solid-State Electronics，State Key Laboratory of Electronic Thin Films and Integrated Devices，Chengdu 610054，China)

In order to operate on variable-size packets in CICQ(Combined Input Crosspoint Queued)switch effectively,segmentation and reassembly(SAR)is generally used to segment packets into cells to be switched.Existing packet segmentation schemes have the disadvantage of low switching efficiency and poor flexibility in dynamic network traffic.In this paper,a novel efficient adaptive packet segmentation scheme for CICQ switch is proposed.The main idea is modifying the segment size flexibly according to the status of input queues,and performing packet segmentation based on cell-merging,to adapt different traffic flows and packet lengths in network environments.Simulation results show that the proposed packet segmentation scheme is can exhibit excellent delay performance and system stability superior to existing variable-size multipacket segments scheme under various traffic models.

CICQ switch；segmentation scheme；adaptive

TP393

A

10.16157/j.issn.0258-7998.2016.02.031

（2015-10-15）

王晓婷（1987-），女，博士研究生，主要研究方向：高性能交换机架构设计、调度算法设计、SOC实现。

王忆文（1966-），通信作者，男，博士，教授，主要研究方向：高性能交换机技术、可重构 SOC架构，指纹识别等，E-mail：yiwen@uestc.edu.cn。

李平（1957-），男，硕士，教授，博导，主要研究方向：FPGA设计与测试、SOC设计与验证。

中文引用格式：王晓婷，王忆文，李平.一种高效自适应的 CICQ交换机数据包切分机制[J].电子技术应用，2016，42 (2)：114-117，121.

英文引用格式：Wang Xiaoting，Wang Yiwen，Li Ping.A novel efficient adaptive packet segmentation scheme in CICQ switches[J]. Application of Electronic Technique，2016，42(2)：114-117，121.