Subject: [sip-overload] draft-ietf-soc-overload-control-07 section 6.3 algorithm

From: Eric McMurry <[email-masked]>
Date: Wed, 7 Mar 2012 13:10:53 -0600

I'm a bit confused on the default loss-based algorithm in section 6.3 of draft-ietf-soc-overload-control-07.  Based on the text, I believe that this algorithm is intended to apply to outbound messages from a client and to use previously stored information about the overload condition of the downstream server the message is targeted to.

When I read through the algorithm part though, I'm not sure of the intent.  I've made some changes in the algorithm to try to communicate what I think it was saying.  Does this match the intent?

    cat1 := 40.0          // Category 1 --- subject to reduction
   cat2 := 100.0 - cat1  // Category 2 --- Not subject to
                         // reduction.  40/60 mix.
   in_oc := false        // Not operating under overload

   while (true)  {
     sip_msg := get_outgoing_sip_msg()
     if (is_response(sip_msg))  {
         process_msg(sip_msg)
     }
     else if (is_request(sip_msg))  {

       // Determine if target server wants to enter overload or is
       // in overload
       target_server := extract_target(sip_msg)
       in_oc := lookup_in_oc(target_server)

       // Get validity value
       oc_validity := lookup_oc_validity(target_server)

       // Get oc parameter value
       oc_value := lookup_oc_value(target_server)

       pct_to_reduce := oc_value / cat1 * 100
       // Example: if oc=10,
       // server uses 10 / 40 * 100 = 25 or 25% of messages in
       // Category 1 can be reduced.

       if (in_oc == false)  {
         process_msg(sip_msg)
       }
       else  {

         // Either Category 1 or Category 2
         assign_msg_to_category(sip_msg)

         if (oc_validity is in effect)  {
           process_msg(get_msg_from_cat2())
           sip_msg := get_msg_from_cat1()

           // Draw a random number between 1 and 100
           r := random()

           if (r <= pct_to_reduce)  {
               // Do not send to server, handle locally by
               // generating a final response
           }
           else  {
             process_msg(sip_msg)
           }
         }
       }
     }
   }

---

From: Adam Roach <[email-masked]>
Date: Wed, 07 Mar 2012 13:14:27 -0600

Sigh. Eric and I have been discussing this just now, and we got our 
messages crossed. He fixed one of about four problems with his changes 
below. See my message of about 2 minutes ago for a proposal that fixes 
several other issues.

/a

On 3/7/12 1:10 PM, Eric McMurry wrote:
>         // Determine iftarget  server wants to enter overload or is
>         // in overload
>         in_oc :=lookup_in_oc(target_server)
>
>         // Get validity value
>         oc_validity :=lookup_oc_validity(target_server)
>
>         oc_value :=lookup_oc_value(target_server)
>
>             if (r<= pct_to_reduce)  {
> _______________________________________________
> sip-overload mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sip-overload

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Thu, 08 Mar 2012 12:08:21 -0600

Adam, Eric: Thank you for looking over the algorithm.  I was hoping
that more eyeballs will look at it and uncover problems.  The
baroqueness you refer to is an artefact of trying to come up with
a cohesive algorithm based on a simple textual description [1] coupled
with ensuing discussions on the list on how to specify local policy when
the server is overloaded and bolstered by some underlying unstated
assumptions.

In any case, I have modified the algorithm based on your suggested
changes with unstated assumptions filled out, for instance,
in the algorithm below, I have included more details on message
prioritization that occurs for category 2 messages under overload.
In the ealier iteration, I had simply stated in text that if there
are not enough messages in category 1, then client may use
"local policies" to target messages in category 2.

With the algorithm relatively fresh in our minds, let's see if what
appears below addresses your comments.  Note that I have also fixed
category 1 / category 2 messages to be a 80/20 mix instead of a
40/60 mix earlier.  It seems appropriate that the corpus of messages
that are subject to reduction be more than those that are not (unless
an emergency situation is occurring).

Thank you for pointing out where the errors lie!  Please take a look
at the updated algorithm below and lets see if we can work at making
this any better.

cat1 := 80.0         // Category 1 --- subject to reduction
cat2 := 100.0 - cat1 // Category 2 --- Not subject to reduction
                      // 80/20 mix.
while (true)  {
    sip_msg := get_sip_msg() // Next SIP message to process, could be a
                             // request or a response

    if (is_response(sip_msg)) {
        if (sip_msg has oc parameter values)  {
            create_or_update_oc_context()  // For the specific server
            // that sent the response, create or update the oc context;
            // i.e., extract the values of the oc-related parameters
            // and store them for later use.
        }
        process_msg(sip_msg)  // Rest of normal processing occurs on
        // the response, which may include consuming it if the client
        // is a user agent or sending it upstream if a proxy
    }
    else if (is_request(sip_msg))  {
       destination := get_next_hop(sip_msg)
       oc_context := get_oc_context(destination)

       if (oc_context == null)  {
           process_msg(sip_msg) // Process it normally by sending the
           // request downstream since this particular destination
           // is not subject to overload
       }
       else  {
          // Determine if server wants to enter in overload or is in
          // overload
          in_oc := extract_in_oc(oc_context)

          oc_value := extract_oc(oc_context)
          oc_validity := extract_oc_validity(oc_context)

          if (in_oc == false or oc_validity is not in effect)  {
             process_msg(sip_msg) // Process it normally by sending the
              // request downstream since this particular destination
              // is not subject to overload.  Optionally, clear
              // the oc context for this server (not shown).
          }
          else  {
             category := assign_msg_to_category(sip_msg)
             drop_msg := 0
             pct_to_reduce := min(100, oc_value / cat1 * 100)

             r := random()
                drop_msg := 1
             }

             if (category == cat2 && drop_msg == 1)  {
                if (local_policy(sip_msg, oc_value) says process message) {
                    drop_msg := 0  // See Note 1 below
                }
             }

             if (drop_msg == 0) {
                 process_msg(sip_msg) // Process it normally by sending
                // the request downstream
             }
             else  {
                // Do not send request downstream, handle locally by
                // generating response.
             }
          }
       }
    } // is_request(sip_msg)
}

