Subject: [sip-overload] Issue: Multiple algorithms -> Single algorithm for overload control

From: "Vijay K. Gurbani" <[email-masked]>
Date: Fri, 10 Jun 2011 16:34:27 -0500

Folks: During the Prague IETF, Mr. Kaplan reopened the
case for supporting multiple overload control algorithms [1].

Summarizing, the basic problems with multiple algorithms are:

1) Interoperability suffers as protocol gets complex.
2) Get out one algorithm now (loss), and later if there is a need to
    standardize more add the oc-algo parameter in a backwards
    compatible manner.
3) Re-negotiating the chosen algorithm is not trivial.
4) Servers will have to maintain negotiated algorithms as pieces
    of state for a potentially large set of upstream clients.

I cannot say that I am unsympathetic to the above list.  If we can
simplify processing, then we should do so.

The main reason to support multiple algorithms appear to have been
the need to not preclude rate-based algorithms [2,3].  However
subsequent discussions in the thread started off by [3] have
resulted in the understanding that rate-based algorithms may have
a slight advantage if the offered load at the client significantly
surges over a period of time << then the overload server's feedback
period.  Since the overload server's feedback period is already short
(500ms by default), the advantage possessed by rate-based algorithms
may be moot [5].

Further, minimizing state in the server is an argument to pick
loss-based as the default algorithm instead of rate-based.  The
latter requires the server to assign --- and keep track --- of a
share of its overall capacity with each upstream client.

So ... given all this, it may be a good idea to go with one
algorithm, and make that the loss based algorithm.

I will like have discussion so we can reach consensus on this
issue and close it for good.

[1] http://www.ietf.org/mail-archive/web/sip-overload/current/msg00564.html
[2] http://www.ietf.org/mail-archive/web/sip-overload/current/msg00565.html
[3] http://www.ietf.org/mail-archive/web/sip-overload/current/msg00600.html
[4] http://www.ietf.org/mail-archive/web/sip-overload/current/msg00606.html
[5] http://www.ietf.org/mail-archive/web/sip-overload/current/msg00606.html

Thanks,

- vijay
-- 
Vijay K. Gurbani, Bell Laboratories, Alcatel-Lucent
1960 Lucent Lane, Rm. 9C-533, Naperville, Illinois 60566 (USA)
Email: vkg@{bell-labs.com,acm.org} / [email-masked]
Web:   http://ect.bell-labs.com/who/vkg/

---

From: Janet P Gunn <[email-masked]>
Date: Fri, 10 Jun 2011 18:03:48 -0400

Do I understanding that you are expecting an (already overloaded) SIP 
server to recalculate the desired "loss rate" twice a second?

Is that wise?

Janet

[email-masked] wrote on 06/10/2011 05:34:27 PM:

> [image removed] 
> 
> [sip-overload] Issue: Multiple algorithms -> Single algorithm for 
> overload control
> 
> Vijay K. Gurbani 
> 
> to:
> 
> [email-masked]
> 
> 06/10/2011 05:34 PM
> 
> Sent by:
> 
> [email-masked]
> 
> [1] 
http://www.ietf.org/mail-archive/web/sip-overload/current/msg00564.html
> [2] 
http://www.ietf.org/mail-archive/web/sip-overload/current/msg00565.html
> [3] 
http://www.ietf.org/mail-archive/web/sip-overload/current/msg00600.html
> [4] 
http://www.ietf.org/mail-archive/web/sip-overload/current/msg00606.html
> [5] 
http://www.ietf.org/mail-archive/web/sip-overload/current/msg00606.html
> _______________________________________________
> sip-overload mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sip-overload

---

From: "Bharrat, Shaun" <[email-masked]>
Date: Fri, 10 Jun 2011 18:14:53 -0400

> Is that wise?

I am also am concerned about adding any extra load to the overloaded
server, but that makes me come down on the other side. It would seem
to me that making the overloaded server try to track/compute the
rates distributed to each upstream node would be even more work intensive.

