Scalable segment identifier allocation in segment routing

Patent metadata

Field	Value
Publication number	US-9516118-B2
Application number	US-201414275007-A
Country	US
Kind code	B2
Filing date	May 12, 2014
Priority date	May 12, 2014
Publication date	Dec 6, 2016
Grant date	Dec 6, 2016

Abstract

Exemplary methods for allocating multiple local sub-blocks (LsBs) of segment identifiers (IDs) include allocating a first set of LsBs, each LsB associated with a start index and a range, wherein the start index indicates a starting SID of a corresponding LsB and the range indicates a total number of SIDs included in the corresponding LsB, each LsB identified by a sub-block number. In one embodiment, the methods include mapping a plurality of segment routing global block (SRGB) indexes to a plurality of corresponding SIDs of the first set of LsBs, the mapping performed based on the SRGB indexes, start indexes of each LsB, and ranges of SIDs of each LsB. In one embodiment, the methods include advertising the first set of LsBs by transmitting a first advertisement message that includes the start indexes, ranges of SIDs, and sub-block numbers of all LsBs of the first set of LsBs.

First claim

What is claimed is:

1. A method in a first network device that is communicatively coupled to a plurality of segment routing (SR) devices in a SR network, the method comprising:
allocating a first set of local sub-blocks (LsBs) of segment identifiers (SIDs), each LsB associated with a start index and a range of SIDs, wherein the start index indicates a starting SID of a corresponding LsB and the range of SIDs indicates a total number of SIDs included in the corresponding LsB, wherein each LsB is identified by a sub-block number;
mapping a plurality of segment routing global block (SRGB) indexes to a plurality of corresponding SIDs of the first set of LsBs, wherein the mapping is performed based on the SRGB indexes, start indexes of each LsB, and ranges of SIDs of each LsB;
advertising the first set of LsBs to the plurality of SR devices by transmitting a first advertisement message that includes the start indexes, ranges of SIDs, and sub-block numbers of all LsBs of the first set of LsBs;
determining whether an SRGB range exceeds a combined range of SIDs of all LsBs of the first set of LsBs;
allocating a new LsB in response to a determination that the SRGB range exceeds the combined range of SIDs of all LsBs of the first set of LsBs; and
advertising a second set of LsBs by transmitting a second advertisement message that includes start indexes, ranges of SIDs, and sub-block numbers of all LsBs of the first set of LsBs and the new LsB.

2. The method of claim 1 , wherein mapping the plurality of indexes of the SRGB to the plurality of corresponding SIDs of the first set of LsBs comprises:
determining a range of SIDs of a first LsB is less than an SRGB index;
determining a combined range of SIDs of the first LsB and a second LsB by adding a range of SIDs of the first LsB and a range of SIDs of the second LsB; and
in response to determining the combined range of SIDs of the first LsB and the second LsB is greater than the SRGB index:
determining a difference by subtracting the range of the first LsB from the SRGB index,
determining a sum by adding the difference to a start index of the second LsB, and
mapping the SRGB index to the sum.

3. The method of claim 1 , further comprising in response to determining a combined range of SIDs of all LsBs of the first set of LsBs exceeds a desired reduced SRGB range, decreasing the combined range of SIDs of the first set of LsBs by de-allocating an SID of an LsB having a highest sub-block number among all the LsBs of the first set of LsBs.

4. The method of claim 3 , wherein de-allocating the SID comprises:
determining a prefix is associated with a current SID which exceeds the desired reduced SRGB range;
advertising a new SID for the prefix by transmitting a second advertisement message that includes the new SID and a no-ingress flag set to a Boolean true value, wherein the no-ingress flag with the Boolean true value causes one or more of the plurality of SR devices to set up an entry in an incoming label map (ILM) table for the new SID, without setting up an entry in a forwarding equivalence class (FEC) to next hop (FTN) table for the new SID;
advertising the new SID for the prefix by transmitting a third advertisement message that includes the new SID and a no-ingress flag set to a Boolean false value, wherein the no-ingress flag with the Boolean false value causes one or more of the plurality of SR devices to set up an entry in the FTN table corresponding to the new SID;
advertising the current SID by transmitting a fourth advertisement message that includes the current SID and a no-ingress flag set to a Boolean true value, wherein the no-ingress flag with the Boolean true value causes one or more of the plurality of SR devices to remove an entry from the FTN table corresponding to the current SID; and
de-allocating the current SID.

