scoreboard-rh.cc

Go to the documentation of this file.

/* -*-  Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 1996 The Regents of the University of California.
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *  This product includes software developed by the Network Research
 *  Group at Lawrence Berkeley National Laboratory.
 * 4. Neither the name of the University nor of the Laboratory may be used
 *    to endorse or promote products derived from this software without
 *    specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */


/* 9/96 Pittsburgh Supercomputing Center
 *      UpdateScoreBoard, CheckSndNxt, MarkRetran modified for fack
 */

#ifndef lint
static const char rcsid[] =
    "@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/tcp/scoreboard-rh.cc,v 1.2 2000/08/12 21:45:39 sfloyd Exp $ (LBL)";
#endif

/*  A quick hack version of the scoreboard  */
#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>
#include <math.h>

#include "packet.h"
#include "scoreboard-rh.h"
#include "tcp.h"

#define ASSERT(x) if (!(x)) {printf ("Assert SB failed\n"); exit(1);}
#define ASSERT1(x) if (!(x)) {printf ("Assert1 SB (length)\n"); exit(1);}

#define SBNI SBN[i%SBSIZE]

// last_ack = TCP last ack
int ScoreBoardRH::UpdateScoreBoard (int last_ack, hdr_tcp* tcph, int rh_id)
{
    int i, sack_index, sack_left, sack_right;
    int sack_max = 0;
    int retran_decr = 0;

    /* Can't do this, because we need to process out the retran_decr  */
#if 0
    if (tcph->sa_length() == 0) {
        // There are no SACK blocks, so clear the scoreboard.
        this->ClearScoreBoard();
        return(0);
    }
#endif

    /*  What we do need to do is not create a scoreboard if we don't need one.  */
    if ((tcph->sa_length() == 0) && (length_ == 0)) {
        return(0);
    }
    

    //  If there is no scoreboard, create one.
    if (length_ == 0) {
        i = last_ack+1;
        SBNI.seq_no_ = i;
        SBNI.ack_flag_ = 0;
        SBNI.sack_flag_ = 0;
        SBNI.retran_ = 0;
        SBNI.snd_nxt_ = 0;
        SBNI.sack_cnt_ = 0;
        SBNI.rh_id_ = 0;
        first_ = i%SBSIZE;
        length_++;
        if (length_ >= SBSIZE) {
            printf ("Error, scoreboard too large (increase SBSIZE for more space)\n");
            exit(1);
        }
    }   

    //  Advance the left edge of the block.
    if (SBN[first_].seq_no_ <= last_ack) {
        for (i=SBN[(first_)%SBSIZE].seq_no_; i<=last_ack; i++) {
            //  Advance the ACK
            if (SBNI.seq_no_ <= last_ack) {
                ASSERT(first_ == i%SBSIZE);
                first_ = (first_+1)%SBSIZE; 
                length_--;
                ASSERT1(length_ >= 0);
                SBNI.ack_flag_ = 1;
                SBNI.sack_flag_ = 1;
                if (SBNI.retran_) {
                    SBNI.retran_ = 0;
                    SBNI.snd_nxt_ = 0;
                    retran_decr++;
                    retran_sacked_ = rh_id;
                }
                if (length_==0) 
                    break;
            }
        }
    }

    for (sack_index=0; sack_index < tcph->sa_length(); sack_index++) {
        sack_left = tcph->sa_left(sack_index);
        sack_right = tcph->sa_right(sack_index);

        /*  Remember the highest segment SACKed by this packet  */
        if (sack_right > sack_max) {
            sack_max = sack_right;
        }

        //  Create new entries off the right side.
        if (sack_right > SBN[(first_+length_+SBSIZE-1)%SBSIZE].seq_no_) {
            //  Create new entries
            for (i = SBN[(first_+length_+SBSIZE-1)%SBSIZE].seq_no_+1; i<sack_right; i++) {
                SBNI.seq_no_ = i;
                SBNI.ack_flag_ = 0;
                SBNI.sack_flag_ = 0;
                SBNI.retran_ = 0;
                SBNI.snd_nxt_ = 0;
                SBNI.sack_cnt_ = 0;
                SBNI.rh_id_ = 0;
                length_++;
                if (length_ >= SBSIZE) {
                    printf ("Error, scoreboard too large (increase SBSIZE for more space)\n");
                    exit(1);
                }
            }
        }
        
        for (i=SBN[(first_)%SBSIZE].seq_no_; i<sack_right; i++) {
            //  Check to see if this segment is now covered by the sack block
            if (SBNI.seq_no_ >= sack_left && SBNI.seq_no_ < sack_right) {
                if (! SBNI.sack_flag_) {
                    SBNI.sack_flag_ = 1;
                }
                if (SBNI.retran_) {
                    SBNI.retran_ = 0;
                    SBNI.snd_nxt_ = 0;
                    retran_decr++;
                    retran_sacked_ = rh_id;
                }
            }
        }
    }

    /*  Now go through the whole scoreboard and update sack_cnt
        on holes which still exist.  */
    if (length_ != 0) {
        for (i=SBN[(first_)%SBSIZE].seq_no_; i<sack_max; i++) {
            //  Check to see if this segment is a hole
            if (!SBNI.ack_flag_ && !SBNI.sack_flag_) {
                SBNI.sack_cnt_++;
            }
        }
    }

    retran_decr += CheckSndNxt(sack_max);

    return (retran_decr);
}
int ScoreBoardRH::CheckSndNxt (int sack_max)
{
    int i;
    int num_lost = 0;

    if (length_ != 0) {
        for (i=SBN[(first_)%SBSIZE].seq_no_; i<sack_max; i++) {
            //  Check to see if this segment's snd_nxt_ is now covered by the sack block
            if (SBNI.retran_ && SBNI.snd_nxt_ < sack_max) {
                // the packet was lost again
                SBNI.retran_ = 0;
                SBNI.snd_nxt_ = 0;
                SBNI.sack_cnt_ = 1;
                num_lost++;
            }
        }
    }
    return (num_lost);


}

void ScoreBoardRH::ClearScoreBoard()
{
    length_ = 0;
}

/*
 * GetNextRetran() returns "-1" if there is no packet that is
 *   not acked and not sacked and not retransmitted.
 */
int ScoreBoardRH::GetNextRetran()   // Returns sequence number of next pkt...
{
    int i;

    if (length_) {
        for (i=SBN[(first_)%SBSIZE].seq_no_; 
             i<SBN[(first_)%SBSIZE].seq_no_+length_; i++) {
            if (!SBNI.ack_flag_ && !SBNI.sack_flag_ && !SBNI.retran_
                && (SBNI.sack_cnt_ >= *numdupacks_)) {
                return (i);
            }
        }
    }
    return (-1);
}


void ScoreBoardRH::MarkRetran (int retran_seqno, int snd_nxt, int rh_id)
{
    SBN[retran_seqno%SBSIZE].retran_ = 1;
    SBN[retran_seqno%SBSIZE].snd_nxt_ = snd_nxt;
    SBN[retran_seqno%SBSIZE].rh_id_ = rh_id;
    retran_occured_ = rh_id;
}

int ScoreBoardRH::GetFack (int last_ack)
{
    if (length_) {
        return(SBN[(first_)%SBSIZE].seq_no_+length_-1);
    }
    else {
        return(last_ack);
    }
}

int ScoreBoardRH::GetNewHoles ()
{
    int i, new_holes=0;

    for (i=SBN[(first_)%SBSIZE].seq_no_;
         i<SBN[(first_)%SBSIZE].seq_no_+length_; i++) {
        //  Check to see if this segment is a new hole
#if 1
        if (!SBNI.ack_flag_ && !SBNI.sack_flag_ && SBNI.sack_cnt_ == 1) {
            new_holes++;
        }
#else
        if (!SBNI.ack_flag_ && !SBNI.sack_flag_ && SBNI.sack_cnt_ == *numdupacks_) {
            new_holes++;
        }
#endif
    }
    return (new_holes);
}

void ScoreBoardRH::TimeoutScoreBoard (int snd_nxt)
{
    int i, sack_right;

    if (length_ == 0) {
        // No need to do anything!  
        return;
    }

    sack_right = snd_nxt;  // Use this to know how far to extend.

    //  Create new entries off the right side.
    if (sack_right > SBN[(first_+length_+SBSIZE-1)%SBSIZE].seq_no_) {
        //  Create new entries
        for (i = SBN[(first_+length_+SBSIZE-1)%SBSIZE].seq_no_+1; i<sack_right; i++) {
            SBNI.seq_no_ = i;
            SBNI.ack_flag_ = 0;
            SBNI.sack_flag_ = 0;
            SBNI.retran_ = 0;
            SBNI.snd_nxt_ = 0;
            SBNI.sack_cnt_ = 0;
            SBNI.rh_id_ = 0;
            length_++;
            if (length_ >= SBSIZE) {
                printf ("Error, scoreboard too large (increase SBSIZE for more space)\n");
                exit(1);
            }
        }
    }

    /*  Now go through the whole scoreboard and update sack_cnt on holes;
        clear retran flag on everything.  */
    for (i=SBN[(first_)%SBSIZE].seq_no_;
         i<SBN[(first_)%SBSIZE].seq_no_+length_; i++) {
        //  Check to see if this segment is a hole
        if (!SBNI.ack_flag_ && !SBNI.sack_flag_) {
            SBNI.retran_ = 0;
            SBNI.snd_nxt_ = 0;
            SBNI.sack_cnt_ = *numdupacks_;  // This forces all holes to be retransmitted.
        }
    }

    /*  And, finally, check the first segment in case of a renege.  */
    i=SBN[(first_)%SBSIZE].seq_no_;
    if (!SBNI.ack_flag_ && SBNI.sack_flag_) {
        printf ("Renege!!! seqno = %d\n", SBNI.seq_no_);
        SBNI.sack_flag_ = 0;
        SBNI.retran_ = 0;
        SBNI.snd_nxt_ = 0;
        SBNI.sack_cnt_ = *numdupacks_;  // This forces it to be retransmitted.
    }
}

