Subject: RFC 2960, section 7.2.2 - partial_bytes_acked

From: David Lehmann <[email-masked]>
Date: Tue, 22 Jul 2003 14:42:43 -0400

RFC 2960, section 7.2.2, says:
   o  When partial_bytes_acked is equal to or greater than cwnd and
      before the arrival of the SACK the sender had cwnd or more bytes
      of data outstanding (i.e., before arrival of the SACK, flightsize
      was greater than or equal to cwnd), increase cwnd by MTU, and
      reset partial_bytes_acked to (partial_bytes_acked - cwnd).

What should SCTP do if the first condition (partial_bytes_acked >= cwnd)
is true, but the second condition (prev_flightsize >= cwnd) is false?
Should partial_bytes_acked be left unchanged?  That is, leave 
partial_bytes_acked >= cwnd.  If so, it could grow again... and again.
Or should we set it to zero or to cwnd if the prev_flightsize < cwnd?

Also, is the order of the steps correct?  If 
partial_bytes_acked == cwnd and I follow those
steps above, partial_bytes_acked will become negative.

-- 

David Lehmann                          Ulticom, Inc.
AOL/Yahoo IM: davidULCM                1020 Briggs Road
1-856-787-2729                         Mt. Laurel, NJ 08054   USA

---

From: [email-masked]
Date: Tue, 22 Jul 2003 18:25:16 -0700 (PDT)

Hi David,
The procedure woule be like this.
/*   o  Whenever cwnd is greater than ssthresh, upon each SACK arrival
      that advances the Cumulative TSN Ack Point, increase
      partial_bytes_acked by the total number of bytes of all new chunks
      acknowledged in that SACK including chunks acknowledged by the new
      Cumulative TSN Ack and by Gap Ack Blocks.
*/
   if cwnd > ssthresh
      partial_bytes_acked+=Total Bytes Acked in the SACK;

/*   o  When partial_bytes_acked is equal to or greater than cwnd and
      before the arrival of the SACK the sender had cwnd or more bytes
      of data outstanding (i.e., before arrival of the SACK, flightsize
      was greater than or equal to cwnd), increase cwnd by MTU, and
      reset partial_bytes_acked to (partial_bytes_acked - cwnd).
*/
      if partial_bytes_acked >= cwnd & flightsize >= cwnd
          cwnd+=MTU;
          partial_bytes_acked-=cwnd;
      end
   end
So there is not case where partial_bytes_acked could be negative.
If the conditions are not true, I think we should leave the value unchanged.
> steps above, partial_bytes_acked will become negative.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Zhou Yu
%  Electrical and Computer Enigneering, UBC
%  vancouver Canada
%  Email: [email-masked]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

---

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Tue, 22 Jul 2003 21:10:00 -0600

David,

I do:

  if (sd->cwnd <= sd->ssthresh) {
      /* RFC 2960 7.2.1 */
      if (sd->in_flight > sd->cwnd)
          sd->cwnd += accum < sd->mtu ? accum : sd->mtu;
  } else {
      /* RFC 2960 7.2.2 */
      sd->partial_ack += accum;
      if (sd->in_flight >= sd->cwnd && sd->partial_ack >= sd->cwnd) {
          sd->cwnd += sd->mtu;
          sd->partial_ack -= sd->cwnd;
      }
  }

Which is pretty much the same as Zhou describes below.

--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 ¦

---

From: David Lehmann <[email-masked]>
Date: Wed, 23 Jul 2003 08:30:56 -0400

> So there is not case where partial_bytes_acked could be negative.

Let's say (partial_bytes_acked == cwnd).
Wouldn't partial_bytes_acked be equal to negative MTU if
(flightsize >= cwnd)?
And if so, was this intended?

The logic seems to be out of order.  We are counting bytes
acked.  As long as the bytes acked < cwnd, it is "partial".
When we get a full cwnd worth of acked data, then we want
to increase the cwnd.  This is fine.  However, it seems to
me that when we want to reset the counter (partial_bytes_acked),
it should subtract the cwnd value to which we were originally 
comparing partial_bytes_acked.  Otherwise, we are losing 
one MTU worth of acked data.

In addition, it is possible that flightsize < cwnd on consecutive
sacks. In this case partial_bytes_acked could become very
large. If so, was this intended?

