Subject: Re: [Tsvwg] SCTP partial delivery

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Wed, 30 Nov 2005 23:31:59 -0700

Mark,

On Wed, 30 Nov 2005, Mark Butler wrote:

> 
>    Brian,
> 
> SCTP_FRAGMENT_INTERLEAVE would enable interleaving fragments from 
> different streams.
> It is an unexpected, non-Posix compliant behavior, and should be 
> disabled by default.
>     
> 
> POSIX does not say that fragments from different streams can't be
> interleaved.
>   
> 
>    But  it does specify that records may not be interleaved, which is the
>    same  thing.   Adding streams shouldn't be an excuse to break existing
>    semantics  - principle of least surprise, at a minimum. Streams should
>    be transparent to readers.
>     - Mark
>     
> 
> Not the same thing.  That is interleaving records from the SAME stream.
>   
> 
>    We will have to disagree here.
>    - Mark

Apparently you disagree with POSIX here too.  While you seem to be
reading out loud, considere these two passages:

   The SOCK_SEQPACKET socket type is similar to the SOCK_STREAM type, and
   is  also  connection-oriented. The only difference between these types
   is  that  record  boundaries  are  maintained using the SOCK_SEQPACKET
   type.  A  record  can  be sent using one or more output operations and
   received  using  one  or more input operations, but a single operation
   never  transfers  parts of more than one record. Record boundaries are
   visible  to  the receiver via the MSG_EOR flag in the received message
   flags  returned by the [10]recvmsg() function. It is protocol-specific
   whether a maximum record size is imposed.

"a single operation never transfers parts of more than one record."

And here:

   The  contents of a receive buffer are logically structured as a series
   of data segments with associated ancillary data and other information.
   A  data segment may contain normal data or out-of-band data, but never
   both.  A  data  segment may complete a record if the protocol supports
   records  (always  true  for  types  SOCK_SEQPACKET  and SOCK_DGRAM). A
   record  may  be  stored  as more than one segment; the complete record
   might never be present in the receive buffer at one time, as a portion
   might  already  have  been  returned  to  the application, and another
   portion  might  not  yet  have  been  received from the communications
   provider. A data segment may contain ancillary protocol data, which is
   logically  associated  with the segment. Ancillary data is received as
   if  it  were  queued  along  with  the  first normal data octet in the
   segment  (if  any). A segment may contain ancillary data only, with no
   normal  or  out-of-band  data.  For  the  purposes  of this section, a
   datagram  is considered to be a data segment that terminates a record,
   and  that  includes  a  source  address as a special type of ancillary
   data.  Data segments are placed into the queue as data is delivered to
   the socket by the protocol. Normal data segments are placed at the end
   of the queue as they are delivered. If a new segment contains the same
   type  of data as the preceding segment and includes no ancillary data,
   and if the preceding segment does not terminate a record, the segments
   are logically merged into a single segment.

   The receive queue is logically terminated if an end-of-file indication
   has been received or a connection has been terminated. A segment shall
   be  considered  to  be terminated if another segment follows it in the
   queue,  if  the  segment  completes  a record, or if an end-of-file or
   other  connection  termination  has been reported. The last segment in
   the  receive queue shall also be considered to be terminated while the
   socket has a pending error to be reported.

   A  receive  operation  shall  never return data or ancillary data from
   more than one segment.

Now, I believe that I am doing this exactly correct, particularly
considering stream id is "ancillary data", and a fragment is a "segment".

What you propose deviates quite widely from these passages.

--brian

-- 
Brian F. G. Bidulock    ¦ The reasonable man adapts himself to the ¦
[email-masked]    ¦ world; the unreasonable one persists in  ¦
http://www.openss7.org/ ¦ trying  to adapt the  world  to himself. ¦
                        ¦ Therefore  all  progress  depends on the ¦
                        ¦ unreasonable man. -- George Bernard Shaw ¦

_______________________________________________
tsvwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tsvwg

---

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Wed, 30 Nov 2005 23:41:31 -0700

Mark,

While your reading, read down in chapter 2 under Socket Receive Queue:

    Socket Receive Queue

   A  socket has a receive queue that buffers data when it is received by
   the  system  until  it  is removed by a receive call. Depending on the
   type  of  the socket and the communication provider, the receive queue
   may  also  contain  ancillary  data  such  as the addressing and other
   protocol  data  associated  with the normal data in the queue, and may
   contain  out-of-band  or  expedited  data. The limit on the queue size
   includes  any normal, out-of-band data, datagram source addresses, and
   ancillary  data  in the queue. The description in this section applies
   to  all  sockets,  even though some elements cannot be present in some
   instances.

