Hierarchical label switching across multiple OSPF areas

• US 6,473,421 B1
• Filed: 03/29/1999
• Issued: 10/29/2002
• Est. Priority Date: 03/29/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Tappan, Daniel C.
• Primary Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/280,872
• Time in Patent Office: 1,310 Days
• Field of Search: 370/238, 370/238.1, 370/351, 370/397, 370/399, 709/230, 709/238, 709/241
• US Class Current: 370/351
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

In a communications-networking autonomous system consisting of an OSPF domain, autonomous-system border routers (I-ASBR and E-ASBR) cause exchange of hierarchical forwarding labels whose hierarchies are based on OSPF areas. A border router transmits into the domain an OSPF LSA Update message containing an AS-External LSA whose External Route Tag field other routers interpret as specifying a label to be used for forwarding. When that LSA is flooded into the OSPF domain, area border routers respond by flooding new LSAs created from the received one by replacing the label contained in the External Route Tag field with labels that specify their forwarding tables'"'"' locations containing information for forwarding to the originating autonomous system border router. In so doing, they enable packets destined for an extra-domain location to be forwarded through the autonomous system without requiring non-border routers to allocate labels to the exterior location or to border routers outside their areas. This enables a networking backbone to conserve its label space even though it carries a large variety of external traffic.

Claims

1. An OSPF domain configured as a plurality of OSPF areas and comprising a plurality of OSPF-speaking label-switching routers, including at least one area border router and one autonomous-system border router, that maintain forwarding information bases containing forwarding entries, identified by respective forwarding labels, that contain information that the label-switching routers use for forwarding packets toward respective destinations, at least some of the label-switching routers responding to reception of an AS-External LSA by interpreting part of the AS-External LSA'"'"'s External Route Tag field as indicating whether the External Route Tag field contains a forwarding label and, if so, interpreting part of the External Route Tag field as a forwarding label and installing that forwarding label as a replacement label in any forwarding entry based on that LSA for the destination that the AS-External LSA'"'"'s Link-State ID field specifies.

2. An OSPF domain as defined in claim 1 wherein each said area border router interprets part of the AS-External LSA'"'"'s External Route Tag field as indicating that the External Route Tag field contains a forwarding label only if the LSA External Route Tag field'"'"'s first bit is a zero.

3. An OSPF domain as defined in claim 2 wherein each said area border router interprets part of the AS-External LSA'"'"'s External Route Tag field as indicating that the External Route Tag field contains a forwarding label only if a format part of the AS-External LSA'"'"'s External Route Tag field contains a predetermined label-container-indicating value.

4. An OSPF domain as defined in claim 3 wherein the format part of the External Route Tag field is seven bits in length.

5. An OSPF domain as defined in claim 3 wherein the forwarding label occupies a twenty-bit-long part of the LSA External Route Tag field.

6. An OSPF domain as defined in claim 1 wherein, in response to receipt, from one said OSPF area, of each of at least some received OSPF AS-External LSAs whose Link-State ID fields specify autonomous-system border routers and whose External Route Tag fields it interprets as containing a forwarding label, at least one said area border router sends into another OSPF area a filtered OSPF AS-External LSA, whose Link-State ID field specifies the autonomous-system border router specified by the received OSPF AS-External LSA, whose Forwarding Address field contains an address of that area border router, and whose External Route Tag field contains the forwarding label associated by that border router with its forwarding-table entry that contains forwarding information for packets destined for the given autonomous-system border router.

7. An OSPF domain as defined in claim 6 wherein said at least one area border router that sends filtered OSPF AS-External LSAs interprets part of the External Route Tag fields that it interprets as containing forwarding labels as also including a filter-at-ABR field and sends filtered OSPF AS-External LSAs only in response to received OSPF AS-External LSAs in which the filter-at-ABR field contains a predetermined do-filter value.

