臺灣博碩士論文加值系統

混合光纖同軸電纜(Hybrid Fiber Coaxial, HFC)網路是一個建構在共享媒體上的多頻道架構，因此需要以多頻道排程演算法，來管理每個頻道上的資料傳遞行為。但目前在HFC網路上最常用的Data-Over-Cable Service Interface Specifications (DOCSIS)協定，並未對於多頻道排程演算法加以規範，而是開放給業者和學界自行設計，因此之前產生了許多的演算法，企圖解決此一問題。然而這些論文皆忽略了HFC網路中non-UGS資料的運作。因此在本篇論文中，我們提出一個多頻道的排程演算法，它能為每個non-UGS資料需求(data request)算出最有效的排程延遲時間(scheduling delay time)。
這個演算法能依據整個網路的負載，以及每個上行頻道(upstream channel)上可用的頻寬，來管理所有上行頻道的資料傳遞。我們首先以數學模型來分析此一演算法，並透過模擬產生結果，最後針對這些模擬結果進行討論。

Hybrid Fiber Coaxial (HFC) Network is essentially a shared media with multiple channels and requires an algorithm to manage data transmission within each channel. Since the Data-Over-Cable Service Interface Specification (DOCSIS) protocol does not specify the scheduling algorithm, it is open for vendors and researchers. So, many algorithms were proposed, but the operation of the non-UGS data in the multi-channel HFC network is omitted by all these algorithms. In this paper, we propose one feasible multi-channel scheduling algorithm that optimizes the scheduling delay time of each transmission non-UGS request.
This algorithm manages the amount of data transmission in each upstream channel according to the whole network load and available bandwidth in each channel. We analyze this algorithm mathematically, perform several simulations, and discuss the results.

目錄
摘 要 i
Abstract ii
目錄 iii
圖目錄 v
表目錄 vi
第一章 簡介 1
1.1 背景 1
1.2 動機與目的 2
第二章 HFC網路介紹 4
2.1 HFC網路的發展背景 4
2.1.1 國外部分 4
2.1.2 國內部分 6
2.2 HFC網路架構 6
2.2.1 頭端 7
2.2.2 傳輸線路 7
2.2.3 用戶端 8
2.3 HFC網路上的標準 8
2.3.1 IEEE 802.14 標準 9
2.3.1.1 IEEE 802.14舊版草案 9
2.3.1.2 IEEE 802.14新版草案 10
2.3.2 MCNS 標準 10
2.3.3 DOCSIS 相關標準 22
2.3.4 IEEE 802.14 與 DOCSIS 標準的異同 23
2.3.4.1 MAC Layer的技術 24
2.3.5 北美地區之外其他標準 27
2.3.5.1 DVB與DAVIC標準 27
2.3.5.2 EuroDOCSIS標準 28
2.4 HFC網路的運作 28
2.5 多頻道網路的運作 30
2.6 HFC網路的延遲分析 31
第三章 演算法 34
3.1 動機 34
3.2 排程器(Scheduler)的模型 35
3.3 演算法介紹 35
3.4 範例 38
第四章 模擬與討論 40
4.1 模擬環境 40
4.2模擬與討論 42
4.2.1 Case 1：所有上行頻道的頻寬皆相同 42
4.2.2 Case 2：所有上行頻道的頻寬皆不同 43
4.2.3 Case 3：上行頻道中有一條頻寬較狹小，其餘三條的頻寬皆相同 46
4.2.4 Case 4：上行頻道中有一條頻寬較寬大，其餘三條的頻寬皆相同 48
4.2.5 Case 5：上行頻道的頻寬分成兩對不同頻寬 50
第五章 結論 52
參考文獻 53
致謝 56



圖目錄
圖1.1 HFC網路架構圖 2
圖1.2 HFC網路頻譜分配圖 2
圖1.3 HFC網路的運作方式 3
圖2.1 HFC網路架構圖 7
圖2.2 DOCSIS架構圖 12
圖2.3 HFC網路傳輸架構圖 12
圖2.4 下行實體層架構圖 13
圖2.5 上行頻道實體層架構圖 14
圖2.6 DOCSIS相關通訊協定架構圖 15
圖2.7 上行頻道頻寬配置圖 17
圖2.8 截斷二元指數倒退演算法流程圖 18
圖2.9 一般保留存取模式的時間表示圖 19
圖2.10 unsolicited grant service (UGS) 20
圖2.11 unsolicited grant service with activity detection (UGS-AD) 21
圖2.12 real-time polling service (rtPS) 21
圖2.13 DOCSIS協定中傳送資料的運作流程 29
圖3.1 多頻道排程器的模型 35
圖3.2 DMS演算法的虛擬碼 37
圖3.3 範例中兩個上行頻道的情形 39
圖4.1 三個演算法在Case 1的平均排程延遲時間的比較 42
圖4.2 三個演算法在Case 1平均排程延遲時間的標準差的比較 43
圖4.3 三個演算法在Case 2平均排程延遲時間的比較 44
圖4.4 三個演算法在Case 2平均排程延遲時間標準差的比較 45
圖4.5 三個演算法在Case 3平均排程延遲時間的比較 47
圖4.6 三個演算法在Case 3平均排程延遲時間標準差的比較 47
圖4.7 三個演算法在Case 4平均排程延遲時間的比較 48
圖4.8 三個演算法在Case 4平均排程延遲時間標準差的比較 49


