Improving Software Middleboxes and Datacenter Task Schedulers

  • Hugo Sadok Universidade Federal do Rio de Janeiro
  • Miguel Elias Mitre Campista Universidade Federal do Rio de Janeiro
  • Luis Henrique Maciel Kosmalski Costa Universidade Federal do Rio de Janeiro


Shared systems have contributed to the popularity of many technologies. However, these systems often confront a common challenge: to ensure that resources are fairly divided without compromising utilization efficiency. In this master's thesis we look at this problem in two distinct systems---software middleboxes and datacenter task schedulers. We first present Sprayer, a system that uses packet spraying to load balance packets to cores in software middleboxes. Our design eliminates the imbalance problems of per-flow solutions and addresses the new challenges of handling shared flow states that come with packet spraying. Then, we present Stateful Dominant Resource Fairness (SDRF), a task scheduling policy for datacenters that looks at past allocations and enforces fairness in the long run. SDRF reduces users' waiting time on average and improves fairness by increasing the number of completed tasks for users with lower demands, with small impact on high-demand users.


H. Sadok, M. E. M. Campista, L. H. M. K. Costa. "A Case for Spraying Packets in Software Middleboxes." In ACM HotNets, pp. 127-133, Nov. 2018. Qualis A1.

H. Sadok, M. E. M. Campista, L. H. M. K. Costa. "O Passado Também Importa: Um Mecanismo de Alocação Justa de Múltiplos Tipos de Recursos ao Longo do Tempo." In SBRC, May 2018. Qualis B2.

H. Sadok, M. E. M. Campista, L. H. M. K. Costa. "Um Mecanismo para Compar-tilhamento de Recursos em Nuvens Colaborativas Baseado na Credibilidade dos Usuários." In SBRC, pp. 458-471, May 2017. Qualis B2.

H. Sadok, M. E. M. Campista, L. H. M. K. Costa. "Per-Packet Load Balancing for Multi-Core Middleboxes." Poster in USENIX NSDI, Apr. 2018. Qualis A1.

R. S. Couto, H. Sadok, P. Cruz, F. F. Silva, T. Sciammarella, M. E. M. Campista, L. H. M. K. Costa, P. B. Velloso, M. G. Rubinstein. "Building an IaaS Cloud with Droplets: a Collaborative Experience with OpenStack." In Journal of Network and Computer Applications, vol. 117, pp. 59-71, Sep. 2018. Qualis A2 (Impact Factor: 3.991).

Barreto, H. F. S. S. M. (2018). Improving software middleboxes and datacenter task schedulers. Master's thesis, Universidade Federal do Rio de Janeiro.

Bonald, T. and Roberts, J. (2015). Multi-resource fairness: Objectives, algorithms and performance. In ACM SIGMETRICS.

Chiosi, M. et al. (2012). Network functions virtualisation: An introduction, benefits, enablers, challenges & call for action. Technical report, ETSI.

Friedman, E., Psomas, C.-A., and Vardi, S. (2017). Controlled dynamic fair division. In ACM EC.

Ghodsi, A., Sekar, V., Zaharia, M., and Stoica, I. (2012). Multi-resource fair queueing for packet processing. In ACM SIGCOMM.

Ghodsi, A., Zaharia, M., Hindman, B., Konwinski, A., Shenker, S., and Stoica, I. (2011). Dominant resource fairness: Fair allocation of multiple resource types. In USENIX NSDI.

Grandl, R., Chowdhury, M., Akella, A., and Ananthanarayanan, G. (2016). Altruistic scheduling in multi-resource clusters. In USENIX OSDI.

Handley, M., Raiciu, C., Agache, A., Voinescu, A., Moore, A. W., Antichi, G., and Wój-cik, M. (2017). Re-architecting datacenter networks and stacks for low latency and high performance. In ACM SIGCOMM.

Joe-Wong, C., Sen, S., Lan, T., and Chiang, M. (2013). Multiresource allocation: Fairnes-efficiency tradeoffs in a unifying framework. IEEE/ACM Trans. Netw., 21(6).

Kablan, M., Alsudais, A., Keller, E., and Le, F. (2017). Stateless network functions: Breaking the tight coupling of state and processing. In USENIX NSDI.

Kash, I., Procaccia, A. D., and Shah, N. (2014). No agent left behind: Dynamic fair division of multiple resources. J. Artif. Intell. Res., 51(1):579-603.

Kulkarni, S. G., Zhang, W., Hwang, J., Rajagopalan, S., Ramakrishnan, K. K., Wood, T., Arumaithurai, M., and Fu, X. (2017). NFVnice: Dynamic backpressure and scheduling for NFV service chains. In ACM SIGCOMM.

Parkes, D. C., Procaccia, A. D., and Shah, N. (2015). Beyond dominant resource fairness. ACM Trans. Econ. Comput., 3(1):3:1-3:22.

Reiss, C., Tumanov, A., Ganger, G. R., Katz, R. H., and Kozuch, M. A. (2012). Hetero-geneity and dynamicity of clouds at scale: Google trace analysis. In ACM SoCC.

Sadok, H., Campista, M. E. M., and Costa, L. H. M. K. (2018a). A case for spraying packets in software middleboxes. In ACM HotNets.

Sadok, H., Campista, M. E. M., and Costa, L. H. M. K. (2018b). O passado também importa: Um mecanismo de alocação justa de múltiplos tipos de recursos ao longo do tempo. In SBRC.

Sekar, V., Egi, N., Ratnasamy, S., Reiter, M. K., and Shi, G. (2012). Design and imple-mentation of a consolidated middlebox architecture. In USENIX NSDI.

Sun, C., Bi, J., Zheng, Z., Yu, H., and Hu, H. (2017). NFP: Enabling network function parallelism in NFV. In ACM SIGCOMM.

Woo, S., Sherry, J., Han, S., Moon, S., Ratnasamy, S., and Shenker, S. (2018). Elastic scaling of stateful network functions. In USENIX NSDI.
Como Citar

Selecione um Formato
SADOK, Hugo; MITRE CAMPISTA, Miguel Elias; COSTA, Luis Henrique Maciel Kosmalski. Improving Software Middleboxes and Datacenter Task Schedulers. In: CONCURSO DE TESES E DISSERTAÇÕES - SIMPÓSIO BRASILEIRO DE REDES DE COMPUTADORES E SISTEMAS DISTRIBUÍDOS (SBRC), 2. , 2019, Gramado. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 . p. 137-144. ISSN 2177-9384. DOI: