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

Re: [ns] Vegas Retransmission mechanism



> 1) Does Vegas decrease its cwnd after receiving the 1st non-duplicate ACK to
>  3/4 of its value before the 1st loss was detected??
Yes, sort of. It actually decreases cwnd to 3/4 the value of the effective
window before the loss (3/4 * min(congestion window, flow window)).

> 2) Is the original Vegas (even in ns-2.1b7) have a problem where the
> packet transmissions during recovery decreases until no packets could be
> transmitted?? At this point, since no ACKs can be received, a timeout
> has to occur.
Vegas checks with the following code (expired>=0 means we're timing out,
numdupacks_ defaults to 3)
    if (expired>=0 || dupacks_ == numdupacks_) {
        .. do a fast retransmit ..
    } else if (dupacks_ > numdupacks_) {
        ++cwnd_;
    }
So it will fast retransmit one packet per RTT, and for each ack beyond 3 will
inflate the congestion window by 1. This should allow another packet to be sent
across the wire to keep probing the network and getting back ack information.
(Effectively, ignoring the loss and maintaining an effective 3/4 send rate until
the hole is filled).

>From what I understand, Vegas can only recover 2 more packets beyond the
> 1st one lost during one RTT?? If that's the case I wanna make changes to
> vegas to ensure that it recovers all packets in cwnd that were sent
> prior to the invocation of fast retransmit mechanism.
> I just need to change vegas to make sure that vegas keeps transmitting
> packets at the 3/4th rate continously, but not sure where exactly in the
> code this could be done.
Uh... AFAIK the code as implemented can only recover a single loss via the fast
retransmit mechanism; beyond that timeouts are required. I guess I'm not sure
what you mean by recovering packets *prior* to the invocation of fast
retransmit? Do you mean just retransmitting all packets [dupack+1 .. last
segment transmitted before duplicate ack received]? If so, Vegas in ns does not
do this.

> I want to keep track of the last segment sent before duplicate ACKs were
> received.
The number of this is stored as int recover_, the simulation code only keeps
track of metadata not actual segments.

> Until an ack for this latter segment is received, I want to make a
> modification to vegas code to ensure recovery is not terminated. I'm
> finding trouble in knowing where exactly in the code is recovery
> terminated. Can anyone help me with this? Does vegas already do what I'm
> thinking of doing?
I'm unclear on what you want to do exactly, but see below for more information.
 
> Can anyone please pin point to me where can I find these issues in the
> code. I really appreciate any help or comments.
All vegas code is found in the file tcp-vegas.cc, however vegas is derived from
the tcp base class which is found in tcp.cc and tcp.h, so some important
functions are found in those files.
Most processing is driven by the recv() function in tcp-vegas.cc, called when a
packet is received by the Vegas agent.

Be warned that there are at least two bugs in the source having to do with
instrumentation that have not yet been added to CVS. I'll post a patch to the
list in a few hours and hopefully it'll make it into the tree.

Once upon a time I went through the Vegas code and converted it into a pseudo-C
code. It was helpful in understanding the algorithm, although I'm sure I
introduced some errors in the conversion (i.e. take look at the real code if
something seems wrong). I'm attaching that file, you might find it a useful
starting point or reference when looking at the actual vegas code in ns.

-Eric

--------------------------------------------
 Eric H. Weigle   CCS-1, RADIANT team
 [email protected]     Los Alamos National Lab
 (505) 665-4937   http://home.lanl.gov/ehw/
--------------------------------------------
void VegasTcpAgent::recv(Packet *pkt, Handler *) {
    increment ack packet count.

    if this is an ECN echo packet,
        handle it (possibly cut CWND and slow-start threshold by 1/2)
        
    // First big part of this function; the sequential ack case.
    if this is a sequential ack (sequence number > last ack received) {

        if new connection and set to delay growth until 1st data received,
            set congestion window to initial window.

        if received at least 3 (configurable) duplicate acks and congestion window was inflated {
            ensure slow start is off (set ssthresh=2)
            reset congestion window to:
            { 2 if old window was <=3
              3/4 * old window if transmitted packet only once
              1/2 * old window otherwise } <-- these choices were made when the duplicate ack was recieved, earlier.
        }

        via function recv_newack_helper(pkt) {
            update RTT timing if it is valid to do so.
            update average window.
            henceforth consider this ack packet as the last_ack_
            
            if the connection is done, terminate it.
        }
    
        // This next section is performed once per RTT.
        //  1. update path baseRTT
        //  2. decide what to do with cwnd_, inc/dec/unchanged
        if this packet's sequence number is greater than or equal to our tag (v_begseq_) {
            if this test isn't degenerate (we have actually measured for an RTT) then {

                if there's only one pkt in transit
                    update baseRTT

                calculate delta in packets (= (expected pkts/sec - actual pkts/sec) * base RTT(sec))

                if in slow start (congestion window < slow start threshold) {
                    we adjust congestion window every other round trip time.
                    if this round trip time is one where we adjust {
                        if delta is greater than gamma parameter {
                            turn off slow start (set slow start threshold = 2)
                            slow down a bit (cwnd to max(7/8 * cwnd, 2))
                        } else {
                            plan to increment cwnd by 1 for this packet.
                        }
                    }
                } else (in congestion avoidance, not slow start) {
                    if delta > beta_ parameter {
                        set cwnd to max(current cwnd-1, 2)
                        plan to NOT increment cwnd in the next RTT.
                    } else if delta < alpha parameter {
                        plan to increment cwnd by 1/cwnd
                    } else {
                        current rate is cool-- plan to leave cwnd alone.
                    }
                }
            }

            set up tag the next packet we will send (set v_begseq_ = sequence no, etc.)
        } // end of once per-rtt section

        since we set how much to incr only once per rtt,
           check if we surpass ssthresh during slow-start
           before the rtt is over
        
        increment the cwnd unless we havent been able to keep up with it

        if we need to update the fine grained timeout value,
          do so.


        check the 1st or 2nd acks after dup ack received,
        if any pkt has been timeout, retransmit it. but do NOT change cwnd here.

    // Second big part of this function; the duplicate ack case.
    } else if this is a duplicate ack {
        if a timeout should occur or we have 3 (configurable) duplicate acks, (plus misc. programmatic conditions) {
             // Fast retransmit handling.

             set timeout+= 1/8*timeout if only sent once,
             otherwise double timeout (v_rto expon. backoff)

             if the congestion window hasn't changed since the pkt was sent {
                 record proper value for reset after receive next sequential ack (above)

                 inflate cwnd_ by the number of duplicate acks.
            } 

            update coarser grained rto

            retransmit.
        } else if the current number of duplicate acks is greater than 3 (configurable) {
            increment (inflate) the congestion window by 1
        }
    }

    if have a maximum congestion window parameter, limit the size of the congestion window here.

    Try to send more data, if possible.
}