Christopher Leet, Xin Wang, Y. Richard Yang, James Aspnes, and Changjun Jiang. Toward the first SDN programming capacity theorem on realizing high-level programs on low-level datapaths. IEEE INFOCOM 2018 - IEEE Conference on Computer Communications, April 2018.
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.
@inproceedings{LeetWYA2018,
author = {Leet, Christopher and Wang, Xin and Yang, Y. Richard and Aspnes, James},
title = {Toward the first {SDN} programming capacity theorem on realizing high-level programs on low-level datapaths},
month = apr,
year = 2018,
booktitle = {IEEE INFOCOM 2018 - IEEE Conference on Computer Communications},
pages = {1--9}
}