具有网络编码功能的片上网络及其网络拓扑和路由算法

摘要

本申请公开了一种具有网络编码功能的片上网络路由器及其适用的网络拓扑和路由算法，编码子模块对接收到的多个分组数据进行编码，编码后的数据由中间路由节点以多播的方式进行转发，解码子模块根据已知信息对接收到的数据进行解码，还原出原始数据；网络编码模块实现了分组数据的压缩，进而增加了网络所传数据携带的信息量，解决了如何达到网络传输容量极限问题，以及便于网络规模扩展，且网络编码功能可以降低网络负载提高网络性能。

说明书

技术领域

本申请涉及通信技术领域，具体涉及用于科研范围的具有网络编码功能的片上网络及其网络拓扑和路由算法。 

背景技术

随着集成电路工艺的发展，总线结构的片上系统的缺点越发突出，为了克服其不足，片上网络（NoC）应运而生。片上网络采用合理的拓扑结构并引入路由交换理论，因此其并行通信的特点可以满足未来发展的需求。例如，2012年Intel公司最新的片上网络处理器Xeon Phi 5110P采用22nm工艺的3D晶体管集成了60个IP核，工作频率高达1.053GHz，并获得高达1.011TFlops的双精度峰值性能，成为高性能计算的新基础。因此，开展片上网络基础理论及关键技术的研究是具有理论意义和实用价值的。

随着应用的发展，多播通信在片上网络的应用越来越广。例如，在分布式共享缓存系统中，为了维持各缓存中数据的一致性需要广播信令，这种情况下多播通信的比例高达12.4%。然而，传统的片上网络设计当中往往只考虑单播通信，如果直接将传统的单播片上网络运用于多播通信，会使得网络性能急剧下降。片上资源有限，多播业务的加入更容易导致阻塞，造成网络流量不均衡、平均链路利用率低，进而降低网络并行性，因此，对于从多播角度出发如何提高片上通信系统的性能是一个挑战。因此，研究片上网络多播技术解决由于多播业务导致的低并行性等问题成为当前业界的研究热点。

多种多播分组可能同时到达一个中间路由器，由于普通的路由节点每次只能转发一种多播分组，其他多播分组需要排队等待，降低了网络的吞吐量，并且无法实现由“最大流最小割”定理决定的最大传输容量。 

发明内容

针对多播分组通信在片上网络应用中，如何达到片上网络的最大传输容量的问题，本发明提出了一种具有网络编码功能的片上网络，以及其网络拓扑和路由算法。

根据本申请的第一方面，本申请提供一种具有网络编码功能的片上网络，包括上子路由器和下子路由器，上子路由器用于处理网络中向上传输的分组数据，下子路由器用于处理网络中向下传输的分组数据；上子路由器和下子路由器分别包括输入模块、开关分配模块、交叉开关模块和输出模块；开关分配模块和交叉开关模块的输出端分别与输出模块信号连接；上子路由器和下子路由器分别还包括网络编码模块；

网络编码模块的输入端与输入模块的输出端信号连接，网络编码模块的输出端分别与开关分配模块的输入端和交叉开关模块的输入端信号连接；

网络编码模块包括编码子模块和解码子模块，编码子模块用于对分组数据做编码处理，解码子模块用于对编码的分组数据做解码处理。

根据本申请的第二方面，本申请提供一种适用于上述片上网络的网络拓扑，包括上子网和下子网，上子网由所有上子路由器相互连接组成，下子网由所有下子路由器相互连接组成；上行子网设有上子纵向链路和上子横向链路，下子网设有下子纵向链路和下子横向链路；上子纵向链路由下向上单向传输，下子纵向链路由上向下单向传输，上子横向链路和下子横向链路分别是双向传输。

根据本申请的第三方面，本申请提供一种应用于上述网络拓扑的路由算法，上子纵向链路和下子纵向链路分别设有路由器，并分别形成Y维路由，上子横向链路和下子横向链路分别设有路由器，并分别形成X维路由；

若分组数据的源路由与目的路由不在同一维上，则分组数据在结束X维路由的节点的前一节点转向Y维路由，并且在此之前可以根据相邻下游节点虚信道数目自适应路由；Y维路由结束后转向X维完成X维路由；若分组数据的源路由与目的路由在同一维上，则无需转向。

