Hierarchical label distribution protocol for computer networks

• US 7,936,780 B1
• Filed: 03/09/2009
• Issued: 05/03/2011
• Est. Priority Date: 03/12/2008
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Kompella, Kireeti
• Primary Examiner(s): Phunkulh; Bob A
• Application Number:
  US12/400,478
• Time in Patent Office: 785 Days
• Field of Search: None
• US Class Current: 370/466
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/507 Label distribution

Abstract

Techniques are described for providing routing scalability within a protocol such as a label distribution protocol. A method comprises receiving a label mapping message at an ingress router for establishing a label switched path (LSP) that identifies within a first portion a first label to be used for forwarding network traffic to an intermediate router of the LSP, and identifies within a separate portion a second label to be used for forwarding network traffic to an egress router of the LSP. The method further comprises parsing the first and separate portions, installing first forwarding state at the ingress router identifying the first label for forwarding network traffic to the intermediate router, and installing second forwarding state at the ingress router identifying a two-label stack comprising the first label as an outer label and the second label as an inner label for forwarding network traffic to the egress router.

Claims

1. A method comprising:

receiving a label mapping message at an ingress router within a first routing domain of a network for establishing an inter-routing domain label switched path (LSP), wherein the label mapping message identifies within a first portion of the label mapping message a first label to be used for forwarding network traffic to an intermediate router of the LSP, and identifies within a second portion of the label mapping message a second label to be used for forwarding network traffic to an egress router of the LSP within a second routing domain of the network;

parsing the first portion and the second portion of the label mapping message to identify the first label and the second label;

installing first forwarding state at the ingress router identifying the first label to be used for forwarding network traffic to the intermediate router; and

installing second forwarding state at the ingress router identifying a two-label stack to be used for forwarding network traffic on the inter-routing domain LSP to the egress router, the two-label stack comprising the first label as an outer label and the second label as an inner label.

2. The method of claim 1, further comprising forwarding network traffic to the egress router using the two-label stack according to the second forwarding state.

3. The method of claim 1, further comprising forwarding network traffic to the intermediate router using the first label according to the first forwarding state.

4. The method of claim 1,

wherein the first portion of the label mapping message comprises a required label type-length-value (TLV) that identifies the first label and a forwarding equivalence class (FEC) TLV that specifies a full network address of the intermediate router, and

wherein the second portion of the label mapping message comprises an optional label mapping TLV that identifies the second label and a full network address of the egress router.

5. The method of claim 4, wherein the second label and a network address of the egress router are specified within a sub-TLV of the label mapping TLV.

6. The method of claim 1, wherein the label mapping message identifies within the second portion of the label mapping message a plurality of additional labels to be used for forwarding network traffic to respective egress routers for establishing a plurality of additional LSPs.

7. The method of claim 6, further comprising selecting a subset of the plurality of additional labels in accordance with a policy;

and

installing third forwarding state at the ingress router identifying one or more different two-label stacks to be used for forwarding network traffic to respective egress routers corresponding to the selected subset of the plurality of additional labels.

8. The method of claim 1, wherein parsing the first portion and the second portion, installing the first forwarding state, and installing the second forwarding state comprise parsing the first portion and the second portion, installing the first forwarding state, and installing the second forwarding state with a label distribution protocol.

9. The method of claim 1, wherein the first routing domain and the second routing domain comprises first and second autonomous systems.

10. The method of claim 1, wherein the first routing domain and the second routing domain comprises first and second interior gateway protocol (IGP) routing domains of a single autonomous system.

11. A method for distributing labels for establishing an inter-domain label switched path (LSP) for forwarding network traffic, comprising:

executing a routing protocol to maintain routing information for a first routing domain of a network partitioned into a plurality of routing domains;

receiving a label mapping message at a border router of the first routing domain, the label mapping message identifying a first label to be used for forwarding network traffic to a first egress router within a second one of the routing domains of a network;

with the border router, allocating a second label to advertise to neighboring routers in the first routing domain to be used for forwarding network traffic to the first egress router;

with the border router, allocating a third label to advertise to neighboring routers the first routing domain to be used for forwarding network traffic to the border router;

generating a second label mapping message that includes at least both;

(i) a required portion of the second label mapping message identifying the third label to be used for forwarding network traffic to the border router, and (ii) a separate optional portion identifying the second label to be used for forwarding network traffic to the first egress router; and

advertising the second label mapping message to one or more neighboring routers within the first routing domain of the network.

12. The method of claim 11, further comprising:

receiving a third label mapping message at the border router that identifies a fourth label to be used for forwarding network traffic to a second egress router within the second routing domain of the network;

