Apparatus and method for processing alternately configured longest prefix match tables

Patent metadata

Field	Value
Publication number	US-9729447-B2
Application number	US-201615140424-A
Country	US
Kind code	B2
Filing date	Apr 27, 2016
Priority date	Mar 12, 2013
Publication date	Aug 8, 2017
Grant date	Aug 8, 2017

Abstract

A network switch includes a memory configurable to store alternate table representations of an individual trie in a hierarchy of tries. A prefix table processor accesses in parallel, using an input network address, the alternate table representations of the individual trie and searches for a longest prefix match in each alternate table representation to obtain local prefix matches. The longest prefix match from the local prefix matches is selected. The longest prefix match has an associated next hop index base address and offset value. A next hop index processor accesses a next hop index table in the memory utilizing the next hop index base address and offset value to obtain a next hop table pointer. A next hop processor accesses a next hop table in the memory using the next hop table pointer to obtain a destination network address.

First claim

The invention claimed is:

1. A network switch, comprising:
a memory configurable to store alternate table representations of an individual trie in a hierarchy of tries, wherein the alternate table representations include a sparse mode representation that identifies selected trie nodes, a bit map mode representation with a bit map that identifies selected trie nodes, and a leaf-push representation that identifies selected trie nodes at the bottom of a trie;
a hardware prefix table processor to
access in parallel, using an input network address, the alternate table representations of the individual trie and search for a longest prefix match in each alternate table representation to obtain local prefix matches, and
select the longest prefix match from the local prefix matches, wherein the longest prefix match has an associated next hop index base address and offset value.

2. The network switch of claim 1 further comprising a next hop index processor to access a next hop index table in the memory utilizing the next hop index base address and offset value to obtain a next hop table pointer.

3. The network switch of claim 2 wherein the next hop index processor processes a block of next hop table entries to facilitate equal-cost multi-path routing.

4. The network switch of claim 3 wherein the block specifies up to 1024 paths.

5. The network switch of claim 2 further comprising a next hop processor to access a next hop table in the memory using the next hop table pointer to obtain a destination network address.

6. The network switch of claim 1 wherein the sparse mode representation includes a branch identification and a stride value.

7. The network switch of claim 1 wherein the bit map mode representation includes a branch identification and a stride value.

8. The network switch of claim 1 wherein the leaf-push representation includes a branch identification and a stride value.

9. The network switch of claim 1 wherein the prefix table processor is a hardware resource with a deterministic look-up latency.

10. The network switch of claim 1 wherein the alternate table representations include tables with different packet types in the same table.

11. The network switch of claim 10 wherein the different packet types include IPV4 packets and IPV6 packets.

12. The network switch of claim 1 wherein the prefix table processor identifies a longest prefix match for a remote host and an exact match for a directly attached host.

13. The network switch of claim 12 wherein the prefix table processor identifies the longest prefix match for the remote host and the exact match for the directly attached host in the same table.

Assignees

• Xpliant Inc
• Cavium Inc

Inventors

• Wang Weihuang
• Balan Mohan
• Siva Nimalan
• Shah Zubin

Classifications

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/748 Primary

  using longest matching prefix · CPC title

• H04L45/741

  Routing in networks with a plurality of addressing schemes, e.g. with both IPv4 and IPv6 · CPC title

• H04L45/54

  Organization of routing tables · CPC title