ALGORITHM TO COMPUTE REORDER BUFFER-OCCUPACNY DENSITY Date: 10/06/2004 ****************************************************** Variables used: E: Next expected sequence number. S: Sequence number of the next arrived packet. B: Current buffer occupancy. BT: Occupancy threshold window[1..BT+1]: List of incoming sequence numbers. buffer: Hypothetical buffer. FB[i]: Frequency of buffer occupancy i (0 <= i <= BT). 1. Initialize. Store first unique BT+1 sequence numbers in arriving order into window; 2. Repeat. # The smallest element in window is taken as E to neglect lost packets. E = smallest sequence number in window; # Following is regular RBD processing. S = first sequence number in window; Delete first sequence number from window; If (S == E) # Next expected packet arrived. { Repeat # Until loop is not broken { If (buffer not empty) { M = smallest sequence number in window and buffer; # If M is present in buffer, it can be freed. If (M is present in buffer) Delete M from buffer; Else break loop; } Else break loop; } # E should be modified to detect duplicates correctly E = smallest sequence number in window; } Else add S to buffer; # S is an early arrival. Add it to the buffer. B = number of occupied slots in buffer; FB[B]++; # Increment frequency of current buffer occupancy. # Get next incoming non-duplicate sequence number, if any. # A sequence number <= E or present in window or buffer is duplicate. Do { newS = get next incoming sequence number; } While (newS is valid and (newS <= E or newS is in window or buffer)); If (newS is valid) { Add newS to window; } If (window is empty) go to step 3; 3. Normalize FB to get RBD.