[ Back to course homepage ]

Software Project for ECE 544 Spring 2017

This project seeks to implement a datacenter traffic engineering solution for effective load balancing among network links. A typical datacenter topology consists of multiple paths between any two pairs of hosts (Figure 1). A simple way to load balance the traffic across these multiple paths is called equal cost multi path (ECMP) routing, i.e., divide traffic equally among multiple paths that have the same cost. Cost is dependent on the number of hops in a route and the capacities of links along the route. Thus, two paths with the same number of hops and same link capacities along the path have the same cost. In Figure below, the three paths from D  to E via A, B and C have the same cost.

The equal division of traffic is performed in a way that all packets of a single flow take the same route and flows are equally distributed from different paths. If each flow is small, this approach achieves good load balancing among network links.  However, even a few large flows (called “elephant flows”) that occupy a significant fraction of the link capacity can disrupt the load balance properties of these links. The problem is more severe if multiple large flows collide on the same link. In Figure below, three flows are shown as colliding on link AD. As a result, these large flows will have a throughput that is at most one-third the link capacity of AD.

In this project, our datacenter traffic engineering solution performs two main actions: (1) it identifies these large flows and (2) designs custom routing for them to minimize the occurrence of such collisions. For example, in the above case, a collision can be avoided by having each flow be assigned separate path, allowing each flow to fully utilize the links AD, BD and CD respectively.

We will implement this solution in the Mininet framework [1]. Mininet uses OpenVSwitch (OVS)[2] as the switch/router in its network dataplane. We will use the sFlow extensions in OVS [3] to sample packets arriving at a switch. Thereafter, a centralized decision making controller will use efficient algorithms to detect the large flows from the stream of packets and compute routing for these large flows to load balance traffic among data center links. It will configure network switches to implement the custom per-flow routing using either the OpenFlow protocol or OVS specific commands (such as ovs-ofctl and ovs-vsctl).

1. Mininet: http://mininet.org/

2. OpenVSwitch:  http://openvswitch.org/

3. sFlow: http://docs.openvswitch.org/en/latest/howto/sflow/

Assignment 1

Assignment 2

Assignment 3

Assignment 4