Subject: RE: SIP Request Glare.

From: "Kelley, Kalon" <[email-masked]>
Date: Fri, 24 Mar 2000 13:59:56 -0500

Robert:

I agree completely with your assertion that the current glare resolution
mechanism seems inadequate, for most of the reasons you cited.

I've got to admit that I didn't even notice that the specification states
that the specified Retry-After delay must be an integer number of seconds,
which, as you clearly demonstrate, requires the introduced delay to be
unacceptably large.  Even if this requirement were relaxed, however, the
introduced random back-off must still be large enough to ensure that the
difference between both sides' random delays will almost always exceed the
time it takes to transmit the message across the network (so that one side
will receive the other side's invitation before sending its own.)  I suspect
that this means that the introduced delay will often exceed the maximum
acceptable "second or two".

I don't know what most implementers are doing at present.  I suspect the
issue hasn't come up a lot because the rate of incidence of crossing INVITEs
in point-to-point communications is probably quite low.  I believe, however,
that the problem is more common in multipoint conferences with decentralized
control, which is what brought the problem to my attention.

We've introduced an alternate proposal in a recent I-D (see, in particular,
section 7 of http://www.ietf.org/internet-drafts/draft-mark-sip-dmcs-00.txt)
that attempts to address the problem.  Loosely, our proposal entails
comparing the URIs used in the To and From fields of the INVITEs as the
basis for comparison.  The party whose URI is lesser is designated the
victor when crossing INVITEs arise.

This solution DOES starve one of the parties in this situation, contrary to
your stated requirements (in our draft, we consequently describe it as a
non-egalitarian approach.)  Although I'm not sure that a more egalitarian
approach is really required, we describe other approaches in section 7.5 of
the draft that respect this additional requirement.  Your Retry-Resolve
proposal is a specific implementation of one of the options we enumerate
there.

Is there a compelling reason why you believe that neither party should be
consistently favored?  If so, I'd readily embrace something akin to the
Retry-Resolve approach.  (It may be possible to do this without introducing
a new header; our draft describes an extension to our URI-comparison
proposal that uses CSeq values to eliminate concerns about starvation.)

Regards,

Kalon Kelley
Intel Dialogic Division
mailto:[email-masked]
http://www.dialogic.com/

> -----Original Message-----
> From: Fairlie-Cuninghame, Robert [mailto:[email-masked]]
> Sent: Thursday, March 23, 2000 11:53 PM
> To: [email-masked]'
> Subject: SIP Request Glare.
> 
> 
> 
> I refer to the clarification on "The SIP Page":
> 
> ---
> 	CSeq
> 	The spec is not clear on whether both parties "share" the CSeq
> space. In other words, if A sends an INVITE to B with CSeq: 
> 0, and then B
> sends a BYE to A, does B need use CSeq:1 in its BYE? Answer: 
> no. The CSeq
> space is maintained independently in both directions. This 
> raises a state
> inconsistency issue. Lets say A and B are in a call, and A 
> sends a re-INVITE
> to B at the same time B sends it to A. It is possible that 
> the transactions
> complete in different orders at A and B, yielding an 
> inconsistent view of
> the session state. This is similar to the "glare" problem in 
> telephony. The
> solution: if A has a transaction pending (pending = no final response
> received), and a request from the remote side arrives, it 
> should send a 500
> response (possibly with a Retry-After randomly generated to 
> enable back-
> off). This should (??) guarantee ordered completion of transactions. 
> ---
> Firstly concerning, request ordering and pending requests: Does order
> consistency condition extend to other methods, such as glare between
> METHOD-INFO & INFO-INFO request for example ? If not, then 
> INFO and INVITE
> methods must be able execute independently (that is, you 
> could have multiple
> active requests: an INVITE and an INFO, or two INFOs). What 
> is the correct
> handling of this situation ? 
> 
> Now regarding glare resolution: Is the proposed glare 
> resolution solution
> acceptable in a telephony environment? The granularity of 
> Retry-After is in
> seconds. So to have a reasonable chance of not colliding 
> again you must make
> the random range large; yet it is unacceptable to have a 
> delay any more than
> a second or two in most telephony applications. For instance 
> if the random
> range of Retry-After is up to three seconds, then this only 
> allows three
> random outcomes => leading to a roughly 33% chance of re-collision.
> Additionally, even for this small value of Retry-After there 
> is roughly only
> a 66% chance that a request will commence within 2 seconds 
> (which is still
> unacceptable in many situations). Whether or not you have a 
> small or large
> random range for Retry-After doesn't help because of the lack 
> of random
> granularity.
> 
> We need a glare resolution that completes resolves quickly, 
> does not starve
> one side and has little chance of recollision. 
> 
> One possible solution might be to include a header field with 
> a 32bit random
> value ( eg Retry-Resolve?). Both sides can use this value to 
> quickly resolve
> the glare and the winner could instantly retransmit.
> 
> I am not sure if I have "gone off the rails" somewhere along 
> the way but to
> me it seems like this is a pretty big hole in the protocol. 
> What are people
> doing at the moment?
> 
> Cheers,
> 
> Robert.

---

From: "Fairlie-Cuninghame, Robert" <[email-masked]>
Date: Mon, 27 Mar 2000 02:06:57 -0800

> Well, how about we add random granularity? We could simply 
> say that both
> sides should retry within a random time distributed between 0 and some
> number. This number has to be chosen large enough to reduce the
> probability of collision again, but small enough to make the re-invite
> resolve quickly. Glare happens again if both sides choose a number
> within 1/2 RTT of each other. Lets say 1/2 RTT = 50ms. If we want the
> re-glare case to happen with < 5% probability, choosing the number
> randomly between 0 and 1 second should work.
> 
> This solution doesn't require an extension. Its not as fast as above,
> but its not as complex.
> 
That sounds reasonable but the clients must be able to differentiate this
glare situation from a normal 500 server overload response. Are you
proposing to send a "Retry-After: 0" or "Retry-After: 1" to indicate that
the client should retry after a small random delay? This scheme would still
require the clients to understand the "extension".

Maybe my math's is wrong but for RTT=100ms with a random retransmit range of
0-1 second isn't the chance of recollision equal to (0.95 * 100ms) + (0.05 *
(0.75 * 100ms)) = 8.75%. 

