Providing extended administrative groups in computer networks

• US 8,634,418 B2
• Filed: 07/01/2011
• Issued: 01/21/2014
• Est. Priority Date: 07/01/2011
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Kwong, Ambrose, Sheth, Nischal, Gredler, Hannes, Bahadur, Nitin, Sitaraman, Harish, Sachdev, Avneesh
• Primary Examiner(s): Wilson, Robert
• Assistant Examiner(s): Aung, Sai
• Application Number:
  US13/174,962
• Publication Number:
  US 20130003728A1
• Time in Patent Office: 935 Days
• Field of Search: 370252-256, 370230-238, 370/392, 370/389, 370/400, 370/401, 370/349, 370/338, 370397-399, 370/229
• US Class Current: 370/389
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

In general, techniques are described for providing extended administrative groups in networks. A network device comprising an interface and a control unit may implement the techniques. The interface receives a routing protocol message that advertises a link. This message includes a field for storing first data associated with the link in accordance with the routing protocol. The field is defined by the routing protocol as a field having a different function from an administrative group field defined by the same routing protocol. The control unit determines that this field has been repurposed to store second data, wherein this second data specifies an extended administrative group for the link different from those that may be specified by the administrative group field. The control unit then updates routing information to associate the advertised link with the extended administrative group and performs path selection to select paths based on the updated routing information.

Claims

1. A method comprising:

receiving, with a network device, a routing protocol message that advertises a link, wherein the routing protocol message includes a field for storing first data associated with the link in accordance with the routing protocol, and wherein the field is defined by the routing protocol as a type of field having a different function from an administrative group field as defined by the same routing protocol and comprises a shared risk link group (SRLG) type-length-value (TLV) field defined by the routing protocol to have a type portion, a length portion and a value portion, wherein the type portion of the SRLG TLV field identifies the second data stored by the value portion of the SRLG TLV field as associating the advertised link with a SRLG, and wherein the administrative group field comprises an administrative group TLV field defined by the routing protocol to have a type portion, a length portion and a value portion, wherein the type portion of the Administrative Group TLV field identifies the first data stored by the value portion of the Administrative Group TLV field as associating the advertised link with the one or more administrative groups in accordance with the routing protocol;

determining, with the network device, that the field of the received routing protocol message has been repurposed to store second data in addition to the first data, wherein the second data specifies one or more extended administrative groups for the link different from the one or more administrative groups that are to be specified by the administrative group field;

upon determining that the field has been repurposed, updating routing information to associate the advertised link with the one or more extended administrative groups specified by the second data; and

performing, with the network device, path selection to select one or more paths based on the updated routing information.

2. The method of claim 1, further comprising receiving configuration data from a user that specifies a range of values of the first data that are to be repurposed to specify the second data,

wherein determining whether the field of the received protocol message has been repurposed to specify second data comprises:

determining whether the field stores the first data identifying a value that is included within the range of values specified by the configuration data; and

determining that the field of the received routing protocol message has been repurposed to specify the second data associating the link with the one or more extended administrative groups based on the determination that the field stores the first data identifying a value that is included within the range of values specified by the configuration data.

3. The method of claim 1,

wherein the routing protocol comprises an Open Shortest Path First (OSPF) routing protocol,

wherein the routing protocol message comprises a link state advertisement (LSA), Administrative Group TLV, and

wherein the type portion of the SRLG TLV field stores a value of sixteen to indicate that the value portion of the SRLG TLV field associates the advertised link with the SRLG in accordance with the OSPF routing protocol.

4. The method of claim 1,

wherein the routing protocol comprises an Intermediate System to Intermediate System (IS-IS) routing protocol,

wherein the routing protocol message comprises a Link State Protocol Data Unit, Administrative Group TLV, and

wherein the type portion of the SRLG TLV field stores a value of 138 to indicate that the value portion of the SRLG TLV field associates the advertised link with the SRLG in accordance with the IS-IS routing protocol.

5. The method of claim 1, further comprising:

receiving configuration data from a user that specifies a range of values of the first data that are to be repurposed to specify the second data;

receiving link data from a user that associates at least one of the extended administrative groups with a link that is different from the link advertised by the received routing protocol message, wherein the advertised link comprises a first link and the link that is different from the advertised link comprises a second link;

generating a routing protocol message to advertise the second link, wherein the routing protocol message to advertise the second link comprises the repurposed SRLG field for storing a value within the range of values to associate the link with one of the extended administrative groups rather than one or more SRLGs, and wherein the SRLG field is different than the administrative group field defined by the routing protocol; and

transmitting the routing protocol message to advertise the second link to adjacent network devices.

6. The method of claim 1, wherein performing path selection comprises performing a Constrained Shortest Path First (CSPF) path selection algorithm to select the one or more paths based on the updated routing information.