What is the expected range for partial_bytes_acked?

--

---

From: Caitlin Bestler <[email-masked]>
Date: Wed, 23 Jul 2003 09:16:48 -0500

Section 6.1 of RFC2960 specifies:

> C) When the time comes for the sender to transmit, before
> sending new DATA chunks, the sender MUST first transmit
> any outstanding DATA chunks which are marked for
> retransmission (limited by the current cwnd).

If that means "when choosing the next Data Chunk for
inclusion in an outbound SCTP packet  a Data Chunk marked
for retransmission MUST be taken in preference to initial
Data Chunks." then I have no problems.

But I can see some cases where the MUST might imply steps
that I would consider to be counter-productive and/or require
specific permissive interpretations.

Comments on the desirability/legality of each would be appreciated:

-- Recalling already queued but untransmitted SCTP Packets
      because they contain Data Chunks that are new.
      
      Permissive Interpretation: Not a violation if "transmission"
      can be understood to be done  at the time the SCTP Packet is
      submitted to the IP layer, as opposed to when it hits the wire.
      
--  Holding off inclusion of a new unordered Data chunk that fits
      within the current SCTP packet because there is a Data Chunk
      that needs retransmission -- even though it won't fit within
      the current SCTP packet.
      
--   Allowing a new Data Chunk to be sent because it is "available"
       for transmission, while the Data Chunk that requires retransmission
       is not.

      Permissive interpretation: the Data Chunk is not a Data Chunk until
      it is available. It is merely a TSN that has been flagged for retransmission.
      
      Explanation: A typical Network Processor has a small amount of memory
      intended to support "Fast Path" work. Using this memory to hold already
      sent buffers that will probably be acked (99%+) would not be an optimum
      use of this critical resource. Instead, the Data Chunks would be left in
      their original "slow path" memory.
      
      If a new Data Chunk is already in "fast memory", would it make sense
      to overwrite it from slow path memory, send the retransmission and
      *then* refetch the original Data Chunk from slow memory? Slow
      memory might be a processor buffer accessed over a system bus that
      may be barely faster than the network interface. 
      
      Allowing the already fetched Data Chunk to take precedence over
      the unfetched Data Chunk would reduce the amount of churn on
      the system bus. When dealing with a high speed network interface
      and a legacy system bus this can be very desirable.

---

From: "Randall Stewart (cisco)" <[email-masked]>
Date: Thu, 24 Jul 2003 09:50:05 -0500

David:

I am still traveling so email is spotty for me :> sorry for the
delayed response..

I have a similar algroithm to what Brian and Zhou layed out:
{
 /* We are in congestion avoidance */
       if (((net->flight_size+net->net_ack) >= net->cwnd) ||
            (asoc->burst_limit_applied)) {
             /* add to pba only if we
              * had a cwnd's worth (or so) in flight OR
              * the burst limit was applied.
              */
              net->partial_bytes_acked += net->net_ack;
           
             /* Do we need to increase (if pba is > cwnd)? */
             if (net->partial_bytes_acked >= net->cwnd) {
                   if (net->cwnd < net->partial_bytes_acked) {
                        net->partial_bytes_acked -= net->cwnd;
                     } else {
                          net->partial_bytes_acked = 0;
                     }
                     net->cwnd += net->mtu;
                }
       }

Note that:

1) I will NOT let pba go negative... It can if you bump cwnd first but it
    was NEVER intended that it be allowed to go negative (IMO)... so I 
don't let it :>

2) Note that I DO NOT credit PBA unless the full cwnd is being used. This
    I realize is unspecified.. and I think could be done either way.. I 
just did
    not think it right.. otherwise you could hit a situation where you build
    pba up to 4 MTU's and then, when you finally do use the full cwnd
   (say for 4 send op's) you would do basically a slow-start for the next
   3-4 acks or so... This seemed wrong and against the spirit of what the
   idea that Lixia intended when she wrote the PBA algorithm...

Maybe we should specify it better, I am adding Lixia on here to
get her opinion...

R

David Lehmann wrote:

> comparing partial_bytes_acked.  Otherwise, we are losing one MTU worth 
> of acked data.
>

-- 
Randall R. Stewart
ITD
Cisco Systems Inc.
[email-masked] 815-342-5222(cell) or 815-477-2127(office)

---

From: "Randall Stewart (cisco)" <[email-masked]>
Date: Thu, 24 Jul 2003 09:52:31 -0500

>>retransmission (limited by the current cwnd).
Caitlin:

I will not comment on your other items below.. since the
SINGLE purpose of C) is to make sure you re-send things
marked to be retransmitted BEFORE sending new data
chunks that have never been transmitted...

