wcett.c

Vitual Ring Routing 管你知不知道

// -*- mode: C++; tab-width: 4; indent-tabs-mode: nil -*- (for GNU Emacs)
//
// (c) Microsoft Corporation. All rights reserved. 
//
// This file is part of the Microsoft Virtual Ring Routing distribution.
// You should have received a copy of the Microsoft Research Shared Source
// license agreement (MSR-SSLA) for this software; see the file "license.txt".
// If not, please see http://research.microsoft.com/vrr/license.htm,
// or write to Microsoft Research, One Microsoft Way, Redmond, WA 98052-6399.
//
// This file is derived from the Microsoft Research Mesh Connectivity Layer,
// available under the MSR-SSLA license, and downloadable from
// http://research.microsoft.com/mesh/.
//

#include "headers.h"

//
// 1 second probe period. 
//
//  -- moved to headers.h
//#define DEFAULT_WCETT_PROBE_PERIOD (1 * SECOND)

//
// 30 second loss interval.
//
//  -- moved to headers.h
//#define DEFAULT_WCETT_LOSS_INTERVAL (30 * SECOND)
//#define DEFAULT_WCETT_LOSS_INTERVAL (5 * SECOND)

//
// When a data packet is dropped, we take an additional
// penalty.
//
#define DEFAULT_WCETT_PENALTY_FACTOR 3            

//
// This is the weight given to the bottleneck-channel ETT,
// versus the overall path ETT. Scaled by MAXALPHA of 10.
//
#define DEFAULT_WCETT_BETA      1

//
// This is the smoothing factor used for loss rate calulations.
// Scaled by MAXALPHA of 10.
//  -- moved to headers.h
//#define DEFAULT_WCETT_ALPHA     1
//#define DEFAULT_WCETT_ALPHA     3

//
// Loss probabilities greater than this indicate that the link is broken.
//
//  -- moved to headers.h
//#define DEFAULT_WCETT_BROKEN    4055 // About 99% loss probability.

//
// The initial loss probability for a link, absent any real information.
//
//  -- moved to headers.h
//#define DEFAULT_WCETT_INITIAL   2048 // 50% loss probability.

//
// The minimum congestion window, in time units.
//
#define WCETT_CWMIN     (320 * MICROSECOND)

//
// How often to probe for bandwidth measurement.
//
//  -- moved to headers.h
//#define DEFAULT_WCETT_PKTPAIR_PROBE_PERIOD (60 * SECOND)
//#define DEFAULT_WCETT_PKTPAIR_MIN_OVER_PROBES 10

//* WcettDefaultBandwidth
//
//  Given the maximum bandwidth of a link in bps,
//  calculates a default bandwidth in bps.
//
__inline uint
WcettDefaultBandwidth(uint Bandwidth)
{
    return Bandwidth / 2;
}

//* WcettEncodeBandwidth
//
//  Converts bandwidth in bps to our 12-bit encoded format.
//  Bandwidth is encoded with a 10-bit mantissa and a 2-bit exponent:
//      bps = Bmant * (1000 ^ (Bexp + 1))
//  In other words, Bexp = 0 means Kbps, Bexp = 1 means Mbps, etc.
//
uint
WcettEncodeBandwidth(uint Bandwidth)
{
    uint Bexp;

    for (Bexp = 0; Bandwidth >= 1000; Bexp++)
        Bandwidth /= 1000;
    VRRASSERT(Bexp <= 4);

    if (Bexp == 0)
        return 0;
    else
        return (Bandwidth << 2) | (Bexp - 1);
}

//* WcettDecodeBandwidth
//
//  Converts bandwidth in our 12-bit encoded format to bps.
//  Bandwidth is encoded with a 10-bit mantissa and a 2-bit exponent:
//      bps = Bmant * (1000 ^ (Bexp + 1))
//  In other words, Bexp = 0 means Kbps, Bexp = 1 means Mbps, etc.
//
uint
WcettDecodeBandwidth(uint Bandwidth)
{
    uint Bexp = Bandwidth & 3;
    uint Bmant = Bandwidth >> 2;

    Bandwidth = Bmant * 1000;
    while (Bexp != 0) {
        Bandwidth *= 1000;
        Bexp--;
    }

    return Bandwidth;
}