#if 0
/*  This routine inserts a fake sack block of length num_dupacks,
    starting at last_ack+1.  It is for use during NewReno recovery.
*/
int ScoreBoardRH::FakeSack (int last_ack, int num_dupacks)
{
    int i, sack_left, sack_right;
    int retran_decr = 0;

    //  If there is no scoreboard, create one.
    if (length_ == 0) {
        i = last_ack+1;
        SBNI.seq_no_ = i;
        SBNI.ack_flag_ = 0;
        SBNI.sack_flag_ = 0;
        SBNI.retran_ = 0;
        SBNI.snd_nxt_ = 0;
        SBNI.sack_cnt_ = 0;
        SBNI.rh_id_ = 0;
        first_ = i%SBSIZE;
        length_++;
        if (length_ >= SBSIZE) {
            printf ("Error, scoreboard too large (increase SBSIZE for more space)\n");
            exit(1);
        }
    }   

    //  Advance the left edge of the scoreboard.
    if (SBN[first_].seq_no_ <= last_ack) {
        for (i=SBN[(first_)%SBSIZE].seq_no_; i<=last_ack; i++) {
            //  Advance the ACK
            if (SBNI.seq_no_ <= last_ack) {
                ASSERT(first_ == i%SBSIZE);
                first_ = (first_+1)%SBSIZE; 
                length_--;
                ASSERT1(length_ >= 0);
                SBNI.ack_flag_ = 1;
                SBNI.sack_flag_ = 1;
                if (SBNI.retran_) {
                    SBNI.retran_ = 0;
                    SBNI.snd_nxt_ = 0;
                    retran_decr++;
                }
                if (length_==0) 
                    break;
            }
        }
        /*  Now create a new hole in the first position  */
        i=SBN[(first_)%SBSIZE].seq_no_;
        SBNI.ack_flag_ = 0;
        SBNI.sack_flag_ = 0;
        SBNI.retran_ = 0;
        SBNI.snd_nxt_ = 0;
        SBNI.rh_id_ = 0;
        SBNI.sack_cnt_ = num_dupacks;
    }

    sack_left = last_ack + 1;
    sack_right = sack_left + num_dupacks - 1;

    //  Create new entries off the right side.
    if (sack_right > SBN[(first_+length_+SBSIZE-1)%SBSIZE].seq_no_) {
        //  Create new entries
        for (i = SBN[(first_+length_+SBSIZE-1)%SBSIZE].seq_no_+1; i<sack_right; i++) {
            SBNI.seq_no_ = i;
            SBNI.ack_flag_ = 0;
            SBNI.sack_flag_ = 0;
            SBNI.retran_ = 0;
            SBNI.snd_nxt_ = 0;
            SBNI.sack_cnt_ = 0;
            SBNI.rh_id_ = 0;
            length_++;
            if (length_ >= SBSIZE) {
                printf ("Error, scoreboard too large (increase SBSIZE for more space)\n");
                exit(1);
            }
        }
    }
        
    for (i=SBN[(first_)%SBSIZE].seq_no_; i<sack_right; i++) {
        //  Check to see if this segment is now covered by the sack block
        if (SBNI.seq_no_ >= sack_left && SBNI.seq_no_ < sack_right) {
            if (! SBNI.sack_flag_) {
                SBNI.sack_flag_ = 1;
            }
            if (SBNI.retran_) {
                SBNI.retran_ = 0;
                retran_decr++;
            }
        }
    }

    /*  Now go through the whole scoreboard and update sack_cnt
        on holes which still exist.  In this case the only possible 
        case is the first hole.  */
        i=SBN[(first_)%SBSIZE].seq_no_;
    //  Check to see if this segment is a hole
    if (!SBNI.ack_flag_ && !SBNI.sack_flag_) {
        SBNI.sack_cnt_++;
    }

    return (retran_decr);
}

#endif

int ScoreBoardRH::RetranSacked (int rh_id) {
    return (retran_sacked_ == rh_id);
}

---