Router Buffer Data Analysis

This page provides different sort of data analysis using ping and traceroute data.

Goals

To find the minimum buffer size along a network path.
To utilise existing measurements if they already exist.

Non-goals (at this time)

To determine where the bottleneck queuesize exists in a network path.
To deploy new measurement infrastructures.

Delays:

There are three types of delays a packet can have during its transmission from source to destination.

Yee: We don't care about how long it takes for each hop to send data etc. we only care about the goals specified above.

1. Propagation delay (Pd): A time required to send a single bit from one hop to another along the path.
2. Transmission delay (Td): A time required to transmit whole packet from a hop along the outgoing link.
3. Queing delay (Qd): A time required by the packet to wait in the buffer before being ready for transmission into an outgoing link.

Yee: Maybe specify:

1. Propagation Delay (T _p ): The time it takes for a packet to transfer across the network path when the queuing and transmission delays are zero.

1. Transmission Delay (T _d ): The time it takes for a packet to be processed and transfered through the network nodes.

1. Queuing Delay (T _q ): Variation in the end-to-end delay because the packet had to be serviced by deviced due to queuing.

There may be many nodes along the network path, each contributing to the transmission and queuing delays.

As such, the one way latency along a network path is composed of

T = T _p + T _d + T _q

Bearing in mind that the transmission and queuing delays may be at both ends of the peer link, for a single hop, we have

T _i = T _p + T _di + T _di+1 + T _qi + T _qi+1

And the complete end-to-end one way latency is defined as

T = Sum ⁿ _i of T _i

where n is the total number of nodes along a route.

Total delay is the sum of all Pd,Td and Qd along the path. Round trip time(RTT) is equal to 2 * total delay, if the reverse path takes the same route and delays.  Note: Pd is normally taken as 0, compared to other delays.
Cannot ignore Pd on long distance links, ie. it is 1 ms ~ 100km so for 1000km we have 10ms and to Pakistan (say 10,000km) it is 1000ms. for fast long distance links one can probably ignore Td since if the packet is say 100Bytes~1000bits, it takes 1ms (1000 bits / 1*10^6bps) to clock from the NIC to the wires at 1 Mbit/s, 10 usec at 100Mbits/s and 0.1us at 10Gbits/s.

Let's say, we have to find minimum buffer sizes along the path. Practically, it is very difficult to measure the exact buffer size of each hop along the path. We can somehow easily estimate the queing delay along the path using ping and traceroute tools. From queing delay, we can estimate congestion, buffer overflow, incoming and outgoing data rate. If we take the difference of incoming and outgoing datarate that will give us the queue occupancy. From queue occupancy, we can roughly estimate the buffer size of that specific router. In the following sections, I am going to explain how we can measure the average queing delay using ping, and queing delay at each and every hop along the path using traceroute.

Ping and Delays:

In a network world, ping basically helps us to measure round trip time(RTT) from source to destination using ICMP Echo Messages.  It doesn't provide, what path the packet takes to each router and the no. of routers the packet have traversed. Normally network engineers provides the no. of attempts e.g. 10 in PingER for each probe. From these 10 attempts, they measure four or five different metrics. Min Rtt, Max RTT, Avr RTT, Packet loss and sometimes the standard deviation of the RTTs. Using these metrics, we can measure the average queing delay along the whole path by subtracting MaxRTT from MinRTT.

Let L = size of the packet and, R = data rate of the whole path.

Average Qd = MaxRTT - MinRTT.
Average Td = L/R

It is practically, impossible to get a very good estimate of Queing delay at each hop along the path using ping. Yee: Why???

Traceroute and Delays:

 The default traceroute basically provides us with following metrics:

1. No. of hops from source to destination
2. IP and names of hops.
3. Three times measured RTTs from source to each hop along the path. There is an option to change three to another number.

In my own personal point of view, we can measure a good estimate of buffer size at each hop using traceroute measurement. The following sections describe the steps to figure out estimate of buffer size at each hop.

Lets say we have two hops(R1, R2) between source A and destination B.  Traceroute measure three different RTTs from A to R1 and R2 respectively. and let's denote those RTTs by (RTT1(1), RTT1(2), RTT1(3)) for R1 and (RTT2(1), RTT2(2), RTT2(3)) for R2.
Now get the max and min RTT from the two sets separately. and denote it minRTT1, maxRTT1 for R1 and minRTT2 and maxRTT2 for R2.
If we disregard the variability of the RTTs it is simple to find queing delay at R1 which is:
Queing Delay at R1 (Qd1) = maxRTT1 - minRTT1

As the packet goes, the latency from A to R2 is mainly affected by the queing delay of R1.  Hence we need to subtract the queing delay at R1 from the difference of maxRTT2 and minRTT2.
Queing Delay at R2 (Qd2) = maxRTT2 - minRTT2 - Qd1
Hence, Queing Delay of nth hop router (Rn) is given below:

In fact queing delay is variable, and three RTTs are not enough to measure a good estimate of queing delay. In this case, we need to measure the analysis of like arround 10-100 RTTs to get a sufficient good estimate of queing delay. The more RTTs we have in a set for a router, the better estimate we can fetch.
Once we have the queing delay from source to router A, we can easily find the tramission delay. Once we have transmission delay we can figure out the Incoming data rate of that router.
We know that RTT from A to R1 = 2(PdA + Td1 + Qd1), lets consider Pd, is 0 compared to Td and Qd  then
RTT from A to R1 = 2(Td1 + Qd1)
Td1 = RTT/2 - Qd1
RTT from A to R2 = 2(Td1 + Qd1) + 2(Td2 + Qd2)
                          = 2(Td1 + Td2 + Qd1 + Qd2)
Td2 = RTT/2 -Td1 - Qd1 - Qd2

In order to get a good estimate of Td we calculate the average RTT for each hop avgRTT1 = avg(RTT1, RTT2, RTT3) for router R1.
Hence the transmission delay for nth hop is given below:

In order to find queue occupancy, we need to know the incoming and outgoing link datarate.
Queue Occupancy (Qo)= incoming rate - outgoing rate
Now the incoming rate of R1 is Td1 and outgoing rate of R1 is Td2. So,
Qo1 = Td1 - Td2
Qo2 = Td2 - Td3

I am still working on figuring out the estimate of buffer size at each router, using the above calculated metrics.