Scheduling Nonuniform Traffic in a Packet Switching System with Large Propagation Delay

Bruce Hajek, Timothy Weller

Research output: Contribution to journalArticlepeer-review


Transmission algorithms are introduced for use in a single-hop packet switching system with nonuniform traffic and with propagation delay that is large relative to the packet transmission time. The traffic model allows arbitrary traffic streams subject only to a constraint on the number of data packets which can arrive at any individual source in the system or for any individual destination in the system over time periods of specified length. The algorithms are based primarily on sending transmission schedules to the receivers immediately before transmitting each data packet multiple times so that the receiver can maximize the number of packets it captures. An algorithm based on matchings in a random graph is shown to provide mean total delay divided by mean propagation delay arbitrarily close to one, as the propagation delay tends to infinity.

Original languageEnglish (US)
Pages (from-to)358-365
Number of pages8
JournalIEEE Transactions on Information Theory
Issue number2
StatePublished - Mar 1995


  • Switching
  • large propagation delay
  • nonuniform traffic
  • scheduling

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Scheduling Nonuniform Traffic in a Packet Switching System with Large Propagation Delay'. Together they form a unique fingerprint.

Cite this