//* WcettConvertPktPairDelayToBandwidth
//
//  Converts packet-pair delay in 100ns units to bandwidth in bps.
//
__inline uint
WcettConvertPktPairDelayToBandwidth(uint Delay)
{
    //
    // Delay is in 100ns units and we measure a 1088-byte packet.
    // Calculate Bandwidth in bps.
    //
    return ((1088 * 8 * 100000) / Delay) * 100;
}

//* WcettIsInfinite
//
//  Returns TRUE if the link metric indicates that the link
//  is effectively broken.
//
boolint
WcettIsInfinite(uint Metric)
{
    WCETTMetric *wcett = (WCETTMetric *)&Metric;

    return (wcett->LossProb > DefaultWcettBroken);
}

//* WcettChannel
//
//  Extracts the channel from a link metric.
//
__inline uint
WcettChannel(uint LinkMetric)
{
    WCETTMetric *wcett = (WCETTMetric *)&LinkMetric;
    return wcett->Channel;
}

//* WcettConvETT
//
//  Converts a link metric (loss probability & bandwidth) to ETT.
//  The ETT value uses 100-ns time units.
//
uint
WcettConvETT(uint LinkMetric)
{
    WCETTMetric *wcett = (WCETTMetric *)&LinkMetric;
    uint Temp;
    uint Backoff;
    uint Bandwidth;
    uint Transmit;

    //
    // First calculate a temp value (scaled by 4096)
    // from the loss probability (which is scaled by 4096):
    //   Temp = 1 + p + 2p^2 + 4p^3 + 8p^4 + 16p^5 + 32p^6 + 64p^7
    //
    Temp = 4096 + 2 * wcett->LossProb;
    Temp = (4096*4096 + 2 * wcett->LossProb * Temp) / 4096;
    Temp = (4096*4096 + 2 * wcett->LossProb * Temp) / 4096;
    Temp = (4096*4096 + 2 * wcett->LossProb * Temp) / 4096;
    Temp = (4096*4096 + 2 * wcett->LossProb * Temp) / 4096;
    Temp = (4096*4096 + 2 * wcett->LossProb * Temp) / 4096;
    Temp = (4096*4096 + wcett->LossProb * Temp) / 4096;
    //
    // Now finish the backoff calculation, converting to time units:
    //  Backoff = (CWmin / 2) * (Temp / (1 - p))
    //
    Backoff = (WCETT_CWMIN * Temp) / (2 * (4096 - wcett->LossProb));

    //
    // Calculate the transmission time for a 1024-byte packet,
    // converting to time units:
    //  Transmit = (S / B) * (1 / (1 - p))
    // We use S = 1024 bytes.
    // So we want to calculate
    //  Transmit = (8 * 1024 * SECOND * 4096) / (B * (4096 - wcett->LossProb))
    // We divide both numerator & denominator by 1024 * 1024.
    //
    Bandwidth = WcettDecodeBandwidth(wcett->Bandwidth);
    if (Bandwidth >= 1024 * 1024)
        Temp = ((Bandwidth / 1024) * (4096 - wcett->LossProb)) / 1024;
    else
        Temp = (Bandwidth * (4096 - wcett->LossProb)) / (1024 * 1024);
    if (Temp == 0)
        return (uint)-1;
    else
        Transmit = (4 * 8 * SECOND) / Temp;

    if (Backoff + Transmit < Transmit)
        return (uint)-1;

    return Backoff + Transmit;
}

