[發(fā)明專利]一種傳輸時延最小化的中繼多路徑流量分配方法

有效

• 申請?zhí)枺?/td>: 201810783246.9
• 申請日: 2018-07-17
• 公開（公告）號: CN108989148B
• 公開（公告）日: 2020-07-21
• 發(fā)明（設(shè)計）人: 謝磊;陳惠芳;傅林捷
• 申請（專利權(quán)）人: 浙江大學(xué)
• 主分類號: H04L12/26
• 分類號: H04L12/26;H04L12/707;H04L12/721;H04L12/751;H04L12/801
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 忻明年

1.一種傳輸時延最小化的中繼多路徑流量分配方法，其特征在于該方法具體步驟如下：

步驟1.信息收集：

監(jiān)測網(wǎng)絡(luò)流量，收集并估計鏈路信息；根據(jù)收集到的鏈路信息，生成從源節(jié)點經(jīng)過匯聚節(jié)點到目的節(jié)點的路徑集合；

把網(wǎng)絡(luò)看作有向圖G＝(V,E)，其中表示節(jié)點的集合，E＝{e_ij}，表示節(jié)點間鏈路的集合；s表示源節(jié)點，d表示目的節(jié)點，n_ij表示第i條路徑上第j個網(wǎng)絡(luò)節(jié)點,N表示一般網(wǎng)絡(luò)節(jié)點的集合，e_ij表示第i條路徑上第j條網(wǎng)絡(luò)鏈路；源節(jié)點s和目的節(jié)點d之間的簡單無循環(huán)可用路徑集合為P，P＝{P₁,P₂,...,P_K}，K為路徑數(shù)；

步驟2.路徑拆分：

將源節(jié)點s到目的節(jié)點d的路徑根據(jù)匯聚節(jié)點c拆分成多個部分，并重新定義各個部分的邏輯路徑集合，P＝{P′:P″:...}＝{(P′₁,P′₂,P′₃,P′₄,...):(P″₁,P″₂,...):...}，其中P′表示拆分后的第一個邏輯路徑集合，P″表示拆分后的第二個邏輯路徑集合，P_i′＝{e′_i1,e′_i2,...}，P_i″＝{e″_i1,e″_i2,...}表示第i條路徑上各節(jié)點間的相互獨立鏈路,e′_i1表示第一個邏輯路徑集合中，第i條路徑上的第一條鏈路,e″_i1表示第二個邏輯路徑集合中，第i條路徑上的第一條鏈路；

步驟3.網(wǎng)絡(luò)路徑建模：

選取一個邏輯路徑集合，獲取并更新路徑網(wǎng)絡(luò)參數(shù)：路徑P_i上的丟包率表示鏈路e_ij上的丟包率，最大可用帶寬a_i，平均傳輸速率r_i，定義路徑P_i上的傳輸可用帶寬w_i＝r_i+a_i；定義路徑P_i上的趨勢帶寬為當前時刻t與前q個時刻傳輸可用帶寬變化趨勢的預(yù)測值：其中參數(shù)φ₁,φ₂,φ₃...,φ_q為自回歸系數(shù)，ε_t為相互獨立的白噪聲序列；

步驟4.質(zhì)量評估：

根據(jù)路徑P_i上的傳輸可用帶寬w_i，丟包率p_i，結(jié)合時間序列模型，計算質(zhì)量評估后的評估帶寬：其中和θ為加權(quán)系數(shù)，分別表示丟包率權(quán)重與趨勢帶寬權(quán)重，0＜θ＜1，滿足

步驟5.傳輸流量分配：

所有數(shù)據(jù)分組到達的發(fā)送端的平均速率為λ分組/秒，到達源節(jié)點后，發(fā)送端將數(shù)據(jù)分組分配到K條路徑上傳輸；每個數(shù)據(jù)分組以概率γ_i分配到第i條路徑上，被請求的數(shù)據(jù)分組以速率γ_iλ到達路徑P_i進行發(fā)送；

步驟6.計算路徑P_i的排隊時延，求解時延最小的流量分配：

根據(jù)排隊論，給出路徑P_i的平均傳輸時延：源節(jié)點在P_i上發(fā)送數(shù)據(jù)分組的平均時間構(gòu)建傳輸時延最小的流量分配問題，并求解最優(yōu)化流量分配向量γ＝(γ₁,γ₂,...,γ_K)；λ_i表示分配到第i條路徑的速率，表示第i條路徑上的評估帶寬，pd_i表示第i條路徑上的傳播時延；

約束條件C2是對數(shù)據(jù)分組分配的規(guī)范性和非負性要求；

定義拉格朗日函數(shù)μ、v、α為拉格朗日乘子，根據(jù)KKT條件求解：

其中m為路徑集合中被選取進行流量分配的路徑數(shù)目，各條路徑上分配的流量為：

步驟7.若各條路徑的傳播時延差小于設(shè)定時間，視為傳播時延相近，進入步驟8；若各條路徑的傳播時延差大于等于設(shè)定時間，視為傳播時延相差較大，進入步驟9；所述的設(shè)定時間為3～8毫秒；

步驟8.各條路徑子流的傳播時延相近，求解流量分配的閉式解：

進入步驟10；

步驟9.采用二分搜索，確定搜索的上下界，求α近似解得到流量分配結(jié)果，具體如下：

步驟9.1.設(shè)置搜索精度σ，確定二分搜索的上下界：

步驟9.2.更新二分搜索的中間值

步驟9.3.計算判決：

若調(diào)整搜索下界，返回步驟9.2；若調(diào)整二分搜索的上界，返回步驟9.2；若求得精度為σ下的近似解

步驟9.4.將求得的代入得到流量分配結(jié)果：

步驟10.若存在未進行流量分配的邏輯路徑集合，則對下一個邏輯路徑集合進行流量分配，進入步驟3；否則，進入步驟11；

步驟11.耦合流量分配結(jié)果：

對各部分流量分配結(jié)果進行耦合，生成源節(jié)點到目的節(jié)點的傳輸路徑P＝{P′:P″:...}和流量分配結(jié)果，進行數(shù)據(jù)發(fā)送；若發(fā)送完成后有新的數(shù)據(jù)分組到達，進入步驟3，對新一輪數(shù)據(jù)傳輸進行傳輸時延最小的中繼多路徑流量分配；否則，結(jié)束并退出。