本申请的有益效果是：本申请提供的片上网络具有编解码功能，编码子模块对接收到的多个分组数据进行编码，编码后的数据由中间路由节点以多播的方式进行转发，目的节点接收到编码后的数据，解码子模块根据已知信息对接收到的数据进行解码，还原出原始数据；网络编码模块实现了分组数据的压缩，进而增加了网络所传数据携带的信息量，解决了如何达到网络传输容量极限问题；除此之外，在特定的应用背景下，网络编码技术也可以提升网络吞吐量，均衡网络负载，提高带宽利用率、提高整体性能等。

附图说明

图1为具有网络编码功能的片上网络的上子路由器结构图；

图2为适用于3x3 mesh的分组数据格式示意图；

图3为网络编码模块的编码子模块结构图；

图4为网络编码模块的解码子模块结构图；

图5为适用于本发明路由器的网络拓扑图（以3x3规模为例）。

具体实施方式

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

本例提供一种具有编码功能的片上网络，包括上子路由器和下子路由器，上子路由器用于处理网络中向上传输的分组数据，下子路由器用于处理网络中向下传输的分组数据；本例的上子路由器包括输入模块、网络编码模块、开关分配模块、交叉开关模块和输出模块；开关分配模块和交叉开关模块的输出端分别与输出模块信号连接，网络编码模块的输入端与输入模块的输出端信号连接，网络编码模块的输出端分别与开关分配模块的输入端和交叉开关模块的输入端信号连接。

上子路由器的具体结构如图1所示，输入模块包括上子西输入端口11、上子东输入端口12、上子南输入端口13和上子本地输入端口14；输出模块5包括上子西输出端口51、上子北输出端口52、上子东输出端口53和上子本地输出端口；进一步，上子本地输出端口包括上子本地西输出端口541、上子本地东输出端口542、上子本地南输出端口543和上子解码输出端口544。

本例的上子路由器与普通片上网络路由器相比结构基本相似，但不同之处在于包括网络编码模块，网络编码模块用于对输入模块的分组数据做编解码处理，然后，同经过普通路由器一样经过各功能模块完成分组数据的转发；另外，本例的上子路由器将虚信道分配模块与输出模块合并，分组数据在路由器中先经过开关分配模块再分配下一节点虚信道。

本例的下子路由器与上子路由器结构相同，也包括输入模块、网络编码模块、开关分配模块、交叉开关模块和输出模块，但是，下子路由器的输入模块的端口方向不同于上子路由器的输入模块的端口方向，以及下子路由器的输出模块的端口方向不同于上子路由器的输出模块的端口方向，具体的：本例的下子路由器的输入模块包括下子西输入端口、下子东输入端口、下子北输入端口和下子本地输入端口；下子路由器的输出模块包括下子西输出端口、下子东输出端口、下子南输出端口和下子本地输出端口；进一步，下子本地输出端口包括下子本地西输出端口、下子本地东输出端口、下子本地北输出端口和下子解码输出端口。

本例中，上子网或下子网的源节点产生分组，源节点生成的分组包括头微片、体微片和尾微片；本例中，头微片、体微片和尾微片都包括微片类型、虚信道号、编码标记符和分组唯一标识符，在其他实施例中，体微片和尾微片可不携带编码标记符和分组唯一标识符；其中，分组唯一标识符由4bit源地址和3bit序列号组成，序列号为源节点生成的分组编号，当编号达到最大值时自动归零。进一步，头微片还包括分组数据的目的地址和分组数据的分支的目的地址或已经到达的目的地址以及空的解码编号和头微片序号。由于源节点生成的分组不是编码分组，所以解码编号设定为0，即设置空的解码编号，编码后在编码模块正确填充；分组包括至少两个头微片，一个头微片携带解码编号，另一个头微片携带目的地址，具体的，如分组拥有多个头微片（如图2所示，该图适用于3x3 mesh），前几个头微片携带目的地址信息，后几个头微片携带解码编号，每个头微片携带自己的头微片序号。目的地址使用bi-string编码，每一位代表一个节点。每个分组拥有一个唯一标识符。非编码分组的标识符由源地址和该分组在源地址的序号组成，编码分组的标识符由生成该编码分组的编码路由器地址和该路由器生成的编码分组的序号组成。在3x3 mesh网络中，分组的标识符由4bit地址和3bit（可根据网络最高负载调整位宽）序号共7bit组成，分组中剩余的就是携带的负载信息。

