Subject: [sipcore] "Gaps" in call flows

From: [email-masked] (Dale R. Worley)
Date: Wed, 24 Oct 2012 19:07:25 -0400 (EDT)

As I see it, the central pivot of the problem is this:  What does a
proxy do when it receives a response that contains a "duplicate"
hi-entry?  (That is, an hi-entry whose index is the same as in a
previously received hi-entry, but whose URI is different.)  (The two
responses involved necessarily are generated by different forks made
by a non-supporting proxy, and will come from two different elements,
or at least, two different proxy transactions.)

Actually, the problem is messier than a single duplicate hi-entry, as
each of the duplicate hi-entries can have "child" hi-entries.  For
example, one response can contain:

    History-Info: ..., 
                  <a.example.com>;index=1.1.0.1, 
                  <e.a.example.com>;index=1.1.0.1.1,
                  <h.e.a.example.com>;index=1.1.0.1.1.1,
                  <i.e.a.example.com>;index=1.1.0.1.1.2

and the other can contain:

    History-Info: ..., 
                  <b.example.com>;index=1.1.0.1, 
                  <g.b.example.com>;index=1.1.0.1.1,
                  <n.g.b.example.com>;index=1.1.0.1.1.1

"At the top level", <a.example.com> and <b.example.com> are
duplicates, but they have the corresponding (with index 1.1.0.1.1.1)
child duplicates <h.e.a.example.com> and <n.g.b.example.com>, and the
hi-entry with index 1.1.0.1.1.2 <i.e.a.example.com> is affected by the
duplication despite not being a duplicate itself.

The first consideration is that we can't avoid the problem.  All
proposals that have been discussed will cause this situation, at least
occasionally, when a supporting proxy forwards a request to a
non-supporting proxy, which forks the request to two supporting
elements.

One alternative is for the RFC to say nothing about handling the
situation.  This is dangerous, because the text leaves the strong
impression that the index of an hi-entry uniquely determines the URI,
and the needed processing naturally suggests using data structures
that depends on this uniqueness.  So if we say nothing, it is likely
that implementations will crash when they encounter this problem.

So we need to warn the implementer about this problem.  There are two
obvious alternatives that an implementer can choose.

One choice is for the implementation to keep one hi-entry and discard
the other hi-entry (and to discard the "child" hi-entries of that
other hi-entry).  The cache is still keyed by the index values, but
when there is a duplication, one of the duplicate hi-entries is lost.
This approach loses information, but results in a History-Info header
that conforms to everyone's expectations.  In the above example, the
History-Info in the proxy's response would be one of the two received
response History-Infos.

The other choice is for the implementation to keep both hi-entries.
This requires a different data structure for the cache, and causes the
proxy to send History-Info that contain duplicate hi-entries.  These
duplicate hi-entries in a single response create cascading
duplications upstream.  This choice also raises the question of how
the hi-entries are to be ordered in History-Info, since the prescribed
tree preorder assumes that indexes are unique.

In the above example, we could place the two index-1.1.0.1 hi-entries
as siblings and have their children follow in tree order:

    History-Info: ..., 
                  <a.example.com>;index=1.1.0.1, 
                  <e.a.example.com>;index=1.1.0.1.1,
                  <h.e.a.example.com>;index=1.1.0.1.1.1,
                  <i.e.a.example.com>;index=1.1.0.1.1.2,
                  <b.example.com>;index=1.1.0.1, 
                  <g.b.example.com>;index=1.1.0.1.1,
                  <n.g.b.example.com>;index=1.1.0.1.1.1

or we could sort the hi-entries by their index values, which is what
the current text seems to demand:

    History-Info: ..., 
                  <a.example.com>;index=1.1.0.1, 
                  <b.example.com>;index=1.1.0.1, 
                  <e.a.example.com>;index=1.1.0.1.1,
                  <g.b.example.com>;index=1.1.0.1.1,
                  <h.e.a.example.com>;index=1.1.0.1.1.1,
                  <n.g.b.example.com>;index=1.1.0.1.1.1,
                  <i.e.a.example.com>;index=1.1.0.1.1.2

