RakNet::CCRakNetUDT Class Reference

Encapsulates UDT congestion control, as used by RakNet Requirements:. More...

#include <CCRakNetUDT.h>

List of all members.

Public Member Functions

void Init (CCTimeType curTime, uint32_t maxDatagramPayload)
 Reset all variables to their initial states, for a new connection.
void Update (CCTimeType curTime, bool hasDataToSendOrResend)
 Update over time.
bool ShouldSendACKs (CCTimeType curTime, CCTimeType estimatedTimeToNextTick)
DatagramSequenceNumberType GetNextDatagramSequenceNumber (void)
void OnSendBytes (CCTimeType curTime, uint32_t numBytes)
void OnGotPacketPair (DatagramSequenceNumberType datagramSequenceNumber, uint32_t sizeInBytes, CCTimeType curTime)
 Call this when you get a packet pair.
bool OnGotPacket (DatagramSequenceNumberType datagramSequenceNumber, bool isContinuousSend, CCTimeType curTime, uint32_t sizeInBytes, uint32_t *skippedMessageCount)
void OnResend (CCTimeType curTime)
void OnAck (CCTimeType curTime, CCTimeType rtt, bool hasBAndAS, BytesPerMicrosecond _B, BytesPerMicrosecond _AS, double totalUserDataBytesAcked, bool isContinuousSend, DatagramSequenceNumberType sequenceNumber)
void OnSendAckGetBAndAS (CCTimeType curTime, bool *hasBAndAS, BytesPerMicrosecond *_B, BytesPerMicrosecond *_AS)
void OnSendAck (CCTimeType curTime, uint32_t numBytes)
void OnSendNACK (CCTimeType curTime, uint32_t numBytes)
CCTimeType GetRTOForRetransmission (void) const
void SetMTU (uint32_t bytes)
uint32_t GetMTU (void) const
 Return what was set by SetMTU().
BytesPerMicrosecond GetLocalSendRate (void) const
 Query for statistics.
double GetRTT (void) const
 Query for statistics.

Static Public Member Functions

static bool GreaterThan (DatagramSequenceNumberType a, DatagramSequenceNumberType b)
 Is a > b, accounting for variable overflow?
static bool LessThan (DatagramSequenceNumberType a, DatagramSequenceNumberType b)
 Is a < b, accounting for variable overflow?

Protected Member Functions

void SetNextSYNUpdate (CCTimeType currentTime)
 Update nextSYNUpdate by SYN, or the same amount past the current time if no updates have occurred for a long time.
BytesPerMicrosecond ReceiverCalculateDataArrivalRate (CCTimeType curTime) const
 Returns the rate of data arrival, based on packets arriving on the sender.
BytesPerMicrosecond ReceiverCalculateDataArrivalRateMedian (void) const
 Returns the median of the data arrival rate.
CCTimeType GetSenderRTOForACK (void) const
void EndSlowStart (void)
 Stop slow start, and enter normal transfer rate.
double BytesPerMicrosecondToPacketsPerMillisecond (BytesPerMicrosecond in)
 Does the named conversion.
void UpdateWindowSizeAndAckOnAckPreSlowStart (double totalUserDataBytesAcked)
 Update the round trip time, from ACK or ACK2.
void UpdateWindowSizeAndAckOnAckPerSyn (CCTimeType curTime, CCTimeType rtt, bool isContinuousSend, DatagramSequenceNumberType sequenceNumber)
 Update the corresponding variables post-slow start.
void ResetOnDataArrivalHalveSNDOnNoDataTime (CCTimeType curTime)
 Sets halveSNDOnNoDataTime to the future, and also resets ExpCount, which is used to multiple the RTO on no data arriving at all.

Static Protected Member Functions

static BytesPerMicrosecond CalculateListMedianRecursive (const BytesPerMicrosecond inputList[CC_RAKNET_UDT_PACKET_HISTORY_LENGTH], int inputListLength, int lessThanSum, int greaterThanSum)
 Calculates the median an array of BytesPerMicrosecond.

Protected Attributes

MicrosecondsPerByte SND
double CWND
CCTimeType nextSYNUpdate
int packetPairRecieptHistoryWriteIndex
double RTT
double minRTT
 Update: Use min/max, RTTVar follows current variance too closely resulting in packetloss.