Note 1: local_policy() will have to decide whether to allow a category
  2 request downstream if that request has been marked for discard.
  Some discussion on how to make this decision is captured in Section
  5.10.1.

  There will be four cases to consider in figuring out how local_policy()
  should behave.  These are enunciated below, and in these cases, t is
  the inter-invocation time of local_policy() and oc is the value of
  the "oc" parameter.

  Case 1: t is small (<= 10 times/sec?) and oc is small (<20%?)
  Case 2: t is large (>= 500 times/sec?) and oc is large (>70%?)
  Case 3: t is small and oc is large
  Case 4: t is large and oc is small

  The decision in cases 1 and 3 seems simple.  In case 1, local_policy()
  is not invoked as often and the oc value is small.  On the few
  times that local_policy() is invoked, it could allow the request to
  to be sent to the server.

  In case 3, local_policy() is not invoked as often but the oc value
  is large.  This implies that there are enough category 1 messages
  that are being dropped.  On the few times that local_policy() is
  invoked, it could allow the request to be sent to the server.

  It is cases 2 and 4 that local_policy() should do something more
  intelligent.

  In case 2, local_policy() is getting invoked very
  often and the oc is also large.  This implies that category 1
  requests are being dropped as much as possible and it will help
  to drop a good number of category 2 requests as well.  Thus,
  it seems reasonable to drop all but the SOS URN [RFC5031]
  requests and high priority RPH content requests.

  In case 4, local_policy() is getting invoked very often, but the
  oc value is small.  This implies that the bulk of traffic to be
  dropped consists of category 2 requests.  So here, it seems
  reasonable to drop all but the SOS URN [RFC5031] requests.

[1] www.ietf.org/mail-archive/web/sip-overload/current/msg00318.html

Thanks,

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

---

From: Adam Roach <[email-masked]>
Date: Thu, 08 Mar 2012 12:30:35 -0600

No, now I'm even more confused. I have a rather long list of things I 
think need to change here, but I don't want to throw them all out for 
fear of them being confused with each other.

Let's start simple, with the most fundamentally important question: 
where is "get_sip_msg()" getting a message from?

(a) Some internal queue of outgoing SIP messages to be sent to the network
(b) A network interface (or some abstraction thereof) representing 
incoming SIP messages
(c) Somewhere else

/a

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Thu, 08 Mar 2012 13:04:57 -0600

> (b) A network interface (or some abstraction thereof) representing

So I fail to see the need to pin down exactly where it is getting
these messages from?  From the processing point of view, the
algorithm (being executed at a client upstream of the overloaded
server) gets a SIP message and it has to decide if it is a
request or response.  The host executing this algorithm could be a
UAC, in which case it is getting SIP responses from the network
and it is getting SIP requests from its TU.  Or, that host could be a
proxy, in which case it is getting (in a sense) both requests and
responses from the network.

