Tutorial 6 - Network Calculus and QUIC

Submission process:

  • Submission deadline is January 30, 14:00 CET (before the lecture) .
  • Commit and push your solution as single notebook file via git as ./tutorial/tutorial6/tutorial6.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 February 6, 14:00 CET (before the lecture) to submit a corrected version of your submission:
    1. Rework your solution according to our discussion in class.
    2. Commit and push the corrected version as single file via git as ./tutorial/tutorial6/tutorial6.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 February 6, 14:00 CET eventually.
  • Please use acn@net.in.tum.de for questions regarding lecture, tutorial, and project of ACN.

Problem 1: Network Calculus (7 credits)

We will apply Network Calculus to the small network represented below:

tutorial_network_calculus_application.png

a) [0.25 credits] Represent the curves $\beta_{10,10}$ and $\gamma_{5,25}$ in the same figure.
In [1]:
%matplotlib inline

import numpy as np
import matplotlib.pyplot as plt

plt.figure(figsize=(5, 5))
plt.xlabel("Time")
plt.ylabel("Data")
plt.axis((-1,20,0,100))

# Use the following template:
# plt.plot([...], [...], label="Arrival curve")
# plt.plot([...], [...], label="Service curve")

# begin insert code

plt.plot([0, 0, 15], [0, 25, 100], label="Arrival curve")
plt.plot([0, 10, 20], [0, 0, 100], label="Service curve")

# end insert code

plt.legend()
plt.show()
No description has been provided for this image
b) [0.25 credits] Represent the backlog and the delay bounds in the figure.
In [2]:
%matplotlib inline

import numpy as np
import matplotlib.pyplot as plt

plt.figure(figsize=(5, 5))
plt.xlabel("Time")
plt.ylabel("Data")
plt.axis((-1,20,0,100))

# Use the following template:
# plt.plot([...], [...], label="Arrival curve")
# plt.plot([...], [...], label="Service curve")
# plt.plot([...], [...], label="Delay bound")
# plt.plot([...], [...], label="Buffer bound")

# begin insert code

plt.plot([0, 0, 15], [0, 25, 100], label="Arrival curve")
plt.plot([0, 10, 20], [0, 0, 100], label="Service curve")
plt.plot([0, 12.5], [25, 25], label="Delay bound")
plt.plot([10, 10], [0, 75], label="Buffer bound")

# end insert code

plt.legend()
plt.show()
No description has been provided for this image

c) [0.5 credits] What is the latency/delay bound of the flow after S1?

  • Can be determined graphically (see the previous plot)
  • Or also mathematically

$$ \begin{align*} d = & T + \frac{b}{R} \\ = & 10 + \frac{25}{10} \\ = & 12.5 \end{align*} $$

d) [0.5 credits] What is the arrival curve of the flow after it has traversed the server S1?

  • Use the definition of the output envelope: $$\alpha^*(t) = (\alpha \oslash \beta)(t)$$
  • In this case, we have: $$(\gamma_{5,25} \oslash \beta_{10,10})(t) = \gamma_{5,25 + 5 \cdot 10}(t) = \gamma_{5, 75}(t)$$

e) [0.3 credits] Using the two previous results, what is the end-to-end latency/delay bound of the flow?

  • Use the result of the previous question to compute the latency for traversing S2
  • The delay for S2 is 17.5 (see plot)
  • The end-to-end delay (S1 and S2) is: $$12.5 + 17.5 = 30$$

f) [0.5 credits] Apply the concatenation theorem to compute the end-to-end latency/delay bound of the flow and interpret the result.

  • The concatenation of S1 and S2 gives: $$ \begin{align*} (\beta_{10,10} \otimes \beta_{10,10})(t) & = \beta_{\min(10, 10), 10 + 10}(t) \\ & = \beta_{10,20}(t) \end{align*} $$

  • The end-to-end delay is then computed using $\gamma_{5,25}$ and $\beta_{10,20}$

  • The result is $22.5$, which is less than the $30$ previously calculated!

