# US 2012/0250696 A1 · Soft Preemption For Minimizing Preemptions In A Network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0250696 A1
- Document ID: US20120250696A1
- Status: Published application
- Kind: A1
- Application number: 13/077,352
- Filed: 2011-03-31
- Published: 2012-10-04
- Earliest claimed: 2011-03-31
- Assignees: Cisco Technology, Inc.
- Inventors: Rakesh Gandhi; Robert Sawaya; Tarek Saad; Junaid Israr
- Web page: https://patentgrep.com/patent/US20120250696A1

## CPC

- H04L 45/50: using label swapping, e.g. multi-protocol label switch [MPLS]
- H04L 47/245: {using preemption}
- H04L 47/724: at intermediate nodes, e.g. resource reservation protocol [RSVP]
- H04L 47/805: {QOS or priority aware}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

In an embodiment, a method is disclosed for minimizing soft preemptions of LSPs. Upon receiving a reservation message for an LSP whose requested bandwidth that exceeds the available bandwidth of downstream links, a network node may select a set of LSPs for soft preemption and share the selection with other nodes along their paths, both upstream and downstream. By coordinating the selection of LSPs to soft-preempt among nodes on the path, fewer LSPs may require soft preemption, which may result in minimizing excessive network disruptions, and thus, allowing the network to function more efficiently.

## Claims

### Claim 1

A method, comprising:
receiving, at a first network node, a resource reservation message specifying a first label switched path (LSP), a first priority value, and a first minimum required bandwidth value associated with the first LSP;
determining, at the first network node, that a sum of the first minimum required bandwidth value and a second minimum required bandwidth associated with a previously received, second LSP exceeds an available bandwidth of a first link of the first network node to a second network node;
determining whether the first priority value indicates that the first LSP has a higher priority than the second LSP;
in response to determining that the first LSP has a higher priority than the second LSP, marking the second LSP as being soft-preempted and refraining from reserving bandwidth for the second LSP on the first link;
sending an error message to a third network node specifying that the second LSP is being soft-preempted at the first link of the first node, wherein the third network node is upstream of the first network node and the second network node, and wherein the third network node is not an origin of the second LSP.

### Claim 2 (depends on 1)

The method of claim 1, further comprising the third network node marking the second LSP as soft-preempted.

### Claim 3 (depends on 1)

The method of claim 1, further comprising sending a message to a fourth network node specifying that the second LSP is soft-preempted, wherein the fourth network node is downstream of the first network node and the second network node.

### Claim 4 (depends on 3)

The method of claim 3, further comprising the fourth network node marking the second LSP as soft-preempted.

### Claim 5 (depends on 4)

The method of claim 4, further comprising:
in response to receiving at the fourth network node, the resource reservation message specifying a fourth LSP, a fourth priority value, and a fourth minimum required bandwidth value associated with the fourth LSP, determining whether any LSP, of a set of LSP's for which traffic is carried over the fourth link, must be preempted;
in response to determining that at least one LSP that is carried over the second link must be soft-preempted, selecting a fifth LSP for soft preemption, wherein the fifth LSP is one of the second LSP or another LSP that is already marked for soft preemption;
sending an error message to a second network node specifying that the fifth LSP is soft-preempted, wherein the second network node is upstream of the fourth network node.

### Claim 6 (depends on 3)

The method of claim 3 wherein the message to the fourth network node is an RSVP new path change message.

### Claim 7 (depends on 1)

The method of claim 1, further comprising determining whether any LSP, of one or more LSP's previously assigned to the first link, must be preempted by determining that a sum of the first minimum required bandwidth value and each minimum required bandwidth value associated with each LSP of the one or more LSP's previously assigned to the first link exceeds the available bandwidth of the first link of the first network node to the second network node.

### Claim 8 (depends on 7)

The method of claim 7, wherein determining whether an LSP, of the one or more LSP's previously assigned to the first link, must be soft-preempted comprises determining that the first LSP has higher priority than at least one of the LSP's.

### Claim 9 (depends on 1)

The method of claim 1, wherein the first LSP has higher priority than the second LSP when the first priority value is less than a second priority value associated with the second LSP, and the first LSP has lower priority than the second LSP when the first priority value is greater than the second priority value.

### Claim 10 (depends on 1)

The method of claim 1, further comprising:
the third network node receiving the error message specifying that the second LSP is soft-preempted, wherein the third network node sends traffic for the second LSP over a second link;
the third network node marking the second LSP as being soft-preempted by a downstream node;
in response to receiving at the third network node, the resource reservation message specifying a first label switched path (LSP), the first priority value, and the first minimum required bandwidth value associated with the first LSP, determining whether any LSP, of a set of LSP's for which traffic is carried over the second link, must be soft-preempted;
the third network node forwarding the path error message upstream;
in response to determining that at least one LSP that is carried over the second link must be preempted, selecting a third LSP for soft preemption, wherein the third LSP is one of the second LSP or another LSP that is already marked for soft preemption;
sending an error message to a fifth network node specifying that the third LSP is soft-preempted, wherein the fifth network node is upstream of the third network node.

### Claim 11 (depends on 1)

The method of claim 1 wherein each of the messages conforms to resource reservation protocol (RSVP).

### Claim 12

