網路效用是指分配網路頻寬給網路用戶後用戶的滿意程度。網路效用最最佳化就是設計分配網路資源的方案或算法以使所有網路用戶的總的效用最大並且單個網路用戶的效用也能讓該用戶滿意。
通信網路的可用頻寬是有限的，因此提高對網路資源的利用率，增強網路的穩定性和公平性具有很重要的意義，這個問題就是網路效用最最佳化理論（Network Utility Maximization, NUM提出的背景。該理論由劍橋大學的Frank Kelly[0]教授通過論文提出。 網路效用最最佳化理論巧妙地將網路流的控制與頻寬分配投射進一個統一的最最佳化框架里。這個框架提出在網路的源和連線上進行分散式計算從而解決了網路上受制於容量限制的聚合資源效用最大化的最最佳化問題。作者展示了導出效用最最佳化總的流的速率向量的數學模型和解決方案，然後用數字實例更進一步的解釋了它們。
基本介紹
- 中文名：網路效用最最佳化理論
- 外文名：Network Utility Maximization Theory(NUM)
以下主要介紹網路效用最最佳化理論的研究現狀。
研究現狀
文獻研究傳輸彈性流的通信網路（比如，提供可用位速率服務的ATM 網路）的收費，速率控制和路由的問題。從最大和最小的公平率作為一個特殊的例子，作者描述了一個模型。更一般的，收費用戶準備好去付費進而影響他們的分配率。在模型的首選版本中，一個用戶選擇它將要付的單位時間的費用。其後，根據套用於每單位費用的速率的一個比例公平標準，從而決定用戶的速率。當用戶選擇的費用和網路選擇的分配速率達到平衡，系統的最優狀態就實現了。
文獻分析了針對通信網路的穩定性和公平性的兩種類型速率控制算法。這些算法提供了對簡單的附加遞增或遞減計畫的大規模網路的自然歸納，並且在被一個比例公平準則所描述的系統最佳狀態下達到穩定性。在有一個對整個最佳化問題適當的規劃的條件下，網路的隱含目標函式提供了一個針對由速率控制算法定義的動態系統的Lyapunov函式。網路的最最佳化問題可以投射進原始或對偶形式；這樣很自然的引申出兩類算法。這些算法可以被擁塞指示反饋信號或基於影子價格明確速率所解釋。兩類算法都可以推廣到路由控制和對成比例公平定價提供自然實現。
文獻是網路效用最最佳化理論的奠基之作，其後華中師範大學計算機學院的譚連生教授及其合作者對此理論進行了發展。以下選取他們的論文予以介紹。
文獻的作者將Frank Kelly的網路效用最最佳化模型擴展到雙向流的情形，也就是說，流中的數據包和確認（ACK）共享一個完整的雙向通道。這是一個有趣的推廣。
文獻指出，在無線網路中，為了滿足網路用戶的特殊的服務質量（QoS）要求去分配有限的資源是一個挑戰，特別是當用戶又不同類型的流量要求，比如硬性的Qos流量，最大努力流，彈性的Qos流量。在這篇文獻里，作者研發出了基於效用的資源分配算法。這些算法分為三個方面，1）在硬性的Qos流量與彈性的Qos流量下的資源分配，2）在最大努力流與彈性的Qos流量下的資源分配，3）在硬性的Qos流量，最大努力流與彈性的Qos流量下的資源分配，這些算法是通過使用Karush-Kuhn-Tucker 條件解決網路效用最大化解決的。作者給出了一系列的判定定理去給出同一個框架下發現上述三種情形下的最優解的條件。這些定理之後就擔任這三種算法的設計指南。這些被提出的算法將流量類型，總共的可用的資源以及用戶的信道質量考慮進去。作者評估算法的時間複雜度為為多項式時間並且通過數字例子研究了網路性能。
在文獻中作者研究了在無線網路中的最佳資源分配問題，在這裡所有的流量類型被同一個效用方程描述。這個問題被投射進一個網路效用最最佳化模型中。作者按用戶的效用和流量類型用公式表示出公平指數，然後研究他們的關係。邊際效用遞減原則在經濟學中廣泛使用。在這篇文獻中，作者確立了平等原則和邊際效用遞減原則。通過使用這兩個原則作者發現了對於網路效用最最佳化模型的最優解決方案。這些解決方案分別針對總資源充分和不充分兩種情形。作者提出了一些必要的定理和算法去發現針對以上兩種情形最優方案。
文獻指出，最最佳化理論和非線性規劃方法已經被成功的運用到網際網路去開發高效率的資源分配與擁塞控制方案。在通信網路中的資源分配問題已經被建模成一個最最佳化問題：目標是在服從網路資源限制的條件下去最大化資源綜合效用。然而，對於無線網路，如何分配軟服務質量流量的資源還是一個重要的設計挑戰。從數學角度講，最大的困難來自於網路效用最大化過程中軟服務流量的非凹方程。之前的結果只能找出次優的結果。面對這一挑戰，這篇文獻確立了一些關鍵性的定理去發現最優解。然後提出了一個針對軟服務質量的基於效用分配的完整算法，進而得到最優解。
文獻指出，在網路中的資源分配被投射進網路效用最大化問題中。對於有線網路中的擁塞控制和彈性流量已經有分散式算法用於解決此問題。然而對於無彈性網路包括軟服務質量流量的無線網路的資源分配，這個問題還面臨著挑戰。首先，在無線網路中，對用戶的效用方程建模是很困難的。其次，軟服務質量流量的效用方程通常是非凹的，這樣導致網路效用最最佳化問題在數學上很難解決。在和通常的網路效用最最佳化理論存在偏差的情況下，這篇文獻提出了一個新奇的最最佳化模型，並且它的算法對於頻寬的分配接近在無線網路中用戶對於軟服務質量流量的渴望值。作者的模型利用軟服務流量的基本特徵。換言之，它需要一些優先的頻寬但是在正常的操作中允許一些靈活性。與基於效用的方法和解決方案，我們的方法避免通過使用偏愛的頻寬值為每個用戶找到準確的效用方程表達式的困難。這加速了現實中無線網路的操作。文章用實例核實了提出的模型和算法並且證明它的性能優於網路效用最最佳化理論方法（NUM approach）。
Frank Kelly教授的網路效用最最佳化理論（NUM）問題和解決方法是在滿足連線容量限制的條件下最最佳化綜合效用。它們是使用個體流的速率向量來表述和解決的。由於現有網路的結構，對於網路服務提供者，單個流的速率在路由器里一般上不是直接可測量的。然而，總共的流的速率是很方便獲得和調整的。在這篇文章里，作者研究了通信網路的NUM問題，但是從一個路由層的頻寬分配角度。通過使用廣義逆矩陣，作者提出了一個效用最最佳化路由層頻寬分配的一般模型和它的解決方案。它的目標方程和限制條件使用總的流的速率表示而不是像在NUM問題中使用單一流的速率向量表示。作者發現新提出的模型和Frank Kelly教授提出的NUM模型是等價的,因為它們得到同樣的最優狀態和它們的方案滿足給定的路由計畫.作者也討論了當路由矩陣是滿秩和在網路中每一個連線有一個單跳流的的特殊情形。作者提出了一個對於後者的網際網路基於協定的虛擬網路的直接套用。作者展示了導出效用最最佳化總的流的速率向量的數學模型和解決方案，然後用數字實例更進一步的解釋了它們。
