Toward the first SDN programming capacity theorem on realizing high-level programs on low-level datapaths

Christopher Leet, Xin Wang, James Aspnes, and Y. Richard Yang. Toward the first SDN programming capacity theorem on realizing high-level programs on low-level datapaths. Accepted to INFOCOM 2018.

Abstract

High-level programming and programmable data paths are two key capabilities of software-defined networking (SDN). A fundamental problem linking these two capabilities is whether a given high-level SDN program can be realized onto a given low-level SDN datapath structure. Considering all highlevel programs that can be realized onto a given datapath as the programming capacity of the datapath, we refer to this problem as the SDN datapath programming capacity problem. In this paper, we conduct the first study on the SDN datapath programming capacity problem, in the general setting of high-level, datapath oblivious, algorithmic SDN programs and state-of-art multi-table SDN datapath pipelines. In particular, considering datapath-oblivious SDN programs as computations and datapath pipelines as computation capabilities, we introduce a novel framework called SDN characterization functions, to map both SDN programs and datapaths into a unifying space, deriving the first rigorous result on SDN datapath programming capacity. We not only prove our results but also conduct realistic evaluations to demonstrate the tightness of our analysis.

BibTeX

Download
@unpublished{LeetWAY2017,
author    = {Leet, Christopher and Wang, Xin and Aspnes, James and Yang, Y. Richard},
title     = {Toward the first {SDN} programming capacity theorem on realizing high-level programs on low-level datapaths},
  month = dec,
  year = 2017,
  note={Accepted to INFOCOM 2018}
}

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page