高性能可變長度封包反覆相匹配演算法

Abstract

由於網際網路的蓬勃發展，對於網路頻寬的需求越來越大，高效能的交換機也就成了學術研究中相當熱門的領域。通常高性能的IP交換機皆利用固定時間格的技術將可變長度封包切割為數個固定大小的細胞，再將每一個細胞依據其目的地妥善地進行配對，使每一個細胞能夠傳送到輸出端再進行重組還原成原本的封包。由於反覆相匹配演算法具有低複雜度且高效能的優勢，近來已有許多相關的演算法出現；其中，EDRRM是一種專為可變長度封包進行匹配的排程演算法，使得同屬於一個封包的細胞可以在連續的時間格中進行傳送，如此一來輸出端的重組單元的複雜度便可大大降低甚至移除；且EDRRM對於封包這種叢聚輸入的輸入模型能夠提供較低的等待延遲時間，而且對於非平均分配的輸入模型更能夠提供高流量的效能。然而，EDRRM在平均分配的輸入模型中表現卻不盡理想，所以在這篇論文中，我們提出了忙碌提醒的機制並成就了一套新的演算法EDRRM/BN。利用忙碌提醒的機制，可避免EDRRM中無用的要求進而提升建立匹配的效率，經過我們廣泛地模擬測試，我們提出的EDRRM/BN與其他反覆相匹配演算法比較起來，在各種輸入模型都提供了最佳的效能。

Fixed-length switching technology is widely adopted for the high-performance switches. In order to resolve the HOL problem of input queuing (IQ) switch, Virtual Output Queuing architectures with different matching algorithms are used. The Exhaustive DRRM (EDRRM) algorithm possesses the lower delay under bursty and nonuniform traffics and the Output Reassemble Unit (ORU) is not needed, however, EDRRM performs worse under the uniform i.i.d. traffic. In the thesis, we propose a busy notification mechanism and modified the EDRRM algorithm into an improved version, EDRRM/BN. The EDRRM/BN avoids the useless requests and increases the efficiency of setting up the matching. We have evaluated the EDRRM/BN using extensive simulations and we will show that the EDRRM/BN yields the lowest delay comparing with other algorithms under all traffic patterns.