Assuming that the overloaded server is using some dynamic algorithm
to determine the (aggregate) load to let in, I would think that it is
recomputing (aggregate) accept rates at least this granularity anyway.

My vote is for the simplest requirement on the overloaded server with
any bells and whistles (if any) on the upstream (non-overloaded) nodes.

Cheers,
Shaun

-----Original Message-----
From: [email-masked] on behalf of Janet P Gunn
Sent: Fri 6/10/2011 6:03 PM
To: Vijay K. Gurbani
Cc: [email-masked]; [email-masked]
Subject: Re: [sip-overload] Issue: Multiple algorithms -> Single algorithmfor	overload control

Is that wise?

Janet

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Sat, 11 Jun 2011 17:46:27 -0500

> server to recalculate the desired "loss rate" twice a second?

Janet: I am not sure I understand your question.  If
you are asking about the default value of the server's
feedback period, it has been 500ms since the beginning
of this work.

> Is that wise?

Recalculation by the overload server has to be done for
any algorithm, right?

Thanks,

- vijay

---

From: Janet P Gunn <[email-masked]>
Date: Sat, 11 Jun 2011 20:49:59 -0400

I am sure it was, it just hadn't sunk in for me.

I guess the wisdom of that value depends on the complexity of the 
algorithm for choosing the loss parameter. If it is a simple calculation 
it shouldn't matter.

Janet

"Vijay K. Gurbani" <[email-masked]> wrote on 06/11/2011 06:46:27 PM:

> [image removed] 
> 
> Re: [sip-overload] Issue: Multiple algorithms -> Single algorithm 
> for overload control
> 
> Vijay K. Gurbani 
> 
> to:
> 
> Janet P Gunn
> 
> 06/11/2011 06:46 PM
> 
> Cc:
> 
> "[email-masked]"
> 
> Janet P Gunn wrote:

---

From: <[email-masked]>
Date: Tue, 14 Jun 2011 12:02:09 +0100

Thanks Vijay,

For continuing to consider the arguments that I raised supporting multiple restriction  algorithms. I would like to make some comments and provide some further proposals below.

First, taking the points that you raised:

'...the basic problems with multiple algorithms are:

1) Interoperability suffers as protocol gets complex.'

I'm not sure that I understand this one - perhaps could you elaborate? In fact I see interoperability is an argument for supporting multiple (in particular rate-based) controls. The usefulness of proportional rejection is not just limited by performance issues, but perhaps more important they are not well suited for applying capacity guarantees (SLAs), which I have described in my original e-mail. I expect that as SIP becomes more ubiquitous across operator boundaries this will become increasingly important, and I suggest that we should be future-proofing SIP overload control for this reason.

'2) Get out one algorithm now (loss), and later if there is a need to
    standardize more add the oc-algo parameter in a backwards
    compatible manner.'

Realistically, if this is the approach taken then suppliers will only provide proportional rejection, and it will become difficult/expensive to introduce other restriction methods such as rate-based controls.

'3) Re-negotiating the chosen algorithm is not trivial.'

If support for restriction algorithms is mandatory, i.e. you either support all ( 3?) algorithms or none at all, then it would just be a case of indicating that overload control is supported. This does not seem to be complex.

If upstream clients have to support multiple algorithms, then this is not necessary, since it is up to the overloaded server to decide which restriction algorithm to use. The server can be confident that if overload control is supported, then it can choose which algorithm (if no algorithms are supported this is an issue already with the current spec).

I would also like to re-iterate that the 3 client restriction algorithms have been around for a long time, and are already widely deployed (and subject to limited variation in their realisation). Therefore we would expect it to be less contentious to standardise these methods within SIP, but in any case we would expect less sensitivity to design variations.

Regarding another issue that was raised - the computational overhead of adaptation calculation performed by the overloaded server, from practical experience designing and deploying overload controls, I suggest that this should be insignificant compared to the other functions of the server. However there are much more critical constraints:

