Jitter control in QoS networks

We study jitter control in networks with guaranteed quality of service (QoS ) from the competitive analysis point of view: we propose on-line algorithm s that control jitter and compare their performance to the best possible (b y an off-line algorithm) for any given arrival sequence. For delay jitter, where the goal is to minimize the difference between delay times of differe nt packets, we show that a simple on-line algorithm using a buffer of B slo ts guarantees the same delay jitter as the best off-line algorithm using bu ffer space B/2. We prove that the guarantees made by our on-line algorithm hold, even for simple distributed implementations, where the total buffer s pace is distributed along the path of the connection, provided that the inp ut stream satisfies a certain simple property. For rate jitter, where the g oal is to minimize the difference between inter-arrival times, we develop a n on-line algorithm using a buffer of size 2B + h for any h greater than or equal to 1, and compare its jitter to the jitter of an optimal off-line al gorithm using buffer size B. We prove that our algorithm guarantees that th e difference is bounded by a term proportional to B/h.