[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [dccp] DCCP-Ack Processing for CCID 2

Hi David,

Your summary combines elements that are pretty mandatory with elements that are implementation-dependent (I could imagine another implementation doing it differently). That's OK!

On Jul 26, 2005, at 7:49 PM, David Barrett wrote:
I'm trying to understand specifically how DCCP senders and receivers manage Acks in conjuction with CCID 2 (TCP-Like congestion control). I've read through the draft (especially Appendix A) and I think I get the details, but I'm still fuzzy on the "big picture".

Can you clarify if my summary below is about right?

(To simplify, ignore ECN and sender-Acks for now, and assume an Ack ratio of 1; I'll pick up those later.)

---- Sender Variables ----
The sender maintains at least the following data for each connection:
- cwnd (congestion window, default 1 packet)
- ssthresh (slow start threshold, default 2 packets)
- pipe (packets in-flight measure, default 0 packets)
- seqnum (last sequence number, default specified in 7.2)
- rto (transmit timeout, default 1s)
- dropstart (search for drops after this, default segnum)
- dataVector (recent history of Data packets)

The dataVector should also probably remember an approximation of the RTT within which each data packet was sent, and it should remember whether a packet has been acknowledged. dropstart is an optimization.

---- Receiver Variables ----
The receiver maintains at least the following data for each connection:
- ackVector (recent history of packet reception)


---- Send Process ----
When sending, the sender increments and inserts a sequence number. The sender also sets dataVector[segnum] if the packet is a Data packet, else it clears it.

By "is a Data packet", I assume you mean "is not a non-data packet". See DCCP spec Section 7.7. You must, for example, include DataAck packets here.

---- Receive Process ----
When receiving, the receiver updates its reception history and sets ackVector[segnum] (actually it does RLE encoding in a circular buffer as described in Appendix A, but it's conceptually the same). If it's a DCCP-Data packet, it also returns a DCCP-Ack packet.


---- Ack Receive Process ----
When receiving a DCCP-Ack packet, the sender:
    1) Updates 'rto' if it's Ack'ing the RTT sample
    2) Increments 'cwnd' according the current rule in force
    3) Decrements 'pipe'
    4) Detects and responds to dropped packets (see below)
    5) Possibly sends up to (cwnd-pipe) Data packets


---- Dropped Packet Detection ----
But this is where I get especially fuzzy. The closest I've come up with so far is the sender maintains 'dropstart', which is the last sequence number searched for drops (ie, the starting point for this search), and 'dataVector', which is (conceptually) a bit vector stating whether a particular segnum was sent as a data or non-data packet. It would generally work as follows:

onDrop( segnum )
{
    // Ignore if it's not a data packet
    if( dataVector[segnum] )
    {
        // Update for a dropped data packet
        pipe--;
        // ... update 'cwnd' and 'ssthresh' ...
    }
}

detectAndHandleDrops( ackStart, ackEnd, ackVector )
{
    // First check those that come before our Ack vector
    if( dropstart < ackStart )
    {
        // See if three or more have been delivered at all
        if( COUNTACKS( ackStart, ackEnd, ackVector ) >= 3 )
        {
            // All unacked packets have been dropped
            for( c=dropStart; c<ackStart; ++c )
                onDrop( c );
        }
        dropstart = ackStart;
    }

    // Skip past any segnums that have already been Ack'd
    while( ackVector[dropstart] ) ++dropstart;

    // Test remaining segnums that overlap this Ack vector
    for( c=dropstart; c<(ackEnd-3); ++c )
        if( !ackVector[c] )
        {
            // See if it is followed by 3 Acks
            if( COUNTACKS( c, ackEnd, ackVector ) >= 3 )
            {
                // Assume this has been dropped
                onDrop( c );
                dropstart = c;
            }
        }
}

I think this gets me into the ballpark. But this whole area is full of subtle, unintented consequences, so I suspect there are more holes that I'm missing (both algorithmic, as well as due to my misunderstanding the spec). What flaws do you see?

This is, as you say, getting there, but it's not there yet. In particular, I don't think it handles a division of ack vector information into multiple packets. I would say something like this. Again, no ECN, and I didn't bother with the dropstart optimization.

struct sent_packet_info {
    unsigned is_data : 1;
    unsigned acknowledged : 1;
    unsigned lost : 1;
    unsigned rtt;
} data_vector[];

send_packet() {
    ...
    data_vector[seqno].is_data = /* 1 or 0, depending */;
    data_vector[seqno].acknowledged = 0;
    data_vector[seqno].lost = 0;
    data_vector[seqno].rtt = current "round":
            how many RTTs have passed since connection began;
            /* could also do this with timestamps &
               stored RTT estimates */
}

handle_ack_vector(ackvec) {
    for each ackno where ackvec[ackno].state != 3 {
        if (data_vector[ackno].lost)
            /* potentially recover cwnd from false loss */;
        else if (!data_vector[ackno].acknowledged)
            pipe--;
        data_vector[ackno].acknowledged = 1;
    }

    let lost_before equal the largest seqno so that
        there exist NUMDUPACK different seqnos S
           where S >= lost_before and data_vector[S].acknowledged == 1;

for each seqno < lost_before in data_vector {
if (!data_vector[seqno].acknowledged && !data_vector [seqno].lost) {
pipe--;
for each S where data_vector[S].rtt == data_vector [seqno].rtt {
if (data_vector[S].lost)
goto already_cut_cwnd;
}
adjust cwnd etc.;
already_cut_cwnd:
data_vector[seqno].lost = 1;
}
}

Clear as mud, no?
Eddie




Thanks!

-david