Method of associating forwarding references with data packets by means of a TRIE memory, and packet processing device applying such method

• US 6,704,313 B1
• Filed: 01/28/2000
• Issued: 03/09/2004
• Est. Priority Date: 02/12/1999
• Status: Expired due to Term

• Current Assignee: Monarch Networking Solutions LLC (Acacia Research Corporation)
• Original Assignee: Orange S.A.
• Inventors: Guesdon, Herve, Bonjour, Servane, Lattmann, Joel, Duret, Christian
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): HA, YVONNE QUY M
• Application Number:
  US09/493,583
• Time in Patent Office: 1,502 Days
• Field of Search: 370/254, 370/256, 370/363, 370/368, 370/392, 370/389, 370/393, 370/395.32, 370/392.52, 711/216
• US Class Current: 370/392
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Different portions of a header of each packet containing protocol data are analyzed in succession from different gate registers of the TRIE memory. As a packet arrives, its header is stored in a buffer memory and a first portion of the stored header is analyzed. Each analysis of a portion of header produces either the forwarding reference associated with the packet or an intermediate reference containing a first code, making it possible to locate at an arbitrary location of the buffer memory a next portion to be analyzed, and a second code, making it possible to locate at an arbitrary location of the TRIE memory a gate register from which this next portion is to be analyzed. Having analyzed the first portion of a stored header, the subsequent portions thereof are analyzed in accordance with the first and second codes contained in the intermediate references produced in succession until the forwarding reference is produced.

Claims

1. A method of associating forwarding references to data packets by means of a TRIE memory, which comprises analysing in succession, from different gate registers of the TRIE memory, different portions of a header of each packet, said header containing protocol data, wherein in response to the arrival of a packet, the header of said packet is stored in a buffer memory and a first portion of the stored header is analysed, wherein each analysis of a header portion of a packet produces either the forwarding reference associated with the packet or an intermediate reference containing a first code, making it possible to locate at any location of the buffer memory a next portion to be analysed, and a second code, making it possible to locate, at any location of the TRIE memory, a gate register from which said next portion is to be analysed, and wherein, after the first portion of a stored header has been analysed, subsequent portions of said header are analysed in accordance with the first and second codes contained in the intermediate references produced in succession until the forwarding reference is produced.

2. A method as claimed in claim 1, wherein the TRIE memory comprises elementary cells, each having a field indicating whether the cell contains a forwarding reference, and wherein each elementary cell which does not contain a forwarding reference has at least a first field to contain a piece of information designating a location of the buffer memory at which the analysis is to be continued and a second field to contain a piece of information designating a continue analysis register of the TRIE memory.

3. A method as claimed in claim 2, wherein said information designating a location of the buffer memory at which the analysis is to be continued contains a format code indicating a numerical representation of said location of the buffer memory and an address code designating said location of the buffer memory in accordance with said representation.

4. A method as claimed in claim 3, wherein the format code indicates (i) a sequential representation whereby the data elements of the stored header are analysed in the order in which they appear, (ii) an absolute representation whereby the next data element to be analysed is designated by its absolute position in the stored header, (iii) a differential representation whereby the next data element to be analysed is designated by its position relative to the data element currently being analysed or (iv) a relative representation whereby the next data element to be analysed is designated by its position relative to a given portion of the stored header.

5. A method as claimed in claim 2, wherein each elementary cell which does not contain a forwarding reference has an additional field which contains a piece of information indicating whether a counting operation is necessary and wherein each elementary cell which does not contain a forwarding reference and whose additional field indicates that a counting operation is necessary has, in its second field, a pointer to a memory location containing a counter to be incremented when said operation is performed and associated with another memory location containing a pointer to the continue analysis register of the TRIE memory.

6. A method as claimed in claim 1, wherein each elementary cell of the TRIE memory has a command field which contains instructions for an auxiliary controller.

7. A method as claimed in claim 6, wherein a forwarding reference is issued from the TRIE memory with parameters applied to the controller so as to specify any amendments to be applied on a portion of the header of the packet stored in the buffer memory.

8. A packet processing device having a circuit for analysing the header of packets received, using an associative TRIE memory having a plurality of gate registers, said headers containing protocol data, said circuit comprising a buffer memory, means for storing the header of each arriving packet in the buffer memory and means for analysing in succession, from different gate registers of the TRIE memory, different portions of each stored header from a first portion of the stored header, wherein said means for analysing are arranged to produce, upon each analysis of a header portion of a packet, either a forwarding reference associated with the packet or an intermediate reference containing a first code, making it possible to locate at any location of the buffer memory a next portion to be analysed, and a second code, making it possible to locate, at any location of the TRIE memory, a gate register from which said next portion is to be analysed, whereby after the first portion of a stored header has been analysed, subsequent portions of said header are analysed in accordance with the first and second codes contained in the intermediate references produced in succession until the forwarding reference is produced.

9. A packet processing device as claimed in claim 8, wherein the TRIE memory comprises elementary cells, each having a field indicating whether the cell contains a forwarding reference, and wherein each elementary cell which does not contain a forwarding reference has at least a first field to contain a piece of information designating a location of the buffer memory at which the analysis is to be continued and a second field to contain a piece of information designating a continue analysis register of the TRIE memory.

10. A packet processing device as claimed in claim 9, wherein said information designating a location of the buffer memory at which the analysis is to be continued contains a format code indicating a numerical representation of said location of the buffer memory and an address code designating said location of the buffer memory in accordance with said representation.

11. A packet processing device as claimed in claim 10, wherein the format code indicates (i) a sequential representation whereby the data elements of the stored header are analysed in the order in which they appear, (ii) an absolute representation whereby the next data element to be analysed is designated by its absolute position in the stored header, (iii) a differential representation whereby the next data element to be analysed is designated by its position relative to the data element currently being analysed or (iv) a relative representation whereby the next data element to be analysed is designated by its position relative to a given portion of the stored header.

12. A packet processing device as claimed in claim 9, wherein each elementary cell which does not contain a forwarding reference has an additional field which contains a piece of information indicating whether a counting operation is necessary and wherein each elementary cell which does not contain a forwarding reference and whose additional field indicates that a counting operation is necessary has, in its second field, a pointer to a memory location containing a counter to be incremented when said operation is performed and associated with another memory location containing a pointer to the continue analysis register of the TRIE memory.

13. A packet processing device as claimed in claim 8, further comprising an auxiliary controller, and wherein each elementary cell of the TRIE memory has a command field for containing instructions for the auxiliary controller.

14. A packet processing device as claimed in claim 13, wherein a forwarding reference is issued from the TRIE memory with parameters applied to the controller so as to specify any amendments to be applied on a portion of the header of the packet stored in the buffer memory.