代数交换系统及其组装和解码算法、数据包的解码算法

摘要

本发明属于通信技术领域，涉及到代数交换和网络编码等范围，具体涉及一种代数交换系统及其组装和解码算法、数据包的解码算法。本发明是具有网络编码功能的代数交换(即多路径自路由)系统中的解码算法。其特点是能够根据编码信元中的冗余信息恢复出在交换结构中丢失的信元，而信元的丢失是信元经过交换结构的时候由于端口争用造成的。这种解码功能能够减小数据包在交换过程中的丢失率，从而达到增加网络吞吐量，提高通信效率等目标。

说明书

技术领域

本发明属于通信技术领域，到代数交换和网络编码等范围，具体涉及一种代数交换系统及其组装和解码算法、数据包的解码算法。

背景技术

近年来，随着互联网用户数量飞速增加，网络规模不断扩大，丰富的网络应用尤其是网络视频服务的流行普及，现有网络的数据流量持续迅猛增长，这对作为网络互连重要枢纽的路由器提出了巨大的挑战。Internet规模的扩展、网络流量的激增，以及新型网络应用的不断出现，对路由器等网络设备提出了新的要求。高性能的路由器要具有强大的能力和良好的扩展性，具有较高的稳定性、可靠性、安全性。

就目前而言，高性能路由器一般具有以下特征：

·系统具有足够高的数据包处理能力以达到每秒数百万包(Mp/s)的转发能力；

·分布式大容量矩阵式交换结构；

·高密度、多端口及其扩展性；

·硬件查找路由表；

·全面的冗余设计、高可靠性；

·有效的QoS手段来满足客户在不同场合对不同服务质量的要求。

研究出高性能的路由器来满足人们的网络技术需求已经迫在眉睫。为了提高路由器的性能并降低实现代价，国际上提出了许多交换结构，其中又引人注目的有共享总线结构[1],共享存储(SharedMemory)[2],交叉矩阵(Crossbar)[4]等结构。共享总线结构易于扩展也比较容易实现，但是其速率较低。共享存储结构虽然可以达到比较高的速度，但是其速率仍然受到内存速度的限制，其存储器带宽性能瓶颈使得当端口数量较多时，存储器带宽需求较大，不能满足大规模扩展应用的条件。交叉矩阵是最典型的使用最普遍的交换结构，它是一种简单的空分交换开关，将N个输入端口和N个输出端口任意的互连。当端口数N较小时，交叉矩阵是一种实现无阻塞、自路由的理想交换结构。但该结构需要的交换单元的数量是N²，硬件实现复杂度为O(N²)，当N较大时，其成本变得不可接受，不满足大规模扩展的要求。

为了构造一种适合大规模扩展的交换结构，何伟等人提出了一种多路径自路由交换结构[3]，这种结构将代数分配格理论应用于自路由模型，该结构具有完全分布式自路由、无内部缓存、无缓存时延及无抖动等优势[3]。在保证提供QoS的条件下，适合大规模扩展，很好的满足了用户的需求。

然而这种结构具有一定的由内部阻塞造成的丢包，这一缺陷严重阻碍了该结构的发展与应用。本发明提出了在多路径路由交换系统的基础上，添加网络编码模块，并设计了一套数据交换和编码算法来更好的实现多路径路由交换系统的各项功能。该方法的核心是通过对数据包进行编码，添加有效的冗余信息，解码恢复丢失的信息，来减小数据包在传输过程中的丢失率，从而达到增加网络吞吐量，提高通信质量等目标，减小了数据重传的代价。

引用文献：

[1]ChengTD,FranaszekPA,GeorgiouCJ,etal.Dynamicswitchprotocolsonasharedmediumnetwork:U.S.Patent5,235,592[P].1993-8-10.11s.

[2]AndradeP,CoopermanM,SieberRW.ATMsharedmemoryswitchwithcontentaddressing:U.S.Patent5,513,134[P].1996-4-30.

[3]HuiLi,WeiHe,XiCHEN,PengYi,BinqiangWang,“Multi-pathSelf-routingSwitchingStructurebyInterconnectionofMultistageSortingConcentrators”,IEEECHINACOM2007，Aug.2007,Shanghai.

[4]B.Prabhakar，N.McKeown，R.Ahuja；“Multicastschedulingforinput-queuedswitches”，IEEEJ.SelectedAreasCommun，vol.15，no.5，p855-866，1997.

发明内容

一种具有网络编码功能的代数交换系统，主要包含以下模块：N个输入端口(1-1-1，...，1-1-N)、数据预处理模块(1-2)、编码模块(1-3)、N个VOQ调度模块(1-4-1,1-4-2，...,1-4-N)、代数交换模块(1-5)、组装模块(1-6-1，...,1-6-N)、解码模块(1-7-1,...,1-7-N)、N个输出端口(1-8-1,...,1-8-N)；上述各个模块相互配合完成数据包在系统中的切割、编码、交换、组装、解码等操作。

