Subject: Unordered messages and SCTP_FRAGMENT_INTERLEAVE=2

From: Anders Torger <[email-masked]>
Date: Tue, 24 Apr 2007 16:30:16 +0200

With no limits in fragment interleave, there can be several partial 
deliveries going on, one per stream for ordered mode.

However, when it comes to unordered messages, the number of partial 
deliveries could theoretically be more than one for a single stream, or 
is there some limit such that one can guarantee that there is only one 
unordered partial delivery going on per stream?

The current Solaris SCTP implementation seems to interleave the most, 
does anyone know if there can be more than one partial delivery for 
unordered messages on a single stream going on simultaneously?

My assumption so far has been that there is per stream at most one 
partial delivery for an ordered message and one partial delivery for an 
unordered message going on simultaneously, but I just realized that it 
may not be correct.

/Anders Torger

---

From: Randall Stewart <[email-masked]>
Date: Tue, 24 Apr 2007 11:02:27 -0400

> unordered partial delivery going on per stream?

Well an unordered msg DOES have a stream associated with
it even though the ssn means nothing.
The spec (though not binding) does say..
"
Only one message at a time can be partially delivered in any stream.
"
Which implies that you should NOT get more than one PD-API in
any stream no matter if its ordered or unordered.

I know BSD will enforce this..

> unordered messages on a single stream going on simultaneously?

Don't know on solaris.. but BSD won't allow it.. (of course
you must set the level to 2 to get the fragment interleave anyway).

> unordered message going on simultaneously, but I just realized that it 

I think you are correct.. at least the document says so..

R

-- 
Randall Stewart
NSSTG - Cisco Systems Inc.
803-345-0369 <or> 803-317-4952 (cell)

---

From: Mark Butler <[email-masked]>
Date: Tue, 24 Apr 2007 11:11:00 -0600

>unordered message going on simultaneously, but I just realized that it 
That assumption is correct.  That is what level 2 means.

The only way to support multiple partial deliveries on the same stream 
at the same time would be to add a new level 3 to 
SCTP_FRAGMENT_INTERLEAVE, as well as add some sort of synthetic message 
id (such as the start TSN) to the auxilliary receive info.  Otherwise 
there would be no way to attach partial deliveries to the correct message.

I think that would be a nice feature that would be trivial to implement 
and which would allow applications to eliminate an important case of 
head of line blocking problems that would occur even with relatively 
small messages. I can only guess how anyone else feels of course.

 - Mark B.

---

From: Anders Torger <[email-masked]>
Date: Wed, 25 Apr 2007 09:04:01 +0200

Randall,

you (indirectly) say two contradicting things here, first that there 
will only be one message at a time partially delivered per stream, 
regardless if it is unordered or not, and then you say my assumption 
that there can be one ordered and one unordered (=2) partial deliveries 
per stream simultaneously is correct too.

Could you please clarify?

/Anders Torger

On Tuesday 24 April 2007 17:02, Randall Stewart wrote:
> > deliveries could theoretically be more than one for a single
> > stream, or is there some limit such that one can guarantee that
> > there is only one unordered partial delivery going on per stream?
>
> > The current Solaris SCTP implementation seems to interleave the
> > most, does anyone know if there can be more than one partial
> > delivery for unordered messages on a single stream going on
> > simultaneously?
>
> > partial delivery for an ordered message and one partial delivery
> > for an unordered message going on simultaneously, but I just
> > realized that it may not be correct.
>

---

From: Randall Stewart <[email-masked]>
Date: Wed, 25 Apr 2007 06:12:19 -0400

> per stream simultaneously is correct too.

Sorry I was not clear..

> Could you please clarify?

BSD will allow only ONE PD-API per stream. It does not
care if the message is ordered or unordered. Basically if
you set level-2, then there is a stream-started-delivery flag
that gets set when the PD-API begins... no other message will
be delivered for that stream until the PD-API terminates..

This is what I think the spec says as well.. aka:

It does not say "only one ordered and as many unordered as you would
like".. only one message partially delivered in any stream..

Now, I suppose you COULD get a message non-partially delivered in
a stream that was unordered where a PD-API was happening.. i.e.
lets say you