Is this solution acceptable for connections where the RTT is larger?
Consider a ½ RTT of 150 ms which is a quite noticeable but  tolerable delay
for voice media, however, the actual SIP RTT may be quite larger than the
media path. Now, if we chose 1 second for the random retransmit range I
believe this gives a chance of recollision of around 28%.  500ms RTT -> ~44%
(if my maths is correct). Loaded proxies and the like could conceivably
create an even longer SIP RTT, no ? 

Including the Retry-Resolve header separately and additionally to the
Retry-After means that a client which does not understand the former can
simply use the latter (and also differentiates glare from normal 500 server
internal errors). 
Can you see any flaws in the following scheme: After sending a 500 response
with Retry-After _and_ Retry-Resolve header, the client waits for a 500
response. If the inbound 500 response 
-	does contain a Retry-Resolve header
-	and the reverse CSeq in the Retry-Resolve matches the outbound
glaring request (see below) 
-	and the received Retry-Resolve random discriminator value is smaller
than the outbound value
then the response is immediately retransmitted; or otherwise the client
waits the full Retry-After duration before retransmitting (or terminates the
session).

I agree that the Retry-Resolve header needs to include the reverse glaring
request Cseq to eliminate certain race conditions (as you described).

For example: "Retry-Resolve:" <random descriminator> <reverse Cseq number>
<reverse Cseq method>. 

Can you see any holes in this scheme? Does this sound too complex or
incompatible with the current scheme? Is it worth it ? I believe that the
existence of methods to _robustly_ resolve problems such as glare are
important for overall confidence in a protocol - even if glare is normally
deemed an unlikely event.

Regards,

Robert.

---

From: "Kelley, Kalon" <[email-masked]>
Date: Mon, 27 Mar 2000 20:30:11 -0500

Jonathan:

Thanks for turning your critical eye to this proposal.  Your points are
well-taken.  Further comments are interspersed below.

Jonathan Rosenberg wrote:
> 
> Regarding the glare issue, Kelly later writes:
> > section 7 of 
> http://www.ietf.org/internet-drafts/draft-mark-sip-dmcs-00.txt)
> I'm afraid this solution does not work as specified. It only works if
> both sides agree they are in a glare situation. Consider the following
> case. A sends a reinvite to B. B receives it, and responds with a 200.
> This response takes a while to get to A. Now, B sends a re-INVITE to A
> (as far as B is concerned, the reinvite it received has been responded
> to, thus there is no glare, and it can send a new re-INVITE). 
> A receives
> that re-invite. A thinks there is glare, and decides its the 
> winner, so
> it responds w/ a 200 OK. Then, A gets the non-500 response 
> from B. Now A
> is really confused.
> 
> You could argue that B shouldn't even send that re-INVITE 
> until the ACK
> is received for the re-INVITE B got first. 

This is probably what I would argue.  However, it sounds like you're
uncomfortable with this.  What drawbacks are there to this requirement?