If you realize that a message fragment is a "segment" and stream id is
"ancillary data", then this is precisely how I have implemented the
sockets interface: adjacent fragments are merged and delivered together,
fragments with different stream id are delivered separate, fragments
are delivered in order of arrival (at the buffer, after gap logic), all
fragments do not have to be received to deliver the first ones, MSG_EOR
is set on the last segment of a record.

I don't see why this could not apply to 1:many also, particularly if
you consider association id as "ancillary data".

--brian

On Wed, 30 Nov 2005, Mark Butler wrote:

> 
>    (This  is  a  repeat  with extraneous whitespace from a defective mail
>    client removed)
>    Brian F. G. Bidulock wrote:
> 
> Yes, standard Posix SOCK_SEQPACKET semantics.  The serious problem, is 
> with partial deliveries on a one-to-many socket, because they serialize 
> communication from all other associations, potentially hanging the 
> socket for a very long time.  Lksctp is currently vulnerable to this 
> problem. 
>     
> 
> Well, no.  POSIX SOCK_SEQPACKET sets MSG_TRUNC if the message (not the
> record) is larger that the supplied buffer, just as does SOCK_DGRAM.
>   
> 
>    LKSCTP   is   vulnerable  as   implemented.   Partial  delivery  locks
>    one-to-many sockets by association.
>    Regrettably,   the   Posix   documentation   for   SOCK_SEQPACKET   is
>    inconsistent. This is the description from section 2.10.6:
> 
>      The  SOCK_SEQPACKET socket type is similar to the SOCK_STREAM type,
>      and  is also connection-oriented. The only difference between these
>      types   is   that   record  boundaries  are  maintained  using  the
>      SOCK_SEQPACKET  type. A record can be sent using one or more output
>      operations  and  received using one or more input operations, but a
>      single  operation  never  transfers  parts of more than one record.
>      Record  boundaries are visible to the receiver via the MSG_EOR flag
>      in   the  received  message  flags  returned  by  the  [1]recvmsg()
>      function.  It is protocol-specific whether a maximum record size is
>      imposed.
> 
>    No  difference  from  SOCK_STREAM except record boundaries, means that
>    message  boundaries  are  either  invisible  or  identical with record
>    boundaries.  Not two independent sets of boundaries.
>    However  the  documentation  for  recvmsg()  implies  that records and
>    messages are different:
> 
>      The  recvmsg()  function  shall  return  the  total  length  of the
>      message.   For   message-based  sockets,  such  as  SOCK_DGRAM  and
>      SOCK_SEQPACKET,  the  entire  message  shall  be  read  in a single
>      operation. If a message is too long to fit in the supplied buffers,
>      and  MSG_PEEK  is  not  set in the flags argument, the excess bytes
>      shall  be  discarded,  and  MSG_TRUNC shall be set in the msg_flags
>      member  of  the msghdr structure. For stream-based sockets, such as
>      SOCK_STREAM,  message  boundaries  shall  be ignored. In this case,
>      data shall be returned to the user as soon as it becomes available,
>      and no data shall be discarded.
>      ...
> 
>    MSG_EOR
>    This  is  a  complete  contradiction. It only makes sense if there are
>    protocols  that  support  two  sets of boundaries, lower level message
>    boundaries embedded in higher level record boundaries.  Are there any?
>    More  likely  there  are  two  conceptions of SOCK_SEQPACKET that made
>    their  way  into  the  standard  - One is SOCK_DGRAM with ordering and
>    reliability  added.   The  other  is  a  byte  stream  with occasional
>    boundary   markers.    The  draft  api  uses  the  latter  conception,
>    consistent  with  Posix  XSH  2.10.6.   Which  conception  do existing
>    SOCK_SEQPACKET protocols use?
>    I guess I can't say standard SOCK_SEQPACKET semantics anymore. Sigh.
>    - Mark
>    POSIX references:
>     [2]http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02
>    _10.html
>     [3]http://www.opengroup.org/onlinepubs/009695399/functions/recvmsg.ht
>    ml
> 
> References
> 
>    1. file://localhost/home/brian/functions/recvmsg.html
>    2. http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_10.html
>    3. http://www.opengroup.org/onlinepubs/009695399/functions/recvmsg.html

---

From: Mark Butler <[email-masked]>
Date: Thu, 01 Dec 2005 05:04:37 -0700

Brian,