recv() <--- BEGIN stream=1 SSN=3 NO-MSG_EOR
(you are now in PD-API for stream 1)
You migiht get (and still be within the above restriction
recv() <----stream=1 flags=UNORDERED and MSG_EOR

Since the wording above does not prohibit this.. It does
prohibit this though:

recv() <----stream=1 flags=UNORDERED and NO-MSG_EOR

BSD will not do either one.. once you begin delivery in stream 1 you
MUST get all the message before ANY other message in stream 1 will
arrive.

Does that help? ;-D

R

---

From: Randall Stewart <[email-masked]>
Date: Wed, 25 Apr 2007 06:28:08 -0400

Mark Butler wrote:
>> deliveries could theoretically be more than one for a single stream, 
>> or is there some limit such that one can guarantee that there is only 
>> one unordered partial delivery going on per stream?
>>
>> partial delivery for an ordered message and one partial delivery for 
>> an unordered message going on simultaneously, but I just realized that 
>> it may not be correct.
>>  
>>

The whole point of streams is to have ordered delivery.. so if
Msg 1 is in stream 1 and Msg 2 is in stream 1, they are depandant
on each other.. aka 1 needs to be delivered first (of course talking
about ordered messages only though).

The only way such an option would make sense is for unordered messages.

R

---

From: Anders Torger <[email-masked]>
Date: Wed, 25 Apr 2007 13:47:30 +0200

Ok, in other words:

Only one message per stream can be partially delivered, however if the 
partial delivery is of an ordered message, it may be interleaved with a 
full unordered message.

If instead the partial delivery is of an unordered message, it cannot be 
interleaved with a full unordered message (since sinfo_ssn is zero 
there is no support in the API to know if it is the last fragment of 
the partial delivery or if it is a new full message).

Hmm... this seems a bit messy. I don't like the exception for unordered 
messages. If there was a way to separate different unordered messages 
(like the sinfo_ssn for ordered), the rule could be simplified to:

Only one message per stream can be partially delivered, however it can 
be interleaved with a full message on the same stream (an partially 
delivered ordered message interleaved with a full unordered message and 
vice versa).

/Anders Torger

On Wednesday 25 April 2007 12:12, Randall Stewart wrote:
> Anders Torger wrote:
> > Randall,
> >
> > you (indirectly) say two contradicting things here, first that
> > there will only be one message at a time partially delivered per
> > stream, regardless if it is unordered or not, and then you say my
> > assumption that there can be one ordered and one unordered (=2)
> > partial deliveries per stream simultaneously is correct too.
>
> Sorry I was not clear..
>
> >>> With no limits in fragment interleave, there can be several
> >>> partial deliveries going on, one per stream for ordered mode.
> >>>
> >>> However, when it comes to unordered messages, the number of
> >>> partial deliveries could theoretically be more than one for a
> >>> single stream, or is there some limit such that one can guarantee
> >>> that there is only one unordered partial delivery going on per
> >>> stream?
> >>
> >> Only one message at a time can be partially delivered in any
> >> stream. "
> >>> My assumption so far has been that there is per stream at most
> >>> one partial delivery for an ordered message and one partial
> >>> delivery for an unordered message going on simultaneously, but I
> >>> just realized that it may not be correct.
> >>

---

From: Randall Stewart <[email-masked]>
Date: Wed, 25 Apr 2007 08:29:38 -0400

> partial delivery is of an ordered message, it may be interleaved with a 
Not of the same stream though.. basically no matter if its an
ordered or unordered message.. once it starts partial delivery, it
blocks any more messages on that stream from being received.

> (like the sinfo_ssn for ordered), the rule could be simplified to:

There is no exception that I read in the spec..

only one message in a stream can be partially delivered.

Please tell me what is unclear about this.. unordered messages are
also assigned a stream number..

R

---

From: Anders Torger <[email-masked]>
Date: Wed, 25 Apr 2007 14:19:11 +0200

Sorry for replying to myself, but I just found out that it does not seem 
to messy if I change the wording:

- Only one message per stream can be partially delivered.
- A partially delivered message can be interleaved with a full message
  with opposite order mode on the same stream.
     - That is an ordered partial delivery can be interleaved with a 
       full unordered message and vice versa. But an unordered partial
       delivery cannot be interleaved with a full unordered message.

There is a small head-of-line blocking introduced here in the API for 
unordered messages, but I guess it can be accepted.

/Anders Torger

On Wednesday 25 April 2007 13:47, Anders Torger wrote:
> Ok, in other words:
>
> Only one message per stream can be partially delivered, however if
> the partial delivery is of an ordered message, it may be interleaved
> with a full unordered message.
>
> If instead the partial delivery is of an unordered message, it cannot
> be interleaved with a full unordered message (since sinfo_ssn is zero
> Hmm... this seems a bit messy. I don't like the exception for
> unordered messages. If there was a way to separate different
> unordered messages (like the sinfo_ssn for ordered), the rule could
> be simplified to:
>
> Only one message per stream can be partially delivered, however it
> can be interleaved with a full message on the same stream (an
> partially delivered ordered message interleaved with a full unordered
> message and vice versa).
>
> /Anders Torger
>
> > stream.
> > It does not say "only one ordered and as many unordered as you
> > would like".. only one message partially delivered in any stream..
> >
> > BSD will not do either one.. once you begin delivery in stream 1
> > you MUST get all the message before ANY other message in stream 1
> > will arrive.
> >
> > Does that help? ;-D
> >
> > R
> >
> > > /Anders Torger
> > >
> > >>> single stream, or is there some limit such that one can
> > >>> guarantee that there is only one unordered partial delivery
> > >>> going on per stream?
> > >>
> > >>> delivery for an unordered message going on simultaneously, but
> > >>> I just realized that it may not be correct.
> > >>

---

From: Randall Stewart <[email-masked]>
Date: Wed, 25 Apr 2007 08:36:05 -0400

Ok now I get what you are saying... did not understand the
last email.. so your reply to you helped :-D

> - Only one message per stream can be partially delivered.

correct.

>   with opposite order mode on the same stream.

Yes, I would guess. Not in BSD but the spec does not prevent this..

>        delivery cannot be interleaved with a full unordered message.

why not? If you were going to support this .. you COULD deliver
<--- Unordered msg (strm=1) PD-API NO-MSG_EOR
and
<--- Unordered msg (strm=1) MSG_EOR
or
<--- Ordered msg (strm=1 seq=X) MSG_EOR

What you can NOT do is:

<----Ordered msg (strm=1, seq=X) PD-API NO-MSG_EOR
<----Ordered msg (strm=1, seq=X+1) MSG_EOR

Since this would violate ordering rules.

Now that all being said.. I don't plan to do any of the above on
BSD.. it gets a bit to tricky and adds to much code to the receive
path which is already getting overweight :-D

R

---

From: Janardhan Iyengar <[email-masked]>
Date: Wed, 25 Apr 2007 10:03:53 -0400

> path which is already getting overweight :-D

This looks ugly to me, and seems like inconsistencies can be introduced 
between implementations that may make life difficult for apps.

I do not want to speak for app developers, but it seems to me that 
clarification should be there in the doc. One way or the other, we 
should have more clarity about what can/cannot be done. If we want to 
have the possibility of partial delivery of ordered with interleaving 
full delivery of unordered, maybe that can be stated clearly? App 
developers can then expect it.

My opinion is that this interleaving should be kept out, and that the 
doc should clearly state it so. It seems to make things messy in the 
general case... but there may be others who finf this valuable.

What do you all think?
- jana

-- 
Janardhan R. Iyengar
Visiting Assistant Professor
Connecticut College
http://cs.conncoll.edu/iyengar/

---

From: Vlad Yasevich <[email-masked]>
Date: Wed, 25 Apr 2007 10:10:00 -0400

Randall

Randall Stewart wrote:
>> Sorry for replying to myself, but I just found out that it does not
>> seem to messy if I change the wording:
>>

How is the application supposed to tell if the second message is a completion
of the first, or a separate message by itself?

There is no sigal/flag on the message that says it's a partial delivery.  At
least I haven't seen one defined.  Having such a flag, might allow for the
above scenario.

> <--- Ordered msg (strm=1 seq=X) MSG_EOR

-vlad

---

From: Anders Torger <[email-masked]>
Date: Wed, 25 Apr 2007 16:43:58 +0200

On Wednesday 25 April 2007 14:36, Randall Stewart wrote:
> >      - That is an ordered partial delivery can be interleaved with
> > a full unordered message and vice versa. But an unordered partial

The problem is that the information you get in your sctp_sndrcvinfo is 
not enough.

You cannot differ between

<--- Unordered msg (strm=1) PD-API NO-MSG_EOR (first fragment)
<--- Unordered msg (strm=1) PD-API MSG_EOR    (last fragment)

and

<--- Unordered msg (strm=1) PD-API NO-MSG_EOR (first fragment)
<--- Unordered msg (strm=1) MSG_EOR           (full unrelated message)

Mark Butler pointed out this problem in an earlier mail.

With an ordered message you have the sinfo_ssn which make it possible to 
differ between messages, but for ordered messages there is no need, 
since they always come in order. (One could use sinfo_ssn on ordered 
messages to detect aborted partial delivery though, if the stack does 
not support MSG_TRUNC flag and while there's no stream member in 
SCTP_PARTIAL_DELIVERY_EVENT).

I tried to figure out if I could use the sinfo_tsn/sinfo_cumtsn in some 
way to detect the difference between a new unordered message or the 
continuation of a partial delivered one, but I don't think that is 
possible. If the sinfo_tsn always contained the tsn of the first chunk 
of the message, regardless if recvmsg() returned a fragment into the 
message, then it would be possible. But sinfo_tsn typically contains 
the tsn of the first or the last chunk in the fragment recvmsg() 
returns.

/Anders Torger

---

From: Randall Stewart <[email-masked]>
Date: Wed, 25 Apr 2007 15:33:11 -0400

> Mark Butler pointed out this problem in an earlier mail.

Good point.. I missed this.. so I think its even
a better reason NOT to allow any more deliveries on a
stream once it gets a PD-API.. unordered or ordered.

It would prevent the above ;-D

R

---

From: Randall Stewart <[email-masked]>
Date: Wed, 25 Apr 2007 15:48:33 -0400

> of the first, or a separate message by itself?

I missed this point :-(

> least I haven't seen one defined.  Having such a flag, might allow for the

I think we just aught to disallow delivery of anything more in
a stream once you start a pd-api for that stream.

If its so critical to send a message at the same time.. the app
can use an unordered message in a different stream ;-)

If I hear no complaints I will see if I can add some text
to explicitly state that once PD-API has started in a
stream.. no other messages will be delivered in that stream
until the full message is read.

R

---

From: Mark Butler <[email-masked]>
Date: Wed, 25 Apr 2007 23:38:51 -0600

> can use an unordered message in a different stream ;-)

Just for completeness sake, suppose you have an application that is best 
served by sending a large number of latency sensitive unordered messages 
at the same time, so many that it is not desirable to allocate a 
different stream for each one.  Wouldn't it be helpful for applications 
to be able to avoid head of line blocking problems in such a case?

The only difficulty would be the application would need a way to 
distinguish between messages in such a case.  There is a field that 
could be used.  If the send/receive info TSN value for was fixed to 
always be the first TSN in a message,  that field could subsitute as a 
message identifier for unordered message fragment disambiguation.

So it seems to me a reasonable proposal to add a level 3 to 
SCTP_FRAGMENT_INTERLEAVE that adds the ability to interleave between 
different unordered messages on the same stream as well, with the 
sinfo_tsn fixed to the start tsn and used to distinguish between 
different messages.

 - Mark B.

---

From: Anders Torger <[email-masked]>
Date: Thu, 26 Apr 2007 07:44:49 +0200

I would think Mark Butler and Kacheong Poon will complain a bit if they 
see the message, but I'll let them speak for themselves.

As a general design guideline, I think that an API for a protocol should 
not introduce any artificial limitations which do not exist in the 
protocol itself.

And I think this is such a limit, and thus I hereby complain a 
little ;-).

