Abstract
在全光封包交換網路 (all-optical packet-switched networks) 中，建造光封包的緩衝器是一個重要的課題，而目前已知可行的方法是利用光交換機 (optical switches) 與光纖延遲線 (fiber delay lines) 來建造光封包的緩衝器。在這篇論文裡，我們考慮的問題是如何建造有繞行次數限制之光佇列 (optical queues)。這樣的一個繞行次數限制是來自實作上的考量。由先前的研究成果，我們已經知道在有繞行次數限制的情況下，光學線性壓縮器 (optical linear compressors) 與光學線性解壓縮器 (optical linear decompressors) 的最大有效延遲時間 (effective maximum delay)，以及雙輸入埠與單輸出埠之先進先出光學多工器 (optical 2-to-1 FIFO multiplexers) 的有效緩衝區容量 (effective buffer size)，都等於一個最大可表示整數$B(\dbf_1^M;k)$，其中$\dbf_1^M=(d_1,d_2,\ldots,d_M)$為光纖延遲線長度的數列，$k$為光封包繞行此$M$條光纖的次數限制 ($B(\dbf_1^M;k)$的數學定義請參閱論文第一章的(1.4)式)。另外，我們已經知道光學線性壓縮器、光學線性解壓縮器、以及雙輸入埠與單輸出埠之先進先出光學多工器的最佳建造方式，必定可由一個貪婪建造法 (greedy constructions) 得到，換句話說，要找到上述光佇列的最佳建造方式 ，我們只需在貪婪建造法所構成的集合$\Gcal_{M,k}$裡找出一個${\dbf^*}_1^M$使得$B({\dbf^*}_1^M;k)=\max_{\dbf_1^M\in\Gcal_{M,k}}B(\dbf_1^M;k)$即可。 在這篇論文裡，我們證明上述光佇列最多存在兩種最佳建造方式，並且我們提出一個簡單的演算法以得到這些最佳建造方式。我們主要的做法是透過配對比較 (pairwise comparison) 來移除$\Gcal_{M,k}$中比較不好的建造方式。出人意料地，我們的演算法與輾轉相除法 (Euclid's algorithm) 有關。我們證明了如果$\gcd(M,k)=1$，那麼只存在一個最佳建造方式；如果$\gcd(M,k)=2$，那麼我們有兩種最佳建造方式；如果$\gcd(M,k)=3$，那麼最多只存在兩種最佳建造方式。