WO2019084859A1

WO2019084859A1 - Data routing method and network element

Info

Publication number: WO2019084859A1
Application number: PCT/CN2017/109047
Authority: WO
Inventors: Guijuan WANG; Yun Tian; Junjie JI; Mingliang HUANG; Wei Xu
Original assignee: Telefonaktiebolaget LM Ericsson AB
Current assignee: Telefonaktiebolaget LM Ericsson AB
Priority date: 2017-11-02
Filing date: 2017-11-02
Publication date: 2019-05-09
Anticipated expiration: 2020-05-02

Abstract

The present disclosure proposes a method of routing data and a network element. The method comprises: receiving, from a first node, data to be routed and a first indicator, the first indicator being unique to the network element; determining, based on the first indicator, a second indicator, the second indicator indicating a routing segment destined to a second node; and transmitting, via the routing segment corresponding to the second indicator, the data to be routed.

Description

DATA ROUTING METHOD AND NETWORK ELEMENT

TECHNICAL FIELD

The present disclosure generally relates to the field of network communication, and in particular, to a data routing method and a network element.

BACKGROUND

With fast development of technologies and growing demand for networking, higher requirements are put forward on the networks in terms of capacity, throughput, latency, robustness, etc. To meet such requirements, one of the most important aspects to be improved is network routing. Routing is the process of selecting a path for traffic in a network, or between or across multiple networks.

As a routing protocol, Segment Routing (SR) is an emerging protocol that allows flexible and efficient definition of end-to-end paths, and is an ideal design for Software-Defined Networking (SDN) deployments, with a combination of centralized and distributed intelligence. SR uses the source routing paradigm. Therefore, an ingress node may encode an ordered list of instructions (also known as “segments” ) into a packet, which conducts the packet to its destination. A segment can represent any instruction, topological or service-based. Further, a segment may be globally significant, called global segment, or be meaningful to the originating node, called local segment.

With regard to forwarding plane, SR can be directly applied to the Multiple Protocol Label Switching (MPLS) architecture. A segment can be encoded as an MPLS label. SR does not require Label Distribution Protocol (LDP) or Resource Reservation Protocol -Traffic Engineering (RSVP-TE) label signaling protocol. With the segment routing extension to a link state routing protocol, a Segment ID (SID) can be advertised by the link state routing protocol, such as Open Shortest Path First (OSPF) or Intermediate System -Intermediate System (IS-IS) .

When OSPF is used, SR paths can be expressed by prefix segments and/or adjacency segments. A prefix segment represents the shortest path to a prefix or node based on the Interior Gateway Protocol (IGP) topology by using a global SID. An adjacency segment represents a hop between two adjacent nodes in the IGP topology using a local SID. An SR node may use a prefix segment, an adjacency segment, or a mix of them to steer packets into a segment routing path based on the network requirement.

OSPF supports complex networks having a lot of routers. To support better administration and a larger scale, an OSPF network is often divided into areas which are logical groups of networks and routers. Backbone Area (typically with an area ID of 0 or area0) is the center of all areas. An Area Border Router (ABR) , which has at least an interface in area0 and one or more interfaces in one or more other areas, connects the areas together. A router having its interfaces connected to a same area is called an Internal Router (IR) .

Each area has a separated Link State Database (LSDB) . When an ABR sends link state information from one of its connected area to other connected area (s) , the advertising router for the link state information is set to the ABR itself and the information may be summarized. Thus, the topology of an area is unknown to other areas. This can reduce the size of the routing information database and also reduce routing traffic between areas.

SUMMARY

As described above, a large OSPF network may be divided into areas. To set up an end-to-end SR path across OSPF areas, two methods are typically used, but either of them has its own limitations.

The first method is that an ABR propagates directly an intra-area node SID from an area to another area as the example described in section 3.6 “Inter-Area Considerations” of [RFC Segment Routing Architecture] . In this way, an end-to-end path can be set up, but there are some limitations:

● A node SID is required to be unique within its visible domain. Therefore, the SID must be unique throughout the whole OSPF domain, meanwhile the SID range is limited, for example, 65535 in an existing Cisco system.

● If a constraint-based path calculation algorithm is used, a source router needs to encode the whole SR path into packets. Therefore, the SID stack depth could be very deep for a long path, which may exceed the depth limit of a hardware label stack.

● In addition, a source router in an area doesn’t know the topologies of other areas since the ABR associated with the area may have changed the advertising router of the link state information for the source router to the ABR itself before propagating the inter-area prefix. In this case, the source router cannot control the portion of the path in the other areas with its own topology knowledge in an efficient manner.

Furthermore, the second method is that an ABR performs an aggregation for its intra-area prefixes, and propagates only an SID for the summary prefix, for example, by using a “range 10.10.10.0/24” command to summarize all prefixes in 10.10.10. ＊/32 and then propagating only an SID for the 10.10.10.0/24.

In this way, the SID number needed to be advertised across areas can be decreased greatly. In this case, however, a path between an IR A in an area and another IR B in another area gets disjointed at the ABR between the two areas. In other words, the first part of the path may be established from the source router A to the ABR using the summary prefix SID, and the second part may be established from the ABR to the IR B using the specified prefix SID. In this case, the labeled traffic is first tunneled through the first part of the path, and when arriving at the ABR, it is turned into pure IP traffic, and an IP-to-label mapping is needed to be done again. If the segment routing is used in an MPLS Virtual Private Network (VPN) provider network, the traffic would be dropped at the ABR since the ABR cannot recognize the customer destination in the packet.

In view of the above issues, the present disclosure proposes a method of routing data and a network element.

According to a first aspect of the present disclosure, a method at a network element of routing data is proposed. The method comprises: receiving, from a first node, data to be routed and a first indicator, the first indicator being unique to the network element; determining, based on the first indicator, a second indicator, the second indicator indicating a routing segment destined to a second node; and transmitting, via the routing segment corresponding to the second indicator, the data to be routed.