An apparatus, comprising:
a network interface that is coupled to the data network for receiving one or more packet flows therefrom;
a processor;
one or more stored sequences of instructions which, when executed by the processor, cause the processor to perform:
receiving, at a first network node, a resource reservation message specifying a first label switched path (LSP), a first priority value, and a first minimum required bandwidth value associated with the first LSP;
determining, at the first network node, that a sum of the first minimum required bandwidth value and a second minimum required bandwidth associated with a previously received, second LSP exceeds an available bandwidth of a first link of the first network node to a second network node;
determining whether the first priority value indicates that the first LSP has a higher priority than the second LSP;
in response to determining that the first LSP has a higher priority than the second LSP, marking the second LSP as soft-preempted and refraining from reserving bandwidth for the second LSP;
sending an error message to a third network node specifying that the second LSP is soft-preempted, wherein the third network node is upstream of the first network node and the second network node, and wherein the third network node is not an origin of the second LSP.

### Claim 13 (depends on 9)

The apparatus of claim 9, further comprising sequences of instructions which, when executed by the processor, cause the processor to perform:
sending a message to a fourth network node specifying that the second LSP is soft-preempted, wherein the fourth network node is downstream of the first network node and the second network node.

### Claim 14 (depends on 9)

The apparatus of claim 9, further comprising sequences of instructions which, when executed by the processor, cause the processor to perform:
determining whether any LSP, of one or more LSP's previously assigned to the first link, must be preempted by determining that a sum of the first minimum required bandwidth value and each minimum required bandwidth value associated with each LSP of the one or more LSP's previously assigned to the first link exceeds the available bandwidth of the first link of the first network node to the second network node.

### Claim 15 (depends on 11)

The apparatus of claim 11, wherein determining whether an LSP, of the one or more LSP's previously assigned to the first link, must be preempted comprises determining that the first LSP has higher priority than at least one of the LSP's.

### Claim 16 (depends on 9)

The apparatus of claim 9, further comprising sequences of instructions which, when executed by the processor, cause the processor to perform:
the third network node receiving the error message specifying that the second LSP is soft-preempted, wherein the third network node sends traffic for the second LSP over a second link;
the third network node marking the second LSP as being soft-preempted by a downstream node;
in response to receiving at the third network node, the resource reservation message specifying a first label switched path (LSP), the first priority value, and the first minimum required bandwidth value associated with the first LSP, determining whether any LSP, of a set of LSP's for which traffic is carried over the second link, must be soft-preempted;
the third network node forwarding the path error message upstream;
in response to determining that at least one LSP that is carried over the second link must be preempted, selecting a third LSP for soft preemption, wherein the third LSP is one of the second LSP or another LSP that is already marked for soft preemption;
sending an error message to a fifth network node specifying that the third LSP is soft-preempted, wherein the fifth network node is upstream of the third network node.

### Claim 17

A non-transitory computer-readable storage medium storing one or more sequences of instructions, which when executed cause one or more processors to perform:
receiving, at a first network node, a resource reservation message specifying a first label switched path (LSP), a first priority value, and a first minimum required bandwidth value associated with the first LSP;
determining, at the first network node, that a sum of the first minimum required bandwidth value and a second minimum required bandwidth associated with a previously received, second LSP exceeds an available bandwidth of a first link of the first network node to a second network node;
determining whether the first priority value indicates that the first LSP has a higher priority than the second LSP;
in response to determining that the first LSP has a higher priority than the second LSP, marking the second LSP as preempted and refraining from reserving bandwidth for the second LSP;
sending an error message to a third network node specifying that the second LSP is soft-preempted, wherein the third network node is upstream of the first network node and the second network node, and wherein the third network node is not an origin of the second LSP.

### Claim 18 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, further comprising instructions, which when executed, cause the one or more processors to perform:
sending a message to a fourth network node specifying that the second LSP is soft-preempted, wherein the fourth network node is downstream of the first network node and the second network node.

### Claim 19 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, further comprising instructions, which when executed, cause the one or more processors to perform:
determining whether any LSP, of one or more LSP's previously assigned to the first link, must be preempted by determining that a sum of the first minimum required bandwidth value and each minimum required bandwidth value associated with each LSP of the one or more LSP's previously assigned to the first link exceeds the available bandwidth of the first link of the first network node to the second network node.

### Claim 20 (depends on 16)

The non-transitory computer-readable storage medium of claim 16, wherein determining whether an LSP, of the one or more LSP's previously assigned to the first link, must be preempted comprises determining that the first LSP has higher priority than at least one of the LSP's.

### Claim 21 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, further comprising instructions, which when executed, cause the one or more processors to perform:
the third network node receiving the error message specifying that the second LSP is soft-preempted, wherein the third network node sends traffic for the second LSP over a second link;
the third network node marking the second LSP as soft-preempted;
in response to receiving at the third network node, the resource reservation message specifying a first label switched path (LSP), the first priority value, and the first minimum required bandwidth value associated with the first LSP, determining whether any LSP, of a set of LSP's for which traffic is carried over the second link, must be preempted;
in response to determining that at least one LSP that is carried over the second link must be preempted, selecting a third LSP for soft preemption, wherein the third LSP is one of the second LSP or another LSP that is already marked for soft preemption;
sending an error message to a fifth network node specifying that the third LSP is soft-preempted, wherein the fifth network node is upstream of the third network node;
forwarding the error message specifying that the second LSP is soft-preempted to the fifth network node.