网络编码模块包括编码子模块21和解码子模块22，编码子模块21负责网络编解码功能中的编码功能。

如图3所示，编码子模块21包括编码仲裁模块211、编码缓存分配模块212、生成读信号模块213、编码起止控制模块214、编码计算模块215、重组编码微片模块216、编码缓存217、生成编码分组标识符模块218、状态机读编码数据219、输出编码数据状态机模块2110、生成编码头微片模块2111、非编码分组请求开关分配状态机模块2112和编码分组请求开关分配模块2113。本例中，分组必须满足以下条件才能被编码： 1. 分组的目的地址不能与编码路由器坐标有相同的Y坐标；2. 分组是多播分组且是一个分支；3. 两分组彼此的目的地址存在这样的关系，分组的目的地址是另一分组的分支目的地址的子集。

编码子模块21的工作原理是：编码仲裁模块211判断输入模块1端口的分组数据是否满足编码条件，若一组满足编码条件的分组大于两个还要轮询仲裁出两个分组做编码运算，但可以同时有多对（每一对之间没有任何关联）分组做编码运算。仲裁失败的分组跳过编码过程，与分组经过普通路由器一样输出本节点。若同时满足编码条件的分组多于两对，编码缓存分配模块212也要做仲裁（轮询仲裁）处理，给其中的两对分组分配编码缓存217，因为路由器中的缓存数目为2。此时仲裁失败的分组会继续等待编码缓存分配模块212为其分配合适的编码缓存。

分配到合适的编码缓存后，编码子模块21就需要准备读取输入缓存中的分组做编码处理。分组的读取需要生成读信号模块213的读信号。读信号的产生要有严格的控制，防止输入缓存读空或编码缓存满而导致写溢出。而且参与编码的两分组长度不相等，当短分组结束之后其占用的缓存会被释放并存入新的分组，但此时长分组还没有结束，编码计算继续，因此此时就不能再读取短分组曾占用的缓存的数据直到此次编码结束，长分组继续读取。

上述条件满足时便会产生读信号，分组输出输入缓存并输入编码子模块21。分组在编码计算模块215完成编码运算（异或）。分组的所有微片按顺序对齐作异或处理生成编码分组。生成的编码分组微片类型除最后一个微片是尾微片外其余微片都是体微片。微片类型在重组编码微片模块216中设定。该模块还会更新编码分组标识符。编码分组标识符由生成编码分组标识符模块218生成。由于生成的编码分组属于新的分组，即该节点作为源节点产生了一个新的分组，所以需要为编码分组设定分组标识符（7bit）。分组标识符由本地地址（4bit）和当前路由器产生的编码分组序列号（3bit）组成。

此时的编码分组可以存入编码缓存217中，同普通分组一样等待输出本节点。编码分组存入编码缓存217后即刻由编码分组请求开关分配模块2113生成开关分配请求信号，请求交叉开关的使用权限。编码分组获得交叉开关的使用权限后就可以输出编码缓存发送到下一节点。但是在编码缓存中的编码分组的体微片发送前，首先要发送编码分组的头微片。

编码分组的头微片由生成编码头微片模块2111产生。头微片中的信息与普通分组头微片中的信息种类相同。其中编码分组的目的地址为参加编码的两分组的目的地址的并集，编码分组标记设定为1，微片类型设定为头微片，其余信息设定为0但在其他模块更新。编码分组的头微片不会存入编码缓存，只是寄存在寄存器中等待输出。

编码分组的各类型微片按顺序输出，其次序为头微片、体微片、尾微片。输出的顺序由输出编码数据状态机模块2110控制。

另外，上述没有参加编码的分组跳过编码过程输出路由器。非编码分组请求开关分配状态机模块2112等待编码仲裁结束后为这些未编码的分组生成开关分配请求信号。

上述过程中的编码仲裁、编码缓存分配、生成读信号、写缓存和重组编码微片操作还需要编码起止信号的控制。编码起止控制模块214会生成编码开始、编码结束和短分组退出编码运算标识三种信号。编码仲裁和编码缓存分配则使用编码结束信号在编码结束时将所有的信号复位。写缓存则需要编码开始和编码结束信号控制编码分组写入编码缓存。重组编码微片使用编码结束信号判断编码分组的尾微片，为其设置正确的微片类型。生成读信号模块则需要短分组退出编码运算标识，防止误读短分组曾占用的缓存中的新分组。