In some embodiments, the determination of the second indicator comprises: determining, based on the first indicator, one or more indicators comprising the second indicator, the one or more indicators indicating one or more routing segments, respectively, which form a route from the network element to the second node. In some embodiments, the second indicator indicates a routing segment which associated with the next hop for the network element in the route. In some embodiments, the method further comprises: determining, based on the first indicator, a third indicator which is unique to the second node and enables the second node to determine one or more routing segments for the data; and transmitting, via the routing segment corresponding to the second indicator, the third indicator. In some embodiments, the determination of the one or more indicators comprises: looking the first indicator up in a forwarding table maintained by the network element to determine the one or more indicators, and/or the determination of the third indicator comprises: looking the first indicator up in the forwarding table maintained by the network element to determine the third indicator. In some embodiments, the method further comprises: receiving, from the first node, a fourth indicator, the fourth indicator indicates a routing segment destined to the network element. In some embodiments, before the reception of the data to be routed and the first indicator, the method further comprises: receiving, from the second node, the one or more indicators indicating one or more routing segments, respectively, which form a route from the network element to the second node; updating the forwarding table by storing the one or more indicators into the forwarding table in association with the first indicator; and advertising, to the first node, the fourth indicator and the first indicator on behalf of the second node. In some embodiments, before the reception of the data to be routed and the first indicator, the method further comprises: receiving, from the second node, the third indicator which is unique to the second node and enables the second node to determine one or more routing segments for the data; and updating the forwarding table by storing the third indicator into the forwarding table in association with the first indicator. In some embodiments, the method further comprises: receiving, from a third node, a route setting request to set up a route from the network element to a fourth node; and updating the forwarding table based on the route setting request. In some embodiments, the route setting request comprises a fifth indicator which is unique to the network element and one or more six indicators indicating one or more routing segments, respectively, which form a route from the network element to the fourth node, and the updating of the forwarding table comprises: storing the one or more six indicators into the forwarding table in association with the fifth indicator. In some embodiments, the route setting request further comprises a seventh indicator which is unique to the fourth node, and the updating of the forwarding table further comprises: storing the seventh indicators into the forwarding table in association with the fifth indicator. In some embodiments, each of the indicators is a Multiple Protocol Label Switching (MPLS) label. In some embodiments, the network element is an Area Border Router (ABR) coupled to a first area and a second area, and the first node belongs to the first area and the second node belongs to the second area. In some embodiments, the third node is a Software Defined Network (SDN) controller.

According to a second aspect of the present disclosure, a network element is proposed. The network element comprises: a processor; and a memory storing instructions which, when executed by the processor, cause the processor to perform any of the above methods.

According to a third aspect of the present disclosure, a non-transitory computer readable storage medium having instructions stored thereon, which, when executed by a processor, cause the processor to perform any of the above methods.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing and other features of the present disclosure will become more fully apparent from the following description and appended claims, taken in conjunction with the accompanying drawings. Understanding that these drawings depict only several embodiments in accordance with the disclosure and therefore are not to be considered limiting of its scope, the disclosure will be described with additional specificity and detail through use of the accompanying drawings.

Fig. 1 is a block diagram showing an exemplary configuration of an OSPF system with SR extension according to an embodiment of the present disclosure.

Fig. 2 is a flow chart showing an exemplary method of mapping between a prefix SID and a local SID according to an embodiment of the present disclosure.

Fig. 3 is a diagram showing a network comprising two areas in which a method of routing data according to an embodiment of the present disclosure is applied at an ABR.

Fig. 4 is a diagram showing an exemplary message flow among some nodes in the network shown in Fig. 3.

Fig. 5 is a diagram showing a network comprising three areas in which a method of routing data according to an embodiment of the present disclosure is applied at two ABRs.

Fig. 6 is a diagram showing an exemplary message flow among some nodes in the network shown in Fig. 5.

Fig. 7 is a diagram showing a network comprising three areas in which a method of routing data according to an embodiment of the present disclosure is applied at an ABR and an IR, respectively.

Fig. 8 is a diagram showing a network comprising three areas in which a method of routing data according to an embodiment of the present disclosure is compared with a conventional data routing method.

Fig. 9 is a diagram showing a network comprising three areas with respective PCE based controllers according to an embodiment of the present disclosure.

Fig. 10 is a block diagram schematically showing an exemplary arrangement which may be used in a network element according to an embodiment of the present disclosure.

DETAILED DESCRIPTION

Hereinafter, the present disclosure is described with reference to embodiments shown in the attached drawings. However, it is to be understood that those descriptions are just provided for illustrative purpose, rather than limiting the present disclosure. Further, in the following, descriptions of known structures and techniques are omitted so as not to unnecessarily obscure the concept of the present disclosure.

Hereinafter, some embodiments of the present disclosure will present a mechanism used in setting up an end-to-end inter-area path based on the segment routing. The mechanism can be implemented at an ABR, which will work as a translator and a shield for prefix SIDs of Internal Routers (IR) in an area associated with the ABR. For example, when the ABR is required to propagate an intra-area prefix SID of an IR in the area to other areas, it may translate the global prefix SID to a local SID and encodes its own node SID on top of the local SID to be advertised for routers outside of the area to recognize it. The ABR node SID can be recognized by the routers outside of the area and can be used for steering traffic to the ABR. The local SID is used to determine the actual prefix SID/SIDs of the intended IR after the traffic arrives at the ABR. This (ABR node SID, ABR local SID) tuple may work as a glue which joints the path from the routers outside of the area to the ABR and the path from the ABR to the intra-area router. Furthermore, the mechanism may also hide the intra-area router SID from other areas, and thus each of the areas can enjoy the whole global SID space.

