Topology-aware fast re-route algorithms for fault tolerant networking

Abstract

Haberleşme ağlarındaki gerçek zamanlı servisler, katı servis kalitesi gereksinimlerinin karşılanabilmesi için hata toleranslı bir veri iletimini gerektirirler. İnternet Mühendisliği Görev Gücü (Internet Engineering Task Force), ağ hataları süresince IP paketlerinin kesintisiz iletimini sağlayan tam hata kapsamasına sahip IP Hızlı Yeniden Yönlendirme (IP Fast Re-Route - IPFRR) teknolojilerinin standartlaştırılması üzerinde çalışmaktadır. Çoklu Topoloji Yönlendirmesi tabanlı IPFRR (Multi Topology Routing based IPFRR -MT-IPFRR) teknolojileri, arızalanması muhtemel olan ağ bileşenlerinden sakınan alternatif yönlendirme tablolarının hesaplanması için sanal topolojiler (ST) kullanırlar. Bu tezde, MT-IPFRR mekanizmalarından olan Çoklu Yönlendirme Konfigürasyonlarının (Multiple Routing Configurations - MRC) ve Azami Fazlalık Ağaçlarının (Maximally Redundant Trees - MRT) performanslarını kıyaslamaktayız. Sonuçlar, MRC 'ye ait alternatif güzergah uzunlukları ağdaki düğüm sayısı ve link yoğunluğu arttıkça sadece çok az değişirken MRT'ye ait alternatif güzergah uzunluklarının ölçeklenebilir olmadığını göstermektedir. Bunun, IP ağlardaki düğümler arasındaki erişilebilirliği iyileştirmek için kullanılacak MT-IPFRR mekanizmasının seçimine kılavuzluk edecek önemli bir ölçeklenebilirlik sonucu olduğuna inanmaktayız. Ayrıca, MRC 'nin ayrıntılı bir topolojik bağımlılık analizini sunmaktayız. Otomatik topolojik analiz aracımızı kullanarak, MRC 'nin performansı ile topolojik karakteristikler arasında önemli bir bağımlılığın bulunduğunu tespit etmekteyiz. MRC, bir ağ topolojisinin içerdiği, derecesi ağdaki diğer düğümlerin derecelerinden çok daha büyük olan merkezi (hub) düğümlerin sayısının artması durumunda, tam alternatif güzergah kapsaması sağlayabilmesi için daha fazla sayıda ST oluşturmaya ihtiyaç duymaktadır. Topolojik analiz sonuçlarımızdan esinlenerek, MRC 'nin operasyonel karmaşıklığının iyileştirilmesi için MRC 'nin kullandığı ST sayısını azaltacak sezgisel algoritmalar önermekteyiz. Sayısal deneylerimiz, sezgisel algoritmalarımızın, topolojik karakteristiklerin sistematik analizinin etkinliğini doğrulayarak, MRC 'nin performansını belirgin bir şekilde iyileştirdiğini göstermektedir. Ayrıca, kendi kendini onaran hata toleranslı Yazılım Tabanlı Ağların oluşturulabilmesini hedefleyen yeni bir MT-IPFRR yöntemi önermekteyiz. Deneysel sonuçlarımız, yaklaşımımızın, tepkisel (reactive) onarım sürecine kıyasla hata onarım süresini önemli ölçüde azalttığını göstermektedir. Real-time services in communication networks require a fault tolerant data transmission to support their stringent quality of service requirements. The Internet Engineering Task Force has been working on standardizing IP Fast Re-Route (IPFRR) technologies with a full failure coverage which provide seamless forwarding of IP packets during network failures. Multi Topology Routing based IPFRR (MT-IPFRR) technologies use virtual topologies (VTs) to compute alternate routing tables to recover from failures. In this thesis, we compare the performances of the MT-IPFRR mechanisms, namely, Multiple Routing Configurations (MRC) and Maximally Redundant Trees (MRT). The results show that the alternate path lengths of the MRC are scalable with respect to the network size and density as opposed to the case for the MRT. We also provide an elaborate topological dependency analysis of the MRC. Using our automated topological analysis tool, we discover a significant correlation between the performance of the MRC and the heterogeneity level of a topology, namely, the tendency to have hub nodes, whose degree is much higher than the rest of the network. Inspired by our topological analysis results, we propose heuristic algorithms to reduce the number of VTs used by the MRC to decrease its operational complexity. Finally, we propose a new MT-IPFRR technique leading to selfrecovering Software Defined Networks.