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

摘要

本发明属于通信技术领域，涉及到网络编码和代数交换等范围，具体涉及一种具有网络编码功能的代数交换系统及其预处理算法。本发明是具有网络编码功能的代数交换系统中的数据预处理模块。该模块的主要功能和特点是：为了更好更快捷的执行数据在系统中的编码和解码，本发明在数据进入编码模块之前进行预处理，对进入的数据包添加了一个包头，并把数据包进行切割为长度固定的信元，然后再送入到调度器和编码器中，极大地加速了编码和解码的处理过程，从而提高了系统的吞吐量和通信效率。

说明书

技术领域

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

背景技术

随着互联网的发展突飞猛进，网络技术已经渗透到人类生活的各个方面，深刻影响着人们的工作和学习方式。互联网规模的扩大和用户数量急剧增加，网络复杂性日益明显。现有网络的数据流量持续迅猛增长，这给以IP为核心的互联网带来了越来越严重的技术挑战。现有的网络主要由交换设备和传输设备组成。目前以路由器为代表的交换设备的核心交换能力严重滞后于传输线卡带宽的发展，路由器已经成为制约网络进一步发展的瓶颈。同时，Internet以TCP/IP体系结构为基础，其网络层只提供尽最大努力交付的服务并不提供服务质量(QoS)承诺。因此，研究出更高效且保证QoS的交换结构是充分利用现有传输能力和为下一代网络提供QoS保证的业务的关键。

为了提高路由器的性能并降低实现代价，国际国内提出了许多交换结构，其中又引人注目的有共享总线结构[1],共享存储(Shared Memory)[2],交叉矩阵(Crossbar)[4]等结构。

共享总线结构易于扩展也比较容易实现，但是其速率较低。共享存储结构虽然可以达到比较高的速度，但是其速率仍然受到内存速度的限制，其存储器带宽性能瓶颈使得当端口数量较多时，存储器带宽需求较大，不能满足大规模扩展应用的条件。交叉矩阵是最典型的使用最普遍的交换结构，它是一种简单的空分交换开关，将N个输入端口和N个输出端口任意的互连。当端口数N较小时，交叉矩阵是一种实现无阻塞、自路由的理想交换结构。但该结构需要的交换单元的数量是N²，硬件实现复杂度为O(N²)，当N较大时，其成本变得不可接受，难以满足大规模扩展的要求。

代数交换是一种多路径自路由交换结构[3]，这种结构将代数分配格理论应用于自路由模型，该结构具有完全分布式自路由、无内部缓存、线速及无抖动等优势[3]。在保证提供QoS的条件下，适合大规模扩展。然而这种结构会产生内部争用和外部阻塞，从而导致了一定的丢包率。为了降低丢包率和提高数据在传输中的吞吐率，一种有效的方法是将网络编码和代数交换结构融合，利用网络编码来恢复丢失的数据包，从而有效降低系统的丢包率。本发明就是针对基于网络编码的代数交换系统中的数据预处理算法。

引用文献：

[1]Cheng T D,Franaszek P A,Georgiou C J,et al.Dynamic switchprotocols on a shared medium network:U.S.Patent 5,235,592[P].1993-8-10.11s.

[2]Andrade P,Cooperman M,Sieber R W.ATM shared memory switch withcontent addressing:U.S.Patent 5,513,134[P].1996-4-30.

[3]Hui Li,Wei He,Xi CHEN,Peng Yi,Binqiang Wang,“Multi-pathSelf-routing Switching Structure by Interconnection of MultistageSorting Concentrators”,IEEE CHINACOM2007，Aug.2007,Shanghai.

[4]B.Prabhakar，N.McKeown，R.Ahuja；“Multicast scheduling forinput-queued switches”，IEEE J.Selected Areas Commun，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)；

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

一种具有网络编码功能的代数交换系统的预处理算法，包括：从原始数据包中提取目的地址和数据进入的端口号，然后根据数据包的长度和信元长度，判断该数据包是否需要切割，若需要切割的话，计算出将要切割成的信元的数目以及需要填充的字节数，然后再把所有这些信息储存在一个信元包头(图2)中并对数据包根据前面的判断和计算结果切割成多个信元，最后把包头附加在每个切割而成的信元上发送给后面编码模块；