(1) The inaccuracy introduced by making updates too frequent, during to stochastic nature of arrivals etc. The updates will be based upon measures such as counting requests/messages and CPU occupancy. If the number of requests processed is 'too small' then there will be significant inaccuracy in the estimated throughput and therefore the required control parameters. The main factors here are the inherent limit to the accuracy of measuring CPU occupancy (what is really required is time-integrated measurement of all CPU activity between two updates), but also the effect of subsequent phases of session processing. By the latter I include mid-session processing and disconnects (which are not controlled by the sources). To overcome these issues it is necessary to measure for sufficiently long and to apply appropriate smoothing. [Note that the mix/complexity may change very suddenly due to surges, disconnect avalanches, etc. These must all be taken into account].

(2) The number of sources (clients) and the way in which the restriction algorithm state is changed. For example, with proportional rejection (loss-based) it will be typically be implemented as a deterministic sequence of alternating admissions and rejections. When the arrival rate at each source is very low this deterministic sequence is interrupted and has to be changed to reflect the modified control parameter, and how this is done may have a significant impact on the overall admission rate from all sources. If updates are very frequent and the number of sources very large some sources may not have even receive an arrival before the change is made!

Because of these factors there are fundamental limits to how quickly updates can be made. Generally the update time has to be longer when the server throughput is lower (more complex requests) and the number of sources is larger. The problem with proportional restriction is that during the time between updates it is possible that one or more rogue streams suddenly inflate. Although the precise performance depends upon the network configuration, in general an advantage of rate-based controls is that there will be an upper limit to the admission rate even before an update is made (not so for proportional rejection).

If these factors are not taken into account and the update period is too short, then the likely outcome is unstable control, and this can have a dramatic (bad) effect on throughput.

To progress the debate further I would like to offer to produce a modified version of draft-ietf-soc-overload-control-02 for comment. I could also (later) submit a recommendation for implementation of proportional rejection and rate-based methods if this is deemed a useful addition to the draft in order to facilitate adoption.

Regards,

Phil Williams

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Vijay K. Gurbani
Sent: 10 June 2011 22:34
To: [email-masked]
Subject: [sip-overload] Issue: Multiple algorithms -> Single algorithm for overload control

Thanks,

- vijay

---

From: "NOEL, ERIC C (ERIC C)" <[email-masked]>
Date: Tue, 14 Jun 2011 10:16:44 -0400

Folks,

If decision is made to support a rate control algorithm, I could submit a contribution that describes AT&T rate control algorithm developed in support of the Overload Design team work. 

Thanks,

Eric Noel 
LMTS
AT&T Labs, Inc. 
Rethink Possible

Network Design and Performance Analysis
200 South Laurel Avenue, D5-3D19
Middletown, NJ 07748
P: 732.420.4174
[email-masked]

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: Tuesday, June 14, 2011 7:02 AM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [sip-overload] Issue: Multiple algorithms -> Single algorithm for overload control

Thanks Vijay,

Regards,

Phil Williams

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Vijay K. Gurbani
Sent: 10 June 2011 22:34
To: [email-masked]
Subject: [sip-overload] Issue: Multiple algorithms -> Single algorithm for overload control

Thanks,

- vijay

---

From: Janet P Gunn <[email-masked]>
Date: Tue, 14 Jun 2011 15:28:45 -0400

I would certainly like to see such an ID.

Janet

From:
"NOEL, ERIC C (ERIC C)" <[email-masked]>
To:
"[email-masked]" <[email-masked]>, "[email-masked]" 
<[email-masked]>
Cc:
"JOHNSON, CAROLYN R \(ATTSI\)" <[email-masked]>, "[email-masked]" 
<[email-masked]>
Date:
06/14/2011 10:15 AM
Subject:
Re: [sip-overload] Issue: Multiple algorithms -> Single algorithm for 
overload control

Folks,

If decision is made to support a rate control algorithm, I could submit a 
contribution that describes AT&T rate control algorithm developed in 
support of the Overload Design team work. 