7. The method of claim 6, further comprising receiving configuration data from a user that defines one or more constraints that constrains path selection as performed by the CSPF path selection algorithm,

wherein the one or more constraints comprise the one or more extended administrative groups,

wherein the updated routing information comprises a graph data structure having nodes that represent network devices and edges that represent links;

wherein performing the CSPF path selection algorithm includes;

pruning the graph data structure based on the constraints to generate a pruned graph data structure; and

selecting the one or more paths based on the pruned graph data structure.

8. The method of claim 1, wherein performing path selection comprises performing path selection with a multiprotocol label switching (MPLS) protocol module executing within the network device to resolve the routing information in order to generate at least one MPLS forwarding table, wherein the MPLS forwarding table includes entries that are each associated with a different label, wherein each of the entries defines an action that is to be taken with respect to an incoming MPLS packet having a label stack that includes the label associated with the corresponding entry, wherein the action includes one or more of pushing a different label onto the label stack, swapping the label of the label stack with a different label and popping the label from the label stack.

9. The method of claim 1, wherein the network device comprises one of a label switching router (LSR) or a label edge router (LER).

10. A network device comprising:

at least one interface that receives a routing protocol message that advertises a link, wherein the routing protocol message includes a field for storing first data associated with the link in accordance with the routing protocol, and wherein the field is defined by the routing protocol as a type of field having a different function from an administrative group field as defined by the same routing protocol;

a hardware control unit that receives configuration data from a user that specifies a range of values of the first data that are to be repurposed to specify second data, receives link data from a user that associates at least one of the extended administrative groups with a link that is different from the link advertised by the received routing protocol message, determines that the field of the received routing protocol message has been repurposed to store the second data in addition to the first data, wherein the second data specifies one or more extended administrative groups for the link different from the one or more administrative groups that are to be specified by the administrative group field, upon determining that the field has been repurposed, update routing information to associate the advertised link with the one or more extended administrative groups specified by the second data perform path selection to select one or more paths based on the updated routing information, and generates a routing protocol message to advertise the link that is different from the link advertised by the received routing protocol message, wherein the routing protocol message to advertise the second link comprises a repurposed shared risk link group (SRLG) field for storing a value within the range of values to associate the link with one of the extended administrative groups rather than one or more SRLGs, and wherein the SRLG field is different than the Administrative Group field defined by the routing protocol,

wherein the at least one interface transmits the routing protocol message to advertise the second link to adjacent network devices.

11. The network device of claim 10, wherein the control unit further receives configuration data from a user that specifies a range of values of the first data that are to be repurposed to specify the second data, determines whether the field stores the first data identifying a value that is included within the range of values specified by the configuration data and determines that the field of the received routing protocol message has been repurposed to specify the second data associating the link with the one or more extended administrative groups based on the determination that the field stores the first data identifying a value that is included within the range of values specified by the configuration data.

12. The network device of claim 10,

wherein the administrative group field comprises an administrative group type-length-value (TLV) field defined by the routing protocol to have a type portion, a length portion and a value portion, wherein the type portion of the Administrative Group TLV field identifies the first data stored by the value portion of the Administrative Group TLV field as associating the advertised link with the one or more administrative groups in accordance with the routing protocol, and

wherein the field of the received routing protocol message comprises another SRLG TLV field defined by the routing protocol to have a type portion, a length portion and a value portion, wherein the type portion of the SRLG TLV field identifies the second data stored by the value portion of the SRLG TLV field as associating the advertised link with a SRLG.

13. The network device of claim 12,

wherein the routing protocol comprises an Open Shortest Path First (OSPF) routing protocol,

wherein the routing protocol message comprises a link state advertisement (LSA), Administrative Group TLV, and

wherein the type portion of the SRLG TLV field stores a value of sixteen to indicate that the value portion of the SRLG TLV field associates the advertised link with the SRLG in accordance with the OSPF routing protocol.

14. The network device of claim 12,

wherein the routing protocol comprises an Intermediate System to Intermediate System (IS-IS) routing protocol,

wherein the routing protocol message comprises a Link State Protocol Data Unit, Administrative Group TLV, and

wherein the type portion of the SRLG TLV field stores a value of 138 to indicate that the value portion of the SRLG TLV field associates the advertised link with the SRLG in accordance with the IS-IS routing protocol.

15. The network device of claim 10, wherein the control unit further performs a Constrained Shortest Path First (CSPF) path selection algorithm to select the one or more paths based on the updated routing information.

16. The network device of claim 15, wherein the control unit receives configuration data from a user that defines one or more constraints that constrains path selection as performed by the CSPF path selection algorithm,

wherein the one or more constraints comprise the one or more extended administrative groups,

wherein the updated routing information comprises a graph data structure having nodes that represent network devices and edges that represent links, and

