About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Algorithmica
Paper
Maximal selection in tandem networks with symmetric hearing range
Abstract
We consider an infinite tandem network in which every node is capable of hearing its neighbors up to a given distance n. At any moment of time every node may contain in the top of its queue a message destined to one of its neighbors. This network can be used as a model for a microwave or optic link with many users. For small and large n we investigate the maximal selection of nodes in the network, for which their transmissions are collision-free. For a large hearing range we show that the upper bound on the maximal selection, which is found herein, is asymptotically achievable. For small hearing ranges we show that a greedy selection is better but not asymptotically optimal. We also specify a sequence of upper bounds which converge to the maximal throughput. © 1989 Springer-Verlag New York Inc.