What is the current purpose/value of sinfo_tsn and sinfo_cumtsn (just 
protocol debug info?), and why is sinfo_cumtsn only available for 
unordered messages? Say if we would define the contents of sinfo_tsn 
more strictly, that it always shows the TSN of the *first* data chunk 
received in the SCTP user message instead of 'TSN of any data chunk' 
like it is now, then it can be used to multiplex between different 
unordered messages on the same stream. Or actually, the TSN could be 
any, but the important thing is that one should define that sinfo_tsn 
is always the same for all fragments delivered, which it is not today.

To satisfy everyone, one could do the above and add

SCTP_FRAGMENT_INTERLEAVE=3

like Mark Butler suggested (and state that it is optional to implement 
by a stack), so we get:

SCTP_FRAGMENT_INTERLEAVE setting:
 - 0 -- no interleave.
 - 1 -- interleave between associations (one-to-many only).
 - 2 -- interleave between streams.
 - 3 -- interleave between messages, stack may or may not support
        multiple partial deliveries on the same stream. Use
        sinfo_tsn to multiplex between different unordered messages on
        the same stream.

Only mode 3 with a stack that support multiple partial deliveries 
introduce no API-related head-of-line blocking.

/Anders Torger

---

From: Randall Stewart <[email-masked]>
Date: Thu, 26 Apr 2007 05:40:37 -0400

Anders:

I could live with that.. but I think you are correct, for
at least un-ordered messages the sinfo_tsn must have
a more stricter definition to make it work.

R