Generic Fault-Avoidance Routing Protocol for Data Center Networks

1.1. Acronyms & Definitions

DCN - Data Center Network¶

FAR - Fault-Avoidance Routing¶

BRT - Basic Routing Table¶

NRT - Negative Routing Table¶

NDT - Neighbor Devices Table¶

ADT - All Devices Table¶

LFT - Link Failure Table¶

DA - Device Announcement¶

LFA - Link Failure Announcement¶

DLR - Device and Link Request¶

IP - Internet Protocol¶

VM - Virtual Machine¶

3.1. The Impact of Large-scale Networks on Route Calculation

In a large-scale cloud data center network, there may be thousands of routers. Running OSPF or IS-IS in such network will encounter these two challenges: (1) Network convergence time would be too long, which will cause a longer time to elapse for creating and updating the routes. The response time to network failures may be excessively long; (2) High resource consumption. Since a large number of routing protocol packets need to be sent, it causes the routing information consuming too much network bandwidth and CPU(central processing unit) resources, and easily leads to packet loss and makes the challenge (1) more prominent. In order to solve these two challenges, a common practice is to partition a large network into some small areas, where the route calculation runs independently within different areas. However, nowadays the cloud data centers typically require very large internal bandwidth. To meet this requirement, a large number of parallel equivalent links are deployed in a network, such as a Fat-tree network. Partitioning such a network will affect the utilization of routing algorithm on equivalent multi-path and reduce internal network bandwidth requirements. In the FAR routing calculation process, a Basic Routing Table (BRT) is built on local network topology leveraging the regularity of the network topologies. In addition to BRT, FAR also builds a Negative Routing Table (NRT). FAR gradually builds NRT in the process of learning network link failure information, which does not require learning a complete network fault information. FAR does not need to wait for the completion of the network convergence in the process of building these two tables. Therefore, it avoids the problem of excessive network convergence overheads in the route calculation process. In addition, FAR only needs to exchange a small amount of link change information between routers, and hence consumes less network bandwidth.¶

3.2. Issues of Conventional Routing Methods in a Large-scale Network with Giant Number Nodes of Routers

