Look-up engine for packet-based network

• US 5,917,821 A
• Filed: 08/16/1996
• Issued: 06/29/1999
• Est. Priority Date: 12/24/1993
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent Canada Incorporated (Nokia Corporation)
• Original Assignee: Newbridge Networks Corporation (Nokia Corporation)
• Inventors: Gobuyan, Jerome, Burwell, Wayne, Behki, Nutan
• Primary Examiner(s): NGUYEN, CHAU T
• Application Number:
  US08/663,263
• Time in Patent Office: 1,047 Days
• Field of Search: 370/392, 370/395, 370/400, 370/401-405, 370/465, 370/466, 370/351, 370/389, 370/396, 370/397, 370/474, 395/200.68
• US Class Current: 370/392
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

An arrangement is disclosed for parsing packets in a packet-based data transmission network. The packets include packet headers divided into fields having values representing information pertaining to the packet. The arrangement includes an input receiving fields from the packet headers of incoming packets, a memory for storing information related to possible values of said fields, and a device for retrieving the stored information appropriate to a received field value. The retrieving device comprises a look-up engine including at least one memory organized in a hierarchical tree structure, and a controller for controlling the operation of the memory. The arrangement is capable of performing fast look-up operations at a low cost of implementation.

Claims

1. An arrangement for parsing packets in a packet-based digital communications network, said packets including packet headers divided into fields having values representing information pertaining to the packet, said arrangement comprising:

a) an input memory for receiving fields from said packet headers of incoming packets; and

(b) a look-up engine for retrieving stored information appropriate to a received field value, said look-up engine including;

(i) at least one memory storing information related to possible values of said fields in a hierarchical tree structure and associated with a respective field of packet headers;

(ii) a memory controller associated with each said memory storing information related to possible values of said fields for controlling the operation thereof to retrieve said stored information therefrom; and

(iii) a microcode controller for parsing a remaining portion of the packet header while said stored information is retrieved and controlling the overall operation of said look-up engine.

2. An arrangement as claimed in claim 1, wherein said memory controller associated with each said memory compares, at each decision point on the tree structure, the current field with a stored value or range, and moves to the next decision point by moving a pointer for the current field and branching to new code if said comparison results in a first logical condition, and if said comparison results in a second logical condition the current field is compared to a different value or range, and so on until said comparison results in said first logical condition.

3. An arrangement as claimed in claim 1, wherein said controller associated with each said memory compares values based on successive nibbles of a field value in said memory with stored values to locate the related information.

4. An arrangement as claimed in claim 3, wherein said memory controller associated with each said memory concatenates a first nibble of an incoming field value with a root pointer to obtain an index to a root pointer array, retrieves a word at a location identified by said index, concatenates the next nibble with the retrieved word to form the next pointer and so on until said related information is retrieved.

5. An arrangement as claimed in claim 1, wherein said at least one memory is a random access memory (RAM).

6. An arrangement as claimed in claim 1, wherein one of said fields comprises a destination address and said related information comprises the path data associated with said respective destination addresses.

7. An arrangement as claimed in claim 1, wherein a plurality of said memories storing information related to possible values of said fields in a hierarchical tree structure operate in parallel and are associated with respective fields of said packet headers.

8. An arrangement as claimed in claim 7, wherein each said memory is a random access memory (RAM).

9. An arrangement as claimed in claim 7, wherein one of said fields comprises a destination address and said related information comprises the path data associated with said destination address, and another of said fields comprises a source address, and said look-up engine also locates path data associated with the source in parallel with the location of the path data associated with the destination address.

29. An arrangement as claimed in claim 1, wherein said at least one memory provides table look-ups using nibble indexing for variable portions of the packet header and said microcode controller employs bit pattern recognition on fixed portions of the packet header for network layer protocol determination.

10. An arrangement for parsing packets in a packet-based digital communications network, said packets including packet headers divided into fields having values representing information pertaining to the packet, said arrangement comprising:

(a) an input memory for receiving fields from said packet headers of incoming packets; and

(b) a look-up engine for retrieving stored information appropriate to a received field value, said look-up engine including;

(i) a plurality of memories storing information related to possible values of said fields in a hierarchical tree structure and operating in parallel, said memories being associated with respective fields of said packet headers;

(ii) a main controller controlling overall operation of the look-up engine; and

(iii) a memory controller associated with each said respective memory for controlling the operation thereof to retrieve said stored information therefrom.

11. An arrangement as claimed in claim 10, wherein said main controller is a microcode.

12. An arrangement as claimed in claim 11, wherein said microcode controller comprises an interface memory for receiving headers of incoming packets, a station information block memory for storing information pertaining to endstations, a microcode memory storing microcode instructions, and logic circuitry for implementing said microcode instructions.

13. An arrangement as claimed in claim 11, wherein said microcode controller parses the remainder of the packet header using a specific instruction set while said information is retrieved from said plurality of memories.

14. An arrangement as claimed in claim 13, wherein said microcode controller comprises separate buses for instructions and data.

