非同步可變長度封包交換機之設計與效能分析

目前一般的交換機設計處理固定長度的封包（稱之為細包），而且要求所有的輸入接口的資料流同步。然而，目前網路上盛行非固定長度的封包，如網際網路通訊協定(IP)、乙太網路(Ethernet)封包，因此此種交換機必須將接收到的封包先切割成多個細包，再經由細包交換機同步地交換所有輸入埠的細包，最後在輸出至網路傳輸前，必須再將交換過的細包組合成封包。細包交換機在處理非同步長度可變的封包時，必須使用額外的切割組合電路和暫存區，同時效能上也較不具效率。為了能夠非同步地直接交換接收的封包，我們在此論文中提出了一個新穎的交換機架構，並且討論如何設計以達到最佳的效能，同時也提出了一個可行的電路實現。一般的交換機架構可分為含輸入暫存區（Input Queued Switch），含輸出暫存區（Output Queued Switch），及混合式（Combined Input Output Queued Switch）三種。含輸入暫存區之交換機最為簡單，但是卻受限於頭端封包阻塞效應而有相當高的阻塞率（blocking probability）。為了避免此阻塞效應的影響，交換機必須將暫存區置於輸出端（output buffering），以達到高流通量，低封包漏失量的效能。此時，交換機的內部傳輸速度必須為外部傳輸線速度之數倍，以達到可以在同一時槽（time slot）將多個封包送往同一個輸出端。為了達到加速傳輸之目的，暫存區資料的存取時間（access time）必須很短。隨著網際網路交通量的急遽成長，以及光纖通訊技術之進步，交換機必須提供更大的容量。然而目前的硬體技術限制了交換機內部最高傳輸速度，因而無法達到輸出端暫存封包的效能。為了避免硬體上速度的限制，勢必採用輸入端暫存封包的架構，因而出現了各式各樣改善含輸入暫存區交換機效能的解決方法。然而，這些架構需要複雜的交換機控制單元，所以不適合高速高容量之交換機之實現。就硬體的實現上而言，如何簡單控制交換機路由選擇，為實現交換機高容量，低漏失率效能之關鍵。除了具備複雜的控制單元，一般的交換機要求所有的輸入端同步，亦即必須同時處理所有輸入端的封包以決定封包的交換路徑。一般交換機的路由控制之機制，皆操作在同步模式下，因此增加交換機對同步的負擔。採用同步交換的機制增加了封包經過交換機的延遲時間，並且不適合可變長度封包的交換。為了能夠直接處理不同長度之封包，而不經過切割成小細包和重新組合的程序，以及提供整合不同型態資料流服務，目前的網路上層通訊協定要求交換機能夠提供交換不同長度封包之弁遄C所以新一代的交換機設計必須能夠直接處理不同長度之封包。對於現今一般交換機的設計，此一要求大大地增加了其控制電路之複雜度。本論文提出新型之交換機設計，其設計之目的即為了在簡單可實現的硬體架構下，達到非同步且能直接交換不同長度封包之要求。本交換機設計之另一考量為交換機之可擴充性（scalability）。隨著網路對交換機的容量要求逐日增加，交換機的設計必須滿足模組化（modular design）的要求。因此，在我們的架構中，沒有傳統交換機所需要之同步電路及中央控制電路；而是以模組化設計之交換元素配合簡單的輸入端控制器，以達到非同步地交換不同長度封包之目的。本交換機可以提供單傳（unicast）和多傳（multicast）可變長度的封包交換。學理上，我們完整地分析了此交換機架構之效能理論值，以得到系統參數的最佳化值；並且完整的電腦模擬實驗驗證了我們所提出的理論模型可以準確地預測此交換機的效能。同時本論文亦提出了詳細的交換機之硬體設計，以整合單傳和多傳封包交換的操作模式，並且考慮如何對封包的交換提供服務品質（Quality of Service）的機制，以及如何維護封包順序的完整性（packet sequence integrity）。本論文所提出的交換機架構簡單可行，已獲得兩項中華民國專利和公開中的美國專利，可滿足高速網路中高容量交換機的需求。