There are many real world scenario where tens of thousands of nodes(or much more nodes) need to be deployed in a flat area, such as infiniband routing and switching system, high-performance computer network, and many IDC(Internet Data Center) networks in China. The similar problems have been existed long ago. People have solved the problems through similar solutions, such as the traditional regular topology-based RFC3619[RFC3619] protocol, the routing protocols of infiniband routing and switching system, and high-performance computer network routing protocol. Infiniband defines a switch-based network to interconnect processing nodes and the I/O nodes. Infiniband can support very large scale networks, use the regularity in topology to simplify its routing algorithm, which is just the same to what we do in FAR. Why OSPF and IS-IS do not work well in a large-scale network with giant number nodes of routers? As we know, the OSPF protocol uses multiple databases, more topological exchange information (as seen in the following example) and complicated algorithm. It requires routers to consume more memory and CPU processing capability. But the processing rate of CPU on the protocol message per second is very limited. When the network expands, CPU will quickly approach its processing limits, and at this time OSPF can not continue to expand the scale of the management. The SPF(Shortest Path First) algorithm itself does not thoroughly solve these problems. On the contrary, the FAR protocol does not need to calculate SPF, which saves calculation time and resources, so FAR does not have the convergence time delay and the additional CPU overheads, which SPF requires. Because in the initial stage, FAR already knows the regular information of the whole network topology and does not need to periodically do SPF operation. One of the examples of "more topological exchange information": In the OSPF protocol, LSA(Link-State Advertisement) floods every 1800 seconds. Especially in the larger network, the occupation of CPU and band bandwidth will soon reach the router's performance bottleneck. In order to reduce these adverse effects, OSPF introduced the concept of Area, which still has not solved the problem thoroughly. By dividing the OSPF Area into several areas, the routers in the same area do not need to know the topological details outside their area. (In comparison with FAR, after OSPF introducing the concept of Area, the equivalent paths cannot be selected in the whole network scope) OSPF can achieve the following results by Area : 1) Routers only need to maintain the same link state databases as other routers within the same Area, without the necessity of maintaining the same link state database as all routers in the whole OSPF domain. 2) The reduction of the link state databases means dealing with relatively fewer LSA, which reduces the CPU consumption of routers; 3) The large number of LSAs flood only within the same Area. But, its negative effect is that the smaller number of routers which can be managed in each OSPF area. On the contrary, because FAR does not have the above disadvantages, FAR can also manage large-scale network even without dividing Areas. The aging time of OSPF is set in order to adapt to routing transformation and protocol message exchange happened frequently in the irregular topology. Its negative effect is: when the network does not change, the LSA needs to be refreshed every 1800 seconds to reset the aging time. In the regular topology, as the routings are fixed, it does not need the complex protocol message exchange and aging rules to reflect the routing changes, as long as LFA mechanism in the FAR is enough. Compared with the LSVR(Link State Vector Routing) protocol, the LSVR protocol has no special requirements for the network topology structure, however, the FAR draft is applicable to the regular topology network architecture and simplifies unnecessary processing. It is a solution proposed to greatly improve the routing efficiency of the regular network topology. The FAR solution is more efficient than the general methods such as LSVR in regular topology. Therefore, in FAR, we can omit many unnecessary processing and the packet exchange. The benefits are fast convergence speed and much larger network scale than other dynamic routing protocol. Now there are some successful implementations of simplified routings in the regular topology in the HPC(High Performance Computing) environment. Conclusion: As FAR needs few routing entries and the topology is regular, the database does not need to be updated regularly. Without the need for aging, there is no need for CPU and bandwidth overhead brought by LSA flood every 30 minutes, so the expansion of the network has no obvious effect on the performance of FAR, which is contrary to OSPF. Comparison of convergence time: The settings of OSPF spf_delay and spf_hold_time can affect the change of convergence time. The convergence time of the network with 2480 nodes is about 15-20 seconds; while the FAR does not need to calculate the SPF, so there is no such convergence time. These issues still exist in rapid convergence technology of OSPF ,ISIS (such as I-SPF, Incremental SPF) and LSVR. The convergence speed and network scale constraint each other. FAR does not have the above problems, and the convergence time is almost negligible. Can FRR(Fast Reroute) solve these problems? IP FRR has some limitations. The establishment of IP FRR backup scheme will not affect the original topology and traffic forwarding which are established by protocol, however, we can not get the information of whereabouts and status when the traffic is switched to an alternate next hop.¶

3.3. Network Addressing Issues

Routers are typically configured with multiple network interfaces, each connected to a subnet. OSPF and other routing algorithms require that each interface of a router must be configured with an IP address. A large-scale data center network may contain thousands of routers and each router has dozens of network interfaces, thus, there are tens of thousands of IP addresses needed to be configured in a data center. It will be very complex to configure and manage a large number of network interfaces and will be difficult to troubleshoot network problems, then network maintenance will be costly and error-prone. In FAR, the device position information is encoded in the IP address of the router. Each router only needs to be assigned a unique IP address according its location, which greatly solves complex network addressing issues in large-scale networks.¶

3.4. Big Routing Table Issues

There are a large number of subnets in the large-scale data center network. A router may build a routing entry for each subnet, and therefore the size of routing tables on each router may be very large. It will increase a router's cost and reduce the querying speed of the routing table. FAR uses two measures to reduce the size of its routing tables: a)It builds a BRT on the regularity of the network topologies; b)It introduces a new routing table, i.e., a NRT. In this way FAR can reduce the size of routing tables to only a few dozen routing entries.¶

3.5. Adaptivity Issues for Routing Algorithms

