pktpair.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/.
//
// Abstract:
//
// Packet pair measurements.
//

#include "headers.h"

// 
// The basic algorithm is as follows: each node sends 
// two packets, back-to-back, to each of its neighbors. 
// The neighbor responds back to the second packet, 
// and reports the time difference between the two 
// receive events. If no response is received by the 
// time we are ready to send the next packet-pair, 
// the sender takes a penalty of 3 times the current 
// average.
// 

//
// Default PKT_PAIR parameter values.
//

// Scaled by MAXALPHA of 10, this becomes 0.1.  
#define DEFAULT_PKT_PAIR_ALPHA  1

// 2 second probe period. 
#define DEFAULT_PKT_PAIR_PROBE_PERIOD (2 * SECOND)

// PKT_PAIR penalty factor of 3.
#define DEFAULT_PKT_PAIR_PENALTY_FACTOR 3            

// Initial Packet pair estimate.
#define INITIAL_PKTPAIR_ESTIMATE (1 * MILLISECOND)

// Probe padding size.
#define PROBE_PADDING 1000

// Calculate min over this multiple of probe period.
#define MIN_OVER_PROBES 50

// Values larger than this are considered infinite.
#define DEFAULT_PKT_PAIR_INFINITY (30 * MILLISECOND)

//* PktPairIsInfinite
//
//  Returns TRUE if the link metric indicates that the link
//  is effectively broken.
//
boolint
PktPairIsInfinite(uint Metric)
{
    return (Metric > DEFAULT_PKT_PAIR_INFINITY);
}

//* PktPairInitLinkMetric
//
// Init metric informtion for a new link.
//
void 
PktPairInitLinkMetric(
    MiniportAdapter *VA,
    int SNode,
    Link *Link, 
    Time Now)
{
    uint i; 

    UNREFERENCED_PARAMETER(SNode);

    //
    // The basic metric.
    //
    Link->Metric = INITIAL_PKTPAIR_ESTIMATE;

    //
    // PktPair sender-specific info.
    //
    Link->MetricInfo.PktPair.ProbeSeq = 0;
    Link->MetricInfo.PktPair.PairsSent = 0;
    Link->MetricInfo.PktPair.RepliesSent = 0;
    Link->MetricInfo.PktPair.RepliesRcvd = 0;
    Link->MetricInfo.PktPair.LostPairs = 0;
    Link->MetricInfo.PktPair.ProbeTimeout = Now + 
                                            VA->MetricParams.PktPair.ProbePeriod +
                                            GetRandomNumber(VA->MetricParams.PktPair.ProbePeriod >> 2);
    Link->MetricInfo.PktPair.Outstanding = 0; 
    Link->MetricInfo.PktPair.Delta = 0; 
    Link->MetricInfo.PktPair.RTT = INITIAL_PKTPAIR_ESTIMATE; 
    Link->MetricInfo.PktPair.LastRTT = 0; 
    Link->MetricInfo.PktPair.LastPktPair = 0; 

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

    //
    // Min Time History. 
    //
    Link->MetricInfo.PktPair.CurrMin = (uint)-1; 
    Link->MetricInfo.PktPair.NumSamples = 0;
    Link->MetricInfo.PktPair.NextMinTime = Now + VA->MetricParams.PktPair.ProbePeriod * MIN_OVER_PROBES; 
    for (i = 0; i < MAX_PKTPAIR_HISTORY; i++) { 
        Link->MetricInfo.PktPair.MinHistory[i].Min = (uint)-1; 
        Link->MetricInfo.PktPair.MinHistory[i].Seq = (uint)-1;
    }
}

//* PktPairInit
// 
//  Called by MiniportInitialize.
//
void PktPairInit(
    MiniportAdapter *VA) 
{
    VA->IsInfinite = PktPairIsInfinite;
    VA->ConvMetric = MiniportConvMetric;
    VA->PathMetric = MiniportPathMetric;
    VA->InitLinkMetric = PktPairInitLinkMetric;

    VA->MetricParams.PktPair.Alpha = DEFAULT_PKT_PAIR_ALPHA;
    VA->MetricParams.PktPair.ProbePeriod = DEFAULT_PKT_PAIR_PROBE_PERIOD; 
    VA->MetricParams.PktPair.PenaltyFactor = DEFAULT_PKT_PAIR_PENALTY_FACTOR; 
}