到此时，编码子模块21已经执行完所有编码操作。编码分组按照图1中的结构顺序从网络编码模块的编码子模块21输出到下一节点，其路由方式与普通路由器相似。唯一不同在于虚信道分配设置在输出端口，分组在输出端口更新虚信道号。因为虚信道分配放置在输出端口所以分组离开输入缓存或编解码缓存时必须保证能分配到空闲的虚信道。

当编码分组经过中间路由器的转发到达目的地址时，编码分组首先存入路由器的输入缓存中，路由计算模块同时计算出输出端口。当路由计算模块发现分组已经到达目的地址时即刻检测该分组是否为编码分组。当分组不是编码分组时，跳过网络编码模块，与通过普通路由器一样输出网络。当分组是编码分组时生成解码请求，请求图1中网络编码模块2的解码子模块22为此编码分组解码。

图4为网络编码模块的解码子模块22。该模块负责网络编解码功能中的解码功能。

解码子模块22包括查找解码分组模块221、解码缓存模块222、生成读信号模块223、生成解码屏蔽信号模块224、解码起止控制模块225、删除编码分组头微片模块226、解码模块227、解码缓存模块228和请求开关分配模块229。

解码子模块22的工作原理是：查找解码分组模块221接收到解码请求后根据编码分组携带的解码编号和输入缓存中非编码分组的标识符查找解码分组，若分组标识符与解码编号相符则判定该分组为解码分组。分组标识符和解码编号在各分组存入输入缓存时由输入模块译码头微片产生。由于解码分组只有一个，所以这里不需要仲裁。

查找到解码分组后，由生成解码屏蔽信号模块224生成屏蔽信号。该信号复位输出端口信息和交叉开关分配模块生成的读信号，防止解码分组等待超时被输出路由器。由于路由器的编解码功能是分布式处理，所以解码分组不能预知其为解码分组，因此需要到达目的节点的非编码分组等待一段时间，等待编码分组的到来，若超时则判定其为非解码分组并将其输出网络。该定时信号由路由计算模块生成，并在输入端口完成计时任务。

查找到解码分组后编码分组就请求解码缓存分配模块222为其分配合适的解码缓存。解码缓存每次应分配两个分别存储解码分组和解码后的分组。

解码缓存分配的结果在生成读信号模块223转化成读信号，读取输入缓存中的解码分组和编码分组。该读信号也应该有严格的流控信号控制，防止输入缓存读空和解码缓存写溢出。同编码类似，解码分组为短分组时，该分组会提前退出解码运算。但解码运算此时没有结束，所以解码分组曾占用的缓存会被新的分组占用。此时，应防止新的分组被读取参加解码运算。这一点需要解码起止控制模块225的调控。

读进来的分组在解码前需要先经过删除编码分组头微片模块226剔除编码分组的头微片。该头微片是编码结束时插入的路由信息微片，与编码运算无关，因此与解码运算亦无关，应删除。

删除头微片的编码分组输入解码模块227与解码分组完成解码任务。由于编码时，在编码运算结束时对微片类型做了调整，所以解码后的微片类型也是错误的需要调整。与解码运算同时完成。

解码后的分组与解码分组分别存入各自的解码缓存228。解码缓存存入数据后立刻使能请求开关分配模块229生成开关分配请求信号。

接下来的操作与普通路由器类似，直到分组通过专用的解码输出端口输出节点。由于有专用的解码输出端口所以开关分配模块不对解码相关的分组仲裁。

基于上述的片上网络路由器，本例还提供一种适用于该片上网络路由器的网络拓扑。

图5为适用于该片上网络的网络拓扑图，包括上子网和下子网，上子网由所有上子路由器相互连接组成，下子网由所有下子路由器相互连接组成；上行子网设有上子纵向链路和上子横向链路，下子网设有下子纵向链路和下子横向链路；上子纵向链路由下向上单向传输，下子纵向链路由上向下单向传输，上子横向链路和所述下子横向链路分别是双向传输；图5中（1）为网络拓扑的整体结构图，（2）为下子网结构图，（3）为上子网结构图。

