Question
When Bob wants to send Alice a message M on the Internet, he breaks M into n data packets, numbers the packets consecutively, and injects them into the network. When the packets arrive at Alice’s computer, they may be out of order, so Alice must assemble the sequence of n packets in order before she can be sure she has the entire message. Describe an efficient scheme for Alice to do this. What is the running time of this algorithm?
Answer
To efficiently assemble the sequence of n packets in order, Alice can use the following scheme:
- Alice maintains a buffer to store the received packets until they can be properly ordered.
- As each packet arrives, Alice checks its packet number.
- If the packet number is the next expected packet number, Alice immediately processes it.
- If the packet number is out of order, Alice places it in the buffer.
- After receiving a packet, Alice checks if there are any buffered packets that are now in the correct order. If so, she processes them.
- Alice repeats steps 4 and 5 until all packets have been received and processed.
By using this scheme, Alice ensures that packets are processed and assembled in the correct order, even if they arrive out of order.
- The running time of this algorithm depends on the efficiency of the data structures used for buffering and packet processing.
- If a suitable data structure like a priority queue (min-heap) is used for buffering, the time complexity of inserting a packet into the buffer is O(log n), where n is the number of packets in the buffer. The time complexity of processing a packet is O(1) since it only requires extracting the next packet from the buffer.
Therefore, the overall running time of the algorithm would be determined by the number of packets and the efficiency of the buffering data structure. In the worst-case scenario, where packets arrive in completely random order, the algorithm's running time can be approximated as O(n log n), assuming efficient data structures are used.