一种具有网络编码功能的代数交换系统的组装和解码算法，包括：数据信元以并行的形式经过代数交换模块，组装模块先将并行数据信元写入并转串缓存中，后将串行的数据信元从并转串缓存读出，然后组装模块中的输入状态机分别进行信元头提取、信元头识别、存取地址确定、存储到组装缓存、数据包完整判断等操作；其中数据包完整判断将判断结果发送到输出状态机；组装这一功能主要是靠输出状态机实现的，分别进行数据包完整判断结构接收查询、取完整包或丢弃或解码、数据包输出；若数据包完整则不用解码，直接发送数据包至输出缓存；若数据包中丢了一个数据信元，可以结合剩下的数据信元和编码信元解码出丢失的数据信元；若丢了两个及两个以上则直接丢弃此包。

一种具有网络编码功能的代数交换系统的数据包的解码算法，包括：信元在经过交换后，可能产生丢失，通过在数据编码模块中，对切割好的信元按照一定的规则进行编码，将新产生的编码信元同其他原有信元一起送入VOQ模块和交换结构，在交换结束后，若信元有丢失，则由通过特定的解码算法，在解码模块和组装模块中恢复出原始数据信息，整个处理过程如图2和图3所示。

本发明的这种解码功能能够减小数据包在交换过程中的丢失率，从而达到增加网络吞吐量，提高通信效率等目标。

附图说明

图1为具有网络编码功能的代数交换系统。

图2为数据包Packet1在系统中的处理过程。

图3为信元组装和解码设计图。

具体实施方式

下面通过具体实施方式结合附图对本发明作进一步详细说明。

本发明提出了一种在具有网络编码功能的代数交换系统中的适合代数交换的编码算法。该算法以信元为单位进行编码，把编码后的数据发送到VOQ调度模块器和代数交换结构中，最后在解码和组装模块中恢复出原来的数据包。

本发明中所涉及的整个基于网络编码的代数交换系统的结构如图1所示。标准的IP数据包从N个输入端口11(1-1-1,...,1-1-N)进入，在数据预处理模块12中(1-2)，将添加同步控制信号，并把数据包切割成长度相等的数据片和添加包头控制信息。图1中黑色粗箭头表示封包，即标准的以太网数据包；数据包进入数据预处理模块12之后，灰色粗箭头表示被切割之后的数据片，即信元；灰色细箭头表示流控，即数据同步信号。编码模块13(1-3)对信元进行编码，产生的冗余信息随原始数据包一起进入后级模块。N个并行的VOQ模块14(1-4-1,...,1-4-N)将数据按照输出端口分流，同时将数据包按一定的调度算法送入交换结构15(1-5)，交换结构15即代数交换模块。在组装模块16中(1-6-1,...,1-6-N)，系统将归属于同一个数据包的信元按照一定的顺序重新组装，恢复出原始的数据包。只有当组装过程中监测到有一个信元丢失时，才会启动解码模块(1-7-1,...,1-7-N)，通过解码恢复出丢失的信元。输出端口18(1-8-1，...，1-8-N)用于输出数据包。

结合图3，组装模块包含两个功能：并转串(3-1)和组装输出。并转串部分(即并转串状态机31)将交换处理完的数据信元串行化：在前半个交换间隙内，将并行数据信元存入信元缓存32(3-2)中，同时提取出信元头，检验信元有效性，放入信元头缓存33(3-3)中，在后半个交换间隙内，将信元以串行的方式读出，并添加控制信号，连同信元头缓存一起送入组装部分。

在组装输出部分，其输入状态机分别进行信元头提取、信元头识别、存取地址确定，存入包头缓存34(3-4)、数据包完整性判断等操作，由于数据包在被切割成若干个信元时，给每个信元配备的数据包识别字和数据信元识别字，存放在信元头中。在信元头提取出后，根据数据包识别字和数据信元识别字确定信元存储的地址。数据信元存入数据包缓存36(3-6)后，检查数据包是否完整，若完整或者不完整且超过最大等待时间，将数据包完整性判断结果(包括包完整、包丢失信元但可解码恢复、包丢失信元并不可解码恢复)发送到输出状态机。

组装这一功能主要是靠输出解码状态机35(3-5)实现的，分别进行数据包完整判断结构接收查询、取完整包或丢弃或解码、数据包输出。若数据包完整则不用解码，直接发送数据包至输出缓存37(3-7)；若数据包中丢了一个信元，可以结合剩下的信元和编码信元解码出丢失的数据信元；若丢了两个及两个以上则直接丢弃此包做异常处理，并清空存储空间。

解码是编码的逆过程，思路如下：如图2所示，Packet1由N个信元组成，编码后一共有N+1个信元。假如在交换的过程中，Packet1中第n个信元丢失，则启动解码模块恢复出丢失的数据。解码算法为：Cell_n＝Cell_1⊕Cell_2⊕…⊕Cell_n-1⊕Cell_n+1⊕…⊕Cell_N+1。

最后，输出缓存将组装好的数据包发送至网络接口输出。

图2具体为，对数据包Packet1先进行数据预处理21,从而得到被切割的信元22，再对这些信元进行编码操作23，从而得到新的信元24，之后经过VOQ调度器25处理、交换模块26处理，完成组装、解码步骤27。

以上内容是结合具体的实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换。