上子网和下子网均为二维网状网络，且上子网通过分组数据的形式传输上子路由器的数据，下子网通过分组数据的形式传输下子路由器的数据，上下子网拓扑具体为3x3 mesh。上下子网纵向链路各拥有4个虚信道，横向链路各拥有2个虚信道。上下子网本地链路都设定为双向，各子网各拥有一个本地输入链路，各链路拥有2个虚信道，各子网本地输出链路对应其所在子网非本地输入端口各一个，本地输出端口虚信道数目与其所对应的输入端口虚信道数目相等。

本例的网络拓扑的链路中的路由器（2-1）的坐标使用数学坐标形式，即(x,y)标记形式。坐标下面的数字0、1分别代表其属于下子网或上子网，所以图（2）、图（3）中坐标相同的路由器由于其属于不同的子网，所以路由器也不相同。IP核（2-2）亦有坐标，但没有上下子网标号，所以图（2）、图（3）中坐标相同的IP核即为同一个IP核。图（2）、图（3）中的链路（2-3）、（2-4）虽然都为双向链路，但属于不同的子网即为不同的链路，其他双向链路亦是如此。

为防止死锁发生，分组在网络中不能跨子网传输。分组注入网络时根据目的节点选择其占用的子网。

基于上述的网络拓扑，本例还提供一种适用于该网络拓扑的路由算法。

上子纵向链路的路由器和下子纵向链路的路由器分别形成Y维路由，上子横向链路的路由器和下子横向链路的路由器分别形成X维路由；本例的路由算法是基于X-Y维序路由的改进路由算法。若分组数据的源路由与目的路由不在同一维上，则分组数据在结束X维路由的节点的前一节点转向Y维路由，并且在此之前可以根据相邻下游节点虚信道数目自适应路由（不能逆向路由）；Y维路由结束后转向X维完成X维路由。若分组数据的源路由与目的路由在同一维上则无需转向。

按照上述路由算法，分组的路由路径是一个Z字形，所以同时存在X-Y和Y-X转向，在普通的mesh网络中存在死锁环，产生死锁，但是此路由算法应用于本发明的网络拓扑时不存在死锁环，因为本拓扑使用上下子网，纵向链路都为单向链路并且分组不能夸子网传输。

为更详细的描述本发明，下面通过一个具体的实例说明本发明，该实例基于3x3 mesh网络。

该实例发生在图5中的上子网中，一个源节点（节点包括路由器（2-1）和IP核（2-2））00与目的节点01和21通信，另一个源节点20与目的节点01和21通信，两源节点的分组经过上述路由在节点10相遇，继而发生的一系列编解码和路由操作。

源节点生成分组时，分组微片中的所有信息都需要填充准确，如微片类型、编码分组标记、虚信道号（根据虚信道状态合理分配）、目的地址、头微片编号、分组唯一标识符、解码编号等，剩余的就是携带的负载信息。其格式如图2所示。分组携带这些信息就可以正确完成所有操作。其中，分组唯一标识符由4bit源地址和3bit序列号组成。序列号为源节点生成的分组编号。当编号达到最大值时自动归零。3bit序列号相对于小的网络已足够用。由于源节点生成的分组一定不是编码分组，所以解码编号设定为0，编码分组标记设定为0。

两个源节点都会产生两个分支分组沿不同的路径发送到目的节点。源节点00和源节点20的一个分支会分别直接到达目的节点01和21，但是两源节点另外的分支分组会在节点10的路由器中相遇。两分组在此节点满足编码条件，因此下面将发生一系列与本发明有关的编码和路由操作。

图1为具有网络编码功能的片上网络结构图。来自源节点00和20的两分组首先存入上子西输入端口11和上子东输入端口12的缓存中等待处理。输入端口的路由计算模块计算分组的输出端口，同时还译码头微片中携带的目的地址信息。上述信息被送入网络编码模块2中的编码子模块21，编码子模块21按上述的编码工作原理根据该信息进行编码处理，其具体编码过程请参考上述编码子模块21的工作原理的过程，不作赘述；经编码后，在目的路由器生成解码请求，解码子模块22按上述的解码工作原理对编码的分组进行解码处理。

上述的网络拓扑结构和其路由算法能够使本例的片上网络路由器发挥更大的编码特性，通过片上网络路由器的编码功能，实现了分组的压缩，进而增加了网络所传数据携带的信息量，解决了如何达到网络传输容量极限问题。

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