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

• Networks • 上一篇    下一篇

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

Zhang Yongtang, Fan Bo   

  1. 广东东软学院
  • 收稿日期: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   

  1. 广东东软学院
  • 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).

摘要: 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