To implement efficient routing in large-scale datacenters, besides FAR, some other routing methods are proposed for some specific network architectures, such as Fat-tree and BCube. These routing methods are different(from both design and implementation viewpoints) and not compatible with the conventional routing methods, which brings big troubles to network equipment providers to develop new routers supporting various new routing methods. FAR is a generic routing method. With slight modification, FAR method can be applied to most of regular datacenter networks. Furthermore, the structure of routing tables and querying a routing table in FAR are the same as conventional routing method. If FAR is adopted, the workload of developing a new type of router will be significantly decreased.¶

3.6. Virtual Machine Migration Issues

Supporting VM migration is very important for cloud-based datacenter networks. However, in order to support layer-3 routing, routing methods including OSPF and FAR require limiting VM migration within a subnet. For this paradox, the mainstream methods still utilize layer-3 routing on routers or switches, transmit packets encapsulated by IPinIP or MACinIP between hosts by tunnels passing through network to the destination access switch, and then extract original packet out and send it to the destination host. By utilizing the aforementioned methods, FAR can be applied to Fat-tree, MatrixDCN or BCube networks for supporting VM migration in entire network.¶

5.1. Data Tables

Some data tables are maintained on each router in FAR. They are: Neighbor Device Table (NDT): To store neighbor routers and related links. All Devices Table (ADT): To store all routers in the entire network. Link Failures Table (LFT): To store all link failures in the entire network. Basic Routing Table (BRT): To store the candidate routes. Negative Routing Table(NRT): To store the avoiding routes. Device ID: The ID of a neighbor router. Device IP: The IP address of a neighbor router. Port ID: The port ID that a neighbor router is attached to. Link State: The state of the link between a router and its neighbor router. There are two states: Up and Down. Update Time: The time of updating the entry. Device ID: The ID of a neighbor router. Device IP: The IP address of a neighbor router. Type: The type of a neighbor router. State: The state of a neighbor router. There are two states: Up and Down. Update Time: The time of updating the entry. No: The entry number. Router 1 IP: The IP address of one router that a failed link connects to. Router 2 IP: The IP address of another router that a failed link connects to. Timestamp: It identifies when the entry is created. Destination: A destination network Mask: The subnet mask of a destination network. Next Hop: The IP address of a next hop for a destination. Interface: The interface related to a next hop. Update Time: The time of updating the entry. Destination: A destination network. Mask: The subnet mask of a destination network. Next Hop: The IP address of a next hop that should be avoided for a destination. Interface: The interface related to a next hop that should be avoided. Failed Link No: A group of failed link numbers divided by "/", for example 1/2/3. Timestamp: The time of updating the entry. The format of NDT¶

 ----------------------------------------------------------
 Device ID | Device IP | Port ID | Link State | Update Time
 ----------------------------------------------------------

The format of ADT¶

 --------------------------------------------------
 Device ID | Device IP | Type | State | Update Time
 --------------------------------------------------

The format of LFT¶

 --------------------------------------------
 No | Router 1 IP | Router 2 IP | Timestamp
 --------------------------------------------

The format of BRT¶

 -------------------------------------------------------
 Destination | Mask | Next Hop | Interface | Update Time
 -------------------------------------------------------

The format of NRT¶

 -------------------------------------------------------------------
 Destination| Mask| Next Hop| Interface| Failed Link No| Timestamp
 -------------------------------------------------------------------

5.2. Messages

