Abstract
週期性保留多重存取是一種應用在高速區域或是大都會型高速網路上的存 取技術，它是架購在一個單方向性、雙匯流排的結構上。此網路提供了高 系統效能和高公平性的存取方式，而此一高效能及高公平性和網路的大小 及結點的距離無關。在這個網路上，有一個稱之為資料槽產生器的頭節點 ，此一結點會週期性的產生一個控制命令稱之為保留命令。此一命令會經 由匯流排而流經每個節點，此時若節點有資料要傳送，它就會先在此一保 留命令上註冊它所需要的資料槽個數。最後這個保留命令會經由另一個方 向的匯流排回到頭節點。在接收到此一保留命令後，頭節點會總合所有結 點提出的資料槽要求，並且產生一連串的空資料槽給剛剛提出要求的節點 使用，而此一串空資料槽的長度就等於所有剛剛提出提出資料槽的節點所 需資料槽個數的總合，這一串資料槽我們就稱之為一個週期。一般來說， 一個週期的長度若是越長，存取的延遲時間將會越長，而且系統的效能將 會降低。但事實上我們發現一般的資料傳送都有所謂的區域性的趨勢，也 就是說其時有些節點的資料傳送是可以重複使用同樣的資料槽。藉由這樣 的觀念，我們可以安排某些節點的資料傳送使用同一塊資料槽以達到減短 週期長度的目地。所以我們將會提出一個方法來盡可能的來減少週期的長 度，達到減少延遲時間以及提高系統效能的目地。在這一篇論文中，我們 藉由證明了想要在這樣的一個高速網路上尋找最短週期的問題是和在圖學 理論上的一個所謂的區塊著色問題是等價的，進一步證明我們的這個問題 是NP完全的。同時我們也提供了一個複雜度是O(n^2)的驅近的演算法。截 至目前為止，我們對我們所提出的演算法的效率只提出了實驗模擬的結果 ，和傳統的存取網路比較起來，我們所提的新方法得到了更短的週期長度 ，系統效能也比傳統方式好了很多。更進一步，我們發現實驗的結果和所 為謂的完美值相去不遠，同時也比其它發表的資料槽重複使用的技術來的 要好。 Cyclic-Reservation Multiple-Access (CRMA) is an access scheme for high-speed local and metropolitan area networks based on a dual-bus configuration. CRMA provides high throughput efficiency and fairness independent of the network speed or distance. In CRMA, the headend generates the reserve commands periodically. Each station reserves a number of slots in each reserve command if necessary. The headend will generate a sequence of cycles each of which is used to service the reservations on the corresponding reserve command. The length of each cycle is equal to the total number of slots reserved by the stations in the corresponding reserve command. Generally, a longer cycle length will conduct a longer access delay and a lower slots utilization. It is desirable to have a scheme to make the cycle length as short as possible. In this dissertation, we prove that the problem of finding a shortest cycle for a CRMA reservation (called as cycle compression problem) is NP-complete by showing that it is equivalent to the interval coloring problem. We also propose an O(n^2) approximation algorithm to solve this problem; where n is the number of stations in the network. The effectiveness of the algorithm is evaluated via simulation. Simulations results show that compared to the traditional CRMA reservation scheme, the new scheme makes a much shorter cycle length and hence the obtained throughput is much better than the traditional scheme.