Abstract
寬頻網路之大量整合傳輸服務的理論與技術已漸漸成熟。由於傳輸介質容量的增加，使得交換節點(switching node)的效率成為寬頻網路成效的瓶頸。而交換節點上的效率主要取決於排隊定律(queueing discipline) 的結果。如果提高排隊效率，即可提高交換節點上的效率，進而提高整個寬頻網路的成效。在論文中我們所提的分封資料排程(cell schedul-ing)便是以解決交換節點輸出競爭(Output contention) 并且提高網路成效(Performance) 為目的。ATM 網路是目前被廣為應用的網路自助路徑(self-routing)方法。所有整合網路服務資料以固定大小的分封資料(cell)為單位。把輸送目的位置存於分封資料表頭(header)。每一個分封資料到達交換系統後，停留在緩衝器上，依據其所載目的位址等待輸出。以前的研究結果顯示FIFO佇列最大飽和輸出效能為0.586。向前看佇列(look-ahead) 視窗無限大時可達0.90。我們的分封資料排程在相同的機率模型下可達最大飽和輸出效能為0.957。 時間復雜度(time complexity) 平均在N 以下。論文中我們的分封資料方法是把在緩衝器里的分封資料記錄在交通矩陣中(traffic matrix)。同時每一個分封資料的輸入/ 輸出位址，對應到交換矩陣(switching matrix)的相對位置。每一個交換時間糟里(switching time slot) 以一個交換矩陣為輸入/ 輸出的交換組態(switching xonfiguration) ，當一個新的分封資料進入交換系統(switching system)時，我們便依其輸入/ 輸出或產生一個新的交換矩陣與之對應,或安排的有的交換矩陣與之對應. 這裡我們有一個重置方法副程式(Reallocation algorithm), 主要功能是置換取代兩個交換矩陣的元素, 以改變交換組態,使其預留位置調整使之對應新進分封資料的位置. 當我們知道新進分封資料的輸入/輸出不會增加最小傳輸時間(minimum transmission time) 時, 我們便可找出兩個各別在輸入與輸出處有預留位置(dummy cell)的交換矩陣,然後呼叫重置副程式,很快調整出兩個新的交換矩陣。論文中，提出這個分封資料排程演算法後，我們也提出了執行這個演算法的網路交換系統結構(switching fabric), 我們以排程網路(sorting network) 將重置副程式以硬體結構執行，來減少演算法的時間。而後我們以程式實際模擬此演算法，得到高效能結果，分別是最大輸出效能0.957,平均等候時間在重負荷區間低於FIFO, 分封資料遺失率,要求品質所需緩衝器低於input smoothing。這顯示了我們的演算法是高成效(high perfor-mance) 的方法。