>record) is larger that the supplied buffer, just as does SOCK_DGRAM.
After further checking, it seems the SOCK_SEQPACKET world is split three 
ways:

Packet oriented protocols generally use packet level reads with 
truncation / discard semantics and no MSG_EOR.  X.25, Bluetooth, IRDA, 
and Unix domain sockets use SOCK_SEQPACKET this way.

Record oriented protocols generally use byte stream reads and MSG_EOR - 
no packet level visibility, no truncation / discard.  DECNet and ISO TP 
use SOCK_SEQPACKET that way.

Packet / record hybrids generally use SOCK_SEQPACKET with truncation / 
discard semantics on the packet level, and record terminating packets 
marked with MSG_EOR.  SPX and XNS SPP use SOCK_SEQPACKET this way.

- Mark

---

From: Mark Butler <[email-masked]>
Date: Thu, 01 Dec 2005 19:26:59 -0700

Brian,

><POSIX section 2.10.11 omitted>
>  
>

>considering stream id is "ancillary data", and a fragment is a "segment".

I agree that what you are doing is in full compliance with the letter of 
POSIX  XSH sections 2.10.6 and 2.10.11 as currently specified.  However, 
whether some fragment is a "segment", a portion of a "segment", or a 
even a series of "segments" is arbitrary as far as POSIX is concerned.   
The mapping of lower level entities to POSIX "segments" varies by both 
protocol and socket type.  Anything can be presented to the socket layer 
as a "segment" as long as the relevant rules are followed. Whether such 
a presentation is useful is a different issue.

A POSIX "segment" on a SOCK_STREAM socket normally extends the length of 
the whole connection.  A SOCK_SEQPACKET "segment" typically extends for 
either one packet (SPX, Unix domain, X.25, etc.) or one arbitrary length 
"record" (DECnet, ISO TP).  Many of these protocols support both 
SOCK_STREAM and SOCK_SEQPACKET semantics over identical wire protocols.

> What you propose deviates quite widely from these passages.

All I am proposing is a SOCK_DGRAM socket type (or equivalent mode) for 
SCTP.  There is absolutely nothing  in POSIX that prevents an SCTP 
message from being mapped to a SOCK_DGRAM "segment".  Nothing in POSIX 
prohibits interleaved SAR below the socket layer.  Otherwise the socket 
interfaces for IP, ATM AAL5, and TCP would all be in violation.

- Mark

---

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Thu, 1 Dec 2005 20:50:27 -0700

Mark,

> interfaces for IP, ATM AAL5, and TCP would all be in violation.

Yet, it is that very approach that causes the blocking problems that
you wish to avoid.

--brian

---

From: Mark Butler <[email-masked]>
Date: Thu, 01 Dec 2005 23:20:35 -0700

Brian,

>Yet, it is that very approach that causes the blocking problems that
Inter-association blocking is radically more serious than 
intra-association blocking.  No implementations I am aware of introduce 
any unnecessary intra-association blocking, save perhaps for 
applications that can benefit from fractional messages, which are rare.

How often does anyone have a need to inspect fragments of UDP 
datagrams?  There is nothing stopping someone from writing an 
application interface to UDP datagram fragments.  Or what about a 
partial delivery interface to AAL5?

Partial message delivery, as an actual application requirement (instead 
of an occasional implementation side effect) has a considerable 
throughput cost in terms of context switches up and down the stack. 
Practically every modern networking technology is designed to avoid 
fractional delivery semantics for efficiency reasons.  It is the whole 
reason for RDMA to exist.  RDMA is both efficient and useful for large 
read and write operations because the utility of a partially completed 
operation is usually nil.  It is likely that in a few years RDMA 
adaptations will dominate network file systems, network file transfer, 
electronic mail, electronic commerce, cluster communications, cache 
coherency protocols, and web browsing.  I don't think anyone is going to 
complain.  SCTP over RDMA may very well come to dominate RDMA over SCTP.

 - Mark

---

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Fri, 2 Dec 2005 01:39:04 -0700

Mark,

Read the socket buffer passage in Chapter 2 again.

If you are doing SAR beneath the socket buffer, there is no partial
delivery at the socket.  Existing things like IP fragmentation that do
SAR beneath the socket buffer, are not bound by the size of the socket
buffer.   (One of the reasons why IP fragmentation is a bad thing.)
SCTP, on the other hand, uses the receive socket buffer (or some weird
kind of instance of a receive socket buffer for 1:many) as the advertise
receive window to the peer in SCTP.  The protocol is not designed to do
SAR beneath the socket buffer.

