The Controller Placement Problem

Authors: 
Brandon Heller, Rob Sherwood and Nick McKeown
Published: 
HotSDN
Year: 
2012

Question: Given SDN topology,

  1. How many controllers are needed and

  2. where do they go?

Problems especially in WAN with long propogation delay – affects convergence and availability and informs decision as to whehter control is “real time” or pushed out to forwarding elements.

Motivating examples:

  • Internet2, placing SDN controllers in existing network

  • Aster*x distributed load balancer

  • Flowvizor centralised network slicing tool

Placement metrics:

  • Average case latency between nearest of k controllers and all nodes (problem known as minimum k-median)

  • Worst case latency from any node to k controllers (problem known as minimum k-centre)

  • Maximise no of nodes within latency bound (problem known as maximum cover)

Application is only for small networks since problem is “exponential for k”. Refer to literature for algorithms for larger tests.

Most results are shown initially for Internet 2 topology. Tradeoffs exist between metrics – e.g. worst case versus average case trade off.

Figure three shows results for “random” placement as ratio to optimal – not clear if random results are just one instantiation or average over many.

Later results draw more widely from topology zoo.

Discussion points include:

  • Optimising for robustness (distributed versus centralised control reliability)

  • State distribution problem (more than one controller must share state).

Show bibtex
Page generated 2014-01-07, by jemdoc.