Hierarchical routing with table management across hardware modules

Patent metadata

Field	Value
Publication number	US-10904146-B2
Application number	US-201816133370-A
Country	US
Kind code	B2
Filing date	Sep 17, 2018
Priority date	Nov 5, 2013
Publication date	Jan 26, 2021
Grant date	Jan 26, 2021

Abstract

Systems, methods, and non-transitory computer-readable storage media for performing hierarchical routing are disclosed. The method includes identifying routes in a computer network and arranging those routes in two separate routing tables. The first routing table is stored on a first module and the second routing table is stored on a second module.

First claim

What is claimed is:

1. A system for routing data in a computer network, the system comprising:
a line card having a first processor configured to:
receive a data packet having a destination address;
determine, based on the destination address, whether an appropriate route for the data packet is available in a first routing table stored on the line card, the first routing table storing a first plurality of network route entries; and
in response to determining that the appropriate route is not available in the first routing table, forward the data packet to a fabric module;

the fabric module having a second processor configured to:
receive the data packet from the line card;
determine, based on the destination address, that the appropriate route for the data packet is available in a second routing table stored on the fabric module, the second routing table storing a portion of the first plurality of network route entries and a second plurality of network route entries, the second routing table containing coarser routes relative to the first routing table, the first routing table and the second routing table including a safety overlap to ensure redundancy, the safety overlap defining a desired number of duplicate routes as a multiple greater than a number of outstanding routes; and
forward the data packet to the destination address according to the appropriate route.

2. The system of claim 1 , wherein if the line card determines that the appropriate route is available in the first routing table, the line card is further configured to:
modify the data packet to include a proper egress port and yield a modified data packet; and
forward the modified data packet to the fabric module for switching to the proper egress port.

3. The system of claim 1 , wherein the line card is further configured to balance network traffic.

4. The system of claim 1 , wherein the first plurality of network route entries and the second plurality of network route entries are organized according to a network mask.

5. The system of claim 4 , wherein a portion of the first plurality of network route entries stored at an end of the first routing table is duplicated at a start of the second routing table.

6. The system of claim 4 , wherein the second routing table is a complimentary routing table.

7. The system of claim 1 , wherein the fabric module is further configured to:
determine, based on the destination address, that the appropriate route for the data packet is not available in the second routing table; and
forward the data packet to a default route to avoid dropping the data packet.

8. A computer-implemented method for configuring a computer network, the method comprising:
identifying, via a processor, a plurality of routes in the computer network;
arranging a first portion of the plurality of routes in a first routing table and a second portion of the plurality of routes in a second routing table so that the second routing table contains coarser routes relative to the first routing table;
storing the first routing table on a first module configured to look up routes for incoming data packets; and
storing the second routing table on a second module configured to receive and route each of the incoming data packets that could not be routed by the first module, the first routing table and the second routing table including a safety overlap to ensure redundancy, the safety overlap defining a desired number of duplicate routes as a multiple greater than a number of outstanding routes.

9. The computer-implemented method of claim 8 , wherein a first route in the first routing table corresponds to a host route and a last route in the second routing table corresponds to a default route.

10. The computer-implemented method of claim 8 , wherein the first portion of the plurality of routes have a network mask that is more specific than a cut-off mask.

11. The computer-implemented method of claim 8 , wherein each of the plurality of routes comprises a network mask and an address prefix, and wherein the arranging orders the plurality of routes from specific routes to coarse routes according first to the network mask and second to the address prefix.

12. The computer-implemented method of claim 11 , wherein the first routing table and the second routing table have a number of shared routes corresponding to routes located at an end of the first routing table that are replicated at a start of the second routing table.

13. The computer-implemented method of claim 12 , further comprising:
inserting a plurality of new routes in the first routing table, wherein the plurality of new routes is less than or equal to the number of shared routes.

14. The computer-implemented method of claim 8 , wherein each of the plurality of routes are stored based on route type.

15. A non-transitory computer-readable storage medium having stored therein instructions which, when executed by a processor, cause the processor to perform operations comprising:
identify a new route having a network mask and an address prefix;
determine, according to the network mask and the address prefix, that the new route should be stored on a first routing table, the first routing table having a first portion of a plurality of routes and a second routing table having a second portion of the plurality of routes;
store the new route in the first routing table; and
update the second routing table to maintain a desired number of duplicate routes on the first routing table and the second routing table, the second routing table updated to contain coarser routes relative to the first routing table, the first routing table and the second routing table including a safety overlap to ensure redundancy, the safety overlap defining the desired number of duplicate routes as a multiple greater than a number of outstanding routes.

16. The non-transitory computer-readable storage medium of claim 15 , wherein the first routing table is stored on a line card and the second routing table is stored on a fabric module.

17. The non-transitory computer-readable storage medium of claim 16 , wherein the first routing table includes a last default entry that forwards data packets to the fabric module for routing.

18. The non-transitory computer-readable storage medium of claim 15 , wherein the desired number of duplicate routes are stored at an end of the first routing table and at a beginning of the second routing table.

19. The non-transitory computer-readable storage medium of claim 18 , wherein a first route in the first routing table corresponds to a host route and a last route in the second routing table corresponds to a default route.

20. The non-transitory computer-readable storage medium of claim 15 , wherein the multiple is four times the number of outstanding routes.

Assignees

• Cisco Tech Inc

Inventors

• Banerjee Ayan
• Mellacheruvu Ramana
• Saxena Abhishek
• Jain Vishal
• Cafiero Luca

Classifications

• H04W72/30

  Resource management for broadcast services · CPC title

• H04L45/745 Primary

  Address table lookup; Address filtering · CPC title

• H04L45/16 Primary

  Multipoint routing · CPC title

• H04L47/33

  using forward notification · CPC title

• H04L45/748

  using longest matching prefix · CPC title