基于加权层分配和轮转实现的支持区分服务质量交换结构

摘要

一种基于加权层分配和轮转实现的支持区分服务质量交换结构，由N个1x1的包流均衡端、N个1xk的解复用端、k个NxN的交换层和N个kx1的复用端组成。其中N为交换结构支持的输入输出端口数，k为交换结构支持的并行的交换层数。输入的分组包经过包流均衡端到解复用端，解复用端输出连接所有的并行交换层，单个交换层的输出连接所有的复用端，分组包在复用端输送至输出端口。本发明基于权重值为不同服务质量类的包流分配相区分的交换层，并仅需用轮转，就实现了分布式控制、区分服务质量支持和降速交换，且实现复杂度低、不需要中心调度算法和反馈机制、简易动态可调，适用于高性能核心路由器中。

说明书

技术领域：

本发明涉及一种高性能路由器中的交换结构，尤其涉及一种高性能路由器中基于加权层分配和轮转实现的支持区分服务质量的交换结构。此交换结构适合于广域主干网中的分组域核心路由器实现区分服务质量支持和降速交换，适用于广域主干网节点进行分组交换的核心路由器内部。属于计算机网络技术领域。

背景技术：

目前，支持区分服务质量的路由器交换结构主要有四种方法：

基于权重值匹配的交换结构(McKeown N..Scheduling algorithms for input-queuedcell switches[D].University of California at Berkeley.1995.)：通过配置端口不同的权重值来控制交换结构匹配调度的方法实现。该方法结构简单、易于实现，但调度控制是基于信元的，难以达到真正意义上基于流的服务质量的保证，粒度较粗，且容易使匹配率降低，影响吞吐量。

基于转置矩阵匹配的交换结构(Chang C.S.，Lee D.S.，Jou Y.S..Load balancedBirkhoff-von Neumann switches，part I：one-stage buffering[J].Computer Comm，2002，25：611-622.)(Chang C.S.，Lee D.S.，Lien C.M..Load balanced Birkhoff-von Neumannswitches，part II：multi-stage buffering[J].Computer Comm，2002，25：623-624.)：通过分解得到不同的加权矩阵来控制交换结构匹配调度的方法实现。该方法操作复杂度低，但分解需要事先对流的需求有明确的认知，并且在端口多、数据量大情况下计算复杂、计算量大。

基于输出反馈匹配的交换结构(Firoiu V.，Zhang X.，Gunduzhan E.，Christin N..Providing service guarantees in high-speed switching systems with feedback outputqueuing[J].IEEE Transactions on Parallel and Distributed Systems，2006，17(5)：434-447.)(Farajianzadeh A.，Khorsandi S..Toward a differentiated-service enabledparallel packet switch[C].IEEE ISCC’07，2007.885-891.)：通过输出反馈对输入端进行调度和匹配控制的方法实现。该方法可实现动态控制，但根据交换结果进行调度调整较为被动，并且需要复杂的中心反馈控制模块，无法实现分布式控制，导致交换系统健壮性不强。

基于静态、动态分类优先级的交换结构(Shi L.，Liu B.，Li W.，Wu B.，Liu Y..DS-PPS：A practical framework to guarantee differentiated QoS in terabit routers withparallel packet switch[C].IEEE INFOCOM’06，2006.1-12.)：通过对不同业务包流类型和输出反馈情况分别按照其对应的静态恒定机制和动态可调机制进行交换层调度和输出优先级配置的方法。该方法弱化对输出端反馈信息处理的复杂度，但解复用端的分配繁琐，交换层和复用层结构复杂，并且仍然需要整体级别的反馈控制。

由此，上述支持区分服务质量的交换结构都普遍存在着中心算法调度、反馈机制、结构复杂等缺陷。

在解决高性能核心路由器交换结构的扩展瓶颈和实现降速上主要采用并行包交换结构(S.Iyer，A.Awadallah，N.McKeown.Analysis of a packet switch with memories runningslower than the line rate[C].IEEE INFOCOM’00，2000.529-537.)(S.Iyer，N.McKeown.Making parallel packet switches practical[C].IEEE INFOCOM’01，2001.1680-1687.)(S.Iyer，N.McKeown.Analysis of the parallel packet switches[J].IEEETransactions on Networking，2003，11(2)：314-324.)，并行包交换结构利用多个并行的低速交换层实现高速交换，并减少了工作在线速line rate的缓存的数量。并行包交换结构一般包含N个线速为R的输入端口和输出端口，以及k个N×N的慢速交换机组成的交换层，交换层的端口速率为Sx(R/k)，其中S为加速比，并行包交换结构在中心算法调度下不带有工作在线速的缓存且S＝2时，或者在分布式下带有少量工作在线速的缓存且S＝1时，均可以模拟一种先来先服务输出排队交换性能。理想情况下，k不断增加可以使降速性能无限提升。但并行包交换结构无法提供区分服务质量支持，不能实现基于流的控制和管理，在分布式下加速比为1时仍然需要一定量的工作在线速的缓存，难以满足高性能路由器的继续发展要求。

发明内容：

