项目作者: manas11

项目描述 :
Implementation of rLEDBAT in ns-3
高级语言: C++
项目地址: git://github.com/manas11/implementation-of-rLEDBAT-in-ns-3.git


Implementation-of-rLEDBAT-in-ns-3

Course Code: CO365

Course Name: Advanced Computer Networks

Team members:

Overview

rLEDBAT, a receiver-based, less-than-best-effort congestion control algorithm. rLEDBAT is inspired in.

LEDBAT but with the following differences:

  • rLEDBAT is implemented in the TCP receiver and controls the sending rate of the sender through the TCP Receiver Window.
  • rLEDBAT uses the round-trip-time (RTT) to estimate the queuing delay.
  • rLEDBAT uses an Additive Increase/Multiplicative Decrease algorithm to achieve inter-(r)LEDBAT fairness and avoid the latecomer advantage observed in LEDBAT.

    • rLEDBAT limits the queueing delay in the path to a target delay T.
    • rLEDBAT uses the RTT to estimate the queueing delay.
    • The rLEDBAT receiver uses the TCP TimeStamp option to measure the RTT.
    • rLEDBAT estimates the Base RTT (i.e. the RTT when there is no queuing delay) as the minimum observed RTT in the last n minutes.
  • rLEDBAT estimation of the queuing delay (qd) is obtained subtracting the Base RTT from latest sample(s) of the RTT.

Suppose that the rl.WND was last updated at time t0 and its current value is then rl.WND(t0) and at time t1 a packet is received.The rLEDBAT receiver updates rl.WND as follows:

  1. if qd < T, then rl.WND(t1) = rl.WND(t0) + alpha*MSS/rl.WND(t0)
  2. if qd > T, then rl.WND(t1) = rl.WND(t0)*betad
  3. alpha > 1
  4. 0 < betad < 1
  5. with MSS being the Maximum Segment Size of the TCP connection, and alpha and betad being the additive increase and multiplicative decrease parameters respectively
  • The multiplicative reduction is applied at most one per RTT.

Controlling Receiver Window

  • rLEDBAT uses the Receive Window (RCV.WND) of TCP to enable the receiver to control the sender’s rate.

  • RCV.WND is used to announce the available receive buffer to the sender for flow control purposes.

  • fc.WND - flow Controll Reciever Window as proposed by RFCRFC793bis (in simple terms its the standard TCP reciever window followed in New Reno or most of the TCP’s).

  • rl.WND = Reciver window as proposed by rLEDBAT draft(this needs to be calculated using the LEDBAT equation replacing the one-way delay by RTT delay).

    1. Thus
    2. RCV.WND = min(fl.WND, rl.WND)
    1. SND.WND = min(cwnd , RCV.WND)

Avoiding Window Shrinking

  • The rLEDBAT algorithm increases or decreases the rl.WND according to congestion signals
    (variations on the estimations of the queueing delay and packet loss).

  • If the new congestion window is smaller than the current one, we progressively reduce the advertised receiver window to avoid packet drops.

    1. For example, if the current congestion window is 500, the next congestion window is 300. Instead of directly advertising 300 as the receiver window, we will subtract the bytes acknowledged(received in this case), hence avoiding the packet drop.
  • The rLEDBAT algorithm only allows to perform at most one multiplicative
    decrease per RTT, this allows the receiver to drain enough packets
    from the packets in-flight to reach the reduced window resulting form
    the rLEDBAT algorithm without need for resorting to shrinking the
    receiver window.

Window Scale option

  • The rLEDBAT client should set WS option values lower than 12.(This is as per the recommendation made in the rLEDBAT draft)

Using the RTT to estimate the queueing delay

  1. This section needs to be updated because as per the draft there is no algorithm available.
  2. We can try using the queueing delay calculation algorithm by replacing the one-way delay by RTT. (Not sure how to do so placing it in Things need to be done)

