In this paper we describe a class of routing algorithms called multi-class algorithms. Multi-class algorithms support multiple
classes of routing simultaneously, thereby allowing different applications, and even different messages, to select the most
advantageous kind of rout- ing. For example some applications prefer the smaller latency variance of oblivious routing, while
others prefer the higher throughputs achieved by adaptive routing. Typical systems provide a single class routing algo- rithm,
but applications benefit from the flexibility of multiple classes.
Integrated multi-class routers have two characteristics. First, they pro- vide an integrated algorithm where routing classes
share resources such as buffers. Each class is not an independent routing algorithm on an in- dependent network, but rather
to reduce costs, each class is implemented by a single algorithm on a shared network. Second, multi-class routers help increase
performance by providing routing flexibility and network services which help simplify the network interface or system software.
The idea of multi-class routing is perhaps obvious and it has appeared before. Our contribution, however, lies in defining
multi-class routers, describing their advantages, providing an appropriate method for evalu- ating such routers, and by demonstrating
their usefulness though exam- ples.
This work was supported in part by the National Science Foundation Grant MIP-9213469 and by an ARPA Graduate Research Fellowship.