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
SIAM Journal on Computing
Paper
DISTRIBUTED MULTI-DESTINATION ROUTING: THE CONSTRAINTS OF LOCAL INFORMATION.
Abstract
In computer networks, message routing is often accomplished by network nodes using local information. The unavailability of global information intuitively makes hard routing problems virtually impossible. This paper formalizes this intuition by examining a hard (NP-complete) routing problem, the problem of multi-destination routing. It is shown that with only limited information it is impossible to optimize network utilization for the multi-destination routing problem. Moreover, it is impossible to even approximate optimality to within a specific tolerance. Several versions of this result are proved; the versions differ in terms of the amount of information available at a node, and the extent to which the problem cannot be approximated. An improved local information algorithm is presented which is best possible amongst local information algorithms.