with the border router, allocating a fifth label to advertise to neighboring routers in the first routing domain to be used for forwarding network traffic to the second egress router;

generating a fourth label mapping message that identifies within a required portion of the fourth label mapping message the third label to be used for forwarding network traffic to the border router, and identifies within a separate optional portion of the fourth label mapping message the second label to be used for forwarding network traffic to the first egress router and the fifth label to be used for forwarding the network traffic to the second egress router; and

advertising the fourth label mapping message to neighboring routers within second routing domain.

13. The method of claim 12, wherein

wherein the required portion of the label mapping message comprises a required label type-length-value (TLV) that identifies the third label and a required forwarding equivalence class (FEC) TLV that identifies a network address of the border router, and

wherein the optional portion of the label mapping message comprises an optional label mapping TLV having a first sub-TLV that identifies the second label and a network address of the first egress router and a second sub-TLV that identifies the fifth label and a network address of the second egress router.

14. The method of claim 12, wherein

wherein the required portion of the label mapping message comprises a required label type-length-value (TLV) that identifies the second label and a required forwarding equivalence class (FEC) TLV that identifies a network address of the border router, and

wherein the optional portion of the label mapping message comprises an optional label mapping TLV having a first sub-TLV that identifies the first label and a network address of the first egress router and a second sub-TLV that identifies the third label and a network address of the second egress router.

15. The method of claim 11, further comprising:

receiving a third label mapping message at the border router that identifies a fourth label to be used for forwarding network traffic to a second egress router within the second routing domain of the network, wherein a network address of the first egress router and a network address of the second egress router may both be represented by a single network address prefix;

allocating the second label to advertise to neighboring routers in the first routing domain to be used for forwarding network traffic to the first egress router or the second egress router;

generating a fourth label mapping message that identifies within a required portion of the fourth label mapping message the third label to be used for forwarding network traffic to the border router, and identifies within a separate optional portion of the fourth label mapping message the second label to be used for forwarding network traffic to the network address prefix; and

advertising the fourth label mapping message to neighboring routers within the first routing domain of the network.

16. The method of claim 11, wherein generating the second label mapping message comprises generating the second label mapping message with a label distribution protocol.

17. The method of claim 16, wherein the label distribution protocol is the Label Distribution Protocol (LDP).

18. The method of claim 16, wherein the label distribution protocol is the Resource Reservation Protocol (RSVP).

19. The method of claim 11, wherein the first routing domain and the second routing domain comprise first and second autonomous systems.

20. The method of claim 11, wherein the first routing domain and the second routing domain comprise first and second interior gateway protocol (IGP) areas of a single autonomous system.

21. The method of claim 11, wherein the routing protocol comprises a link-state routing protocol, wherein the routing information comprises link-state routing information, and wherein the routing domain comprises a link-state routing area.

22. A router comprising:

an interface configured to receive a label mapping message at an ingress router within a first routing domain of a network for establishing an inter-routing domain label switched path (LSP), wherein the label mapping message identifies within a first portion of the label mapping message a first label to be used for forwarding network traffic to an intermediate router of the LSP, and identifies within a second portion of the label mapping message a second label to be used for forwarding network traffic to an egress router of the LSP within a second routing domain of the network;

a control unit configured to the first portion and the second portion of the label mapping message to identify the first label and the second label; and

forwarding information that associates network destinations with specific next hops and corresponding interfaces,

wherein the control unit is configured to install first forwarding state to the forwarding information identifying the first label to be used for forwarding network traffic to the intermediate router, and

wherein the control unit is configured to install second forwarding state to the forwarding information identifying a two-label stack to be used for forwarding network traffic on the inter-routing domain LSP to the egress router, the two-label stack comprising the first label as an outer label and the second label as an inner label.

23. The router of claim 22, wherein the control unit is configured to forward network traffic to the egress router using the two-label stack according to the second forwarding state and forward network traffic to the intermediate router using the first label according to the first forwarding state.

24. The router of claim 22, wherein the first portion of the label mapping message comprises a required label type-length-value (TLV) that identifies the first label and a required forwarding equivalence class (FEC) TLV that specifies a full network address of the intermediate router, and

wherein the second portion of the label mapping message comprises an optional label mapping TLV that identifies the second label and a full network address of the egress router.

25. The router of claim 22, wherein the label mapping message identifies within the second portion of the label mapping message a plurality of additional labels to be used for forwarding network traffic to respective egress routers for establishing a plurality of additional LSPs.

26. The router of claim 22, further comprising a label distribution protocol executing within the control unit to parse the first portion and the second portion of the label mapping message to identify the first label and the second label, and install the first and second forwarding state.

27. A non-transitory computer-readable medium comprising instructions for causing a programmable processor to:

