On the Complexity of Channel Assignment for Real-Time Flows

J.A. Cobb (USA)


Quality of Service, MultiChannels, Scheduling, Complex ity.


Consider a computer network in which adjacent nodes ex change messages via multiple communication channels. Multiple channels between adjacent nodes are desirable due to their cost effectiveness and improved fault-tolerance. We consider the problem of providing deterministic qual ity of service guarantees in this network. In particular, we consider a set of flows that traverse between a pair of neigh boring nodes. Each flow must be assigned to one and only one of the channels joining the pair of nodes. We study the complexity of this flow assignment problem. We show the problem to be NP-hard, even under significant restric tions on the quality of service parameters of flows. We also present a pseudopolynomial solution to the problem when the number of channels is fixed.

Important Links:

Go Back