ALGORITHM FOR COMPUTING REORDER DENSITY (LATE/EARLY) ***************************************************** Variables used: RI: receive_index. S: Arrival under consideration for lateness/earliness computation. D: Lateness or earliness of a packet. FLE[ -DT..DT]: Frequency of lateness and earliness. window[1..DT+1]: List of incoming sequence numbers. buffer[1..DT]: Array to hold sequence numbers of early arrivals. window[] and buffer[] are empty at the beginning. Step 1. Initialize: Store first unique DT+1 sequence numbers in arriving order into window; RI = 1; Step 2. Repeat: If (window or buffer contains sequence number RI) { Copy first sequence number in window to S; Delete first sequence number from window; D = RI - S; # compute displacement If (absolute(D) <= DT) # Apply threshold { FLE[D]++; # Update frequency If (buffer contains sequence number RI) Delete RI from buffer; If (D < 0) # Early Arrival add S to empty slot in buffer; RI++; # Update RI value } Else # Displacement beyond threshold. { Discard S; } # Get next incoming non-duplicate sequence number, if any. newS = get_next_arrival(); # subroutine called* if (newS != null) { add newS to window; } if (window is empty) go to step 3; } Else # RI not found. Get next RI value. { # Next RI is the minimum among window and buffer contents. m = minimum (minimum (window), minimum (buffer)); If (RI < m) RI = m; Else RI++; } Step 3. Normalize FLE to get RD; * Get a new sequence number from packet stream, if any subroutine get_next_arrival() { do # get non-duplicate next arrival { newS = new sequence from arriving stream; if (newS == null) # End of packet stream return null; } while (newS < RI or newS in buffer or newS in window); return newS; }