Analysis of worst-case backlog bounds for Networks-on-Chip

Junhui Wang, Yue Qian, Yi Wang, Zili Shao, Wenhua Dou, Qiang Dou

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)


In networks-on-chips (NoCs), analyzing the worst-case backlog bounds of routers is very important to identify network congestions and improve network performance. In this paper, we propose a method called DiGB (DIrected- contention-Graph-based Backlog bound derivation) to analyze worst-case backlog bounds. For primitive scenarios, we propose analytical models for backlog bound derivation. For complex scenarios, we first construct a directed-contention- graph (DCG) to analyze the relationships among traffic flows. Then, we use the Breadth-First-Search strategy to traverse the DCG so that complex scenarios can be divided into primitive scenarios. Finally we compute the worst-case backlog bounds of each router. To illustrate this method, we present the derivation of closed-form formulas to compute the worst-case backlog bounds under all-to-one gather communication. The experimental results show that our method can achieve correct and tight worst-case backlog bounds.
Original languageEnglish
Pages (from-to)494-508
Number of pages15
JournalJournal of Systems Architecture
Issue number6
Publication statusPublished - 1 Jan 2014


  • Congestion
  • Directed-contention-graph
  • Network calculus
  • Networks-on-chip
  • Worst-case backlog bound

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture


Dive into the research topics of 'Analysis of worst-case backlog bounds for Networks-on-Chip'. Together they form a unique fingerprint.

Cite this