優先權控制及使用量配額排程於網際網路接取管理之研究

Abstract

摘要 在一個免費或相同收費的網際網路接取環境，通常存在網路資源濫用或不公平的頻寬使用。 本論文中，以台灣大學宿舍網際網路接取做為研究平台並基於台大孫雅麗教授之配額限制及差別服務等級概念,而提出了兩個解決方法及其對應之方法論。 首先為使用量配額優先權控制(Quota-based Priority Control， QPC )，目標主要為限制網路頻寬使用之大用戶的濫用以滿足大多數使用者使用網際網路時最基本的頻寬需求。針對頻寬優先權使用，此論文設計了兩種服務。 第一種為一般優先權服務(regular service);即在每個使用量配額控制期間,每個使用者會有一相同的配額(quota),以使用此等級的網路服務,若使用者已經使用完怹的配額則只能使用較低優先權的服務等級，此類稱為監管服務(custody service)，在此等級下，只有當有多餘頻寬時才提供網際網路接取服務。這個方法使用於由台大孫雅麗教授及周怡廷等人所設計開發的實驗系統,其中包含了一台服務品質伺服器( quality of service (QoS) router)，一台量測伺服器(meter reading server)，一台計帳伺服器(accounting server)及一台網頁伺服器(web-based service management server) ，並且這樣的方法使得侵犯使用者隱私及對現有服務的干擾可以降到最低。實驗結果顯示在原有的網路壅塞瓶頸處，降低了48.9%的平均封包遺失率( average packet drop rate)，並且降低了前2%網路使用量大用戶的57.82%網際網路接取之濫用量。然而超過91%的使用者很滿意這個方案並且增加他們的網路傳送量。 這是雙贏的結果，在這個新的方法下使用者付相同的費用下可以得到公平的資源分享。 儘管QPC成功的應用在實際的網路環境下改善了網路頻寬濫用與減輕網路頻寬的壅塞並改善網路頻寬存取的公平性，但是因為QPC並沒有考量到使用者的需求是隨著時間而變化的，因此這些衡量指標在網路尖峰時段時,並不盡理想。所以我們提出了第二個方法，即在QPC下額外加入使用量配額排程(Quota Scheduling)。我們將一天分隔成幾個時段,而所有的使用者在每一個使用量配額控制之時段內,分配到相同數量的配額，但當他們的配額用完後網際網路接取會獲得較低優先權。在一個免費或相同收費的網際網路接取環境，此方法之目標是基於在尖峰時段時減少網路頻寬濫用，減輕壅塞及改善公平性，並引導大用戶於尖峰時刻的用量到離峰使用。我們新設計的方法採用一個以實驗資料為基礎的模型( empirical data-based modeling approach)且包含了下列五項模組(1)前導實驗的進行與分析， (2) 以實驗資料為基礎的使用者模型之建立， (3) 用於改善壅塞集中的配額排程之設計， (4) 藉由電腦模擬,以產生網路品質及使用者使用量的預測，及 (5) 在一超過5000人之運行網路環境下之實驗。使用量配額排程主要為針對使用者行為是隨著時間而改變的現象所設計。從先前之使用者行為之實驗結果及其經濟學特性，我們推導出使用者之需求行為為一雙曲線，這樣的結果對於需求模型是一項創新的發現。藉由結合我們所設計之以壅塞疏解為基礎的資源分配方法與有效頻寬之觀念，我們設計一套新的決定配額排程的方法。如我們所設計的模型之預測結果一般，實驗的結果顯示出與QPC比較下，在網路尖峰時段網路頻寬濫用至少降低了83.2%並且網路頻寬使用的公平性也改善了96.9%。更進一步，伴隨著網路尖峰時段的壅塞改善了32.2%，因此大多數的使用者在尖峰時段網路頻寬的可使用量增加了365.6%。這些結果展示出此設計方法論於免費或相同收費之網際網路接取管理環境下有實用之潛力、有效之控制及適應於使用者多變等特性。

Abstract In a best effort and free of charge or flat-rate Internet access environment, there often exists abusive and unfair usage of network resources. In this thesis, the Internet access by the dormitory users at the National Taiwan University (NTU) serves as a conveyer problem for studying the design methodology to reduce abuse and improve fairness. Although several current network management tools, such as Cisco P-Cube and Packeteer Packet-Shaper, are popular in LAN environments for Internet access management, they are not only costly in installation and maintenance, but also need additional design methodology for effective operation. These deficiencies will be systematically addressed in this thesis. Based a conceptual framework of quota limitation and priority differentiation, two Internet access control schemes and their corresponding design methodologies are proposed. First, a quota-based priority control (QPC) is developed to resolve the problem of unfair and abusive Internet access encountered in the NTU dormitory networks. The goal is to meet the basic traffic demands of the majority users while limiting abusive usage from ignorant heavy users. Two classes of services are provisioned. The regular class sets a quota on each user’s traffic volume per quota control period. Out-of-profile or possibly abusive traffic is directed to a lower priority service class called the custody service and served when there is an excess bandwidth. The new policy and schemes are implemented on a quality of service (QoS) router, a meter reading server, an accounting server and a web-based service management server with minimal intrusion of user privacy and least disturbance to the existing service offering. The QoS router was designed and implemented by Sun et al, 2000, and the other servers were designed and implemented by Chou et al, 2001. The experimental results show that the original congestion at the bottleneck link was alleviated with a 48.9% reduction of the average packet drop rate. Abusive Internet access by the top 2% heavy users is greatly reduced by 57.82%. Astonishingly, over 91% users are pleased with this new policy and their network usages all increase. This is a win-win result. Under the new policy and implementation, users paying the same amount of service fee are now able to fairly share resources. Despite the aforementioned successful application of the QPC scheme, its peak-hour performance is unsatisfactory because it does not take the temporal variation of user demands into consideration. We then presents a design methodology for QPC with quota scheduling (QPC/QS) for time-of-the-day Internet access management. All users are given the same quota during each period in a day for regular access of the Internet and may still access at a lower priority when their quota has run out. The goals lie in reducing abuse, alleviating congestion and improving fairness of Internet access during peak hours over a free-of-charge or flat-rate network by exploiting existing network management tools. The quota scheduling scheme aims at inducing part of heavy user’s need from peak hours to off-peak hours. Our design methodology adopts an empirical data-based modeling approach and consists of the following five modules: 1] conduction of pilot experiment, a simple case of quota scheduling, 2] construction of the user demand model, 3] design of the quota scheduling scheme for smoothing congestion, 4] prediction of network performance and user usages through Monte Carlo simulation and 5] validation by an experiment over a 5000-user production network. Core to this Internet access management is the characterization of user demands with respect to time of day. By exploiting the empirical data and economic properties of user behavior, we model individual user’s volume of transmission as a hyperbolic function of quota. By combining a congestion-based resource allocation approach with a notation of effective bandwidth, a scheduling scheme is designed to determine the quota value for each period. Experimental results, consistent with the prediction by simulation, show that compared to QPC without quota scheduling, the heavy users’ abuse is reduced by at least 83.2% and the peak-hour congestion is improved by at least 32.2%. Therefore, the peak-hour traffic volume generated by majority of users is increased by 365.6%. The fairness is improved by at least 96.9% during peak hours. These results demonstrate the effectiveness of the design methodology and the potential of the control scheme for Internet access management over free-of-charge or flat-rate networks. Moreover, our methodology is easily implemented, complementary to emerging network management tools and may cope with network environment changes.