Subject: [dcp] flow window

From: Alkis Evlogimenos <[email-masked]>
Date: Tue, 7 May 2002 14:16:23 -0700

Hi all,

I am an undergraduate student in UC Berkeley and currently working (along with 
3 other students) on a user space implementation of the DCCP protocol.

We believe that adding a flow window option to the DCCP protocol will be very 
beneficial in at least 3 areas: case of slow receiver, detection of valid 
sequence numbers and the requirement for acknowledgements of acknowledgemens 
and ack vector implementation. More specifically:

a) The case of slow receiver: since the sender will know the available window 
on the receiving side it will never overload the receiver with excess 
traffic. Without a flow window the protocol will simply send packets until 
the receiver drops one. At that point the congestion mechanism will kick in 
and slow down the sender, but at that point the receiver is already 
overloaded. It is also worth noting that a change in the rate of the sender 
must take at least one RTT from the time of the drop and this latency may be 
unacceptable in some situations.

b) valid sequence number: with a flow window it is easy to choose between 
valid and invalid sequence numbers. Everything inside is valid, otherwise 
invalid. This is currently an unsolved issue with the current specification.

c) acks of acks: With a flow window there is no need for acks of acks. Here 
are possible two issues with acks of acks:
i) Hard to keep track of what to send back in the ack vector. The receiver 
must keep state of what sender sequence number it acked with which packet, in 
order to be able to clear the state correctly. Even with that information at 
hand there are still some corner cases to take care of (section 7.8.3 in the 
draft). 
ii) If the link is severely asymmetricm the ack of acks requirement may cause 
throughput problems (with asymmetric I mean every asymmetry possible - 
asymmetry in bandwidth, rtt, loss percentage).
The proposal here is to require that ack vector is acknowledging a flow window 
worth of packets each time. This will guarantee a reliable transmition of all 
acks and also alleviate the need for acks of acks. It will also make the ack 
vector implementation much simpler.

Comments/ideas?

Thanks,

Alkis Evlogimenos
UC Berkeley

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

---

From: Eddie Kohler <[email-masked]>
Date: Tue, 07 May 2002 18:38:42 -0700

Hi Alkis, thanks for your message, which brought up a bunch of issues we
need to deal with!

We don't believe that a flow window makes sense for DCCP. Take the two
existing CCIDs, TFRC and TCP-like.

* For TFRC, any kind of flow window doesn't make sense. A window doesn't
  really match up with a rate-based protocol, there is no Ack Vector to
  carry flow window information, and TFRC's slow increase strategy would
  make recovery from transient receiver congestion a painful process.

  The 'slow receiver' and 'sequence number validity' problems are generic
  DCCP problems, whose solutions should work for all CCIDs. Since flow
  windows don't work for TFRC, let's agree that the solutions for 'slow
  receiver' and 'sequence number validity' will not involve a flow window.
  This leaves the 'ack of acks' problem, which is relevant only for
  TCP-like CC.

* For TCP-like congestion control, a flow window seems more sensible; after
  all, TCP has one. However, in DCCP, a flow window might actually
  complicate the 'ack of acks' problem, since acks are not cumulative, and
  DCCP's ack clocking can be much slower than TCP's. 

  How should the flow window move when an Ack Vector indicates loss or
  congestion in the middle of a 'window'? Or at the beginning of a
  'window'? What if a whole 'window' of packets is lost? The sender would
  go quiescent, unable to send anything until the 'window' reopened, so
  there would have to be a timeout, after which the receiver would send an
  ack to restart the sender. What about reverse-path congestion, where Ack
  Ratio gets high? Then the receiver cannot send very many acks, so the
  flow window would get updated only sporadically, causing bursty sending.

  There may be other issues too. Overall it doesn't seem any less
  complicated than the current ack-of-acks logic.

The three problems you mention are real, though. We decided on solutions
that we preferred, as follows:

> the receiver drops one.

We propose a one-byte option, meaning, roughly, "Receiver Reaching
Capacity, Please Don't Send Faster". The receiver will put this option on
Ack packets to indicate that this DCP connection is reaching the limit of
the receiver's CPU, buffer space, or what-have-you. (We believe CPU is the
most likely limiting factor for today's machines.) Upon receiving this
option, the sender will refrain from increasing its send rate for one RTT
(send rate interpreted according to the sender's CCID). Thus, the receiver
should keep sending the option until it gets some spare CPU, buffer space,
or what-have-you.

The sending application can use some API to find out whether its rate is
limited by network congestion or receiver congestion (= "Reaching Capacity"
and "Receive Buffer Drops"). It may respond differently to the two kinds of
congestion. For example, if the network is congested, the sender might
switch to a more compressed format; whereas if the receiver is congested,
the sender might switch to a _less_ compressed format, to reduce CPU
pressure. DCCP doesn't require any particular application behavior, of
course, but it's nice to provide the hooks.

Note that "Receiver Reaching Capacity" is inherently less precise about the
receiver's limitations than TCP's receive window. This can be seen as an
advantage.

> invalid. This is currently an unsolved issue with the current specification.

We propose a non-negotiable feature, "Valid Sequence Space", which the
sender uses to inform the receiver of how big the valid sequence space
should be. The sender should control this number, not the receiver, since
only the sender can estimate how many packets it might send. (A flow window
would confuse two concepts here: how much the sender might send, and how
much the receiver wants to receive.) A reasonable guideline: the sender
will set "Valid Sequence Space" to the maximum number of packets it expects
to send in any RTT, times 4 or 8. "Valid Sequence Space" will default to,
say, 512.

> hand there are still some corner cases to take care of (section 7.8.3 in the 

You are right. Acks of acks are hard. There's no way around it. But they
are necessary. Hopefully we've explained why flow windows don't necessarily
make it any easier.

We didn't quite understand your point about asymmetric links, but maybe
this is enough for now. Thanks for bringing up these good points!

Eddie, with Mark and Sally