[發(fā)明專利]一種基于片上網(wǎng)絡(luò)的無死鎖路由方法

有效

• 申請?zhí)枺?/td>: 201110321481.2
• 申請日: 2011-10-21
• 公開（公告）號: CN102333038A
• 公開（公告）日: 2012-01-25
• 發(fā)明（設(shè)計(jì)）人: 武鵬;付宇卓;蔣江;劉婷
• 申請（專利權(quán)）人: 上海交通大學(xué)
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 上海思微知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 31237
• 代理人: 鄭瑋

1.一種基于片上網(wǎng)絡(luò)的無死鎖路由方法，其特征在于，所述方法包括如下步驟：

在源節(jié)點(diǎn)將數(shù)據(jù)包復(fù)制n份，其中，n≥3；

在片上網(wǎng)絡(luò)中設(shè)定n條自源節(jié)點(diǎn)至目的節(jié)點(diǎn)的不交叉的通道，n份數(shù)據(jù)包分別在n條通道上傳輸；

n份數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)后再通過表決器得到正確結(jié)果，實(shí)現(xiàn)空間上的冗余。

2.根據(jù)權(quán)利要求1所述的基于片上網(wǎng)絡(luò)的無死鎖路由方法，其特征在于：

在源節(jié)點(diǎn)將數(shù)據(jù)包復(fù)制三份；

在片上網(wǎng)絡(luò)中設(shè)定三條自源節(jié)點(diǎn)至目的節(jié)點(diǎn)的不交叉的通道，三份數(shù)據(jù)包分別在三條通道上傳輸；

三份數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)后再通過表決器得到正確結(jié)果，實(shí)現(xiàn)了空間上的三模冗余。

3.根據(jù)權(quán)利要求2所述的基于片上網(wǎng)絡(luò)的無死鎖路由方法，其特征在于：

在片上網(wǎng)絡(luò)中開設(shè)四條虛通道，其中兩條分別為XY通道和YX通道，另外兩條是紅通道和黑通道；

具有高可靠性要求的數(shù)據(jù)包在源節(jié)點(diǎn)首先拷貝成三份，其中的兩份分別通過XY通道和YX通道向目的節(jié)點(diǎn)發(fā)包；

第三份數(shù)據(jù)包首先通過源節(jié)點(diǎn)的紅通道/黑通道發(fā)送到與前兩條通道不同的相鄰節(jié)點(diǎn)，再通過XY通道/YX通道發(fā)送到距離目的節(jié)點(diǎn)為一的節(jié)點(diǎn)，必須在源節(jié)點(diǎn)與目的節(jié)點(diǎn)組成的矩形區(qū)域以外，保證與另外兩份數(shù)據(jù)包無交叉路徑；再通過黑通道/紅通道發(fā)送到目的節(jié)點(diǎn)。

4.根據(jù)權(quán)利要求3所述的基于片上網(wǎng)絡(luò)的無死鎖路由方法，其特征在于：

如果源節(jié)點(diǎn)是偶節(jié)點(diǎn)則通過黑通道發(fā)送到與前兩條通道不同的相鄰節(jié)點(diǎn)，再通過YX通道發(fā)送到距離目的節(jié)點(diǎn)為一的節(jié)點(diǎn)，必須在源節(jié)點(diǎn)與目的節(jié)點(diǎn)組成的矩形區(qū)域以外，保證與另外兩份數(shù)據(jù)包無交叉路徑；再通過紅通道發(fā)送到目的節(jié)點(diǎn)；

如果源節(jié)點(diǎn)是奇節(jié)點(diǎn)則通過紅通道發(fā)送到與前兩條通道不同的相鄰節(jié)點(diǎn)，再通過XY通道發(fā)送到距離目的節(jié)點(diǎn)為一的節(jié)點(diǎn)，必須在源節(jié)點(diǎn)與目的節(jié)點(diǎn)組成的矩形區(qū)域以外，保證與另外兩份數(shù)據(jù)包無交叉路徑；再通過黑通道發(fā)送到目的節(jié)點(diǎn)。

5.根據(jù)權(quán)利要求4所述的基于片上網(wǎng)絡(luò)的無死鎖路由方法，其特征在于：

所有紅通道都是從奇節(jié)點(diǎn)為源節(jié)點(diǎn)，發(fā)送到偶節(jié)點(diǎn)；紅通道對所有偶節(jié)點(diǎn)來說都是接收通道，對所有奇節(jié)點(diǎn)都是發(fā)出通道；黑通道與之相反。

6.根據(jù)權(quán)利要求4所述的基于片上網(wǎng)絡(luò)的無死鎖路由方法，其特征在于：

所述奇節(jié)點(diǎn)、偶節(jié)點(diǎn)的定義為：將片上網(wǎng)絡(luò)的左下角router節(jié)點(diǎn)的坐標(biāo)定位為(1，1)，向右為X正向，向上為Y正向，將任一router節(jié)點(diǎn)的XY坐標(biāo)相加，如果為奇數(shù)該節(jié)點(diǎn)就是奇節(jié)點(diǎn)，如果該節(jié)點(diǎn)XY坐標(biāo)相加為偶數(shù)就是偶節(jié)點(diǎn)。