wherein the control unit further prunes the graph data structure based on the constraints to generate a pruned graph data structure and selects the one or more paths based on the pruned graph data structure.

17. The network device of claim 10, wherein the control unit further performs path selection with a multiprotocol label switching (MPLS) protocol module executing within the network device to resolve the routing information in order to generate at least one MPLS forwarding table, wherein the MPLS forwarding table includes entries that are each associated with a different label, wherein each of the entries defines an action that is to be taken with respect to an incoming MPLS packet having a label stack that includes the label associated with the corresponding entry, wherein the action includes one or more of pushing a different label onto the label stack, swapping the label of the label stack with a different label and popping the label from the label stack.

18. The network device of claim 10, wherein the network device comprises one of a label switching router (LSR) or a label edge router (LER).

19. A network system comprising:

two or more customer networks; and

a transport network that includes a plurality of routers, wherein at least two of the

plurality of routers couple the two or more customer networks to the transport network, wherein a first one of the plurality of routers includes;

at least one interface that receives a routing protocol message that advertises a link, wherein the routing protocol message includes a field for storing first data associated with the link in accordance with the routing protocol, and wherein the field is defined by the routing protocol as a type of field having a different function from an administrative group field as defined by the same routing protocol;

a hardware control unit that determines that the field of the received routing protocol message has been repurposed to store the second data in addition to the first data, wherein the second data specifies one or more extended administrative groups for the link different from the one or more administrative groups that are to be specified by the administrative group field, upon determining that the field has been repurposed, update routing information to associate the advertised link with the one or more extended administrative groups specified by the second data, data and perform path selection to select one or more paths based on the updated routing information receives configuration data from a user that specifies a range of values of the first data that are to be repurposed to specify second data, receives link data from a user that associates at least one of extended administrative groups with a link that is different from the link advertised by the received routing protocol message, and generates a routing protocol message to advertise the link that is different from the link advertised by the received routing protocol message, wherein the routing protocol message to advertise the link that is different from the link advertised by the received routing protocol message comprises a repurposed shared risk link group (SRLG) field for storing a value within the range of values to associate the link with one of the extended administrative groups rather than one or more SRLGs, and wherein the SRLG field is different than the Administrative Group field defined by the routing protocol, and

wherein the at least one interface transmits the routing protocol message to advertise the second link to adjacent ones of the plurality of routers.

20. A non-transitory computer-readable device comprising instructions that, when executed, cause one or more processors to:

receive a routing protocol message that advertises a link, wherein the routing protocol message includes a field for storing first data associated with the link in accordance with the routing protocol, and wherein the field is defined by the routing protocol as a type of field having a different function from an administrative group field as defined by the same routing protocol and comprises a shared risk link group (SRLG) type-length-value (TLV) field defined by the routing protocol to have a type portion, a length portion and a value portion, wherein the type portion of the SRLG TLV field identifies the second data stored by the value portion of the SRLG TLV field as associating the advertised link with a SRLG, and, and wherein the administrative group field comprises an administrative group TLV field defined by the routing protocol to have a type portion, a length portion and a value portion, wherein the type portion of the Administrative Group TLV field identifies the first data stored by the value portion of the Administrative Group TLV field as associating the advertised link with the one or more administrative groups in accordance with the routing protocol;

determine that the field of the received routing protocol message has been repurposed to store second data in addition to the first data, wherein the second data specifies one or more extended administrative groups for the link different from the one or more administrative groups that are to be specified by the administrative group field;

upon determining that the field has been repurposed, update routing information to associate the advertised link with the one or more extended administrative groups specified by the second data; and

perform path selection to select one or more paths based on the updated routing information.

21. The computer-readable device of claim 20, further comprising instruction that, when executed, cause the one or more processors to:

receive configuration data from a user that specifies a range of values of the first data that are to be repurposed to specify the second data;

determine whether the field stores the first data identifying a value that is included within the range of values specified by the configuration data; and

determine that the field of the received routing protocol message has been repurposed to specify the second data associating the link with the one or more extended administrative groups based on the determination that the field stores the first data identifying a value that is included within the range of values specified by the configuration data.

22. The non-transitory computer-readable device of claim 20,

wherein the routing protocol comprises an Open Shortest Path First (OSPF) routing protocol,

wherein the routing protocol message comprises a link state advertisement (LSA), Administrative Group TLV, and

wherein the type portion of the SRLG TLV field stores a value of sixteen to indicate that the value portion of the SRLG TLV field associates the advertised link with the SRLG in accordance with the OSPF routing protocol.

23. The non-transitory computer-readable device of claim 20,

wherein the routing protocol comprises an Intermediate System to Intermediate System (IS-IS) routing protocol,

wherein the routing protocol message comprises a Link State Protocol Data Unit, Administrative Group TLV, and