15. An arrangement as claimed in claim 14, wherein said microcode controller is arranged to implement optimized instructions that perform bit level logical comparisons and conditional branches within the same cycle and other instructions tailored to retrieving date from nibble-indexed data structures.

16. An arrangement as claimed in claim 15, wherein said microcode controller is implemented as an ASIC processor.

17. An arrangement for parsing packets in a packet-based digital communications network, said packets including packet headers including destination and source address fields, said arrangement comprising:

(a) an input memory for receiving fields from said packet headers of incoming packets; and

(b) a look-up engine for retrieving stored information appropriate to a received field value, said look-up engine including;

(i) a source address look-up engine including a memory storing information related to possible values of said source address field in a hierarchical tree structure;

(ii) a memory controller associated with said source look-up engine for controlling the operation thereof to retrieve stored information therefrom;

(iii) a destination address look-up engine including a memory storing information related to possible values of said destination address field in a hierarchical tree structure;

(iv) a memory controller associated with said destination look-up engine for controlling the operation thereof to retrieve stored information therefrom;

(v) a processor controlling overall operation of said source and destination address look-up engines, said source and destination address look-up engines and said processor operating in parallel.

18. An arrangement as claimed in claim 17, wherein said processor is a microcode controller.

19. An arrangement as claimed in claim 18, wherein said memory controllers compare, at each decision point on the tree structure, the current field with a stored value or range, and move to the next decision point by moving a pointer for the current field and branching to new code if said comparison results in a first logical condition, and if said comparison results in a second logical condition, the current field is compared to a different value or range, and so on until said comparison results in said first logical condition.

20. An arrangement for parsing packets in a packet-based digital communications network, said packets including packet headers including destination and source address fields, said arrangement comprising:

(a) an input memory for receiving fields from said packet headers of incoming packets; and

(b) a look-up engine for retrieving stored information appropriate to a received field value, said look-up engine including;

(i) a source address look-up engine including a memory storing information related to possible values of said source field in a hierarchical tree structure;

(ii) a memory controller associated with said source look-up engine for controlling the operation thereof to retrieve stored information therefrom;

(iii) a destination address look-up engine including a memory storing information related to possible values of said destination field in a hierarchical tree structure and an associated memory controller;

(iv) a memory controller associated with said destination look-up engine for controlling the operation thereof to retrieve stored information therefrom; and

iii) a microcode processor controlling overall operation of said source and destination address look-up engine, said source and destination address look-up engines and said processor operating in parallel, and said microcode processor being arranged to parse additional fields in said packet header while said source and destination address look-up engines retrieve said related information.

21. An arrangement as claimed in claim 20 wherein said microcode processor comprises an interface memory for receiving said incoming packets, a station information block memory for storing information pertaining to endstations, a microcode memory storing microcode instructions, and logic circuitry for implementing said instructions.

22. A method of parsing packets in a packet-based digital communications network, said packets including packet headers divided into fields having values representing information pertaining to the packet, comprising the steps of:

(a) receiving fields of packet headers from incoming packets in an input memory;

(b) retrieving stored information appropriate to a received field value by performing a tree search in a look-up engine having at least one memory storing information related to possible values of said fields in a hierarchical tree structure and associated with a respective field of packet headers, said at least one memory being controlled by a memory controller associated therewith to retrieve said stored information therefrom; and

(c) parsing a remaining portion of the packet header while said stored information is being retrieved from said at least one memory with a main controller, which main controller also controls the overall operation of said look-up engine.

23. A method as claimed in claim 22, wherein at each decision point in the tree search, in retrieving said information the current field is compared with a stored value or range, a pointer for the current field is moved and branched to new code if said comparison results in a first logical condition, and if said comparison results in a second logical condition, the current field is compared to a different value or range, and so on until said comparison results in said first logical condition.

24. A method as claimed in claim 22, wherein values based on successive nibbles of a field value are compared with stored values to locate the related information.

25. A method as claimed in claim 24, wherein a first nibble of an incoming field value is concatenated with a root pointer to obtain an index to a root pointer array, a word at a location identified by said index is retrieved, the next nibble is concatenated with the retrieved word to form the next pointer and so on until said related information is retrieved.

26. A method as claimed in claim 22, wherein information related to a plurality of fields is retrieved in parallel.

27. A method as claimed in claim 26, wherein one of said fields comprises a destination address and said related information comprises the path data associated with said respective destination address, and another of said fields comprises a source address and said related information comprises the path data associated with said source address.

28. A method of parsing packets in a packet-based digital communications network, said packets including packet headers divided into fields having values representing information pertaining to a packet, comprising the steps of:

(a) storing in memory information related to possible values of said fields in a hierarchical tree structure;

(b) receiving a plurality fields from said packet headers of incoming packets, one of said fields being a destination address and said related information therefor comprising path data associated with said respective destination address, and another of said fields being a source address and said related information therefor comprising path data associated with said source address;

(c) retrieving in parallel said stored information appropriate to received field values by performing a tree search under the control of a microcode controller; and

(d) parsing a remaining portion of the packet header using a specific instruction set while said related information is retrieved.