So, for example, IP waits for all fragments of an IP message to arrive
before resassembling them and delivering them to the transport protocol.
If there is not enough available resource to reassemble all of the
fragements, the obvious and simple choice is to discard the packet.  The
same is true for AAL5 (particularly with IP running over it).

SCTP, by contrast, acknowledges the delivery of each TSN for each
fragment.  If there is not enough receive buffer to reassemble the
message, it does not have the choice of discarding it: it is, after all,
a reliable transport.  Therefore, your choice become: overflow the
receive buffer allocation (bad idea), or attempt to free up enough
receive buffer to reassemble the remainder of the message (only other
choice).

There are two ways within the protocol to free up receive buffer (both
are necessary):

1. Renegging.  Renegging is discarding TSNs that follow a gap and not gap
   acking them in the next gap report.  This frees up buffer and informs
   the peer that it must now retransmit that data.  If a receiver does not
   support renegging, it can stall in any number of situations of TSN loss.

2. Partial delivery.  I don't know whay your definition is, but partial
   delivery here consists of releasing the intial or intermediate
   (continguous) fragments of a message that, if left in the receive buffer,
   would ultimately make it impossible to reassemble the message.  Case in
   point is where the message itself is larger than the receive buffer.
   You see, it does not take a missing TSN or an aborted connection to
   force an SCTP receiver to invoke partial delivery.

I'm sorry, but SCTP is a reliable transport protocol with built in ULP
flow control, not the unreliable datagram service to which you compare
it.  If you want to avoid partial delivery: send smaller messages.
Otherwise, it is a necessary part of the protocol:

  RFC 2960 Section 6.9 Fragmentation and Reassembly:

  "Note: If the data receiver runs out of buffer space while still
   waiting for more fragments to complete the re-assembly of the
   message, it should dispatch part of its inbound message through a
   partial delivery API (see Section 10), freeing some of its receive
   buffer space so that the rest of the message may be received."

 and Section 10:

   G) Receive

   Format: RECEIVE(association id, buffer address, buffer size
           [,stream id])
   -> byte count [,transport address] [,stream id] [,stream sequence
      number] [,partial flag] [,delivery number] [,payload protocol-id]

   ...

   o  partial flag - if this returned flag is set to 1, then this
      Receive contains  a partial delivery of the whole message.  When
      this flag is set, the stream id and stream sequence number MUST
      accompany this receive.  When this flag is set to 0, it indicates
      that no more deliveries will be received for this stream sequence
      number.

Partial delivery is not an implementation side-effect.  Nor is it an
optional function of the API.  It is a requirement of the protocol.

Read POSIX Chapter 2 socket receive buffer again.  This time think
reliable transport protocol with variable record sizes.  Think
SOCK_SEQPACKET.  SOCK_STREAM is acheivable: just don't set MSG_EOR and
allow one record to blend into another.  SOCK_DGRAM is not.  All
SOCK_DGRAM applications are inherently unreliable, and all impose a
maximum message size.  SCTP is (and does) neither.

--brian

On Thu, 01 Dec 2005, Mark Butler wrote:

>    intra-association   blocking.    No  implementations  I  am  aware  of
>    introduce any unnecessary intra-association blocking, save perhaps for
>    Partial   message  delivery,  as  an  actual  application  requirement
>    (instead   of   an   occasional  implementation  side  effect)  has  a
>    considerable  throughput cost in terms of context switches up and down
>    the  stack. Practically every modern networking technology is designed
>    to  avoid fractional delivery semantics for efficiency reasons.  It is
>    the whole reason for RDMA to exist.  RDMA is both efficient and useful
>    for large read and write operations because the utility of a partially
>    completed  operation is usually nil.  It is likely that in a few years
>    RDMA  adaptations  will  dominate  network  file systems, network file
>    transfer,    electronic    mail,    electronic    commerce,    cluster
>    communications,  cache coherency protocols, and web browsing.  I don't
>    think  anyone is going to complain.  SCTP over RDMA may very well come
>    to dominate RDMA over SCTP.
>     - Mark

---

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Fri, 2 Dec 2005 01:55:18 -0700

Mark,

Checking?  What are your souces?  I wouldn't base POSIX
compliance on Linux code...  (Particularly the hacked packet
layer X.25 implementations, which in fact do set MSG_EOR).
MSG_TRUNC on SOCK_SEQPACKET is rather protocol and
implementation dependent.  MSG_EOR is not so.