Thanks,

Eric Noel 
LMTS
AT&T Labs, Inc. 
Rethink Possible

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
On Behalf Of [email-masked]
Sent: Tuesday, June 14, 2011 7:02 AM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [sip-overload] Issue: Multiple algorithms -> Single algorithm 
for overload control

Thanks Vijay,

For continuing to consider the arguments that I raised supporting multiple 
restriction  algorithms. I would like to make some comments and provide 
some further proposals below.

I'm not sure that I understand this one - perhaps could you elaborate? In 
fact I see interoperability is an argument for supporting multiple (in 
particular rate-based) controls. The usefulness of proportional rejection 
is not just limited by performance issues, but perhaps more important they 
are not well suited for applying capacity guarantees (SLAs), which I have 
described in my original e-mail. I expect that as SIP becomes more 
ubiquitous across operator boundaries this will become increasingly 
important, and I suggest that we should be future-proofing SIP overload 
control for this reason.

Realistically, if this is the approach taken then suppliers will only 
provide proportional rejection, and it will become difficult/expensive to 
introduce other restriction methods such as rate-based controls.

If support for restriction algorithms is mandatory, i.e. you either 
support all ( 3?) algorithms or none at all, then it would just be a case 
of indicating that overload control is supported. This does not seem to be 
complex.

If upstream clients have to support multiple algorithms, then this is not 
necessary, since it is up to the overloaded server to decide which 
restriction algorithm to use. The server can be confident that if overload 
control is supported, then it can choose which algorithm (if no algorithms 
are supported this is an issue already with the current spec).

I would also like to re-iterate that the 3 client restriction algorithms 
have been around for a long time, and are already widely deployed (and 
subject to limited variation in their realisation). Therefore we would 
expect it to be less contentious to standardise these methods within SIP, 
but in any case we would expect less sensitivity to design variations.

Regarding another issue that was raised - the computational overhead of 
adaptation calculation performed by the overloaded server, from practical 
experience designing and deploying overload controls, I suggest that this 
should be insignificant compared to the other functions of the server. 
However there are much more critical constraints:

(1) The inaccuracy introduced by making updates too frequent, during to 
stochastic nature of arrivals etc. The updates will be based upon measures 
such as counting requests/messages and CPU occupancy. If the number of 
requests processed is 'too small' then there will be significant 
inaccuracy in the estimated throughput and therefore the required control 
parameters. The main factors here are the inherent limit to the accuracy 
of measuring CPU occupancy (what is really required is time-integrated 
measurement of all CPU activity between two updates), but also the effect 
of subsequent phases of session processing. By the latter I include 
mid-session processing and disconnects (which are not controlled by the 
sources). To overcome these issues it is necessary to measure for 
sufficiently long and to apply appropriate smoothing. [Note that the 
mix/complexity may change very suddenly due to surges, disconnect 
avalanches, etc. These must all be taken into account].

(2) The number of sources (clients) and the way in which the restriction 
algorithm state is changed. For example, with proportional rejection 
(loss-based) it will be typically be implemented as a deterministic 
sequence of alternating admissions and rejections. When the arrival rate 
at each source is very low this deterministic sequence is interrupted and 
has to be changed to reflect the modified control parameter, and how this 
is done may have a significant impact on the overall admission rate from 
all sources. If updates are very frequent and the number of sources very 
large some sources may not have even receive an arrival before the change 
is made!

Because of these factors there are fundamental limits to how quickly 
updates can be made. Generally the update time has to be longer when the 
server throughput is lower (more complex requests) and the number of 
sources is larger. The problem with proportional restriction is that 
during the time between updates it is possible that one or more rogue 
streams suddenly inflate. Although the precise performance depends upon 
the network configuration, in general an advantage of rate-based controls 
is that there will be an upper limit to the admission rate even before an 
update is made (not so for proportional rejection).

If these factors are not taken into account and the update period is too 
short, then the likely outcome is unstable control, and this can have a 
dramatic (bad) effect on throughput.

