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

作　　者：Zhang Yongtang Fan Bo 

机构地区：[1]Department of Computer Science and Technology, Guangdong Neusoft Institute, Foshan 528225, China [2]Guangdong Key Laboratory of Big Data Analysis and Processing, Guangzhou 510006, China

出　　处：《The Journal of China Universities of Posts and Telecommunications》2017年第6期14-23,共10页中国邮电高校学报（英文版）

基　　金：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.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 

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术]