SCHEDULING NONUNIFORM TRAFFIC IN A PACKET-SWITCHING SYSTEM WITH LARGEPROPAGATION DELAY

Transmission algorithms are introduced for use in a single-hop packet switching system with nonuniform traffic and with propagation delay th at is large relative to the packet transmission time. The traffic mode l allows arbitrary traffic streams subject only to a constraint on the number of data packets which can arrive at any individual source in t he system or for any individual destination in the system over time pe riods of specified length. The algorithms are based primarily on sendi ng transmission schedules to the receivers immediately before transmit ting 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 p ropagation delay arbitrarily close to one, as the propagation delay te nds to infinity.