International Journal of Computer Networks and Applications

Open Access Open Access  Restricted Access Subscription Access

A Hybrid Distance Vector Link State Algorithm: Distributed Sequence Number


Affiliations
1 Department of Computing Machines Systems and Networks, National Research University "MPEI", Krasnokazarmennaya, Moscow, Russian Federation
 

Requirements in data centers to meet the increasing demands on traffic have evolved. There is a need for a simple, scalable routing protocol, which has the flexibility and ease of management to support large networks. Distance vector routing protocols are very simple and easy to implement but they suffer from routing loops. Link state protocols, on the other hand, have the advantages of fast convergence, area division of the routing domain, at the expense of the added complexity of implementation, configuration, and troubleshooting. A new loop free protocol is proposed in this paper that combines the simplicity of the distance vector protocols, loop freedom, and the ability to be used in large scale mesh networks as in link state protocols. The protocol uses a hybrid distance vector link state algorithm. It employs techniques from Enhanced Interior Gateway Routing Protocol (EIGRP), Babel, and Open Shortest Path First Protocol (OSPF). Simplicity, ease of implementation, and scalability make the proposed solution appropriate for large scale networks. Additionally, it can be used to perform the underlay routing in SDN (Software Defined Networks) overlay networks in place of IS-IS (Intermediate-System to Intermediate-System) protocol, which is usually used in these solutions. The combination of distance vector and link state helps to reduce the size of information in the database that is needed to be maintained by each node. It also helps to reduce the overhead and computing load after topology changes.

Keywords

Hybrid Routing Protocol, Loop Free Routing, Distance Vector, Link State, Sequence Number, Babel, DUAL, EIGRP, OSPF.
User
Notifications
Font Size

  • Benzekki, Kamal, et al. “Software-Defined Networking (SDN): A Survey.” Security and Communication Networks, vol. 9, no. 18, 2016, pp. 5803–33. Wiley Online Library, doi:https://doi.org/10.1002/sec.1737

  • Raza MH, Sivakumar SC, Nafarieh A, Robertson B. “A comparison of software defined network (SDN) implementation strategies”. Procedia Computer Science 2014;32:1050{5. doi:10.1016/j.procs.2014.05.532

  • Sridhar, T., et al. Virtual EXtensible Local Area Network (VXLAN): A Framework for Overlaying Virtualized Layer 2 Networks over Layer 3 Networks. Tech. Rep., Aug. 2014. [Online]. Available: https://doi.org/10.17487/rfc7348

  • Gross, Jesse, et al. Geneve: Generic Network Virtualization Encapsulation. Tech. Rep., Nov. 2020. [Online]. Available: https://doi.org/10.17487/rfc8926

  • Lewis, Darrel, et al. The Locator/ID Separation Protocol (LISP). Tech. Rep., Jan. 2013. [Online]. Available: https://doi.org/10.17487/rfc6830

  • Premji, Ariff, et al. “Use of BGP for Routing in Large-Scale Data Centers”. Tech. Rep., Aug. 2016. [Online]. Available: https://doi.org/10.17487/rfc7938

  • Medhi, Deepankar, and Karthik Ramasamy. Network Routing: Algorithms, Protocols, and Architectures. 2nd edition, Elsevier, Morgan Kaufmann Publishers, an imprint of Elsevier, 2018.

  • D. Savage, J. Ng, S. Moore, D. Slice, P. Paluch, and R. White, “Cisco's enhanced interior gateway routing protocol (EIGRP),” Tech. Rep., May 2016. [Online]. Available: https://doi.org/10.17487/rfc7868

  • A. Bruno, CCIE Routing and Switching Exam Certification Guide, ser. Certification and training series. Cisco Press, 2002. [Online]. Available: https://books.google.ru/books?id=NzYb1pPZTB0C

  • J. Garcia-Lunes-Aceves, “Loop-free routing using diffusing computations,” IEEE/ACM Transactions on Networking, vol. 1, no. 1, pp. 130–141, 1993. [Online]. Available: https://doi.org/10.1109/90.222913

  • H. Khayou, M. A. Rudenkova, and L. I. Abrosimov, “On the algebraic theory of loop free routing,” in Distributed Computer and Communication Networks. Springer International Publishing, 2020, pp. 161–175. [Online]. Available: https://doi.org/10.1007/978-3-030-66471-8_14

  • J. Chroboczek and D. Schinazi, “The babel routing protocol,” Tech. Rep., Jan. 2021. [Online]. Available: https://doi.org/10.17487/rfc8966

  • C. E. Perkins and P. Bhagwat, “Highly dynamic destinationsequenced distance-vector routing (DSDV) for mobile computers,” ACM SIGCOMM Computer Communication Review, vol. 24, no. 4, pp. 234–244, Oct. 1994. [Online]. Available: https://doi.org/10.1145/190809.190336

  • C. Perkins, E. Belding-Royer, and S. Das, “Ad hoc on-demand distance vector (AODV) routing,” Tech. Rep., Jul. 2003. [Online]. Available: https://doi.org/10.17487/rfc3561

  • A. J. T. Gurney and T. G. Griffin, “Lexicographic products in metarouting,” in 2007 IEEE International Conference on Network Protocols. IEEE, Oct. 2007. [Online]. Available: https://doi.org/10.1109/icnp.2007.4375842

  • H. Khayou and B. Sarakbi, “A validation model for non-lexical routing protocols,” Journal of Network and Computer Applications, vol. 98, pp. 58–64, Nov. 2017. [Online]. Available: https://doi.org/10.1016/j.jnca.2017.09.006

  • J. Sobrinho, “Algebra and algorithms for QoS path computation and hop-by-hop routing in the internet,” in Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213), vol. 2. IEEE, 2001, pp. 727–735 vol.2. [Online]. Available: https://doi.org/10.1109/infcom.2001.916261

  • J. L. Sobrinho, “Network routing with path vector protocols,” in Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications – SIGCOMM '03. ACM Press, 2003. [Online]. Available: https://doi.org/10.1145/863955.863963

  • J. Sobrinho, “An algebraic theory of dynamic network routing,” IEEE/ACM Transactions on Networking, vol. 13, no. 5, pp. 1160–1173, Oct. 2005. [Online]. Available: https://doi.org/10.1109/tnet.2005.857111

  • T. G. Griffin, “Lecture notes in an algebraic approach to internet routing,” 2010. [Online]. Available: https://www.cl.cam.ac.uk/teaching/1011/L11/

  • T. G. Griffin and A. J. T. Gurney, “Increasing bisemigroups and algebraic routing,” in Relations and Kleene Algebra in Computer Science. Springer Berlin Heidelberg, 2008, pp. 123–137. [Online]. Available: https://doi.org/10.1007/978-3-540-78913-0_11

  • Y. Yang and J. Wang, “Design guidelines for routing metrics in multihop wireless networks,” in IEEE INFOCOM 2008 - The 27th Conference on Computer Communications. IEEE, Apr. 2008. [Online]. Available: https://doi.org/10.1109/infocom.2008.222

  • E. W. Dijkstra and C. Scholten, “Termination detection for diffusing computations,” Information Processing Letters, vol. 11, no. 1, pp. 1–4, Aug. 1980. [Online]. Available: https://doi.org/10.1016/0020-0190(80)90021-6

  • J. Jaffe and F. Moss, “A responsive distributed routing algorithm for computer networks,” IEEE Transactions on Communications, vol. 30, no. 7, pp. 1758–1762, Jul. 1982. [Online]. Available: https://doi.org/10.1109/tcom.1982.1095632

  • Brugnoli, Ignacio, et al. “Tunnelless SDN Overlay Architecture for Flow Based QoS Management.” 2021 24th Conference on Innovation in Clouds, Internet and Networks and Workshops (ICIN), IEEE, 2021, pp. 62–69. DOI.org (Crossref), doi:10.1109/ICIN51074.2021.9385539

  • McPherson, D., et al. Border Gateway Protocol (BGP) Persistent Route Oscillation Condition. Tech. Rep., Aug. 2002. [Online]. Available: https://doi.org/10.17487/rfc3345

  • Yu, Chen, et al. “Intelligent Optimizing Scheme for Load Balancing in Software Defined Networks.” 2017 IEEE 85th Vehicular Technology Conference (VTC Spring), IEEE, 2017, pp. 1–5. DOI.org (Crossref), doi:10.1109/VTCSpring.2017.8108541

  • Chiang, Mei-Ling, et al. “SDN-Based Server Clusters with Dynamic Load Balancing and Performance Improvement.” Cluster Computing, vol. 24, no. 1, Mar. 2021, pp. 537–58. Springer Link, doi:10.1007/s10586-020-03135-w

  • Liu, Yazhi, et al. “Load Balancing Oriented Predictive Routing Algorithm for Data Center Networks.” Future Internet, vol. 13, no. 2, Feb. 2021, p. 54. www.mdpi.com, doi:10.3390/fi13020054

  • J. Moy, “OSPF version 2,” Tech. Rep., Apr. 1998. [Online]. Available: https://doi.org/10.17487/rfc2328.


