Method for prevention of out-of-order delivery of data

• US 20050259659A1
• Filed: 05/20/2004
• Published: 11/24/2005
• Est. Priority Date: 05/20/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Vaidhyanathan, Natarajan, Verplanken, Fabrice J., Basso, Claude, Calvignac, Jean L.
• Granted Patent: US 7,333,493 B2
• Time in Patent Office: Days
• US Class Current: 370/394
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/166 IP fragmentation; TCP segmentation
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method for sequencing delivery of information packets from a router having several processing elements to a receiving processing installation, wherein delivery of the packets must be completed in the order the packets arrive at the router. A linked list of packets is formed in the order they are received at the router, and each packet fragmented into successive fragments. Each fragment is processed at the router. The last fragment of each packet in each linked list is labeled with the sequence in which the packet was received, and enqueued in the order labeled for each last fragment on each linked list. Each fragment of each packet is delivered as processed, except the last fragment of each packet on its linked list to the receiving processor installation, and thereafter, transmitting the final fragment of each packet after processing only if that fragment is at the head of the queue.

Claims

1. A method of sequencing the delivery of a series of packets of information from a router which has a first processor installation having a plurality of processor elements, to a second processor installation, and wherein delivery of said packets of information must be completed in the order in which said packets arrive at the first processor installation, comprising the steps of:

forming a linked list of the packets of information in the order in which said packets of information are received at said first processor installation;

fragmenting each packet of information into successive fragments and processing each fragment at said first processor installation;

labeling the last fragment of each packet of information in each linked list with the sequence in which the packet was received and enqueuing the order marked for each last fragment in each linked list;

delivering each fragment of each packet as processed at said first processor installation on a given linked list, except the last fragment of each packet on said linked list to said second processor installation;

thereafter transmitting the final fragment of each packet after processing if, and only if, that fragment is at the head of the queue on said linked list, and removing that fragment from the queue when transmitted; and

reassembling each packet of information from said fragments at said second processor installation after all the fragments of said given packet of information are received at said second processor installation.

2. The invention as defined in claim 1 wherein there are multiple linked lists, and wherein multiple packets of information are transmitted from each linked list.

3. The invention as defined in claim 1 wherein the fragments of each packet of information are transmitted in the order in which they are fragmented.