NPLab

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
**Sizing Router Buffer**

For a single long lived QUIC connection over a bottleneck link, what is the best buffer size for the router before the bottleneck link. A buffer that is too big adds queuing delay. A buffer that is too small has a negative effect on the throughput.

Appenzeller et. al. describe in section 2 of the paper Sizing Router Buffers the theory. Here, I try to show how the theory applies to the QUIC implementation for INET.

====== Theory ======

===== Scenario =====
A single saturated sender sends over one bottleneck link to a discard server. The sender steadily increases its congestion window and fills the buffer of the router before the bottleneck link, until the buffer has to drop the first packet.

===== The behavior =====
Once the sender detects the packet loss, it halves its cwnd from W_max to W_max/2. It now has to wait for ACKs to decrease the number of outstanding packets (packets in flight) from W_max to a value just below W_max/2, before it is allowed to continue sending packets. During that time the router empties its full buffer by sending packets onto the bottleneck link at rate C, which is the capacity of the bottleneck link in packets/sec. Thus, these packets arrive at the discard server at rate C. If the server responds on each received packet with an ACK, these ACKs in turn arrive at the sender at rate C.

Since the sender has to wait for W_max/2 ACKs, it pauses sending packets for exactly (W_max/2)/C seconds. Since the router empties its buffer at rate C, the buffer hits empty after B/C seconds, where B denotes the size of the buffer. To just avoid the buffer to go empty, the B must be chosen to hold

    (W_max/2)/C <= B/C
    <==> B >= W_max/2

## The value for W_max
The critical moment is when the router buffer is about to drain. When the sender starts sending again it has to send at least at rate C. In congestion avoidance the sending rate is W/RTT, thus we have

    C = W/RTT

When the sender just starts sending again, W = W_max/2, and the router buffer is empty (no queuing delay) which gives us

    RTT = Tt + Tp + Tt' + Tp = 2Tp + Tt + Tt'

where Tp denotes the propagation delay of the bottleneck link, Tt the transmission delay for packets from the sender to the discard server, and Tt' the transmission delay for the ACKs from the discard server to the sender (note: Appenzeller et. al. omit the transmission delays(?)).

Using these three equations, we get

    C = W/RTT = (W_max/2) / (2Tp + Tt + Tt')
    <==> W_max/2 = (2Tp + Tt + Tt') * C

This leads to this inequation for B.

    B >= (2Tp + Tt + Tt') * C

====== Simulation ======

===== The environment =====
The simulation of an example shows that the theory applies to the QUIC implementation for INET. The example used is quic/use_link_bandwidth/sizingRouterBuffer.ini, which uses this network

Client --- router1 ---(bottleneck-link)--- router2 --- Server

where the Client is the sender and the Server is a discard server.

To avoid flow control, set the values as high as possible.

    **.quic.initialMaxData = 4294967295
    **.quic.initialMaxStreamDataBidiRemote = 4294967295
    **.quic.initialMaxStreamDataUni = 4294967295

To have a saturated sender, set the send queue parameters, such that it does not dry out.

    **.client.quic.sendQueueLimit = 500000
    **.client.quic.sendQueueLowWaterRatio = .8

To keep the ACKs of the server small, let the client send ACKs on non ack eliciting packets (i. e. the ACKs from the server).

    **.quic.bundleAckForNonAckElicitingPackets = true

To have a more direct response from the server, let the server reply with an ACK on each received ack-eliciting packet from the client.

    **.server.quic.numReceivedAckElicitingsBeforeAck = 1

Define a common MTU for each interface.

    **.ppp[*].ppp.mtu = 1280

A MTU of 1280 bytes leads to full sized packets of size 1287 bytes (including the PPP header and trailer).

Set the bottleneck parameters.

    **.bottleneckDelay = 1ms
    **.bottleneckDatarate = 100Mbps

The other links are set to a unlimited datarate and no delay.

===== Size of the router buffer =====
How to size the buffer of router before the bottleneck link now? The theory says B >= (2Tp + Tt + Tt') * C. We set Tp = 1ms. C is the datarate in packets per second, thus C = 100Mb/s / 1287bytes. Tt is the transmission delay for packets from the client to the server. That is Tt = 1287bytes / 100Mb/s. Tt' is the transmission delay for the ACKs from the server to the client. At the moment of right before the client sends after the pause, these ACK packets are 58 bytes lon. Thus, Tt' = 58bytes / 100Mb/s.

    B >= (2Tp + Tt + Tt') * C = (2 * 1ms + 1287bytes / 100Mb/s + 58bytes / 100Mb/s) * 100Mb/s / 1287bytes = 20,47...

This leads to a buffer size for 21 packets. However, because the rate of incoming and outgoing packets in the router buffer might not be in sync, it happens that the last packet arrives the buffer right before a packet leaves the buffer. In this case the router has in fact only 20 packets to send during the sending pause of the client. To avoid that, increment the number by one.

    **.ppp[*].queue.frameCapacity = 22

===== The result =====
The cwnd (client.quic.cwnd) shows in congestion avoidance a maximum value of 55138 bytes. Since QUIC calculates the packet size without PPP, IP, and UDP header, we have to divide this number by 1252 bytes. If we round down to the next integer, we get W_max = 44.

==== Duration of sending pause ====
In the simulation the client starts sending at 2 s and stops at 11 s. One of the clients sending pause starts at around 8.092 s. The theory says the pause is (W_max/2)/C seconds long.

    (W_max/2)/C = 44/2 / C = 0,00226512 s

The simulation result shows (in client.quic.packetSent:sum(packetByts) that the client sends its last packet at t0 = 8.0289672 s and continues sending at t1 = 8,03123232 s, which is exactly a pause of

    t1 - t0 = 0,00226512 s

==== Length of time the router empties its buffer ====
During a pause the theory says the router empties its buffer in B/C seconds.

    B / C = 22 / C = 0,00226512 s

The simulation result shows (in ppp[1].queue.queueLength:vector) that the rate of incoming packets is not in sync with the rate of outgoing packets. So, lets look at the time the last packet left the router before the last packet from the client before the pause arrived. This happened at t2 = 8,0289188 s. The buffer hits empty at t3 = 8,03118392 s, which gives us the time the router needs to empty its buffer with

    t3 - t2 = 0,00226512 s

==== ACK receive rate ====
The theory says the ACKs arrive the client at rate C. 

The simulation result shows (in client.quic.packetReceived:sum(packetByts) that we receive from t0 to t1 22 packets, which gives us a rate of

    22 / (t1 - t0) = C

==== Throughput ====
Now, as all values are as expected, lets check the archived throughput. Sum up all received bytes (in server.ppp[0].ppp.rxPkOk:vector(packetBytes)) between second 5 and 10 multiplied by 8 * 10^6. Divide this by the difference in the time between the last and the first considered packet. The result is exactly 100 [Mb/s].