片上网络通信死锁避免方法、路由器及通信网络

摘要

本发明公开了一种片上网络通信死锁避免方法、路由器及通信网络，通过网络分层的方法来减少网络中多个多播分组发生多播死锁的概率，在单个通信子网内，多播分组最多发往2个输出端口，多播分组间产生多播死锁概率大大降低。另一方面当多播树建立过程中形成死锁时，缓存发生死锁的多播分组，同时改变其他多播分组传输路径为水平方向，促使网络从死锁中恢复过来。本发明具有通信效率较高，且路由器结构简单、设计面积低的优点。

主权项

一种片上通信网络死锁避免方法，其特征在于：定义片上通信网络的规模为N*M的拓扑结构，由N*M个路由器组成；以通信网络左下角路由器为原点，水平向右为x轴正方向，竖直向上为y轴正方向；所述N为通信网络x轴路由器数量，所述M为通信网络y轴路由器数量，其中N和M的取值都是正整数；所述路由器根据其在通信网络中位置的不同使用唯一的标号，所述标号为自然数，从位于原点的路由器开始沿着x轴正方向或者负方向顺序递增，到达边界路由器后沿y轴正方向递增一次后继续在x轴方向递增，到第N*M个路由器结束；所述通信网络由向上通信子网和向下通信子网组成，所述向上通信子网通过分组数据的方式传输通信数据，其中目标路由器的标号大于数据所在路由器的标号；所述向下通信子网通过分组数据的方式传输通信数据，其中目标路由器的标号小于数据所在路由器的标号；所述分组数据由头微片、体微片和尾微片组成，所述头微片表示分组数据开始，包括虚信道号和目标地址,数量为k个，k的取值为正整数；所述体微片表示所需传输的数据载荷；所述尾微片表示分组数据结束；当源路由器接受来自输入端口的分组数据后，从分组数据的头微片中提取目的路由器信息，根据目的路由器标号与源路由器标号的大小判断分组数据要发往的通信子网；在中间路由器，分组数据从输入端口输入后，根据头微片所携带的虚信道号存入相应的虚信道，并且提取目的地址；中间路由器提取目的地址后根据路由算法确定该头微片所在的分组数据要发往的输出端口，从而传输分组数据到达目的地址。