In any case, it becomes more difficult for a UAS application to
extract knowledge about the origin of the request that it received --
if hi-entries are discarded, information is inevitably lost; if
duplicates are preserved, parameters referencing indexes are
inevitably ambiguous.

It seems to be safer for the RFC to specify that one or the other
approach is required in proxies, so that all proxies handle duplicates
consistently, and applications can depend on that.

It seems to be safer to require that the proxy discard one duplicate
(and all its children), because that approach never generates
History-Info values that contain duplicates -- there is less
information in History-Info, but the structure of History-Info is not
made more complex, and the way to interpret it is unambiguous.

Regardless of how we prescribe that a proxy should handle duplicates,
it is clear that we want to minimize the chances of duplicates
happening, since duplicates unavoidably result in loss of information.

Within this context, we can discuss how we would like to handle
"gaps", as that affects how often duplicates will be seen.

One approach is to not mark gaps at all, which is the approach in RFC
4244.  This results in duplicates being generated every time a call
passes through the troublesome situation:  a supporting proxy forwards
a request to a non-supporting proxy, which forks the request to two
supporting elements.  Additionally, the existence of the gap is not
flagged at all.

The approach in the draft is to represent gaps by inserting "0" as a
number in the index.  This is an improvement relative to RFC 4244,
because the presence of gaps are marked explicitly, but it does not
reduce the number of duplicates:  duplicates are generated by every
call that passes through the troublesome situation.

Another approach is to represent gaps by a randomly-chosen number from
a suitably large range.  If the specified range does not overlap the
branch numbers that are generated in normal situations, gaps are
flagged explicitly.  In addition, the number of duplicates can be
reduced to whatever degree is desired, since duplicates only happen
when two random numbers happen to be the same -- with high
probability, even in the troublesome situation, two responses will not
not contain duplicates, and the proxy will assemble a History-Info
that unambiguously presents all the information that it received.

Dale

---

From: Mary Barnes <[email-masked]>
Date: Thu, 25 Oct 2012 09:14:03 -0500

I believe the best and most appropriate approach is to include this in the
application considerations section. The addition of the hi-entries is
mechanical and it's not up to a proxy to determine validity of the
information.  I don't think we should add normative text around this.  You
need to keep in mind that one use case for HI is debug, so you really don't
want to muck with the entries or synthesize the information so that it's
compatible for a specific application.  Note that even with the duplicates
there is value in the ordering and it's up to an application to decide
whether it needs the "last set of entries associated with a duplicate index
or a previous set.  My guess is that the last set would be the usual and
again, we could add a note about that in the application considerations
section.  I think we need to be very careful about changing the normative
text without a solid reason that is consistent with the intent of 4244bis
which is described in the section summarizing the differences.

I think complicating the creation of the index is a really bad idea and
well beyond the intent of 4244 or 4244bis.

Regards,
Mary.

On Wed, Oct 24, 2012 at 6:07 PM, Dale R. Worley <[email-masked]> wrote:

> _______________________________________________
> sipcore mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sipcore
>

---

From: Paul Kyzivat <[email-masked]>
Date: Thu, 25 Oct 2012 12:22:38 -0400

On 10/25/12 10:14 AM, Mary Barnes wrote:
> I believe the best and most appropriate approach is to include this in
> the application considerations section. The addition of the hi-entries
> is mechanical and it's not up to a proxy to determine validity of the
> information.  I don't think we should add normative text around this.
>   You need to keep in mind that one use case for HI is debug, so you
> really don't want to muck with the entries or synthesize the information
> so that it's compatible for a specific application.  Note that even with
> the duplicates there is value in the ordering and it's up to an
> application to decide whether it needs the "last set of entries
> associated with a duplicate index or a previous set.  My guess is that
> the last set would be the usual and again, we could add a note about
> that in the application considerations section.

Which set should be the "last set" among those with duplicate indexes?

	Thanks,
	Paul (as individual)