本发明的目的在于针对现有技术的不足，设计提出一种新的高性能路由器中基于加权层分配和轮转实现的支持区分服务质量交换结构，该交换结构基于权重值为不同服务质量类包流分配相区分的交换层来支持区分服务质量，并且仅需用轮转，实现了分布式控制、区分服务质量支持和降速交换。从而依靠实现复杂度低的加权层分配和轮转取代了复杂度高的调度算法和匹配算法，无需中心控制和反馈机制，并且通过分布式环境下的并行结构使单个模块的计算量降低为总流量的1/N，N为交换结构支持的输入输出端口数。

为实现上述目的，本发明的交换结构解决其技术问题所采用的技术方案是：若本发明的交换结构支持N个输入端口和N个输出端口，每个端口支持的最大线速R，则本交换结构由N个输入R速输出R速的1 x 1的包流均衡端(1)、N个输入R速输出R/k速的1 x k的解复用端(2)、k个输入R/k速输出R/k速的NxN的交换层(3)和N个输入R/k速输出R速的kx1的复用端(4)组成，其中k为本交换结构支持的并行的交换层(3)数，为实现降速有k>N。输入的分组包输入到包流均衡端(1)，N个包流均衡端(1)的输出端分别连接着N个解复用端(2)的输入端，单个解复用端(2)的k个输出端分别连接所有k个并行的交换层(3)的每层中的一个输入端，单个交换层(3)的N个输出端分别连接所有的N个复用端(4)的每个中的一个输入端，分组包在复用端(4)输送至输出端口。

本发明的交换结构中的包流均衡端(1)由两个功能模块组成：包均匀模块(5)和负载平衡模块(6)，包流均衡端(1)将接收到的分组包在包均匀模块(5)中分拆成等大的信元队列，并在每个信元头部添加有信元的目的端口号和信元序列号信息的信元头，之后负载平衡模块(6)将信元队列中的信元依次轮转发送到N个解复用端(2)的输入端，使得N个解复用端(2)的输入端口接收到的信元的大小和各个服务质量的信元流量都均匀化，以支持分布式控制。

本发明的交换结构中的解复用端(2)具有流量计数器(7)和分配控制(8)，解复用端(2)针对每一种服务质量类都单独拥有一个流量计数器(7)，解复用端(2)收到一个信元就会在该信元对应的服务质量类流量计数器(7)加一，然后根据包流流量计数器(7)中各个服务质量的流量变化动态调整权重值，分配控制(8)基于更新后的权重值为不同服务质量类信元流分配相区分的交换层(3)，之后将信元轮转转发至其所分配的交换层(3)输入端，以支持区分服务质量。

本发明的交换结构中的交换层(3)输入端将收到的信元根据在包均匀模块(5)添加的信元头中的目的端口号信息存放在输入端虚拟输出队列VOQ(9)缓存中，此时，同一个交换层(3)的各个输入端口接收到的信元流完全同态化，只要将交换层(3)所有输入端口VOQ(9)以轮转关系匹配(10)对应到交换层(3)的输出VOQ(11)，就可以实现交换，之后交换层(3)的输出VOQ(11)将接收到的信元发送到与其相连接的复用端(4)的输入端，通过并行结构和k>N条件，轮转关系匹配(10)输出为NR/k速的，实现降速交换。

本发明的交换结构中的复用端(4)输入端以轮转方式将接收到的信元存放在基于服务质量类分层的虚拟输入队列QoS-VIQ(12)缓存中，复用端(4)在QoS-VIQ(12)中根据在包均匀模块(5)添加的信元头中的目的端口号和信元序列号信息对接收到的信元队列进行调序和检验丢包情况，在完成上述工作后将信元队列恢复成在包流均衡端(1)接收时的分组包，复用端(4)将恢复后的分组包输送到输出端，完成整个交换过程。

和现有技术相比，本发明基于加权层分配和轮转实现的支持区分服务质量交换结构具有的优越性是：

依靠基于权重值为不同服务质量类包流分配相区分的交换层的分层思想来支持区分服务质量，并仅需用轮转实现，取代目前支持区分服务质量交换结构的复杂的调度算法。在无需加速比且分布式环境下所有缓存工作速率均低于线速，达到降速交换，且仅需通过带低速虚拟输出队列VOQ的轮转输出实现，无需带有匹配算法的交叉开关矩阵Crossbar。不需要目前支持区分服务质量交换结构所要求的中心调度算法和反馈，且实现复杂度低，对包流具有简易动态可调的测量、控制和管理功能，且无输入包的大小必须为等大的限定。

附图说明：

图1是本发明基于加权层分配和轮转实现的支持区分服务质量交换结构的结构图；

图2是包流均衡端(1)的包均匀模块(5)图；

图3是包流均衡端(1)的负载平衡模块(6)图；

图4是解复用端(2)转发图；

图5交换层(3)轮转图；

图6复用端(4)模块运行过程图。

图中：