However, please note that although the embodiments presented herein are provided in a context of an OSPF network, they are actually also applicable in other contexts, for example any other network with another SR implementation, for example, an IS-IS network. Please also note that although the mechanism is implemented at ABRs in some of the embodiments, the mechanism may be actually also implemented at any node within the network, for example, IRs, backbone routers, or Autonomous System Boundary Routers (ASBR) as will explained later.

When the segment routing is deployed over an OSPF network with multiple areas, with the mechanism proposed in the present disclosure:

● An end-to-end SR path across areas can be set up, which can meet the requirement of MPLS VPN provider network.

● IR node prefix SIDs in an area can be hidden from other areas. Thus, an area can use the whole global SID range, and more SR routers can be supported in an OSPF domain. Also, SID administration becomes easier since SID conflicting domain becomes smaller.

● An ABR gets a chance to control segment paths within its connected area. By doing this, a long SR path can be expressed with fewer SIDs, and therefore SR can better fit to the maximum hardware label stack depth in an existing network environment.

● The mechanism can be implemented by updating only the ABRs, or in general, to some specified routers in a network, no change is made to the IRs (note: most OSPF nodes are IRs) , or in general, other routers in the network, thereby resulting an easier deployment.

The mechanism will be described in detail below with reference to the drawings.

Fig. 1 is a block diagram showing an exemplary configuration of an OSPF system 1 (for example, an OSPF or SR router) with SR extension according to an embodiment of the present disclosure. As shown in Fig. 1, the OSPF system 1 may comprise an OSPF packet receiver 11, an OSPF packet sender 12, an SR arithmetic unit 13, an OSPF arithmetic unit 14, an SID/label manager 15, and a policy manager 16. Further, the OSPF system 1 may also comprise an OSPF Routing Information Base (RIB) 17 and a segment information base 19. Furthermore, the OSPF system 1 may be coupled to a segment/label Forwarding Information Base (FIB) 18. Please note that some of the above-mentioned modules may be omitted, replaced with some other modules, incorporated with some other modules, or shared by another OSPF system in some other embodiments, and therefore none of them is indispensable.

As shown in Fig. 1, the OSPF packet receiver 11 may accept packets into the OSPF system 1. After some basic processing, for example, packet validation, the packets may be passed to the OSPF arithmetic unit 14 or the SR arithmetic unit 13 based on its packet type. For example, as shown in Fig. 1, if the incoming packet has a packet type of SR Link State Advertisement (SR LSA) , then the packet will be forwarded to the SR arithmetic unit 13. Otherwise, the packet will be forwarded to the OSPF arithmetic unit 14. Further, as also shown in Fig. 1, the OSPF packet sender 12 may transfer packets generated by the OSPF or SR process to the neighbors.

The OSPF arithmetic unit 14 may process various kinds of OSPF packets and events, maintain the OSPF neighborhood, and set up Link State Database (LSDB) and Routing Information Base (RIB) 17. The policy manager 16 may be used for configuring and storing user defined or system policies. For example, an SR router may use various algorithms to calculate reachability, such as Shortest Path First (SPF) , Strict SPF, or even security based algorithm. An SR node may also choose whether and how to advertise SID (s) for the prefixes/links. For example, at an ABR, it is not necessary to propagate SIDs of all intra-area routers. In other words, such policies can be managed by the policy manager 16. The SID/label Manager 15 may oversee SID management, such as allocating/recycling Segment Routing Global Block (SRGB) and Segment Routing Local Block (SRLB) .

The SR arithmetic unit 13 may decode the SR data from an LSA packet, and calculates the best segment path based on the OSPF RIB 17 in case of the SPF algorithm is used. In addition or alternatively, the calculation of the best segment path may also be based on polices if a constraint-based algorithm is used, for example, in terms of QoS, load-balance, and/or security. Further, the SR arithmetic unit 13 may pass the selected segment/segment-stack information for prefixes and/or links to the forwarding managers which in turns installs the best path into the Forwarding Information Base (FIB) , which is the Label FIB (LFIB) 18 in case of an MPLS data path is used.

In the embodiment shown in Fig. 1, the SR arithmetic unit 13 may generate LSA packets for its own links/prefixes. If the system 1 is an ABR, it may propagate the node SID for IRs to other area, wherein the SID is generated by the IR itself, or generated by another IR or a SR mapping server. In case of aggregation is performed at the ABR, only the SID for summary route is propagated.

When the ABR is required to propagate a prefix SID of a router in an area to routers outside of the area, and if the mechanism mentioned above is enabled, the ABR will not send directly the SID of the router used within the area. Instead, it may allocate a local SID in SRLB, and then push the allocated local SID and the ABR’s own node SID (which is in the SRGB) on top thereof into the label stack. Those two SIDs together represent the intra-area prefix, and are then propagated to other areas. Also, this “Prefix SID” to “ABR SID + local SID” mapping is installed into this ABR’s LFIB (for example, the segment information base 19) . With the local SID, the ABR can determine the intra-area prefix SID when the labeled traffic arrives at this ABR. An exemplary process will be described with reference to Fig. 2 below.

Please note that although a local SID is used in mapping “the prefix SID” , the present disclosure is not limited thereto. In some other embodiments, other unique indicator than the local SID can be used in mapping “the prefix SID” . In fact, as long as the indicator is unique to the ABR and the ABR can determine the prefix SID from the indicator, such an indicator can be used in mapping “the prefix SID” . For example, an example of the indicator may be a randomly generated number which is locally unique at the ABR. In this case, when the ABR receives a packet having this unique number on the top of its label stack (without loss of generality, assuming the penultimate node along the path to the ABR already popped the label/SID of the ABR from the label stack) , the ABR may determine the actual prefix SID for the destination node of the packet based on the random number, for example, by looking it up in a local table.