BytesPerMicrosecond packetArrivalHistory [CC_RAKNET_UDT_PACKET_HISTORY_LENGTH]
int packetArrivalHistoryWriteIndex
CCTimeType lastPacketArrivalTime
 Tracks the time the last packet that arrived, so BytesPerMicrosecond can be calculated for packetArrivalHistory when a new packet arrives.
BytesPerMicrosecond AS
CCTimeType lastTransmitOfBAndAS
bool isInSlowStart
uint32_t NAKCount
uint32_t AvgNAKNum
uint32_t DecCount
 How many times we have decremented SND this congestion period. Used to limit the number of decrements to 5.
uint32_t DecInterval
 Every DecInterval NAKs per congestion period, we decrease the send rate.
DatagramSequenceNumberType nextDatagramSequenceNumber
 Every outgoing datagram is assigned a sequence number, which increments by 1 every assignment.
CCTimeType lastPacketPairPacketArrivalTime
DatagramSequenceNumberType lastPacketPairSequenceNumber
CCTimeType lastUpdateWindowSizeAndAck
double ExpCount
uint64_t totalUserDataBytesSent
CCTimeType oldestUnsentAck
DatagramSequenceNumberType expectedNextSequenceNumber
BytesPerMicrosecond mostRecentPacketArrivalHistory


Detailed Description

Encapsulates UDT congestion control, as used by RakNet Requirements:.

  1. Each datagram is no more than MAXIMUM_MTU_SIZE, after accounting for the UDP header
  2. Each datagram containing a user message has a sequence number which is set after calling OnSendBytes(). Set it by calling GetNextDatagramSequenceNumber()
  3. System is designed to be used from a single thread.
  4. Each packet should have a timeout time based on GetSenderRTOForACK(). If this time elapses, add the packet to the head of the send list for retransmission.

Recommended:

  1. Call sendto in its own thread. This takes a significant amount of time in high speed networks.

Algorithm:

  1. On a new connection, call Init()
  2. On a periodic interval (SYN time is the best) call Update(). Also call ShouldSendACKs(), and send buffered ACKS if it returns true.
  3. Call OnSendAck() when sending acks.
  4. When you want to send or resend data, call GetNumberOfBytesToSend(). It will return you enough bytes to keep you busy for estimatedTimeToNextTick. You can send more than this to fill out a datagram, or to send packet pairs
  5. Call OnSendBytes() when sending datagrams.
  6. When data arrives, record the sequence number and buffer an ACK for it, to be sent from Update() if ShouldSendACKs() returns true
  7. Every 16 packets that you send, send two of them back to back (a packet pair) as long as both packets are the same size. If you don't have two packets the same size, it is fine to defer this until you do.
  8. When you get a packet, call OnGotPacket(). If the packet is also either of a packet pair, call OnGotPacketPair()
  9. If you get a packet, and the sequence number is not 1 + the last sequence number, send a NAK. On the remote system, call OnNAK() and resend that message.
  10. If you get an ACK, remove that message from retransmission. Call OnNonDuplicateAck().
  11. If a message is not ACKed for GetRTOForRetransmission(), resend it.

Member Function Documentation

DatagramSequenceNumberType RakNet::CCRakNetUDT::GetNextDatagramSequenceNumber ( void   ) 

Every data packet sent must contain a sequence number Call this function to get it. The sequence number is passed into OnGotPacketPair()

CCTimeType RakNet::CCRakNetUDT::GetRTOForRetransmission ( void   )  const

Retransmission time out for the sender If the time difference between when a message was last transmitted, and the current time is greater than RTO then packet is eligible for retransmission, pending congestion control RTO = (RTT + 4 * RTTVar) + SYN If we have been continuously sending for the last RTO, and no ACK or NAK at all, SND*=2; This is per message, which is different from UDT, but RakNet supports packetloss with continuing data where UDT is only RELIABLE_ORDERED Minimum value is 100 milliseconds

CCTimeType RakNet::CCRakNetUDT::GetSenderRTOForACK ( void   )  const [protected]

Same as GetRTOForRetransmission, but does not factor in ExpCount This is because the receiver does not know ExpCount for the sender, and even if it did, acks shouldn't be delayed for this reason

