Parallel and pipelined architectures for high speed ip packet forwarding

İnternet kullanıcı sayısı ve trafik hacmindeki önemli artış, ağ yönlendirici tasarımı için yeni sorunlar ortaya çıkarmaktadır. Mevcut yönlendiriciler internet trafik artışına ayak uydurabilmek için, yüksek hızda bilgi hatlarını ve çok sayıda hat kartlarının kullanımını desteklemelidir, buda fiziksel alan, güç ve bellek kullanımında artışa gereksinim ortaya çıkarır.Bir yönlendiricinin temel görevleri arasında yer alan paket yönlendirme, internet altyapısı için performans dargeçidi durumundadır. Genel olarak, paket yönlendirme algoritmalarının çoğunluğu yazılım ile gerçeklenir. Fakat, donanım tabanlı çözümlerde yüksek çıkan iş miktarına sahip olmalarından ötürü son yıllarda popüler olmuşlardır. Çıkan iş oranının yanısıra, bellek verimliliği, artımlı / dinamik güncellemeler ve güç tüketimi paket yönlendirme mimarileri için temel başarım metrikleridir. Ağ yönlendiricileri için donanım tabanlı paket anahtarlama mimarileri içerik adreslenebilir bellek (TCAM) tabanlı ve dinamik/statik rastgele erişimli bellek (DRAM/SRAM) tabanlı çözümler olarak iki gruba ayrılabilir. TCAM- tabanlı yapılar basittir ve bu nedenle bugünkü yönlendiriciler için popüler çözümlerdir. Fakat TCAM pahalıdır, çok güç harcar ve yeni adresleme yapılarına ve yönlendirme protokollerineuyumlulukları azdır. Diğer yandan, SRAM daha yüksek yoğunluğa, düşük güç tüketimine, ve yüksek hıza sahiptir. SRAM tabanlı çözümlerde en uzun öntakı eşleşmesi (LPM) yapmak için kullanılan genel veri yapısı bir çeşit ağaç veri yapısıdır. Bu çözümlerde eşleşen en uzun öntakıyı bulmak için çok sayıda bellek giriş/çıkışı gerekmektedir. Bu nedenle çıkan iş oranını iyileştirebilmek için paralel ve boru hattı davranışlı teknikler kullanılmaktadır.Bu tezde yüksek başarımlı paket yönlendirme için TCAM ve SRAM tabanlı, paralel ve boru hattı davranışlı mimarileri incelendi. TCAM tabanlı paralel IP paket yönlendirme mimarisinin üzerine başarımını arttırmak için, bellek etkin bağımsız öntakı seti oluşturma algoritmasının kullanımını önerdik. Bu tezin temel katkısı olarak, öntakı ağacı kullanan IP paket araması için SRAM tabanlı, paralel, birbirini kesen ve değişken uzunluklu çoklu boru hatlı yeni bir dizilim yapısı (SAFIL) tasarladık. SAFIL üzerine inşa edilmis¸çift giriş çıkışlı SRAM tabanlı daha yüksek çıkan iş gücüne sahip bir IP arama mimarisi (SAFILD) de önerdik. IParaması için geleneksel öntakı ağaç yapısına alternatif olarak ise sıkışık kümelenmiş ağaç (CCT) olarak adlandırdığımız bellek etkin bir veri yapısı önerdik. Ayrıca, alan programlanabilir kapı dizilimi (FPGA) üzerinde yüksek bas¸arımlı IPv4/v6 araması ic¸in yeni bir boru hattı davranışlı birleştirilmiş uzunluk-içtakı araması yapan mimariyi (CLIPS) geliştirdik. Son olarak, paket sınıflandırması için bellek kullanımı etkin kümelenmiş sıradüzensel bir arama yapısı (CHSS) tasarladık. CHSS için ayrıca, FPGA üzerinde uygulanan doğrusal, boru hattı davranışlı SRAM tabanlı bir mimari önerdik. A substantial increase in the number of internet users and the traffic volume bring new challengesfor network router design. The current routers need to support higher link data rates and large number of line cards to accommodate the growth of the internet traffic, which necessitate an increase in physical space, power and memory use.Packet forwarding, which is one of the major tasks of a router, has been a performance bottleneckin internet infrastructure. In general, most of the packet forwarding algorithms are implemented in software. However, hardware based solutions has also been popular in recent years because of their high throughput performance. Besides throughput, memory efficiency, incremental/dynamic updates and power consumption are the basic performance challenges for packet forwarding architectures. Hardware-based packet forwarding engines for network routers can be categorized into two groups that are ternary content addressable memory (TCAM) based and dynamic/static random access memory (DRAM/SRAM) based solutions. TCAM-based architectures are simple and hence popular solutions for today?s routers. However, they are expensive, power-hungry, and oer little adaptability to new addressing and routing protocols. On the other hand, SRAM has higher density, lower power consumption, and higher speed. The common data structure used in SRAM-based solutions for performing longest prefix matching (LPM) is some type of a tree. In these solutions, multiple memoryaccesses are required to find the longest matched prefix. Therefore, parallel and pipelining techniques are used to improve the throughput.This thesis studies TCAM and SRAM based parallel and pipelined architectures for high performance packet forwarding. We proposed to use a memory efficient disjoint prefix set algorithm on TCAM based parallel IP packet forwarding engine to improve its performance. As a fundamental contribution of this thesis, we designed an SRAM based parallel, intersecting and variable length multi-pipeline array structure (SAFIL) for trie-based internet protocol (IP) lookup. We also proposed a novel dual port SRAM based high throughput IP lookup engine (SAFILD) which is built upon SAFIL. As an alternative to traditional binary trie, we proposed a memory efficient data structure called compact clustered trie (CCT) for IP lookup. Furthermore, we developed a novel combined length-infix pipelined search (CLIPS) architecture for high performance IPv4/v6 lookup on FPGA. Finally, we designed a memory efficientclustered hierarchical search structure (CHSS) for packet classification. A linear pipelined SRAM-based architecture for CHSS which is implemented on FPGA is also proposed. 156