//* PktPairSendProbeComplete
//
//  Called after sending a probe.  Cleans up after PktPairCreateProbePacket.
//
void
PktPairSendProbeComplete(
    MiniportAdapter *VA,
    NDIS_PACKET *Packet,
    NDIS_STATUS Status)
{
    SRPacket *srp = PC(Packet)->srp;

    UNREFERENCED_PARAMETER(VA);
    UNREFERENCED_PARAMETER(Status);

    NdisFreePacketClone(Packet);
    SRPacketFree(srp);
}

//* PktPairFreePadding
//
//  Helper function when probe is padded.
//
static void
PktPairFreePadding(
    ProtocolAdapter *PA,
    NDIS_PACKET *Packet)
{
    UNREFERENCED_PARAMETER(PA);
    NdisFreePacketClone(Packet);
}

//* PktPairCreateProbePacket
//
//  Creates a packet to send a probe.
//
NDIS_STATUS
PktPairCreateProbePacket(
    MiniportAdapter *VA,
    Link *Adjacent,
    Time Timestamp,
    NDIS_PACKET **ReturnPacket,
    uint Seq,
    boolint LargeProbe,
    MetricType ProbeType)
{
    SRPacket *srp;
    NDIS_PACKET *Packet;
    NDIS_PACKET *ProbePadding;
    void *PaddingData;
    NDIS_STATUS Status;
    
    InterlockedIncrement((PLONG)&VA->CountXmitProbe);

    //
    // Initialize an SRPacket for the Probe.
    // The Probe carries no data so it does not need an IV.
    //
    srp = ExAllocatePool(NonPagedPool, sizeof *srp);
    if (srp == NULL) {
        return NDIS_STATUS_RESOURCES;
    }
    RtlZeroMemory(srp, sizeof *srp);

    //
    // Initialize the Probe option. The probe carries
    // only generic variables, so no need to allocate
    // extra space. 
    //
    srp->Probe = ExAllocatePool(NonPagedPool, sizeof *srp->Probe);
    if (srp->Probe == NULL) {
        Status = NDIS_STATUS_RESOURCES;
        goto FreesrpAndExit;
    }
    RtlZeroMemory(srp->Probe, sizeof *srp->Probe);
    srp->Probe->Opt.OptionType = VRR_OPTION_TYPE_PROBE;
    srp->Probe->Opt.OptDataLen = PROBE_LEN;
    srp->Probe->Opt.MetricType = VA->MetricType;
    srp->Probe->Opt.ProbeType = METRIC_TYPE_PKTPAIR;
    srp->Probe->Opt.Seq = Seq;
    srp->Probe->Opt.Timestamp = Timestamp;
    RtlCopyMemory(srp->Probe->Opt.From, VA->Address, sizeof(VirtualAddress));

    {
        //
        // Obtain physical neighbor address from NCE containing Link Adjacent.
        //
        NeighborCacheEntry *NCE;
        
        NCE = CONTAINING_RECORD(Adjacent,NeighborCacheEntry,AdjOut);
        RtlCopyMemory(srp->Probe->Opt.To, NCE->VAddress, sizeof(VirtualAddress));
    }
    
    srp->Probe->Opt.OutIf = Adjacent->outif;
    srp->Probe->Opt.InIf = Adjacent->inif;
    srp->Probe->Opt.Metric = Adjacent->Metric;

    //
    // Create padding data based on whether LargeProbe is true or false.  
    // NB: MiniportMakeEmptyPacket is defined in headers.h.
    //
    if (LargeProbe) {
        Status = MiniportMakeEmptyPacket(VA, 
                                         PROBE_PADDING, 
                                         &ProbePadding, 
                                         &PaddingData);
        if (Status != NDIS_STATUS_SUCCESS) {
            goto FreesrpAndExit;
        }

        //
        // Note that all-zero padding ensures that we
        // will fail decryption at the receiver, since we
        // do not have correct ethertype. But this is okay,
        // since there are no piggybacked options. 
        //
        RtlZeroMemory(PaddingData, PROBE_PADDING);
    
        srp->Packet = ProbePadding;
        srp->PayloadOffset = 0;
        srp->FreePacket = PktPairFreePadding;
    }

    //
    // Initialize srp members used in VrrHeader construction.
    //
    RtlCopyMemory(srp->Dest, srp->Probe->Opt.To, sizeof(VirtualAddress));
    RtlCopyMemory(srp->Source, VA->Address, sizeof(VirtualAddress));
    RtlCopyMemory(srp->Origin, VA->Address, sizeof(VirtualAddress));
    srp->FrameSeqNo = InterlockedIncrement((unsigned long *)&VrrGlobal.NextFrameSeqNo);
    srp->HopCount = 0;


    //
    // Convert the SRPacket to an NDIS Packet. Again, note that we have
    // not called MsgLoadSRPfromPCache. This ensures that it is okay to 
    // fail decryption at the receiver. Furthermore, without piggybacked 
    // options, we have a better estimate of packet size.
    //
    Status = SRPacketToProbe(VA, srp, &Packet);
    if (Status != NDIS_STATUS_SUCCESS) {
        goto FreesrpAndExit;
    }

    PC(Packet)->srp = srp;
    PC(Packet)->TransmitComplete = PktPairSendProbeComplete;

    *ReturnPacket = Packet;
    return NDIS_STATUS_SUCCESS;

FreesrpAndExit:
    SRPacketFree(srp);
    return Status;
}



