在混合式光纖同軸電纜網路上提供品質服務之兩階段迷你時槽排程演算法

Abstract

在混合式光纖同軸電纜（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.