Mechanism to improve preemption behavior of resource reservations

• US 20060056291A1
• Filed: 09/10/2004
• Published: 03/16/2006
• Est. Priority Date: 09/10/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Oran, David R., Davie, Bruce S., Baker, Frederick, Levesque, Roger, Iturralde, Carol, DiBiasio, Michael V.
• Granted Patent: US 7,953,000 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks

Abstract

A technique is provided for one or more network nodes to deterministically select data flows to preempt. In particular, each node employs a set of predefined rules which instructs the node as to which existing data flow should be preempted in order to admit a new high-priority data flow. The rules are precisely defined and are common to all nodes configured in accordance with the present invention. Illustratively, a network node not only selects a data flow to preempt, but additionally may identify other “fate sharing” data flows that may be preempted. As used herein, a group of data flows has a fate-sharing relationship if the application instance(s) containing the data flows functions adequately only when all the fate-shared flows are operational. In a first illustrative embodiment, after a data flow in a fate-sharing group is preempted, network nodes may safely tear down the group'"'"'s remaining data flows. In a second illustrative embodiment, when a data flow is preempted, all its fate-shared data flows are marked as being “at risk.” Because the at-risk flows are not immediately torn down, it is less likely that resources allocated for the at-risk flows may be freed then subsequently used to establish relatively lower-priority data flows instead of relatively higher-priority data flows.

Claims

1. A method for a network node in a computer network to allocate network resources for a new data flow, the method comprising:

receiving a request to reserve network resources for the new data flow;

determining whether the requested network resources are available;

if the requested resources are determined to be unavailable, performing the steps of;

(i) selecting an existing data flow to preempt based on a predefined set of rules, the predefined set of rules being common to a plurality of nodes in the computer network;

(ii) preempting the selected data flow, thereby freeing network resources previously reserved for the selected data flow; and

(iii) reallocating the freed network resources for the new data flow.

2. The method of claim 1, further comprising:

allocating the requested resources to the new data flow if the requested resources are determined to be available.

3. The method of claim 1, further comprising:

determining whether the selected data flow participates in a fate-sharing group of data flows, where utility of data flows in the fate-sharing group depends on all data flows in the fate-sharing group being operational; and

if the selected data flow is determined to participate in a fate-sharing group of data flows, preempting every data flow in the fate-sharing group.

4. The method of claim 3, wherein the step of determining whether the selected data flow participates in a fate-sharing group further comprises:

locating a fate-sharing identifier associated with the selected data flow, the fate-sharing identifier corresponding to the fate-sharing group.

5. The method of claim 4, wherein the fate-sharing identifier is a universal unique identifier (UUID).

6. The method of claim 1, further comprising:

determining whether the selected data flow participates in a fate-sharing group of data flows, where utility of data flows in the fate-sharing group depends on all data flows in the fate-sharing group being operational; and

if the selected data flow is determined to participate in a fate-sharing group of data flows, identifying every data flow in the fate-sharing group as being “

at risk”

of being preempted.

7. The method of claim 6, wherein the step of determining whether the selected data flow participates in a fate-sharing group further comprises:

locating a fate-sharing identifier associated with the selected data flow, the fate-sharing identifier corresponding to the fate-sharing group.

8. The method of claim 7, wherein the fate-sharing identifier is a universal unique identifier (UUID).

9. The method of claim 1, further comprising:

forwarding the received request to an upstream network node in the computer network.

10. The method of claim 1, wherein the request is a RSVP Reservation (Resv) message.

11. The method of claim 1, wherein the network node is an intermediate network node.

12. The method of claim 1, wherein the request is generated in the network node.

13. The method of claim 1, wherein the selected data flow is associated with a lower defending-priority value than a preemption-priority value associated with the new data flow.

14. The method of claim 1, further comprising:

dropping the received request if a preemption-priority value associated with the new data flow is less than or equal to defending-priority values of all existing data flows; and

transmitting an error message to the network node'"'"'s neighboring downstream node to inform the neighboring node that the requested network resources could not be allocated.

15. A method for a network node in a computer network to allocate network resources for a new data flow, the method comprising:

receiving a request to reserve network resources for the new data flow;

determining whether the requested network resources are available;

if the requested resources are determined to be unavailable, performing the steps of;

(i) selecting an existing “

at-risk”

data flow to preempt, the at-risk data flow participating in a fate-sharing group of data flows where at least one data flow in the fate-sharing group has already been preempted;

(ii) preempting the selected at-risk data flow, thereby freeing network resources previously reserved for the selected at-risk data flow; and

(iii) reallocating the freed network resources for the new data flow.

16. The method of claim 15, wherein the step of selecting an existing at-risk data flow to preempt further comprises:

determining whether the new data flow participates in a fate-sharing group of data flows;

if the new data flow is determined to participate in a fate-sharing group of data flows, locating an existing at-risk data flow that was placed at risk by a preempting data flow participating in the same fate-sharing group as the new data flow; and

selecting the located at-risk data flow to preempt.

17. The method of claim 16, wherein the step of locating an existing at-risk data flow further comprises:

