[發(fā)明專利]一種集中式的多路徑效用公平帶寬分配方法

有效

• 申請?zhí)枺?/td>: 202011054508.1
• 申請日: 2020-09-29
• 公開（公告）號: CN112422455B
• 公開（公告）日: 2023-05-23
• 發(fā)明（設(shè)計）人: 鄭嘉琦;余浩宇;陳貴海
• 申請（專利權(quán)）人: 南京大學(xué)
• 主分類號: H04L47/78
• 分類號: H04L47/78;H04L47/80
• 代理公司: 南京鐘山專利代理有限公司 32252
• 代理人: 陳月菊

本發(fā)明公開了一種集中式的多路徑效用公平帶寬分配方法，包括：為每個用戶/應(yīng)用指定分段線性效用函數(shù)；結(jié)合分段線性效用函數(shù)，采用預(yù)設(shè)的分段最大最小規(guī)劃算法計算得到一個部分分配方案；計算得到初始劃分，將該初始劃分作為輸入，不斷迭代執(zhí)行預(yù)設(shè)的效用迭代填水算法，每輪迭代產(chǎn)生一個新的分配方案，直至連續(xù)兩輪產(chǎn)生的分配方案的差別小于既定閾值時，停止迭代，返回當(dāng)前輪的分配結(jié)果作為最終的分配方案。本發(fā)明能夠在保證部分最大最小公平性的同時，有效地降低帶寬分配方案計算時間，并且可以在公平性和計算時間兩者之間做靈活取舍。

技術(shù)領(lǐng)域

本發(fā)明涉及通信網(wǎng)絡(luò)資源分配技術(shù)領(lǐng)域，具體而言涉及一種集中式的多路徑效用公平帶寬分配方法。

背景技術(shù)

帶寬分配研究如何將有限的網(wǎng)絡(luò)帶寬資源分配給多個網(wǎng)絡(luò)用戶。隨著網(wǎng)絡(luò)基礎(chǔ)設(shè)施的發(fā)展，越來越多的網(wǎng)絡(luò)能夠提供多條路徑供單個用戶使用?，F(xiàn)如今一個越來越常見的需求是把多個不同源點和匯點的流看作一個整體進(jìn)行資源的分配與調(diào)度。因此，一個成熟的帶寬分配方案需要將多路徑考慮在內(nèi)。除此之外，共享網(wǎng)絡(luò)的用戶/應(yīng)用多種多樣，文件備份軟件、視頻播放軟件等常常共享同樣的通信網(wǎng)絡(luò)，不同類型的應(yīng)用對帶寬的需求、對帶寬變化的敏感程度存在顯著差異。因此，將網(wǎng)絡(luò)資源進(jìn)行絕對平等的分配是不可取的，在分配帶寬時，應(yīng)該綜合考慮不同應(yīng)用對帶寬的需求。

帶寬分配需要兼顧效率與公平性，一方面，我們需要最大化某個全局指標(biāo)，一方面，我們不希望因此犧牲部分用戶。為了平衡這兩者，網(wǎng)絡(luò)領(lǐng)域的研究者們提出了許多實用的公平性概念。被廣泛實用的公平性概念包括，比例公平性、阿爾法公平性和最大最小公平性，其中最大最小公平性被普遍認(rèn)為是最公平的標(biāo)準(zhǔn)。然而，當(dāng)涉及到多路徑帶寬分配時，傳統(tǒng)的最大最小公平的分配方案的計算需要迭代地求解大量線性規(guī)劃，因而需要的計算時間極長。在用戶需求或是拓?fù)洳粩嘧兓木W(wǎng)絡(luò)當(dāng)中，難以根據(jù)實時的信息及時調(diào)整帶寬分配方案，從而得到次優(yōu)的表現(xiàn)。

為了降低多路徑最大最小公平性帶寬分配方案的計算復(fù)雜度，一些研究者主張放松對最大最小公平性的要求，得到“局部”最大最小公平的結(jié)果，一些研究者提出了在特定拓?fù)湎驴焖偾蠼獾姆桨?。然而，前者缺乏放松后的解與最優(yōu)解之間差距的保證，后者不適用于一般的網(wǎng)絡(luò)拓?fù)?。在向多路徑最大最小公平帶寬分配問題中引入對效用函數(shù)的考慮之后，帶寬分配問題變得更加復(fù)雜，計算復(fù)雜度進(jìn)一步上升，如何減少多路徑效用公平帶寬分配方案的計算時間是一個迫在眉睫的問題。一般的效用函數(shù)的數(shù)學(xué)性質(zhì)可能不好，難以甚至不可能求解，一些研究者使用分段線性函數(shù)來擬合一般的效用函數(shù)，這也是本發(fā)明對一般的效用函數(shù)的處理方法，一些研究者利用二分搜索獲取對最優(yōu)分配方案的近似，這類方法算法復(fù)雜度更高，而且缺乏靈活性。

發(fā)明內(nèi)容

本發(fā)明針對現(xiàn)有技術(shù)中的多路徑效用公平帶寬分配方案計算復(fù)雜度高的問題，提供一種集中式的多路徑效用公平帶寬分配方法，能夠在保證部分最大最小公平性的同時，有效地降低帶寬分配方案計算時間，并且可以在公平性和計算時間兩者之間做靈活取舍。

為實現(xiàn)上述目的，本發(fā)明采用以下技術(shù)方案：

一種集中式的多路徑效用公平帶寬分配方法，所述分配方法包括以下步驟：

S1，為每個用戶/應(yīng)用指定分段線性效用函數(shù)；

S2，結(jié)合分段線性效用函數(shù)，采用預(yù)設(shè)的分段最大最小規(guī)劃算法計算得到一個部分分配方案，在所述部分分配方案中，分到帶寬最少的k％的用戶獲得的帶寬是最大最小公平的，其余的用戶獲得的帶寬不少于這k％用戶中單個用戶分到的最大帶寬，其中，k大于等于0小于等于100，且動態(tài)可調(diào)；

S3，結(jié)合步驟S2得到的部分分配方案，計算得到初始劃分，劃分是指同一用戶使用的多條路徑中，各條路徑上分配到的帶寬占總帶寬的比例；將該初始劃分作為輸入，不斷迭代執(zhí)行預(yù)設(shè)的效用迭代填水算法，每輪迭代產(chǎn)生一個新的分配方案，直至連續(xù)兩輪產(chǎn)生的分配方案的差別小于既定閾值時，停止迭代，返回當(dāng)前輪的分配結(jié)果作為最終的分配方案。

為優(yōu)化上述技術(shù)方案，采取的具體措施還包括：