Some protocol messages are exchanged between routers in FAR. Hello Message: This message is exchanged between neighbor routers to learn adjacency. Device Announcement (DA): Synchronize the knowledge of routers between routers. Link Failure Announcement (LFA): Synchronize link failures between routers. Device and Link Request (DLR): When a router starts, it requests the knowledge of routers and links from its neighbors by a DLR message. A FAR Message is directly encapsulated in an IP packet. The protocol field of IP header indicates an IP packet is an FAR message. The four types of FAR messages have same format of packet header, called FAR header (as shown in Figure 2). Version: FAR version Message Type: The type of FAR message. Packet Length: The packet length of the total FAR message. Checksum: The checksum of an entire FAR message. AuType:Authentication type. 0: no authentication, 1: Plaintext Authentication, 2: MD5 Authentication. Authentication: Authentication information. 0: undefined, 1: Key, 2: key ID, MD5 data length and packet number. MD5 data is appended to the backend of the packet. AuType and Authentication can refer to the definition of OSPF packet. For Hello messages, the Message Type in FAR header is set to 1.Besides FAR header, a Hello message(Fig. 3) requires the following fields: Router IP: The router IP address. HelloInterval: The interval of sending Hello messages to neighbor routers. RouterDeadInterval: The interval to set a neighbor router dead(out-of-service). If in the interval time, a router doesn't receive a Hello message from its neighbor router, the neighbor router is treated as dead. Neighbor Router IP: The IP address of a neighbor router. All the neighbor router's addresses should be included in a Hello message. For DA messages(Fig. 4), the Message Type in FAR header is set to 2. Besides FAR header, a DA message includes IP addresses of all the announced routers. For LFA messages(Fig. 5), the Message Type in FAR header is set to 3. Besides FAR header, a LFA message includes all the announced link failures. Left IP: The IP address of the left endpoint router of a link. Right IP: The IP address of the right endpoint router of a link. State: Link state. 0: Up, 1: down For DLR messages(Fig. 6), the Message Type in FAR header is set to 1.Except for FAR header, DLR has no additional fields.¶

 |<--- 1 --->| <--- 1 --->|<--------- 2 ---------->|
 +-----------+------------+------------------------+
 |  Version  |Message Type|    Message Length      |
 +-----------+------------+------------------------+
 |        Checksum        |       AuType           |
 +------------------------+------------------------+
 |                  Authentication                 |
 +-------------------------------------------------+
 |                  Authentication                 |
 +-------------------------------------------------+
 |                   Timestamp                     |
 +-------------------------------------------------+

 |<--- 1 --->| <--- 1 --->|<--------- 2 ---------->|
 +-----------+------------+------------------------+
 |  Version  |Message Type|    Message Length      |
 +-----------+------------+------------------------+
 |        Checksum        |       AuType           |
 +------------------------+------------------------+
 |                  Authentication                 |
 +-------------------------------------------------+
 |                  Authentication                 |
 +-------------------------------------------------+
 |                   Timestamp                     |
 +-------------------------------------------------+
 |                    Router IP                    |
 +------------------------+------------------------+
 |     HelloInterval      |     HelloDeadInterval  |
 +------------------------+------------------------+
 |                Neighbor Router IP               |
 +-------------------------------------------------+
 |                       ...                       |
 +-------------------------------------------------+

 |<----1---->| <----1---->|<----------2----------->|
 +-----------+------------+------------------------+
 |  Version  |Message Type|    Message Length      |
 +-----------+------------+------------------------+
 |        Checksum        |       AuType           |
 +------------------------+------------------------+
 |                  Authentication                 |
 +-------------------------------------------------+
 |                  Authentication                 |
 +-------------------------------------------------+
 |                   Timestamp                     |
 +------------------------+------------------------+
 |                   Router1 IP                    |
 +-------------------------------------------------+
 |                       ...                       |
 +-------------------------------------------------+

 |<----1---->| <----1---->|<----------2----------->|
 +-----------+------------+------------------------+
 |  Version  |Message Type|    Message Length      |
 +-----------+------------+------------------------+
 |        Checksum        |       AuType           |
 +------------------------+------------------------+
 |                  Authentication                 |
 +-------------------------------------------------+
 |                  Authentication                 |
 +-------------------------------------------------+
 |                   Timestamp                     |
 +------------------------+------------------------+
 |                     Left IP                     |
 +-------------------------------------------------+
 |                    Right IP                     |
 +------------------------+------------------------+
 |                      State                      |
 +-------------------------------------------------+
 |                       ...                       |
 +-------------------------------------------------+

 |<----1---->| <----1---->|<----------2----------->|
 +-----------+------------+------------------------+
 |  Version  |Message Type|    Message Length      |
 +-----------+------------+------------------------+
 |        Checksum        |       AuType           |
 +------------------------+------------------------+
 |                  Authentication                 |
 +-------------------------------------------------+
 |                  Authentication                 |
 +-------------------------------------------------+
 |                   Timestamp                     |
 +-------------------------------------------------+