Consider the following larger network with multiple flows. We are interested in computing the latency/delay bound for flow $f_1$.

Assume all servers use strict priority queuing as scheduling algorithm. Assume that $f_1$ has the lowest priority while $f_2$ and $f_3$ have the highest priority. Furthermore, assume that the scheduling is preemptive.

topo-formula.png

g) [0.3 credits] Expain the difference between preemptive and non-preemptive scheduling.

  • Preemptive scheduling interrupts packet transmissions if the scheduler decides to serve a different packet.
  • Non-preemptive scheduling does not interrupt the transmission of packets once started.

h) [3 credits] Use the three steps of the Separate Flow Analysis to calculate the latency/delay bound for $f_1$. Clearly differentiate between the three steps in your answer.

  • LOSC:

    • $f_1$ at $s_1$: $\beta_{10,10}$

    • $f_1$ at $s_2$: $\beta_{10,10} - \gamma_{3,10} : R=7, T=\frac{110}{7}$

    • $f_1$ at $s_3$: $\beta_{10,10} - \gamma^{\star}_{3,10} -\gamma_{1,5} : R=6, T=\frac{145}{6}$

    • $f_2$ after $s_2$: $\gamma^{\star}_{3,10} = \gamma_{3,10 + 3 \cdot 10} =\gamma_{3,40}$

  • Concatenation:

$$ \begin{align*} & \beta_{e2e}^{f_1} = \beta_{10,10} \otimes \beta_{7,\frac{110}{7}} \otimes \beta_{6,\frac{145}{6}} \\ & \beta_{e2e}^{f_1} \approx \beta_{6,49.88} \\ \end{align*} $$

  • Bounds:

$$ \begin{align*} & d = 49.88 + \frac{25}{6} \approx 54.05 \\ \end{align*} $$

i) [0.7 credits] Assume that the priorities of the flows are switched (i.e. $f_1$ is the highest priority and $f_2$ and $f_3$ are the lowest priority). Use the Separate Flow Analysis to calculate the latency/delay bound of $f_1$ traversing the network.

$$ \begin{align*} & d = 30 + \frac{25}{10} = 32.5 \\ \end{align*} $$

j) [0.7 credits] Assume a flow with an arrival curve $\gamma_{10,5}$ traverses a server with a service curve $\beta_{7,3}$. Give an explanation why the latency/delay bound is infinity.

The arrival curve rate is larger than service curve rate, therefore the two curves diverge and the maximum horizontal distance between them is infinity.

Problem 2 QUIC (4.5 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

  • https://www.rfc-editor.org/rfc/rfc9000.html#section-19

Frame Types

  • PADDING Frames
  • PING Frames
  • ACK Frames
  • RESET_STREAM Frames
  • ...

d) [1 credits] Explain why there are multiple header formats in QUIC. Also explain which fields (not flags) in the short header are not encrypted and why this is the case.

Why multiple header formats: To reduce overhead during connection. Some fields only needed during connection establishment.

Not encrypted: DCID. Because it's needed to map an incoming packet to the right connection and crypto material to decrypt the rest.

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.

In [3]:
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])


7[Files: 0  Bytes: 0  [0 B/s] Re]8
7[https://acn.net.in.tum.de/exer]87Saving 'quic.qlog'
87quic.qlog            100% [=============================>]   10.70K    --.-KB/s87HTTP response 200  [https://acn.net.in.tum.de/exercise/quic.qlog]
87quic.qlog            100% [=============================>]   10.70K    --.-KB/s87[Files: 1  Bytes: 10.70K [60.12]8
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.quictools.info/.

Also, the format of the file is specified in this draft.

e) [0.6 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.

In [4]:
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'}]

f) [0.7 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

g) [0.7 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: Christian Dietze, Sebastian Gallenmüller, Max Helm, Benedikt Jaeger, Marcel Kempf, Jihye Kim, Patrick Sattler