關鍵字

可變長度封包；交換機；多傳交換；效能分析；單傳交換

並列摘要

Currently most of the switches are cell-based and synchronous,such that the length of the packet is fixed. However, a great partof the current network traffic consists of variable lengthpackets, for example, Ethernet or IP traffics. Hence, thecell-based switch must segment the incoming packets at the inputports into cells, switch these cells synchronously, reassemblethem at the output ports, and finally transmit the packets to theoutput links. The additional segmentation and reassembly circuitsare required. The synchronous cell-based switch incurs performancedeterioration due to synchronization and segmentation overheadwhen the input traffic consists of variable length packets. Inorder to switch the incoming packets with variable lengthasynchronously, we propose a novel switch architecture in thisthesis. Its performance is analyzed in detail by queueing theoryand simulation. The system parameters are optimized to attain thebest performance with the minimum cost. In general, we can categorize the switch architecture as InputQueued (IQ), Output Queued (OQ), or Combined Input Output Queued(CIOQ) switch according to the position of the buffers. The IQswitch is simplest but its throughput is rather low because of theHead-Of-the-Line (HOL) blocking effect. The HOL blocking can beeliminated completely in an OQ switch, which stores the packets inthe output ports. However, the operation speed of the OQ switchmust be many times the rate of the input link in order to obtainhigh throughput. The required speedup of the switch operationrequires extreme short access time of the buffer memory. The speedof the transmission link increases fast because of thecontinuously growing network bandwidth demand and the advent ofWavelength Division Multiplexing (WDM) technology. However, thebottleneck of the network performance still exists because of thelack of high speed switches with large ports. The requirement ofextreme high switching operation speed makes an OQ switchinfeasible. Hence, a lot of schemes were proposed in theliterature to improve the performance of CIOQ switches, whichdon't require the speedup of switching speed too much. However,these schemes require complicated control unit and thus aredifficult to implement. The key to success for a high capacity andhigh performance switch is a simple hardware design to arbitratethe contending packets and to control the routes of packets withthe switching fabric. The design goal of the proposed switch inthis thesis is to switch variable length packets asynchronouslywith simple and feasible hardware. We also take into account thescalability of the switch, i.e., the switch design is based on amodular architecture. There is neither packet arrivalsynchronization circuits nor central controllers, which arerequired in the conventional cell-based switches. Modularswitching elements and simple input controllers are used to switchpackets asynchronously. The proposed switch provides unicast and multicast capabilitiesfor variable length packets. We theoretically analyze and obtainthe performance metric in closed form. Computer simulations aredone to verify the theoretical results. We also derive the optimalsystem parameters, which can be used as the design rule of theswitch. Moreover, we present a circuit level design of the switcharchitecture, which integrates the unicast and multicastcapabilities. This complete design also takes into account Qualityof Service(QoS) provision and packet sequence integrity afterswitching. We believe that the proposed switch is easy toimplement and can satisfy the requirement of high capacity in themodern high speed network.

並列關鍵字

variable length packet ； performance analysis ； unicast ； switch ； multicast

參考文獻

[1]E. Aanen, J. L. van den Berg, and R. J. F. de Vries, "Cell loss performance of the Gauss ATM switch," Proc. INFOCOM '92, pp. 717--726, 1992.

[2]H. Ahmadi and W. E. Denzel, "A survey of modern high-performance switching techniques," IEEE Journal on Selected Areas in Communications, vol. 7, pp. 1091--1103, 1989.

[4]R. e. Y. Awdeh and H. T. Mouftah, "Survey of ATM switch architectures," Computer Networks and ISDN Systems, vol. 27, pp. 1567--1613, 1995.

[5]F. Barber, "A 64x17 non-blocking crosspoint switch," Proc. ISSCC '88, pp. 116--117, 1988.

[6]K. E. Batcher, "Sorting networks and their applications," Proc. Proc. AFIPS Spring Joint COnf., pp. 307--314, 1968.

國際替代計量

非同步可變長度封包交換機之設計與效能分析

全文下載

主題瀏覽