6.1. Neighbor and Link Detection Module(M1)

M1 is responsible for sending and receiving Hello messages, and detecting directly-connected links and neighbor routers. Each Hello message is encapsulated in an IP packet. M1 sends Hello messages periodically to all the active router ports and receives Hello messages from its neighbor routers. M1 detects neighbor routers and directly-connected links according to received Hello Messages and stores these neighbors and links into a Neighbor Devices Table (NDT). Additionally, M1 also stores neighbor routers into an All Devices Table (ADT).¶

6.2. Device Learning Module(M2)

M2 is responsible for sending, receiving, and forwarding device announcement (DA) messages, learning all the routers in the whole network, and deducing faulted routers. When a router starts, it sends a DA message announcing itself to its neighbors and a DLR message requesting the knowledge of routers and links from its neighbors. If M2 module of a router receives a DA message, it checks whether the router encapsulated in the message is in an ADT. If the router is not in the ADT, M2 puts this router into the ADT and forwards this DA message to all the active ports except for the incoming one, otherwise, M2 discards this message directly. If M2 module of a router receives a DLR message, it replies a DA message that encapsulates all of the learned routers.¶

6.3. Invisible Neighbor and Link Failure Inferring Module(M3)

M3 is responsible for inferring invisible neighbors of the current router by means of the ADT. If the link between a router A and its neighbor B breaks, which results in that M1 module of A cannot detect the existence of B, then B is an invisible neighbor of A. Since a device's location is coded into its IP address, it can be judged whether two routers are adjacent, according to their IP addresses. Based on this idea, M3 infers all of the invisible neighbors of the current router and the related link failures. The results are stored into an NDT. Moreover, link failures also are added into a link-failure table (LFT). LFT stores all of the failed links in the entire network.¶

6.4. Link Failure Learning Module(M4)

M4 is responsible for sending, receiving and forwarding link failure announcement (LFA) and learning all the link failures in the whole network. M4 broadcasts each newly inferred link failure to all the routers in the network. Each link failure is encapsulated in a LFA message and one link failure is broadcasted only once. If a router receives a DLR request from its neighbor, it will reply a LFA message that encapsulates all the learned link failures through M4 module. If M4 receives a LFA message, it checks whether the link failure encapsulated in the message is in a LFT by comparing two link ends and timestamp. If the link failure is not in the LFT or timestamp is different, M4 puts this link failure into the LFT (or update timestamp only) and forwards this LFA message to all the active ports except for the incoming one, otherwise, M4 discards this message directly. There is a special case a router will rebroadcast a link failure. If a router receives a data packet and must forward the packet going ahead to destination through a failed link, it means some previous router should avoid this failed link according to its NRT but it doesn't. In this case, maybe the previous router missed the LFA message of the link failure due to some uncertain reasons. So the forwarding router rebroadcasts the LFA message.¶

6.5. BRT Building Module(M5)

M5 is responsible for building a BRT for the current router. By leveraging the regularity in topology, M5 can calculate the routing paths for any destination without the knowledge of the topology of whole network, and then build the BRT based on an NDT. Since the IP addresses of network devices are continuous, M5 only creates one route entry for a group of destination addresses that have the same network prefix by means of route aggregation technology. Usually, the size of a BRT is very small. The detail of how to build a BRT is described in section 5.¶

6.6. NRT Building Module(M6)