To progress the debate further I would like to offer to produce a modified 
version of draft-ietf-soc-overload-control-02 for comment. I could also 
(later) submit a recommendation for implementation of proportional 
rejection and rate-based methods if this is deemed a useful addition to 
the draft in order to facilitate adoption.

Regards,

Phil Williams

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
On Behalf Of Vijay K. Gurbani
Sent: 10 June 2011 22:34
To: [email-masked]
Subject: [sip-overload] Issue: Multiple algorithms -> Single algorithm for 
overload control

[1] 

Thanks,

- vijay

---

From: <[email-masked]>
Date: Thu, 16 Jun 2011 12:03:25 +0100

Eric,

Thanks for the offer.

Incidentally, one issue that you may already have taken account of is 'resonance' or 'synchronisation'. I was originally made aware of this in the papers by Leonard Forys et al, but I have modelled and verified it by simulation. This can occur with any naive implementation of a restriction algorithm, and occurs when there are a large number of client sources and the load is high and arises quickly.

In the specific case of leaky bucket ('rate-based') it will be manifested by the bucket fills all being nearly the same in synchronisation (and similarly for windowing).

In the case of proportional rejection ('loss-based') it would be when a deterministic sequence of admission/rejects are in phase.

The net result on the arrival stream at the overloaded server is that it can be extremely batched and peaky, resulting in very poor response times at best and at worst lost messages (and potentially rather catastrophic).

For the leaky bucket case a solution that I favour is to randomise the fill when control starts (about the initial fill) and when the bucket empties. The reason for the latter is to deal with the case of a mid-overload abatement followed by another surge, which can have the effect of re-synchronising the fill.

This may not be the forum to go into this in detail (as a separate thread?), but I would be interested in your solutions...

Regards,

Phil Williams

-----Original Message-----
From: NOEL, ERIC C (ERIC C) [mailto:[email-masked]] 
Sent: 14 June 2011 15:17
To: Williams,PM,Phil,DEV6 R; [email-masked]
Cc: [email-masked]; DOLLY, MARTIN C (ATTSI); JOHNSON, CAROLYN R (ATTSI)
Subject: RE: [sip-overload] Issue: Multiple algorithms -> Single algorithm for overload control

Folks,

Thanks,

Eric Noel 
LMTS
AT&T Labs, Inc. 
Rethink Possible

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: Tuesday, June 14, 2011 7:02 AM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [sip-overload] Issue: Multiple algorithms -> Single algorithm for overload control

Thanks Vijay,

Regards,

Phil Williams

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Vijay K. Gurbani
Sent: 10 June 2011 22:34
To: [email-masked]
Subject: [sip-overload] Issue: Multiple algorithms -> Single algorithm for overload control

Thanks,

- vijay

---

From: <[email-masked]>
Date: Thu, 16 Jun 2011 14:01:08 +0100

Vijay,

To follow up on my e-mail below, I am producing a proposed revision of draft-ietf-soc-overload-control-02 for comment, and I expect to send this out for consideration early next week.

So far it looks like there will be a considerable simplification, since essentially the overloaded SIP server is now master and there is no longer any need for negotiation of the restriction algorithm at the SIP client. It should also make future evolution more straightforward both for the spec and for deployments.

There may some additional complexity to specify the algorithms themselves, but it is not clear to me to what extent the spec is expected to nail them down.

Regards,

Phil Williams

-----Original Message-----
From: Williams,PM,Phil,DEV6 R 
Sent: 14 June 2011 12:02
To: 'Vijay K. Gurbani'
Cc: [email-masked]
Subject: RE: [sip-overload] Issue: Multiple algorithms -> Single algorithm for overload control

Thanks Vijay,

Regards,

Phil Williams

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Vijay K. Gurbani
Sent: 10 June 2011 22:34
To: [email-masked]
Subject: [sip-overload] Issue: Multiple algorithms -> Single algorithm for overload control

Thanks,

