雙向的廣義Shuffle-Exchange網路之逆向網路之快速標記式路線安排演算法

Abstract

在記憶體管理、通訊技術中, shuffle-exchange network是廣泛被拿來運用以及討論的網路。 在1991年的時候, Padmanbhan定義並討論了廣義的shuffle-exchange network(簡記為 GSEN), 此網路不再限制輸入與輸出個數必為k的次方(假設switch element 的size均為 k*k)。 Padmanbhan也提出了快速標記式路線安排演算法。 到了2003年， Chen、Liu以及Qiu又將GSEN推廣成所有的連線均為雙向，並稱之為bidirectional GSEN。 一個bidirectional GSEN包含了兩個網路：一個正向網路與一個逆向網路。 關於正向網路的路線安排，可以用Padmanbhan所提出的演算法解決； 關於逆向網路的路線安排，Chen、Liu以及Qiu等人也提出了利用Padmanbhan的演算法， 先求出正向網路的標記， 然後利用此標記得出逆向網路的路線安排。 在這篇論文中， 我們證出了逆向網路具有很好的性質： 對每個終點i而言, 有兩個標記伴隨著它, 任意一個起點$j$均可利用這兩個標記中的一個， 來安排訊息傳送路線。 我們利用此性質做出快速的一對一路線安排演算法， 此演算法在建構routing table時， 速度比使用Chen、Liu以及Qiu所提出的演算法來得快。

In [7], Padmanbhan proposed the general shuffe-exchange network (GSEN) and an effcient tag-based routing algorithm for it. In [1], Chen, Liu and Qiu further enhanced the GSEN with bidirectional links. The bidirectional GSEN can be divided into two dependent networks, the forward network and the backward network. Since the forward network is a GSEN, Padmanbhan's tag-based routing algorithm can be applied on it. As for the backward network, Chen et al. [1] proposed a routing algorithm which is based on the idea of inversely using the forward control tag. In this thesis, we will show that the backward network has a wonderful property: for each destination i, there are two backward control tags associated with it such that every source j can get to i by using one of the two control tags. We will use this property to derive effcient algorithms for one-to-one routing and for constructing a routing table.