If a response, the algorithm extracts the oc parameters and creates the
oc context for the server that filled in the oc parameters.  If it is
a request, it decides whether the request is destined to server
that indicated oc before.

We can chat over the phone if that will make the convergence process
faster?

- vijay

---

From: Adam Roach <[email-masked]>
Date: Thu, 08 Mar 2012 13:12:32 -0600

On 3/8/12 1:04 PM, Vijay K. Gurbani wrote:
> these messages from?

Because responses that you're *sending* will *not* contain overload 
information that you need to extract. In fact, you'll need to take 
action to *put* overload information in them.

Responses that you're *receiving* will potentially contain overload 
information that you need to extract and store.

Similarly, requests that you're about to *send* are subject to the 
overload state of their next hop host, and might be dropped accordingly. 
Requests that you've just *received* aren't (although they might be 
subject to local rejection, per the behavior in 5.10.2).

Critically, there are four different behaviors that need to be detailed: 
inbound request, outbound request, inbound response, and outbound 
response. The algorithm in the draft (and the revised one that you 
proposed) seem to mash these all together into two cases (request and 
response), which are then slightly or radically wrong, depending on 
whether they're applied to inbound or outbound messages.

/a

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Thu, 08 Mar 2012 13:30:09 -0600

> action to *put* overload information in them.

Well ... if you are *sending* a response, you're acting as a proxy
and in fact, will take out oc parameters from a response going upstream.

> information that you need to extract and store.

Right.

> overload state of their next hop host, and might be dropped accordingly.

Right.

> subject to local rejection, per the behavior in 5.10.2).

Right.

> whether they're applied to inbound or outbound messages.

So assume that you are a proxy (the most general of the entities doing
overload control).  And also assume that when you execute

while (true)  {
    sip_msg := get_sip_msg() ... }

that if this is a request, it has been picked up from the network and
put on your processing queue.  If it is a response, then it has been
picked up from the network and put on your processing queue.  From your
viewpoint, requests are now destined downstream subject to overload
control.  Similarly, responses are to be processed to extract overload
control information and proxied upstream.

With this context, see if things make more sense.

- vijay

---

From: Adam Roach <[email-masked]>
Date: Thu, 08 Mar 2012 14:04:14 -0600

> With this context, see if things make more sense.

No, because there's a lot of processing that needs to take place between 
receipt of a message and sending that same message. This is complicated 
by the fact that proxies can, for example, fork requests.

I think what we really want here is to show one loop that demonstrates 
how the entity (proxy or user agent) handles messages that are going to 
the network. Then, separately, we should show a different loop that 
handles messages coming from the network.

I suspect we're not going to get untangled from the axle otherwise.

/a

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Thu, 08 Mar 2012 14:27:13 -0600

On 03/08/2012 02:04 PM, Adam Roach wrote:
> No, because there's a lot of processing that needs to take place
> between receipt of a message and sending that same message.

Absolutely, however showing all of that processing will simply detract
from showcasing the overload control behaviour in an example
algorithm.  We have to abstract out a lot of information to keep the
focus on the overload control part of the algorithm.

> This is complicated by the fact that proxies can, for example, fork
> requests.

Sure, and this can be trivially handled by applying the overload control
to each branch, and generating a local response if a particular branch
belongs to a server that is under overload, and caching that response
until all branches have responded, and then doing response aggregation
to choose the best response, etc.  But again, we do not have to show
all of this in a reference algorithm.  Showing all of this processing
detracts from the main message of the reference algorithm, which should
be to highlight which messages are dropped and how that choice is made.

> I think what we really want here is to show one loop that
> demonstrates how the entity (proxy or user agent) handles messages
> that are going to the network. Then, separately, we should show a
> different loop that handles messages coming from the network.

Then you straddle the processing between two event loops and folks
will have questions on their execution model --- are they executing
in the same thread, different threads?  I suspect that this
will become just as complex as the current reference algorithm is.

> I suspect we're not going to get untangled from the axle otherwise.

I'd respectfully urge you one more time to see if you can make sense
with the context that get_sip_msg() picks up the next SIP message from
its processing queue to focus on the overload control part.  But if
that is still not clear, then I am open to suggestions on how to
proceed.  I can work with you to break this up into two processing
loops and see if they make things more understandable.

Thanks,

- vijay

---

From: Eric McMurry <[email-masked]>
Date: Thu, 8 Mar 2012 14:31:31 -0600

I agree with this sentiment.  I think I (and probably Adam) were coming from the assumption that the algorithm described in 6.3 was for clients, based on the start of the section:

   This section describes a default algorithm that a SIP client can to
   throttle SIP traffic going downstream by the percentage loss value
   specified in the "oc" parameter.

