Universal Timestamp-Scheduling for real-time networks

Consider a network of computers interconnected by point-to-point communication channels. For each flow of packets through the network, the network reserves a fraction of the packet rate of each channel along the path of the flow. We define a family of scheduling protocols, called Universal Timestamp-Scheduling, to forward packets in this network, such that all members of the protocol family provide the same upper bound on packet delay as the well-known packet delay of Virtual Clock scheduling. The protocol family is called universal because it encompasses a wide variety of protocols. To show this, we prove that many scheduling protocols in the literature are members of the protocol family, and thus provide the above guarantee. In addition, we show that the protocols in the literature have only considered one side of the spectrum of possible scheduling protocols, and that there is another side of the spectrum that deserves attention and remains to be investigated. (C) 1999 Elsevier Science B.V. All rights reserved.