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 (RakNetTimeUS curTime)
 Reset all variables to their initial states, for a new connection.
void Update (RakNetTimeUS curTime, bool hasDataToSendOrResend)
 Update over time.
uint32_t GetNumberOfBytesToSend (RakNetTimeUS curTime, RakNetTimeUS estimatedTimeToNextTick, uint32_t unacknowledgedBytes)
bool ShouldSendACKs (RakNetTimeUS curTime, RakNetTimeUS estimatedTimeToNextTick, RakNetTimeUS timeOldestACKGenerated)
DatagramSequenceNumberType GetNextDatagramSequenceNumber (void)
void OnSend (RakNetTimeUS curTime, uint32_t numBytes)
void OnGotPacketPair (DatagramSequenceNumberType datagramSequenceNumber, uint32_t sizeInBytes, RakNetTimeUS curTime)
 Call this when you get a packet pair.
void OnGotPacket (RakNetTimeUS curTime, uint32_t sizeInBytes)
void OnNAK (RakNetTimeUS curTime, DatagramSequenceNumberType nakSequenceNumber)
void OnAck (RakNetTimeUS curTime, RakNetTimeUS rtt, bool hasBAndAS, BytesPerMicrosecond _B, BytesPerMicrosecond _AS)
void OnSendAck (RakNetTimeUS curTime, bool *hasBAndAS, BytesPerMicrosecond *_B, BytesPerMicrosecond *_AS)
RakNetTimeUS GetSenderRTOForACK (void) const

Protected Member Functions

void SetNextSYNUpdate (RakNetTimeUS currentTime)
 Update nextSYNUpdate by SYN, or the same amount past the current time if no updates have occurred for a long time.
void InitPacketPairRecieptHistory (void)
 Init corresponding list to use 1 MTU sized packet per second default.
void InitPacketArrivalHistory (void)
 Init corresponding list to use 1 MTU sized packet per second default.
BytesPerMicrosecond ReceiverCalculateLinkCapacity (void)
 Returns the average link capacity as based on the packet pair technique, after doing median filtering.
BytesPerMicrosecond ReceiverCalculateLinkCapacityMedian (void)
 Returns the median of the link capacity.
BytesPerMicrosecond ReceiverCalculateDataArrivalRate (void)
 Returns the rate of data arrival, based on packets arriving on the sender.
BytesPerMicrosecond ReceiverCalculateDataArrivalRateMedian (void)
 Returns the median of the data arrival rate.
RakNetTimeUS GetRTOForRetransmission (void) const
void EndSlowStart (void)
 Stop slow start, and enter normal transfer rate.
double BytesPerMicrosecondToPacketsPerMillisecond (BytesPerMicrosecond in)
 Does the named conversion.
void UpdateRTT (RakNetTimeUS rtt)
 Update the round trip time, from ACK or ACK2.
void UpdateWindowSizeAndAckOnAckPreSlowStart (void)
 Update the corresponding variables pre-slow start.
void UpdateWindowSizeAndAckOnAckPostSlowStart (RakNetTimeUS curTime)
 Update the corresponding variables post-slow start.
bool HasHalveSNDOnNoDataTimeElapsed (RakNetTimeUS curTime)
 Returns true on elapsed, false otherwise.
void UpdateHalveSNDOnNoDataTime (RakNetTimeUS curTime)
 Sets halveSNDOnNoDataTime to the future, unless we don't know the RTO (ping*2) yet.