8. An OSPF domain as defined in claim 7 wherein each said area border router interprets part of the AS-External LSA'"'"'s External Route Tag field as indicating that the External Route Tag field contains a forwarding label only if the LSA External Route Tag field'"'"'s first bit is a zero.

9. An OSPF domain configured to provide a plurality of OSPF areas, including at least first and second OSPF areas, the OSPF domain including:

A) a first autonomous-system border router, located in the first OSPF area, that transmits requests for use of a first label on packets to be forwarded by it to a given external destination outside that OSPF domain;

B) an area border router, located in the second OSPF area, that transmits requests for use of a second label on packets to be forwarded by it to the first autonomous-system border router;

C) a transit router, located in the second OSPF area, that transmits requests for use of a third label on packets to be forwarded by it to the area border router; and

D) a second border router that receives the requests from the transit, area border, and autonomous-system border routers and responds to at least some data packets from an external source outside the OSPF domain and destined for the given external destination by forwarding those data packets into the OSPF domain with a forwarding-label stack that includes the first, second, and third labels.

10. An OSPF domain as defined in claim 9 wherein the area border router sends its request as an OSPF AS-External LSA whose External Route Tag field includes the first label.

11. An OSPF domain as defined in claim 10 wherein the area border router sends its request as an OSPF AS-External LSA whose Link-State ID field specifies the first autonomous-system border router and whose Forwarding Address field contains an address of the area border router.

12. An OSPF domain as defined in claim 10 wherein the area border router sends its request as an OSPF AS-External LSA in which part of the AS-External LSA'"'"'s External Route Tag field is interpreted by the second autonomous-system border router as indicating that the External Route Tag field contains a forwarding label.

13. An OSPF domain as defined in claim 9 wherein the area border router maintains a forwarding information base containing forwarding entries, identified by respective forwarding labels, that contain information that it uses for forwarding packets toward respective destinations, responds to reception of an AS-External LSA by interpreting part of the AS-External LSA'"'"'s External Route Tag field as indicating whether the External Route Tag field contains a forwarding label, and, if so, interpreting part of the External Route Tag field as a forwarding label and installing that forwarding label as a replacement label in any forwarding entry based on that LSA for the destination that the AS-External LSA'"'"'s Link-State ID field specifies.

14. An OSPF domain as defined in claim 10 wherein the area border router sends its request in response to receipt, from outside the second OSPF area, of an OSPF AS-External LSA whose Link-State ID field specifies the autonomous-system border router and whose External Route Tag field it interprets as containing a forwarding label.

15. An OSPF-speaking label-switching router comprising:

A) a forwarding information base containing forwarding entries, identified by respective forwarding labels, that contain information that the router uses for forwarding packets toward respective destinations;

B) an interface for receiving AS-External LSAs; and

C) circuitry for responding to reception of an AS-External LSA by interpreting part of the AS-External LSA'"'"'s External Route Tag field as indicating whether the External Route Tag field contains a forwarding label and, if so, interpreting part of the External Route Tag field as a forwarding label and installing that forwarding label as a replacement label in any forwarding entry based on that LSA for the destination that the AS-External LSA'"'"'s Link-State ID field specifies.

16. A router as defined in claim 15 that interprets part of the AS-External LSA'"'"'s External Route Tag field as indicating that the External Route Tag field contains a forwarding label only if the LSA External Route Tag field'"'"'s first bit is a zero.

17. A router as defined in claim 16 that interprets part of the AS-External LSA'"'"'s External Route Tag field as indicating that the External Route Tag field contains a forwarding label only if a format part of the AS-External LSA'"'"'s External Route Tag field contains a predetermined label-container-indicating value.

18. A router as defined in claim 17 wherein the format part of the External Route Tag field is seven bits in length.

19. A router as defined in claim 17 wherein the forwarding label occupies a twenty-bit-long part of the LSA External Route Tag field.

20. A router as defined in claim 19 wherein the format part of the External Route Tag field is seven bits in length.

