Method and system of tracking missing packets in a multicast TFTP environment
View Patent ↗A method, system, and program product for efficiently tracking lost data packets in a multicast TFTP network environment. An algorithm is encoded within the receiving client processing system that tracks received packets within a 64 Kbit tracking array. The array is stored in memory. If the number of packets of a file being transmitted is larger than 64K, the algorithm performs a grouping function, by which each set of two neighboring spaces within the array are combined. Combining of the spaces involves ANDing the spaces together, and the ANDed results stored within a single space indicates whether or not the packets within the group needs to be re-requested. Thus if either one of the values in the spaces is a zero (indicating that the corresponding packet is lost) then the combined space is tagged with a zero. In this way, when the client is determining which packet(s) or groups to re-request, the client checks the array for holes (i.e., 0's) and re-requests the packet(s) represented by each hole found.
1. A system for tracking missing packets at a receiving terminal of a network transmission comprising:
processing logic;
a memory in which incoming packets and a tracking array are stored;
means for determining a maximum number N, corresponding to the number of sequentially numbered spaces within said tracking array utilized for tracking said incoming packets;
means for receiving an incoming packet and identifying a sequence number, M, of said incoming packet;
means, responsive to receipt of a packet with sequence number, M, that is greater than a current maximum number that may be tracked by said tracking array, for compressing spaces within said tracking array in multiples of X, where X is an integer, and N is a multiple of X, to create an array of N group values, wherein each group value indicates whether or not each packet within a particular group of packets assigned to a particular array space was received, wherein a number of packets within said particular group is initially 1 and increases by a factor of X after each compression; and
means for setting a value of said particular array space of said tracking array to a first value indicating receipt of all packets within said particular group of packets, wherein said value is set to a second value when all of said packets within said particular group of packets have not been received.
2. The system of claim 1 , further comprising:
means, responsive to a receipt of a final packet of a file being transmitted, for checking said array for occurrence of holes, each hole representing that at least one packet within a group was not received; and
means for issuing a request for each packet within a group whose array space contains a hole, wherein an entire group is re-requested when said hole is found.
3. The system of claim 1 , wherein:
Y packets are received at a time by said receiving terminal, where Y is an integer with value greater than 1, and said Y packets may be received out of sequential order with respect to each other
said system further comprising:
means for tracking each packet in a buffered storage area comprising a current group and at least one previous group, wherein each of said received packets are sorted into their respective groups before a received status of a group corresponding to the received packets is recorded within the array.
4. The system of claim 3 , wherein said tracking means further comprises:
means, responsive to a packet being in said at least one previous group or said current group, for respectively updating a status of said previous group or said current group within said buffer.
5. The system of claim 4 , wherein, responsive to all packets of a group being received, said system further comprises:
means for updating a received status of said group within said array to indicate receipt of said group; and
means for moving said group out of said buffer.
6. The system of claim 5 , wherein said group is a previous group, said system further comprising:
means for identifying said current group as a previous group, wherein a next group is selected as the current group; and
means, when a final packet has not been received, for subsequently tracking packets for said next current group within said buffer.
7. The system of claim 5 , wherein said updating step further comprises:
means, responsive to a receipt of a new packet not within said current group or said at least one previous group, for moving a first created previous group out of said buffer; and
means for updating a received status of said first created previous group within said array to indicate non-receipt of each packet of said first created previous group.
8. The system of claim 7 , wherein N is a multiple of 2, X is 2 and L is the number of packets in a current group, said system further comprising means for determining a group space, P, of a received packet by dividing said sequence number, M, of said packet by L, wherein a sum of a resulting quotient of said division+1 indicates the group space within the array and a remainder of said division indicates the position of the received packet within the particular group.
9. The system of claim 1 , said compression means further comprising means for ANDing each value within X adjacent spaces of said array to create a first set of group values stored within a first section of said array, wherein a second set of group values are determined when packets within subsequent groups are received after the compression and stored in a second section of said array.
10. A computer program product comprising:
a tangible computer readable medium; and
program code on said computer readable medium for tracking missing packets at a receiving terminal of a network transmission, said program code including code for:
determining a maximum number N, corresponding to the number of sequentially numbered spaces within said tracking array utilized for tracking said incoming packets;
receiving an incoming packet and identifying a sequence number, M, of said incoming packet;
responsive to receipt of a packet with sequence number, M, that is greater than a current maximum number that may be tracked by said tracking array, compressing spaces within said tracking array in multiples of X, where X is an integer, and N is a multiple of X, to create an array of N group values, wherein each group value indicates whether or not each packet within a particular group of packets assigned to a particular array space was received, wherein a number of packets within said particular group is initially 1 and increases by a factor of X after each compression; and
setting a value of said particular array space of said tracking array to a first value indicating receipt of all packets within said particular group of packets, wherein said value is set to a second value when all of said packets within said particular group of packets have not been received.
11. The computer program product of claim 10 , further comprising program code for:
responsive to a receipt of a final packet of a file being transmitted, checking said array for occurrence of holes, each hole representing that at least one packet within a group was not received; and
issuing a request for each packet within a group whose array space contains a hole, wherein an entire group is re-requested when said hole is found.
12. The computer program product of claim 10 , wherein:
Y packets are received at a time by said receiving terminal, where Y is an integer with value greater than 1, and said Y packets may be received out of sequential order with respect to each other;
said computer program product further comprising program code for:
tracking each packet in a buffered storage area comprising a current group and at least one previous group, wherein each of said received packets are sorted into their respective groups before a received status of a group corresponding to the received packets is recorded within the array.
13. The computer program product of claim 12 , wherein said program code for tracking further comprises program code for:
responsive to a packet being in said at least one previous group or said current group, respectively updating a status of said previous group or said current group within said buffer.
14. The computer program product of claim 13 , wherein, responsive to all packets of a group being received, said computer program product further comprises program code for:
updating a received status of said group within said array to indicate receipt of said group; and
moving said group out of said buffer.
15. The computer program product of claim 14 , wherein said group is a previous group, said computer program product further comprising program code for:
identifying said current group as a previous group, wherein a next group is selected as the current group; and
when a final packet has not been received, subsequently tracking packets for said next current group within said buffer.
16. The computer program product of claim 14 , wherein said program code for updating further comprises program code for:
responsive to a receipt of a new packet not within said current group or said at least one previous group, moving a first created previous group out of said buffer; and
updating a received status of said first created previous group within said array to indicate non-receipt of each packet of said first created previous group.
17. The computer program product of claim 16 , wherein N is a multiple of 2, X is 2 and L is the number of packets in a current group, said computer program product further comprising program code for determining a group space, P, of a received packet by dividing said sequence number, M, of said packet by L, wherein a sum of a resulting quotient of said division+1 indicates the group space within the array and a remainder of said division indicates the position of the received packet within the particular group.
18. The computer program product of claim 10 , said program code for compressing said array further comprises code for ANDing each value within X adjacent spaces of said array to create a first set of group values stored within a first section of said array, wherein a second set of group values are determined when packets within subsequent groups are received after the compression and stored in a second section of said array.
19. A communication network comprising:
a transmitting agent that transmits a file as a plurality of sequentially numbered packets; and
at least one receiving agent that receives said packet, wherein said receiving agent comprises:
processing logic;
a memory in which incoming packets and a tracking array are stored;
means for determining a maximum number N, corresponding to the number of sequentially numbered spaces within said tracking array utilized for tracking said incoming packets;
means for receiving an incoming packet and identifying a sequence number, M, of said incoming packet;
means, responsive to receipt of a packet with sequence number, M, that is greater than a current maximum number that may be tracked by said tracking array, for compressing spaces within said tracking array in multiples of X, where X is an integer, and N is a multiple of X, to create an array of N group values, wherein each group value indicates whether or not each packet within a particular group of packets assigned to a particular array space was received, wherein a number of packets within said particular group is initially 1 and increases by a factor of X after each compression; and
means for setting a value of said particular array space of said tracking array to a first value indicating receipt of all packets within said particular group of packets, wherein said value is set to a second value when all of said packets within said particular group of packets have not been received.
20. The communication network of claim 19 , further comprising:
means, responsive to a receipt of a final packet of a file being transmitted, for checking said array for occurrence of holes, each hole representing that at least one packet within a group was not received; and
means for issuing a request for each packet within a group whose array space contains a hole, wherein an entire group is re-requested when said hole is found.
21. The communication network of claim 19 , wherein:
Y packets are received at a time by said receiving terminal, where Y is an integer with value greater than 1, and said Y packets may be received out of sequential order with respect to each other;
said communication network further comprising:
means for tracking each packet in a buffered storage area comprising a current group and at least one previous group, wherein each of said received packets are sorted into their respective groups before a received status of a group corresponding to the received packets is recorded within the array.
22. The communication network of claim 21 , wherein said tracking means further comprises:
means, responsive to a packet being in said at least one previous group or said current group, for respectively updating a status of said previous group or said current group within said buffer.
23. The communication network of claim 22 , wherein, responsive to all packets of a group being received, said communication network further comprises:
means for updating a received status of said group within said array to indicate receipt of said group; and
means for moving said group out of said buffer.
24. The communication network of claim 23 , wherein said group is a previous group, said communication network further comprising:
means for identifying said current group as a previous group, wherein a next group is selected as the current group; and
means, when a final packet has not been received, for subsequently tracking packets for said next current group within said buffer.
25. The communication network of claim 23 , wherein said updating means further comprises:
means, responsive to a receipt of a new packet not within said current group or said at least one previous group, for moving a first created previous group out of said buffer; and
means for updating a received status of said first created previous group within said array to indicate non-receipt of each packet of said first created previous group.
26. The communication network of claim 25 , wherein N is a multiple of 2, X is 2 and L is the number of packets in a current group, said communication network further comprising:
means for determining a group space, P, of a received packet by dividing said sequence number, M, of said packet by L, wherein a sum of a resulting quotient of said division+1 indicates the group space within the array and a remainder of said division indicates the position of the received packet within the particular group.
27. The communication network of claim 19 , wherein said network supports multicast transmission.
28. The communication network of claim 19 , wherein said compression means further comprises means for ANDing each value within X adjacent spaces of said array to create a first set of group values stored within a first section of said array, wherein a second set of group values are determined when packets within subsequent groups are received after the compression and stored in a second section of said array.