void ResetOnDataArrivalHalveSNDOnNoDataTime (RakNetTimeUS 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 (BytesPerMicrosecond inputList[CC_RAKNET_UDT_PACKET_HISTORY_LENGTH], int inputListLength, int lessThanSum, int greaterThanSum)
 Calculates the median an array of BytesPerMicrosecond.
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 Attributes

MicrosecondsPerByte SND
double CWND
const RakNetTimeUS SYN
RakNetTimeUS nextSYNUpdate
BytesPerMicrosecond packetPairRecieptHistory [CC_RAKNET_UDT_PACKET_HISTORY_LENGTH]
int packetPairRecieptHistoryWriteIndex
BytesPerMicrosecond B
double RTT
double RTTVar
BytesPerMicrosecond packetArrivalHistory [CC_RAKNET_UDT_PACKET_HISTORY_LENGTH]
int packetArrivalHistoryWriteIndex
RakNetTimeUS lastPacketArrivalTime
 Tracks the time the last packet that arrived, so BytesPerMicrosecond can be calculated for packetArrivalHistory when a new packet arrives.
BytesPerMicrosecond AS
RakNetTimeUS lastTransmitOfBAndAS
bool isInSlowStart
DatagramSequenceNumberType LastDecSeq
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.
RakNetTimeUS lastPacketPairPacketArrivalTime
DatagramSequenceNumberType lastPacketPairSequenceNumber
RakNetTimeUS lastUpdateWindowSizeAndAck
RakNetTimeUS halveSNDOnNoDataTime
double ExpCount
RakNetTimeUS nextAllowedSend
uint64_t totalUserDataBytesSent


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 OnSend(). 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 OnSend() 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 OnAck().

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()

uint32_t RakNet::CCRakNetUDT::GetNumberOfBytesToSend ( RakNetTimeUS  curTime,
RakNetTimeUS  estimatedTimeToNextTick,
uint32_t  unacknowledgedBytes 
)

How many bytes can we send, pursuant to congestion control, at any given time? You can send more than this amount to fill out a datagram, or to send two messages as a packet pair Just keep it under control so as to not overflow the network or significantly affect congestion control

RakNetTimeUS RakNet::CCRakNetUDT::GetRTOForRetransmission ( void   )  const [protected]

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

RakNetTimeUS RakNet::CCRakNetUDT::GetSenderRTOForACK ( void   )  const

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 ( RakNetTimeUS  curTime,
RakNetTimeUS  rtt,
bool  hasBAndAS,
BytesPerMicrosecond  _B,
BytesPerMicrosecond  _AS 
)

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

void RakNet::CCRakNetUDT::OnGotPacket ( RakNetTimeUS  curTime,
uint32_t  sizeInBytes 
)

Call this when you get a packet (including packet pairs) If the DatagramSequenceNumberType is out of order, and the message is reliable, you should send a NAK

void RakNet::CCRakNetUDT::OnNAK ( RakNetTimeUS  curTime,
DatagramSequenceNumberType  nakSequenceNumber 
)

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

void RakNet::CCRakNetUDT::OnSend ( RakNetTimeUS  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 OnAck()

void RakNet::CCRakNetUDT::OnSendAck ( RakNetTimeUS  curTime,
bool *  hasBAndAS,
BytesPerMicrosecond *  _B,
BytesPerMicrosecond *  _AS 
)

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

bool RakNet::CCRakNetUDT::ShouldSendACKs ( RakNetTimeUS  curTime,
RakNetTimeUS  estimatedTimeToNextTick,
RakNetTimeUS  timeOldestACKGenerated 
)

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


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

BytesPerMicrosecond RakNet::CCRakNetUDT::B [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

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

If you send, and get no data at all from that time to RTO, then halve send rate Used to backoff for low-bandwidth networks (as in UDT 4.5) Set to: 0 initially curTime+RTO when elapsed during per-update tick, and data is waiting to be sent, or resent. (And halves send rate at that point) curTime+RTO when data is sent if already elapsed

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

DatagramSequenceNumberType RakNet::CCRakNetUDT::LastDecSeq [protected]

Largest sequence number sent so far when a NAK arrives Initialized to 0 If a NAK arrives with a sequence number larger than LastDecSeq, then this is defined as a new congestion period, in which case we do various things to slow our send rate.

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 UpdateWindowSizeAndAckOnAckPostSlowStart() to once speed increase per SYN This is to prevent speeding up faster than congestion control can compensate for

uint32_t RakNet::CCRakNetUDT::NAKCount [protected]

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

RakNetTimeUS RakNet::CCRakNetUDT::nextAllowedSend [protected]

Every time we send, nextAllowedSend is set to curTime + the number of bytes sent * SND We can then not send again until that time elapses The best amount of time to wait before sending again is exactly up until that time

RakNetTimeUS 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)

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

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

Tracks PacketPairHistoryNode History is initialized with 1 second intervals for all packets (slow start) All values greater than 8x of the median or less than 1/8 of the median should be ignored when calculating the average Used to calculate link capacity (via ReceiverCalculateLinkCapacity()) B = averageAmongElements(numBytes/intervalBetweenPair) B is calculated on the receiver, and send to the sender back in acks B is only sent to the sender every 10 acks, to avoid unnecessary calculation Each node represents numBytes in one of the packets in the pair / intervalBetweenPair Value is in bytes per microsecond

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]

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

double RakNet::CCRakNetUDT::RTTVar [protected]

Round trip time variance Only sender needs to know this Initialized to UNSET Set to rtt on first calculation Updated gradually by RTTVar = RTTVar * 0.875 + abs(RTT - rtt)) * 0.125

MicrosecondsPerByte RakNet::CCRakNetUDT::SND [protected]

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

const RakNetTimeUS RakNet::CCRakNetUDT::SYN [protected]

Interval at which to update aspects of the system 1. send acks 2. update time interval between outgoing packets 3, Yodate retransmit timeout

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 Wed Aug 5 09:35:47 2009 for RakNet by  doxygen 1.5.7.1