Semi-centralized multiple path routing

• US 8,755,389 B1
• Filed: 04/04/2012
• Issued: 06/17/2014
• Est. Priority Date: 04/04/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Poutievski, Leon, Mandal, Subhasree, Venkata, Subbaiah, Gupta, Amit, Ong, Joon
• Primary Examiner(s): Zhou, Yong
• Application Number:
  US13/439,748
• Time in Patent Office: 804 Days
• Field of Search: None
• US Class Current: 370/395.31
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for semi-centralized routing. One of the methods includes receiving one or more routes and determining that a received route identifies a new set of paths different from each routing path group in a maintained set of routing path groups. A new routing path group is created that corresponds to the new set of paths. The new routing path group is assigned an identifier of the routing path group. The new routing path group is converted to a corresponding new flow path group. A flow path group that was converted from the routing path group is replaced on a network device with the converted new flow path group.

Claims

1. A computer-implemented method comprising:

maintaining a set of routing path groups, wherein each routing path group is a distinct set of paths, wherein a path identifies a network address and a device interface identifier, and wherein each routing path group has an associated identifier;

maintaining a set of routes of a routing protocol, wherein each route is identified by a destination network address prefix, wherein each route identifies a set of paths, and wherein each route is associated with a routing path group identifier of a routing path group that corresponds to the identified set of paths;

receiving one or more updated routes;

determining that a received updated route identifies a new set of paths different from each routing path group in the maintained set of routing path groups;

creating a new routing path group corresponding to the new set of paths;

determining that each received updated route that identifies the new set of paths corresponds to a maintained route that is associated with a particular routing path group identifier;

assigning to the new routing path group an identifier of the particular routing path group;

converting the new routing path group to a corresponding new flow path group; and

replacing on a network device a particular flow path group that was converted from the particular routing path group with the converted new flow path group.

2. The method of claim 1, wherein determining that each received updated route that identifies the new set of paths corresponds to a maintained route comprises:

maintaining a reference count for each routing path group of routes that use the routing path group;

decrementing the reference count for the particular routing path group when an updated route changes from the particular routing path group to the new routing path group; and

determining that the reference count for the particular routing path group is zero.

3. The method of claim 1, further comprising:

converting each received route to a flow; and

writing each converted flow to a network device.

4. The method of claim 3, further comprising:

maintaining a flow table of converted flows, wherein a key to the flow table is a set of match rules.

5. The method of claim 1, wherein each flow is an OpenFlow protocol flow.

6. The method of claim 5, further comprising:

maintaining a flow path group table of flow path groups converted from routing path groups, wherein a key to the flow path group table is a flow path group identifier, and wherein a value of the flow path group table is a set of actions.

7. The method of claim 1, wherein maintaining a set of routing path groups comprises maintaining a routing path group table, wherein a key to the routing path group table is a routing path group identifier and a value of the routing path group table is a distinct set of paths.

8. The method of claim 1, wherein maintaining a set of routes of a routing protocol comprises maintaining a routing table, wherein a key to the routing table is a destination network address prefix.

9. A computer-implemented method comprising:

maintaining a set of routing path groups, wherein each routing path group is a distinct set of paths, wherein a path identifies a network address and a device interface identifier, and wherein each routing path group has an associated identifier;

maintaining a set of routes of a routing protocol, wherein each route is identified by a destination address prefix, wherein each route identifies a set of paths, and wherein each route is associated with a routing path group identifier of a routing path group that corresponds to the set of paths;

providing flows to a network device that processes network traffic, each flow having been converted from a respective received route, each flow identifying a respective flow path group derived from a corresponding routing path group from the set of maintained routing path groups;

determining that communication with the network device has been interrupted;

after resuming connection with the network device, receiving from the network device, one or more flow path groups;

converting each maintained routing path group to a corresponding converted flow path group;

determining that one or more particular flow path groups received from the network device each match a respective converted flow path group; and

assigning to each maintained routing path group that matches a respective flow path group received from the network device an identifier of the matching flow path group.

10. The method of claim 9, further comprising:

after resuming connection with the network device, designating each maintained routing path group as potentially changed;

removing the designation for each matching routing path group;

determining that a flow path group did not match a converted flow path group using remaining designations after checking each routing path group in the set of routing path groups against the flow path groups received from the network device; and

erasing on the network device each flow path group that did not match a converted flow path group.

11. The method of claim 9, further comprising:

after resuming connection with the network device, designating each maintained routing path group as potentially changed including clearing routing path group identifiers of maintained routing path groups;

converting only routing path groups with unassigned identifiers to flow path groups; and

writing the converted flow path groups to the network device.

12. The method of claim 11, wherein designating each maintained routing path group as potentially changed includes erasing each routing path group identifier.

13. The method of claim 11, further comprising:

converting routing path groups that are designated as potentially changed to corresponding flow path groups; and

writing the corresponding flow path groups to the network device.

14. The method of claim 13, further comprising:

maintaining a flow path group table of flow path groups converted from routing path groups, wherein a key to the flow path group table is a flow path group identifier, and wherein a value of the flow path group table is a set of actions.

15. The method of claim 11, further comprising:

maintaining a flow table of converted flows, wherein a key to the flow table is a set of match rules.

16. The method of claim 9, further comprising:

after resuming connection with the network device, receiving from the network device a set of flows, each flow identifying a destination and having an identifier of a flow path group;

for a particular flow of the received set of flows;

determining that a destination network address of the particular flow matches a destination network address of a particular route in the set of maintained routes, and

determining that the flow path group identifier of the particular flow corresponds to a routing path group identifier of the particular route; and

designating the particular route as unchanged.

17. The method of claim 16, further comprising:

bypassing a flow update process for the flows that correspond to routes designated as unchanged.

18. The method of claim 16, further comprising:

converting only routes not designated as unchanged to corresponding flows; and

writing flows to the network device.

19. The method of claim 9, further comprising:

converting each received route to a flow; and

writing each converted flow to a network device.

20. The method of claim 9, wherein each flow is an OpenFlow protocol flow.

21. The method of claim 9, wherein maintaining a set of routing path groups comprises maintaining a routing path group table, wherein a key to the routing path group table is a routing path group identifier and a value of the routing path group table is a distinct set of paths.

22. The method of claim 9, wherein maintaining a set of routes of a routing protocol comprises maintaining a routing table, wherein a key to the routing table is a destination network address prefix.