Scalable bandwidth shaping scheme via adaptively managed parallel heaps in manycore-based network processors

Taehyun Kim, Jongbum Lim, Jinku Kim, Woo Cheol Cho, Eui Young Chung, Hyuk Jun Lee

Research output: Contribution to journalArticlepeer-review


Scalability of network processor-based routers heavily depends on limitations imposed by memory accesses and associated power consumption. Bandwidth shaping of a flow is a key function, which requires a token bucket per output queue and abuses memory bandwidth. As the number of output queues increases, managing token buckets becomes prohibitively expensive and limits scalability. In this work, we propose a scalable software-based token bucket management scheme that can reduce memory accesses and power consumption significantly. To satisfy real-Time and low-cost constraints, we propose novel parallel heap data structures running on a manycore-based network processor. By using cache locking, the performance of heap processing is enhanced significantly and is more predictable. In addition, we quantitatively analyze the performance and memory footprint of the proposed software scheme using stochastic modeling and the Lyapunov central limit theorem. Finally, the proposed scheme provides an adaptive method to limit the size of heaps in the case of oversubscribed queues, which can successfully isolate the queues showing unideal behavior. The proposed scheme reduces memory accesses by up to three orders of magnitude for one million queues sharing a 100Gbps interface of the router while maintaining stability under stressful scenarios.

Original languageEnglish
Article number59
JournalACM Transactions on Design Automation of Electronic Systems
Issue number4
Publication statusPublished - 2017 May

Bibliographical note

Publisher Copyright:
© 2017 ACM.

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Scalable bandwidth shaping scheme via adaptively managed parallel heaps in manycore-based network processors'. Together they form a unique fingerprint.

Cite this