receive a label mapping message at an ingress router within a first routing domain of a network for establishing an inter-routing domain label switched path (LSP), wherein the label mapping message identifies within a first portion of the label mapping message a first label to be used for forwarding network traffic to an intermediate router of the LSP, and identifies within a second portion of the label mapping message a second label to be used for forwarding network traffic to an egress router of the LSP within a second routing domain of the network;

parse the first portion and the second portion of the label mapping message to identify the first label and the second label;

install first forwarding state at the ingress router identifying the first label to be used for forwarding network traffic to the intermediate router; and

install second forwarding state at the ingress router identifying a two-label stack to be used for forwarding network traffic on the inter-routing domain LSP to the egress router, the two-label stack comprising the first label as an outer label and the second label as an inner label.

28. A network system comprising:

a computer network comprising a plurality of label switching routers,

the label switching routers executing a routing protocol that partitions the computer network into a plurality of routing domains, each of the label switching routers maintaining routing information containing full network addresses for the routing domain in which the respective label switching router resides,

the label switching routers executing a label distribution protocol to establish a label switched path that spans at least two of the routing domains, the label distribution protocol for at least one of the label switching routers requiring that network addresses advertised by label mapping messages of the label distribution protocol match the full network addresses of the routing information, and

at least a first one of the label switching routers in one of the routing domains outputting one of the label mapping messages to include at least;

(i) a first Multi-protocol Label Switching (MPLS) label and a full network address for reaching the first one of the label switching routers, and (ii) one or more additional pairs of MPLS labels and corresponding network addresses for reaching network destinations within the other routing domains.

29. The network system of claim 28, further comprising at least a second one of the label switching routers to receive the label mapping message output by the first one of the label switching router,

the label distribution protocol executing on the second one of the label switching routers installing forwarding state within the second one of the label switching routers to forward packets to the first one of the label switching routers using the first MPLS label, and

the label distribution protocol executing on the second one of the label switching routers disregarding the additional pairs of MPLS labels and corresponding network addresses specified by the label mapping message.

30. The network system of claim 28,

wherein the second one of the label switching routers comprises routing information that excludes network addresses corresponding to the additional pairs of MPLS labels and corresponding network addresses included within the label mapping message output by the first one of the label switching routers for reaching network destinations within the other routing domains.

31. The network system of claim 28, wherein the additional pairs of MPLS labels and corresponding network addresses are recursively encoded within one or more fields of the label mapping message.

32. The network system of claim 28, wherein the additional pairs of MPLS labels and corresponding network addresses are encoded as one or more sub-fields that each indicates a label and corresponding network address to which the advertising label switching router has MPLS forwarding connectivity.

33. The network system of claim 28, wherein the additional pairs of MPLS labels and corresponding network addresses are encoded as one or more sub-fields, the sub-fields being arranged in a tree-like hierarchical order from one or more parent sub-fields to one or more child sub-fields, and each network address specified by any sub-field within the tree-like hierarchical order being reachable using a label stack comprising the first MPLS label and those MPLS labels defined by sub-fields arranged in the tree-like hierarchical order between one of the parent sub-fields and the child sub-field containing the network address to be reached.

34. A method for distributing labels for establishing an inter-area label switched path (LSP) for forwarding network traffic, comprising:

executing, on a first label switching router, a routing protocol to maintain routing information for a first routing domain of a network partitioned into a plurality of routing domains; and

outputting a label mapping message to include at least;

(i) a first Multi-protocol Label Switching (MPLS) label and a full network address of the first label switching router, and (ii) one or more additional pairs of MPLS labels and corresponding network addresses for reaching for reaching label switching routers in other the routing domains of the network,

the additional pairs of MPLS labels and corresponding network addresses encoded as one or more sub-fields of the label mapping message, the sub-fields being arranged in a tree-like hierarchical order from one or more parent sub-fields to one or more child sub-fields, and each network address specified by any sub-field within the tree-like hierarchical order being reachable using a label stack comprising the first MPLS label and those MPLS labels defined by sub-fields arranged in the tree-like hierarchical order between one of the parent sub-fields and the child sub-field containing the network address to be reached.

35. A method comprising:

receiving a label mapping message at an ingress router within a first routing domain of a network for establishing an inter-routing domain label switched path (LSP), wherein the label mapping message identifies within a first portion of the label mapping message a first label to be used for forwarding network traffic to an intermediate router of the LSP, and identifies within a second portion of the label mapping message a second label to be used for forwarding network traffic to an egress router of the LSP within a second routing domain of the network;

parsing the first portion and the second portion of the label mapping message to identify the first label and the second label; and

presenting information relating to the LSP to a user, wherein the information includes the first label and the second label.