不阻塞網路及不中斷網路之研究

Abstract

不阻塞交換網路有三種不同程度的不阻塞，分別為：strictly nonblocking (SNB)、wide-sense nonblocking (WSNB)及rearrangeable (RNB)。對於古典交換網路，我們定義阻塞發生的條件為兩條連線(connection)嘗試使用同一條線(link)。由於現今光學技術的限制，學者們在研究光學交換網路時分別假設了各種不同的限制，其中一種就是點阻塞條件；這個條件在現實上對應到使用方向耦合器(directional coupler)時的無干擾限制(crosstalk-free constraint)。 在這篇論文中，我們研究古典交換網路的阻塞度(degree of blockingness)；藉由這樣的研究，我們將阻塞度的定義擴展至點阻塞度(degree of node-blockingness)，並且將點阻塞度應用到無干擾的光學交換網路上。更進一步地，我們可以用很簡單的論證將一些古典交換網路的結果轉換成目前文獻中無干擾光學交換網路的結果；同時我們也給出了一些目前文獻中沒有的新結果。 除了研究不阻塞交換網路，我們也研究了一類新的不阻塞交換網路，稱為不中斷(noninterruptive rearrangeable (NIR))網路。不中斷網路和前面提及的RNB不阻塞網路十分類似，除了連線重排(rearrange)時需要先將新路線走通再行中斷舊路線，以保證所有連線在重排時不會有資料遺失。在這篇論文裡頭，我們對於不中斷的Clos網路做了完整的研究，並且給出了許多有效率的不中斷網路，並且和已知的結果做比較。 1973年時，Bassalygo提出了一個新的想法可以令RNB不阻塞網路的重排數(number of rearrangements)減少，Bassalygo同時宣稱了一個重排數的上界，但他並沒有給出仔細的證明。在這篇論文當中，我們針對他的方法給出一系列的例子反證他的上界，並且給出一個新的上界。同時我們也改良這個原本應用在RNB不阻塞網路上的方法，使之可以應用在不中斷網路上。

For nonblocking switching networks, there are different levels of nonblockingness: strictly (SNB), wide-sense (WSNB), and rearrangeable (RNB). Traditionally, the blocking condition of classical networks occurs when two connections are attempting to use the same links. However, due to the limitation of current optical technology, researchers studies different blocking conditions for optical switching networks. One of the most important blocking conditions is the node-blocking condition, which reflects the crosstalk-free constraint by using directional couplers as switching elements. In this thesis, we study the degree of blockingness for classical strictly nonblocking networks. By extending the definition of the degree of blockingness, we also study the degree of node-blockingness, which is used for crosstalk-free networks. Further, we give a simple argument to transform classical SNB (RNB) results to crosstalk-free results. At the same time, we also give some new results. Besides studying the nonblockingness in the literature, we also study a new class of nonblocking networks called noninterruptive rearrangeable (NIR) networks, which are rearrangeable under the additional condition that existing connections are not interrupted while their paths are rerouted. In this thesis, we give a complete characterization of NIR Clos networks built of switching elements of various nonblocking properties. Our approaches provide recursive constructions of NIR networks, and thus deduce many cost-efficient NIR networks. We also give comparisons between our constructions and previous known results. In 1973, Bassalygo proposed an idea to rearrange existing connections for RNB Clos networks that can connect requests with fewer rearrangements. He claimed an upper bound of the rearrangements and gave an outline of proof but no detail. In this thesis, we give a series of examples invalidating his upper bound and also give a new upper bound. Further, we modify the routing algorithm to fit NIR networks.