非對稱時槽化網路上基於統計的最佳化上行頻寬管理

Abstract

混合式光纖同軸 (HFC) 網路因為具備高頻寬以及普及的基礎建設，在未來的網際網路中扮演相當重要的角色，也因此制定了存取這種網路的技術標準。但是，標準制定的目的是讓不同廠商的設備能夠溝通，並沒有對系統的效能有特別考量，因此有許多效能提昇的空間可發揮。本篇論文目的是最佳化上行頻寬的使用，其中提出的概念甚至做法，可以適用於區域多點分散式系統 (LMDS)、IEEE 802.16、以及衛星網路等非對稱時槽化網路上。 本論文包含四個部分 : 首先，對HFC網路的兩個主要的 MAC協定標準DOCSIS及IEEE802.14做深入的探討與比較，並點出可研究的議題 ; 接著，分別針對測距區域及要求競爭區域提出基於統計的最佳化頻寬分配方法，使得這些區域的時槽流通率最高 ; 這兩個頻寬分配方法觀念是一樣的，先根據競爭碰撞的結果並查詢一個事先建立的最大可能性要求數(MLR)表格，推測出競爭要求數，然後採納ALOHA最大流通率分析的結論，作為最佳的配置策略，使得最佳流通率能趨近理論最佳值 ; 最後，針對資料傳送區域，設計一個兩階段時槽排程演算法，由服務品質參數所推導出的全域成本值作為時槽選取的參考值，時槽排程的結果若對其他資料流的時槽選取阻礙越低，則該時槽可越早排程，此演算法使得資料流的服務品質得到保障，並有效降低服務品質違背率。

The Hybrid Fiber Coax (HFC) networks play essential role in the Internet due to its high bandwidth and prevalence; therefore, standards are developed to facilitate interoperability between cable modems and headends designed by different vendors. However, there are rooms for developers to design sophisticated approaches to utilize the bandwidth efficiently. This study proposed algorithms for improving system performance in terms of bandwidth throughput and QoS violation rate. These approaches can also be applied to any asymmetric bi-directional slotted networks, such as Local Multipoint Distributed System (LMDS), IEEE 802.16, and satellite networks. This thesis consists of four parts: (I) an investigation into HFC MAC protocols, (II) an optimal ranging algorithm to allocate right size of ranging area, (III) a statistically-based approach to allocate right size of request contention area according to the pattern of contention result, and (IV) a two-phase scheduling algorithm to meet the QoS requirement of each flow as well as reduce the QoS violation rate. First of all, this thesis comprehensively reviews two HFC MAC protocols, Data-Over-Cable Service Interface Specifications (DOCSIS) and IEEE 802.14a. Research issues are also identified. Then, we propose statistically optimized ranging area (SORA) algorithm to determine the optimal random delay to minimize the average cycle time of the ranging process. Regarding to the request contention area, we proposes a statistically optimized minislot allocation (SOMA) algorithm to optimize minislot throughput. A time proportional scheme is adopted to estimate the number of new requests in the initial resolution process, and the number of retry requests in the collision resolution process is estimated by looking up a pre-determined table of the most likely number of requests (MLR). For data transmission area, we present a two-phase minislot scheduling algorithm to reduce the QoS violation rate. In the scheduling sequence determination phase, the flow whose packets are most unlikely to violate QoS is scheduled first. Then, in the minislot assignment phase, the scheduler allocates to a flow the available interval where the likelihood of packet violation is minimum. 1.1 Previous Studies 1.1.1 Performance investigation 1.1.2 Allocating request minislots 1.1.3 Scheduling data minislots 1.1.4 Other issues 1.2 Research Issues 2. HFC MAC Protocols Investigation 2.1 Standards 2.2 Overview of DOCSIS and IEEE 802.14a Protocols 2.2.1 Physical features 2.2.2 MAC operation 2.3 Mechanisms 2.3.1 Upstream as a stream of minislots 2.3.2 Upstream bandwidth management 2.3.3 Virtual queue 2.3.4 Downstream MPEG-2 format 2.3.5 Transport mechanisms 2.3.6 Access modes 2.3.7 QoS support 2.4 Algorithms 2.4.1 Data-link-layer security 2.4.2 Ranging 2.4.3 Collision resolution 2.5 Summary 3. Ranging Minislots Allocation 3.1 Problem Statement 3.2 Statistically Optimized Ranging Area 3.2.1 Optimal allocation policy 3.2.2 Collision estimation 3.2.3 Algorithm summary 3.3 Numerical Results 3.3.1 Throughput 3.3.2 Sensitivity analysis 3.4 Summary 4. Request Minislot Allocation 4.1 Problem Statement 4.2 Statistically Optimized Minislot Allocation 4.2.1 Motivation 4.2.2 Initial estimation - time proportional 4.2.3 Collision estimation - MLR-based 4.2.4 Algorithm summary 4.2.5 Relaxed SOMA 4.3 Throughput Analysis 4.3.1 Analysis model 4.3.2 Minislot throughput for initial resolution 4.3.3 Minislot throughput for collision resolution 4.4 Numerical Results 4.4.1 Models 4.4.2 Simulation results 4.4.3 Analysis results 4.4.4 Discussion 4.5 Implementation Issues in IEEE 802.14a 4.6 Interleaving Collision Resolution Engines 4.6.1 Problem statement 4.6.2 Analysis work 4.6.3 Numerical results 4.7 Summary 5. Data Minislots Scheduling 5.1 DOCSIS v1.1 Upstream Scheduling Services 5.1.1 Unsolicited grant service (UGS) 5.1.2 Real time polling service (rtPS) 5.1.3 Unsolicited grant service with activity detection (UGS-AD) 5.1.4 Non real time polling service (nrtPS) 5.1.5 Best effort (BE) 5.2 Problem Statement 5.2.1 Motivation 5.2.2 Satisfying region 5.2.3 QoS violation 5.3 Two-Phase Minislot Scheduling Algorithm 5.3.1 Minislot cost setup 5.3.2 Scheduling sequence determination phase 5.3.3 Minislot assignment phase 5.3.4 Algorithm summary 5.4 Simulation Results 5.4.1 Models 5.4.2 Numerical results 5.5 Summary 6. Conclusion