表目錄
表2.1 IEEE 802.14 新舊草案在碰撞解決演算法的差異 10
表2.2 DOCSIS支援的六種服務等級 20
表2.3 IEEE 802.14 與DOCSIS 在實體層的差異 23
表2.4 IEEE 802.14 與 DOCSIS 在媒體存取控制層的差異 24
表4.1 封包大小的分佈情形 41
表4.2 不同Case中上行頻道的頻寬 41

[1] Cable Television Laboratories. (2003, Sep). DOCSIS Overview. [Online]. Available: http://www.cablemodem.com
[2] Cable Television Laboratories, Data-Over-Cable Service Interface Specifications, Radio Frequency Interface Specification, SP-RFIv2.0-I04-030730, July 2003.
[3]朱國志, 劉安哲, 李維聰, 詹寶珠, "混合光纖同軸網路之動態頻道分配機制", 中華民國九十年全國計算機會議, pp. E79-E88, Dec. 2001, Taipei, Taiwan
[4]黃進芳,有線電視系統與量測技術工程,全華科技圖書股份有限公司, Aug. 1996.
[5] IEEE Project 802.14 Working Group, “IEEE P 802.14 Cable-TV Functional Requirements and Evaluation Criteria”, MARCH 3,1995.
[6] IEEE Project 802.14 Working Group, “IEEE 802,14/a Draft 3 Revision 2”, Aug. 1998.
[7]凌志綺, ”IEEE 802.14 PHY標準制訂介紹”,經濟部中央標準局, 工業財產權與標準, Oct. 1997
[8]楊鴻岳, ”IEEE 802.14 MAC標準制訂介紹”,經濟部中央標準局, 工業財產權與標準, Aug. 1997.
[9]楊鴻岳, ” 軸纜數據資料服務介面規格介紹”, 經濟部中央標準局, 工業財產權與標準, April. 1998.
[10]凌志綺,”軸纜數據資料服務射頻實體層介面規格介紹”,經濟部中央標準局, 工業財產權與標準, Oct. 1998.
[11]楊鴻岳, ”MCNS MAC 通訊協定規格(上)”, 經濟部中央標準局, 工業財產權與標準, May. 1998.
[12]楊鴻岳, ”MCNS MAC 通訊協定規格(下)”, 經濟部中央標準局, 工業財產權與標準, June 1998.
[13] Jung-Tsan Lin and Wei-Tsong Lee, “Bandwidth admission control mechanism for supporting QoS over DOCSIS 1.1 HFC networks,” ICON 2002., Pages:9 – 13, Aug. 2002.
[14] Cable Television Laboratories. OpenCable. [Online]. Available: http://www.cablemodem.com
[15] Cable Television Laboratories. PacketCable. [Online]. Available: http://www.cablemodem.com
[16] Cable Television Laboratories. CableHome. [Online]. Available: http://www.cablemodem.com
[17] Chen-Yu Huang & Ying-Dar Lin, “Comparing IEEE 802.14 and MCNS Standards for hybrid fiber coaxial networks”, ICS, pp.149-156, Dec. 1998.
[18] Ying-Dar Lin, Chen-Yu Huang, and Wei-Ming Yin, “Allocation and Scheduling Algorithms for IEEE 802.14 and MCNS in Hybrid Fiber Coaxial Networks”, IEEE Transactions On Broadcasting, Vol.44, No.4, December 1998.
[19] Ying-Dar Lin, Wei-Ming Yin, and Chen-Yu Huang, “AN INVESTIGATION INTO HFC MAC PROTOCOLS: MECHANISMS, IMPLEMENTATION, AND RESEARCH ISSUES,” IEEE Communications Surveys • http://www.comsoc.org/pubs/surveys • Third Quarter 2000
[20] N. Golmie, Y. Saintillan, and D. Su, “Review of Contention Resolution Algorithms for IEEE 802.14 Networks,” IEEE Communication Surveys, http://www.comsoc.org/pubs/surveys, vol. 2, no. 1, 1999.
[21] DAVIC. DOCSIS Overview. [Online]. Available: http://www.davic.org
[22] Cable Television Laboratories. (2003, Sep). [Online]. Available: http://www.cablemodem.com
[23] Kuo-Chi Chu , Yi-Gang Tai , Wei-Tsong Lee , and Pau-Choo Chung , "A Novel Priority Scheme for Hybrid Fiber Coaxial Broadband Network," Proceedings of IEEE TENCON, Oct. 2002, Beijing, CHINA.
[24] Char-Long Chen and Wei-Tsong Lee , "A Novel MAC Protocol for Supporting Quality of Service over IEEE 802.14," Proceedings of IEEE Tencon 2001, pp. 18-22, Aug. 2001, Singapore.
[25]朱國志 , 戴義剛 , 李維聰 , and 詹寶珠 , "混和光纖同軸網路上MCNS標準中頻寬需求法則之研究," Proceedings of 第五屆電腦與通信技術研討會, Oct. 2000, Chang-Hwa,Taiwan.
[26] Y. D. Lin, C. Y. Huang, and W. M. Yin, “Allocation and Scheduling Algorithms for IEEE 802.14 and MCNS in Hybrid Fiber Coaxial Networks,” IEEE Transactions On Broadcasting, Vol. 44, No. 4,pp.427-435, December 1998.
[27] W. M. Yin and Y. D. Lin., “Statistically Optimized Minislot Allocation for Initial and Collision Resolution in Hybrid Fiber Coaxial Networks,” IEEE Journal on Selected Area in Communications, Vol. 18, No. 9, pp.1764-1773, September 2000.
[28]朱國志 , 戴義剛 , 李維聰 , and 詹寶珠 , "混合光纖同軸網路上MCNS標準中截斷二元指數後退演算法之研究," Proceedings of Proceedings of the 1999 National Computer Symposium, pp. B152-B158, Dec. 1999, Taipei.
[29]Y.G. Tai and Wei-Tsong Lee , "Quality of Service Support in IEEE 802.14 and MCNS standards in HFC Networks," Proceedings of 1999 Workshop on Distributed System Technology and Application, May 1999, Tainan, Taiwan.
[30]Chin-Ping Tan , Kuo-Chi Chu , and Wei-Tsong Lee , "LSRAM: A Lo-Su Resource Allocation Mechanism over DOCSIS Cable Network," Proceedings of International Computer Symposium 2002, Dec. 2002, Hualien, Taiwan.
[31] Jung-Tsan Lin and Wei-Tsong Lee , "Bandwidth Admission Control Mechanism for Supporting QoS Over DOCSIS 1.1 HFC Networks," Proceedings of IEEE ICON 2002, Aug. 2002, Singapore.
[32] 林榮燦 and 李維聰 , "在有線電視網路中支援服務品質保證的頻寬允許機制," Proceedings of 2002數位生活網際網路科技研討會, June 2002, Tainan, Taiwan..
[33]李維聰 and 朱國志 , "多頻道有線電視網路之動態頻寬管理," Proceedings of 2000網際網路與分散式系統研討會, May 2000, Tainan.
[34] Jung-Tsan Lin and Wei-Tsong Lee, “Bandwidth admission control mechanism for supporting QoS over DOCSIS 1.1 HFC networks,” ICON 2002., Pages:9 – 13, Aug. 2002.
[35] Hawa Mohanmmed and W. Petr David ”Quality of service scheduling in cable and broadband wireless access systems,” Tenth IEEE International Workshop on Quality of Service, 2002, Pages:247 – 255, 15-17 May 2002.
[36] Heyaime-Duverge and C.; Prabhu, V.K.”Traffic-based bandwidth allocation for DOCSIS cable networks,” International Conference on Computer Communications and Networks, 2002 , Pages:586 – 590, Oct. 2002
[37] Naaman, N. and Rom, R.,”Scheduling constant bit rate flows in data over cable networks,” ISCC 2002, Pages:577 – 582, July 2002.
[38] Huei-Jiun Ju and Wanjiun Liao , “Adaptive scheduling in DOCSIS-based CATV networks,” International Conference on Computer Communications and Networks, 2002. Pages:543 – 547, Oct. 2002
[39] Wen-Kuang Kuo, Kumar, S. and Kuo, C.-C.J, ”Bandwidth allocation and traffic scheduling for DOCSIS systems with QoS support,” IEEE GLOBECOM '02., Pages:1990 - 1994 vol.2, Nov. 2002.
[40] Wen-Kuang Kuo, Kumar, S. and Kuo, C.-C.J, ”Bandwidth allocation and traffic scheduling for DOCSIS systems with QoS support,” IEEE GLOBECOM '02., Pages:1990 - 1994 vol.2, Nov. 2002.
[41] Wei-Ming YIN, Chia-Jen Wu, and Ying-Dar LIN, “Two-Phase Minislot Scheduling Algorithm for HFC QoS Service Provisioning”, IEICE Trans. COMMUN., Vol. E85-B, NO.3, MARCH 2002
[42]朱國志 , 劉安哲 , 李維聰 , and 詹寶珠 , "混合光纖同軸網路之動態頻道分配機制," Proceedings of 中華民國九十年全國計算機會議, pp. 79-88, Dec. 2001, Taipei, Taiwan.
[43] J. Limb, “Performance evaluation process for MAC protocols,”. IEEE 802.14 Working Group Meet., May 1996. contract IEEE802.14-96/08