Packet Reassembler

Data Structures Algorithm System Design

You are tasked with designing and implementing a class (or module) called PacketReassembler that deals with the challenge of out-of-order network packet arrivals. Each packet is represented as an object (or dictionary) with two properties:

  • sequence: an integer starting from 1 that indicates the packet's order in the overall message.
  • payload: a non-empty string containing part of the overall message.

The packets will be received in arbitrary order. Implement the following functionality:

  1. A method (e.g., receive(packet)) which takes a packet as input and stores it until it and all preceding packets have been received.
  2. Once a packet is received that allows the assembly of a continuous sequence starting from sequence number 1, output (or return) the concatenated payloads of the packets from sequence number 1 up to the highest sequence number that forms an unbroken chain.

For example, if the PacketReassembler receives packets in the order:

  • Packet with sequence 1,
  • Packet with sequence 3,
  • Packet with sequence 2,

then the system should wait after receiving packet 3 (since packet 2 is missing) and once packet 2 is received, it should output the full concatenated message corresponding to packets 1, 2, and 3.

Your solution should also consider how the class might handle high throughput and a large volume of packets arriving out of order. Write code to simulate receiving packets in an arbitrary order and demonstrate that your reassembler correctly outputs completed segments of the overall message as soon as they become available.

Feel free to design any helper functions or data structures that you find appropriate for ensuring both correctness and efficiency.


Loading...