Genesis: Synthesizing Forwarding Tables in Multi-tenant Networks

Abstract:

Operators in multi-tenant cloud datacenters re- quire support for diverse and complex end-to-end policies, such as, reachability, middlebox traversals, isolation, traffic engineering, and network resource management. We present Genesis, a data-center network management system which allows policies to be specified in a declarative manner without explicitly programming the network data plane. Genesis tackles the problem of enforcing policies by synthesizing switch forwarding tables. It uses the formal foundations of constraint solving in combination with fast off-the-shelf SMT solvers. To improve synthesis performance, Genesis incorporates a novel search strategy that uses regular expressions to specify properties that leverage the structure of datacenter networks, and a divide-and-conquer synthesis procedure which exploits the structure of policy relationships. We have prototyped Genesis, and conducted experiments with a variety of workloads on real-world topologies to demonstrate its performance.

Download Genesis Virtual Machine [2 GB]

All test scripts and README.txt can be found in the $HOME/Genesis/AEC folder.
Refer to README.txt for detailed instructions on code organization, running Genesis, GPL syntax and evaluation scripts.

Running Genesis

The Virtual Machine (Ubuntu 14.04) comes with all packages installed. To run Genesis, go to the $HOME/Genesis folder and use the terminal to run Genesis:


	python -O genesis.py -topo [topology-filename] -gpl [gpl-filename]

To run Genesis with tactic enabled:


	python -O genesis.py -topo [topology-filename] -gpl [gpl-filename] -useTactic [tactic]

Our current implementation supports 4 tactics that can be supplied as arguments:

noEdge : the edge-to-edge path will not contain another edge switch in the path
valleyFree : valley-free routing, that is paths are of the form eacae
len7 : Length of path <= 7
noEdgeLen7 : Length of path <= 7 and does not contain another path.

[Note: these tactics assume that each paths start and end at edge switches. New tactics can be added to generalize these tactics]

To run Genesis using divide-and-conquer synthesis:


	python -O genesis.py -topo [topology-filename] -gpl [gpl-filename] -dc

To run Genesis for network repair:


	python -O genesis.py -topo [topology-filename] -gpl [gpl-filename] -repair

GPL syntax

To define a packet class(pc) -


	p0_0 := tcp.port = 0 : e14 >> e17

[pc-name] := [network-predicate] : [source-sw] >> [destination-sw] The current implementation of Genesis simply uses the network predicate as a string. For actual network deployments, the network predicate would translate to SDN Match rules. To add waypoints to a reachability policy:


	e11 >> [ a29, a24; a20, a28 ] >> e2

which enforces that [a29, a24] must be traversed before [a20, a28] in the path, and ordering in a set is irrelevant. To define an isolation policy using the packet class names-


	pc1 || pc2

To define isolation among different sets of classes -


	[pc1, pc2] || [pc3, pc4]

This translates to: pc1 || pc3 and pc1 || pc4 and pc2 || pc3 and pc2 || p4

To define a link capacity policy:


	e11 -> a28 : capacity-value

To define a switch table size policy:


	e11 : size

TE Objective: Minimizing the average link utilization -


	minimize-avg-te

TE Objective: Minimizing the average link utilization -


	minimize-max-te

Installing Genesis on Ubuntu 14.04

Genesis comes with a install script intended to install all dependencies of Genesis. The install script can be found in the Genesis directory - install Copy install to $HOME, and from $HOME, run on terminal:


	chmod +x install
	sudo ./install

Open a new terminal to run Genesis (.bash_profile updated by install) If you get errors regarding METIS, ensure that environment variable $METIS_DLL points to $HOME/libmetis.so