Prefix matching structure and method for fast packet switching
View Patent ↗A prefix matching apparatus for directing information to a destination port includes a memory configured to store a piece of data including an address and a plurality of levels each including a plurality of memory locations, the levels each representing a unique address space. A controller is coupled to the memory and to the plurality of levels, and is configured to read the data address and to direct the data to the next level associated with a unique address space associated with the data address. In one embodiment, the controller is configured to match the data address prefix to a plurality of addresses associated with the unique address spaces. Advantages of the invention include fast switch decisions and low switch latency.
1. A method of directing information to a destination level based at least in part on a memory storing address ranges, comprising:
using a network routing or switching device that comprises the memory and a controller and is configured for performing a process comprising:
storing a piece of data including a data address;
reading the data address and comparing the data address to the address ranges; and
directing the piece of data to a next level associated with a unique address space associated with the data address, wherein
the act of directing the piece of data to the next level comprises storing address spaces in a plurality of active slices that include predetermined address spaces representing address relationships of an index,
the index allows inferring the next level from a current level without requiring to store the index in a volatile memory,
the process infers the next level by using a map or an equation rather than using the index, and
a shadow slice is utilized by exchanging the shadow slice with one of the plurality of active slices, whereupon the one of the plurality of active slices becomes the shadow slice upon exchange, in which the shadow slice is characterized by being programmed to comprise a recalculated database to capture an insertion or deletion operation on an original database residing in the one or more active slices.
2. The method of claim 1 , further comprising matching a prefix of the data address to a plurality of addresses associated with the unique address spaces.
3. The method of claim 1 , further comprising identifying a map that represents the index.
4. The method of claim 1 , further comprising identifying an equation that represents the index.
5. The method of claim 1 , wherein the utilizing includes reprogramming the shadow slice.
6. The method of claim 5 , wherein the utilizing includes exchanging the shadow slice in response to a fault with an active slice.
7. A prefix matching apparatus for directing information to a destination, comprising:
a memory configured to store a piece of data including a data address;
a plurality of levels, at least one of which includes a plurality of memory locations and represents a unique address space;
a controller coupled to the memory and to the plurality of levels, and configured to read the data address and to direct the data to a next level associated with a unique address space associated with the data address;
a plurality of slices which comprise a plurality of active slices, each of which includes predetermined address spaces representing address relationships of an index, and a shadow slice, wherein
the index allows the prefix matching apparatus to infer the next level from a current level without requiring to store the index in a volatile memory, and
the controller is configured to infer the next level from the current level by using a map or an equation rather than using the index; and
the shadow slice that is characterized by being capable of being utilized by the controller,
wherein
the shadow slice is characterized by being capable of being exchanged with one of the plurality of active slices and further by being programmed to comprise a recalculated database to capture an insertion or deletion operation on an original database residing in the one or more active slices, whereupon the one of the plurality of active slices becomes the shadow slice upon exchange.
8. The prefix matching apparatus of claim 7 , wherein
the controller is configured to match a prefix of the data address to a plurality of addresses associated with the unique address space.
9. The prefix matching apparatus of claim 7 , wherein the controller comprises a map that represents the index.
10. The prefix matching apparatus of claim 7 , wherein the controller comprises an equation that represents the index.
11. The prefix matching apparatus of claim 7 , wherein the shadow slice can be reprogrammed.
12. The prefix matching apparatus of claim 11 , wherein the shadow slice is reprogrammed simultaneously with operation of the active slices.
13. The prefix matching apparatus of claim 7 , wherein the shadow slice is exchanged in response to a fault with an active slice.
14. The prefix matching apparatus of claim 7 , wherein the plurality of levels support simultaneous lookup of multiple addresses.
15. The prefix matching apparatus of claim 7 , further comprising:
an external memory.
16. The prefix matching apparatus of claim 7 , wherein the controller directs the data based at least in part on the index.
17. The prefix matching apparatus of claim 7 , wherein the memory includes internal memory.
18. The prefix matching apparatus of claim 17 , wherein the controller is further coupled to external memory separate from the internal memory.