[發(fā)明專利]一種高性能網(wǎng)絡(luò)中多條可變路徑固定帶寬的調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201810193491.4
• 申請日: 2018-03-09
• 公開（公告）號: CN108600098B
• 公開（公告）日: 2020-09-04
• 發(fā)明（設(shè)計）人: 侯愛琴;吳奇石;房鼎益;王濤;張曉陽;王永強
• 申請（專利權(quán)）人: 西北大學(xué)
• 主分類號: H04L12/709
• 分類號: H04L12/709;H04L12/917;H04L12/801
• 代理公司: 西安恒泰知識產(chǎn)權(quán)代理事務(wù)所 61216
• 代理人: 李婷;周春霞

1.一種高性能網(wǎng)絡(luò)中多條可變路徑固定帶寬的調(diào)度方法，其特征在于，該方法根據(jù)用戶請求，選擇使數(shù)據(jù)傳輸結(jié)束時間最早的路徑集p₁＝{p₁(P),...p₁(i),...p₁(Q)}和路徑集p₂＝{p₂(P),...p₂(i),...p₂(Q)}，將數(shù)據(jù)大小為δ的數(shù)據(jù)由源節(jié)點v_s傳輸?shù)侥康墓?jié)點v_d；其中，p₁(i)表示路徑集p₁中第i個時隙下的路徑，p₂(i)表示路徑集p₂中第i個時隙下的路徑，P表示數(shù)據(jù)傳輸?shù)拈_始時隙，Q表示數(shù)據(jù)傳輸?shù)慕Y(jié)束時隙；

所述的選擇使數(shù)據(jù)傳輸結(jié)束時間最早的路徑集p₁＝{p₁(P),...p₁(i),...p₁(Q)}和路徑集p₂＝{p₂(P),...p₂(i),...p₂(Q)}，采用的方法如下：

(1)忽略路徑切換時延的情況

步驟1,數(shù)據(jù)傳輸結(jié)束時隙為q，q的起始值為0；利用Dijkstra算法找到源節(jié)點到目的節(jié)點之間的，在第q時隙帶寬最大和次大的兩條路徑p₁[q]和p₂[q]，路徑p₁[q]和p₂[q]節(jié)點不相交，該兩條路徑p₁[q]和p₂[q]的帶寬分別為β₁[q]和β₂[q]；

步驟2，數(shù)據(jù)傳輸開始時隙為p，0≤p≤q，p的起始值為0；判斷數(shù)據(jù)大小為δ的數(shù)據(jù)能否在第q時隙傳輸結(jié)束，若(β₁+β₂)·(t[q+1]-t[p])≥δ，其中，β₁＝min(β₁[p],β₁[p+1],...β₁[q])，β₂＝min(β₂[p],β₂[p+1],...β₂[q])，t[p]表示第p時隙的開始時刻，t[q+1]表示第q時隙的結(jié)束時刻，則數(shù)據(jù)能夠在第q時隙傳輸結(jié)束，執(zhí)行步驟3；否則，q的值加1，返回步驟1；

步驟3，計算完成時刻t_end＝t[p]+δ/β，其中，β＝β₁+β₂，β為時間段(t[p],t[q+1])內(nèi)數(shù)據(jù)傳輸?shù)膸捴停粚鬏旈_始時隙p的值加1，并返回步驟2，直至p＝q；所有計算得到的t_end中的最小值對應(yīng)的q的值即為數(shù)據(jù)傳輸結(jié)束時隙Q，對應(yīng)的p的值即為數(shù)據(jù)傳輸開始時隙P；第P時隙到第Q時隙之間，每個時隙中選擇出的帶寬最大的路徑形成路徑集p₁，每個時隙中選擇出的帶寬次大的路徑形成路徑集p₂；

(2)不忽略路徑切換時延的情況

步驟1，利用Dijkstra算法找到源節(jié)點到目的節(jié)點之間的，在每個時隙帶寬最大的路徑，所有路徑形成路徑集p₁'＝{p₁'(0),p₁'(1),...p₁'(i)...p₁'(T-1)},其中，p₁'(i)表示在第i個時隙找到的帶寬最大的路徑，T表示時隙總數(shù)，路徑p₁'(i)的帶寬用β₁(i)表示；

步驟2，數(shù)據(jù)傳輸結(jié)束時隙為q，0≤q≤T-1，q的初始值為0；

步驟3，數(shù)據(jù)傳輸開始時隙為p，0≤p≤q，p的初始值為0；找到路徑集p₁'中在[p,q]時隙區(qū)間內(nèi)的路徑的切換次數(shù)k₁，并得到更新后的[p,q]時隙區(qū)間內(nèi)的每個時隙下的路徑，所有路徑形成路徑集p₁″；

步驟4，采用Dijkstra算法找到源節(jié)點到目的節(jié)點之間的，在每個時隙與路徑集p₁′的路徑不相交的帶寬最大的路徑，所有路徑形成路徑集p₂′；

步驟5，找到路徑集p₂'中在[p,q]時隙區(qū)間內(nèi)的路徑的切換次數(shù)k₂，以及得到更新后的[p,q]時隙區(qū)間內(nèi)的每個時隙下的路徑,所有路徑形成路徑集p₂″；

步驟6，若路徑集p₁″和路徑集p₂”的最大并行傳輸數(shù)據(jù)量D≥δ,D＝β″₁[p,q]·((t[q]-t[p])-τ·k₁)+β″₂[p,q]·((t[q]-t[p])-τ·k₂)，其中，β₁″[p,q]為路徑集p₁″中的路徑的最大帶寬，β₁″[p,q]＝min(β₁″[p],...β₁″[q])，β₁″[p]為路徑集p₁″中第p時隙的路徑的帶寬，β₁″[q]為路徑集p₁″中第q時隙的路徑的帶寬，β₂″[p,q]為路徑集p₂'中的路徑的最大帶寬，β₂″[p,q]＝min(β₂″[p],...β₂″[q])，β₂″[p]為路徑集p₂″中第p時隙的路徑的帶寬，β₂″[q]為路徑集p₂″中第q時隙的路徑的帶寬，τ為路徑切換時延，t[p]表示第p時隙的開始時刻，t[q]表示第q時隙的開始時刻，則執(zhí)行步驟7，否則，將q的值增加1，執(zhí)行步驟2；

步驟7，計算完成時刻t_end＝t[q]+δ'/β”；δ'為在t[q]時刻剩余數(shù)據(jù)量,δ'＝δ-D；β”＝β₁″[p,q]+β₂″[p,q]；將p的值增加1，返回步驟3，直至p＝q；所有計算得到的t_end中的最小值對應(yīng)的路徑集p₁″和路徑集p₂″即為選擇出的路徑集p₁和路徑集p₂。