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

Abstract

愈來愈多高性能的IP交換機以ATM交換機為其交換核心架構。然而，傳統運用在ATM交換機的匹配演算法，皆以固定大小細胞為交換排程單位。因此，如何在這些高性能IP交換機中有效率的直接以可變長度IP封包形式交換排程，實為重要議題。 在本論文中，我們提出一個新的可變長度封包匹配演算法－EAF/STF/LPF以克服IP-PIM[26]的飢餓問題，並由模擬結果顯示EAF/STF/LPF比PIM[19]有較好的平均封包延遲效能。再者，我們提出另一個演算法－STF/EAF/LPF以增進EAF/STF/LPF的效能表現，並探討飢餓問題與效能之間的關係。

ATM switches which carry fixed-size packets (called ATM cells) have been designed to support high speed networks and several researchers have investigated the migration of ATM switch to high-speed IP switch in attempt to cope with the explosive growth of Internet traffic. The critical issue behind here is how to efficiently schedule variable-length IP packets onto these high performance IP switches. In this thesis, we present a new variable-length packet matching algorithm to avoid the starvation, which occurs in the design of IP-PIM algorithm [26] and the simulation results demonstrate that our proposed algorithm could improve the performance of the original PIM cell scheduling algorithm [19]. In addition, we propose another algorithm to successively promote the performance of IP switch, and discuss the relation between the starvation and the average packet delay.