package jist.swans.rate;

/**
 * 5.2 Implementation
 * SampleRate is implemented in three functions: apply_rate(), which assigns a
 * bit-rate to a packet, process_feedback(), which updates the link statistics
 * based on the number of retries a packet used and whether the packet was
 * successfully acknowledged, and remove_stale_results(), which removes results
 * from the transmission results queue that were obtained longer than 10 sec
 * ago. remove_stale_results() and apply_rate() are called, in that order,
 * immediately before packet transmission and process_feedback() is called 
 * immediately after packet transmission.
 * SampleRate maintains data structures that keep track of the total 
 * transmission time, the number of successive failures, and the number of 
 * successful transmits for each bit-rate and destination as well as the total
 * number of packets sent across each link. It also keeps a queue of 
 * transmission results (transmission time, status, destination and bit-rate)
 * so it can adjust the average transmission time for each bit-rate and 
 * destination when transmission results become stale.
 * 
 * apply_rate() performs the following operations:
 * - If no packets have been successfully acknowledged, return the highest
 *   bit-rate that has not had 4 successive failures.
 * - Increment the number of packets sent over the link.
 * - If the number of packets sent over the link is a multiple of ten, select
 *   a random bit-rate from the bit-rates that have not failed four successive
 *   times and that have a minimum packet transmission time lower than the
 *   current bit-rate's average transmission time.
 * - Otherwise, send the packet at the bit-rate that has the lowest average
 *   transmission time.
 *   
 * When process_feedback() runs, it updates information that tracks the number
 * of samples and recalculates the average transmission time for the bit-rate
 * and destination. process_feedback() performs the following operations:
 * - Calculate the transmission time for the packet based on the bit-rate and
 *   number of retries using Equation 5.1 below.
 * - Look up the destination and add the transmission time to the total
 *   transmission times for the bit-rate.
 * - If the packet succeeded, increment the number of successful packets sent
 *   at that bit-rate.
 * - If the packet failed, increment the number of successive failures for the
 *   bit-rate. Otherwise reset it.
 * - Re-calculate the average transmission time for the bit-rate based on the
 *   sum of transmission times and the number of successful packets sent at
 *   that bit-rate.
 * - Set the current-bit rate for the destination to the one with the minimum
 *   average transmission time.
 * - Append the current time, packet status, transmission time, and bit-rate to
 *   the list of transmission results.
 *   
 * SampleRate's remove_stale_results() function removes results from the
 * transmission results queue that were obtained longer than ten seconds ago.
 * For each stale transmission result, it does the following:
 * - Remove the transmission time from the total transmission times at that
 *   bit-rate to that destination.
 * - If the packet succeeded, decrement the number of successful packets at
 *   that bit-rate to that destination.
 * 
 * After remove_stale_results() performs these operations for each stale
 * sample, it recalculates the minimum average transmission times for each
 * bit-rate and destination. remove_stale_results() then sets the current
 * bit-rate for each destination to the one with the smallest average trans-
 * mission time.
 * # Oliver, comment on remove_stale_results():
 * # This functionality is not implemented in this version, as it is neither
 * # in the Atheros Madwifi driver. A behaviour in the direction of ignoring
 * # stale failures is found in "pickSampleIdx" where it says "rarely sample
 * # bit-rates that fail a lot".
 * 
 * To calculate the transmission time of a n-byte unicast packet given the
 * bit-rate b and number of retries r, SampleRate uses the following equation
 * based on the 802.11 unicast retransmission mechanism (see Section 2.2):
 * 
 * tx time(b; r; n)
 *   = difs + backoff(r) + (r + 1) * (sifs + ack + header + (n * 8=b) (5.1)
 * 
 * where difs is 50 microseconds in 802.11b and 28 microseconds in 802.11a/g,
 * sifs is 10 microseconds for 802.11b and 9 for 802.11a/g, and ack is
 * 304 microseconds using 1 megabit acknowledgments for 802.11b and
 * 200 microseconds for 6 megabit acknowledgments. header is 192 microseconds
 * for 1 megabit 802.11b packets, 96 for other 802.11b bit-rates, and 20 for
 * 802.11a/g bit-rates. backoff(r) is calculated using the table in Figure 2-2.
 * 
 * 		Attempt | Average Backoff (Bicket) | Avg. Backoff used here
 *      --------+--------------------------+-----------------------
 * 			1   |		155                |		310
 *  		2   |		315                |		630
 *  		3   |		635                |		1270
 *  		4   |		1275               |		2550
 *  		5   |		2555               |		5110
 *  		6   |		5115               |		10230
 *  		7   |		5115               |		10230
 *  		8   |		5115               |		10230
 *  
 * COMMENTS: The backoff values are not reproducable. For a slot time of 20 us
 *           in 802.11b and a minimal collision window (CW) of 31, the average
 *           backoff would be:
 *           	SLOTTIME * CW / 2 = 20 us * 31 / 2 = 310 us                (1)
 *           not 155 us. It looks like - for some unknown reason - John Bicket
 *           used 10 us as slot time; that would explain the values in the
 *           table above. I used the values based on the given calculation (1).
 */

