Method for increasing Layer-3 longest prefix match scale

Patent metadata

Field	Value
Publication number	US-9825857-B2
Application number	US-201414449007-A
Country	US
Kind code	B2
Filing date	Jul 31, 2014
Priority date	Nov 5, 2013
Publication date	Nov 21, 2017
Grant date	Nov 21, 2017

Abstract

Various embodiments are disclosed for increasing Layer-3 LPM (longest prefix match) routing database in a network platform. In some embodiments, chipsets in fabric modules (FMs) can be partitioned into multiple banks. Network traffic can be directed towards a corresponding bank in the FMs by using a LPM table on a line card (LC). Entries in the LPM table on the LC can be programmed either statically or dynamically based upon LPM routes that are dynamically learned.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
partitioning each of two or more fabric modules (FMs) into two or more banks, wherein the partitioning comprises associating at least two chipsets for each of the two or more FMs into different banks selected from among the two or more banks;
dynamically assigning two or more entries in a LPM table of a line card (LC) at least based upon routes that are dynamically learned at the LC;
programming the two or more banks in each of the two or more FMs based upon the dynamically assigned two or more entries in the LPM table;
in response to receiving a Layer-3 packet, looking up the Layer-3 packet in the LPM table of the LC to determine a particular bank in one of the two or more FMs for routing the Layer-3 packet; and
routing the Layer-3 packet to the particular bank.

2. The computer-implemented method of claim 1 , further comprising:
assigning a virtual module (VM) identifier to each of the two or more banks in one of the two or more FMs.

3. The computer-implemented method of claim 2 , wherein forwarding the Layer-3 packet among the two or more banks of the two or more FMs is based at least upon assigned VM identifiers of the two or more banks in the two or more FMS.

4. The computer-implemented method of claim 1 , further comprising:
increasing, based upon participation of the LC in virtual routing and forwarding (VRF) or virtual design and construction (VDC), a number of the routes using a selective download.

5. The computer-implemented method of claim 1 , further comprising:
adding an additional entry to the LPM table of the LC based upon the routes that are dynamically learned; and
hashing the additional entry to one of the two or more banks in one of the two or more FMs.

6. The computer-implemented method of claim 1 , further comprising:
in response to the routes at the LC becoming too granular to fit in the LPM table, aggregating the routes up by 1 bit-level.

7. The computer-implemented method of claim 1 , further comprising:
measuring traffic flows on each of the two or more banks in the two or more FMs;
based upon measured traffic flows on the two or more banks in the two or more FMs, determining a new bank in the two or more FMs for at least one route to the LC, the new bank being different from an existing bank for the at least one route to the LC; and
switching the at least one route from the existing bank in the two or more FMs to the new bank in the two or more FMs.

8. The computer-implemented method of claim 7 , further comprising:
adding a pre-determined delay to a determination of whether to switch the route from the existing bank in the two or more FMs to the new bank in the two or more FMs.

9. The computer-implemented method of claim 7 , further comprising:
in response to a determination to switch the route from the existing bank in the two or more FMs to the new bank in the two or more FMs, making both the existing bank and the new bank available before the route is switched from the existing bank to the new bank.

10. A system, comprising:
at least one processor; and
memory including instructions that, when executed by the at least one processor, cause the system to:
partition each of two or more fabric modules (FMs) into two or more banks, wherein the partitioning comprises associating at least two chipsets for each of the two or more FMs into different banks selected from among the two or more banks;
dynamically assign two or more entries in a LPM table of a line card (LC) at least based upon routes that are dynamically learned at the LC;
program the two or more banks in each of the two or more FMs based upon the dynamically assigned two or more entries in the LPM table;
in response to receiving a Layer-3 packet, look up the Layer-3 packet in the LPM table of the LC to determine a particular bank in one of the two or more FMs for routing the Layer-3 packet; and
route the Layer-3 packet to the particular bank.

11. The system of claim 10 , wherein the instructions when executed further cause the system to:
assign a virtual module (VM) identifier to each of the two or more banks in one of the two or more FMs.

12. The system of claim 11 , wherein forwarding of the Layer-3 packet among the two or more banks of the two or more FMs is based at least upon assigned VM identifiers of the two or more banks in the two or more FMs.

13. The system of claim 10 , wherein the instructions when executed further cause the system to:
add an additional entry to the LPM table of the LC based upon the routes that are dynamically learned; and
hash the additional entry to one of the two or more banks in one of the two or more FMs.

14. The system of claim 10 , wherein the instructions when executed further cause the system to:
in response to the routes at the LC becoming too granular to fit in the LPM table, aggregate the routes up by 1 bit-level.

15. The system of claim 10 , wherein the instructions when executed further cause the system to:
measure traffic flows on each of the two or more banks in the two or more FMs;
based upon measured traffic flows on the two or more banks in the two or more FMs, determine a new bank in the two or more FMs for at least one route to the LC, the new bank being different from an existing bank for the at least one route to the LC; and
switch the at least one route from the existing bank in the two or more FMs to the new bank in the two or more FMs.

16. The system of claim 15 , wherein the instructions when executed further cause the system to:
add a pre-determined delay to a determination whether to switch the route from the existing bank in the two or more FMs to the new bank in the two or more FMs.

Assignees

• Cisco Tech Inc

Inventors

• Banerjee Ayan
• Merchant Sameer
• Mellacheruvu Ramana
• Ponnapalli Ramesh V N
• Ramabadran Srinivasan

Classifications

• H04W72/30

  Resource management for broadcast services · CPC title

• H04L45/748

  using longest matching prefix · CPC title

• H04L45/72

  Routing based on the source address · CPC title

• H04L51/10

  Multimedia information · CPC title

• H04W28/12

  using signalling between network elements · CPC title