Flow Control Power is Nondecentralizable

Abstract

Flow control in store-and-forward computer networks is appropriate for decentralized execution. A formal description of a class of “decentralized flow control algorithms” is given. The feasibility of maximizing power with such algorithms is investigated. On the assumption that communication links behave like M/M/l servers it is shown that no “decentralized flow control algorithm” can maximize network power. Power has been suggested in the literature as a network performance objective. It is also shown that no objective based only on the users' throughputs and average delay is decentralizable. Finally, a restricted class of algorithms cannot even approximate power. Copyright © 1981 by The Institute of Electrical and Electronics Engineers, Inc.