一種基於多路徑路由的片上網絡業務流拆分方法
2023-05-01 08:28:36 1
一種基於多路徑路由的片上網絡業務流拆分方法
【專利摘要】本發明提供了一種基於多路徑路由的片上網絡業務流拆分方法，通過衝突矩陣，推導出每條目標子業務流的路徑衝突係數，受電阻分流準則啟發，提出電阻非均勻拆分策略，對目標業務流進行拆分，求出目標業務流的延遲上界，相比於基於節點的局部優化，考慮了整條路徑的衝突情況，分配策略參考價值更大，能更準確指導流量分配；相比於均勻全拆分策略，可以根據路徑衝突大小合理分配網絡資源，減小目標業務流的延遲上界，從而優化網絡性能。
【專利說明】一種基於多路徑路由的片上網絡業務流拆分方法
【技術領域】
[0001]本發明屬於網絡通信【技術領域】，尤其涉及一種基於多路徑路由的片上網絡業務流拆分方法。
【背景技術】
[0002]發表於2012 年第八屆 IEEE/ACM/IFIPinternationalconferenceon Hardware/softwarecodesignandsystemsynthesis 國際會議第 123-132 頁的「Worst-caseperformanceanalysisof2-DmeshNoCsusingmult1-pathminimal routing，，論文，提出使用一種基於節點的非均勻拆分策略和基於流的非均勻拆分策略，不足之處是基於節點的非均勻拆分策略只考慮了局部的衝突狀況，判斷依據不全面，容易導致局部擁塞過大；基於流的非均勻拆分策略是通過減小路徑數目，對剩餘路徑進行流量均勻分配，沒有考慮各個路徑不同的衝突環境而進行適量分配。
【發明內容】
[0003]本發明的目的在於提供一種基於多路徑路由的片上網絡業務流拆分方法，旨在解決現有片上網絡業務流拆分方法中存在的局部擁塞、路徑衝突等問題。
[0004]本發明是這樣實現的，一種基於多路徑路由的片上網絡業務流拆分方法，包括以下步驟:
[0005]S1、根據片上網絡的結構類型計算衝突矩陣；
[0006]S2、推導每條目標子業務流的等效衝突電阻，即為路徑衝突係數；
[0007]S3、利用歐姆定律計算每條目標子業務流的數據流量分配比；
[0008]S4、使用電阻非均勻拆分策略對目標業務流進行非均勻拆分；
[0009]S5、根據網絡演算分析方法，結合電阻非均勻拆分策略推導出目標業務流的延遲上界。
[0010]優選地，在步驟SI中，所述片上網絡包括二維(NXN)或三維(NXNXN)的網格結構，其中 N= 1，2，3....。
[0011 ] 優選地，在步驟SI中，所述衝突矩陣，在二維網格結構時，為N2X 4矩陣，行代表路由節點，範圍為(1，N2)，列代表東西南北四個方向，每個元素代表路由節點在東西南北四個方向相鄰路由之間由衝突流產生的節點衝突係數；在三維網格結構時，為N3X6矩陣，行代表路由節點，範圍為(1，N3)，列代表東西南北上下六個方向，每個元素代表路由節點在東西南北上下六個方向相鄰路由之間由衝突流產生的節點衝突係數。
[0012]優選地，在步驟S2中，所述子業務流為通過對業務流進行拆分得到，該拆分具體為:在業務流到達路由節點後按照約定的比例將數據流量分配到不同方向並生成不同的子路徑。
[0013]優選地，在步驟S2中，所述目標子業務流為目標業務流拆分所得到的子業務流。
[0014]優選地，在步驟S2中，所述每條目標子業務流等效衝突電阻，為把目標子流經過的節點在其對應方向上的節點衝突係數加和，記為RiQ = 1，2，...η ;n為目標子業務流數目)，節點衝突係數為(ε r+ iib)p，r和b分別為表示業務流特性的平均轉發速率和突發度，ε和H分別為平均轉發速率和突發度對衝突的貢獻指數，P為鏈路的全局拆分比例。
[0015]優選地，在步驟S3中，所述每條目標子業務流的數據流量分配比，為每條目標子業務流路徑所分配流量的比例，記為Xsubl: Xsub2: Asub3: Asub4:...: Xsubn，根據歐姆定
侓，將上式等效為
【權利要求】
1.一種基於多路徑路由的片上網絡業務流拆分方法，其特徵在於包括以下步驟: 51、根據片上網絡的結構類型計算衝突矩陣； 52、推導每條目標子業務流的等效衝突電阻，即為路徑衝突係數； 53、利用歐姆定律計算每條目標子業務流的數據流量分配比； 54、使用電阻非均勻拆分策略對目標業務流進行非均勻拆分； 55、根據網絡演算分析方法，結合電阻非均勻拆分策略推導出目標業務流的延遲上界。
2.如權利要求1所述的基於多路徑路由的片上網絡業務流拆分方法，其特徵在於，在步驟SI中，所述片上網絡包括二維(NXN)或三維(NXNXN)的網格結構，其中N =1， 2 ， 3....。
3.如權利要求2所述的基於多路徑路由的片上網絡業務流拆分方法，其特徵在於，在步驟SI中，所述衝突矩陣，在二維網格結構時，為N2 X 4矩陣，行代表路由節點，範圍為(1，N2)，列代表東西南北四個方向，每個元素代表路由節點在東西南北四個方向相鄰路由之間由衝突流產生的節點衝突係數；在三維網格結構時，為N3X 6矩陣，行代表路由節點，範圍為(1，N3)，列代表東西南北上下六個方向，每個元素代表路由節點在東西南北上下六個方向相鄰路由之間由衝突流產生的節點衝突係數。
4.如權利要求1所述的基於多路徑路由的片上網絡業務流拆分方法，其特徵在於，在步驟S2中，所述子業務流為通過對業務流進行拆分得到，該拆分具體為:在業務流到達路由節點後按照約定的比例將數據流量分配到不同方向並生成不同的子路徑。
5.如權利要求1所述的基於多路徑路由的片上網絡業務流拆分方法，其特徵在於，在步驟S2中，所述目標子業務流為目標業務流拆分所得到的子業務流。
6.如權利要求4所述的基於多路徑路由的片上網絡業務流拆分方法，其特徵在於，在步驟S2中，所述每條目標子業務流等效衝突電阻，為把目標子流經過的節點在其對應方向上的節點衝突係數加和，記為RiQ = 1，2，...η ;n為目標子業務流數目)，節點衝突係數為(er+ilb)p，r和b分別為表示業務流特性的平均轉發速率和突發度，ε和η分別為平均轉發速率和突發度對衝突的貢獻指數，P為鏈路的全局拆分比例。
7.如權利要求1所述的基於多路徑路由的片上網絡業務流拆分方法，其特徵在於，在步驟S3中，所述每條目標子業務流的數據流量分配比，為每條目標子業務流路徑所分配流量的比例，記為λ subl: λ sub—2: λ sub3: λ sub—4:...: λ sub—n，根據歐姆定律，將上式等效為
8.如權利要求1所述的基於多路徑路由的片上網絡業務流拆分方法，其特徵在於，在步驟S4中，所述業務流，為分析路徑得到的業務流，劃分為目標業務流和衝突業務流，目標業務流定義為所需要研究的對象；衝突業務流定義為對目標業務流造成衝突的業務流。
9.如權利要求6所述的基於多路徑路由的片上網絡業務流拆分方法，其特徵在於，在步驟S4中，所述目標業務流進行非均勻拆分為拆分到第i條目標子業務流的數據流量佔目標業務流總 流量的
10.如權利要求8所述的基於多路徑路由的片上網絡業務流拆分方法，其特徵在於，在步驟S5中，所述網絡演算分析方法為先求得目標子業務流路徑上的等價服務曲線，然後利用最小加代數方法來計算該目標子業務流的延遲上界。
【文檔編號】H04L12/803GK103973585SQ201410204425
【公開日】2014年8月6日 申請日期:2014年5月14日 優先權日:2014年5月14日
【發明者】杜高明, 王春來, 宋宇鯤, 張多利, 李苗, 曹舒婷, 宋平 申請人:合肥工業大學