Framework for universally specified affinity topologies with partial path invalidation and generalized network flows

Patent metadata

Field	Value
Publication number	US-11070459-B2
Application number	US-201916456681-A
Country	US
Kind code	B2
Filing date	Jun 28, 2019
Priority date	Dec 8, 2016
Publication date	Jul 20, 2021
Grant date	Jul 20, 2021

Abstract

A method for setting up forwarding tables is described. A USAT part for a node is received. The USAT part includes glow definitions and a FGPL. Each glow describes network traffic flows and role instructions for the flows. Each FGP describes a role for the switching node; a validity rule; and relevant network topology. The method also includes determining a selected active FGP in the FGPL using the validity rule for the FGP, a network state and the ordering of the FGPs; initializing the glows, requesting a role identification to perform based on the selected FGP, determining the role instructions and instructing the TMS to update tables accordingly; and storing entries in software tables based on glows and the role instructions for the identified role, dynamically resolving conflicts among entries, and granting table updates to hardware tables. The tables include a software table for each hardware memory for forwarding packets.

First claim

What is claimed is:

1. A method comprising:
generating a set of candidate fabric graphs, the candidate fabric graphs having a same root node, and each candidate fabric graph including:
a directed tree graph having vertices representing network switches and arcs representing simplex communication links in a network,
a set of partial path validation rules, where each partial path validation rule of the set is a Boolean formula based on at least one network state variable and evaluates to TRUE if a unique path from a vertex associated with the each partial path validation rule to the root node is currently operational, and
node roles defining roles that network switches in the each candidate fabric graph may serve;

establishing relative preferences for the candidate fabric graphs in the set of candidate fabric graphs; and
ordering the candidate fabric graphs in the set of candidate fabric graphs based on the relative preferences;
providing at least a portion of the set of candidate fabric graphs to each of the network switches represented by the vertices, wherein the portion of the set of candidate fabric graphs provided to a network switch are relevant to the network switch; and
at each of the network switches, evaluating in preference order the set of candidate fabric graphs provided to the network switch based on the partial path validation rules of the set of candidate fabric graphs and the node role of the network switch.

2. The method of claim 1 , further comprising implementing, by the network switch, a first candidate fabric graph of the set of candidate fabric graphs that evaluates to TRUE during the evaluating in preference order.

3. The method of claim 1 , wherein the evaluating in preference order is further based on network state variables held by the network switch that indicate operational status of network switches and links associated with evaluation of the partial path validation rules included in the set of candidate fabric graphs provided to the network switch.

4. The method of claim 1 , wherein the generating the set of candidate fabric graphs includes one of pre-computing the set of candidate fabric graphs, centrally computing the set of candidate fabric graphs, or distributively computing the set of candidate fabric graphs.

5. The method of claim 1 , wherein each vertex of the vertices except the root node is associated with at least one partial path validation rule in the set of partial path validation rules.

6. The method of claim 1 , wherein the unique path being currently operational includes the root node being currently operational.

7. The method of claim 1 , wherein node roles include a source role, a destination role, a transit role, an add/drop role, a gateway role, a translator role, a blocker role, or a rate limiter role.

8. A non-transitory computer-readable medium storing instructions executable by a processing resource, the non-transitory computer-readable medium comprising:
instructions to generate a set of candidate fabric graphs, the candidate fabric graphs having a same root node, and each candidate fabric graph including:
a directed tree graph having vertices representing network switches and arcs representing simplex communication links in a network,
a set of partial path validation rules, where each partial path validation rule of the set is a Boolean formula based on at least one network state variable and evaluates to TRUE if a unique path from a vertex associated with the each partial path validation rule to the root node is currently operational, and
node roles defining roles that network switches in the each candidate fabric graph may serve;

instructions to establish relative preferences for the candidate fabric graphs in the set of candidate fabric graphs;
instructions to order the candidate fabric graphs in the set of candidate fabric graphs based on the relative preferences;
instructions to provide at least a portion of the set of candidate fabric graphs to each of the network switches represented by the vertices, wherein the portion of the set of candidate fabric graphs provided to a network switch are relevant to the network switch; and
instructions to evaluate, at each of the network switches, the set of candidate fabric graphs provided to the network switch, in preference order, based on the partial path validation rules of the set of candidate fabric graphs and the node role of the network switch.

9. The non-transitory computer-readable medium of claim 8 , further comprising instructions to implement, at the network switch, a first candidate fabric graph of the set of candidate fabric graphs that evaluates to TRUE during the evaluating in preference order.

10. The non-transitory computer-readable medium of claim 8 , wherein the instructions to evaluate is further based on network state variables held by the network switch that indicate operational status of network switches and links associated with evaluation of the partial path validation rules included in the set of candidate fabric graphs provided to the network switch.

11. The non-transitory computer-readable medium of claim 8 , wherein the instructions to generate the set of candidate fabric graphs includes pre-computing the set of candidate fabric graphs, centrally computing the set of candidate fabric graphs, or distributively computing the set of candidate fabric graphs.

12. The non-transitory computer-readable medium of claim 8 , wherein each vertex of the vertices except the root node is associated with at least one partial path validation rule in the set of partial path validation rules.

13. The non-transitory computer-readable medium of claim 8 , wherein node roles include a source role, a destination role, a transit role, an add/drop role, a gateway role, a translator role, a blocker role, or a rate limiter role.

14. A system comprising:
a processing resource; and
a computer-readable medium storing instructions executable by the processing resource to:
generate a set of candidate fabric graphs, the candidate fabric graphs having a same root node, and each candidate fabric graph including:
a directed tree graph having vertices representing network switches and arcs representing simplex communication links in a network,
a set of partial path validation rules, where each partial path validation rule of the set is a Boolean formula based on at least one network state variable and evaluates to TRUE if a unique path from a vertex associated with the each partial path validation rule to the root node is currently operational, and
node roles defining roles that network switches in the each candidate fabric graph may serve;

establish relative preferences for the candidate fabric graphs in the set of candidate fabric graphs;
order the candidate fabric graphs in the set of candidate fabric graphs based on the relative preferences;
provide at least a portion of the set of candidate fabric graphs to each of the network switches represented by the vertices, wherein the portion of the set of candidate fabric graphs provided to a network switch are relevant to the network switch; and
evaluate, at each of the network switches, the set of candidate fabric graphs provided to the network switch, in preference order, based on the partial path validation rules of the set of candidate fabric graphs and the node role of the network switch.

15. The system of claim 14 , wherein the computer-readable medium stores instructions executable by the processing resource to implement, at the network switch, a first candidate fabric graph of the set of candidate fabric graphs that evaluates to TRUE during th

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Barry Richard A
• Zhang Lei

Classifications

• H04L12/4641 Primary

  Virtual LANs, VLANs, e.g. virtual private networks [VPN] (LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272) · CPC title

• H04L12/44

  Star or tree networks · CPC title

• H04L12/4633

  Interconnection of networks using encapsulation techniques, e.g. tunneling · CPC title

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/02 Primary

  Topology update or discovery · CPC title