A theory of multi‐channel schedulers for quality of service

Abstract

A computer network consists of a set of computing nodes interconnected via communication channels. It is commonly assumed that, for each pair of network nodes u and v, there is at most one channel from u to v. However, it is often desirable to have multiple channels between nodes. That is, for every pair of network nodes u and v, there may be multiple channels from u to v. In this paper, we consider the problem of providing deterministic quality of service guarantees when there are multiple channels between nodes. We show that any packet scheduling protocol that operates over a single channel can be modified to operate over multiple channels. In addition, this transformation increases the packet delay through the node by only a small amount. However, having multiple channels between nodes may cause packet reorder. This reorder significantly increases the upper bound on end‐to‐end delay. We show how this increase in delay is avoided through the use of efficient sorting techniques.