Inter-rLEDBAT fairness

  • In rLEDBAT the congestion window is decreased by a multiplicative factor betad when the measured queueing delay is larger than the target T.

  • AIMD reduces the large flows rapidly hence allowing space for new flows.

Reacting to packet loss

ALgorithm

The Below algorithm assumes that we don’t use WS option because if we use that and it get more than 11 then the nature of rLEDBAT is not known.
Also according to the draft a value less than 11 is suggested.

  1. on initialization
  2. DRAINED.BYTES = 0
  3. base_RTTs set to maximum value
  4. current_RTTs set to maximum value
  5. rl.WND set to max value
  6. end.reduction.time = 0
  1. on packet arrival
  2. DRAINED.BYTES = DRAINED.BYTES + SEG.LEN
  3. RTT calculation
  4. SEG.RTT = SEG.Time - SEG.TSE (the new sample of the RTT is the time of
  5. arrival of the segment minus the time at which the segment containing
  6. the TSVal value was issued)
  7. Update current_RTTs with SEG.RTT (substitute the oldest RTT sample in
  8. the current_RTTs array by SEG.RTT)
  9. Update base_RTTs with SEG.RTT (store SEG.RTT in the current current
  10. minute position, if SEG.RTT is smaller than the value in that
  11. position)
  1. QD = min(current_RTTs) - min(base_RTTs)
  1. If local.time > end.reduction.time then
  2. If SEG.SEQ < RCV.HGH AND SEG.TSE > TSE.HGH then
  3. rl.WND = max(rl.WND*betal, 1)
  4. end.reduction.time = local.time + min(current_RTTs)
  5. else
  6. If QD < T, then rl.WND = rl.WND+ alpha*MSS/rl.WND
  7. else QD > T, then rl.WND(t1) = max(rl.WND*beta1, 1)
  8. on sending a packet
  9. if rl.WND > rl.WND.WS or (rl.WND.WS - rl.WND) < DRAINED.BYTES then
  10. rl.WND.WS = rl.WND
  11. else
  12. rl.WND.WS = rl.WND.WS - DRAINED.BYTES
  13. DRAINED.BYTES = 0
  14. RCV.WND = min(fc.WND, rl.WND.WS)

Parameters

  1. T: Target delay
  2. betal: multiplicative decrease factor in case of packet loss
  3. betad: multiplicative decrease factor in case of RTT exceeds T
  4. alpha: additive increase factor.

Variables

  1. current_RTTs is an array with the last k measured RTTs
  2. base_RTTs is an array with the minimum observed RTTs in the last n
  3. minutes
  4. RCV.SEQ is the sequence number of the last byte that was received
  5. and acknowledged
  6. RCV.HGH is the highest sequence number of a received byte (which
  7. may not have been acknowledged yet)
  8. TSE.HGH is the TSecr value contained in the segment containing the
  9. byte with sequence number RCV.HGH
  10. SEG.SEQ is the sequence number of the incoming segment
  11. SEG.TSE is the TSecr value of the incoming segment
  12. SEG.time is the local time at which the incoming segment was
  13. received
  14. SEG.RTT is the latest sample of the RTT
  15. QD latest estimation of the queueing delay
  16. rl.WND window calculated by rLEDBAT without taking into account
  17. the window shrinking avoidance constraints
  18. rl.WND.WS window calculated by rLEDBAT after taking into account
  19. the window shrinking avoidance constrains
  20. DRAINED.BYTES number of bytes drained from the flight-size since
  21. the last packet sent
  22. fc.WND window calculated by standard TCP receiver
  23. end.reduction.time auxiliary variable used to prevent rl.WND from
  24. being updated after a window reduction

NOTE:- The proposed algorithm has been derived after going through the draft algorithm may change and some other variable might be used when actually implemting in NS-3.

Assumptions

  • No Packet drop
  • System Clocks are not synchronized.

    TODO Task

    • How to solve synchronisation problem
    • Modify the existing LEDBAT NS-3 code to make it rLEDBAT instead of writing it from scratch