wcett.c

Vitual Ring Routing 管你知不知道

    Link->MetricInfo.Wcett.PktPair.RepliesSent = 0;
    Link->MetricInfo.Wcett.PktPair.RepliesRcvd = 0;
    Link->MetricInfo.Wcett.PktPair.LostPairs = 0;
    // Ref WcettSendPktPairProbes.
    Diff = VA->MetricParams.Wcett.PktPairProbePeriod + GetRandomNumber(VA->MetricParams.Wcett.PktPairProbePeriod >> 2);
    Link->MetricInfo.Wcett.PktPair.ProbeTimeout = Now + Diff; 
    Link->MetricInfo.Wcett.PktPair.Outstanding = 0;
    Link->MetricInfo.Wcett.PktPair.Delta = 0;
    Link->MetricInfo.Wcett.PktPair.RTT = 0;
    Link->MetricInfo.Wcett.PktPair.LastRTT = 0;
    Link->MetricInfo.Wcett.PktPair.LastPktPair = 0;

    //
    // PktPair receiver-specific info.
    //
    Link->MetricInfo.Wcett.PktPair.LastProbeTimestamp = (uint)-1;
    Link->MetricInfo.Wcett.PktPair.TimeLastProbeRcvd = 0;
    Link->MetricInfo.Wcett.PktPair.LastProbeSeq = (uint)-1;

    //
    // Packetpair minimum. 
    //
    Link->MetricInfo.Wcett.PktPair.CurrMin = (uint)-1;

    Link->MetricInfo.Wcett.NumPktPairValid = 0;
    Link->MetricInfo.Wcett.NumPktPairInvalid = 0;
}


//* WcettInit
//
//  Called by MiniportInitialize.
//
void WcettInit(
    MiniportAdapter *VA)
{
    Time Now = KeQueryInterruptTime();

    VA->IsInfinite = WcettIsInfinite;
    VA->ConvMetric = WcettConvETT;
    VA->InitLinkMetric = WcettInitLinkMetric;
    VA->PathMetric = WcettCalcWCETT;

    VA->MetricParams.Wcett.ProbePeriod = DEFAULT_WCETT_PROBE_PERIOD;

    //
    // Broadcast metric is special. The packets are not sent
    // on a per-link basis, but on a per-node basis.
    //
    VA->MetricParams.Wcett.ProbeTimeout = Now + VA->MetricParams.Wcett.ProbePeriod;

    //
    // We measure loss interval over this time period.
    //
    VA->MetricParams.Wcett.LossInterval = DEFAULT_WCETT_LOSS_INTERVAL;

    VA->MetricParams.Wcett.Alpha = DEFAULT_WCETT_ALPHA;
    VA->MetricParams.Wcett.PenaltyFactor = DEFAULT_WCETT_PENALTY_FACTOR;
    VA->MetricParams.Wcett.Beta = DEFAULT_WCETT_BETA;

    //
    // We use a packet-pair type probe for determining bandwidth.
    //
    VA->MetricParams.Wcett.PktPairProbePeriod = DEFAULT_WCETT_PKTPAIR_PROBE_PERIOD;
    VA->MetricParams.Wcett.PktPairMinOverProbes = DEFAULT_WCETT_PKTPAIR_MIN_OVER_PROBES;
}

//* WcettRemoveOldProbes
//
//  Removes old probes.
//
void
WcettRemoveOldProbes(
    MiniportAdapter *VA,
    Link *Link)
{
    Etx *Etx = &(Link->MetricInfo.Wcett.Etx);
    uint MEPH = MAX_ETX_PROBE_HISTORY;
    uint LI = VA->MetricParams.Wcett.LossInterval;
    Time Now = KeQueryInterruptTime();
    
    VRRASSERT(Link->MetricInfo.Wcett.Etx.ProbeHistorySZ <= MEPH);
    VRRASSERT(Link->MetricInfo.Wcett.Etx.PHStart < MEPH);

    while (((Now - Etx->PH[Etx->PHStart].RcvdTS) >= LI) && (Link->MetricInfo.Wcett.Etx.ProbeHistorySZ > 0)) {
        Etx->PHStart = (Etx->PHStart + 1) % MEPH;
        Link->MetricInfo.Wcett.Etx.ProbeHistorySZ--;
    }

    VRRASSERT(Link->MetricInfo.Wcett.Etx.PHStart < MEPH);
}

