BGP link-state extensions for segment routing

Patent metadata

Field	Value
Publication number	US-9660897-B1
Application number	US-201414230946-A
Country	US
Kind code	B1
Filing date	Mar 31, 2014
Priority date	Dec 4, 2013
Publication date	May 23, 2017
Grant date	May 23, 2017

Abstract

Mechanisms are described by which link state “path” information can be collected from networks and shared with external components, such as routers or centralized controllers or path computation elements, using an exterior gateway protocol, such as the Border Gateway Protocol. That is, the link state information for multiple interior gateway protocol (IGP) routing domains is shared between external components using the exterior gateway protocol, such as BGP. As such, the techniques described herein allow link state information to be shared across different routing domains, such as routing and reachability information shared between different autonomous systems. The extensions described herein allow an exterior gateway protocol to be used to signal explicit path segments within IPG routing domains so as to set up an overall path that spans the multiple IPG routing domains.

First claim

The invention claimed is:

1. A method for constructing a path across a plurality of interior gateway protocol (IGP) routing domains, the method comprising:
generating, with a network device external to the IGP routing domains, a routing message that conforms to an exterior gateway protocol (EGP) and includes EGP reachability information that encodes interior gateway protocol (IGP) link state information for the plurality of IGP routing domains, wherein the EGP reachability information encodes the path within the IGP link state information as a sequence of IGP path segments associated with the plurality of IGP routing domains; and
outputting, from the network device and in accordance with the EGP, the routing message to a plurality of routing devices, each of the routing devices being associated with a one of the IGP routing domains.

2. The method of claim 1 , wherein the IGP link state information encoded by the EGP reachability information specifies, for each of the IPG path segments, a corresponding MPLS label to be used for forwarding packets along the respective IGP path segment.

3. The method of claim 2 , wherein the EGP reachability information encodes the IGP path segments as a set of explicit route objects, each of the explicit route objects specifying a respective next hop along the path and a corresponding path segment identifier that defines the MPLS label to be used when forwarding the packets along the IGP path segment to a forwarding equivalence class (FEC) associated with a destination of the path.

4. The method of claim 1 , wherein EGP reachability information is extended to specify IGP link state encodings for the following new segment routing identifiers: IGP prefix segment identifiers (SIDs), IGP-Adjacency SIDs, IGP-LAN-Adjacency SIDs and Binding SIDs.

5. The method of claim 1 ,
wherein the EGP reachability information encodes within a single type-length-value structure both a primary path and a backup path that span the IGP multiple routing domains, and
wherein the EGP reachability information encodes both the primary path and the backup path within the IGP link state information as a plurality of IGP path segments associated with the plurality of IGP routing domains.

6. The method of claim 1 , further comprising:
receiving, with the network device, one or more inbound routing messages from the routing devices associated with the IGP routing domains, wherein each of the routing messages conform to the exterior gateway protocol and includes EGP reachability information that encodes IGP link state information for the IGP routing domains, wherein the EGP reachability information encodes within the IGP link state information one or more existing IGP path segments internal to the plurality of IGP routing domains, each of the IGP path segments represented as a binding between a segment identifier and an MPLS label;
constructing, with the network device, an aggregate link state database that represents internal topologies of the IGP routing domains in accordance with the IGP link state information;
determining the path across the plurality of IGP routing domains by selecting one or more of the current IGP path segments from the IGP link state information within the aggregate link state database; and
generating the routing message in accordance with the selected one or more IPG path segments.

7. The method of claim 1 wherein the network device comprises one of a router, a path computation element and a software defined network (SDN) controller.

8. A network device comprising:
an aggregate link state database storing interior gateway protocol (IGP) link state information for a plurality of IGP routing domains;
a path computation element executed by a processor configured to select, based on the link state database, a path across the plurality of IGP routing domains;
a routing engine executed by the processor configured to output a routing message that conforms to an exterior gateway protocol (EGP),
wherein the routing engine constructs the routing message to include EGP reachability information that encodes IGP link state information to specify the path across the plurality of IGP routing domains, and
wherein the EGP reachability information encodes the path within the IGP link state information as a sequence of IGP path segments associated with the plurality of IGP routing domains.

9. The network device of claim 8 , wherein the IGP link state information encoded by the EGP reachability information specifies, for each of the IPG path segments, a corresponding MPLS label to be used for forwarding packets along the respective IGP path segment.

10. The network device of claim 8 , wherein the EGP reachability information encodes the IGP path segments as a set of explicit route objects, each of the explicit route objects specifying a respective next hop along the path and a corresponding path segment identifier that defines the MPLS label to be used when forwarding the packets along the IGP path segment to a forwarding equivalence class (FEC) associated with a destination of the path.

11. The network device of claim 8 , wherein EGP reachability information of the exterior gateway protocol is extended to contain fields to specify IGP link state encodings for the following new segment routing identifiers: IGP prefix segment identifiers (SIDs), IGP-Adjacency SIDs, IGP-LAN-Adjacency SIDs and Binding SIDs.

12. The network device of claim 8 ,
wherein the EGP reachability information encodes within a single type-length-value structure both a primary path and a backup path that span the IGP multiple routing domains, and
wherein the EGP reachability information encodes both the primary path and the backup path within the IGP link state information as a plurality of IGP path segments associated with the plurality of IGP routing domains.

13. The network device of claim 8 , further comprising:
wherein the routing engine receives one or more inbound routing messages from routing devices associated with the IGP routing domains, each of the routing messages conforming to the exterior gateway protocol and including EGP reachability information that encodes IGP link state information specifying one or more existing IGP path segments internal to the plurality of IGP routing domains, each of the IGP path segments represented as a binding between a segment identifier and forwarding equivalence class (FEC) associated with a destination of the path;
constructing, with the network device, an aggregate link state database that represents internal topologies of the IGP routing domains in accordance with the IGP link state information;
determining the path across the plurality of IGP routing domains by selecting one or more of the current IGP path segments from the IGP link state information within the aggregate link state database; and
generating the routing message in accordance with the selected one or more IPG path segments.

14. The network device of claim 8 , wherein the network device comprises one of a router, a path computation element and a software defined network (SDN) controller.

15. A non-transitory computer-readable medium comprising instructions that cause a processor to:
generate, with a network device external to the IGP routing domains, a routing message that conforms to an exterior gateway protocol (EGP) and includes EGP reachability information that encodes interior gateway protocol (IGP) link state information for the plurality of IGP routing domains, wherein the EGP reachability information encodes the path within the IGP link state information as a sequence of IGP path segments associated with the p

Assignees

• Juniper Networks Inc

Inventors

• Gredler Hannes

Classifications

• H04L45/50

  using label swapping, e.g. multi-protocol label switch [MPLS] · CPC title

• H04L45/04 Primary

  Interdomain routing, e.g. hierarchical routing · CPC title