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

Christopher Leet, Xin Wang, Y. Richard Yang, and James Aspnes.
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.

- INFOCOM 2018 proceedings version:
**PDF**.

## BibTeX

Download@unpublished{LeetWYA2017,
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 = jan,
year = 2018,
note={To appear, INFOCOM 2018}
}

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page