[[alternative]]Design and implementation of cid merge/split algorithm for IEEE 802.16 wireless metropolitan area network

碩士[[abstract]]隨著網路的快速發展，各種寬頻資料服務已成為日趨重要的服務元素，愈來愈多元的網路內容需要更多的頻寬來傳輸，現今全球各地僅有少數電腦使用者能獲得DSL、纜線寬頻存取服務等高速有線寬頻服務，網路服務業者希望擴展其寬頻網路的涵蓋範圍，但佈建有線網路的相關基礎建設與建構成本往往會使業者望而卻步。在此之際，寬頻無線網路技術就成為重要的解決方案，綜觀目前無線網路的技術，其以距離來分類，可分為廣域網路、大都會網路、區域網路和個人網路。其中IEEE 802.16 是一項新興的無線傳輸介面技術，最初是為發展大都會存取網路的一種線電標準，讓系統能運用低成本的「最後一哩」的寬頻連線技術，支援如有線電視或DSL 這類有線型寬頻網路無法涵蓋的用戶，之後經過持續地改進，現已能支援更多的市場，包括各種行動與高速寬頻應用。 本論文主要是針對IEEE 802.16標準協定中基地台（Base station）在分配Transport CID給用戶站（Subscriber Station）時所產生之問題進行修正，方法在於利用自行設計之CID融合與分離引擎（CID Merging and Splitting Engine－CID MSE）配合Classifier與QoS Scheduler之間的資訊交換來進行CID的融合與分離。在真實的硬體裝置中，即使網路資源足夠，若CID數量越多，QoS Scheduler運算時所需的資源就越大。因此礙於硬體上的處理限制，本論文將限制CID的數量來減低QoS Scheduler在計算時的負擔。在IEEE 802.16中並無定義QoS Scheduler的標準做法，而QoS Scheduler也是整體上最主要的資源消耗，因此只要降低QoS Scheduler的負擔，整體效能必能提升。 首先，當封包進入MAC層 (Medium Access Control Layer) 之後，一樣會透過Classifier到資料庫中查詢相關資訊，並且將會去檢查QoS Scheduler對CID處理能力是否已達極限，若無 ” 已超過負荷 ” 的相關訊息，表示QoS Scheduler依然能夠處理更多的CID，則此封包將以一般的流程被處理；反之，Classifier將透由CID MSE來進行CID的融合。在進行CID融合機制時，CID MSE將會去資料庫中尋找最適當的CID，作為融合目標。挑選的標準首先考慮的必須是相同QoS等級，接著依可使PHS壓縮最多資料的CID為優先考慮，因此CID MSE將會選擇封包表頭資訊越相同的CID來進行融合。融合成功之後，若再有此封包進入MAC層，Classifier會直接將之引入融合目標的CID佇列，因此QoS Scheduler的負擔也隨之降低。當有任何使用中CID所屬的服務結束，CID MSE會依據收到QoS Scheduler資訊，並依照融合時所做的紀錄，將之前被融合過的服務分離出來。CID分離之後，CID MSE也會改變或刪除原本所紀錄之融合資訊，及增加一個新的服務。 經由CID融合與分離方法可以有效的解決CID數量超過QoS Scheduler 能處理的極限，或CID已用完而無法申請服務；進而提升排程的效率與降低排程的效率與降低排程的複雜度，達到排程最佳的即時性。[[abstract]]Mobile communication system providers already invest money on deploying 3G mobile communication networks. Computer-based industry proposes another wireless communication technology: IEEE 802.16 WMAN (Worldwide Interoperability for Microwave Access), which is also known as IEEE 802.16-2004/16e standards. It is a new wireless communication technology that is designed to provide users wireless data services, and this technique also has the potential to be the Last-mile solution for connecting residential networks to Internet. The Cid Merging and Splitting Mechanism (CID MSM) enhance the IEEE 802.16-2004 MAC protocol when the ability of QoS scheduler that is designed by us is overload. It means that more cids lead more bandwidth allocated time. Because of promoting the performance, we design the Cid Merging and Splitting Mechanism to reach our goal. The IEEE 802.16 CPE (Customer Premise Equipment) will perform cid merging algorithm when our QoS scheduler was overload. As long as the number of cid is reach threshold, the QoS scheduler will send control message with “merge” to the CID MS Engine to tell it the status of QoS scheduler. So, when a new traffic injects into CPE after QoS scheduler was overload, first, the Packet Classifier will search the CID table regularly to know the traffic was recoded or not. Second, if the result is “miss”, the CPE will perform CAC (Call Admission Control) Algorithm. Then the CID MS Engine will judge the status of QoS scheduler, and perform CID Merging algorithm. The major conditions for selecting the target CID are the QoS type and maximum size that the PHS can suppress. So we define priority order, for selecting the suitable target. When the QoS scheduler can’t process more cids, the CID MS engine will perform search algorithm to choose the suitable target cid from CID table according to the header information of new traffic, and it will reference the SFID table to combine the QoS parameters of the new traffic and target cid into a new QoS parameter set. After selecting the target cid, the Dynamic Service Engine will use this new parameter set to find a most corresponding SFID. If the SFID is existence, it will send DSC with this SFID to BS. Otherwise, DSA will be sent.[[tableofcontents]]目錄 目錄.................................................... I 圖目錄 .................................................III 表目錄 ................................................. V 第一章 導論 ..............................................1 1.1 前言 ................................................1 1.2 研究動機 ............................................2 1.3 論文架構 ............................................2 第二章 IEEE 802.16無線大都會網路介紹 ....................4 2.1 引言 ................................................4 2.2 IEEE 802.16 .........................................7 2.3 IEEE 802.16媒體擷取控制層之介紹 .....................12 2.3.1 收斂層（service specific convergence sublayer,CS）.13 2.3.2 通用層（common part sublayer, CPS）................17 2.4 IEEE 802.16實體層之介紹 .............................30 第三章IEEE 802.16無線大都會網路中連線識別碼之融合與分離演 算法 ....................................................32 3.1簡介 .................................................32 3.2連線識別碼之融合 .....................................34 3.3連線識別碼之分離 .....................................39 3.4結論 .................................................41 第四章 連線識別碼之融合與分離演算法之模擬程式 ...........42 4.1 模擬程式說明 .......................................42 4.2 融合演算法之行為顯示 ................................44 4.3 分離演算法之行為顯示 ................................50 第五章 模擬分析結果 ....................................56 5.1 模擬一 .............................................56 5.2 模擬二 ..............................................58 5.3 模擬三 ..............................................58 第六章 未來的工作 ......................................61 參考文獻 ...............................................62 圖目錄 圖2.1、IEEE 802.16媒體擷取控制層之主要層級細分方式 ......12 圖2.2、以下載方向為例之連線代碼（CID）搜尋對應示意圖.....16 圖2.3、連線過程之服務種類範圍 ...........................16 圖2.4、資料檔頭壓縮之步驟 ...............................17 圖2.5、用戶端連線初始化之步驟流程 .......................21 圖2.6、TDD模式下的DL-MAP以及UL-MAP影響時間點為下次訊框之示意圖 ....................................................24 圖2.7、FDD模式下的DL-MAP以及UL-MAP影響時間點為下次訊框之示意圖.....................................................25 圖2.8、TDD模式下的DL-MAP以及UL-MAP影響時間點為此次訊框之示意圖.....................................................26 圖2.9、FDD模式下的DL-MAP以及UL-MAP影響時間點為此次訊框之示意圖.....................................................26 圖2.10、由競爭週期與免競爭週期所組成之上傳週期 ..........27 圖2.11、一般資料檔頭與頻寬請求檔頭之格式 ................29 圖3.1、包含CID MSE之SS系統方塊圖 ........................33 圖3.2、封包表頭資訊及其資料長度 .........................35 圖3.3、選擇融合的CID 所考量因素的優先順序 ...............35 圖3.4、融合演算流程圖 ...................................37 圖3.5、融合演算法 .......................................38 圖3.6、CID表格 ..........................................39 圖3.7、分離演算流程圖 ...................................40 圖3.8、分離演算法 .......................................41 圖4.1、SS端的主視窗畫面 .................................42 圖4.2、CPE端cid table視窗畫面 ...........................43 圖4.3、CPE端sfid table視窗畫面 ..........................44 圖4.4、SS從BS取得可使用之SFID列表 .......................45 圖4.5、SS向BS申請CID後，CID與SFID表格之變化情形 .........46 圖4.6、新進服務與所選出的融合候選目標的表頭資訊關係 .....47 圖4.7、當新進服務無可融合的目標存在的情況發生 ...........48 圖4.8、當無融合目標存在的情況之下觸發其他QoS種類的兩個服務進行融合 ................................................49 圖4.9、已運行融合演算法後CID表格狀態 ....................50 圖4.10、CID表格中索引號碼8的服務即將停止 ................51 圖4.11、索引號碼11服務繼承索引8號服務的結果 .............52 圖4.12、索引號碼4服務即將停止 ...........................53 圖4.13、依據規則所挑選出來需分離的兩服務 ................54 圖4.14、運行分離演算法之後的結果 ........................55 圖5.1、標準協定與運行連線識別碼之融合與分離演算法對於服務處理的效能情形 ............................................57 圖5.2、CID數量級資源使用狀況的關係 ......................58 圖5.3、分離數量與PHS資料壓縮量的關係 ....................60 表目錄 表2.1、IEEE 802.16的近期相關標準 ........................11[[note]]學號: 693390014, 學年度: 9