Subject: [NSIS] QoS NSLP: pre-emption

From: Jukka MJ Manner <[email-masked]>
Date: Tue, 20 Mar 2007 19:15:07 +0200 (EET)

The pre-emption functionality is after all quite a complex issue. We have 
had some discussion about it, and would propose the following:

- If a QNE receives a RESERVE for a flow that causes other flow(s) to be 
pre-empted, for each of these flows, the QNE will send a tearing RESERVE 
downstream and add an INFO_SPEC with pre-emption error code and a 
BOUND_SESSION_ID that indicates the flow that caused the pre-emption

- After sending the tearing RESERVE(s), the QNE will send the (reserving) 
  RESERVE

- Upon receiving this/these tearing RESERVEs, a QNE will set a timer that 
indicates that the indicated session MUST be torn down in the future, and 
sends the tearing RESERVE further downstream.

- Upon receiving the (reserving) RESERVE, the QNE will remove the pending 
resources, and make the new reservation.

- If the (reserving) RESERVE never arrives, e.g., the path of the 
pre-empted and high priority flows diverged at some point, the timer will 
cause the resources to be removed eventually.

Effectively, this causes a sort of "switch resouces from these sessions to 
the session indicated in the BOUND_SESSION once the RESERVE arrives". If 
the RESERVE never arrives, upstream nodes have already removed the 
resources, so the downstream node must do likewise.

This operation has the following benefits:

1. Downstream nodes are able to make the same decision when pre-empting 
   low priority flows due to the high priority flow.

2. We make sure the resources are put aside for the indicated high 
   priority flow in downstream nodes before the RESERVE actually arrives.

Any comments? (I wonder if I explained the idea properly)

Jukka

_______________________________________________
nsis mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/nsis

---

From: "Georgios Karagiannis" <[email-masked]>
Date: Mon, 26 Mar 2007 14:42:36 +0200

Hi Jukka and all

Your description covers almost all the items of the solution 
that we have found during our discussions 
on the coridors of the Hilton hotel in Prague.

However, below I include some more details:
 
Step_1: 
------
If a QNE receives a RESERVE for a session that causes other 
session(s) to be pre-empted, for each of these session, the QNE 
will send a tearing RESERVE downstream and add an INFO_SPEC 
with pre-emption error code and a BOUND_SESSION_ID that 
indicates the session that caused the pre-emption. Note that the value of 
this BOUND_SESSION_ID will have a new Binding Code value, which will 
have to be specified in the QOS-NSLP.
Furthermore, the selection of which 
flows will have to be terminated should be specified 
by the QOSM. An example of this selection process 
can be based on the MRI associated with the high and lower priority
sessions.
In particular the QNE cans select low(er) priority session(s) where the MRI 
is "close" (esp. the target IP) to the one associated with the higher
priority session. 
This has the benefit that the pre-empted session may share most of 
the path with the high priority session. 
Furthermore, the amount of the sessions that have to be preempted 
per each high priority session, has to be specified by the QOSM, 
since the QOSM has to compare the reserved resources by the 
lower priority sessions and the 
requested resources by the high priority session. 

Step_2:
-----
For each of the sent tearing RESERVE, the QNE will send a 
NOTIFY message with an INFO-SPEC that indicates the pre-emption 
error code towards the QNI.

 Step_3
------
After sending the tearing RESERVE(s), the QNE will send the 
(reserving) RESERVE

Step_4:
-----
Upon receiving the first tearing RESERVE, the QNE creates a so called (we
called it like this)
preemption state, which is identified by the SESSION_ID carried
in the preemption related BOUND_SESSION_ID object. Furthermore, this
preemption state 
will include the SESSION_ID of the session associated with the tearing
RESERVE.
If subsequently additional tearing RESERVE(s) are arriving, which include 
in their preemption related BOUND_SESSION_ID object(s) the value of the same
SESSION_ID (of the 
high priority session) as the one included in the first arrived tearing
RESERVE message, 
then the associated SESSION_IDs of these tearing RESERVE messages will be
included in the already 
created preemption state. The QNE then will set 
a timer that indicates that the indicated session MUST be 
torn down in the future, and sends the tearing RESERVE(s)
further downstream.

Step_5:
-----
Upon receiving the (reserving) RESERVE, the QNE will remove 
the pending resources, and make the new reservation. If the QNE will not
receive all 
the tearing RESRVEs sent by the previous upstream QNE, it will have to
calculate 
and select new lower priority sessions that have to be terminated. The
selection process is 
similar to the process described in Step_1.

