Concise Encoding of Flow Attributes in SDN Switches

Authors: Robert MacDavid, Rüdiger Birkner, Ori Rottenstreich, Arpit Gupta, Nick Feamster, and Jennifer Rexford
Proceedings of the Symposium on SDN Research - SOSR '17


Network devices such as routers and switches forward traffic based on entries in their local forwarding tables. Although these forwarding tables conventionally make decisions based on a packet header field such as a destination address, tagging flows with sets or sequences of attributes and making forwarding decisions based on these attributes can enable richer network policies. For example, devices at the edge of a network could add a tag to each packet that encodes a set of egress locations, a set of host permissions, or a sequence of middleboxes to traverse; simpler devices in the core of the network could then forward packets based on this tag.

Unfortunately, naive construction of these tags can create forwarding tables that grow quadratically with the number of elements in the set or sequence—prohibitive for commodity network devices. In this paper, we present PathSets, a compression algorithm that makes such encodings practical. The algorithm encodes sets or sequences (e.g., middlebox service chains, lists of next-hop network devices) in a compact tag that fits in a small packet-header field. Our evaluation shows that PathSets can encode attribute sets and sequences for large networks using tag widths competitive with existing approaches and that the number of forwarding rules grows linearly with the number of attributes encoded.


Dr. Rüdiger Birkner
PhD student


	isbn = {978-1-4503-4947-5},
	doi = {10.1145/3050220.3050227},
	year = {2017-04-03},
	type = {Conference Paper},
	journal = {Proceedings of the Symposium on SDN Research - SOSR '17},
	author = {MacDavid, Robert and Birkner, Rüdiger and Rottenstreich, Ori and Gupta, Arpit and Feamster, Nick and Rexford, Jennifer},
	keywords = {Software-defined networks; Network management; Open-flow; Commodity switch; TCAM},
	language = {en},
	address = {New York, NY},
	publisher = {Association for Computing Machinery},
	title = {Concise Encoding of Flow Attributes in SDN Switches},
	PAGES = {48 - 60},
	Note = {Symposium on SDN Research (SOSR 2017); Conference Location: Santa Clara, CA, USA; Conference Date: April 3-4, 2017}

Research Collection: 20.500.11850/166047