//* PktPairSendProbeReply
//
//  Send a probe reply. 
//
void
PktPairSendProbeReply(
        MiniportAdapter *VA, 
        InternalProbe *Probe, 
        Time Now, 
        Time OutDelta)
{
    SRPacket *srp;
    NDIS_PACKET *Packet;
    NDIS_STATUS Status;
    PRPktPair *Special; 

    UNREFERENCED_PARAMETER (Now); 

    srp = ExAllocatePool(NonPagedPool, sizeof *srp);
    if (srp == NULL)
        return;
    RtlZeroMemory(srp, sizeof *srp);

    //
    // Initialize the Probe Reply option.
    // Allocate extra space to hold packet-pair data.
    //
    srp->ProbeReply = ExAllocatePool(NonPagedPool, sizeof *srp->ProbeReply + sizeof(PRPktPair));
    if (srp->ProbeReply == NULL)
        goto FreesrpAndExit;

    RtlZeroMemory(srp->ProbeReply, sizeof *srp->ProbeReply + sizeof(PRPktPair));

    srp->ProbeReply->Opt.OptionType = VRR_OPTION_TYPE_PROBEREPLY;
    srp->ProbeReply->Opt.OptDataLen = PROBE_REPLY_LEN + sizeof(PRPktPair);
    srp->ProbeReply->Opt.MetricType = VA->MetricType; 
    srp->ProbeReply->Opt.ProbeType = METRIC_TYPE_PKTPAIR;
    srp->ProbeReply->Opt.Seq = Probe->Opt.Seq; 
    srp->ProbeReply->Opt.Timestamp = Probe->Opt.Timestamp; 
    RtlCopyMemory(srp->ProbeReply->Opt.From, VA->Address,
                  sizeof(VirtualAddress));
    RtlCopyMemory(srp->ProbeReply->Opt.To, Probe->Opt.From,
                  sizeof(VirtualAddress));
    srp->ProbeReply->Opt.OutIf = Probe->Opt.InIf;
    srp->ProbeReply->Opt.InIf = Probe->Opt.OutIf;

    //
    // Fill in packet-pair specific data. 
    //
    Special = (PRPktPair *)srp->ProbeReply->Opt.Special; 
    Special->OutDelta = OutDelta; 
    
    //
    // Initialize srp members used in VrrHeader construction.
    //
    RtlCopyMemory(srp->Dest, Probe->Opt.From, sizeof(VirtualAddress));
    RtlCopyMemory(srp->Source, VA->Address, sizeof(VirtualAddress));
    RtlCopyMemory(srp->Origin, VA->Address, sizeof(VirtualAddress));
    srp->FrameSeqNo = InterlockedIncrement((unsigned long *)&VrrGlobal.NextFrameSeqNo);
    srp->HopCount = 0;

    //
    // Convert the SRPacket to an NDIS Packet.
    //
    Status = SRPacketToProbe(VA, srp, &Packet);
    if (Status != NDIS_STATUS_SUCCESS)
        goto FreesrpAndExit;

    PC(Packet)->srp = srp;

    //
    // Reuse completion routine from PktPairSendProbe.
    //
    PC(Packet)->TransmitComplete = PktPairSendProbeComplete;

    if (PC(Packet)->PA == NULL) {
        //
        // This means the packet is trying to use a physical adapter that
        // no longer exists.  Just free the packet and bail.
        //
        PktPairSendProbeComplete(VA, Packet, NDIS_STATUS_FAILURE);

    } else {
        //
        // Transmit the packet.
        //
        ProtocolTransmit(PC(Packet)->PA, Packet);
    }
    return;

FreesrpAndExit:
    SRPacketFree(srp);
    return;
}