Abstract
今日，隨著高速網路的出現，在網路上的等時傳輸服務變得愈來愈重要， 因此，必須設計一些有效率的方法來管理等時傳輸頻寬，並利用等時傳輸 通道合併（merging）和分割（splitting）的技術，來使得網路上的等時 傳輸頻寬能夠達到最佳的使用。在網路形狀的研究方面，我們將在這篇論 文中採用規則網狀網路──雙向的曼哈頓街形網路（ＢＭＳＮ）──來當 作為主要探討的網路，因為它具有許多的優點：它比一度空間的線性網路 系統（例如：ＤＱＤＢ）的生產量更高、可靠度更高、路徑決定簡單、點 對點的平均距離更短。在規則網狀的都會型網路上，等時傳輸路徑的佈置 問題（IPAP）在這篇文章中被探討。在這網路上，給定一組已建立好的等 時傳輸路徑的集合，和一組欲建立等時傳輸路徑之請求的集合，我們的目 的是為每一個欲建立等時傳輸路徑之請求來佈置其路徑，使得能夠使用最 少量的等時傳輸頻寬單位（SLOT）來服務這些請求。從另一個角度來講， 給定一個有限的等時傳輸頻寬，目標是利用這些有限的頻寬來建立最大數 量的等時傳輸路徑。我們證明等時傳輸路徑的佈置問題是ＮＰ－ｃｏｍｐ ｌｅｔｅ，並且提出一些分散式及集中式的heuristic方法來解決等時傳 輸路徑的佈置問題。從實驗結果顯示出，我們提出的heruistic方法可以 提高等時傳輸頻寬單位的利用率、降低等時傳輸路徑請求之失敗比率、以 及提高等時傳輸路徑成功建立的數量，因此，我們提出的方法是有效率的 。 Today, with the high speed network emerging, the isochronous serviceon the network are becoming more important. It is necessary to design some efficient schemes to manage the isochronous bandwidth. In the thesis, we adopt the regular mesh network, Bi-directional Manhattan Street Network (BMSN), as our mainly exploring network because thereare several advantages on this network: higher throughput, more reliablility, path decision is easy, and the average distance is shorter than the linearnetwork system such as DQDB. In this thesis, the isochronous paths allocation problem (IPAP) on regular (mesh) metropolitan area networks is investigated. Given a set of established isochronous paths and a set of isochronous requests, the goal is to allocate path for each of the requests so that a minimal number of isochronous slots is used to service these requests. On the other hand, given a limited isochronous bandwidth, the goal is to establish a maximal number of isochronous paths. We show that the IPAP is NP-complete. Several heuristics for the IPAP, including centralized version and distributed version, are proposed. Simulation results show that the proposed heuristics are efficient in terms of isochronous slots utilization, call blocking rate, and the number of successfully established isochronous paths.