1.包流均衡端，2.解复用端，3.交换层，4.复用端，5.包流均衡端(1)的包均匀模块，6.包流均衡端(1)的负载平衡模块，7.解复用端(2)包流流量计数器，8.解复用端(2)分配控制，9.交换层(3)输入端虚拟输出队列VOQ，10.交换层(3)轮转关系匹配，11.交换层(3)输出VOQ，12.复用端(4)基于服务质量类分层的虚拟输入队列QoS-VIQ。

具体实施方式：

以下结合附图对本发明技术方案的具体实施方式作进一步详细描述。

描述中讨论信息源为三种服务质量QoS类包流，分别为QoS-H、QoS-M、QoS-L。为QoS-H类的分组包，i为输入端口，j为目的出口，是QoS-H类进入本发明的交换结构的第m个分组包。为QoS-M类的分组包，参数参照为QoS-L类的分组包，参数参照为QoS-H类的信元，i为输入端口，j为目的出口，是QoS-H类进入本发明的交换结构的第m个分组包分拆成的第n个信元，n的最大值为原分组包大小除以64字节整除时所得的整数部分或非整除时所得的整数部分加1。为QoS-M类的信元，参数参照为QoS-L类的信元，参数参照

描述以N x N交换结构为例。

在图1中，本发明的交换结构的组成顺序是：N个R速输入、R速输出的1 x 1的包流均衡端(1)的输出端分别连接着N个R速输入、R/k速输出的1 x k的解复用端(2)输入端，单个解复用端(2)的k个输出端分别连接所有的k个R/k速输入、R/k速输出的N x N的交换层(3)每层中的一个输入端，单个交换层(3)的N个输出端分别连接所有的N个R/k速输入、R速输出的kx1的复用端(4)的每个中一个输入端，分组包在复用端(4)输送至输出端口。

在图2和图3中所示，包流均衡端(1)由两个功能模块组成：包均匀模块(5)和负载平衡模块(6)。

图2中的包均匀模块(5)的任务就是将输入的不等大的分组包，拆分成等大的64字节信元队列，并在每一个64字节的信元前添加一个字节大小的信元头，信元头的一个字节中记录着信元的目的端口号跟小包的序列号，即或或中的j和n。

负载平衡模块(6)的任务就是使得解复用端(2)各输入端口接收到的各服务质量类信元流情况相同，设对应的映射矩阵为：$M=\left(\begin{array}{cccc}1& 3& 2& 1\\ 2& 1& 3& 2\\ 3& 2& 1& 3\end{array}\right),$则根据映射矩阵得到的负载平衡之后的结果如图3所示。

在图4中，解复用端(2)实现将接收到的不同服务质量类的信元基于其对应的权重分配，转发到不同组别的下一级交换层(3)中。解复用端(2)针对每一种服务质量类的信元流都单独拥有一个权重指针。当接收到信元时，首先辨别信元的服务质量类，并在其相应的服务质量类流量计数器(7)中加1，然后根据其对应的权重指针指向的发送端口，发送到相应的交换层(3)输入端口中。每隔一段固定的时间周期，各计数器(7)中的数值乘以64字节得到其对应服务质量类信元的流量值，之后根据新的流量值解复用端(2)的分配控制(8)调整交换层(3)分配的权重值。分配优先满足高服务质量包流的交换资源需求。权重指针在其分配的指向范围内采用轮转方式工作。

解复用端(2)的分配控制(8)有两项允许：

1.为提高利用率允许有融合层产生。即当信元流速不为层处理速率整数倍时，允许低一级服务质量信元按比例填补。

2.允许为低服务质量级别信元流固定一个分配底线，防止发生饿死现象。

在图5中，交换层(3)的任务是用于实现包交换。将交换层(3)输入端改为带有工作速率在R/k的虚拟输出队列VOQ(9)缓存结构，即每个缓存队列对应一个输出端口。交换层(3)首先对每个输入信元的信元头进行目的端口号的提取，然后将其存放在目的端口号对应的VOQ(9)中。由于交换层(3)之前的模块都采用轮转方式，此时同一个交换层(3)的各个端口输入的信元流基本是同态、同服务质量类、符合统计平均的。因此同一个交换层(3)的所有输入端口VOQ具有基本相同的信元存储情况，只要将每个输入端口VOQ(9)以轮转关系匹配(10)对应到交换层(3)输出VOQ(11)就可以达到100％的交换吞吐量。交换层(3)输出VOQ(11)的作用是为了使得输出包的时延达到同步。此处的轮转匹配(10)的总速率是NR/k，因此是一个低于线速R的轮转，不需要加速比。

在图6中，复用端(4)实现信元序列的调整和恢复分组包，完成交换过程。复用端(4)采用工作速率低于线速的基于服务质量类分层的虚拟输入队列QoS-VIQ(12)缓存结构，即每个输入队列缓存队列对应一个服务质量类。应用一个R速轮转将k个R/k速的复用端(4)输入端口接收到的信元存放在对应的QoS-VIQ(12)中。此时在QoS-VIQ(12)中提取出信元的信元头中的信元序列号，根据这些序列号调整信元顺序和检验丢包情况。在完成上述工作后，就可以丢弃掉信元的信元头，并将信元队列恢复成分拆前的分组包，输出完成交换过程。