Fast multilevel hierarchical routing table lookup using content addressable memory
First Claim
1. A memory for use in a switch in a communications network for implementing a multilevel hierarchical routing table comprising:
- an input for receiving a destination address of a call or packet,an output for outputting an output port entry indicating a particular output port of said switch for said call or packet,a plurality of content addressable memories, each content addressable memory associated with one level of said multilevel hierarchical routing table and comprising;
a mask circuit for producing a masked destination address by masking out portions of said destination address of said call or packet received at said input which do not correspond to said one level of said routing table, anda memory array for storing routing table entries comprising destination addresses and corresponding output port entries for said one level of said multiple hierarchical routing table and for outputting, when each non-masked portion of said masked destination address matches corresponding portions of a destination address of a routing table entry stored in said memory array, an output port entry contained in the matched routing table entry, anda prioritizer for prioritizing said content addressable memories by selecting, for output from said output, the output port entry outputted from the content addressable memory associated with the lowest level in said hierarchy, in which a match occurred.
10 Assignments
0 Petitions
Accused Products
Abstract
A switch memory 100 for implementing a multilevel hierarchical routing table in a switch is disclosed. The switch memory 100 includes a plurality of mask circuits 120, 121 and 122, which each correspond to one level of the multilevel hierarchy. Each mask circuit 120, 121 and 122 receives a destination address of an incoming call or packet and masks out portions of the received destination address which do not correspond to the level of the hierarchy with which the mask circuit 120, 121 or 122 is associated. A memory array 130, 131 or 132 corresponding to each mask circuit 120, 121 or 122, is provided which is capable of storing a table of entries including an output port entry and a corresponding destination address of one level of the multilevel hierarchy of destination addresses. Additionally, each memory array 130, 131 or 132 is capable of comparing, in parallel, non-masked portions of the masked destination address outputted from the corresponding mask circuit 120, 121 or 122 with corresponding portions of each destination address of each table entry stored therein. Finally, the switch memory 100 includes a prioritizer 150 for enabling the output of an output port entry of a matched table entry from the memory array 130, 131 or 132, storing destination addresses of the lowest level in the hierarchy, in which a match occurred.
198 Citations
13 Claims
-
1. A memory for use in a switch in a communications network for implementing a multilevel hierarchical routing table comprising:
-
an input for receiving a destination address of a call or packet, an output for outputting an output port entry indicating a particular output port of said switch for said call or packet, a plurality of content addressable memories, each content addressable memory associated with one level of said multilevel hierarchical routing table and comprising; a mask circuit for producing a masked destination address by masking out portions of said destination address of said call or packet received at said input which do not correspond to said one level of said routing table, and a memory array for storing routing table entries comprising destination addresses and corresponding output port entries for said one level of said multiple hierarchical routing table and for outputting, when each non-masked portion of said masked destination address matches corresponding portions of a destination address of a routing table entry stored in said memory array, an output port entry contained in the matched routing table entry, and a prioritizer for prioritizing said content addressable memories by selecting, for output from said output, the output port entry outputted from the content addressable memory associated with the lowest level in said hierarchy, in which a match occurred. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A method for routing a call or packet received in a switch in a communications network comprising the steps of:
-
in each of a plurality of mask circuits, each of said plurality of mask circuits corresponding to one level of a multilevel hierarchical routing table, masking out portions of a destination address of said call or packet, which portions depend on said one level of the hierarchy to which a mask circuit corresponds, from each of a plurality of memory arrays, with each memory array being associated with one of said mask circuits and storing routing table entries of said corresponding one level in the hierarchy comprising destination addresses and corresponding output port entries, outputting an output port entry of a routing table entry which comprises a destination address having portions which match each corresponding non-masked portion of the masked destination address, and routing said call or packet onto an output port indicated by an output port entry outputted from the memory array, corresponding to the lowest level in the hierarchy, of said memory arrays which output output port entries. - View Dependent Claims (7, 8, 9)
-
-
10. A memory for use in a central office switch for implementing a multilevel hierarchical routing table comprising a plurality of content addressable memory means, each associated with one level of said multilevel hierarchical routing table and each comprising
mask circuit means for masking out portions of a destination address of a call or packet which do not correspond to said one level of said routing table, and memory array means for storing routing table entries comprising destination addresses and corresponding output port entries for said one level of said routing table and for comparing non-masked portions of the masked destination address to corresponding portions of each destination address of each routing table entry stored therein.
Specification