Efficient algorithms for erasure node placement on slotted dual bus networks

Author

Narahari, Bhagirath ; Shende, Sunil ; Simha, Rahul

Author_Institution

Dept. of Electr. Eng. & Comput. Sci., George Washington Univ., Washington, DC, USA

Volume

4

Issue

5

fYear

1996

fDate

10/1/1996 12:00:00 AM

Firstpage

779

Lastpage

784

Abstract

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 throughput-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

Keywords

channel capacity; minimisation; network topology; packet switching; polynomials; telecommunication networks; cost measures; erasure node placement; minimum number; network congestion; optimal placement; passive stations; polynomial-time algorithms; slot reuse; slotted dual bus networks; throughput; traffic patterns; Approximation algorithms; Computer science; Cost function; Data structures; Helium; Performance analysis; Polynomials; Protocols; Telecommunication traffic; Throughput;

fLanguage

English

Journal_Title

Networking, IEEE/ACM Transactions on

Publisher

ieee

ISSN

1063-6692

Type

jour

DOI

10.1109/90.541325

Filename

541325