FUBAR: Flow Utility Based Routing

Presenter: Nikola Gvozdiev

Authors: Nikola Gvozdiev, Brad Karp, Mark Handley (UCL)

Paper: http://conferences.sigcomm.org/hotnets/2014/papers/hotnets-XIII-final158.pdf

FUBAR presents an application centric routing algorithm that aims to improve the utility of all participants while requiring no modifications to any of the systems: namely, the end hosts and switches.  FUBAR is motivated by the insight that existing routing and traffic engineering techniques have drawbacks.  For example, ECMP uses load balancing to better utilize the network but is prone to errors when the topology changes. Similarly,  shortest-path based routing techniques over come these problems but poorly utilize the network. To overcome limitations, operators many perform traffic engineering (TE) by manually moving traffic and assigning utility.

These approach are manual, slow, and error-prone. FUBAR attempts to automate this by proposing an approach that automatically performs routing and traffic engineering: essentially combining routing and TE.  To successfully achieve this, FUBAR requires a utility function that guides its efforts to mitigate congestion.  The task of defining a utility function is complicated by the fact that users employ many applications resulting in a diversity of network requirements. 

To address this, FUBAR defines a utility function that captures both delay and throughput. Thus allowing FUBAR to optimize for applications with a variety of requirements.  FUBAR requires the operators to provide the delay utility function while FUBAR empirically learns the application’s capacity utility. These two are combined together by multiplying them.  

To optimize the global utility of the network, FUBAR applies an iterative approach that first applies traffic to the lowest delay path and then eliminates congested paths by moving traffic from congested links.

FUBAR was evaluated on hurricane electric backbone and initial results are promising: FUBAR provides close to optimal utility.  Furthermore, the algorithm runs quickly providing results within 40 seconds.

Question: how do you deal with deadline flows?

Answer: 

Question: how do you ensure the LP solves within the timeline?

Answer: compromises need to be made between granularity of input and time to compute a solution.