Efficient algorithms for erasure node placement on slotted dual bus networks

Bhagirath Narahari, Sunil Shende, Rahul Simha

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


We study the problem of placing erasure nodes among passive stations in a slotted dual bus network. Erasure nodes are known to improve throughput by allowing slot reuse. It is also known that choices made in locating erasure nodes significantly impact network congestion and overall through-put - especially when traffic patterns exhibit a high degree of locality. We present algorithms to determine optimal placements of erasure nodes that improve upon prior work on this problem: we present simpler and faster polynomial-time algorithms and also consider various useful cost measures. These algorithms can be used to solve related placement problems in which limits on congestion and existing placements are given as input, and the goal is to find the minimum number of erasure nodes required to meet the congestion bound.

Original languageEnglish (US)
Pages (from-to)779-784
Number of pages6
JournalIEEE/ACM Transactions on Networking
Issue number5
StatePublished - Dec 1 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Efficient algorithms for erasure node placement on slotted dual bus networks'. Together they form a unique fingerprint.

Cite this