for each at-risk data flow, associating a fate-sharing identifier of a preempting data flow that placed the at-risk data flow at risk;

comparing a fate-sharing identifier associated with the new data flow with the fate-sharing identifiers associated with the preempting data flows; and

locating an existing at-risk data flow having a fate-sharing identifier associated with a preempting data flow which is equal to the fate-sharing identifier associated with the new data flow.

18. The method of claim 17, wherein each fate-sharing identifier is a universal unique identifier (UUID).

19. The method of claim 15, wherein the step of selecting an existing at-risk data flow further comprises:

for each at-risk data flow, associating a preemption-priority value of a preempting data flow that placed the at-risk data flow at risk;

comparing a preemption-priority value associated with the new data flow with the preemption-priority values associated with the preempting data flows;

locating an existing at-risk data flow having a preemption-priority value associated with a preempting data flow which is less than the preemption-priority value associated with the new data flow; and

selecting the located at-risk data flow to preempt.

20. The method of claim 15, further comprising:

if an existing at-risk data flow can not be found, performing the steps of;

selecting an existing data flow to preempt based on a predefined set of rules, the selected data flow not being identified as an at-risk data flow;

preempting the selected data flow, thereby freeing network resources previously reserved for the selected data flow; and

reallocating the freed network resources for the new data flow.

21. The method of claim 15, further comprising:

forwarding the received request to an upstream network node in the computer network.

22. The method of claim 15, wherein the request is a RSVP Reservation (Resv) message.

23. The method of claim 15, wherein the network node is an intermediate network node.

24. The method of claim 15, wherein the request is generated in the network node.

25. A network node configured to allocate network resources for a new data flow, the network node comprising:

means for selecting an existing data flow to preempt based on a predefined set of rules, the predefined set of rules being common to a plurality of nodes in a computer network;

means for preempting the selected data flow, thereby freeing network resources previously reserved for the selected data flow; and

means for reallocating the freed network resources for the new data flow.

26. The network node of claim 25, further comprising:

means for cooperating with a plurality of other network nodes to employ the same predefined set of rules for selecting data flows to preempt.

27. The network node of claim 25, further comprising:

means for determining whether the selected data flow participates in a fate-sharing group of data flows, where utility of data flows in the fate-sharing group depends on all data flows in the fate-sharing group being operational; and

means for preempting every data flow in the fate-sharing group.

28. The network node of claim 25, further comprising:

means for determining whether the selected data flow participates in a fate-sharing group of data flows, where utility of data flows in the fate-sharing group depends on all data flows in the fate-sharing group being operational; and

means for identifying every data flow in the fate-sharing group as being “

at risk”

of being preempted.

29. A network node configured to allocate network resources for a new data flow, the network node comprising:

means for selecting an existing “

at-risk”

data flow to preempt, the at-risk data flow participating in a fate-sharing group of data flows where at least one data flow in the fate-sharing group has already been preempted;

means for preempting the selected at-risk data flow, thereby freeing network resources previously reserved for the selected at-risk data flow; and

means for reallocating the freed network resources for the new data flow.

30. A network node configured to allocate network resources for a new data flow, the network node comprising:

a processor; and

a memory configured to store a reservation data structure accessible by the processor, the reservation data structure being adapted to store a fate-sharing identifier associated with a fate-sharing group of data flows which includes the new data flow, where utility of data flows in the fate-sharing group depends on all data flows in the fate-sharing group being operational.

31. The network node of claim 30, wherein the network node obtains the fate-sharing identifier from a message which was forwarded to the network node from another node situated along the new data flow'"'"'s data path.

32. The network node of claim 31, wherein the message is a RSVP Path message received from an upstream node along the new data flow'"'"'s data path.

33. The network node of claim 31, wherein the message is a RSVP Reservation message received from a downstream node along the new data flow'"'"'s data path.

34. The network node of claim 30, wherein the fate-sharing identifier is distributed among a plurality of nodes using an end-to-end signaling protocol.

35. The network node of claim 34, wherein the signaling protocol is the Session Initiation Protocol (SIP).

36. The network node of claim 34, wherein the signaling protocol is the H.323 protocol.

37. The network node of claim 30, wherein the fate-sharing identifier is a universal unique identifier (UUID).

38. A network node configured to allocate network resources for a new data flow, the network node comprising:

a processor; and

a memory configured to store instructions executable by the processor for performing the steps of;

selecting an existing data flow to preempt based on a predefined set of rules, the predefined set of rules being common to a plurality of nodes in the computer network;

preempting the selected data flow, thereby freeing network resources previously reserved for the selected data flow; and

reallocating the freed network resources for the new data flow.

39. A network node configured to allocate network resources for a new data flow, the network node comprising:

a processor; and

a memory configured to store instructions executable by the processor for performing the steps of;

selecting an existing “

at-risk”

data flow to preempt, the at-risk data flow participating in a fate-sharing group of data flows where at least one data flow in the fate-sharing group has already been preempted;

preempting the selected at-risk data flow, thereby freeing network resources previously reserved for the selected at-risk data flow; and

reallocating the freed network resources for the new data flow.