//* WcettAddProbe
//
//  Adds a probe to probe history of this link.
//  And while we are at it, also remove old probes
//  from the history.
//
NDIS_STATUS
WcettAddProbe(
    MiniportAdapter *VA,
    Link *Link)
{
    Time Now = KeQueryInterruptTime();
    Etx *Etx = &(Link->MetricInfo.Wcett.Etx);
    uint MEPH = MAX_ETX_PROBE_HISTORY;
    NDIS_STATUS Status;

    if (Etx->ProbeHistorySZ == MEPH) {
        Status = NDIS_STATUS_RESOURCES;
    }
    else {
        Etx->PH[Etx->PHEnd].RcvdTS = Now;
        Etx->PHEnd = (Etx->PHEnd + 1) % MEPH;
        Etx->ProbeHistorySZ++;
        Status = NDIS_STATUS_SUCCESS;
    }

    //
    // Remove old probes. We have to do this here
    // in case the corresponding outgoing link
    // does not exist and so WcettFindDeliveryCounts will not be called.
    //
    WcettRemoveOldProbes(VA, Link);
    return Status;
}

//* WcettFindDeliveryCounts
//
//  Given a link from this node, finds the forward and reverse delivery counts.
//  These numbers are kept in the reverse link.
//
//  Called with the NeighborCache locked.
//
void
WcettFindDeliveryCounts(
    MiniportAdapter *VA,
    Link *FwdLink,
    OUT uint *FwdDeliv,
    OUT uint *RevDeliv)
{
    Link *RevLink;
    NeighborCacheEntry *NCE;

    VRRASSERT(FwdLink->sourceIndex == 0);
    //
    // Given FwdLink=NCE->AdjOut, find NCE->AdjIn
    //
    NCE = CONTAINING_RECORD(FwdLink,NeighborCacheEntry,AdjOut);
    RevLink = &NCE->AdjIn;
    if (RevLink == NULL) {
        //
        // The reverse link does not exist.
        //
        *FwdDeliv = *RevDeliv = 0;
        return;
    }

    VRRASSERT(RevLink->targetIndex == 0);

    //
    // This is the reverse link. We have to remove old probes here,
    // in case we have stopped receiving probes via the reverse link
    // and so WcettAddProbe has not been called recently.
    //
    WcettRemoveOldProbes(VA, RevLink);
    *FwdDeliv = RevLink->MetricInfo.Wcett.Etx.FwdDeliv;
    *RevDeliv = RevLink->MetricInfo.Wcett.Etx.ProbeHistorySZ;
    
    return;
}

