臺灣博碩士論文加值系統

在混合式光纖同軸電纜（HFC）網路的DOCSIS1.1標準中，定義了五種基本的上傳頻道服務類型（upstream service）來支援個別資料流的品質服務（QoS）。頭端必須根據各個資料流的品質服務參數定期提供適當的上傳機會給各個資料流（Service flow）。然而，當數個資料流需要同一塊頻寬來傳輸時，頭端可能無法滿足每一個資料流的需求，有部分的封包就會在這種狀況下遭到丟棄。因此，在本論文中，我們提出一個兩階段的迷你時槽排程演算法來降低上述違反品質參數的現象，這個演算法包括兩個階段：第一個階段決定排程順序，愈有可能發生違反品質參數的資料流優先進行排程；第二個階段是指定迷你時槽給資料流，原則上優先選擇最不可能發生違反品質參數的區間，以期降低各資料流間的需求衝突。經過我們模擬的結果，與傳統先到先服務且隨機選取迷你時槽的演算法比較，兩階段迷你時槽排程演算法最多可以降低70%的違反品質參數發生率。兩階段迷你時槽演算法能夠運作在DOCSIS1.1架構下的混合式光纖同軸電纜網路。

Data-Over-Cable Service Interface Specifications v1.1 (DOCSIS1.1), developed for data transmission over the Hybrid Fiber Coaxial (HFC) networks, defines five upstream services to support per-flow Quality of Services (QoS). The cable modem termination system (CMTS) has to periodically grant, based on the QoS parameters, upstream transmission opportunities to the QoS flows. However, packets may be dropped while several flows demand the same interval for transmission. In this paper, we propose the two-phase, the scheduling sequence determination phase and the minislot assignment phase, minislots scheduling algorithm to reduce the QoS violation rate. In the scheduling sequence determination phase, the flow whose packets are with the highest probability of being dropped is scheduled first. Then, in the minislot assignment phase, the scheduler allocates the interval with minimal probability of QoS violation. The simulation results demonstrate that our scheduling algorithm can reduce QoS violation rate up to 70% compared with first-come-first-serve-random-selection algorithm. The two-phase minislots scheduling algorithm can work within the framework of DOCSIS1.1 standard.

1 Introduction 1
2 DOCSIS1.1 Overview 3
2.1 DOCSIS MAC protocol 3
2.1.1 Minislot 3
2.1.2 Service Flow 3
2.1.3 MAC Operation 3
2.2 DOCSIS1.1 Upstream Scheduling Services 5
2.2.1 Unsolicited Grant Service (UGS) 5
2.2.2 Real Time Polling Service (rtPS) 6
2.2.3 Unsolicited Grant Service with Activity Detection (UGS-AD) 7
2.2.4 Non Real Time Polling Service (nrtPS) 8
2.2.5 Best Effort (BE) 8
3 Two-phase Minislots Scheduling Algorithm 10
3.1 Motivation 10
3.2 Satisfying Region 10
3.3 QoS violation 13
3.4 Minislot Cost Evaluation 15
3.5 Scheduling Sequence Determination Phase 16
3.6 Minislots Assignment Phase 17
3.7 Algorithm Summary 18
3.8 Example 19
4 Simulation Results 21
4.1 Models 21
4.2 Numerical Results 22
4.2.1 QoS Load 22
4.2.2 Number of Supported Flow 23
4.2.3 Phase Improvement 24
4.2.4 Packet Interarrival Time 26
4.2.5 Tolerated Jitter 27
5 Conclusions 29
References 31

[1] Cable Television Laboratories, Inc., Data-Over-Cable Service Interface Specifications─Radio Frequency Interface Specification v1.1, July 1999.
[2] Ying-Dar Lin, Chen-Yu Huang, and Wei-Ming Yin, “Allocation and scheduling algorithms for IEEE802.14 and MCNS in hybrid fiber coaxial networks,” IEEE Transactions on Broadcasting, vol. 44, no. 4, pp. 427-435, Dec. 1998.
[3] N. Golmie, F. Mouveaux, and D. Su, “A Comparison of MAC Protocols for Hybrid Fiber/Coax Networks: IEEE802.14 vs. MCNS,” IEEE Communications, Apr. 1999.
[4] Douglas E. Comer, “Internetworking with TCP/IP”, Prentice Hall, second edition, 1991, pp. 23, 484.
[5] Francois Fluckiger, “Understanding networked multimedia”, Prentice Hall, 1995, pp. 523.
[6] Donald Gross and Carl M. Harris, “Fundamentals of Queueing Theory”, Wiley Interscience, third edition, 1998, pp. 4, 8, 14.