> I think we need to be
> very careful about changing the normative text without a solid reason
> that is consistent with the intent of 4244bis which is described in the
> section summarizing the differences.
>
> On Wed, Oct 24, 2012 at 6:07 PM, Dale R. Worley <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>                        <a.example.com <http://a.example.com>>;index=1.1.0.1,
>                        <e.a.example.com
>     <http://e.a.example.com>>;index=1.1.0.1.1,
>                        <h.e.a.example.com
>     <http://h.e.a.example.com>>;index=1.1.0.1.1.1,
>                        <i.e.a.example.com
>     <http://i.e.a.example.com>>;index=1.1.0.1.1.2
>
>                        <b.example.com <http://b.example.com>>;index=1.1.0.1,
>                        <g.b.example.com
>     <http://g.b.example.com>>;index=1.1.0.1.1,
>                        <n.g.b.example.com
>     <http://n.g.b.example.com>>;index=1.1.0.1.1.1
>
>     "At the top level", <a.example.com <http://a.example.com>> and
>     <b.example.com <http://b.example.com>> are
>     child duplicates <h.e.a.example.com <http://h.e.a.example.com>> and
>     <n.g.b.example.com <http://n.g.b.example.com>>, and the
>     hi-entry with index 1.1.0.1.1.2 <i.e.a.example.com
>     <http://i.e.a.example.com>> is affected by the
>                        <a.example.com <http://a.example.com>>;index=1.1.0.1,
>                        <e.a.example.com
>     <http://e.a.example.com>>;index=1.1.0.1.1,
>                        <h.e.a.example.com
>     <http://h.e.a.example.com>>;index=1.1.0.1.1.1,
>                        <i.e.a.example.com
>     <http://i.e.a.example.com>>;index=1.1.0.1.1.2,
>                        <b.example.com <http://b.example.com>>;index=1.1.0.1,
>                        <g.b.example.com
>     <http://g.b.example.com>>;index=1.1.0.1.1,
>                        <n.g.b.example.com
>     <http://n.g.b.example.com>>;index=1.1.0.1.1.1
>
>                        <a.example.com <http://a.example.com>>;index=1.1.0.1,
>                        <b.example.com <http://b.example.com>>;index=1.1.0.1,
>                        <e.a.example.com
>     <http://e.a.example.com>>;index=1.1.0.1.1,
>                        <g.b.example.com
>     <http://g.b.example.com>>;index=1.1.0.1.1,
>                        <h.e.a.example.com
>     <http://h.e.a.example.com>>;index=1.1.0.1.1.1,
>                        <n.g.b.example.com
>     <http://n.g.b.example.com>>;index=1.1.0.1.1.1,
>                        <i.e.a.example.com
>     <http://i.e.a.example.com>>;index=1.1.0.1.1.2
>
>     [email-masked] <mailto:[email-masked]>

---

From: Mary Barnes <[email-masked]>
Date: Thu, 25 Oct 2012 14:57:52 -0500

> Which set should be the "last set" among those with duplicate indexes?
[MB] The hi-entries are added in order of the message processing which MUST
be maintained per the requirements and per the definition of the index
(same for 4244). We could add a note in that definition that it is possible
in cases of gaps to have the same index but the chronological order must
still be maintained.  [/MB]

