A new model of nonuniform traffic is introduced for a single-hop packet-switching system. This 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 nonuniform traffic model is flexible enough to cover integrated data networks carrying diverse classes of data. The system model is rather general, and includes passive optical star wavelength-division networks. Transmission algorithms are introduced for a single-hop packet-switching system with such nonuniform traffic and with propagation delay that is negligible relative to the packet length. The algorithms are based on collision-free scheduling of packets using graph-matching algorithms since the global state of the system is known to all stations at any time.

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

A new model of nonuniform traffic is introduced for a single-hop packet switching system. This 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 nonuniform traffic model is flexible enough to cover integrated data networks carrying diverse classes of data. The system model is rather general and includes passive optical star wavelength division networks. Transmission algorithms are introduced for a single-hop packet switching system with such nonuniform traffic and with propagation delay that is negligible relative to the packet length. The algorithms are based on collision-free scheduling of packets using graph matching algorithms, since the global state of the system is known to all stations at any time.>

S. Badr and P. Podar (1989) introduced a zig-zag routing policy and showed its optimality for shortest-path routing on square or infinite grid networks with independent link failures. This paper shows that, contrary to the claim of Badr and Podar, a zig-zag policy is not optimal for shortest-path routing on torus networks.>

It is shown that if formulas constructed from error-prone three-input gates are used to compute Boolean functions, then a per-gate failure probability of 1/6 or more cannot be tolerated. The result is shown to be tight if the per-gate failure probability is constant and precisely known.>