21. A storage medium containing instructions readable by a processor to configure the processor to function as an OSPF-speaking label-switching router that includes:

A) a forwarding information base containing forwarding entries, identified by respective forwarding labels, that contain information that the router uses for forwarding packets toward respective destinations;

B) an interface for receiving AS-External LSAs; and

C) circuitry for responding to reception of an AS-External LSA by interpreting part of the AS-External LSA'"'"'s External Route Tag field as indicating whether the External Route Tag field contains a forwarding label and, if so, interpreting part of the External Route Tag field as a forwarding label and installing that forwarding label as a replacement label in any forwarding entry based on that LSA for the destination that the AS-External LSA'"'"'s Link-State ID field specifies.

22. A storage medium as defined in claim 21 wherein the router interprets part of the AS-External LSA'"'"'s External Route Tag field as indicating that the External Route Tag field contains a forwarding label only if the LSA External Route Tag field'"'"'s first bit is a zero.

23. A storage medium as defined in claim 22 wherein the router interprets part of the AS-External LSA'"'"'s External Route Tag field as indicating that the External Route Tag field contains a forwarding label only if a format part of the AS-External LSA'"'"'s External Route Tag field contains a predetermined label-container-indicating value.

24. A storage medium as defined in claim 23 wherein the format part of the External Route Tag field is seven bits in length.

25. A storage medium as defined in claim 23 wherein the forwarding label occupies a twenty-bit-long part of the LSA External Route Tag field.

26. A storage medium as defined in claim 25 wherein the format part of the External Route Tag field is seven bits in length.

27. For communicating in an OSPF domain configured to provide a plurality of OSPF areas, including at least first and second OSPF areas, a method comprising:

A) from a first autonomous-system border router, located in the first OSPF area, transmiting requests for use of a first label on packets to be forwarded by the first autonomous-system border router to a given external destination outside the OSPF domain;

B) from an area border router, located in the second OSPF area, transmitting requests for use of a second label on packets to be forwarded by the area border router to the first autonomous-system border router;

C) from a transit router, located in the second OSPF area, transmitting requests for use of a third label on packets to be forwarded by it to the area border router; and

D) from a second border router, receiving the requests from the transit, area border, and autonomous-system border routers and responding to at least some data packets from an external source outside the OSPF domain and destined for the given external destination by forwarding those data packets into the OSPF domain with a forwarding-label stack that includes the first, second, and third labels.

28. A method as defined in claim 27 wherein the request from the area border Touter is sent as an OSPF AS-External LSA whose External Route Tag field includes the first label.

29. A method as defined in claim 28 wherein the request from the area border router is sent as an OSPF AS-External LSA whose Link-State ID field specifies the first autonomous-system border router and whose Forwarding Address field contains an address of the area border router.

30. A method as defined in claim 28 wherein the request from the area border router is sent as an OSPF AS-External LSA in which part of the AS-External LSA'"'"'s External Route Tag field is interpreted by the second autonomous-system border router as indicating that the External Route Tag field contains a forwarding label.

31. A method as defined in claim 27 further including:

A) maintaining at the area border router a forwarding information base containing forwarding entries, identified by respective forwarding labels, that contain information that the area border router uses for forwarding packets toward respective destinations;

B) responding to reception of an AS-External LSA by interpreting part of the AS-External LSA'"'"'s External Route Tag field as indicating whether the External Route Tag field contains a forwarding label; and

C) if so, interpreting part of the External Route Tag field as a forwarding label and installing that forwarding label as a replacement label in any forwarding entry based on that LSA for the destination that the AS-External LSA'"'"'s Link-State ID field specifies.

32. A method as defined in claim 28 wherein the request from the area border router is sent in response to receipt, from outside the second OSPF area, of an OSPF AS-External LSA whose Link-State ID field specifies the autonomous-system border router and whose External Route Tag field the area border router interprets as containing a for warding label.