M6 is responsible for building a NRT for the current router. Because M5 builds a BRT without considering link failures in network, the routing paths calculated by the BRT cannot avoid failed links. To solve this problem, a NRT is used to exclude the routing paths that include some failed links from the paths calculated by a BRT. M6 calculate the routing paths that include failed links and stored them into the NRT. The details of how to build a NRT is described in section 5.¶

6.7. Routing Table Lookup(M7)

M7 is responsible for querying routing tables and selecting the next hop for forwarding the packets. Firstly, M7 takes the destination address of a forwarding packet as a criterion to look up route entries in a BRT based on longest prefix match. All of the matched entries are composed of a candidate hops list. Secondly, M7 look up negative route entries in a NRT taking the destination address of the forwarding packet as criteria. This lookup is not limited to the longest prefix match, any entry that matches the criteria would be selected and composed of an avoiding hops list. Thirdly, the candidate hops minus avoiding hops are composed of an applicable hops list. At last, M7 sends the forwarding packet to any one of the applicable hops. If the applicable list is empty, the forwarding packet will be dropped.¶

10.1. BRT Building Procedure

By leveraging the topology's regularity, every switch clearly knows how it forwards a packet. When a packet arrives at an edge switch, if the destination of the packet lies in the same subnet with the switch, then the switch directly forwards the packet to the destination server through layer-2 switching. Otherwise, the switch forwards the packet to any of aggregation switches in the same pod. When a packet arrives at an aggregation switch, if the destination of the packet lies in the same pod, the switch forwards the packet to the corresponding edge switch. Otherwise, the switch forwards the packet to any of core switches that it is connected to. If a core switch receives a packet, it forwards the packet to the corresponding aggregation switch that lies in the destination pod. The forwarding policy discussed above is easily expressed through a BRT. The BRT of an edge switch, such as 10.1.1.1, is composed of the following entries: The BRT of an aggregation switch, such as 10.1.0.1, is composed of the following entries: The BRT of a core switch, such as 10.0.1.1, is composed of the following entries:¶

Destination/Mask       Next hop
10.0.0.0/255.0.0.0     10.1.0.1
10.0.0.0/255.0.0.0     10.1.0.2

Destination/Mask            Next hop
10.1.1.0/255 255.255.0      10.1.1.1
10.1.2.0/255.255.255.0      10.1.2.1
10.0.0.0/255.0.0.0          10.0.1.1
10.0.0.0/255.0.0.0          10.0.1.2

Destination/Mask            Next hop
10.1.0.0/255 255.0.0        10.1.0.1
10.2.0.0/255.255.0.0        10.2.0.1
10.3.0.0/255.255.0.0        10.3.0.1
10.4.0.0/255.255.0.0        10.4.0.1

10.2. NRT Building Procedure

The route entries in an NRT are related with link and node failures. We summarize all types of cases into three (3) catalogs.¶

Destination/Mask            Next hop
10.1.2.0/255.255.255.0      10.1.0.1

Destination/Mask            Next hop
10.1.2.0/255.255.255.0      10.3.0.1

Destination/Mask            Next hop
10.1.0.0/255.255.0.0        10.0.1.2

Destination/Mask            Next hop
10.1.0.0/255.255.0.0        10.3.0.1

10.3. Routing Procedure

