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
Theoretical Computer Science
Paper
The generalized packet routing problem
Abstract
The problem of efficient packet routing is central to the area of communication networks. The special case of permutation packet routing has been extensively studied in the past. While optimal algorithms for permutation routing exist, they do not 'scale up' to give optimal solutions for the general case. Using a novel technique we obtain an optimal algorithm for the general packet routing problem. The core of our solution is an algorithm for a generalized version of the token distribution problem. This result has direct applications to the solution of the load balancing problem in distributed systems. © 1987.