Step_6:
-----
If the (reserving) RESERVE never arrives, e.g., the path of 
the pre-empted and high priority flows diverged at some 
point, the timer will cause the resources to be removed eventually.

Effectively, this causes a sort of "switch resouces from 
these sessions to the session indicated in the BOUND_SESSION 
once the RESERVE arrives". If the RESERVE never arrives, 
upstream nodes have already removed the resources, so the 
downstream node must do likewise.

1. Downstream nodes are able to make the same decision when 
pre-empting low priority flows due to the high priority flow.
 
2. We make sure the resources are put aside for the indicated high 
priority flow in downstream nodes before the RESERVE 
actually arrives.

3. Lower priority sessions are selected that atre assoicated with 
A destination IP address (included in MRI) that is 
"close" (esp. the target IP) to the one associated with the higher priority
session. 
This has the benefit that the pre-empted session may share most of 
the path with the high priority session. 

Best regards,
Georgios

> 
> -----Original Message-----
> From: Jukka MJ Manner [mailto:[email-masked]] 
> Sent: dinsdag 20 maart 2007 18:15
> To: NSIS Working Group
> Subject: [NSIS] QoS NSLP: pre-emption
> 
> 
> The pre-emption functionality is after all quite a complex 
> issue. We have had some discussion about it, and would 
> propose the following:
> 
> - If a QNE receives a RESERVE for a flow that causes other 
> flow(s) to be pre-empted, for each of these flows, the QNE 
> will send a tearing RESERVE downstream and add an INFO_SPEC 
> with pre-emption error code and a BOUND_SESSION_ID that 
> indicates the flow that caused the pre-emption
> 
> - Upon receiving this/these tearing RESERVEs, a QNE will set 
> a timer that indicates that the indicated session MUST be 
> torn down in the future, and sends the tearing RESERVE 
> further downstream.
> 
> - Upon receiving the (reserving) RESERVE, the QNE will remove 
> the pending resources, and make the new reservation.
> 
> - If the (reserving) RESERVE never arrives, e.g., the path of 
> the pre-empted and high priority flows diverged at some 
> point, the timer will cause the resources to be removed eventually.
> 
> Effectively, this causes a sort of "switch resouces from 
> these sessions to the session indicated in the BOUND_SESSION 
> once the RESERVE arrives". If the RESERVE never arrives, 
> upstream nodes have already removed the resources, so the 
> downstream node must do likewise.
>

---

From: "Hancock, Robert" <[email-masked]>
Date: Mon, 26 Mar 2007 14:11:27 +0100

hi all,

This is a very detailed description, but I don't really understand
the problem that is being solved. (That is, what are the special
things that we are trying to require of the solution.)

I interpret from some of the previous discussion that the potential
issue is that if pre-emption is carried out along a path, but the
pre-empted flows are selected independently at each node on the
path, you could end up with large numbers of flows being preempted
in an uncoordinated way (i.e. more than the minimal number necessary);
whereas, if one node knows that flows X/Y/Z have already been preempted
then it can choose to discard these first rather than randomly 
choosing A/B/C.

