The computational complexity of packet routing schemes that are provably efficient with respect to end-to-end delay is considered. This work focuses on finding algorithms that can optimize both the end-to-end delay when the number of packets in the network increases, and the number of packets that can be accepted in the network within a fixed end-to-end delay. The problem of routing within a fixed delay, also termed the call admission problem, is applicable to real-time situations when packets must be delivered by a fixed deadline or become useless, and to optical networks where, as the author explains, it is more desirable to destroy collided packets and request retransmission than to buffer those that cannot be transmitted immediately.

All strategies related to both the minimum end-to-end delay and the maximum number of accepted packets within any sublinear error in the number of packets are proven to be NP-hard. As the author notes, it is therefore impossible to design an algorithm that, in the worst case, is efficient with respect to running time and performs well with respect to the quality of the solutions.

The exposition is excellent. A good extended introduction sets the context for the work as well as any presentation I have seen in this area. The body of the research is contained in sections 2 and 3. Section 4 is a brief conclusion, containing final remarks and open questions.