International Journal of Computer Networks and Applications (IJCNA)

Published By EverScience Publications

ISSN : 2395-0455

International Journal of Computer Networks and Applications (IJCNA)

International Journal of Computer Networks and Applications (IJCNA)

Published By EverScience Publications

ISSN : 2395-0455

A Hybrid Distance Vector Link State Algorithm: Distributed Sequence Number

Author NameAuthor Details

Hussein Khayou, Margarita A. Orlova, Leonid I. Abrosimov

Hussein Khayou[1]

Margarita A. Orlova[2]

Leonid I. Abrosimov[3]

[1]Department of Computing Machines Systems and Networks, National Research University "MPEI", Krasnokazarmennaya, Moscow, Russia

[2]Department of Computing Machines Systems and Networks, National Research University "MPEI", Krasnokazarmennaya, Moscow, Russia

[3]Department of Computing Machines Systems and Networks, National Research University "MPEI", Krasnokazarmennaya, Moscow, Russia

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.

Index Terms

Hybrid Routing Protocol

Loop Free Routing

Distance Vector

Link State

Sequence Number

Babel

DUAL

EIGRP

OSPF

Reference

  1. 1.
    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
  2. 2.
    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
  3. 3.
    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
  4. 4.
    Gross, Jesse, et al. Geneve: Generic Network Virtualization Encapsulation. Tech. Rep., Nov. 2020. [Online]. Available: https://doi.org/10.17487/rfc8926
  5. 5.
    Lewis, Darrel, et al. The Locator/ID Separation Protocol (LISP). Tech. Rep., Jan. 2013. [Online]. Available: https://doi.org/10.17487/rfc6830
  6. 6.
    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
  7. 7.
    Medhi, Deepankar, and Karthik Ramasamy. Network Routing: Algorithms, Protocols, and Architectures. 2nd edition, Elsevier, Morgan Kaufmann Publishers, an imprint of Elsevier, 2018.
  8. 8.
    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
  9. 9.
    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
  10. 10.
    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
  11. 11.
    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
  12. 12.
    J. Chroboczek and D. Schinazi, “The babel routing protocol,” Tech. Rep., Jan. 2021. [Online]. Available: https://doi.org/10.17487/rfc8966
  13. 13.
    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
  14. 14.
    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
  15. 15.
    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
  16. 16.
    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
  17. 17.
    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
  18. 18.
    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
  19. 19.
    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
  20. 20.
    T. G. Griffin, “Lecture notes in an algebraic approach to internet routing,” 2010. [Online]. Available: https://www.cl.cam.ac.uk/teaching/1011/L11/
  21. 21.
    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
  22. 22.
    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
  23. 23.
    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
  24. 24.
    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
  25. 25.
    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
  26. 26.
    McPherson, D., et al. Border Gateway Protocol (BGP) Persistent Route Oscillation Condition. Tech. Rep., Aug. 2002. [Online]. Available: https://doi.org/10.17487/rfc3345
  27. 27.
    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
  28. 28.
    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
  29. 29.
    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
  30. 30.
    J. Moy, “OSPF version 2,” Tech. Rep., Apr. 1998. [Online]. Available: https://doi.org/10.17487/rfc2328.
SCOPUS
SCImago Journal & Country Rank