Parallel and pipelined architectures for high speed ip packet forwarding
Yüksek hızlı internet paketi yönlendirmesi için paralel ve boru hattı davranışlı mimariler
- Tez No: 305132
- Danışmanlar: DOÇ. DR. CÜNEYT BAZLAMAÇCI
- Tez Türü: Doktora
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2011
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Elektronik Mühendisliği Bölümü
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 156
Özet
İ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.
Özet (Çeviri)
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.
Benzer Tezler
- Okunabilir kopyalama algoritmalı DSM sisteminin gerçeklenmesi
Başlık çevirisi yok
ÖZGÜR KORAY ŞAHİNGÖZ
Yüksek Lisans
Türkçe
1998
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. TAKUHİ NADİA ERDOĞAN
- Makine öğrenmesi yöntemleri kullanılarak FPGA tabanlı gerçek zamanlı yeni bir trafik sınıflandırma mimarisi tasarımı
Designing a novel FPGA-based real-time traffic classification engine using machine learning techniques
TUNCAY SOYLU
Doktora
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolTrakya ÜniversitesiHesaplamalı Bilimler Ana Bilim Dalı
DOÇ. DR. OĞUZHAN ERDEM
- VLSI realization of an 8x8 bit pipelined residue arithmetic multiplier
Boru-hattı mimarisi ile artık aritmetiğe göre tasarımlanmış bir 8x8-bitlik çarpıcının çok büyük çapta tümleşik (ÇBÇT) devre olarak gerçekleştirilmesi
FUAT ENVER
Yüksek Lisans
İngilizce
1992
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiPROF. DR. MURAT AŞKAR
- VHDL ile lojik devre tasarımı ve DSP uygulamaları için çarpma bloklarının modellenmesi
Başlık çevirisi yok
SIDDIKA BERNA ÖRS
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET DERVİŞOĞLU
- A/D dönüştürücüler ve 1.5 um CMOS VLSI teknolojisi ile 6 bitlik bir dönüştürücünün tasarımı
A/D converters and design of a 6 bit converter in 1.5 um CMOS VLSI technology
S. NERGİS TURAL
Yüksek Lisans
Türkçe
2002
Elektrik ve Elektronik MühendisliğiYıldız Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. ATİLLA ATAMAN