(I never set MSG_TRUNC, but setting it would help clear the
receive buffer faster.  I think MSG_TRUNC has more to do with
not interleaving receives that were transmitted as a unit (or
beneath a given size like POSIX pipes).  The SCTP transmitter
make no assurances to the sender that sends beneath a given size
will arrive in a single packet.  SCTP is allowed to fragment
transmission into data chunks in whatever way it thinks it can
most efficiently send them.  This makes it possible to use
Nagle's algortihm for SCTP.)

--brian

---

From: Mark Butler <[email-masked]>
Date: Fri, 02 Dec 2005 15:59:01 -0700

>implementation dependent.  MSG_EOR is not so.
I am admittedly describing existing implementations, not POSIX 
compliance, per se.  I think the POSIX specification is ambiguous with 
regard to SOCK_SEQPACKET.   I checked mainline SOCK_SEQPACKET protocol 
interfaces on Linux, xBSD, Solaris, and AIX. 

 - Mark

---

From: Mark Butler <[email-masked]>
Date: Fri, 02 Dec 2005 17:49:40 -0700

>SAR beneath the socket buffer.
The protocol has nothing to do with socket buffers, per se. Sockets are 
a POSIX thing, not an SCTP thing.  I agree of course, that arriving 
message fragments should be accounted against SO_RCVBUF. 

>same is true for AAL5 (particularly with IP running over it).
No problem, since both are unreliable protocols.

>fragment.  
Logically, yes, physically no. A bundle of messages in the same packet 
requires at most one SACK if the transmitter is following the rules.  A 
robust implementation should have an acknowledgement timer that delays a 
SACK for at least a 10 ms or so unless there is reverse traffic.  A 
receiver on a gigabit network might receive hundreds of packets (from 
the same sender) in that time and it would be ridiculously inefficent to 
acknowledge each one (or each pair) independently.

>If there is not enough receive buffer to reassemble the

Of course.  I never said it did.  Any receive buffer under pressure 
might invoke partial delivery.  My point is that it can become a serious 
problem on one-to-many sockets (assuming no record interleaving).  The 
problem for one-to-one senders is negligible.

On one-to-many sockets, partial delivery is much more likely, even with 
predominantly small messages.  Any slow sender may block everyone else, 
with no packet loss whatsover.  An SCTP sender using a 56K frame relay 
link will only be able to send packets every 267 ms.  So if the buffer 
management partially delivers a message from that sender, no other 
messages can be delivered for at least that interval, even with a 
perfect network.

A more common alternative is a sender writing long messages in multiple 
fragments. The draft doesn't support MSG_EOR on write, but other 
implementations may use different semantics.   Say the sending process 
writes half a message and it either blocks for I/O it needs to finish 
the rest of the message, or is switched out by the scheduler.  It may 
not run again for several hundred milliseconds, often longer on systems 
under swap pressure.   Meanwhile the Nagle timer has long since expired, 
and the first part of the message is on its way.

On the receving end, the message may be selected for partial delivery, 
and then the one-to-many socket stalls until the sending process is able 
to finish the message.  Even with a perfect gigabit network, a one to 
many socket may stall for the slowest sender.

>it.  If you want to avoid partial delivery: send smaller messages.
Partial delivery on one-to-many sockets turn it into an unreliable 
protocol, much, _much_ worse than UDP. Unless of course, you don't care 
whether a single sender blocks your whole enterprise.

>   buffer space so that the rest of the message may be received."
Notice that is a "should", not a "must".

>optional function of the API.  It is a requirement of the protocol.
No, it is not.  The preface to section 10 states: "The primitives and 
notifications described in this section should be used as a guideline 
for implementing SCTP".  Section 10 does not require partial deliveries 
to ever occur.

>maximum message size.  SCTP is (and does) neither.
_Nothing_ in SCTP restricts an interface from specifying buffer 
requirements. Atomic delivery can work with multi-megabyte messages if 
the receive buffer is set accordingly.   Should SCTP guarantee reliable 
delivery with a buffer size of 1 byte?

 I am not suggesting that people be _forced_ to use SOCK_DGRAM as the 
only interface.  However, if it or an equivalent option is not added, I 
think one-to-many sockets should be removed from the api, lest someone 
be so unfortunate as to use them for a serious application.   Perish the 
thought that someone might actually think that SCTP is a capable 
replacement for UDP.

Of course, we could always make every application include SAR code 
instead, moving the buffer requirement one level higher.  That sounds 
like a sure way to keep as few people as possible from writing or 
porting SCTP applications.

 - Mark