//* WcettUpdateMetric
//
//  Update the metric for a given link.
//
//  Only called on adjacent links, meaning the source of the link is node 0.
//
void
WcettUpdateMetric(
    MiniportAdapter *VA,
    Link *Link,
    boolint Penalty)
{
    if (Penalty) {
        uint SuccessProb;

        //
        // We penalize the link delivery probability.
        //
        SuccessProb = 4096 - Link->wcett.LossProb;
        SuccessProb /= VA->MetricParams.Wcett.PenaltyFactor;
        if (SuccessProb == 0)
            SuccessProb = 1;

        Link->wcett.LossProb = 4096 - SuccessProb;

        VRRASSERT(Link->wcett.LossProb < 4096);
    }
    else {
        //
        // We calculate the probability of successful packet delivery.
        // This is the product of forward delivery and reverse delivery.
        //          FwdDeliv * RevDeliv.
        //
        // Let's say that this is link is from us to node X.
        //
        // We know the fwd delivery ratio, i.e. number of probes that
        // we sent that got through to X, from the information carried
        // in the last probe we received from X. This information
        // might be stale, if we haven't heard from X in a while.
        //
        // The rev delivery ratio is the number of probes that we
        // received from X. We know this - this is the ProbeHistorySZ.
        //
        // Note that the FwdDeliv and RevDeliv are computed over
        // LossInterval.  We assume that both nodes have the same
        // sending frequency (ProbePeriod).
        //
        uint Prob;

        if (Link->MetricInfo.Wcett.Etx.TotSentProbes == 0) {
            //
            // We are just getting started and have no data.
            //
            Prob = DefaultWcettInitial;
        }
        else {
            uint NumProbes;
            uint FwdDeliv, RevDeliv;

            //
            // Recall that we randomize probe send times by adding 0-25%
            // of the probe interval.  So, we need to account for that by
            // adding expected number of probes - 12.5%.
            //
            NumProbes = VA->MetricParams.Wcett.LossInterval / (VA->MetricParams.Wcett.ProbePeriod + (VA->MetricParams.Wcett.ProbePeriod >> 3)) ;
            VRRASSERT(NumProbes != 0);

            //
            // When the link is first created and  ProbeHistorySZ/FwdDeliv
            // are ramping up, we must adjust NumProbes appropriately.
            //
            if (Link->MetricInfo.Wcett.Etx.TotSentProbes < NumProbes)
                NumProbes = Link->MetricInfo.Wcett.Etx.TotSentProbes;

            //
            // Find the forward and reverse delivery counts,
            // from the reverse link.
            //
            WcettFindDeliveryCounts(VA, Link, &FwdDeliv, &RevDeliv);

            //
            // Probability is scaled by 4096.
            //
            Prob = (4096 * FwdDeliv * RevDeliv) / (NumProbes * NumProbes);

            //
            // Ensure that the success probability is between 0 and 1,
            // in case ProbeHistorySZ and/or FwdDeliv are too large.
            //
            if (Prob > 4096)
                Prob = 4096;

            //
            // Convert to loss probability.
            //
            Prob = 4096 - Prob;
        }

        Link->MetricInfo.Wcett.Etx.LastProb = Prob;
        //
        // Average loss probability into the old value.
        // LossProb = Alpha * New + (1 - Alpha) * Old
        // Alpha is interpreted as Alpha/MAXALPHA.
        //
        Prob = (VA->MetricParams.Wcett.Alpha * Prob +
                ((MAXALPHA - VA->MetricParams.Wcett.Alpha) * Link->wcett.LossProb))
            / MAXALPHA;

        //
        // The 12-bit field can not hold a loss probability of 1.0 (4096).
        //
        if (Prob >= 4096)
            Prob = 4095;
        Link->wcett.LossProb = Prob;
    }
}

//* WcettPenalize
//
//  Takes Penalty due to data packet drop.
//
//  Only called on adjacent links, meaning the source of the link is node 0.
//
void
WcettPenalize(
    MiniportAdapter *VA,
    Link *Adj)
{
    WcettUpdateMetric(VA, Adj, TRUE);
}

//* WcettUpdateMin
//
//  Update the current min reading for this link.
//  Only called on adjacent links, meaning the source of the link is node 0.
//
static void
WcettUpdateMin(
    Link *Link,
    Time OutDelta)
{
    uint Delay;

    Delay = (uint)OutDelta;
    Link->MetricInfo.Wcett.PktPair.LastPktPair = Delay;

    //
    // Is this a valid sample?
    //
    if ((Delay != 0) &&
        ((Link->MetricInfo.Wcett.MaxBandwidth == 0) ||
         (WcettConvertPktPairDelayToBandwidth(Delay)
                                <= Link->MetricInfo.Wcett.MaxBandwidth))) {
        // 
        // Yes, it is a valid sample.
        // Is it less than current minimum?
        //
        if (Delay < Link->MetricInfo.Wcett.PktPair.CurrMin)
            Link->MetricInfo.Wcett.PktPair.CurrMin = Delay;
        Link->MetricInfo.Wcett.NumPktPairValid++;
    }
    else {
        //
        // No, the resulting bandwidth is too large.
        //
        Link->MetricInfo.Wcett.NumPktPairInvalid++;
    }
}

//* WcettUpdateBandwidth
//
//  Update the bandwidth measurement on the given link.
//
static void
WcettUpdateBandwidth(
    Link *Link)
{
    uint Bandwidth;

    if (Link->MetricInfo.Wcett.PktPair.CurrMin == (uint)-1) {