预处理模块产生的信元包头中包含了各种控制信息，后面的编码模块，交换结构以及解码模块都要依据此包头所包含的信息完成一系列指定的功能。

本发明在数据进入编码模块之前进行预处理，对进入的数据包添加了一个包头，并把数据包进行切割为长度固定的信元，然后再送入到调度器和编码器中，极大地加速了编码和解码的处理过程，从而提高了系统的吞吐量和通信效率。

附图说明

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

图2(a)为实施例一的数据总线和控制总线格式。

图2(b)为实施例一的包头信息定义。

具体实施方式

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

本实施例提出了一种在具有网络编码功能的代数交换系统中的适合代数交换的编码算法。该算法以信元为单位进行编码，把编码后的数据发送到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)用于输出数据包。

在数据预处理模块12中，为了方便数据识别和处理，数据预处理模块12首先对输入的数据添加了位宽为2的同步控制信号。当控制总线信号为2’b11时，表示当前时钟下与其同步的数据为整个数据包的起始和包头；当控制总线信号为2’b00时，表示当前同步数据为原始的系统输入数据包中的有效载荷；当控制总线信号为2’b10时，表示当前数据为整个数据包的结束。假定系统的数据总线的位宽是64位，那么数据包的格式如图2(a)所示。

添加同步控制信号后，数据包在数据预处理模块的处理分为2个步骤：1)根据数据包的长度和信元的长度判断是否需要切割和切割的信元的数量；2)将分组切割成信元并为每个信元添加包头。

在第1个步骤中，根据数据包的实际长度和事先定义的信元的长度，首先可以判断该数据包是否需要切割：若数据包的长度小于信元的长度，则不需要切割，而且需要将数据包填充一定数目的无效字节使之长度等于一个信元的长度；若数据包的长度大于信元长度，则计算出需要切割成的信元的数量和最后一个信元需要填充的无效字节的长度。若数据包的长度恰好是信元的长度的整数倍，则切割后无需填充无效字节。最后将这些信息保存在数据包的自定义包头中并把数据传送到执行第2个步骤的功能模块中。

在第2个步骤中，数据包将根据第1步中包头的信息对数据包展开切割、填充的操作。若数据包无需切割，则把数据包填充若干无效字节使之达到信元的长度，并且按照图2(b)的包头格式更新包头信息；若数据包需要切割，则先把数据包的有效载荷按顺序切割成多个信元，然后给每个信元的开头添加图2(b)所示的包头。

整个数据的处理过程中，各个步骤分工协作，或提取数据包内信息生成自定义包头，或利用前级生成的包头提供的信息完成自身预先定义的功能。自定义的包头发挥了巨大的作用，本发明中自定义包头包含分组有效标记、编码标记、目的端口数等信息，如图2(b)所示，下面详细介绍包头的功能及它们所包含的信息。

分组有效标记：用于区分有效分组和无效信元，该类包头信息用于在代数交换系统中，若出现争用，则无效信元优先级较低，有效信元丢失的可能性较小。

保留位：暂时保留，用于系统扩展之后的信息补充。

封包尾信元标记：标记该信元在原始数据包中是否是最后一个信元。若是，则该信息为1，否则为0。

网络编码标记：该字段是编码模块使用，标记该信元是否为编码产生的信元，用于在组装和解码模块时，恢复原始数据包。

分组填补数：一个数据包被切割成长度固定的信元，若该数据包的长度不是信元长度的整数倍，则在最后一个信元中需要填补一定数量的无效的信息，该包头记录需要补充的无效信息的数量，单位是字节。当在组装和解码过程中恢复出原始数据包之后，同时丢弃无效信息。

分组源端口和目的端口：用于记录信元的源地址和目的端口地址。

分组总数：用于组装过程中将收到的信元数量与该包头信息比较，判断是否有信元丢失。

分组识别号：用于记录信元在原始数据包中的位置，用于组装和解码模块。

数据包识别号：相同数据包识别号的信元组装在一起，恢复会原始数据包。

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