Non-SPF routing algorithm based on ordered semi-group preference algebra

doi:10.1016/S1005-8885(17)60238-3

中国邮电高校学报(英文) ›› 2017, Vol. 24 ›› Issue (6): 14-23.doi: 10.1016/S1005-8885(17)60238-3

Non-SPF routing algorithm based on ordered semi-group preference algebra

Zhang Yongtang， Fan Bo

广东东软学院

收稿日期:2017-04-18 修回日期:2017-09-25 出版日期:2017-12-30 发布日期:2017-12-01
通讯作者: 张永棠 E-mail:gov211@163.com
基金资助:
the National Natural Science Foundation of China (61363047), the Open Research Fund of Guangdong Key Laboratory of Big Data Analysis and Processing (2017007), the Foshan Science and Technology Innovation Project (2016AG100792).

Non-SPF routing algorithm based on ordered semi-group preference algebra

Zhang Yongtang， Fan Bo

广东东软学院

Received:2017-04-18 Revised:2017-09-25 Online:2017-12-30 Published:2017-12-01
Contact: 张永棠 E-mail:gov211@163.com
Supported by:
the National Natural Science Foundation of China (61363047), the Open Research Fund of Guangdong Key Laboratory of Big Data Analysis and Processing (2017007), the Foshan Science and Technology Innovation Project (2016AG100792).

摘要/Abstract

摘要： Layer 2 network technology is extending beyond its traditional local area implementation and finding wider acceptance in provider’s metropolitan area networks and large-scale cloud data center networks. This is mainly due to its plug-and-play capability and native mobility support. Many efforts have been put to increase the bisection bandwidth in layer 2 network, which has been constrained by the spanning tree protocol (STP) that layer 2 network uses for preventing looping. The recent trend is to incorporate layer 3’s routing approach into layer 2 network so that multiple paths can be used for forwarding traffic between any source-destination (S-D) node pair. Equal cost multipath (ECMP) is one such example. However, ECMP may still be limited in generating multiple paths due to its shortest path (lowest cost) requirement. In this paper, we consider a non-shortest-path routing approach, called equal preference multipath (EPMP) based on ordered semi group theory, which can generate more paths than ECMP. In EPMP routing, all the paths with different traditionally-defined costs, such as hops, bandwidth, etc., can be determined equally now and thus they become equal candidate paths. By the comparative tests with ECMP, EPMP routing not only generates more paths, provides 15% higher bisection bandwidth, but also identifies bottleneck links in a hierarchical network when different traffic patterns are applied. EPMP is more flexible in controlling the number and length of multipath generation. Simulation results indicate the effectiveness of the proposed algorithm. It is a good reference for non-blocking running of big datacenter networks.

关键词: non-SPF routing algorithm, algebraic routing, equal preference multipath, datacenter networks

Abstract: Layer 2 network technology is extending beyond its traditional local area implementation and finding wider acceptance in provider’s metropolitan area networks and large-scale cloud data center networks. This is mainly due to its plug-and-play capability and native mobility support. Many efforts have been put to increase the bisection bandwidth in layer 2 network, which has been constrained by the spanning tree protocol (STP) that layer 2 network uses for preventing looping. The recent trend is to incorporate layer 3’s routing approach into layer 2 network so that multiple paths can be used for forwarding traffic between any source-destination (S-D) node pair. Equal cost multipath (ECMP) is one such example. However, ECMP may still be limited in generating multiple paths due to its shortest path (lowest cost) requirement. In this paper, we consider a non-shortest-path routing approach, called equal preference multipath (EPMP) based on ordered semi group theory, which can generate more paths than ECMP. In EPMP routing, all the paths with different traditionally-defined costs, such as hops, bandwidth, etc., can be determined equally now and thus they become equal candidate paths. By the comparative tests with ECMP, EPMP routing not only generates more paths, provides 15% higher bisection bandwidth, but also identifies bottleneck links in a hierarchical network when different traffic patterns are applied. EPMP is more flexible in controlling the number and length of multipath generation. Simulation results indicate the effectiveness of the proposed algorithm. It is a good reference for non-blocking running of big datacenter networks.

Key words: non-SPF routing algorithm, algebraic routing, equal preference multipath, datacenter networks