void RakNet::CCRakNetUDT::OnAck ( CCTimeType  curTime,
CCTimeType  rtt,
bool  hasBAndAS,
BytesPerMicrosecond  _B,
BytesPerMicrosecond  _AS,
double  totalUserDataBytesAcked,
bool  isContinuousSend,
DatagramSequenceNumberType  sequenceNumber 
)

Call this when an ACK arrives. hasBAndAS are possibly written with the ack, see OnSendAck() B and AS are used in the calculations in UpdateWindowSizeAndAckOnAckPerSyn B and AS are updated at most once per SYN

bool RakNet::CCRakNetUDT::OnGotPacket ( DatagramSequenceNumberType  datagramSequenceNumber,
bool  isContinuousSend,
CCTimeType  curTime,
uint32_t  sizeInBytes,
uint32_t *  skippedMessageCount 
)

Call this when you get a packet (including packet pairs) If the DatagramSequenceNumberType is out of order, skippedMessageCount will be non-zero In that case, send a NAK for every sequence number up to that count

void RakNet::CCRakNetUDT::OnResend ( CCTimeType  curTime  ) 

Call when you get a NAK, with the sequence number of the lost message Affects the congestion control

void RakNet::CCRakNetUDT::OnSendAck ( CCTimeType  curTime,
uint32_t  numBytes 
)

Call when we send an ack, to write B and AS if needed B and AS are only written once per SYN, to prevent slow calculations Also updates SND, the period between sends, since data is written out Be sure to call OnSendAckGetBAndAS() before calling OnSendAck(), since whether you write it or not affects numBytes

void RakNet::CCRakNetUDT::OnSendAckGetBAndAS ( CCTimeType  curTime,
bool *  hasBAndAS,
BytesPerMicrosecond *  _B,
BytesPerMicrosecond *  _AS 
)

Call when you send an ack, to see if the ack should have the B and AS parameters transmitted Call before calling OnSendAck()

void RakNet::CCRakNetUDT::OnSendBytes ( CCTimeType  curTime,
uint32_t  numBytes 
)

Call this when you send packets Every 15th and 16th packets should be sent as a packet pair if possible When packets marked as a packet pair arrive, pass to OnGotPacketPair() When any packets arrive, (additionally) pass to OnGotPacket Packets should contain our system time, so we can pass rtt to OnNonDuplicateAck()

void RakNet::CCRakNetUDT::OnSendNACK ( CCTimeType  curTime,
uint32_t  numBytes 
)

Call when we send a NACK Also updates SND, the period between sends, since data is written out

void RakNet::CCRakNetUDT::SetMTU ( uint32_t  bytes  ) 

Set the maximum amount of data that can be sent in one datagram Default to MAXIMUM_MTU_SIZE-UDP_HEADER_SIZE

bool RakNet::CCRakNetUDT::ShouldSendACKs ( CCTimeType  curTime,
CCTimeType  estimatedTimeToNextTick 
)

Acks do not have to be sent immediately. Instead, they can be buffered up such that groups of acks are sent at a time This reduces overall bandwidth usage How long they can be buffered depends on the retransmit time of the sender Should call once per update tick, and send if needed

void RakNet::CCRakNetUDT::UpdateWindowSizeAndAckOnAckPreSlowStart ( double  totalUserDataBytesAcked  )  [protected]

Update the round trip time, from ACK or ACK2.

Update the corresponding variables pre-slow start


Member Data Documentation

BytesPerMicrosecond RakNet::CCRakNetUDT::AS [protected]

Data arrival rate from the sender to the receiver, as told to us by the receiver Used to calculate initial sending rate when slow start stops

uint32_t RakNet::CCRakNetUDT::AvgNAKNum [protected]

How many NAKs do you get on average during a congestion period? Starts at 1 Used to generate a random number, DecRandom, between 1 and AvgNAKNum

double RakNet::CCRakNetUDT::CWND [protected]

Supportive window mechanism, controlling the maximum number of in-flight packets Used both during and after slow-start, but primarily during slow-start Starts at 2, which is also the low threshhold Max is the socket receive buffer / MTU CWND = AS * (RTT + SYN) + 16

double RakNet::CCRakNetUDT::ExpCount [protected]