//* WcettCalcWCETT
//
//  Calculates the WCETT metric of an array of links.
//
//  Called with the link cache locked.
//
uint
WcettCalcWCETT(
    MiniportAdapter *VA,
    Link **Hops,
    uint NumHops)
{
    uint ETT, MCETT;
    uint WCETT;
    uint i, j;
    
    VRRASSERT(NumHops <= MAX_SR_LEN);

    //
    // Calculate sum of ETT for each link.
    //
    ETT = 0;
    for (i = 0; i < NumHops; i++) {
        uint New;

        //
        // Check for a broken link.
        //
        if (WcettIsInfinite(Hops[i]->Metric))
            return (uint)-1;

        //
        // Check for overflow.
        //
        New = ETT + WcettConvETT(Hops[i]->Metric);
        if (New < ETT)
            return (uint)-1;
        ETT = New;
    }
    
    //
    // Calculate maximum of ETTs for each channel.
    // We do not have to worry about overflow or broken links,
    // because of the prior checks.
    //
    MCETT = 0;
    for (i = 0; i < NumHops; i++) {
        uint CETT = 0;
        for (j = 0; j < NumHops; j++) {
            if (WcettChannel(Hops[i]->Metric) == WcettChannel(Hops[j]->Metric))
                CETT += WcettConvETT(Hops[j]->Metric);
        }
        if (CETT > MCETT)
            MCETT = CETT;
    }

    VRRASSERT(MCETT <= ETT);
    WCETT = ((ETT * (MAXALPHA - VA->MetricParams.Wcett.Beta)) + (MCETT * VA->MetricParams.Wcett.Beta)) / MAXALPHA;

    //
    // If WCETT is not between ETT and MCETT, we overflowed.
    //
    if ((MCETT <= WCETT) && (WCETT <= ETT))
        return WCETT;
    else
        return (uint)-1;
}

//* WcettInitLinkMetric
//
// Init metric information for a new link. 
//
void 
WcettInitLinkMetric(
    MiniportAdapter *VA,
    int SNode,
    Link *Link, 
    Time Now)
{
    ProtocolAdapter *PA;
    uint i;
    uint Diff;

    //
    // Start with an initial loss probability.
    //
    Link->wcett.LossProb = DefaultWcettInitial;

    if ((SNode == 0) &&
        ((PA = FindPhysicalAdapterFromIndex(VA, Link->outif)) != NULL)) {
        uint Bandwidth;
        //
        // Get the max bandwidth and channel from our physical interface,
        // and calculate an initial bandwidth from the max.
        //
        Link->wcett.Channel = PA->Channel;
        Bandwidth = WcettDecodeBandwidth(PA->Bandwidth);
        Link->MetricInfo.Wcett.MaxBandwidth = Bandwidth;
        Bandwidth = WcettDefaultBandwidth(Bandwidth);
        Link->wcett.Bandwidth = WcettEncodeBandwidth(Bandwidth);
    }
    else {
        //
        // We don't know the bandwidth and channel yet.
        //
        Link->wcett.Channel = 0;
        Link->MetricInfo.Wcett.MaxBandwidth = 0;
        Link->wcett.Bandwidth = 0;
    }

    Link->MetricInfo.Wcett.Etx.TotSentProbes = 0;
    Link->MetricInfo.Wcett.Etx.TotRcvdProbes = 0;
    Link->MetricInfo.Wcett.Etx.FwdDeliv = 0;
    Link->MetricInfo.Wcett.Etx.ProbeHistorySZ = 0;
    Link->MetricInfo.Wcett.Etx.PHStart = 0;
    Link->MetricInfo.Wcett.Etx.PHEnd = 0;
    for (i = 0; i < MAX_ETX_PROBE_HISTORY; i++) { 
        Link->MetricInfo.Wcett.Etx.PH[i].RcvdTS = 0;
    }

    //
    // We use PktPair just to measure link bandwidth.
    //

    //
    // PktPair sender-specific info.
    //
    Link->MetricInfo.Wcett.PktPair.ProbeSeq = 0;
    Link->MetricInfo.Wcett.PktPair.PairsSent = 0;