The method begins with step S21, where a prefix SID of a router in an area associated with a SR node (for example, the ABR or OSPF system 1 as shown in Fig. 1 is received at the SR node and the SR node determines that it is the best based on the SR algorithm and the policies, the packet receiver (for example, the OSPF packet receiver 11) may pass the prefix SID to a forwarding manager (for example, the SR Arithmetic Unit 13) , which can install the mapping to LFIB (for example, the segment information base 19) at step S22. After that, if there is a need to propagate the SID (step S23: Y) , and if this SR node is an ABR (step S24: Y) and the mechanism mentioned above is to be enabled (step S25: Y) , the ABR will translate the intra-area global node SID to a local SID at step S26 and push the local SID together with the ABR’s node SID on top thereof into the label stack at step S29, and then send the tuple (ABR’s node SID, the local SID) out to other areas at step S32, for example, in a form of labels with the ABR’s node SID being the top label in the stack.

Further, if the SPF algorithm is used for calculating the best SR path (S27: N) , the ABR may install the “local SID to intra-area prefix-SID” mapping into the LFIB at step S28, and if a constraint-based-algorithm is used (S27: Y) , the ABR may calculate an SR path to the intra-area prefix which may come out as an SID or a list of SIDs at step S30. The ABR may install the “local-SID to SID/SID-list” mapping in the LFIB at step S31 and proceed to step S29.

Further, if any of steps S23, S24, and S25 gives a negative result, then the process may end directly as shown in Fig. 2.

Please note that at step S21, the node may receive multiple SIDs for the same prefix. Based on the Prefix SID Sub-TLV description in RFC [OSPF segment routing extension] section 5, the receiving node must use the first label and may use subsequent SIDs, and when propagating the SIDs, the original order would be preserved. This allows a consistent view across areas even through some transit nodes support only one label. Therefore, for an ospf-segment-routing-extension RFC conformed IR, it can just use the top SID which is the ABR’s SID, thus no update is needed to implement the mechanism mentioned above.

Please also note that some of the steps in the method shown in Fig. 2 may have different orders and/or may be omitted. For example, steps S23, S24, and/or S25 may be performed in another order, for example, in a reversed order or in any other order. Further, step s27, s30, and s31 may be omitted when only the SPF algorithm is used. Therefore, such variations, modifications, substitutions may be embraced by the present disclosure.

Next, with reference to Fig. 3 through Fig. 8, some specific embodiments of the present disclosure will be described in detail to illustrate the mechanism in a more intuitive manner.

First, a specific embodiment of the present disclosure illustrating a scenario involving two areas will be described in detail with reference to Fig. 3 and Fig. 4. Fig. 3 is a diagram showing a network comprising two

areas

10 and 20 in which a method of routing data according to an embodiment of the present disclosure is applied at an ABR, R1 200. Fig. 4 is a diagram showing an exemplary message flow 400 among some nodes in the network shown in Fig. 3.

As shown in Fig. 3, the network may be divided into two areas, Area0 10 (for example, a backbone area) and Area1 20 (for example, a non-backbone area) . The Area0 10 may comprise three nodes or internal routers R01 110, R02 120, and R03 130, and the Area1 20 may comprise three nodes or internal routers R11 210, R12 220, and R13 230. Further, an ABR R1 200 connects the Area0 10 to the Area1 20. Please note that the number of the routers/nodes in each area, the way to connect the nodes, and the way to divide the network into the areas shown in Fig. 3 are merely examples and the present disclosure is not limited thereto. For example, Area0 10 may comprise one or more nodes and the nodes can be connected in a different manner than that shown in Fig. 3. Also, Area1 20 may comprise one or more nodes and the nodes can be connected in a different manner than that shown in Fig. 3.

Fig. 3 shows the control flow (or SID advertisement) and data flow (or data transmission) for an inter-area SR path between R12 220 in Area1 20 and R02 120 in Area0 10. In the embodiment shown in Fig. 3, the SID of R12 220 is advertised to R02 120 while the data transmission is conducted from R02 120 to R12 220. As the ingress router of the data transmission, R02 120 is required to support attaching two labels for a prefix, and no change is required on IRs.

The top portion of Fig. 3 shows the control flow of R12 SID advertisement, supposing that the SR Global Block (SRGB) is from 100 to 300 and the SR Local Block (SRLB) is from 2000 -3000, and supposing that all node prefix SIDs are same as their reference numerals, for example, R12 220 has a node prefix SID of 220. The hop-to-hop SID advertisement from R12 to R02 is as follows.

● At IRs of Area1 20: R12 220 has a node prefix SID of 220, and it propagates its SID to all internal routers in Area1 20 (for example, S410 shown in Fig. 4) . These internal routers may install the SID 220 into their forwarding tables. When traffic with the label 220 arrives at a router as will be seen later, the router may forward the traffic to R12 220 by using the shortest path.

● At R1 200: when the SID 220 arrives at R1 200 (for example, S410 shown in Fig. 4), R1 200 may also install the SID 220 into its LFIB. If R1 200 is required to propagate the SID 220 to other areas, R1 200 may translate the SID 220 into a local SID, for example, a local SID 2001, push the local SID 2001 and its own node SID 200 on top thereof into the label stack (for example, S420 shown in Fig. 4) , and propagates the label stack to Area0 10 (for example, S430 shown in Fig. 4) . R1 200 may also install a mapping entry, (2001 switches to 220) , into its LFIB. With this entry, when traffic with the local SID 2001 arrives at R1 200, R1 200 can switch the local SID 2001 to the actual R12 prefix SID 220.

● At IRs of Area0 10: When the tuple (200, 2001) for the R12 220 is received at Area0 routers, as defined in the OSPF Segment Routing extension RFC section 5, the receiving router can use only the top SID 200 or using both 200 and 2001. R01 110/R03 130 can choose to install the SID 200 only into LFIB. When propagating, it is required to keep the two labels and their order. The tuple (200, 2001) is finally propagated to the source router R02 120 (for example, S430 shown in Fig. 4) .

In this way, along the SID propagation/advertisement path from R12 to R02, different labels/SIDs may be used for the same node R12 220. For example, at the internal routers in Area1 20, the installed SID for the R12 220 is SID 220. In contrast, at internal routers in Area0 10, the installed SIDs for the R12 220 is the tuple (200, 2001) .

Next, with reference to the bottom portion of Fig. 3 which shows the data transmission from R02 to R12, a detailed description of how to route data with the above-mentioned mechanism will be given.

● At R02 120, packet payload is labeled with (200, 2001) and sent out (for example, S450 shown in Fig. 4) .

● At the following IR R01 110 and/or R03 130 in Area0 10: they may steer the traffic to R1 200 based on the top label 200 (the node SID of ABR R1 200) using the shortest path.

● At ABR R1 200, it pops its SID 200 from the label stack (in some other embodiments, the SID 200 may have been already popped at the penultimate hop of the path to R1 200, for example, at R01 110, if PHP is enabled) , and switches the local SID 2001 to SID 220 (for example, S460 shown in Fig. 4) and sends the traffic to Area1 20 (for example, S470 shown in Fig. 4) .

● At the following IRR11 210 or R13 230 in Area1 20, itsendsthe payloadto R12 220 by means of the prefix SID 220 (for example, S470 shown in Fig. 4) .

In this way, each of the two areas may use the whole SRGB range without disturbing the other area.

Next, another specific embodiment of the present disclosure illustrating a more complex scenario involving three areas will be described in detail with reference to Fig. 5 and Fig. 6. Fig. 5 is a diagram showing a network comprising three areas, Area0 10 (for example, a backbone area) , Area1 20, and Area2 30 (for example, non-backbone areas) in which a method of routing data according to an embodiment of the present disclosure is applied at two ABRs, R1 200 and R2 300. Fig. 6 is a diagram showing an exemplary message flow 500 among some nodes in the network shown in Fig. 5.

As shown in Fig. 5, the network may be divided into three areas, Area0 10, Area1 20, and Area2 30. The Area0 10 may comprise three nodes or internal routers R01 110, R02 120, and R03 130, the Area1 20 may comprise three nodes or internal routers R11 210, R12 220, and R13 230, and the Area2 30 may comprise three nodes or internal routers R21 310, R22 320, and R23 330. Further, an ABR R1 200 may connect the Area0 10 to the Area1 20, and an ABR R2 300 may connect the Area0 10 to the Area2 30. Please note that the number of routers in each area, the way to connect the routers, and the way to divide the network into the areas shown in Fig. 5 are merely examples and the present disclosure is not limited thereto. For example, Area0 10 may comprise one or more nodes and the nodes can be connected in a different manner than that shown in Fig. 5. Also, Area1 20 may comprise one or more nodes and the nodes can be connected in a different manner than that shown in Fig. 5. Also, Area2 30 may comprise one or more nodes and the nodes can be connected in a different manner than that shown in Fig. 5.

Fig. 5 shows the control flow and data flow for an inter-area SR path between R12 220 in Area1 20 and R22 320 in Area2 30 and the data transmission will be conducted from R22 320 to R12 220. In the embodiment shown in Fig. 5, the ingress router R22 of the data transmission is required to support attaching two labels for a prefix, and no change is required on IRs.

The top portion of Fig. 5 shows the control flow of R12 SID advertisement, supposing that the SR Global Block (SRGB) is from 100 to 400 and the SR Local Block (SRLB) is from 2000 -3000, and supposing that all node prefix SIDs are same as their reference numerals, for example, R12 220 may have a node prefix SID of 220. Here is the hop-to-hop SID advertisement from R12 220 to R22 320.

● At IRs of Area1 20: R12 220 has a node prefix SID of 220, and it propagates its SID to all internal routers in Area1 20 (for example, S510 shown in Fig. 6) . The Area1 routers install the SID 220 into their forwarding tables. When traffic with label 220 arrives at a router as can be seen later, the router may forward the packet to R12 220 by using the shortest path.

● At R1 200: when the SID 220 arrives at R1 200 (for example, S510 shown in Fig. 6) , R1 200 may also install SID 220 into its LFIB. If R1 200 is required to propagate the SID 220 to other areas, R1 200 may translate the SID 220 into a local SID, for example, a local SID 2001, push the local SID 2001 and its own node SID 200 on top thereof into the label stack (for example, S520 shown in Fig. 6) , and propagate the label stack to Area0 10 (for example, S530 shown in Fig. 6) . R1 200 may also install a mapping entry, (2001 switches to 220) , into its LFIB. With this entry, when traffic with the local SID 2001 arrives at R1 200, R1 200 can switch the local SID 2001 to the actual R12 prefix SID 220.

● At IRs of Area0 10: When the tuple (200, 2001) for the R12 220 is received at Area0 routers, as defined in the OSPF Segment Routing extension RFC section 5, the receiving router may use the top SID 200 only or both 200 and 2001. R01 110/R02 120/R03 130 can choose to install SID 200 only into LFIB. When propagating, it is required to keep the two labels and their order, and the tuple (200, 2001) may be propagated to the ABR R2 300 (for example, S530 shown in Fig. 6) .

● At R2 300: when the tuple (200, 2001) arrives at R2 300 (for example, S530 shown in Fig. 6) , R2 300 also need to install the tuple (200, 2001) into its LFIB. If R2 300 is required to propagate the tuple (200, 2001) to its associated area (for example, Area2 30) , R2 300 may translate the tuple (200, 2001 ) into a local SID, for example, a local SID 2003, push the local SID 2003 and its own node SID 300 on top thereof into the label stack (for example, S540 shown in Fig. 6) , and propagate the label stack to Area2 30 (for example, S550 shown in Fig. 6) . R2 300 may also install a mapping entry, (2003 switches to the tuple (200, 2001) ) , into its LFIB. With this entry, when traffic with the local SID 2003 arrives at R2 300, R2 300 can switch the local SID 2003 to the tuple (200, 2001 for the R12 220.

● At IRs of Area2 30: When the (300, 2003) for the R12 220 is received at Area2 routers, as defined in the OSPF Segment Routing extension RFC section 5, the receiving router can use the top SID 300 only or both 300 and 2003, R21 310/R23 330 can choose to install 300 only into LFIB. When propagating, it is required to keep the two labels and their order. The tuple (300, 2003) is finally propagated to the source router R22 320 (for example, S550 shown in Fig. 6) .

In this way, on the SID propagation/advertisement path from R12 220 to R22 320, different labels/SIDs may be used for the same node R12 220. For example, at internal routers in Area1 20, the installed SID for the R12 220 is SID 220. In contrast, at internal routers in Area2 30, the installed SIDs for the R12 220 is the tuple (300, 2003) .

Next, with reference to the bottom portion of Fig. 5 which shows the data flow from R22 320 to R12 220, a detailed description of how to route data with the above-mentioned mechanism will be given.

● At R22 320, payload may be labeled with (300, 2003) and sent out (for example, S560 shown in Fig. 6) .

● At the following IR R21 310 or R23 330 in Area2 30: it may steer the traffic to R2 300 based on the top label 300 (the node SID of ABR R2 300) using the shortest path.

● At ABR R2 300, it may pop its SID 300 from the label stack (in some other embodiments, the SID 300 may have been already popped at the penultimate hop of the path to R2 300, for example, at R21 310, if PHP is enabled) , and switch the local SID 2003 to the tuple (200, 2001) (for example, S570 shown in Fig. 6) and send it to Area0 10 (for example, S580 shown in Fig. 6) .

● At the following IR R01 110, R02 120, and/or R03 130 in Area0 10: they may steer the traffic to R1 200 based on the top label 200 (the node SID of ABR R1 200) using the shortest path.

● At ABR R1 200, it may pop its SID 200 from the label stack (in some other embodiments, the SID 200 may have been already popped at the penultimate hop of the path to R1 200, for example, at R01 110, if PHP is enabled) , and switch the local SID 2001 to SID 220 (for example, S590 shown in Fig. 6) and send it to area1 20 (for example, S595 shown in Fig. 6) .

● At the following IR R11 210 or R13 230 in Area1 20, it may send the payload to R12 220 by means of the prefix SID 220 (for example, S595 shown in Fig. 6) .

In this way, each of the three areas may use the whole SRGB range without disturbing the other area.

As described in the above embodiments, the above-mentioned mechanism can be implemented at one or more ABRs in an OSPF network. However, the present disclosure is not limited thereto. In other words, this mechanism can be implemented at one or more IRs or any other node in any SR network. Fig. 7 shows a scenario in which the mechanism is not implemented at the ABR R2 300 but implemented at the IR R21 310.

As shown in Fig 7 which has a configuration similar to that of Fig. 5, since the tuple (310, 2009) which represents the IR R12 220 is propagated to the source router R22 320 from R21 310, the source router R22 320 may use this tuple to forward any traffic destined to R12 220 to the IR R21 310. As shown by the mapping from (310, 2009) to (200, 2001) on the bottom right of Fig. 7, the R21 310 may determine the prefix SID 200 of the ABR R1 200 for the packet and transmit the packet to the ABR R1 200. In this way, even if the above mechanism is not implemented at the ABR R2 300, the IR R21 310 may still provide the same function. In other words, a router (ABR or IR) with the above mechanism can operate in a network no matter whether other routers in the network support the mechanism or not.

Further, please also note that R22 320 may also receive another SID advertisement for R12 220 via another advertisement path, for example, a path comprising the node R23 330 rather than the node R21 310. In this case, R22 320 may determine the route for the packet as usual, for example, by calculating costs associated with different routes based on the SPF algorithm. In this case, the above mechanism may still operate since R22 320 may use the tuple (310, 2009) if the path comprising R21 310 is chosen and the tuple (200, 2001 ) if a path which does not comprise R21 310 is chosen.

As mentioned above, when using the above mechanism, another advantage is that a deeper SID stack can be expressed with fewer labels because there is a chance at an ABR to switch a deep SID stack to less SIDs by using the mechanism, and also because an ABR (R1 200 in the embodiment of Fig. 5 for example) has more topological knowledge on its connected areas and it can calculate a better path than the ingress router (R22 320 in the embodiment of Fig. 5 for example) .

Fig. 8 shows an example use case for constraint-based-path in segment routing. The bottom portion of Fig. 8 shows the traffic flow without the above mechanism, and the top portion shows the traffic flow using the above mechanism. Supposing R03 130 in Area0 10 and R13 230 in Area1 20 are in the shortest path to R12 220, but they cannot be used due to security reasons. Therefore, a possible designated path may be

R22-＞R21-＞R2-＞R02-＞R01-＞R1-＞R11-＞R12.

● Without the above mechanism, the ingress router R22 may need to encode the whole segment path into the SID stack of the packet, and therefore the SID stack may be (310, 300, 120, 110, 200, 210, 220) , 7 labels in total.

● With the above mechanism, the ingress-router R22 320 and ABRs along the path (for example, R1 200 and R2 300) may just encode the path in upcoming area, and the SID-tuples at the ABRs may joint multiple segment-routing-paths together as an end-to-end path. R22 320 may encode the path in Area2 30 to ABR R2 300, namely (310, 300, 2003) ; R2 300 may encode the path in Area0 10 to ABR R1 200, namely (120, 110, 200, 2001) ; and R1 200 may encode the path in Area1 20 to R12, namely (210, 220) . The deepest stack along the path has 4 SIDs in total. Therefore, the max SID stack depth along the path decreases from 7 to 4 by using the above mechanism.

However, to support such a designated path, an ABR along the path shall be able to be configured, by a third party, for example, an SDN controller (for example, a Path Computation Element (PCE) as shown in Fig. 9) , with the translation/mapping between a local SID and a prefix SID.

Fig. 9 is a diagram showing a network comprising three areas, Area0 10, Area1 20, and Area2 30, and PCE based

controllers

40, 50, 60, and 70 according to an embodiment of the present disclosure.

As shown in Fig. 9, in addition to the segment-routing path derived from the IGP shortest path and/or explicit configuration, the routing information can also be calculated by a Path Computation Element (PCE) for traffic engineering purpose in an SDN network.

When using the above mechanism, a PCE-based controller would be responsible for each area, including the prefix and adjacency SID allocations for the internal routers. For example, the PCE-based

controllers

40, 50, and 60 may control the SID allocations for the internal routers in Area0 10, Area1 20, and Area2 30, respectively., and may interact with ABRs R1 and/or R2 to establish the mapping of the intra-area segment path to the (ABR node SID, ABR local SID) tuple. The node SIDs of the ABR routers are globally unique and therefore may be allocated by the parent controller 70 which is responsible for the whole domain.

In some embodiments, when setting up an end-to-end inter-area segment-routing path, the parent controller 70 may calculate according to the bandwidth capacity, congestion and/or capability of the network nodes, and then delegate area segment paths to the ABRs along the path, respectively. As a result, the ingress node only needs to know the (ABR node SID, ABR local SID) tuple in its own area to the destination.

In an embodiment, assuming that R22 320 tries to send some traffic to R12 220. First, R22 320 may initiate a destination resolution request to the parent controller 70, for example, via the PCE-based controller-2 60, to request the parent controller to determine a routing path for the traffic. Based on various factors, such as load, QoS, bandwidth, security, billing &charging, etc., the parent controller may determine a full path from R22 320 to R12 220. Alternatively, the parent controller 70 may determine some nodes, for example, the ABR R1 200 and the ABR R2 300, rather than the full path, and then request each of PCE-based

controllers

40, 50, and/or 60 to determine a portion of the full path in their associated areas, respectively. Further, in some other embodiments, the parent controller 70 may determine the portion of the path for some areas, but not the portion of the path for the rest areas. For example, the parent controller 70 may determine the portion of the full path for Area0 10 and Area1 20, but not the portion for Area2 30, and leave the portion for the PCE-based controller-2 60.

No matter which one of the above options is used, the PCE-based

controllers

40, 50, 60 may aware of the portions of the full path in their own areas, respectively, and they may issue route setting requests to respective ABRs, for example, R1 200 and/or R2 300, to set up a route from R22 320 to R12 220. For example, in some embodiments, the PCE-based controller-1 50 may issue a route setting request to R1 200 and notify R1 200 of the portion of the full path in Area1 20, for example, “R1-＞R11-＞R12” , and therefore R1 200 may update its mapping table accordingly.

Similarly, the PCE-based controller-1 40 may issue a route setting request to R2 300 and notify R2 300 of the portion of the full path in Area0 10, for example, “R2-＞R02-＞R01-＞R1” , and therefore R2 300 may update its mapping table accordingly. In this case, however, R2 may further require a local SID at R1 200 to establish the mapping relation between the local SID and the portion of the path in Area1 20. In the embodiment shown in Fig. 8, the local SID at R1 200 is “2001” , which is allocated by R1 200. In this case, R1 200 notifies R2 300 of such a local SID before the mapping at R2 300 is established, via a PCE-based controller or not. However, in some other embodiments, such an SID may be allocated by any of the PCE-based

controllers

40, 50, 60, and 70, and the uniqueness is ensured by one of the PCE-based

controllers

40, 50, 60, and 70 which allocated the local SID. No matter which method is used, R2 300 now can set up its own mapping from the local SID at R2 300 (for example, 2003 in Fig. 8) to labels (for example, (120, 110, 200, 2001) in Fig. 8) .

The PCE-based controller-2 60 or R2 300 or any other entity that is in charge may finally notify R22 320 of the portion of the path in Area2, for example, (310, 300, 2003) shown in Fig. 8, and now R22 320 is able to transmit the traffic to R12 220 by pushing (310, 300, 2003) into the label stack of packets of the traffic.

In this way, an end-to-end inter-area segment routing path can be established without a full label stack is established at the very beginning and therefore the depth of the label stack can be reduced significantly.

In some embodiments of the present disclosure, a mechanism to set up end-to-end inter-area segment routing path is proposed. ABRs are enhanced to operate as a shield and translator for intra-area node SIDs, and they may translate the intra-area node prefix SID to a tuple (ABR node SID, local SID) when propagating the prefix SID outside of an area. This new SID tuple may hide the intra-area prefix SID from routers in other areas, and an area can use the whole SRGB. Thus more segment routers can be supported in an OSPF domain. Further, the SID administration becomes easier since the SID conflict domain becomes smaller. Meanwhile, this SID tuple may work as a glue, connecting the segment routing path from outside router to an ABR and the path from the ABR to the IR, which is very important to MPLS VPN provider network.

Also, when using the above mechanism, the ABR gets a chance to encode the segment path in the downstream area to which it is connected. Then the SID stack depth may be reduced greatly when a constraint-based path calculation algorithm is used, with which a longer path can be expressed with certain hardware label stack depth limit. In addition, because an ABR may have more knowledge of the area topology than a router outside of the area, a better intra-area path may be selected automatically by the ABR.

Fig. 10 schematically shows an embodiment of an arrangement 1000 which may be used in a network element according to an embodiment of the present disclosure.

Comprised in the arrangement 1000 are a processing unit 1006, e.g., with a Digital Signal Processor (DSP) or a Central Processing Unit (CPU) . The processing unit 1006 may be a single unit or a plurality of units to perform different actions of procedures described herein. The arrangement 1000 may also comprise an input unit 1002 for receiving signals from other entities, and an output unit 1004 for providing signal (s) to other entities. The input unit 1002 and the output unit 1004 may be arranged as an integrated entity or as separate entities.

Furthermore, the arrangement 1000 may comprise at least one computer program product 1008 in the form of a non-volatile or volatile memory, e.g., an Electrically Erasable Programmable Read-Only Memory (EEPROM) , a flash memory and/or a hard drive. The computer program product 1008 comprises a computer program 1010, which comprises code/computer readable instructions, which when executed by the processing unit 1006 in the arrangement 1000 causes the arrangement 1000 and/or the network element in which it is comprised to perform the actions, e.g., of the procedure described earlier in conjunction with Figs. 2, 4 and/or 6 or any other variant.

The computer program 1010 may be configured as a computer program code structured in computer program modules 1010A-1010C. Hence, in an exemplifying embodiment when the arrangement 1000 is used in the network element, the code in the computer program of the arrangement 1000 includes: a reception module 1010A for receiving, from a first node, data to be routed and a first indicator, the first indicator being unique to the network element. The code in the computer program further includes a determination module 1010B for determining, based on the first indicator, a second indicator, the second indicator indicating a routing segment destined to a second node. The code in the computer program further includes a transmission module 1010C for transmitting, via the routing segment corresponding to the second indicator, the data to be routed.

The computer program modules could essentially perform the actions of the flow illustrated in Figs. 2, 4, and/or 6, to emulate the network element. In other words, when the different computer program modules are executed in the processing unit 1006, they may correspond to different modules in the network element.

Although the code means in the embodiments disclosed above in conjunction with Fig. 10 are implemented as computer program modules which when executed in the processing unit causes the arrangement to perform the actions described above in conjunction with the figures mentioned above, at least one of the code means may in alternative embodiments be implemented at least partly as hardware circuits.

The processor may be a single CPU (Central processing unit) , but could also comprise two or more processing units. For example, the processor may include general purpose microprocessors; instruction set processors and/or related chips sets and/or special purpose microprocessors such as Application Specific Integrated Circuit (ASICs) . The processor may also comprise board memory for caching purposes. The computer program may be carried by a computer program product connected to the processor. The computer program product may comprise a computer readable medium on which the computer program is stored. For example, the computer program product may be a flash memory, a Random-access memory (RAM) , a Read-Only Memory (ROM) , or an EEPROM, and the computer program modules described above could in alternative embodiments be distributed on different computer program products in the form of memories within the UE.

The present disclosure is described above with reference to the embodiments thereof. However, those embodiments are provided just for illustrative purpose, rather than limiting the present disclosure. The scope of the disclosure is defined by the attached claims as well as equivalents thereof. Those skilled in the art can make various alternations and modifications without departing from the scope of the disclosure, which all fall into the scope of the disclosure.

Claims

A method at a network element of routing data, the method comprising:

receiving, from a first node, data to be routed and a first indicator, the first indicator being unique to the network element;

determining, based on the first indicator, a second indicator, the second indicator indicating a routing segment destined to a second node; and

transmitting, via the routing segment corresponding to the second indicator, the data to be routed.
The method according to claim 1, wherein the determination of the second indicator comprising:

determining, based on the first indicator, one or more indicators comprising the second indicator, the one or more indicators indicating one or more routing segments, respectively, which form a route from the network element to the second node.
The method according to claim 2, wherein the second indicator indicates a routing segment which associated with the next hop for the network element in the route.
The method according to claim 1, further comprising:

determining, based on the first indicator, a third indicator which is unique to the second node and enables the second node to determine one or more routing segments for the data; and

transmitting, via the routing segment corresponding to the second indicator, the third indicator.
The method according to claim 3 or 4, wherein the determination of the one or more indicators comprises: looking the first indicator up in a forwarding table maintained by the network element to determine the one or more indicators, and/or

wherein the determination of the third indicator comprises: looking the first indicator up in the forwarding table maintained by the network element to determine the third indicator.
The method according to claim 5, further comprising:

receiving, from the first node, a fourth indicator, the fourth indicator indicates a routing segment destined to the network element.
The method according to claim 6, wherein before the reception of the data to be routed and the first indicator, the method further comprises:

receiving, from the second node, the one or more indicators indicating one or more routing segments, respectively, which form a route from the network element to the second node;

updating the forwarding table by storing the one or more indicators into the forwarding table in association with the first indicator; and

advertising, to the first node, the fourth indicator and the first indicator on behalf of the second node.
The method according to claim 7, wherein before the reception of the data to be routed and the first indicator, the method further comprises:

receiving, from the second node, the third indicator which is unique to the second node and enables the second node to determine one or more routing segments for the data; and

updating the forwarding table by storing the third indicator into the forwarding table in association with the first indicator.
The method according to claim 1, further comprising:

receiving, from a third node, a route setting request to set up a route from the network element to a fourth node; and

updating the forwarding table based on the route setting request.
The method according to claim 9, wherein the route setting request comprises a fifth indicator which is unique to the network element and one or more six indicators indicating one or more routing segments, respectively, which form a route from the network element to the fourth node, and the updating of the forwarding table comprises:

storing the one or more six indicators into the forwarding table in association with the fifth indicator.
The method according to claim 10, wherein the route setting request further comprises a seventh indicator which is unique to the fourth node, and the updating of the forwarding table further comprises:

storing the seventh indicators into the forwarding table in association with the fifth indicator.
The method according to any of claims 1-11, wherein each of the indicators is a Multiple Protocol Label Switching (MPLS) label.
The method according to any of claims 1-12, wherein the network element is an Area Border Router (ABR) coupled to a first area and a second area, and the first node belongs to the first area and the second node belongs to the second area.
The method according to any of claims 9-11, wherein the third node is a Software Defined Network (SDN) controller.
A network element comprising:

a processor; and

a memory storing instructions which, when executed by the processor, cause the processor to perform any of the methods of Claims 1-14.
A non-transitory computer readable storage medium having instructions stored thereon, which, when executed by a processor, cause the processor to perform any of the methods of Claims 1-14.