VP/VC lookup function

• US 6,034,958 A
• Filed: 07/11/1997
• Issued: 03/07/2000
• Est. Priority Date: 07/11/1997
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Wicklund, Goran
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): Qureshi, Afsar M.
• Application Number:
  US08/893,479
• Time in Patent Office: 970 Days
• Field of Search: 370/392, 370/395, 370/396, 370/397, 370/399, 370/413, 370/473, 370/476, 370/401, 370/402, 370/403, 370/404, 709/200
• US Class Current: 370/395.32
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/253 using establishment or release of connections between ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• 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

A new, efficient approach to ATM connection table lookup minimizes the number of tables and memory lookups through use of hash coding and binary table search techniques. The virtual connection information associated with an incoming ATM cell is hash coded. The hash code provides a compressed representation of the virtual connection information--allowing the address space of a table accessed based on the hash code to be much smaller than the maximum number of possible virtual connection combinations that can be encoded in the ATM cell header without restricting the set of possible virtual connection combinations. A binary search based on the cell'"'"'s virtual connection information can be used to efficiently select, from plural records accessed based on the hash code, the particular search record corresponding to the cell'"'"'s connection.

Claims

1. In an ATM switch of the type that routes cells from an input port to an output port over a virtual connection based at least in part on virtual connection information provided within a cell header, a virtual path/virtual channel lookup process including the following steps:

(a) hash coding cell virtual connection information including Virtual Path, Virtual Channel and physical link information to provide a reduced length hash code; and

(b) searching for connection information based at least in part on the reduced length hash code.

2. A method as in claim 1 wherein hash coding step (a) includes the step of hash coding at least a virtual path identifier and a physical link identifier.

3. A method as in claim 1 wherein said searching step (b) includes the step of performing a binary search based at least in part on the hash code.

4. A method as in claim 1 wherein hash coding step (a) includes testing whether the virtual connection information corresponds to an active virtual path, and selectively masking at least a part of the virtual connection information based on the results of the test.

5. A method as in claim 4 wherein the selectively masking step comprises selectively masking a virtual channel identifier.

6. A method as in claim 1 wherein said method further includes the step of looking up a search table pointer based on the hash code, and searching step (b) includes accessing a search table based at least in part on the search pointer.

7. A method as in claim 1 wherein the hash coding step (a) includes performing a CRC polynomial division.

8. A method as in claim 1 wherein hash coding step (a) includes processing the virtual connection information at least in part with a feedback register and a network of XOR gates.

9. A method as in claim 1 wherein said searching step (b) includes performing a search based on the hash code and the virtual connection information.

10. A method as in claim 1 wherein said searching step (b) includes searching a search table for search records indexed by the hash code that contain matching virtual connection information.

11. A method as in claim 1 step (b) includes selecting plural records corresponding to the hash code, and selecting one of the plural records based on the virtual connection information.

12. A method as in claim 1 wherein step (a) includes generating a hash coding byproduct, and step (b) includes selecting plural records corresponding to the hash code, and selecting one of the plural records based on the hash coding byproduct.

13. A method as in claim 1 wherein said searching step (b) includes performing a multi-level binary search, and generating an error if a corresponding connection record is not found after a predetermined number of binary search levels.

14. A method as in claim 1 further including the step of balancing a binary search tree, and step (b) is performed by searching the balanced binary search tree.

15. A method as in claim 1 wherein the method further includes:

determining whether there is an active VPC based at least in part on both PHY and VPI virtual connection information; and

step (b) includes the step of determining whether there is an active VCC based on a search table indexed by the hash code.

16. In an ATM switch of the type that routes cells from an input port to an output port over a virtual connection based at least in part on virtual connection information providing within a cell header, a virtual path/virtual channel lookup arrangement comprising:

a hash coding block that hash codes cell virtual connection information to provide a reduced length hash code; and

a search table that searches for connection information based at least in part on the reduced length hash code.

17. An arrangement as in claim 16 wherein the hash coding block includes a feedback register and a gate array.

18. An arrangement as in claim 16 further including means for selectively masking a portion of the virtual connection information based on whether the virtual connection information corresponds to an active virtual path.

19. An arrangement as in claim 16 wherein the search table includes compare logic that compares the virtual connection information with at least portions of search records indexed by the hash code.

20. An arrangement as in claim 16 wherein the search table includes means for storing a binary search tree.

21. An arrangement as in claim 16 wherein the search table includes a memory that stores plural search records each including a virtual connection information field, a connection identifier field, a low field and a high field.

22. An arrangement as in claim 16 wherein the hash coding block hash codes a Virtual Path Identifier, a Virtual Channel Identifier and physical link information.

23. An arrangement as in claim 16 wherein the arrangement further includes a circuit that determines whether the virtual connection information corresponds to an active virtual path connection;

and the search table is used to determine whether the virtual connection information corresponds to an active Virtual Channel connection.

24. A virtual path/virtual channel lookup arrangement comprising:

hash coding means, connected to receive cell virtual connection information, for hash coding the cell virtual connection information to provide a reduced length hash code; and

connection information searching means, coupled to receive the reduced length hash code, for searching connection information based at least in part on the reduced length hash code.

25. An arrangement as in claim 24 wherein the hash coding means comprises means for hash coding a Virtual Path Identifier, a Virtual Channel Identifier and physical link information.

26. A cell routing method including:

(a) obtaining virtual connection corresponding to a cell;

(b) hash coding at least a part of the virtual connection information to provide a reduced length hash code;

(c) using the reduced length hash code, directly or indirectly, to look up a binary search tree stored in a search table, the binary search tree being capable of including plural search records;

(d) selecting one of the plural search records based at least in part on a comparison between the search record contents and the obtained virtual connection information;

(e) obtaining virtual connection information based on the selected search record; and

(f) routing the cell through a digital communications network based at least in part on the virtual connection information obtained by step (e).

27. A cell routing method as in claim 26 wherein the hash coding step (b) comprises hash coding at least portions of VPI, VCI and PHY information.

28. In an ATM cell routing determination arrangement that hash codes cell virtual connection information including VPI, VCI and physical link information to provide a reduced length hash code, a lookup method comprising:

(a) looking up a record in a first table based on a combination of both PHY, VPI virtual connection information;

(b) searching, based on said reduced length hash code, for a record in a second table based on a combination of the PHY, VPI virtual connection information and VCI virtual connection information;

(c) determining based on the first table look up whether the cell has an active virtual path connection; and

(d) determining based on the second table look up whether the cell has an active Virtual Channel connection.

29. A method as in claim 28 wherein step (b) comprises searching the second table based on a selectively masked VCI hash coded with PHY and VPI to provide said reduced length hash code.

30. A method as in claim 28 further including routing the cell based on information derived from the record obtained from the second table.