On the Output Rate of Overloaded Link Schedulers

We derive and compare properties of the output rates at overloaded links for three types of link scheduling algorithms: First-in-First-Out (FIFO), Static-Priority (SP), and EarliestDeadline-First (EDF). Under most general assumptions, i.e., each traffic flow has a long-term average rate, we show that the output rates of flows at overloaded FIFO and EDF links are proportional to their input rates. As a consequence, the service rate guarantee offered by EDF and FIFO cannot exceed the guarantee given to a low-priority flow under SP scheduling.