Abstract
In this paper we propose to construct an flexible delay line with maximum delay d by parallel non-overtaking delay lines. We show that for a fixed number of non-overtaking delay lines, an optimal policy to minimize packet losses is to assign arriving packets to the non-overtaking delay line that has the largest residual service time while maintaining the FIFO order for each non-overtaking delay lines. Based on this optimal policy we show that to exactly emulate an flexible delay line, one needs (d + 1)/2 non-overtaking delay lines. We also show that if one can tolerate a small packet loss probability, one just needs O(√d) non-overtaking delay lines. In this case, we show that the residual service times of the non-overtaking delay lines behaved as if they followed the order statistics of uniform random variables. © 2009 IEEE.