Tutorial 4 - Transport Layer Protocols
Submission process:
- Submission deadline is December 14, 14:00 CET (before the lecture) .
- Commit and push your solution as single notebook file via git as ./tutorial/tutorial4/tutorial4.ipynb. Please take care of the correct subfolder/filename since submission is denied otherwise.
- During the first lecture after the deadline we will discuss a sample solution in class.
- Afterwards, you have time until December 21, 14:00 CET (before the lecture) to submit a corrected version of your submission:
- Rework your solution according to our discussion in class.
- Commit and push the corrected version as single file via git as ./tutorial/tutorial4/tutorial4.ipynb. Please take care of the correct filename since submission is denied otherwise.
Remarks:
- Grading is done based on both versions of your submission.
- If the first submission is missing your submission will not be graded.
- If the second submission contains major flaws after revision not more than half of the credits for this tutorial can be achieved.
- A sample solution is provided after December 21, 14:00 CET eventually.
- Please use acn@net.in.tum.de for questions regarding lecture, tutorial, and project of ACN.
Problem 1 TCP Congestion Control Fairness (4 credits)
This problem is focused on TCP congestion control. Different algorithms are observed and the fairness between them is evaluated.
In the following we consider two TCP flows which share the same bottleneck link. The next cell visualizes the sending rates of the two flows.
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
# Download RTT CSV from ACN website
!wget -N https://acn.net.in.tum.de/exercise/tcp_cc.npz
# Load file into Python
data = np.load('tcp_cc.npz')
ts, flow1, flow2 = data['ts'], data['flow1'], data['flow2']
--2024-01-17 13:10:34-- https://acn.net.in.tum.de/exercise/tcp_cc.npz Resolving acn.net.in.tum.de (acn.net.in.tum.de)... 2a00:4700:0:9:f::1, 188.95.232.11 Connecting to acn.net.in.tum.de (acn.net.in.tum.de)|2a00:4700:0:9:f::1|:443... connected. HTTP request sent, awaiting response... 304 Not Modified File ‘tcp_cc.npz’ not modified on server. Omitting download.
# Helper function to plot data
def plot(*data, x_label=None, y_label=None, legends=[], y_min=None, y_max=None):
plt.figure(figsize=(18, 6))
plt.xlabel(x_label)
plt.ylabel(y_label)
for xs, ys in data:
plt.plot(xs, ys)
plt.legend(legends)
plt.gca().set_ylim(bottom=y_min, top=y_max)
plot((ts, flow1), (ts, flow2), x_label='Time in s', y_label='Sending Rate in bps', legends=['Flow1', 'Flow2'], y_min=0)
a) [0.5 credits] One of the flows uses Cubic congestion control, the other one BBR. Identify which of the flows uses BBR. No credits without short reasoning.
Flow2 uses BBR.
The Probe RTT phases in which BBR reduces its sending rate are visible every tenth second.
b) [0.5 credits] Write a function compute_sum() which computes the total sending rate of two flows. It receives two lists and should return a list of the same size.
def compute_sum(flow1, flow2):
# begin insert code
return [sum(x) for x in zip(flow1, flow2)]
# end insert code
return flow1
plot((ts, flow1), (ts, flow2), (ts, compute_sum(flow1, flow2)),
x_label='Time in s', y_label='Sending Rate in bps', legends=['flow1', 'flow2', 'total'], y_min=0)
c) [0.5 credits] Based on your results from b) estimate the bottleneck link's capacity. What happens if the total sending rate of the two flows exceeds this value?
The bottleneck capacity is 10 Mbit/s.
If the sending rate exceeds the capacity packets are arriving faster at the bottleneck than theey can be processed. This results in the packets getting queued.
d) [0.5 credits] The minimum RTT of both flows is 50ms. Compute the path's BDP using the results from b) in kbit.
BDP = 0
# begin insert code
# BDP : Bandwidth-Delay Product
# BDP = RTT * Bandwidth
# kbit = 10^3 bit
# From b): Bandwidth is 10 Mbit = 10 * 10^6 bit
# RTT is 50ms = 50 * 10^(-3) s
BDP = 50 * 10**(-3) * 10 * 10**6 / 10**3
# end insert code
print('BDP: {:.2f} kbit'.format(BDP))
BDP: 500.00 kbit
e) [0.5 credits] In the following you will quantify the fairness of the two flows using Jain's Fairness Index. Explain two advantages of this index.
- It is within a fixed interval and always returns a value between 0 and 1
- It is scale free which means that its input does not have to be normalized
- It can be computed over an arbitrary number of flows
- It can be easily interpreted by humans. It is $\frac{k}{n}$ if there are $k$ flows are perfectly fair while the other $n − k$ shares are 0
f) [1 credits] Write a function compute_fairness() which receives a list of equal sized lists an then computes Jain's Index elementwise.
# Example:
# input: [[1, 2, 3], [4, 5, 6]]
# output: [jain(1,4), jain(2, 5), jain(3, 6)]
# with jain(x1, x2, ...): jain index of x1, x2, ...
def compute_fairness(*lists):
# this checks is all input lists have same size
assert len(set(map(len, lists))) == 1
# begin insert code
output = []
for i in range(len(lists[0])):
# From RFC 5166
# J = ( sum_i x_i )^2 / (n * sum_i ( (x_i)^2 ))
sum_normal = 0
sum_squared = 0
for l in lists:
sum_normal += l[i]
sum_squared += l[i]**2
output.append( sum_normal**2 / sum_squared / len(lists))
return output
# end insert code
# Dummy output
# returns [1,1, ...] of the same length as the first parameter
return [1, ] * len(lists[0])
plot((ts, compute_fairness(flow1, flow2)), x_label='Time in s', y_label='Jain\'s Index', y_min=0.5, y_max=1)
g) [0.5 credits] Considering the results from e), assess the fairness between Cubic and BBR. Also take the results from the next cell into account (assuming you implemented the compute_fairness function).
print('Flow1 transmitted {:.2f} Mbit/s on average.'.format(np.mean(flow1) / 10**6))
print('Flow2 transmitted {:.2f} Mbit/s on average.'.format(np.mean(flow2) / 10**6))
total_fairness = compute_fairness([np.mean(flow1)], [np.mean(flow2)])
print('This results in a total fairness of {:.5f}'.format(total_fairness[0]))
Flow1 transmitted 4.98 Mbit/s on average. Flow2 transmitted 4.75 Mbit/s on average. This results in a total fairness of 0.99945
- The two flows alternately receive more bandwidth than the other.
- Thus, the bandwidth is not shared fairly at a given point in time.
- However, considering the overall transmitted data it shows that the flows can share the bandwidth well over time.
- So, both approaches have to be considered when comparing the fairness TCP flows.
Remark: this is one of the few cases where Cubic and BBR share then bandwidth fairly. This fairness is mainly influenced by the size of the bottleneck buffer (in this case about 2.5 BDP). With smaller buffers BBR causes many retransmissions and thus pushes Cubic back, while larger buffers favor Cubic. If you want to read more about the fairness between Cubic and BBR you can have a look at this.
Problem 2 Exponential Weighted Moving Average (3 credits)
In this exercise you will compute the retransmission timout of a TCP connection. The first cell downloads a csv file which contains RTT samples of a TCP connection. You will then analyze the RTT values and finally compute the retransmission timout.
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
# Download RTT CSV from ACN website
!wget -N https://acn.net.in.tum.de/exercise/tcp_rtt.npz
# Load file into Python
data = np.load('tcp_rtt.npz')
ts, rtt = data['ts'], data['rtt']
--2024-01-17 13:10:35-- https://acn.net.in.tum.de/exercise/tcp_rtt.npz Resolving acn.net.in.tum.de (acn.net.in.tum.de)... 2a00:4700:0:9:f::1, 188.95.232.11 Connecting to acn.net.in.tum.de (acn.net.in.tum.de)|2a00:4700:0:9:f::1|:443... connected. HTTP request sent, awaiting response... 304 Not Modified File ‘tcp_rtt.npz’ not modified on server. Omitting download.
# Helper function to plot data
def plot(*data, x_label=None, y_label=None, legends=[], y_min=None, y_max=None):
plt.figure(figsize=(18, 6))
plt.xlabel(x_label)
plt.ylabel(y_label)
for xs, ys in data:
plt.plot(xs, ys)
plt.legend(legends)
plt.gca().set_ylim(bottom=y_min, top=y_max)
plot((ts, rtt), x_label='Time in s', y_label='RTT in ms', legends=['flow1'])
a) [0.1 credits] Have a look at the above graph. Which congestion control algorithm was used by the TCP sender? (No explanation required)
TCP Cubic
b) [0.5 credits] Write a function to compute the exponential weighted moving average. The function ewma() gets two parameters, a list of values and a value alpha as weight for the new samples.
def ewma(values, alpha):
# begin insert code
out = []
for sample in values:
if len(out) == 0:
# We just use the first sample as initial value
new_average = sample
else:
new_average = out[-1] * (1 - alpha) + sample * alpha
out.append(new_average)
return out
# end insert code
return values
smoothed_rtt = ewma(rtt, 0.125)
plot((ts, rtt), (ts, smoothed_rtt), x_label='Time in s', y_label='RTT in ms', legends=['RTT', 'EWMA'])
c) [0.4 credits] Compare the results when using different values for alpha and explain how it impacts the resulting average.
Larger values for alpha increase the influence of new samples. The resulting average adjusts to new values faster.
Smalle values increase the influence of past samples which makes the overall value more stable but also inertial.
d) [1.5 credits] Have a look at RFC 6298 how TCP computes the retransmission timeout (RTO). In the following we implement a function to compute this value for our connection. We will ignore the clock granularity G, e.g. consider it small enough.
Write the function compute_rto() which receives a list of RTT samples and computes the RTO values using the two state variables SRTT (smoothed round-trip time) and RTTVAR (round-trip time variation) as explained in RFC 6298.
def compute_rto(samples):
# constants
ALPHA = 0.125
BETA = 0.25
K = 4
G = 0
# begin insert code
output = []
# Initialize values
# SRTT <- R
# RTTVAR <- R/2
# RTO <- SRTT + max (G, K*RTTVAR)
r = samples[0] # first sample
srtt = r
rttvar = r / 2
rto = srtt + max(G, K * rttvar)
output.append(rto)
# we skip the first value since it was already processed in the initialization
for rtt in samples[1:]:
# RTTVAR <- (1 - beta) * RTTVAR + beta * |SRTT - R'|
# SRTT <- (1 - alpha) * SRTT + alpha * R'
# RTO <- SRTT + max (G, K*RTTVAR)
rttvar = (1 - BETA) * rttvar + BETA * abs(srtt - rtt)
srtt = (1 - ALPHA) * srtt + ALPHA * rtt
rto = srtt + max(G, K * rttvar)
output.append(rto)
return output
# end insert code
return samples
plot((ts, rtt), (ts, compute_rto(rtt)), x_label='Time in s', y_label='RTT in ms', legends=['RTT', 'RTO'])
e) [0.5 credits] Discuss the influence on TCP if the RTT is considerably overestimated or underestimated.
- RTT overestimated -> Timeout too long -> it takes a long time before the timeout is triggered after segments are lost.
- RTT unterestimated -> timeout too short -> the timeout is triggered even though no loss occurred, i.e., segments are sent multiple time but no loss occurred.
Problem 3 QUIC (3 credits)
This problem is about the QUIC protocol. QUIC is considered as the sucessor for the TCP/TLS stack and is the based for the new HTTP/3 standard.
a) [0.5 credits] Name all protocols which are usually (e.g. HTTP/1.1) used on top of IP when you visit https://acn.net.in.tum.de/. Which protocols will be used when you would visit the same page with HTTP/3?
HTTP/1.1:
- TCP
- TLS
- HTTP
HTTP/3:
- UDP
- QUIC (includes TLS)
- HTTP/3
The QUIC protocol was standardized in 2021 by the IETF. You can find the RFC here. For the next questions you need to have a closer look into the RFC.
b) [0.5 credits] QUIC differenciates between packets and frames. Name all packet types available in QUIC.
According to
- https://www.rfc-editor.org/rfc/rfc9000.html#table-5
- https://www.rfc-editor.org/rfc/rfc9000.html#name-short-header-packets
Packet Types
- Initial
- 0-RTT
- Handshake
- Retry
- 1-RTT
- Version Negotiation
c) [0.5 credits] Name 5 frame types specified in the RFC.
According to
Frame Types
- PADDING Frames
- PING Frames
- ACK Frames
- RESET_STREAM Frames
- ...
Qlog is a logging format for QUIC. The next cell downloads a qlog file of QUIC connection which transferred a small file between two hosts.
import json
# Download qlog file
!wget -N https://acn.net.in.tum.de/exercise/quic.qlog
# Load file into Python
with open('quic.qlog') as f:
data = json.load(f)
print('\nThe qlog is formatted as follows:')
print(data.keys())
print('\nThis qlog contains {} traces.'.format(len(data['traces'])))
print('Traces is a list containing the following values:')
print(data['traces'][0].keys())
events = data['traces'][0]['events']
print('\nEach trace containes a list of events:')
print(events[0])
--2024-01-17 13:10:36-- https://acn.net.in.tum.de/exercise/quic.qlog Resolving acn.net.in.tum.de (acn.net.in.tum.de)... 2a00:4700:0:9:f::1, 188.95.232.11 Connecting to acn.net.in.tum.de (acn.net.in.tum.de)|2a00:4700:0:9:f::1|:443... connected. HTTP request sent, awaiting response... 304 Not Modified File ‘quic.qlog’ not modified on server. Omitting download. The qlog is formatted as follows: dict_keys(['qlog_version', 'title', 'traces']) This qlog contains 1 traces. Traces is a list containing the following values: dict_keys(['vantage_point', 'title', 'description', 'event_fields', 'configuration', 'common_fields', 'events']) Each trace containes a list of events: [0, 'transport', 'datagram_received', {'byte_length': 1252, 'addr_from': {'ip_v4': '10.0.0.2', 'port_v4': 43109}, 'addr_to': {'ip_v4': '10.0.0.1', 'port_v4': 28695}}]
For the following questions you can either parse the qlog file in Python, or use the qvis tool which nicely visualizes the qlog. We recommend the later. You can use the version hosted at https://qvis.edm.uhasselt.be/.
Also, the format of the file is specified in this draft.
d) [0.5 credits]
Which QUIC version is used in this connection. Paste the version ID as well as which version is specified by it (hint).
Also, find out which QUIC implementation was used to generate the qlog file.
Version ID:
ff000020
draft-ietf-quic-transport-32
picoquic
The qlog containes HTTP/3 request response pair. The request can be found in event 23.
import pprint
pprint.pprint(events[23])
[5660, 'transport', 'packet_received', {'frames': [{'connection_id': '0b742c40802075c3', 'frame_type': 'new_connection_id', 'reset_token': '461136205168acc770a4727140d86cb5', 'retire_before': 0, 'sequence_number': 1}, {'connection_id': 'de22c3d56294eb4c', 'frame_type': 'new_connection_id', 'reset_token': '26661e280039cc75462416928029c39d', 'retire_before': 0, 'sequence_number': 2}, {'connection_id': 'e1b91d3f4241c41f', 'frame_type': 'new_connection_id', 'reset_token': '3201796f1fdce92446e74c64d18d03da', 'retire_before': 0, 'sequence_number': 3}, {'connection_id': '4fba79f6d325177a', 'frame_type': 'new_connection_id', 'reset_token': 'e6049a1d429f9211b22968e3edb65740', 'retire_before': 0, 'sequence_number': 4}, {'connection_id': 'df0353272a3b1bdb', 'frame_type': 'new_connection_id', 'reset_token': '9627a175e6d1a31b79108ec8e8106d48', 'retire_before': 0, 'sequence_number': 5}, {'connection_id': '0218704908ed2b78', 'frame_type': 'new_connection_id', 'reset_token': 'a5576cf0f2b86e65e865c70b20cb2c09', 'retire_before': 0, 'sequence_number': 6}, {'connection_id': 'd5669d6f7ad1b9de', 'frame_type': 'new_connection_id', 'reset_token': '3f9c7f1edbe49e88f5f45363d4344c2c', 'retire_before': 0, 'sequence_number': 7}, {'begins_with': '7465737466696c65', 'fin': True, 'frame_type': 'stream', 'id': 0, 'length': 8, 'offset': 0}], 'header': {'dcid': '7d45ea97f2aa3b42', 'key_phase': 0, 'packet_number': 0, 'packet_size': 233}, 'packet_type': '1RTT'}]
e) [0.5 credits]
- Name the packet type included in this event and explain why this packet type has to be used.
- Name and briefly explain all frame types in this event.
- 1RTT: the handshake is completed and for all further communication 1RTT packets are send which only contain the short header
- new_connection_id: the client offers the server several connection IDs to prevent tracking on connection migration
- stream: the actual HTTP request is send in an individual stream
f) [0.5 credits]
- Which event carries the response of the server?
- How large is the file requested by the client?
Event 32 carries the response. In qvis we can see that it is the only time the server sends a stream frame.
Additionally we see:
"payload_size": 100$\rightarrow$ 100B
Advanced Computer Networking by Prof. Dr.-Ing. Georg Carle
Teaching assistants: Sebastian Gallenmüller, Benedikt Jaeger, Max Helm, Patrick Sattler, Johannes Zirngibl, Marcel Kempf