Abstract Views: 421

PDF Views: 2




  • A Hybrid Distance Vector Link State Algorithm: Distributed Sequence Number

Abstract Views: 421  |  PDF Views: 2

Authors

Hussein Khayou
Department of Computing Machines Systems and Networks, National Research University "MPEI", Krasnokazarmennaya, Moscow, Russian Federation
Margarita A. Orlova
Department of Computing Machines Systems and Networks, National Research University "MPEI", Krasnokazarmennaya, Moscow, Russian Federation
Leonid I. Abrosimov
Department of Computing Machines Systems and Networks, National Research University "MPEI", Krasnokazarmennaya, Moscow, Russian Federation

Abstract


Requirements in data centers to meet the increasing demands on traffic have evolved. There is a need for a simple, scalable routing protocol, which has the flexibility and ease of management to support large networks. Distance vector routing protocols are very simple and easy to implement but they suffer from routing loops. Link state protocols, on the other hand, have the advantages of fast convergence, area division of the routing domain, at the expense of the added complexity of implementation, configuration, and troubleshooting. A new loop free protocol is proposed in this paper that combines the simplicity of the distance vector protocols, loop freedom, and the ability to be used in large scale mesh networks as in link state protocols. The protocol uses a hybrid distance vector link state algorithm. It employs techniques from Enhanced Interior Gateway Routing Protocol (EIGRP), Babel, and Open Shortest Path First Protocol (OSPF). Simplicity, ease of implementation, and scalability make the proposed solution appropriate for large scale networks. Additionally, it can be used to perform the underlay routing in SDN (Software Defined Networks) overlay networks in place of IS-IS (Intermediate-System to Intermediate-System) protocol, which is usually used in these solutions. The combination of distance vector and link state helps to reduce the size of information in the database that is needed to be maintained by each node. It also helps to reduce the overhead and computing load after topology changes.

Keywords


Hybrid Routing Protocol, Loop Free Routing, Distance Vector, Link State, Sequence Number, Babel, DUAL, EIGRP, OSPF.

References





DOI: https://doi.org/10.22247/ijcna%2F2021%2F209188