[發(fā)明專利]一種基于片上網絡中業(yè)務流參數(shù)的交叉沖突預處理方法

有效

• 申請?zhí)枺?/td>: 201410055316.0
• 申請日: 2014-02-18
• 公開（公告）號: CN103812701B
• 公開（公告）日: 2018-03-09
• 發(fā)明（設計）人: 杜高明;王家祥;張多利;宋宇鯤;王春來;王曉蕾
• 申請（專利權）人: 合肥工業(yè)大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;G06F15/78
• 代理公司: 安徽省合肥新安專利代理有限責任公司34101
• 代理人: 何梅生

技術領域

本發(fā)明屬于片上網絡技術應用領域，尤其涉及一種基于片上網絡中業(yè)務流參數(shù)的交叉沖突預處理方法。

背景技術

目前，使用網絡演算理論分析片上網絡性能時，一般將沖突類型分為平行沖突、嵌套沖突和交叉沖突三類。其中交叉沖突的一般處理方法是在交叉點將業(yè)務流切割，轉換為較易處理的平行沖突或嵌套沖突。構成交叉沖突的交叉點有兩個，既有理論允許在任意交叉點切割業(yè)務流。研究發(fā)現(xiàn)，在不同位置切割業(yè)務流，所得的延遲上界有不同的結果。現(xiàn)有的單一切割點算法存在著不能夠有效選擇最佳切割點，計算復雜度高，處理效率低的問題。

因此，發(fā)明一種基于片上網絡中業(yè)務流參數(shù)的交叉沖突預處理方法顯得非常必要。

發(fā)明內容

本發(fā)明的目的在于提供一種基于片上網絡中業(yè)務流參數(shù)的交叉沖突預處理方法，旨在現(xiàn)有的單一切割點算法存在著不能夠有效選擇最佳切割點，計算復雜度高，處理效率低的問題。本發(fā)明是這樣實現(xiàn)的，

本發(fā)明實施例的一種基于片上網絡中業(yè)務流參數(shù)的交叉沖突預處理方法的必要技術方案：

本發(fā)明是這樣實現(xiàn)的，一種基于片上網絡中業(yè)務流參數(shù)的交叉沖突預處理方法包括：

步驟一：進行業(yè)務流標準化；

步驟二：對交叉沖突判斷；

步驟三：對步驟二得出的所有交叉沖突進行預處理判斷；

步驟四：對預處理判斷后進行切割后到達曲線合并；

步驟五：所有切割后的業(yè)務流進行等價服務曲線及延遲上界求解。

本發(fā)明實施例的基于片上網絡中業(yè)務流參數(shù)的交叉沖突預處理方法的次要技術方案：

進一步，在步驟一，根據(jù)目標流TAG_FLOW和沖突流的輸入輸出節(jié)點情況，對業(yè)務流實行標準化表示：假定目標流經過N個節(jié)點，根據(jù)其流經的路由節(jié)點順序，用整數(shù)1到N對路由器序列重新編號。所有流經這N個節(jié)點的沖突業(yè)務流用標準化形式f<a,b>來表示，其中a表示沖突流輸入節(jié)點，b代表沖突流輸出節(jié)點，并求出所有f<a,b>的到達曲線。如沖突流f<1,2>表示該業(yè)務流從節(jié)點1輸入，從節(jié)點2輸出。按照業(yè)務流輸入輸出節(jié)點進行劃分，可以統(tǒng)計得知共有N(N+1)/2種業(yè)務流。標準化過程的結果就是求解每條沖突流f<a,b>在與目標流形成沖突點的到達曲線；

進一步，在步驟二，對交叉沖突判斷，對于存在有交叉沖突的進行步驟三，對沒有存在有交叉沖突的進行步驟五；

進一步，在步驟三，根據(jù)步驟二得出的所有交叉沖突，對每一種交叉情況選擇合適交叉沖突切割點。提出如下判據(jù)：

△D=(b2-b1)/R+b1/(R-r2)-b2/(R-r1)+(b2+r2(T+b1+bt+r1*T+R*T+r1*BT/R+RT*b1/R)/R-(b1+r1(T+BT/R))/R

如果△D>0就將切割點選擇在前端。反之，就將切割點選擇在后端。其中R為片上網絡中路由的服務帶寬，T為服務延遲，RT、r1、r2分別為目標業(yè)務流TAG_FLOW和沖突流f1、f2的平均速率，BT、b1、b2分別為目標業(yè)務流TAG_FLOW和沖突流f1、f2的突發(fā)度；