(btw, there is a grammar issue in the first sentence)

taken as a client algorithm, it only made sense to me if it described the clients *sending* behavior, which is what I was trying to call out in my first message.  As you and Adam have pointed out, there are different behaviors for different elements in the network.  The UAC and UAS can not necessarily be described with the same algorithm (at least not clearly).  Proxies are another mater also as their behavior is potentially more complex.

So let's consider what the interesting cases are that warrant putting ink to the algorithm.  There are several cases to look at:

* sending from an client endpoint
* receiving at an client endpoint

* receiving at a server endpoint
* sending from a server endpoint

* receiving from a client endpoint at an intermediary
* sending to a client endpoint at an intermediary
* receiving from a server endpoint at an intermediary
* sending to a server endpoint at an intermediary

Since this is only for hop-by-hop, I have not listed all possibilities.  I am also limiting the scope of this discussion to the loss-based default algorithm, and not including others or anything else such as algorithm negotiation.  Working our way down the list:

* sending from an client endpoint
The behavior here is more complex than can be described in a couple of sentences and would be made more clear with an algorithmic description.  The modifications to the algorithm in 6.3 from Adam fit the bill here.

* receiving at an client endpoint
I think this can be described clearly in natural language.

* receiving at a server endpoint
I think this can be described clearly in natural language.

* sending from a server endpoint
I think this can be described clearly in natural language.

* receiving from a client endpoint at an intermediary
I think this can be described clearly in natural language.

* sending to a client endpoint at an intermediary
When the intermediary is a proxy, the behavior here is potentially complex.  I think this would be made more clear with an algorithmic description.

* receiving from a server endpoint at an intermediary
When the intermediary is a proxy, the behavior here is potentially complex.  I think this would be made more clear with an algorithmic description.  It may make sense to cover this in conjunction with the algorithm for sending to a client endpoint from a proxy.

* sending to a server endpoint at an intermediary
I think this can be described clearly in natural language.

So, I think a couple of algorithms are in order.  The first provided by the doc along with Adam's modifications, and a second describing proxy behavior.

On Mar 8, 2012, at 14:04 , Adam Roach wrote:

> No, because there's a lot of processing that needs to take place between receipt of a message and sending that same message. This is complicated by the fact that proxies can, for example, fork requests.
> 
> I think what we really want here is to show one loop that demonstrates how the entity (proxy or user agent) handles messages that are going to the network. Then, separately, we should show a different loop that handles messages coming from the network.
>

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Thu, 08 Mar 2012 14:48:28 -0600

On 03/08/2012 02:31 PM, Eric McMurry wrote:
> I agree with this sentiment.  I think I (and probably Adam) were
> coming from the assumption that the algorithm described in 6.3 was
> for clients, based on the start of the section:
>

Eric: Understood.  However, because SIP is so rich, a SIP client
could be part of the proxy as well.  When I was doing work in the
sipclf specification, I was told to simply call it a SIP client
instead of "the SIP client part of a proxy..."

Of course, I can make it clear in the overload draft that wherever
"SIP client" is mentioned, it could mean a SIP UAC or proxy.

[...]
> So, I think a couple of algorithms are in order.  The first provided
> by the doc along with Adam's modifications, and a second describing
> proxy behavior.