FAR decides a routing by looking up its BRT and NRT. We illuminate the routing procedure by an example. In this example, we suppose that the link between 10.3.1.1 and 10.3.0.2 and the link between 10.1.2.1 and 10.1.0.2 have failed. Then we look into the routing procedure of a communication from 10.3.1.3 (source) to 10.1.2.2 (destination). Step 1: The source 10.3.1.3 sends packets to its default router 10.3.1.1 Step 2: The routing of 10.3.1.1. 1) Calculate candidate hops 10.3.1.1 looks up its BRT and gets the following matched entries: So the candidate hops = {10.3.0.1} 2) Calculate avoiding hops Its NRT is empty, so the set of avoiding hop is empty too. 3) Calculate applicable hops The applicable hops are candidate hops minus avoiding hops, so: The applicable hops = {10.3.0.1} 4) Forward packets to 10.3.0.1 Step 3: The routing of 10.3.0.1 1) Calculate candidate hops. 10.3. 0.1 looks up its BRT and gets the following matched entries: So the candidate hops = {10.0.1.1, 10.0.1.2} 2) Calculate avoiding hops So the avoiding hops = {10.0.1.2} 3) Calculate applicable hops The applicable hops are candidate hops minus avoiding hops, so: The applicable hops = {10.0.1.1} 4) Forward packets to 10.0.1.1 Step 4: 10.0.1.1 forwards packets to 10.1.0.1 by looking up its routing tables. Step 5: 10.1.0.1 forwards packets to 10.1.2.1 by looking up its routing tables. Step 6:10.1.2.1 forwards packets to the destination 10.1.2.2 by layer-2 switching.¶

Destination/Mask            Next hop
10.0.0.0/255.0.0.0          10.3.0.1

Destination/Mask           Next hop
10.1.0.0/255.255.0.0       10.0.1.1
10.1.0.0/255.255.0.0       10.0.1.2

Destination/Mask           Next hop
10.1.0.0/255.255.0.0       10.0.1.2

10.4. FAR's Performance in Large-scale Networks

FAR has good performance to support large-scale networks. In this section, we take a Fat-tree network composed of 2,880 48-port switches and 27,648 servers as an example to show FAR's performance.¶

15.1. Normative References

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997.¶

[RFC2328] J. Moy, "OSPF Version 2", BCP 14, RFC2328, April 1998.¶

[RFC3619] SHAH, S.; YIP, M. RFC3619: Extreme Networks' Ethernet Automatic Protection Switching (EAPS) Version 1. 2003.¶

15.2. Informative References

[FAT-TREE] M. Al-Fares, A. Loukissas, and A. Vahdat."A Scalable,Commodity, Data Center Network Architecture",In ACM SIGCOMM 2008.¶

[BCube] Guo, C., Lu, G., Li, D., Wu, H., Zhang, X., Shi, Y., ... Lu, S. (2009, August). BCube: a high performance, server-centric network architecture for modular data centers. In Proceedings of the ACM SIGCOMM 2009 conference on Data communication (pp. 63-74).¶

[MatrixDCN] Sun, Y., Chen, M., Peng, L., Hassan, M. M., Alelaiwi, A. (2016). MatrixDCN: a high performance network architecture for large-scale cloud data centers. Wireless Communications and Mobile Computing, 16(8), 942-959.¶

16.1. Application Area of the Solution

According to the horizontal expansion mode of the above scenarios, the whole Fat-Tree network does not need to be expanded to 4 layers (4 order Fat-Tree) even if it is expanded. Using a standard three-tier Fat-tree network, we can scale the network to meet all the problems of commercial network applications. This scheme is suitable for non-SDN distributed Fat-Tree network architecture.¶

16.2. Technical evolution roadmap

In this draft, we should design different rules for FAR switches in different regular networks to calculate routing tables, which limits FAR's extensibility. Fortunately, the latest SDN technology make it is easy to update the control plane of switches, since all the function of control plane are centralized to a controller in SDN. We are designing the next generation routing scheme for regular networks based on SDN. In the new scheme, we design a regular ToPology Description Language (TPDL) to descript a regular network. In TPDL, the distance between different type of node groups is defined by a group of distance formulas and the number of formulas is finite and fixed without increasing by the scale of a network. And then, switches learn the topology of a network by taking advantage of TPDL and generate flow table entries to forward packets without help of the SDN controller. If no entry is found for a forwarding packet, switches transport the packet to the SDN controller, and the controller recalculates a new routing path using A* algorithm by taking TPDL's distance formulas as a heuristic function and dispatch flow table entries down to related switches on the path.¶

16.3. Updating roadmap

In the next version, we will continue to advance the remaining issues such as protocol fields, section 3.2 simplification, etc.¶