Concise encoding of flow attributes in SDN switches

Robert MacDavid, Rudiger Birkner, Ori Rottenstreich, Arpit Gupta, Nicholas G. Feamster, Jennifer L. Rexford

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationSOSR 2017 - Proceedings of the 2017 Symposium on SDN Research
PublisherAssociation for Computing Machinery, Inc
Number of pages13
ISBN (Electronic)9781450349475
StatePublished - Apr 3 2017
Event2017 Symposium on SDN Research, SOSR 2017 - Santa Clara, United States
Duration: Apr 3 2017Apr 4 2017

Publication series

NameSOSR 2017 - Proceedings of the 2017 Symposium on SDN Research


Other2017 Symposium on SDN Research, SOSR 2017
Country/TerritoryUnited States
CitySanta Clara

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Software


  • Commodity switch
  • Network management
  • Open-flow
  • Software-defined networks
  • TCAM


Dive into the research topics of 'Concise encoding of flow attributes in SDN switches'. Together they form a unique fingerprint.

Cite this