i.e. your comment

" a Data Chunk marked
Data Chunks."

Is EXACTLY what is intended by this statement.

R

---

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Thu, 24 Jul 2003 09:38:59 -0600

Randall,

> chunks that have never been transmitted...

Why MUST instead of SHOULD?  Could you explain how the
Internet will be destroyed if I send out of order data chunks
on stream 0 ahead of retransmissions?

--brian

---

From: Caitlin Bestler <[email-masked]>
Date: Thu, 24 Jul 2003 10:57:22 -0500

> Is EXACTLY what is intended by this statement.

So, suppose that for implementation specific reasons, the set
of Data Chunks being considered for inclusion in a new packet
is a subset of all possible Data Chunks. Further suppose that
this subset was not selected in a way that excluded Chunks
marked for retransmission.

It is permissible to make the selection from this subset
(favoring those that are marked for retransmission), or
MUST you refuse to select a new Chunk until after you
have searched the *entire* population of possible Data
Chunks to ensure that there are none marked for
retransmission?

---

From: Caitlin Bestler <[email-masked]>
Date: Fri, 25 Jul 2003 10:08:49 -0500

> on stream 0 ahead of retransmissions?

I would be interested if anyone can think of a reason how
minor cases of shipping a new Data Chunk ahead of one
requiring retransmission would disrupt the peer or the net.

On a purely technical basis, this requirement can be
downgraded to an effective "SHOULD" because there is
nothing that requires the process of marking a Data
Chunk for retransmission to be synchronous. Timers
may be fuzzy. The processing of SACKs is asynchronous.

With the Network Processor example, you can refetch
a Data Chunk to "fast memory" and *then* mark it for
retransmission.

So, the proposed practice can be described in a fashion
that makes it "legit".

The question is, would it cause performance problems,
lead to deadlocks, confuse peers or any such stuff?

Caitlin Bestler - [email-masked] - http://asomi.com/

---

From: "Randall Stewart (cisco)" <[email-masked]>
Date: Mon, 28 Jul 2003 12:42:08 -0500

> Caitlin Bestler - [email-masked] - http://asomi.com/
The only issue I can think of is that you could end up making
the peer hold more and more data awaiting re-ordering... also
you will not advance your cwnd since the cum-ack is not
moving forward.

So in effect I guess you hurt yourself more than anything else...

It could be  a SHOULD... not sure why it was written as a MUST...
when I get some cycles I will not only catch up on my email
backlog but go re-read the section and see if I can find a
trace of why it was written this way..

R

---

From: Caitlin Bestler <[email-masked]>
Date: Mon, 28 Jul 2003 13:02:11 -0500

> trace of why it was written this way..

I did think of one item, closely related.

Sending a "more convenient" data chunk should not take precedence
over sending "the correct chunk" even when in fact it means
sending a packet that is not fully packed when inclusion of
the more-convenient-chunk will exhaust the send credits, and
thereby prevent the retransmit-chunks from being sent when
they are ready.

But if *both* can be sent, I don't see any benefit in mandating
that one MUST be sent before the other. SHOULD, yes. But "SHOULD"
allows for factors like "A SHOULD go before B, but B is not ready
to be sent".

So perhaps that suggests a clarification along the lines of

    MUST NOT send a new Data Chunk if doing so will delay
    the sending a Data Chunk that require retransmission.

---

From: Kacheong Poon <[email-masked]>
Date: Mon, 28 Jul 2003 16:30:58 -0700

>     the sending a Data Chunk that require retransmission.

Some more related issues:

1. Will sending new data chunks first induce more duplicate SACKs
being sent, thus confuse the sender?
2. Does the MUST requirement prevent algorithms like F-RTO?  I
guess implementors trying F-RTO will ignore the MUST.

-- 

						K. Poon.
						[email-masked]