Trie-tree data structure for IP lookup in virtual routers
Sanal yönlendiricilerde IP arama için ağaç veri yapısı
- Tez No: 368818
- Danışmanlar: DOÇ. DR. CÜNEYT FEHMİ BAZLAMAÇCI, YRD. DOÇ. DR. OĞUZHAN ERDEM
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 111
Özet
Sanal yönlendiriciler ağ servislerinin artan taleplerini karşılamak için önemli bir çözüm olmuştur. Sanal yönlendiriciler tek bir donanım platformu kullanarak birden fazla ağa eş zamanlı olarak hizmet sunabilirler; böylece tasarruf sağlarlar. Sanal yönlendiriciler farklı internet servis sağlayıcılarına ait birden fazla yönlendirme tablosunu idame ettirebilir, her bir internet servis sağlayıcı için IP adresi arama ve yönlendirme faaliyetlerini ortak bir platform kullanarak yürütebilirler. Sanal yönlendiricilerde IP adresi arama işlemi paketlerin taşıdığı servis sağlayıcı bilgisi kullanılarak gerçekleştirilir. IP adresi arama için çeşitli yazılım ve donanım çözümleri geliştirilmiştir. Donanımsal çözüm olarak TCAM ve SRAM kullanılırken, yazılım tabanlı çözümlerde daha yavaş olan ağaç yapıları yer alır. Donanımsal ortamın bellek imkanlarının kısıtlı olması uygulamalardaki temel darboğazı oluşturur. Servis sağlayıcılara ait yönlendirme tabloları ayrı ayrı saklanabilir ancak bunun için büyük miktarda bellek gerekmektedir, bu durumda sanal yönlendiriciler önemli bir bellek kazancı sağlayamamaktadır. Tablolardaki benzerliklerden yararlanabilmek için tablolar genellikle birleştirilerek tek bir ortak veri yapısı oluşturulmaktadır. Bellek büyüklüğünü azaltmak, adres arama performansını yükseltmek ve güncelleme işlemleri sanal yönlendiriciler için öne çıkan önemli konulardır. Adres arama performansı gecikme süresi ve birim zamanda gerçekleşen arama sayısı kriterleri ile değerlendirilir. Bu tez çalışmasında, birleştirilmiş bir ağaç (trie) veri yapısı önerilmiş ve bellek ihtiyacının azaltılması hedeflenirken, arama ve güncelleme işlemlerinde de verimlilik sağlanmıştır. IPv4/IPv6 çekirdek ve kenar yönlendiricilere ait gerçek prefix tabloları birleştirilerek tek bir ağaç (trie) oluşturulmuştur. Birleştirilmiş ağaçtaki bazı bölümlerin az sayıda prefix verisi saklamak için yüksek sayıda boş hücre bulundurduğu gözlenmiştir. Çalışmanın çıkış noktası, ağaçtaki bu düşük yoğunluklu bölgeleri ağacın yapısını değiştirmeden ayıklayarak bellek kullanımını azaltmaktır. Esas ağaçtan alınan prefix verileri ikinci bir ağaç (2-3 tree) kullanarak saklanacaktır. 2-3 ağaç yapısı diğer ağaçlara göre hızlı güncelleme yeteneğinden dolayı tercih edilmiştir. Budama ölçütü prefix verilerinin çoğunun esas ağaçta (trie) kalmasını sağlayacak şekilde belirlenmiştir. Önerdiğimiz yapı mevcut çözümlerle kıyaslandığında, IPv4 çekirdek yönlendiricilerinde %5, diğer tipteki yönlendiricilerde %35 seviyelerinde bellek tasarrufu elde etmiştir. Böylece bellek etkinliği arttırılmış ve her bir güncellemenin tek bir yazma mesajı ile gerçekleştirilmesine olanak sağlanmıştır. Önerdiğimiz yapı her bir adres arama işlemini bir saat döngüsünde gerçekleştirebilir niteliktedir ve gecikme süresi de trie yapısı kullanan diğer çözümler ile eşdeğerdir.
Özet (Çeviri)
Virtual router is an essential solution to fulfill the increasing demands of network services. A virtual router, having a single hardware platform, serves several networks concurrently and hence provides cost saving. A virtual router maintains multiple forwarding tables that belong to separate internet service providers (ISPs) and performs IP lookup and forwarding functionality for each ISP in one common platform. IP lookup in a virtual router is performed by inspecting the incoming packets that also carry information about their ISPs. There exist various software and hardware IP lookup solutions in the literature. In software solutions tree or trie based data structures are usually employed which are relatively slower. Hardware solutions use TCAMs or SRAMs and are much faster. Limited on-chip memory is the main bottleneck for hardware implementations. If all ISP forwarding tables of a virtual router are stored separately then a large amount of memory is required and there occurs no benefit for having a virtual router. Therefore tables are usually merged in such a way that the overlapping parts are stored in one common data structure more efficiently. Decreasing the size of the memory and increasing the performance of look up and update tasks are among the primary concerns and challenges in virtual routers. Lookup performance is considered by means of latency and throughput issues. In this thesis, we investigate and propose an efficient trie overlapping approach and aim to decrease the memory requirement while achieving a good IP lookup and update performance. During this study, we examine real life prefix tables that belong to existing routers. We first merge these IPv4/IPv6 core and edge router tables in a simple manner into a single trie and observe that some parts of the trie use a large number of nodes to store a small number of prefixes. This observation has motivated and led us to reduce the size of the trie by truncating some of these low density subtries without destroying the advantageous trie structure too much. 2-3 tree data structure is then proposed to be used as a secondary storage to keep the deleted prefixes from the trie separately. 2-3 tree is preferred because of its support for incremental updates. Our thesis identifies truncation metrics and we use them to keep most of the prefixes still in the trie. Our approach is evaluated and we have shown that it is possible to achieve around 5% reduction in memory size for IPv4 core routers and around 35% reduction for other type of routers in comparison to existing trie merging solutions. Hence memory efficiency is increased while supporting an update process that is possible using a single write bubble. Our solution achieves one lookup per clock cycle throughput and operates with a latency that is standard among other trie based solutions.
Benzer Tezler
- 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
OĞUZHAN ERDEM
Doktora
İngilizce
2011
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
DOÇ. DR. CÜNEYT BAZLAMAÇCI
- Gövde-Türk: Bir türkçe gövdeleme yöntemi
Gövde-Türk: A turkish stemming method
RABİA TİNTİN
Yüksek Lisans
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÇanakkale Onsekiz Mart ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ SAİT CAN YÜCEBAŞ
- Memory organization in pipelined hierarchical search structures for packet classification
Paket sınıflandırılması için boru hattında hiyerarşik arama yapılarında bellek organizasyonu
ÇAĞLA IRMAK RUMELİLİ
Yüksek Lisans
İngilizce
2013
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. CÜNEYT FEHMİ BAZLAMAÇCI
YRD. DOÇ. DR. OĞUZHAN ERDEM
- Seyitömer Termik Santralı atık uçucu küllerinin yapı malzemesi olarak değerlendirilmesi
Benefication of Seyitömer power plant waste fly ash as a building material
ŞENOL YILMAZ