Is this a correct understanding? (If it is, I believe there are 
simpler solutions, but I thought I'd check the understanding first.)

r.

> From: Georgios Karagiannis [mailto:[email-masked]] 
> Sent: 26 March 2007 13:43
> To: 'Jukka MJ Manner'
> Cc: 'NSIS Working Group'
> Subject: [NSIS] Updated QoS NSLP: pre-emption text
> 
> Hi Jukka and all
> 
> that we have found during our discussions on the coridors of 
> the Hilton hotel in Prague.
> 
> session(s) to be pre-empted, for each of these session, the 
> QNE will send a tearing RESERVE downstream and add an 
> INFO_SPEC with pre-emption error code and a BOUND_SESSION_ID 
> that indicates the session that caused the pre-emption. Note 
> that the value of this BOUND_SESSION_ID will have a new 
> Binding Code value, which will have to be specified in the QOS-NSLP.
> flows will have to be terminated should be specified by the 
> QOSM. An example of this selection process can be based on 
> the MRI associated with the high and lower priority sessions.
> In particular the QNE cans select low(er) priority session(s) 
> where the MRI is "close" (esp. the target IP) to the one 
> associated with the higher priority session. 
> This has the benefit that the pre-empted session may share 
> most of the path with the high priority session. 
> Furthermore, the amount of the sessions that have to be 
> preempted per each high priority session, has to be specified 
> by the QOSM, since the QOSM has to compare the reserved 
> resources by the lower priority sessions and the requested 
> resources by the high priority session. 
> 
> 
> 
> Step_2:
> -----
> NOTIFY message with an INFO-SPEC that indicates the 
> pre-emption error code towards the QNI.
> 
> 
>  Step_3
> ------
> Upon receiving the first tearing RESERVE, the QNE creates a 
> so called (we called it like this) preemption state, which is 
> identified by the SESSION_ID carried in the preemption 
> related BOUND_SESSION_ID object. Furthermore, this preemption 
> state will include the SESSION_ID of the session associated 
> with the tearing RESERVE.
> If subsequently additional tearing RESERVE(s) are arriving, 
> which include in their preemption related BOUND_SESSION_ID 
> object(s) the value of the same SESSION_ID (of the high 
> priority session) as the one included in the first arrived 
> tearing RESERVE message, then the associated SESSION_IDs of 
> these tearing RESERVE messages will be included in the 
> already created preemption state. The QNE then will set a 
> timer that indicates that the indicated session MUST be torn 
> down in the future, and sends the tearing RESERVE(s) further 
> downstream.
> 
> Step_5:
> -----
> the pending resources, and make the new reservation. If the 
> QNE will not receive all the tearing RESRVEs sent by the 
> previous upstream QNE, it will have to calculate and select 
> new lower priority sessions that have to be terminated. The 
> selection process is similar to the process described in Step_1.
> 
> 
>  
> Step_6:
> -----
> 2. We make sure the resources are put aside for the indicated 
> high priority flow in downstream nodes before the RESERVE 
> actually arrives.
> 
> 3. Lower priority sessions are selected that atre assoicated 
> with A destination IP address (included in MRI) that is 
> "close" (esp. the target IP) to the one associated with the 
> higher priority session. 
> This has the benefit that the pre-empted session may share 
> most of the path with the high priority session. 
> 
> Best regards,
> Georgios
> 
> 
> 
> > 
> issue. We 
> > have had some discussion about it, and would propose the following:
> > 
> will send a 
> > tearing RESERVE downstream and add an INFO_SPEC with 
> pre-emption error 
> > code and a BOUND_SESSION_ID that indicates the flow that caused the 
> > pre-emption
> > 
> > - Upon receiving this/these tearing RESERVEs, a QNE will 
> set a timer 
> > that indicates that the indicated session MUST be torn down in the 
> > future, and sends the tearing RESERVE further downstream.
> > 
> > - Upon receiving the (reserving) RESERVE, the QNE will remove the 
> > pending resources, and make the new reservation.
> > 
> > pre-empted and high priority flows diverged at some point, 
> the timer 
> > will cause the resources to be removed eventually.
> > 
> > Effectively, this causes a sort of "switch resouces from these 
> > sessions to the session indicated in the BOUND_SESSION once the 
> > RESERVE arrives". If the RESERVE never arrives, upstream nodes have 
> > already removed the resources, so the downstream node must do 
> > likewise.
> > 
> > pre-empting

---

From: "Georgios Karagiannis" <[email-masked]>
Date: Mon, 26 Mar 2007 15:18:31 +0200

Hi Robert

I assumed that Jukka's problem description was clear enough

The problem description that you gave below is correct!

Best Regards,
Georgios

> From: Hancock, Robert [mailto:[email-masked]] 
> Sent: maandag 26 maart 2007 15:11
> To: Georgios Karagiannis; Jukka MJ Manner
> Cc: NSIS Working Group
> Subject: RE: [NSIS] Updated QoS NSLP: pre-emption text
> 
> hi all,
> 
> This is a very detailed description, but I don't really 
> understand the problem that is being solved. (That is, what 
> are the special things that we are trying to require of the solution.)
> 
> I interpret from some of the previous discussion that the 
> potential issue is that if pre-emption is carried out along a 
> path, but the pre-empted flows are selected independently at 
> each node on the path, you could end up with large numbers of 
> flows being preempted in an uncoordinated way (i.e. more than 
> the minimal number necessary); whereas, if one node knows 
> that flows X/Y/Z have already been preempted then it can 
> choose to discard these first rather than randomly choosing A/B/C.
> 
> Is this a correct understanding? (If it is, I believe there 
> are simpler solutions, but I thought I'd check the 
> understanding first.)
> 
> r.
> 
> 
> > Your description covers almost all the items of the 
> solution that we 
> > have found during our discussions on the coridors of the 
> Hilton hotel 
> > in Prague.
> > 
> QNE will 
> > send a tearing RESERVE downstream and add an INFO_SPEC with 
> > pre-emption error code and a BOUND_SESSION_ID that indicates the 
> > session that caused the pre-emption. Note that the value of this 
> > BOUND_SESSION_ID will have a new Binding Code value, which 
> will have 
> > to be specified in the QOS-NSLP.
> QOSM. An 
> > example of this selection process can be based on the MRI 
> associated 
> > with the high and lower priority sessions.
> > In particular the QNE cans select low(er) priority session(s) where 
> > the MRI is "close" (esp. the target IP) to the one 
> associated with the 
> > higher priority session.
> preempted per 
> > each high priority session, has to be specified by the 
> QOSM, since the 
> > QOSM has to compare the reserved resources by the lower priority 
> > sessions and the requested resources by the high priority session.
> > 
> > 
> > 
> > Step_2:
> > -----
> > For each of the sent tearing RESERVE, the QNE will send a NOTIFY 
> > message with an INFO-SPEC that indicates the pre-emption error code 
> > towards the QNI.
> > 
> > 
> >  Step_3
> > ------
> so called 
> > (we called it like this) preemption state, which is 
> identified by the 
> > SESSION_ID carried in the preemption related 
> BOUND_SESSION_ID object. 
> > Furthermore, this preemption state will include the 
> SESSION_ID of the 
> > session associated with the tearing RESERVE.
> > If subsequently additional tearing RESERVE(s) are arriving, which 
> > include in their preemption related BOUND_SESSION_ID
> > object(s) the value of the same SESSION_ID (of the high priority 
> > session) as the one included in the first arrived tearing RESERVE 
> > message, then the associated SESSION_IDs of these tearing RESERVE 
> > messages will be included in the already created preemption 
> state. The 
> > QNE then will set a timer that indicates that the indicated session 
> > MUST be torn down in the future, and sends the tearing RESERVE(s) 
> > further downstream.
> > 
> > Step_5:
> > -----
> > Upon receiving the (reserving) RESERVE, the QNE will remove the 
> > pending resources, and make the new reservation. If the QNE 
> will not 
> > receive all the tearing RESRVEs sent by the previous 
> upstream QNE, it 
> > will have to calculate and select new lower priority sessions that 
> > have to be terminated. The selection process is similar to 
> the process 
> > described in Step_1.
> > 
> > 
> >  
> > Step_6:
> > -----
> > If the (reserving) RESERVE never arrives, e.g., the path of the 
> > 3. Lower priority sessions are selected that atre assoicated with A 
> > destination IP address (included in MRI) that is "close" (esp. the 
> > target IP) to the one associated with the higher priority session.

---

From: "Hancock, Robert" <[email-masked]>
Date: Mon, 26 Mar 2007 14:56:02 +0100

ok,

so i read between the lines correctly.

what i don't see is the need to send two sets of reserve messages 
to carry out the pre-emption (the tear[s] followed by the 
installation). this would cause some issues message ordering
(race conditions) which are always hard to implement right,
especially when taking account of error conditions.

after all, the downstream node always has to have the freedom
to repeat the algorithm "select flows to be pre-empted". this might 
be for several reasons:
- some of the already pre-empted flows don't go through the 
  downstream node (need to find more resources)
- all the pre-empted flows go through the downstream node but
  it still needs to pre-empt more (less headroom for example)

therefore, there can be no strict need to send the tear[s] first.
all that is needed is for the pre-empting node to send the
pre-empting reserve with a list of the SIDs that it has already
pre-empted as bound sessions. this means that the pre-empting
reserve can be sent immediately. at some point in the future, 
the node can (if it wants) send explicit tears for the 
sessions it is removing, but that can be normal operation.
when the downstream node gets the pre-empting reserve, the
list of bound sessions gets used as another hint in the selection
algorithm.

the main difference in terms of message processing rules is that
in jukka's version, the BOUND_SESSION id refers to a session
that doesn't exist yet, so a node receving the tear has to 
remember it From [email-masked] Mon Mar 26 09:57:00 2007
Date: Mon, 26 Mar 2007 16:55:33 +0300 (EEST)
From: Jukka MJ Manner <[email-masked]>
To: "Hancock, Robert" <[email-masked]>
Subject: RE: [NSIS] QSPEC: Pre-emption
Cc: NSIS Working Group <[email-masked]>

Hi Rob,
Good point. Let's drop this item.

Jukka

On Mon, 26 Mar 2007, Hancock, Robert wrote:

> hi,
> a very simple answer: 
> > Sent: 24 March 2007 18:36
> > To: NSIS Working Group
> > Subject: [NSIS] QSPEC: Pre-emption
> > 
> > 
> > We (at least Roland, Andrew, Georgios) have thought a bit 
> > more about the pre-emption, and how&where it should be 
> > described. Basically, it is a "problem" of QOSMs. The NSLP 
> > provides certain messages to inform of pre-emption, and who 
> > caused it (my recent proposal on the mailing list).
> > 
> > But, how does a QNE choose a flow to be pre-empted in the 
> > first place is out of scope of the NSLP. Yet, it might be 
> > good to say a few words about how to choose the "right" flow 
> > to pre-empt to help QOSM designers.
> > 
> > One simple idea we have talked about is that the QNE should 
> > try to choose a low(er) priority flow where the MRI is 
> > "close" (esp. the target IP) to the higher priority flow. 
> > This has the benefit that the pre-empted flow may share most 
> > of the path with the high priority flow. If the pre-empted 
> > flow has a random MRI, in case of heavy congestion, QNEs 
> > downstream may not see the same low(er) priority flow, and, 
> > thus, pre-empt other flows. 
> > Thus, in order to accommodate one high priority flow, the 
> > network may be killing N other flows.
> > 
> > Do you think giving advise on pre-emption to QOSM designers 
> > is out of scope of the QSPEC Template?
> 
> basically I would say no. At least any normative text will hit
> endless debates about regulation and lawfulness. At most one
> could point out the consequences of particular strategies, but
> it would be preferable IMHO to refer to other documents.
> (In other words, I assume that anything useful that can be
> written on this topic in the IETF has already been written.)
> 
> robert h.
> 
> > 
> > Cheers,
> > Jukka
> > 
> > https://www1.iefor when the new reserve turns up. in what is 
suggested above, the BOUND_SESSION ids refer either to
- existing sessions at the node (i.e. already known), or
- unknown sessions (presumably whose routes have diverged), which
  can just be ignored.

robert h.

> Sent: 26 March 2007 14:19
> To: Hancock, Robert; 'Jukka MJ Manner'
> Cc: 'NSIS Working Group'
> understand the 
> > problem that is being solved. (That is, what are the special things 
> > that we are trying to require of the solution.)
> > 
> > pre-empted flows are selected independently at each node on 
> the path, 
> > you could end up with large numbers of flows being preempted in an 
> > uncoordinated way (i.e. more than the minimal number necessary); 
> > whereas, if one node knows that flows X/Y/Z have already been 
> > preempted then it can choose to discard these first rather than 
> > randomly choosing A/B/C.
> > 
> tf.org/mailman/listinfo/nsis
> > 
>

---

From: "Hancock, Robert" <[email-masked]>
Date: Mon, 26 Mar 2007 14:56:02 +0100

ok,

remember it > > 
> > > > future, and sends the tfor when the new reserve turns up. in what is 

robert h.

> earing RESERVE further downstream.
> > > > 
> actually 
> > > > arrives.

> actually 
> > > > arrives.

---

From: Jukka MJ Manner <[email-masked]>
Date: Mon, 26 Mar 2007 16:56:49 +0300 (EEST)

Hi Georgios,

Such text may go into the RMD document since it is only one way to 
implement pre-emption handling. The NSLP should provide the means, and the 
QOSMs define how to implement it.

Jukka

---

From: "Georgios Karagiannis" <[email-masked]>
Date: Mon, 26 Mar 2007 15:58:42 +0200

Hi Jukka

I agree!

Best regards,
Georgios

> Sent: maandag 26 maart 2007 15:57
> To: Georgios Karagiannis
> Cc: 'NSIS Working Group'
> Subject: Re: Updated QoS NSLP: pre-emption text
> 
> 
> Hi Georgios,
> 
> Such text may go into the RMD document since it is only one 
> way to implement pre-emption handling. The NSLP should 
> provide the means, and the QOSMs define how to implement it.
> 
> Jukka
> 
> > include in their preemption related BOUND_SESSION_ID object(s) the 
> > value of the same SESSION_ID (of the high priority session) 
> as the one 
> > included in the first arrived tearing RESERVE message, then the 
> > associated SESSION_IDs of these tearing RESERVE messages will be 
> > included in the already created preemption state. The QNE then will 
> > set a timer that indicates that the indicated session MUST be torn 
> higher priority