Passive packet re-ordering and packet loss detection
View Patent ↗A plurality of packets are received at a receiver. The plurality of packets are sent in a first ordering from a transmitter and received in a second ordering. The second ordering is different from the first ordering. The packets, when they were sent, are assigned sequence numbers based on the first ordering. As each of the plurality of packets is received in the second ordering, a packet is written to a buffer position in a buffer based on the sequence number associated with the packet. The writes to the buffer positions are out of order or in a non-sequential order as compared to a sequential ordering of buffer positions in the buffer. Packets are then read from the buffer in a sequential order. As packets are read from the buffer, they are read in the first ordering that the packets were sent in.
1. A method for reordering packets sent through a telecommunications network, the method comprising:
receiving a plurality of packets, the plurality of packets sent in a first ordering and received in a second ordering, wherein each packet comprises a plurality of location bits and a plurality of loss detection bits distinct from the plurality of location bits, and wherein a sequence number associated with each packet is determined according to its location bits;
as each packet in the plurality of packets is received in the second ordering, writing a packet to a buffer based on the sequence number associated with the packet, wherein writes of packets in the plurality of packets as the packets are received are to non-sequential buffer locations in the buffer;
reading a first packet from the buffer and establishing an expected value for packets in the buffer based on the plurality of loss detection bits corresponding to the first packet;
reading additional packets from the buffer in a sequential order, wherein the additional packets read from the buffer in the sequential order are read in the first order; and
determining, for each additional packet read from the buffer, a packet loss condition based on the loss detection bits of the additional packet and the expected value.
2. The method of claim 1 , wherein the plurality of packets are received in a streaming manner.
3. The method of claim 1 , further comprising:
determining a first sequence number of a first packet received in the plurality of packets; and
associating the first sequence number with a first buffer location in the buffer.
4. The method of claim 3 , further comprising:
determining a second sequence number of a second packet received in the plurality of packets; and
associating the second sequence number with a second buffer location in the buffer.
5. The method of claim 4 , further comprising:
determining a third sequence number of a third packet received in the plurality of packets; and
associating the third sequence number with a third buffer location in the buffer.
6. The method of claim 5 , wherein the third sequence number is before the second sequence number in the first ordering, wherein the third buffer location is before the second buffer location in the buffer.
7. The method of claim 6 , wherein the first buffer location is determined based on the first sequence number, the second buffer location is determined based on the second sequence number and the third buffer location is determined based on the third sequence number.
8. The method of claim 1 , further comprising:
determining a position of the first packet in the buffer; and
sequentially reading packets after the first packet in sequential positions in the buffer.
9. The method of claim 1 , wherein establishing the expected value comprises:
determining if a packet in the plurality of packets is a first packet in a communication; and
if the packet is the first packet, determining the expected value using at least a part of a sequence number associated with the first packet.
10. The method of claim 1 , wherein writing the packet to the buffer location comprises writing a reference to the packet.
11. The method of claim 10 , wherein reading packets from the buffer locations comprises reading a reference from the buffer and using the reference to retrieve the packet.
12. A method for reordering packets, the method comprising:
receiving a first packet in a plurality of packets, each of said packets comprising a plurality of location bits and a plurality of loss detection bits distinct from the plurality of location bits;
determining a first sequence number for the first packet based on its location bits;
writing the first packet to a first buffer position in a buffer;
receiving a series of packets after the first packet, each packet associated with a sequence number, the series of packets received in a first order different than a second order the series of packets were sent;
determining, for each packet in the series of packets, a sequence number according to its location bits;
writing the series of packets, in the first order the series of packets were received, to buffer positions in the buffer based on a sequence number for each packet, the series of packets written to non-sequential buffer locations as compared to the first order; and
reading the first packet from the buffer and establishing an expected value for packets in the buffer based on the plurality of loss detection bits associated with the first packet;
reading additional packets from locations in the buffer in a sequential order, wherein the additional packets read from the buffer locations in the sequential order are read in the second order; and
determining, for each additional packet read from the buffer, a packet loss condition based on its loss detection bits and the expected value.
13. The method of claim 12 , wherein the plurality of packets are received in a streaming manner.
14. The method of claim 12 , wherein the plurality of packets are sent in a communication.
15. The method of claim 12 , further comprising determining that a packet is the first packet in a communication.
16. The method of claim 15 , further comprising recording the sequence number of the first packet in the communication.
17. A system for reordering packets, the system comprising:
a sender node configured to send a plurality of packets in a first order, wherein each packet in the plurality of packets comprises a plurality of location bits and a plurality of loss detection bits distinct from the plurality of location bits;
a receiver node configured to receive the plurality of packets, wherein packets in the plurality of packets are received in a second order, the receiver node comprising a buffer, wherein the receiver node is configured to:
for each packet in the plurality of packets, write a packet to a buffer location based on a sequence number associated with the packet, wherein writes of packets in the plurality of packets are to non-sequential buffer locations in the buffer;
read a first packet from the buffer and establish an expected value for packets in the buffer based on the plurality of loss detection bits corresponding to the first packet;
read additional packets from buffer locations in the buffer in a sequential order, wherein the additional packets read from the buffer locations in the sequential order are read in the first order; and
determine, for each additional packet read from the buffer, a packet loss condition based on its loss detection bits and the expected value.
18. A telecommunications device for reordering packets sent through a telecommunications network, the device comprising:
logic configured to receive a plurality of packets, the plurality of packets sent in a first ordering and received in a second ordering, wherein each packets in the plurality of packets comprises a plurality of location bits and a plurality of loss detection bits distinct from the plurality of location bits, and wherein a sequence number associated with each packet is determined according to its location bits;
as each packet in the plurality of packets is received in the second ordering, logic configured to write a packet to a buffer based on a sequence number associated with the packet, wherein writes of packets in the plurality of packets as the packets are received are to non-sequential buffer locations in the buffer;
logic configured to read a first packet from the buffer and establish an expected value for packets in the buffer based on the plurality of loss detection bits corresponding to the first packet;
logic configured to read additional packets from buffer locations in the buffer in a sequential order, wherein the additional packets read from the buffer in the sequential order are read in the first order; and
logic configured to determine, for each additional packet read from the buffer, a packet loss condition by comparing the loss detection bits of the additional packet to the expected value.
19. The telecommunications device of claim 18 , wherein the plurality of packets are received in a streaming manner.
20. The telecommunications device of claim 18 , further comprising:
logic configured to determine a first sequence number of a first packet received in the plurality of packets; and
logic configured to associate the first sequence number with a first buffer location in the buffer.
21. The telecommunications device of claim 20 , further comprising:
logic configured to determine a second sequence number of a second packet received in the plurality of packets; and
logic configured to associate the second sequence number with a second buffer location in the buffer.
22. The telecommunications device of claim 21 , further comprising:
logic configured to determine a third sequence number of a third packet received in the plurality of packets; and
logic configured to associate the third sequence number with a third buffer location in the buffer.
23. The telecommunications device of claim 22 , wherein the third sequence number is before the second sequence number in the first ordering, wherein the third buffer location is before the second buffer location in the buffer.
24. The telecommunications device of claim 23 , wherein the first buffer location is determined based on the first sequence number, the second buffer location is determined based on the second sequence number and the third buffer location is determined based on the third sequence number.
25. A telecommunications device for reordering packets, the telecommunications device comprising:
logic to receive a first packet in a plurality of packets each of said packets comprising a plurality of location bits and a plurality of loss detection bits distinct from the plurality of location bits;
logic to determine a first sequence number for the packet based on its location bits;
logic to write the first packet to a first buffer position in a buffer;
logic to receive a series of packets after the first packet, each packet associated with a sequence number, the series of packets received in a first order different than a second order the series of packets were sent;
logic to determine, for each packet in the series of packets, a sequence number according to its location bits;
logic to write the series of packets, in the first order the series of packets were received, to a buffer based on a sequence number for each packet, the series of packets written to non-sequential buffer locations as compared to the first order; and
logic to read the first packet from the buffer and establish an expected value for packets in the buffer based on the plurality of loss detection bits associated with the first packet;
logic configured to read additional packets from the buffer in a sequential order, wherein the additional packets read from the buffer in the sequential order are read in the second order; and
logic configured to determine, for each additional packet read from the buffer, a packet loss condition based on its loss detection bits and the expected value.
26. The telecommunications device of claim 25 , wherein the first packet and the second packet are received in a streaming manner.