Hierarchical routing with table management across hardware modules

Patent metadata

Field	Value
Publication number	US-10079761-B2
Application number	US-201414477753-A
Country	US
Kind code	B2
Filing date	Sep 4, 2014
Priority date	Nov 5, 2013
Publication date	Sep 18, 2018
Grant date	Sep 18, 2018

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; 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, and wherein the line card is further configured to balance network traffic by selectively forwarding one or more data packets to the fabric module or to a second 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, wherein the second routing table only comprises a remaining balance of network routes that are not available on the first routing table; 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
forward the modified data packet to the fabric module for switching to the proper egress port.

3. The system of claim 1 , wherein a first plurality of network route entries are stored on the first routing table and a second plurality of network route entries are stored on the second routing table.

4. The system of claim 3 , 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 4 , wherein each of the plurality of routes are stored in only one of the first routing table or the second routing table based on route type.

8. The system of claim 7 , wherein the route type is designated via a mask.

9. 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.

10. 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 each of the plurality of routes are stored in only one of the first routing table or the second routing table, wherein the combined total of the first portion of the plurality of routes and the second portion of the plurality of routes comprises all network routes available in the computer network;
storing the first routing table on a first module configured to look up routes for incoming data packets, and wherein the first module is further configured to balance network traffic by selectively forwarding one or more data packets to a second module selected from among two or more other modules, wherein the first module is a network line card and the two or more other modules are network fabric modules in a system; and
storing the second routing table on the second module configured to receive and route each of the data packets that could not be routed by the first module.

11. The computer-implemented method of claim 10 , 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.

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

13. The computer-implemented method of claim 10 , 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.

14. The computer-implemented method of claim 13 , 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.

15. The computer-implemented method of claim 14 , 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.

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

17. The computer-implemented method of claim 16 , wherein the route type is designated via a mask.

18. The computer-implemented method of claim 10 , wherein the second routing table is a complimentary routing table.

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

• H04L47/33

  using forward notification · CPC title

• H04W28/12

  using signalling between network elements · CPC title

• H04L45/748

  using longest matching prefix · CPC title

• H04L51/10

  Multimedia information · CPC title