一种具有网络编码功能的代数交换系统及其编码算法

摘要

本发明属于通信技术领域，涉及到代数交换和网络编码等范围，具体涉及一种具有网络编码功能的代数交换系统及其编码算法。本发明是具有网络编码功能的代数交换系统中的编码模块，其功能和特点是通过对已经引入网络编码机理的预处理过的数据进行编码，添加有效的冗余信息，在输出端通过解码来恢复丢失的信息，从而降低数据包在交换过程中的丢失率，从而达到增加网络吞吐量，提高通信效率等目标。

说明书

技术领域

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

背景技术

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

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

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

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

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

●硬件查找路由表；

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

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

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

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

代数交换是一种多路径自路由交换结构[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)；其中，N为大于1的整数。

上述各个模块相互配合完成数据包在系统中的切割、编码、交换、组装、解码等操作。

一种具有网络编码功能的代数交换系统的编码算法，包括：接收从预处理模块接收的信元，然后对所有的属于同一个数据包的信元按照按位异或的方式进行编码，从而产生一个新的编码信元，最后将这个新产生的编码信元发送给VOQ调度模块和交换结构(即代数交换模块)，整个处理过程如图2所示。

本发明是具有网络编码功能的代数交换系统中的编码模块，其功能和特点是通过对已经引入网络编码机理的预处理过的数据进行编码，添加有效的冗余信息，在输出端通过解码来恢复丢失的信息，从而降低数据包在交换过程中的丢失率，从而达到增加网络吞吐量，提高通信效率等目标。

附图说明

图1为实施例一的具有网络编码功能的代数交换系统的示意图；

图2为实施例一的数据包在系统中的编解码过程示意图；

图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)。在组装模块中16(1-6-1,...,1-6-N)，系统将归属于同一个数据包的信元按照一定的顺序重新组装，恢复出原始的数据包。只有当组装过程中监测到有一个信元丢失时，才会启动解码模块(1-7-1,...,1-7-N)，通过解码恢复出丢失的信元。输出端口18(1-8-1，...，1-8-N)用于输出数据包。

编码过程如图2所示，一个标准的IP数据包Packet1在数据预处理模块中被切割成N个长度固定的信元，图中以cell标示信元。每个信元由信元头(cellhead)和数据(payload)组成，如图3(a)所示。然后将N个cell的数据(payload)部分按位异或产生一个新的编码信元的数据块，接着按照图3(b)所示的格式为这个编码数据块产生一个新的信元头并附加到这个新的编码数据块前，这样就产生了一个新的信元，即第N+1个信元cell_N+1。信元头各个标志位的定义如图3(c)所示。我们可以这样简单地表示整个编码过程：cell_N+1＝cell_1⊕cell_2⊕…⊕cell_N。最后这N+1个信元被发送到VOQ模块。

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

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