Jitter regulation in an Internet router with delay constraint

To playback multimedia data smoothly via the world-wide Internet, jitter, the variability of delay of individual packets, must be kept low. We examine on-line algorithms in a router to regulate jitter for a given multimedia stream by holding packets in an internal buffer. The previous work solved the problem with focusing only on the buffer size, allowing a packet to stay in the router infinitely long unless the internal buffer is full. This assumption is unrealistic for many real-time applications. Our main contribution is to introduce a new constraint that a packet can stay in the router at most for a constant time which we name the permitted delay time in order to provide the stream communication with real-time property, besides the conventional constraint about the buffer size. We present a nearly optimal on-line algorithm in terms of competitiveness for this new version of the problem. Our analysis yields the result that the competitiveness of on-line algorithms depends on the permitted delay time rather than the buffer size. We also make clear quantitatively how much jitter is removed by our on-line algorithm.