- vijay

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Thu, 16 Jun 2011 08:36:21 -0500

On 06/16/2011 08:01 AM, [email-masked] wrote:
> To follow up on my e-mail below, I am producing a proposed revision
> of draft-ietf-soc-overload-control-02 for comment, and I expect to
> send this out for consideration early next week.
>
> So far it looks like there will be a considerable simplification,
> since essentially the overloaded SIP server is now master and there
> is no longer any need for negotiation of the restriction algorithm at
> the SIP client. It should also make future evolution more
> straightforward both for the spec and for deployments.
>
> There may some additional complexity to specify the algorithms
> themselves, but it is not clear to me to what extent the spec is
> expected to nail them down.

Phil: I believe that modifying a working group document without
a consensus is probably not appropriate.

Certainly, the same set of folks who have been arguing for the
rate have expressed interest in it again, but I do not sense
that a larger discussion has taken place to develop a consensus
to support *all overload algorithms* at the same time.

As such, it may be best to issue an independent document of how
you see such a solution proceeding, and in such a document,
feel free to use the terminology and parameters established
in draft-ietf-soc-overload-control.  Subsequent to that, we
can debate the merits of supporting all algorithms and incorporate
the consensus into the working group document
(draft-ietf-soc-overload-control).

I am sorry, but I have been tied up and need to catch
up with list email.

Thanks,

- vijay

---

From: <[email-masked]>
Date: Thu, 16 Jun 2011 16:28:30 +0100

Vijay,

Thanks for the advice. I was indeed intending it to be an independent document, but a copy incorporating revisions to the original so that the differences would be made as clear. Given that the intention is for both proposals to support multiple restriction algorithms at clients I suggest that it would help to compare them.

Although in principle both approaches would support (or evolve to support) the same capability, I am concerned (if not convinced) that proceeding with a single mandated algorithm would result in non-adoption of the other algorithms by suppliers and in effect the alternatives would become redundant (rather like a piece of DNA with redundant sequences?). This particular issue is not really a technical one. But I see this as a critical decision for the evolution of SIP.

I see that contributors like yourself have done much valuable work before me. Like you I have been tied up with other work, but for rather longer! Please bear with me,

Regards,

Phil

-----Original Message-----
From: Vijay K. Gurbani [mailto:[email-masked]] 
Sent: 16 June 2011 14:36
To: Williams,PM,Phil,DEV6 R
Cc: [email-masked]
Subject: Re: [sip-overload] Issue: Multiple algorithms -> Single algorithm for overload control

Thanks,

- vijay

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Thu, 16 Jun 2011 11:09:48 -0500

On 06/16/2011 10:28 AM, [email-masked] wrote:
> Vijay,
>
> Thanks for the advice. I was indeed intending it to be an independent
> document, but a copy incorporating revisions to the original so that
> the differences would be made as clear.

Phil: Ah, OK.  Perfect, then.  More inline.

> Although in principle both approaches would support (or evolve to
> support) the same capability, I am concerned (if not convinced) that
> proceeding with a single mandated algorithm would result in
> non-adoption of the other algorithms by suppliers and in effect the
> alternatives would become redundant (rather like a piece of DNA with
> redundant sequences?).

Survival favours the fittest, so I strongly suspect that if one
algorithm does not perform as expected, it will be replaced by the
other.

That said, I think we have to be realistic here in recognizing that
the relative performance of all the algorithms is about the same.
So therefore, if the relative performance is the same then there
may be certain network deployments where the choice of one algorithm
seems better than the other.

Rate-based one will work well in managed networks where the set of
upstream clients sending requests is bounded and rather static; this
also makes it easier to apply capacity guarantees.  Loss-based one
works well where the set of upstream clients sending traffic is
unbounded and frequently changing.

I suspect that we will have a larger discussion on which one of
these becomes mandatory-to-implement, or whether it makes sense
implementing both of them (since no one is championing the windows-based 
one, I will keep it on the back-burner for now).

Thanks,

- vijay