Zhang Yongtang， Fan Bo. Non-SPF routing algorithm based on ordered semi-group preference algebra[J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2017, 24(6): 14-23.

参考文献

1. Allan D, Ashwood-Smith P, Bragg N, et al. Shortest path bridging: efficient control of larger Ethernet networks. IEEE Communications Magazine, 2010, 48(4): 128-135

2. Fedyk D, Ashwood-Smith P, Allan D, et al. IS-IS extensions supporting IEEE 802.1aq shortest path bridging. IETF RFC 6329. 2012: 29-40

3. Perlman R. Eastlake 3rd D, Dutt D, et al. Routing (RBridges): base protocol specification. IETF RFC 6325. 2011: 125-132

4. Tsao Y C, Hou T C. Bridge priority provisioning for maximizing equal cost shortest path availability. Proceedings of the IEEE 16th International Conference on High Performance Switching and Routing (HPSR’15), Jun 1-4, 2015, Budapest, Hungary. Piscataway, NJ, USA: IEEE, 2015: 6p

5. Amaral P, Bernardo L, Pinto P. Multipath policy routing using destination based hop-by-hop forwarding. Proceedings of the IEEE 21st International Conference on Network Protocols (ICNP’13), Oct 7-10, 2013, Goettingen, Germany. Piscataway, NJ, USA: IEEE, 2013: 6p

6. Amaral P, Bernardo L, Pinto P F, et al. An L2 policy based multipath fabric. Proceedings of the 2014 IEEE International Conference on Communications (ICC’14), Jun 10-14, 2014, Sydney, Australia. Piscataway, NJ, USA: IEEE, 2014: 3607-3613

7. Griffin T G, Gurney A J T. Increasing bisemigroups and algebraic routing. Proceedings of the 10th International Conference on Relations and Kleene Algebra in Computer Science and 5th International Conference on Applications of Kleene Algebra, (RelMiCS/AKA’08), Apr 7-11, 2008, Frauenwörth, Germany. LNCS 4988. Berlin, Germany: Springer-Verlag, 2008: 123-137

8. Yang S Q, Tian X D, Yu B T, et al. A matching model of mathematical expressions with FDS based index. International Journal of Machine Learning and Cybernetics, 2015, 6(6): 993-1004

9. Tso F P, Hamilton G, Weber R, et al. Longer is better: exploiting path diversity in data center networks. Proceedings of the IEEE 33rd International Conference on Distributed Computing Systems (ICDCS’13), Jul 8-11, 2013, Philadelphia, PA, USA. Piscataway, NJ, USA: IEEE, 2013: 430-439

10. Aizawa A, Kohlhase M, Ounis I. NTCIR-10 math pilot task overview. Proceedings of the 10th NTCIR Conference, Jun 18-21, 2013, Tokyo, Japan. 2013: 654-661

11. Lu W C, Sahni S. Low power TCAMs for very large forwarding tables. IEEE Transactions on Networking, 2014, 18(3): 948-959

12. Border A, Mitzenmacher M. Using multiple hash functions to improve IP lookups. Proceedings of the 30th Annual Joint Conference of the IEEE Computer and Communications (INFOCOM’11), Apr 10-15, 2011, Shanghai, China. Piscataway, NJ, USA: IEEE, 2011: 1454-1463

13. Ning P, Cui Y, Reeves D S, et al. Techniques and tools for analyzing intrusion alerts. ACM Transactions on Information and System Security, 2014, 7(2): 274-318

14. Du K, Liu W L, Wang B J. Research on Chinese text clustering method based on semantic relevancy. Information Studies: Theory and Application, 2016, 39(2): 129-133 (in Chinese)

15. Leggieri V, Haouari M, Triki C. The steiner tree problem with delays: a compact formulation and reduction procedures. Discrete Applied Mathematics, 2014, 164(1): 178-190

16. Molnar M, Bellabas A, Lahoud S. The cost optimal solution of the multi-constrained multicast routing problem. Computer Networks, 2012, 56(13): 3136-3149

17. Lu T, Zhu J. Genetic algorithm for energy-efficient QoS multicast routing. IEEE Communications Letters, 2013, 17(1): 31-34

18. Liu Y, Han L G, Cai X S. A kernel density estimation based text classification algorithm. Advanced Science and Technology Letters, 2014, 78(9): 49-54

19. Mtonga K, Yoon E J, Kim H. A pairing based authentication and key establishment scheme for remote monitoring systems. Proceedings of the 5th International Conference on E-infrastructure and E-services for Developing Countries (AFRICOMM’13), Nov 25–27, 2013, Blantyre, Malawi. LNICST 135. Berlin, Germany: Springer-Verlag, 2014: 79-89

20. Singh U R, Singh K M, Roy S. Energy efficient key management analysis using AVL trees in wireless sensor network. International Journal of Engineering Science Invention, 2015, 21(4): 59-70

Non-SPF routing algorithm based on ordered semi-group preference algebra

Non-SPF routing algorithm based on ordered semi-group preference algebra

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价