import java.util.Enumeration;
import java.util.Hashtable;

import jist.runtime.JistAPI;
import jist.runtime.Main;
import jist.swans.Constants;
import jist.swans.mac.MacAddress;
import jist.swans.mac.MacDcfMessage;
import jist.swans.mac.MacInfo;
import jist.swans.mac.MacMessageFactory;
import jist.swans.mac.MacTimes;
import jist.swans.misc.Message;
import jist.swans.misc.MessageAnno;
import jist.swans.misc.Util;

import org.apache.log4j.Logger;

/**
 * This is an implementation of John Bicket's SampleRate algorithm.
 * 
 * @author Oliver
 */
public final class SampleRate extends AbstractRca implements
		RateControlAlgorithmIF {

	/** SampleRate logger. */
	public static final Logger log = Logger.getLogger(SampleRate.class);

	// log this only once for all instances
	static {
		if (log.isDebugEnabled())
			log.debug("Debug format for SampleRateState output:\n"
					+ SampleRateState.logFormat());
	}

	/** Message factory instance needed for transmission time calculations */
	MacMessageFactory mmf = new MacMessageFactory.M802_11();

	// /////////////////////////////////////////
	// local constants
	//

	/** Ignore packets that are older than this */
	private static final long STALE_FAILURE_TIMEOUT = 10 * Constants.SECOND;

	/** Minimum interval for rate switching. */
	private static final long MIN_SWITCH_TIME = 1 * Constants.SECOND;

	/** Exponentially weighted moving average (ewma) percentage */
	private static final int SMOOTHING_RATE = 95;

	/** Percentage of tx time that should be used for sampling */
	private static final int SAMPLE_RATE = 10;

	/** Different packet size buckets to distinguish */
	private static final int[] PACKET_SIZE_BINS;

	/** Count of different packet size buckets (at the moment: 3) */
	private static final int PACKET_SIZE_COUNT;

	static {
		PACKET_SIZE_BINS = new int[] { 250, 1600, 3000 };
		PACKET_SIZE_COUNT = PACKET_SIZE_BINS.length;
	}

	// /////////////////////////////////////////
	// local variables
	//

	/** Number of analyzed/managed rates. */
	private int numRates;

	/** Mapping of index to bitrate. */
	private int bitrates[];

	private int staticRateIdx = -1;

	/** Mapping of destinations to their respective SampleRate states */
	protected Hashtable m_macToState = new Hashtable();

	/** List of bit-rates to try for packet transmission */
	private class MultiRateRetryChain {
		int rateIdx0;

		int tries0;

		int rateIdx1;

		int tries1;

		int rateIdx2;

		int tries2;

		int rateIdx3;

		int tries3;

		public MultiRateRetryChain() {
			reset();
		}

		public void reset() {
			rateIdx0 = rateIdx1 = rateIdx2 = rateIdx3 = -1;
			tries0 = tries1 = tries2 = tries3 = 0;
		}

		public String toString() {
			StringBuffer sb = new StringBuffer("index|tries - ");
			sb.append(rateIdx0).append('|').append(tries0).append(' ').append(
					rateIdx1).append('|').append(tries1).append(' ').append(rateIdx2)
					.append('|').append(tries2).append(' ').append(rateIdx3).append('|')
					.append(tries3);
			return sb.toString();
		}
	}

	private MultiRateRetryChain mrrc;

	// /////////////////////////////////////////
	// Constructor
	//

	/**
	 * 
	 */
	public SampleRate(MacInfo macInfo) {
		super(macInfo);
		this.bitrates = macInfo.getBitrateSet();
		this.numRates = bitrates.length;
		mrrc = new MultiRateRetryChain();
	}

	/**
	 * Returns an SampleRateState object for the given MAC address.
	 * SampleRateState objects are created as they are needed.
	 * 
	 * @param address The MAC address for which to retrieve the current state of
	 *          the SampleRate algorithm
	 * @return the state of the SampleRate algorithm for the given MAC address.
	 */
	protected SampleRateState getSampleRateState(MacAddress address) {
		SampleRateState st = (SampleRateState) m_macToState.get(address);
		if (st == null) {
			if (s_macRateInfo.getMacInfo(address) == null)
				throw new RuntimeException("Why don't I have a MacInfo for " + address
						+ "?");
			if (s_macRateInfo.getBitrates(address) == null
					|| s_macRateInfo.getBasicRates(address) == null)
				throw new RuntimeException("Why don't I know any bit-rates for "
						+ address + "?");

			st = new SampleRateState(m_macInfo, PACKET_SIZE_BINS, bitrates);
			m_macToState.put(address, st);
		}
		return st;
	}

	// /////////////////////////////////////////
	// Convenience methods
	//
	private static int sizeToBin(int size) {
		for (int i = 0; i < PACKET_SIZE_COUNT; i++)
			if (size <= PACKET_SIZE_BINS[i])
				return i;
		// default: the middle bin
		return PACKET_SIZE_COUNT / 2;
	}

	private static int binToSize(int index) {
		// default: if given index out of range, use the middle index
		if (index >= PACKET_SIZE_COUNT)
			index = PACKET_SIZE_COUNT / 2;
		return PACKET_SIZE_BINS[index];
	}

	/**
	 * @param sizeBin Index of the size bin for which to find the best rate (idx)
	 * @param requireAckBefore Whether or not a packet must have been successfully
	 *          transmitted at the returned rate (sometime in the past)
	 * @return The bit-rate (idx) with the lowest avg tx time, or -1 if all avg
	 *         times are (still) 0.
	 */
	private int bestRateIdx(SampleRateState st, int sizeBin,
			boolean requireAckBefore) {

		long bestRateTxTime = 0;
		int bestRateIdx = -1;

		for (int i = 0; i < numRates; i++) {

			long transmitTime = st.stats[sizeBin][i].avgTxTime;

			if (transmitTime <= 0
					|| (requireAckBefore && (st.stats[sizeBin][i].packetsAcked <= 0)))
				continue;

			/* 9 megabits never works better than 12 */
			if (bitrates[i] == Constants.BANDWIDTH_9Mbps)
				continue;

			/* don't use a bit-rate that has been failing */
			if (st.stats[sizeBin][i].successiveFailures > 3)
				continue;

			if (bestRateTxTime == 0 || bestRateTxTime > transmitTime) {
				bestRateTxTime = transmitTime;
				bestRateIdx = i;
			}
		} // for

		return bestRateIdx;
	}

	/**
	 * @param sizeBin Index of the size bin for which to find the best rate (idx)
	 * @return The bit-rate (idx) to sample next.
	 */
	private int pickSampleIdx(SampleRateState st, int sizeBin) {

		long currentTxTime;
		int currentIdx = st.currentRateIdx[sizeBin];

		if (currentIdx < 0) {
			/* no successes yet, send at the lowest bit-rate */
			return 0;
		}

		currentTxTime = st.stats[sizeBin][currentIdx].avgTxTime;

		for (int x = 0; x < numRates; x++) {

			int ndx = (st.lastSampleRateIdx[sizeBin] + 1 + x) % numRates;

			/* don't sample the current bit-rate */
			if (ndx == currentIdx)
				continue;

			/* this bit-rate is always worse than the current one */
			if (st.stats[sizeBin][ndx].perfectTxTime > currentTxTime)
				continue;

			/* rarely sample bit-rates that fail a lot */
			if ((JistAPI.getTime() - st.stats[sizeBin][ndx].lastTx < STALE_FAILURE_TIMEOUT)
					&& (st.stats[sizeBin][ndx].successiveFailures > 3))
				continue;

			/*
			 * don't sample more than 2 indexes higher for rates higher than 11
			 * megabits
			 */
			if (bitrates[ndx] > Constants.BANDWIDTH_11Mbps && ndx > currentIdx + 2)
				continue;

			/* 9 megabits never works better than 12 */
			// TODO: leave this? What do our experiments say?
			if (bitrates[ndx] == Constants.BANDWIDTH_9Mbps)
				continue;

			/*
			 * if we're using 11 megabits, only sample up to 12 megabits
			 */
			if (bitrates[currentIdx] == Constants.BANDWIDTH_11Mbps
					&& ndx > currentIdx + 1)
				continue;

			st.lastSampleRateIdx[sizeBin] = ndx;
			return ndx;
		}
		return currentIdx;
	}

	// /////////////////////////////////////////
	// RateSelectionInterface implementations
	//

	/*
	 * (non-Javadoc)
	 * 
	 * @see jist.swans.rate.RateSelectionInterface#getNextDataRate(jist.swans.mac.MacAddress)
	 *      This corresponds to ath_rate_findrate() in sample.c of the MADwifi
	 *      driver.
	 */
	public int getNextDataRate(Message packet, MessageAnno anno, Object dest,
			int frameLen, int triesBefore) {

		// Send broadcast packets at control rate
		// See 802.11-1999.pdf, 9.6 Multirate support
		if (dest == MacAddress.ANY)
			return getControlRate((MacAddress) dest, m_macInfo.getBasicRateSet()[0]);

		// Tx rates have already been calculated for this packet
		if (triesBefore > 0) {
			if (Main.ASSERT)
				Util.assertion(mrrc.rateIdx0 > -1);
			if (triesBefore < mrrc.tries0) {
				return bitrates[mrrc.rateIdx0];
			}
			if (triesBefore < mrrc.tries0 + mrrc.tries1) {
				if (Main.ASSERT)
					Util.assertion(mrrc.rateIdx1 > -1);
				return bitrates[mrrc.rateIdx1];
			}
			if (triesBefore < mrrc.tries0 + mrrc.tries1 + mrrc.tries2) {
				if (Main.ASSERT)
					Util.assertion(mrrc.rateIdx2 > -1);
				return bitrates[mrrc.rateIdx2];
			}
			if (triesBefore < mrrc.tries0 + mrrc.tries1 + mrrc.tries2 + mrrc.tries3) {
				if (Main.ASSERT)
					Util.assertion(mrrc.rateIdx3 > -1);
				return bitrates[mrrc.rateIdx3];
			}
			throw new RuntimeException("Packet retransmission, but no tx rate "
					+ "given for retry " + triesBefore + "!");
		}

		// Get the algorithm state for the receiver of this packet
		SampleRateState st = getSampleRateState((MacAddress) dest);

		// Do some debug logging for non-ACK frames
		if (SampleRateState.log.isDebugEnabled()
				&& (frameLen != MacDcfMessage.Ack.getHeaderSize()))
			SampleRateState.log.debug(this.toString((MacAddress) dest));

		boolean mrrOn = true;
		boolean changeRates = false;
		int sizeBin = sizeToBin(frameLen);
		int ndx = -1;
		int bestIdx = bestRateIdx(st, sizeBin, !mrrOn);
		long averageTxTime = 0;

		if (bestIdx >= 0)
			averageTxTime = st.stats[sizeBin][bestIdx].avgTxTime;

		if (staticRateIdx != -1) {
			ndx = staticRateIdx;
		} else {

			if (st.sampleTxTime[sizeBin] < (averageTxTime * (st.packetsSinceSample[sizeBin]
					* SAMPLE_RATE / 100))) {
				/*
				 * we want to limit the time for measuring the performance of other
				 * bit-bitrates to SAMPLE_RATE% of the total transmission time
				 */
				ndx = pickSampleIdx(st, sizeBin);
				if (ndx != st.currentRateIdx[sizeBin])
					st.currentSampleIdx[sizeBin] = ndx;
				else
					st.currentSampleIdx[sizeBin] = -1;

				if (log.isDebugEnabled() && st.currentSampleIdx[sizeBin] != -1)
					log.debug("[" + Util.getTimeDotted() + "] SAMPLING at "
							+ bitrates[st.currentSampleIdx[sizeBin]]);

				st.packetsSinceSample[sizeBin] = 0;

			} else {
				if (st.packetsSent[sizeBin] == 0 || bestIdx == -1) {
					/*
					 * no packet has been sent successfully yet, so pick an
					 * rssi-appropriate bit-rate. We know if the rssi is very low that the
					 * really high bit bitrates will not work.
					 */
					// int initial_rate = Constants.BANDWIDTH_11Mbps;
					int initial_rate = m_macInfo.getBitrateSet()[m_macInfo
							.getBitrateSet().length - 1]; // Constants.BANDWIDTH_54Mbps;

					// No means of accessing an RSSI value at the time.
					// Where from anyways? It's a receiver based value...
					// if (an->an_avgrssi > 50) {
					// initial_rate = 108; /* 54 mbps */
					// } else if (an->an_avgrssi > 30) {
					// initial_rate = 72; /* 36 mbps */
					// } else {
					// initial_rate = 22; /* 11 mbps */
					// }

					for (ndx = numRates - 1; ndx > 0; ndx--) {
						/*
						 * pick the highest rate <= initial_rate that hasn't failed.
						 */
						if (bitrates[ndx] <= initial_rate
								&& st.stats[sizeBin][ndx].successiveFailures == 0)
							break;
					}
					changeRates = true;
					bestIdx = ndx;
				} else if (st.packetsSent[sizeBin] < 20) {
					/*
					 * let the bit-rate switch quickly during the first few packets
					 */
					changeRates = true;
				} else if (JistAPI.getTime() - MIN_SWITCH_TIME > st.timeSinceSwitch[sizeBin]) {
					/* if rate has not been changed for a while, change now */
					changeRates = true;
				} else if (averageTxTime * 2 < st.stats[sizeBin][st.currentRateIdx[sizeBin]].avgTxTime) {
					/* the current bit-rate is twice as slow as the best one */
					changeRates = true;
				}

				st.packetsSinceSample[sizeBin]++;

				if (changeRates) {
					st.packetsSinceSwitch[sizeBin] = 0;
					st.currentRateIdx[sizeBin] = bestIdx;
					st.timeSinceSwitch[sizeBin] = JistAPI.getTime();
				}
				ndx = st.currentRateIdx[sizeBin];
				st.packetsSinceSwitch[sizeBin]++;
			}
		}

		// if (log.isDebugEnabled())
		// log.debug("ndx:" + ndx);
		if (Main.ASSERT)
			Util.assertion(ndx >= 0 && ndx < numRates);

		// next packet is being sent
		st.packetsSent[sizeBin]++;

		/*
		 * set the multi rate retry object This behaviour is copied from the madwifi
		 * implementation of the SampleRate algorithm. See ath_find_rate() and
		 * ath_rate_get_mrr() in /trunk/ath_rate/sample/sample.c.
		 */
		mrrc.rateIdx0 = ndx;
		if (mrrOn) {
			mrrc.tries0 = 2;
			mrrc.rateIdx1 = ndx > 0 ? ndx - 1 : 0; // if ndx == 0, do not decrease
			mrrc.tries1 = 3;
			mrrc.rateIdx2 = 0; // lowest bit-rate as fallback
			mrrc.tries2 = 3;
			mrrc.rateIdx3 = -1;
			mrrc.tries3 = 0;
		} else {
			mrrc.tries0 = (frameLen > m_macInfo.getThresholdRts()) ? m_macInfo
					.getRetryLimitLong() : m_macInfo.getRetryLimitShort();
			mrrc.rateIdx1 = -1;
			mrrc.tries1 = 0;
			mrrc.rateIdx2 = -1;
			mrrc.tries2 = 0;
			mrrc.rateIdx3 = -1;
			mrrc.tries3 = 0;
		}

		if (log.isDebugEnabled())
			log.debug("[" + Util.getTimeDotted() + "] (getDataRate) Mrrc: " + mrrc);

		// short preambe is handled in PHY layer
		return bitrates[ndx];
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see jist.swans.rate.RateSelectionInterface#getNextBasicRate(jist.swans.mac.MacAddress)
	 *      TODO Replace this method by one w/o a dataRate param
	 */
	public int getControlRate(MacAddress dest, int dataRate) {
		// return getControlRate(getSampleRateState(dest), dest, dataRate);
		// Looks like at least in madwifi the control rate is never changed.
		// They just use the lowest one to make sure, packets arrive.
		// return m_macInfo.getHighestBasicRate(dataRate);
		// if (dest == null) {
		// return m_macInfo.getBasicRateSet()[0];
		// }
		// return s_macRateInfo.getBasicRates(dest)[0];
		if (m_lastDataRate > 0)
			return getBasicRateFromDataRate(m_lastDataRate);
		// TODO Delete this code
		return getBasicRateFromDataRate(dataRate);
	}

	/**
	 * @param dataRate
	 * @return The lowest bit-rate in the OFDM basic rate set if dataRate is an
	 *         OFDM bit-rate, otherwise the lowest bit-rate in the DSSS rate set.
	 */
	private int getBasicRateFromDataRate(int dataRate) {
		if (Util.isInArray(Constants.BITRATES_OFDM, dataRate) > -1)
			return Constants.BASIC_RATES_80211AG[0];
		return Constants.BASIC_RATES_80211B[0];
	}

	// private int getControlRate(SampleRateState st, MacAddress ma, int
	// dataRate) {
	// if (Util.isInArray(bitrates, dataRate) == -1)
	// return bitrates[0];
	// // return bitrates[st.currentRateIdx[0]];
	// // XXX: quick hack
	// return m_macInfo.getHighestBasicRate(dataRate);
	// }

	/*
	 * (non-Javadoc)
	 * 
	 * @see jist.swans.rate.RateControlAlgorithmIF#reportPacketTx(jist.swans.mac.MacAddress,
	 *      int, int, int, int, int, int)
	 */
	public void reportPacketTx(MacAddress nextHop, int type, int size,
			int bitrate, int shortTries, int longTries, int status) {

		// Sanity checks
		if (Main.ASSERT) {
			Util.assertion((shortTries >= 0) && (longTries >= 0));
			Util.assertion((shortTries > 0) || (longTries > 0));
			Util.assertion((size > m_macInfo.getThresholdRts()) || (longTries == 0)
					&& (shortTries > 0));
		}

		/* Only transmission of unicast DATA packets is examined */
		if (type == MacDcfMessage.TYPE_DATA) {
			SampleRateState st = getSampleRateState(nextHop);

			int binIdx = sizeToBin(size);
			size = binToSize(binIdx);

			// Check if mrrc object is set; if not, then report is for a packet,
			// the bit-rate of which was not set by this algo (e.g. w/ AnnoRate)
			if (mrrc.rateIdx0 >= 0 && mrrc.tries0 > 0) {
				
				boolean rtsCtsUsed = size > m_macInfo.getThresholdRts();
				int dataTries = rtsCtsUsed ? longTries : shortTries;
				
				// The effectively used sequence of transmission bit-rates
				// deduced from the initial mrrc and the final txTry count
				MultiRateRetryChain mrrEffective = new MultiRateRetryChain();
				int tryCtr = dataTries;

				if (log.isDebugEnabled())
					log.debug("[" + Util.getTimeDotted() + "] (reportPktTx) Mrrc: "
							+ mrrc);
				
				// if (log.isDebugEnabled()) log.debug("Try counter = " + tryCtr);
				mrrEffective.rateIdx0 = mrrc.rateIdx0;
				mrrEffective.tries0 = Math.min(mrrc.tries0, tryCtr);
				tryCtr -= mrrEffective.tries0;
				// if (log.isDebugEnabled()) log.debug("Try counter = " + tryCtr);
				if (tryCtr > 0) {
					mrrEffective.rateIdx1 = mrrc.rateIdx1;
					mrrEffective.tries1 = Math.min(mrrc.tries1, tryCtr);
					tryCtr -= mrrEffective.tries1;
					// if (log.isDebugEnabled()) log.debug("Try counter = " + tryCtr);
				}
				if (tryCtr > 0) {
					mrrEffective.rateIdx2 = mrrc.rateIdx2;
					mrrEffective.tries2 = Math.min(mrrc.tries2, tryCtr);
					tryCtr -= mrrEffective.tries2;
					// if (log.isDebugEnabled()) log.debug("Try counter = " + tryCtr);
				}
				if (tryCtr > 0) {
					mrrEffective.rateIdx3 = mrrc.rateIdx3;
					mrrEffective.tries3 = Math.min(mrrc.tries3, tryCtr);
					tryCtr -= mrrEffective.tries3;
					// if (log.isDebugEnabled()) log.debug("Try counter = " + tryCtr);
				}
				if (Main.ASSERT)
					Util.assertion(tryCtr == 0);
				if (Main.ASSERT)
					Util.assertion(bitrate == bitrates[mrrEffective.rateIdx0]
							|| bitrate == bitrates[mrrEffective.rateIdx1]
							|| bitrate == bitrates[mrrEffective.rateIdx2]
							|| bitrate == bitrates[mrrEffective.rateIdx3]);
				// if (log.isDebugEnabled())
				// log.debug("MRR tx: " + mrrEffective);
			
			  /*
				 * Comment from sample.c: ************************************* NB:
				 * series > 0 are not penalized for failure based on the try counts
				 * under the assumption that losses are often bursty and since we sample
				 * higher rates 1 try at a time doing so may unfairly penalize them.
				 * ************************************ --> pass negative status only
				 * with the highest bit-rate if it failed
				 */
				MultiRateRetryChain mrry = null;
				if ((mrrEffective.tries0 > 0) && (mrrEffective.rateIdx0 >= 0)) {
					mrry = mrrEffective;
					updateStats(
							st,
							mrry,
							size,
							shortTries,
							longTries,
							dataTries > mrrEffective.tries0 ? Constants.RADIO_RECV_STATUS_LOST
									.byteValue()
									: Constants.RADIO_RECV_STATUS_OK.byteValue());
					if (rtsCtsUsed)
						longTries -= mrry.tries0;
					else
						shortTries -= mrry.tries0;
				}
				if (((shortTries > 0) || (longTries > 0)) && (mrrEffective.tries1 > 0)
						&& (mrrEffective.rateIdx1 >= 0)) {
					mrry = new MultiRateRetryChain();
					mrry.rateIdx0 = mrrEffective.rateIdx1;
					mrry.tries0 = mrrEffective.tries1;
					mrry.rateIdx1 = mrrEffective.rateIdx2;
					mrry.tries1 = mrrEffective.tries2;
					mrry.rateIdx2 = mrrEffective.rateIdx3;
					mrry.tries2 = mrrEffective.tries3;
					updateStats(st, mrry, size, shortTries, longTries, status);
					if (rtsCtsUsed)
						longTries -= mrry.tries0;
					else
						shortTries -= mrry.tries0;
				}
				if (((shortTries > 0) || (longTries > 0)) && (mrrEffective.tries2 > 0)
						&& (mrrEffective.rateIdx2 >= 0)) {
					mrry.reset();
					mrry.rateIdx0 = mrrEffective.rateIdx2;
					mrry.tries0 = mrrEffective.tries2;
					mrry.rateIdx1 = mrrEffective.rateIdx3;
					mrry.tries1 = mrrEffective.tries3;
					updateStats(st, mrry, size, shortTries, longTries, status);
					if (rtsCtsUsed)
						longTries -= mrry.tries0;
					else
						shortTries -= mrry.tries0;
				}
				if (((shortTries > 0) || (longTries > 0)) && (mrrEffective.tries3 > 0)
						&& (mrrEffective.rateIdx3 >= 0)) {
					mrry.reset();
					mrry.rateIdx0 = mrrEffective.rateIdx3;
					mrry.tries1 = mrrEffective.tries3;
					updateStats(st, mrry, size, shortTries, longTries, status);
				}
			} else {
				/* mrrc is "empty", i.e. was not set before this report
				 * Two choices: use this feedback for statistics, or don't.
				 * Here we use it with whatever info we have: assume that packet
				 * was tried to be sent at the same bitrate for <tries> times.
				 */
				int ndx = Util.isInArray(bitrates, bitrate);
				if ((ndx >= 0) && (ndx < numRates)) {
					MultiRateRetryChain mrry = null;
					mrry = new MultiRateRetryChain();
					mrry.rateIdx0 = ndx;
					mrry.tries0 = longTries > 0 ? longTries : shortTries;
					updateStats(st, mrry, size, shortTries, longTries, status);
				}
			}
		}
	}

	private void updateStats(SampleRateState st, final MultiRateRetryChain mrr,
			int size, int shortTries, int longTries, int status) {

		// if (log.isDebugEnabled()) {
		// log.debug("updateStats: size:" + size + " shTry:" + shortTries
		// + " lgTry:" + longTries + " status:" + status);
		// }

		int binIdx = sizeToBin(size);
		size = binToSize(binIdx);

		int rateIdx = mrr.rateIdx0;
		boolean useRtsCts = size > m_macInfo.getThresholdRts();
		int rtsTries = useRtsCts ? shortTries : 0;
		int dataTries = useRtsCts ? longTries : shortTries;
		int boCtr;

		if (Main.ASSERT)
			Util.assertion((rtsTries == 0) || (rtsTries >= dataTries));

		// If rtsTries > dataTries, assume that those extra attempts happened
		// before trying to transmit at the first bit-rate in the mrrc
		int rtsTries0 = rtsTries > dataTries ? rtsTries - dataTries + mrr.tries0
				: rtsTries;
		long transmitTime = MacTimes.avgTransmitTimeUnicastPacket(m_macInfo, size,
				bitrates[mrr.rateIdx0],
				getBasicRateFromDataRate(bitrates[mrr.rateIdx0]), useRtsCts, false,
				rtsTries0, mrr.tries0, false);
		MacTimes mt = new MacTimes(m_macInfo);
		for (boCtr = 0; boCtr < mrr.tries0; boCtr++)
			transmitTime += mt.calcAvgBackoff(bitrates[mrr.rateIdx0], boCtr);
		rtsTries -= rtsTries0;
		dataTries -= mrr.tries0;

		if ((dataTries > 0) && (mrr.tries1 > 0)) {
			transmitTime += MacTimes.avgTransmitTimeUnicastPacket(m_macInfo, size,
					bitrates[mrr.rateIdx1],
					getBasicRateFromDataRate(bitrates[mrr.rateIdx1]), useRtsCts, false,
					Math.min(rtsTries, mrr.tries1), mrr.tries1, false);
			for (; boCtr < mrr.tries0 + mrr.tries1; boCtr++)
				transmitTime += mt.calcAvgBackoff(bitrates[mrr.rateIdx1], boCtr);
			rtsTries -= Math.min(0, mrr.tries1);
			dataTries -= mrr.tries1;
		}

		if ((dataTries > 0) && (mrr.tries2 > 0)) {
			transmitTime += MacTimes.avgTransmitTimeUnicastPacket(m_macInfo, size,
					bitrates[mrr.rateIdx2],
					getBasicRateFromDataRate(bitrates[mrr.rateIdx2]), useRtsCts, false,
					Math.min(rtsTries, mrr.tries2), mrr.tries2, false);
			for (; boCtr < mrr.tries0 + mrr.tries1 + mrr.tries2; boCtr++)
				transmitTime += mt.calcAvgBackoff(bitrates[mrr.rateIdx2], boCtr);
			rtsTries -= Math.min(0, mrr.tries2);
			dataTries -= mrr.tries2;
		}

		if ((dataTries > 0) && (mrr.tries3 > 0)) {
			transmitTime += MacTimes.avgTransmitTimeUnicastPacket(m_macInfo, size,
					bitrates[mrr.rateIdx3],
					getBasicRateFromDataRate(bitrates[mrr.rateIdx3]), useRtsCts, false,
					Math.min(rtsTries, mrr.tries3), mrr.tries3, false);
			for (; boCtr < mrr.tries0 + mrr.tries1 + mrr.tries2 + mrr.tries3; boCtr++)
				transmitTime += mt.calcAvgBackoff(bitrates[mrr.rateIdx3], boCtr);
			rtsTries -= Math.min(0, mrr.tries3);
			dataTries -= mrr.tries3;
		}

		// reset
		dataTries = useRtsCts ? longTries : shortTries;

		if (st.stats[binIdx][rateIdx].totalPackets < (100 / (100 - SMOOTHING_RATE))) {
			/* just average the first few packets */
			long avg_tx = st.stats[binIdx][rateIdx].avgTxTime;
			int packets = st.stats[binIdx][rateIdx].totalPackets;
			st.stats[binIdx][rateIdx].avgTxTime = (transmitTime + (avg_tx * packets))
					/ (packets + 1);
		} else {
			/* use an ewma (exponentially weighted moving average) */
			st.stats[binIdx][rateIdx].avgTxTime = ((st.stats[binIdx][rateIdx].avgTxTime * SMOOTHING_RATE) + (transmitTime * (100 - SMOOTHING_RATE))) / 100;
		}

		if (status != Constants.RADIO_RECV_STATUS_OK.byteValue()) {
			st.stats[binIdx][rateIdx].successiveFailures++;
			for (int y = binIdx + 1; y < PACKET_SIZE_COUNT; y++) {
				/*
				 * also say larger packets failed since we assume if a small packet
				 * fails at a lower bit-rate then a larger one will also.
				 */
				st.stats[y][rateIdx].successiveFailures++;
				st.stats[y][rateIdx].lastTx = JistAPI.getTime();
				st.stats[y][rateIdx].tries += dataTries;
				st.stats[y][rateIdx].totalPackets++;
			}
		} else {
			st.stats[binIdx][rateIdx].packetsAcked++;
			st.stats[binIdx][rateIdx].successiveFailures = 0;
		}
		st.stats[binIdx][rateIdx].tries += dataTries;
		st.stats[binIdx][rateIdx].lastTx = JistAPI.getTime();
		st.stats[binIdx][rateIdx].totalPackets++;

		if (rateIdx == st.currentSampleIdx[binIdx]) {
			st.sampleTxTime[binIdx] = transmitTime;
			st.currentSampleIdx[binIdx] = -1;
		}
	}

	public String toString() {
		StringBuffer sb = new StringBuffer();
		// sb.append(super.hashCode()).append(": ");
		Enumeration e = m_macToState.keys();
		while (e.hasMoreElements()) {
			Object ma = e.nextElement();
			sb.append("dest ").append(ma).append(" :").append(m_macToState.get(ma));
		}
		return sb.toString();
	}

	public String toString(MacAddress ma) {
		StringBuffer sb = new StringBuffer();
		sb.append("SampleRateState for ").append(ma).append(" :").append(
				m_macToState.get(ma));
		return sb.toString();
	}
}