> However, there is still a
> race condition that makes it not work, although its less likely. Heres
> the case: A sends a re-invite to B that gets lost. B sends a re-invite
> to A. A sees glare, and decides B should win, so it responds 
> with a 200
> OK. B ACKs, and A gets the ACK. Then, that lost reinvite 
> arrives at B. B
> thinks everything is fine, since the previous reinvite it 
> sent has been
> ACKed. So, it sends a 200 OK. Now, A is once again confused.

Excellent catch.  Could we deal with this case by requiring the party that
is not the victor (here A) to CANCEL its re-INVITE (and wait until receiving
a response to that CANCEL) prior to accepting the victor's INVITE?  This
would keep the above situation from occurring, since by the time B receives
A's re-INVITE it will necessarily have received A's cancellation thereof.
In the event that a response to the CANCEL is not received within a
reasonable period of time, the client can resort to the basic back-off
Retry-After approach. (My initial instinct is to eliminate the separate
CANCEL step by having A somehow communicate the implied glare cancellation
by adding a header or other mechanism for passing the CSeq of its own
(losing) re-INVITE request in its 200 response to B's re-INVITE, but this
clearly suffers from the same lack of backwards compatibility you note in
conjunction with your fix below.)  

An unknown for me with such a solution is whether or not UASs are expected
to keep track of CANCEL requests for INVITEs they have not received, on the
off-chance that the CANCEL outpaces its INVITE.

> I think this can be fixed if each side includes, in a re-INVITE, the
> CSeq of the request last received from the other party (or -1 or
> something if it hasn't gotten one yet). This will allow each side to
> determine, when it receives a reinvite while reinviting, whether the
> reinvite it sent has been received and responded to by the other side.
> This requires an extension, and its not backwards compatible, which is
> kind of yucky. Below is an alternate solution.

I agree that this fix would work, but may be too "yucky" for the reasons
enumerated.

> > a second or two in most telephony applications. For 
> instance if the random
> > Additionally, even for this small value of Retry-After 
> there is roughly only
> > random range for Retry-After doesn't help because of the 
> lack of random
> > granularity.
> 

I think (modulo my math skills) it may be somewhat worse than this (see also
forthcoming response to Robert's mail.)  In particular, by my calculations
the random time selected must be between 0 and approximately 2.05s in order
to to limit the probability of recollision to 5% given the assumed 1/2 RTT
of 50 ms.

> -Jonathan R.

Thanks again for your insights.

Kalon

Kalon Kelley
Intel Dialogic Division

---

From: "Kelley, Kalon" <[email-masked]>
Date: Tue, 28 Mar 2000 00:38:29 -0500

Robert Fairlie-Cuninghame wrote:

<snip>
> create an even longer SIP RTT, no ? 
<snip>

Robert:

I think your calculations are in the same general ballpark as mine (although
I put the chance of recollision assuming 100ms RTT with a random retransmit
range of 0-1s at 9.75%.)  Coming at it another way, it may be helpful to
calculate the retransmit range required given assumptions about both
expected RTTs and what we believe to be a reasonable level of recollision.

In the following equations:

R = the retransmit range
L = the assumption as to 1/2 RTT
P = the total probability of recollision

Take party A's randomly selected retry-after value.

1.  When it is greater than or equal to 1/2 RTT and less than or equal to
the retransmit range less 1/2 RTT (the probability of this occurrence can be
expressed as (R-2L)/R ), there will be a recollision if party B's
retry-after value is anywhere in the single RTT range beginning with party
A's value less 1/2 RTT and ending with party A's value plus 1/2 RTT (the
probability of this occurrence can be expressed as 2L/R).  Hence, the
probability for recollision in this circumstance can be expressed as:

((R-2L)/R) * (2L/R)

2.  When A's retry-after value is less than L (probability L/R), there will
be a recollision if B's retry-after value is less than A's value plus L.
The combined probability of this event can be integrated over the range of
A's possible retry-after values in this range, yielding a total probability
for this circumstance of ((3/2)*(L^2))/(R^2).

3.  When A's retry-after value is greater than R-L (probability L/R), there
will be a recollision if B's retry-after value is greater than A's value
less L.  As in (2), the total probability for this circumstance is
((3/2)*(L^2))/(R^2).

Therefore, adding these different probabilities yields:

P = (((R-2L)/R) * (2L/R))) + ((3*(L^2))/(R^2))

or (P*(R^2)) - ((2L)*R) + (L^2) = 0

By my calculations, solving for R given L=.05s, and P=.05 yields R of ~1.97s
(I erroneously reported this to be 2.05s in an earlier message.)

Solving for R given L=.15s and P=.05 yields R of ~5.92s.

Obviously it will be important to decide what assumptions are reasonable for
L and P in order to determine whether the random backoff approach is viable.

Please let me know of errors in this equation or computation.

Regards,

Kalon Kelley
Intel Dialogic Division