Optimal Path Encoding for Software-Defined Networks

All packet networks need to maintain state in the form of a expensive, high speed packet forwarding table at each switch. The cost of maintaining and updating this table increases as networks grow and as the table becomes more granular in order to support ever more sophisticated per flow routing, traffic engineering and service chaining requirements. In this paper, we propose a new packet forwarding architecture called Path Addressing (PA) which encodes the path of the packet in the network header itself. This eliminates the lookup table at transit packet switches, thereby rendering the network core stateless and highly scalable. Unlike traditional source routing which relies on variable length custom headers, Path Addressing encodes the path inside existing fixed size packet headers, making it amenable to straightforward integration into existing switches with minimal forwarding plane changes. Besides the Path Addressing architecture, the other key contribution of this paper is optimal path encoding algorithms for packing paths into fixed size headers. We formulate the optimal path encoding problem as a convex optimization problem and solve it using a provably optimal interior-point optimization algorithm. Put together, Path Addressing and the associated optimal path encoding algorithm can be used to create highly scalably Ethernet, MPLS and IP networks with full support for arbitrary per flow routing.