My contention is that the algorithm in the document and the one I
modified based on your and Adam's input is the most general algorithm;
i.e., one corresponding to the proxy processing (I can add more
background text saying that get_sip_msg() gets a SIP message from the
proxy's processing queue, etc.)  If we do a decent job at specifying
the most complex of the algorithms, implementers will know what to
do for the simpler cases.

Now the question is, did we (or I) do a decent job of specifying the
most complex of the algorithms?  I think I did, but it is clear that
there is still some work to be done.

I fear that providing multiple algorithms or descriptions will simply
create more questions and problems.  The focus should be on the
overload control behaviour vis-a-vis percentage of messages to drop and
what to do when there aren't enough of category 1 messages, etc.  The
redone algorithm I posted that includes your and Adam's comments
improves on the one in the document, I believe.  But clearly, we all
have to consent that it is good enough so we can get the work finished.

Thanks,

- vijay

---

From: Adam Roach <[email-masked]>
Date: Thu, 08 Mar 2012 15:28:52 -0600

> loops and see if they make things more understandable.

If you're really concerned about the concurrency implications of showing 
this as two different loops, I'm okay collapsing it into a single loop 
servicing a work queue. But we really need to be clear about where the 
messages are coming from.

I think you really do want to show something that works for both user 
agents and for proxies. I don't think most implementors will be able to 
adapt what you have right now into something applicable to user agents. 
On the other hand, if you split things up to handle message receipt 
separately from message sending, then use in a user agent context 
becomes much clearer.

What's nice about doing it that way is that it allows you to completely 
ignore the complexities of proxy message handling (e.g. forking) by 
hiding them behind the "process_msg" function.

So, here's what I propose. It's based heavily on your most recent code, 
but it handles inbound and outbound messages separately and explains 
where the SIP messages are coming from:

while (true)
{
   // We're modeling message processing as a single work queue
   // that contains both incoming and outgoing messages.
   sip_msg := get_next_message_from_work_queue()

   switch (sip_msg.type) {

     case outbound request:

       if (oc_context == null)  {
           send_to_network(sip_msg) // Process it normally by sending the
           // request to the next hop since this particular destination
           // is not subject to overload
       }
       else  {
          // Determine if server wants to enter in overload or is in
          // overload
          in_oc := extract_in_oc(oc_context)

          if (in_oc == false or oc_validity is not in effect)  {
             send_to_network(sip_msg) // Process it normally by sending the
              // request to the next hop since this particular destination
              // is not subject to overload.  Optionally, clear
              // the oc context for this server (not shown).
          }
          else  {
             category := assign_msg_to_category(sip_msg)
             drop_msg := false
             pct_to_reduce := min(100, oc_value / cat1 * 100)

             r := random()
                drop_msg := true
             }

             if (category == cat2 && drop_msg == true)  {
                if (local_policy(sip_msg, oc_value) says process message) {
                    drop_msg := 0  // See Note 1 below
                }
             }

             if (drop_msg == false) {
                 send_to_network(sip_msg) // Process it normally by sending
                // the request to the next hop
             }
             else  {
                // Do not send request downstream, handle locally by
                // generating response (if a proxy) or treating as
                // an error (if a user agent).
             }
          }
       }

     end case // outbound request

     case outbound response:
       if (we are in overload) {
         add_overload_parameters(sip_msg)
       }
       send_to_network(sip_msg)

     end case // outbound response

     case inbound response:

     end case // inbound response

     case inbound request:

        if (sip_msg does not have oc parameter values &&
            we are in overload)  {
          r := random()
          if (r <= our overload metric that we're advertising) {
            send_response(sip_msg, 503)
          }
          else {
            process_msg(sip_msg)
          }

        }

     end case // inbound request

   }
}

I have at least one other major issue I think needs to be fixed, but I 
don't want to throw it into the mix until we have preliminary agreement 
on how we break up the processing.

/a

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Fri, 09 Mar 2012 13:40:05 -0600

On 03/08/2012 03:28 PM, Adam Roach wrote:
> where the SIP messages are coming from:  [...]

Adam: Sorry for the delay, was tied up in meetings.

I went through your proposal of breaking the processing down.
I am fine with it, however, I think there are some nuances in the
"case inbound request" that we need to be more intelligent about.

I think something along the following lines should be specified for
that case:

...
case inbound request:

if (we are not in overload)  {
    process_msg(sip_msg)
}
else {  // We are in overload
    if (sip_msg has oc parameters)  {  // Upstream client supports oc
       process_msg(sip_msg)  // and only sends important requests
    }
    else {  // Upstream client does not support oc
       if (local_policy(sip_msg) says process message)  {
          process_msg(sip_msg)
       }
       else  {
          send_response(sip_msg, 503)
       }
    }
}

Here, if the above code is being executed by an overloaded
proxy and the upstream client does not support overload, then the
proxy has to consult local policy on what to do.  If local policy
says process the request, then the request gets added to the work
queue and re-appears back in the event loop and is handled by the
"case outbound request" part of the code.

If the above code is being executed by a terminal UAS under the same
conditions (i.e., UAS is overloaded and the upstream client does
not support overload), then local policy can decide whether to
accept that request or send a 503.

Thoughts?

Thanks,

- vijay

---

From: Adam Roach <[email-masked]>
Date: Fri, 09 Mar 2012 14:10:44 -0600

> accept that request or send a 503.

That sounds good to me.

/a

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Fri, 09 Mar 2012 14:20:43 -0600

> That sounds good to me.

Adam: OK, thanks.

So, I can release a new revision with the updated algorithm (we still
have Monday left to submit).  I will do so unless I hear otherwise
before Monday.

Thank you (and Eric) for helping flesh out the algorithm with the
various cases.

- vijay