>>                        <a.example.com <http://a.example.com>>;index=**
>> 1.1.0.1,
>>                        <e.a.example.com
>>     <http://e.a.example.com>>;**index=1.1.0.1.1,
>>                        <h.e.a.example.com
>>     <http://h.e.a.example.com>>;**index=1.1.0.1.1.1,
>>                        <i.e.a.example.com
>>     <http://i.e.a.example.com>>;**index=1.1.0.1.1.2
>>
>>
>>                        <b.example.com <http://b.example.com>>;index=**
>> 1.1.0.1,
>>                        <g.b.example.com
>>     <http://g.b.example.com>>;**index=1.1.0.1.1,
>>                        <n.g.b.example.com
>>     <http://n.g.b.example.com>>;**index=1.1.0.1.1.1
>>
>>                        <a.example.com <http://a.example.com>>;index=**
>> 1.1.0.1,
>>                        <e.a.example.com
>>     <http://e.a.example.com>>;**index=1.1.0.1.1,
>>                        <h.e.a.example.com
>>     <http://h.e.a.example.com>>;**index=1.1.0.1.1.1,
>>                        <i.e.a.example.com
>>     <http://i.e.a.example.com>>;**index=1.1.0.1.1.2,
>>                        <b.example.com <http://b.example.com>>;index=**
>> 1.1.0.1,
>>                        <g.b.example.com
>>     <http://g.b.example.com>>;**index=1.1.0.1.1,
>>                        <n.g.b.example.com
>>     <http://n.g.b.example.com>>;**index=1.1.0.1.1.1
>>
>>
>>                        <a.example.com <http://a.example.com>>;index=**
>> 1.1.0.1,
>>                        <b.example.com <http://b.example.com>>;index=**
>> 1.1.0.1,
>>                        <e.a.example.com
>>     <http://e.a.example.com>>;**index=1.1.0.1.1,
>>                        <g.b.example.com
>>     <http://g.b.example.com>>;**index=1.1.0.1.1,
>>                        <h.e.a.example.com
>>     <http://h.e.a.example.com>>;**index=1.1.0.1.1.1,
>>                        <n.g.b.example.com
>>     <http://n.g.b.example.com>>;**index=1.1.0.1.1.1,
>>                        <i.e.a.example.com
>>     <http://i.e.a.example.com>>;**index=1.1.0.1.1.2
>>
>>
>>     ______________________________**_________________
>>     sipcore mailing list
>>     https://www.ietf.org/mailman/**listinfo/sipcore<https://www.ietf.org/mailman/listinfo/sipcore>
>>
>>
>>
>>
>>
>> ______________________________**_________________
>> sipcore mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/**listinfo/sipcore<https://www.ietf.org/mailman/listinfo/sipcore>
>>
>>
> ______________________________**_________________
> sipcore mailing list
> [email-masked]
> https://www.ietf.org/mailman/**listinfo/sipcore<https://www.ietf.org/mailman/listinfo/sipcore>
>

---

From: Paul Kyzivat <[email-masked]>
Date: Thu, 25 Oct 2012 16:51:48 -0400

On 10/25/12 3:57 PM, Mary Barnes wrote:
>
>
> On Thu, Oct 25, 2012 at 11:22 AM, Paul Kyzivat <[email-masked]
> <mailto:[email-masked]>> wrote:
>
> [MB] The hi-entries are added in order of the message processing which
> MUST be maintained per the requirements and per the definition of the
> index (same for 4244). We could add a note in that definition that it is
> possible in cases of gaps to have the same index but the chronological
> order must still be maintained.  [/MB]

My point is that the order will end up being arbitrary.
IIUC, to get duplicates, the forking must have occurred in a proxy that 
doesn't support H-I. The duplicates will come in responses. The node 
detecting the duplicates will only know in which order it received the 
responses, but not the order in which the requests that yielded those 
responses were sent. Meanwhile, AFAIK the ordering by nodes supporting 
H-I will be by when the requests were sent.

Maybe it doesn't matter - it really is arbitrary. But nobody should be 
deluded into thinking that the order among duplicates has any significance.

	Thanks,
	Paul

---

From: Mary Barnes <[email-masked]>
Date: Thu, 25 Oct 2012 16:30:36 -0500

On Thu, Oct 25, 2012 at 3:51 PM, Paul Kyzivat <[email-masked]> wrote:

>> <mailto:[email-masked]>**> wrote:
>>
> responses were sent. Meanwhile, AFAIK the ordering by nodes supporting H-I
> will be by when the requests were sent.
>
[MB2]  If the forking comes from nodes that don't support HI then an
application that needs 4244bis compliant entries would just ignore those or
provide limited functionality.[/MB2]

> deluded into thinking that the order among duplicates has any significance.
[MB] In the case of forking, the order is always arbitrary in the
responses.  There's no way around that - again we're dealing with the lack
of consistency with forking in SIP.  HI is only as deterministic/consistent
as SIP message ordering itself.[/MB]