US6034958A
Expired / Lapsed
US
⏱️ 0.0 years remaining
VP/VC lookup function
Assignee: Telefonaktiebolaget LM Ericsson AB
•
Filing: 1997-07-11
•
Granted: 2000-03-07
•
Expires: 2017-07-11
Abstract
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.
Inventors
- 👤 Goran Wicklund
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 10:28
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/30; H04L49/3081; H04L45/00; H04L45/74; H04L45/745; H04L49/3009; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L49/25; H04L49/253
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
86 words
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.
Claim 2
Dependent Claim
86 words
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.
Claim 3
Dependent Claim
28 words
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.
Claim 4
Dependent Claim
28 words
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.
Claim 5
Dependent Claim
43 words
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.
Claim 6
Dependent Claim
18 words
A method as in claim 4 wherein the selectively masking step comprises selectively masking a virtual channel identifier.
Claim 7
Dependent Claim
43 words
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.
Claim 8
Dependent Claim
18 words
A method as in claim 1 wherein the hash coding step (a) includes performing a CRC polynomial division.
Claim 9
Dependent Claim
31 words
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.
Claim 10
Dependent Claim
25 words
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.
Claim 11
Dependent Claim
30 words
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.
Claim 12
Dependent Claim
30 words
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.
Claim 13
Dependent Claim
40 words
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.
Claim 14
Dependent Claim
37 words
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.
Claim 15
Dependent Claim
28 words
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.
Claim 16
Dependent Claim
55 words
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.
Claim 17
Dependent Claim
81 words
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.
Claim 18
Dependent Claim
81 words
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.
Claim 19
Dependent Claim
19 words
An arrangement as in claim 16 wherein the hash coding block includes a feedback register and a gate array.
Claim 20
Dependent Claim
32 words
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.
Claim 21
Dependent Claim
31 words
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.
Claim 22
Dependent Claim
18 words
An arrangement as in claim 16 wherein the search table includes means for storing a binary search tree.
Claim 23
Dependent Claim
36 words
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.
Claim 24
Dependent Claim
25 words
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.
Claim 25
Dependent Claim
47 words
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.
Claim 26
Dependent Claim
60 words
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.
Claim 27
Dependent Claim
60 words
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.
Claim 28
Dependent Claim
28 words
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.
Claim 29
Dependent Claim
127 words
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).
Claim 30
Dependent Claim
127 words
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).
Claim 31
Dependent Claim
26 words
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.
Claim 32
Dependent Claim
121 words
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.
Claim 33
Dependent Claim
121 words
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.
Claim 34
Dependent Claim
33 words
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.
Claim 35
Dependent Claim
23 words
A method as in claim 28 further including routing the cell based on information derived from the record obtained from the second table.
References Cited (Backward Citations)
GB2217488A
Cited
US5481687A
Cited
US5440552A
Cited
US5708659A
Cited
US5467349A
Cited
US5455825A
Cited
US5555256A
Cited
US5418786A
Cited
US5414701A
Cited
US5530806A
Cited
GB2301913A
Cited
GB2302913A
Cited
WO1997013377A2
Cited
US5889949A
Cited
EP0847217A1
Cited
US5852607A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-07 | 2003-09-06 | 2004-03-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-07 | 2007-09-06 | 2008-03-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-07 | 2011-09-06 | 2012-03-07 | $7700.00 | Window Closed / Lapsed |