5. The method of claim 1 , further comprising decreasing a number of LsBs of the first set of LsBs by merging a source LsB of the first set of LsBs with a target LsB of the first set of LsBs, by:
advertising a shift LsB (SLsB) by transmitting a second advertisement message that includes a start index of the SLsB, a start index of the source LsB, a start index of the target LsB, a range of SIDs of the SLsB, a range of SIDs of the source LsB, a range of SIDs of the target LsB, and a use-range flag set to a Boolean false value, wherein the use-range flag with the Boolean false value causes one or more of the plurality of SR devices to perform SRGB index to SID mapping using the start indexes of the source LsB and the target LsB, and the ranges of SIDs of the source LsB and the target LsB, instead of performing SRGB index to SID mapping using the start index and range of SIDs of the shift LsB.

6. The method of claim 5 , wherein decreasing the number of LsBs of the first set of LsBs further comprises:
advertising a shift SID for a prefix by transmitting a third advertisement message that includes the shift SID and a do-not-use flag set to a Boolean true value, wherein the shift SID is an SID within a range of SIDs of the SLsB, wherein the do-not-use flag with the Boolean true value causes one or more of the plurality of SR devices to set up an entry in an incoming label map (ILM) table for the shift SID, without setting up an entry in a forwarding equivalence class (FEC) to next hop (FTN) table for the shift SID; and
advertising the shift SID for the prefix by transmitting a fourth advertisement message that includes the shift SID and a do-not-use flag set to a Boolean false value, wherein the do-not-use flag with the Boolean false value causes one or more of the plurality of SR devices to set up an entry in the FTN table for the shift SID.

7. The method of claim 6 , wherein decreasing the number of LsBs of the first set of LsBs further comprises:
advertising a source SID for the prefix by transmitting a fifth advertisement message that includes the source SID and a do-not-use flag set to a Boolean true value, wherein the source SID is an SID within a range of the source LsB, wherein the do-not-use flag with the Boolean true value causes one or more of the plurality of SR devices to remove an entry in the FTN table associated with the source SID; and
advertising the SLsB by transmitting a sixth advertisement message that includes the start index of the SLsB, the start index of the source LsB, the start index of the target LsB, the range of SIDs of the SLsB, the range of SIDs of the source LsB, the range of SIDs of the target LsB, and a use-range flag set to a Boolean true value, wherein the use-range flag with the Boolean true value causes one or more of the plurality of SR devices to perform SRGB index to SID mapping using the start index and range of SIDs of the shift LsB.

8. The method of claim 7 , wherein decreasing the number of LsBs of the first set of LsBs further comprises:
advertising the SLsB by transmitting a seventh advertisement message that includes the start index of the SLsB, the start index of the source LsB, the start index of the target LsB, the range of SIDs of the SLsB, the range of SIDs of the source LsB, the range of SIDs of the target LsB, and a use-range flag set to a Boolean false value, wherein the use-range flag with the Boolean false value causes one or more of the plurality of SR devices to perform SRGB index to SID mapping using the start indexes of the source LsB and the target LsB, and the ranges of SIDs of the source LsB and the target LsB, instead of performing SRGB index to SID mapping using the start index and range of SIDs of the shift LsB.

9. A first network device that is communicatively coupled to a plurality of segment routing (SR) devices in a SR network, the first network device comprising:
a set of one or more pro

Assignees

• Ericsson Telefon Ab L M

Inventors

• Kini Sriganesh
• Varga Balazs

Classifications

• H04L45/507

  Label distribution · CPC title

• H04L45/38 Primary

  Flow based routing · CPC title

• H04L45/34

  Source routing · CPC title

• H04L45/24

  Multipath · CPC title

• H04L43/10

  Active monitoring, e.g. heartbeat, ping or trace-route · CPC title