- 學位論文
結合時段配額與優先權為基礎之網際網路用量管理研究
Research on Time-of-day Internet Access Management by Quota-based Priority Control
摘要
在一個免費或固定費率的網路之下，即使採用使用量配額優先控制(Quota-based Priority Control)，仍然有在尖峰時刻網路資源濫用及不公的情形發生。為了針對網路流量在時間軸上的有效管理，本論文研究和分析兩種不同的解決方案：時段差別價位策略(Time-of-day Pricing)和使用量配額排程(Quota Scheduling)。時段差別價位策略是利用虛擬價格去誘導使用者分配一天的使用量配額。使用量配額排程是將一天分成不同時段，而不同時段有不同的配額(Quota)。這種方法可以在尖峰時強制限制使用者的用量。 時段差別價位策略的設計是利用歷史資料去建構使用者對於時間跟價格的配額分配(Quota Allocation)模型。根據過去資料的分析可以發現存在著警慎小心(Prudent)和短視近利(Myopic)的兩種使用者，而這兩種使用者都喜歡在尖峰時刻傳送資料。我們所建構的使用者模型是採用一般性的效用函數(Utility Function)，它掌握了價格如何影響使用者的行為。在效用函數中的喜好度參數(Preference)可以很容易地利用可量測到的使用量去估計。時段差別價位策略的設計可以藉由賽局(Stackelberg Game)去計算出來。數值實驗顯示對尖峰時刻的濫用和不公平而言，時段差別價位策略比純粹採用配額優先控制有很大的改善。時段差別價位策略的方法只需要兩個簡單而且短期的實驗去收集資料。一個是使用量配額優先控制，另一個是對使用者不做任何流量控制。分析結果說明了時段差別價位策略的有效性並可適用於有著常變化的網路環境。 針對使用量配額排程，本論文亦設計了以平衡負荷為基礎的配額排程(Load Balancing-based Quota Scheduling)和以消平尖峰流量為基礎的配額排程(Peak Shaving-based Quota Scheduling)。以平衡負荷為基礎的配額排程設計精神是讓不同時段的網路平均流量相同。這種方法並不需要有關網路流量的歷史資料。然而以消平尖峰流量為基礎的配額排程主要是利用一個以歷史資料建構的簡單使用者模型去消平尖峰時刻的網路流量。這種方法會利用到配額優先控制的實驗數據去建立使用者配額分配模型。 利用在一個超過5000人的運行網路所獲得的歷史資料去評估顯示時段差別價位策略比使用量配額排程在時間軸上的網路流量控制有效。這是因為時段差別價位策略採用一個精細的使用者模型，可以避免在配額更新時候(Quota Renewal)的網路擁塞。比較計算複雜度，時段差別價位策略的設計需要計算一個最佳化的問題(Optimization Problem)，而使用量配額排程只需要簡單的四則運算。然而時段差別價位策略的價格計算時間約只需花一分鐘左右。故選用網路流量控制策略必須根據歷史資料的多寡及流量特性去做有效的選擇。 我們更進一步針對營利性和提供多種傳輸速率服務的網路設計整合計價與頻寬分配的策略去控制使用者流量進而達到網路服務提供者的總利潤最大化。這個整合的設計問題，我們採用柏克萊大學經實驗所建構的使用者需求模型並將網路提供者的設計問題描述成一個非線性規劃的問題。數值結果顯示當價格隨網路流量變化時，頻寬的分配變化十分微小。使用者使用特定服務的需求與其他服務間敏感度是相當高的。此外，在相同的網路資源之下，結果顯示提供較多的服務會帶給網路提供者較多的利潤。
並列摘要
There exists abusive and unfair Internet access during peak hours by users of a free-of-charge or flat-rate network even under a quota-based priority control (QPC). To effectively managing the Internet access over time based on QPC, this thesis studies and analyzes two classes of schemes: time-of-day pricing (TDP) and quota scheduling (QS). TDP is an incentive control method, where users can flexibly allocate the daily quota by virtual price. QS allocates the daily quota to individual time periods to directly and forcedly limit the maximum volume usage of each user during peak hours. The TDP design takes advantage of the empirical data to characterize user demand and quota-allocation behavior with respect to time and pricing. In-depth analyses of empirical data reveal distinctive behavior patterns of myopic and prudent quota allocations over time and both patterns indicate high preference for peak-hour access. The user models adopt general utility functions and capture how pricing affects user behavior as prudent or myopic. Preference parameters of users’ utility over time are then estimated by collecting easily measurable user volumes. The TDP design problem is then formulated and solved as a Stackelberg game. Numerical results shows that the TDP design leads to significant improvements in peak-hour abuse and fairness, peak shaving and load balancing over pure QPC. The methodology of TDP requires only two simple and short-period data collections from an operational network. One is from the network with QPC; the other is from the network without quota control. Results demonstrate the effectiveness of TDP design methodology when applied to Internet access environments with frequent changes. Two QS schemes, load balancing-based quota scheduling (LB-QS) and peak shaving-based quota scheduling (PS-QS), are proposed. LB-QS intends to equalize average traffic over time by proportional quota allocation to time periods of control. There is no empirical data of traffic usage needed for the LB-QS design. PS-QS aims at reducing total traffic of peak hours by utilizing an aggregate empirical data-based user model. This model needs the measurement data collected from a network with QPC to approximate user quota allocation behavior over time. Both QS schemes are compulsive control measures. Performances of TDP and QS are evaluated and compared over the empirical data of a 5000-user network. Results demonstrate TDP significantly outperforms both LB-QS and PS-QS in regulating the Internet access over time. This is because TDP exploits user behavior modeling and pricing to induce user behavior over time, avoiding congestion at the time of quota renewal. As for calculation complexity, the TDP design needs to solve an optimization problem, while the QS design only requires simple mathematical operations. However, the CPU time for TDP calculation takes about 1 minute. Recommendations are given for selecting an effective Internet access scheme based on data availability and traffic pattern over time. We further study how to manage the user traffic over a profitable and multi-service network by designing pricing and bandwidth allocation at the same time. Although pricing and bandwidth allocation of individual services are two important and coupled resource management functions, they are treated separately in most of the literature. In this thesis, we design for a service provider an integrated pricing and bandwidth allocation (IPBA) scheme for a popular network service, where each user is guaranteed with a minimum bandwidth for transmission according to the service class subscribed. Revenue maximization of service provisioning is the service provider’s objective. The design problem is formulated as a nonlinear programming problem. It adopts an empirical user demand model, where a user’s usage time for a service class is a function of prices. Constrained by the total bandwidth limitation, the revenue-maximizing price design induces user demands for individual classes, which in turn determines an optimal allocation of bandwidth. Analyses of the IPBA solution demonstrate that the price increases with traffic intensity while the bandwidth allocation is insensitive to the variation. Results also reveal that when users’ demand for a class is relatively sensitive to the price of other class. Over the same network capacity, the total revenue of offering more than one service classes is higher than that of offering only single service class.