wherein the type portion of the SRLG TLV field stores a value of 138 to indicate that the value portion of the SRLG TLV field associates the advertised link with the SRLG in accordance with the IS-IS routing protocol.

24. The non-transitory computer-readable device of claim 20, further comprising instruction that, when executed, cause the one or more processors to:

receive configuration data from a user that specifies a range of values of the first data that are to be repurposed to specify the second data;

receive link data from a user that associates at least one of the extended administrative groups with a link that is different from the link advertised by the received routing protocol message, wherein the advertised link comprises a first link and the link that is different from the advertised link comprises a second link;

generate a routing protocol message to advertise the second link, wherein the routing protocol message to advertise the second link comprises a repurposed shared risk link group (SRLG) field for storing a value within the range of values to associate the link with one of the extended administrative groups rather than one or more SRLGs, and wherein the SRLG field is different than the administrative group field defined by the routing protocol; and

transmit the routing protocol message to advertise the second link to adjacent network devices.

25. The non-transitory computer-readable device of claim 20, further comprising instruction that, when executed, cause the one or more processors to perform a Constrained Shortest Path First (CSPF) path selection algorithm to select the one or more paths based on the updated routing information.

26. The non-transitory computer-readable device of claim 25, further comprising instruction that, when executed, cause the one or more processors to:

receive configuration data from a user that defines one or more constraints that constrains path selection as performed by the CSPF path selection algorithm, wherein the one or more constraints comprise the one or more extended administrative groups, and wherein the updated routing information comprises a graph data structure having nodes that represent network devices and edges that represent links;

prune the graph data structure based on the constraints to generate a pruned graph data structure; and

select the one or more paths based on the pruned graph data structure.

27. The non-transitory computer-readable device of claim 20, further comprising instruction that, when executed, cause the one or more processors to perform path selection with a multiprotocol label switching (MPLS) protocol module executing within the network device to resolve the routing information in order to generate at least one MPLS forwarding table, wherein the MPLS forwarding table includes entries that are each associated with a different label, wherein each of the entries defines an action that is to be taken with respect to an incoming MPLS packet having a label stack that includes the label associated with the corresponding entry, wherein the action includes one or more of pushing a different label onto the label stack, swapping the label of the label stack with a different label and popping the label from the label stack.

28. The non-transitory computer-readable device of claim 20, wherein the one or more processors are included within one of a label switching router (LSR) or a label edge router (LER).

29. A method comprising:

receiving, with a network device, a routing protocol message that advertises a link, wherein the routing protocol message includes a field for storing first data associated with the link in accordance with the routing protocol, and wherein the field is defined by the routing protocol as a type of field having a different function from an administrative group field as defined by the same routing protocol;

determining, with the network device, that the field of the received routing protocol message has been repurposed to store second data in addition to the first data, wherein the second data specifies one or more extended administrative groups for the link different from the one or more administrative groups that are to be specified by the administrative group field;

upon determining that the field has been repurposed, updating routing information to associate the advertised link with the one or more extended administrative groups specified by the second data;

performing, with the network device, path selection to select one or more paths based on the updated routing information,

receiving, with the network device, configuration data from a user that specifies a range of values of the first data that are to be repurposed to specify second data;

receiving, with the network device, link data from a user that associates at least one of extended administrative groups with a link that is different from the link advertised by the received routing protocol message;

generating, with the network device, a routing protocol message to advertise the link that is different from the link advertised by the received routing protocol message, wherein the routing protocol message to advertise the second link comprises a repurposed shared risk link group (SRLG) field for storing a value within the range of values to associate the link with one of the extended administrative groups rather than one or more SRLGs, and wherein the SRLG field is different than the Administrative Group field defined by the routing protocol;

transmitting, with the network device, the routing protocol message to advertise the second link to adjacent ones of the plurality of routers.

30. A method comprising:

receiving, with a network device, a routing protocol message that advertises a link, wherein the routing protocol message includes a field for storing first data associated with the link in accordance with the routing protocol, and wherein the field is defined by the routing protocol as a type of field having a different function from an administrative group field as defined by the same routing protocol;

determining, with the network device, that the field of the received routing protocol message has been repurposed to store second data in addition to the first data, wherein the second data specifies one or more extended administrative groups for the link different from the one or more administrative groups that are to be specified by the administrative group field;

upon determining that the field has been repurposed, updating routing information to associate the advertised link with the one or more extended administrative groups specified by the second data;

receiving configuration data from a user that defines one or more constraints that constrains path selection as performed by a Constrained Shortest Path First (CSPF) path selection algorithm, wherein the one or more constraints comprise the one or more extended administrative groups, and wherein the updated routing information comprises a graph data structure having nodes that represent network devices and edges that represent links; and

performing, with the network device, a Constrained Shortest Path First (CSPF) path selection algorithm to prune the graph data structure based on the constraints and select the one or more paths based on the pruned graph data structure.