Geri Dön

Trie-tree data structure for IP lookup in virtual routers

Sanal yönlendiricilerde IP arama için ağaç veri yapısı

  1. Tez No: 368818
  2. Yazar: DİLEK BAYSAL
  3. Danışmanlar: DOÇ. DR. CÜNEYT FEHMİ BAZLAMAÇCI, YRD. DOÇ. DR. OĞUZHAN ERDEM
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2014
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2011

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik ve Elektronik Mühendisliği Bölümü

    DOÇ. DR. CÜNEYT BAZLAMAÇCI

  2. 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

    Türkçe

    2018

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÇanakkale Onsekiz Mart Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ SAİT CAN YÜCEBAŞ

  3. 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

    İngilizce

    2013

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. CÜNEYT FEHMİ BAZLAMAÇCI

    YRD. DOÇ. DR. OĞUZHAN ERDEM

  4. 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

    Yüksek Lisans

    Türkçe

    Türkçe

    1992

    Metalurji Mühendisliğiİstanbul Teknik Üniversitesi

    DOÇ. DR. OSMAN T. ÖZKAN