Every time SND is halved due to timeout, the RTO is increased This is to prevent massive retransmissions to an unresponsive system Reset on any data arriving

DatagramSequenceNumberType RakNet::CCRakNetUDT::expectedNextSequenceNumber [protected]

Track which datagram sequence numbers have arrived. If a sequence number is skipped, send a NAK for all skipped messages

New connections start in slow start During slow start, SND is not used, only CWND Slow start ends when we get a NAK, or the maximum size of CWND is reached SND is initialized to the inverse of the receiver's packet arrival rate when slow start ends

If a packet is marked as a packet pair, lastPacketPairPacketArrivalTime is set to the time it arrives This is used so when the 2nd packet of the pair arrives, we can calculate the time interval between the two

DatagramSequenceNumberType RakNet::CCRakNetUDT::lastPacketPairSequenceNumber [protected]

If a packet is marked as a packet pair, lastPacketPairSequenceNumber is checked to see if the last packet we got was the packet immediately before the one that arrived If so, we can use lastPacketPairPacketArrivalTime to get the time between the two packets, and thus estimate the link capacity Initialized to -1, so the first packet of a packet pair won't be treated as the second

When the receiver last calculated and send B and AS, from packetArrivalHistory and packetPairRecieptHistory Used to prevent it from being calculated and send too frequently, as they are slow operations

Used to cap UpdateWindowSizeAndAckOnAckPerSyn() to once speed increase per SYN This is to prevent speeding up faster than congestion control can compensate for

double RakNet::CCRakNetUDT::minRTT [protected]

Update: Use min/max, RTTVar follows current variance too closely resulting in packetloss.

Round trip time variance Only sender needs to know this Initialized to UNSET Set to rtt on first calculation

BytesPerMicrosecond RakNet::CCRakNetUDT::mostRecentPacketArrivalHistory [protected]

Most recent values read into the corresponding lists Used during the beginning of a connection, when the median filter is still inaccurate

uint32_t RakNet::CCRakNetUDT::NAKCount [protected]

How many NAKs arrived this congestion period Initialized to 1 when the congestion period starts

CCTimeType RakNet::CCRakNetUDT::nextSYNUpdate [protected]

When we do an update process on the SYN interval, nextSYNUpdate is set to the next time we should update Normally this is nextSYNUpdate+=SYN, in order to update on a consistent schedule However, if this would result in an immediate update yet again, it is set to SYN microseconds past the current time (in case the thread did not update for a long time)

CCTimeType RakNet::CCRakNetUDT::oldestUnsentAck [protected]

When we get an ack, if oldestUnsentAck==0, set it to the current time When we send out acks, set oldestUnsentAck to 0

BytesPerMicrosecond RakNet::CCRakNetUDT::packetArrivalHistory[CC_RAKNET_UDT_PACKET_HISTORY_LENGTH] [protected]

Used to calculate packet arrival rate (in UDT) but data arrival rate (in RakNet, where not all datagrams are the same size) Filter is used to cull lowest half of values for bytesPerMicrosecond, to discount spikes and inactivity Referred to in the documentation as AS, data arrival rate AS is sent to the sender and calculated every 10th ack Each node represents (curTime-lastPacketArrivalTime)/bytes Used with ReceiverCalculateDataArrivalRate();

Index into packetArrivalHistory where we will next write The history is always full (starting with default values) so no read index is needed

Index into packetPairRecieptHistory where we will next write The history is always full (starting with default values) so no read index is needed

double RakNet::CCRakNetUDT::RTT [protected]

Sent to the sender by the receiver from packetPairRecieptHistory whenever a back to back packet arrives on the receiver Updated by B = B * .875 + incomingB * .125 Running round trip time (ping*2) Only sender needs to know this Initialized to UNSET Set to rtt on first calculation Updated gradually by RTT = RTT * 0.875 + rtt * 0.125

MicrosecondsPerByte RakNet::CCRakNetUDT::SND [protected]

time interval between bytes, in microseconds. Only used when slowStart==false Increased over time as we continually get messages Decreased on NAK and timeout Starts at 0 (invalid)

Total number of user data bytes sent Used to adjust the window size, on ACK, during slow start


The documentation for this class was generated from the following file:

Generated on Mon Sep 6 06:56:39 2010 for RakNet by  doxygen 1.5.7.1