The provision of a low delay service within the best-effort Internet

In this work, we define a novel Internet service, called ABE (Alternative Best-Effort), which allows interactive multimedia applications to receive low queuing delay within the existing best-effort Internet. We then develop and analyse a number of innovative scheduling algorithms that can implement ABE in a router. ABE differs from other services that provide low queuing delay in that it does not rely on any reservation and requires no charging of those that avail of the low delay service. We retain the best-effort context by protecting traffic that does not require lower delay for individual packets so that the existence of ABE is transparent to them, namely their performance is at least as good as it would be in the current best-effort Internet. The primary scheduler to implement ABE we developed is called DSD (Duplicate Scheduling with Deadlines). It guarantees that traffic marked as low-delay will spend no longer in the system of each router than some operator specified value. The performance of other traffic is protected by the use of a virtual queue, a packet deadline decision based mechanism and a controller. We prove important properties of DSD and show, by the tools of queuing analysis and simulation, that it succeeds in its goal: protecting the performance of other traffic and the best possible performance for low-delay traffic subject to the constraints of not exceeding the maximum permitted delay. The final part of this work addresses the question: what is the resultant long-term distribution of rates amongst flows, with equal round-trip times in a general network, that update their rates by the additive increase/multiplicative decrease algorithm? Contrary to what was previously believed, we find that the rate allocation is not proportionally fair, but is more closely represented by an allocation we derive.