Tutorial 1 - Introduction

Submission process:

• Submission deadline is October 31, 14:00 CET (before the lecture) .
• Commit and push your solution as single notebook file via git as ./tutorial/tutorial1/tutorial1.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 November 7, 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/tutorial1/tutorial1.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 November 7, 14:00 CET eventually.
• Please use acn@net.in.tum.de for questions regarding lecture, tutorial, and project of ACN.

Problem 1 GIT Access [1.5 credits]

This exercise should make you familiar with the git repositories.

Git is a distributed version control system, originally developed by Linus Torvalds for maintaining the Linux kernel. It became popular in professional software development over the past few years due its features, stability, and efficiency. We use git in this course as a version control system for both submissions of exercises as well as the project, i.e., we provide you with a git repository structure hosted on the LRZ Gitlab. You can clone your repository and push changes to the server using SSH or HTTPS with or without a deploy token.

a) [0.5 credits] Explain the differences between the git commands add, commit, and push.

According to git man:

git-add (1) Add file contents to the index.
git-commit (1) Record changes to the repository.
git-push (1) Update remote refs along with associated objects.

b) [0.5 credits] Save your current changes to this Jupyter notebook. Add the file to a new commit and push to remote, then pull again. Execute the command git tag and paste the output here.

Explain the meaning of the output.

The output looks like this:

submission/1476987868
submission/1476989062

The git server responded with a list of tags for every successful commit pushed to the server. Each of those tags points to a specific commit in the history. These tags contain a timestamp of the commit (server time, not local machine time). We use this timestamp to check if the hand-in of the solution was done before the deadline.

c) [0.5 credits] Create and push a new branch called grades. Paste the commands used to do so into your answer. Explain what happens.

A remote branch grades already exists. The remote branch is a protected branch, which means that only authorized users may push to it.

Problem 2 SSH and Virtual Machine (VM) Access [3.0 credits]

If you can see this notebook you probably followed directions from the infrastructure introduction. To hand in your answers, please write them down in the prepared cells.

a) [0.5 credits] What is SSH and what it is being used for?

Secure shell, used for secure remote shell connections, uses TCP (default: port 22).

b) [0.5 credits] What is the difference between public-key and password authentication as offered by SSH?

• password authentication: uses a shared secret (password) between ssh-server and ssh-client for authentication. This secret is send through the tunnel in plaintext.
• public-key authentication: ssh-server and ssh-client each have their own key pair; knowing the public key of such a key pair allows authenticating the respective private key (and therefore its owner). In contrast, the private key is never transmitted over the wire.

c) [1.0 credits] SSH can be used to connect to your testbed VM and execute code (e.g., Jupyter).

You can connect to your VM (in this case we use the host i1-router0) using the command:

ssh -L localhost:1337:localhost:1337 -J svm0020.net.cit.tum.de root@i1-router0

Explain in detail what each part in this command does.

ssh -L localhost:1337:localhost:1337 -J svm0020.net.cit.tum.de root@i1-router0

• ssh -L: creates an SSH connection with local port forwarding
• localhost:1337:localhost:1337: forwards the port 1337 from localhost (first two arguments) to localhost port 1337 on the remote host (latter two arguments). The first localhost can be omitted as id is the default.
• -J svm0020.net.cit.tum.de: use the given host as jumphost to connect further
• root@i1-router0: FQDN of the remote host (i1-router0) you want to connect to and the user to log in as (root)

d) [1.0 credits] Connect to your virtual machine using SSH and execute the following three commands:

• whoami
• uname -a
• pwd

Paste the output of each of the three commands into your answer and explain what each command does.

• whoami:

• uname -a:

• pwd:

Problem 3 Jupyter Introduction (0 credits)

We will shortly introduce Jupyter and its functionality: Jupyter is an interactive programming interface running in your browser. We use the interactive Python interface.

This problem does not give any bonus credits and its purpose is to familiarize yourself with jupyter.

a) [0 credits] Jupyter notebooks consist of cells with different types, e.g., code and markdown. Explain the differences between those two types and what they can be used for.

Code cells:

A code cell allows you to edit and write new code, with full syntax highlighting and tab completion. The programming language you use depends on the kernel, and the default kernel (IPython) runs Python code.

Markdown cells

You can document the computational process in a literate way, alternating descriptive text with code, using rich text. In IPython this is accomplished by marking up text with the Markdown language. The corresponding cells are called Markdown cells. The Markdown language provides a simple way to perform this text markup, that is, to specify which parts of the text should be emphasized (italics), bold, form lists, etc.

Raw cells

Raw cells provide a place in which you can write output directly. Raw cells are not evaluated by the notebook. When passed through nbconvert, raw cells arrive in the destination format unmodified. For example, you can type full LaTeX into a raw cell, which will only be rendered by LaTeX after conversion by nbconvert.

(SOURCE)

To run cells (run Python code or show layouted markdown) either press the "Play/Run" button on top of the page or press Shift+Enter.

Code type cells fail to execute when the content is not valid Python code. We use automated tests to validate your exercises. If your solution fails to execute due to syntax errors, the automated test will also fail. Such hand-ins will be graded with 0 credits. Therefore, always execute your solution at least once on the provided virtual machine. This way you can make sure the provided solution works in our environment.

b) [0 credits] The following cell contains the typical format for programming exercises. This function is used to test your solution. Never change anything outside the begin/end insert code comments and only insert code in between:

# begin insert code
...
your code goes here
...
# end insert code

The print command will show your result in the cell output.

Errors should never occur in your handed-in notebook. Fix this code by defining the hello_world variable, assigning it a value, and returning it.

def hello_world_text():
    # begin insert code
    hello_world = 'Hello World!'
    return hello_world
    # end insert code
    return None

print(hello_world_text())

Hello World!

d) [0 credits] Code cells also allow to execute shell commands. These are executed as the user who started the jupyter server. On your virtual machine this is root. Shell commands can be executed by prefixing them with the '!' character.

# just execute this cell
!pwd  # the path where jupyter has been started
!echo This user is executing the commands: $USER
!ping -c 1 net.in.tum.de

/home/diec/Projekte/acn/exercise/2024/jupyter

This user is executing the commands: diec

PING net.in.tum.de (2a09:80c0:92::19) 56 Datenbytes
64 Bytes von vmcarle30.rbg.net.in.tum.de (2a09:80c0:92::19): icmp_seq=1 ttl=62 Zeit=0.628 ms

--- net.in.tum.de ping-Statistik ---
1 Pakete übertragen, 1 empfangen, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 0.628/0.628/0.628/0.000 ms

e) [0 credits] In some exercise sheets we will use such shell commands to install missing Python modules.

Note that Python 3.11 wants you to install packages in a virtual environment (venv) to not interfere with system-site packages. You will be shown an error if you try to do so without any venv. The tutorial image uses a venv with relevant packages preinstalled. It runs the jupyter server inside this venv. If you run the notebook locally we suggest to use a venv. If you do not know how to setup a venv you can follow this tutorial. Make sure that your jupyter process is executed within the venv.

!pip3 install matplotlib

Requirement already satisfied: matplotlib in /home/diec/Projekte/acn/exercise/2024/venv/lib64/python3.12/site-packages (3.9.2)

Requirement already satisfied: contourpy>=1.0.1 in /home/diec/Projekte/acn/exercise/2024/venv/lib64/python3.12/site-packages (from matplotlib) (1.3.1)
Requirement already satisfied: cycler>=0.10 in /home/diec/Projekte/acn/exercise/2024/venv/lib64/python3.12/site-packages (from matplotlib) (0.12.1)
Requirement already satisfied: fonttools>=4.22.0 in /home/diec/Projekte/acn/exercise/2024/venv/lib64/python3.12/site-packages (from matplotlib) (4.55.0)
Requirement already satisfied: kiwisolver>=1.3.1 in /home/diec/Projekte/acn/exercise/2024/venv/lib64/python3.12/site-packages (from matplotlib) (1.4.7)
Requirement already satisfied: numpy>=1.23 in /home/diec/Projekte/acn/exercise/2024/venv/lib64/python3.12/site-packages (from matplotlib) (2.1.3)
Requirement already satisfied: packaging>=20.0 in /home/diec/Projekte/acn/exercise/2024/venv/lib64/python3.12/site-packages (from matplotlib) (24.2)
Requirement already satisfied: pillow>=8 in /home/diec/Projekte/acn/exercise/2024/venv/lib64/python3.12/site-packages (from matplotlib) (11.0.0)
Requirement already satisfied: pyparsing>=2.3.1 in /home/diec/Projekte/acn/exercise/2024/venv/lib64/python3.12/site-packages (from matplotlib) (3.2.0)
Requirement already satisfied: python-dateutil>=2.7 in /home/diec/Projekte/acn/exercise/2024/venv/lib64/python3.12/site-packages (from matplotlib) (2.9.0.post0)

Requirement already satisfied: six>=1.5 in /home/diec/Projekte/acn/exercise/2024/venv/lib64/python3.12/site-packages (from python-dateutil>=2.7->matplotlib) (1.16.0)

[notice] A new release of pip is available: 23.3.2 -> 24.3.1
[notice] To update, run: pip install --upgrade pip

In order to visualize measurement data tools such as matplotlib are very useful. Jupyter notebook supports inline presentation of matplotlib plots. This is a convenient way to visualize data.

In this exercise you can see how matplotlib is used. Just execute the first cell. It should show you a histogram of datapoints following a normal distribution.

# This enables inline plots
%matplotlib inline

# Example taken from https://matplotlib.org/3.1.1/gallery/statistics/histogram_features.html

import numpy as np
import matplotlib.pyplot as plt

# example data
mu = 0  # mean of distribution
sigma = 1  # standard deviation of distribution
x = mu + sigma * np.random.randn(10000) # 10k data samples

num_bins = 50

fig, ax = plt.subplots()

# the histogram of the data
counts, bins, patches = ax.hist(x, num_bins)

ax.set_xlabel('Value')
ax.set_ylabel('Count')
ax.set_title(r'Histogram of a normal distribution: $\mu=0$, $\sigma=1$')

plt.show()

f) [0 credits] Use the data from the previous cell to produce a CDF. (This and this might help you)

fig, ax = plt.subplots()

# begin insert code
ax.hist(x, num_bins, cumulative=True, density=True)
# end insert code

ax.set_xlabel('Value')
ax.set_ylabel('Cumulated Probability')
ax.set_title(r'CDF of normal distribution: $\mu=0$, $\sigma=1$')

plt.show()

Problem 4 Spanning Tree Protocol (2.5 credits)

We consider the network topology shown in the following figure. The bridge IDs of B1 to B5 correspond to their number, i. e., B1 has ID 1, B2 has ID 2, etc. For the sake of simplicity, we assume equal costs for each bridge port. The network segments are labeled by letters A to H.

To visualize the graph we use the networkx module, which probably needs to be installed.

%matplotlib inline

import networkx as nx
import matplotlib.pyplot as plt


edges = [
         # (src, dst, weight)
         ('netA', 'B2', 1),
         ('netA', 'B5', 1),
         ('netB', 'B5', 1),
         ('netB', 'B1', 1),
         ('netC', 'B2', 1),
         ('netC', 'B3', 1),
         ('netD', 'B5', 1),
         ('netD', 'B4', 1),
         ('netE', 'B3', 1),
         ('netE', 'B4', 1),
         ('netF', 'B1', 1),
         ('netF', 'B4', 1),
         ('netG', 'B4', 1),
         ('netH', 'B1', 1),
         
         ]


networks = {
    # 'name':(posX, posY)
    'netA':(0,0),
    'netB':(20,-20),
    'netC':(0,-40),
    'netD':(10,-60),
    'netE':(0,-80),
    'netF':(20,-80),
    'netG':(10,-100),
    'netH':(30,-60)
}
bridges = {
    # 'name':(posX, posY)
    'B1':(20,-60), 
    'B2':(0,-20),
    'B3':(0,-60),
    'B4':(10,-80),
    'B5':(10,-20)
}
ports = {
    # 'name':(posX, posY)
    'b1pa':(21.5,-60), 
    'b1pb':(20,-55), 
    'b1pc':(20,-65),
    'b2pa':(0,-15),
    'b2pb':(0,-25),
    'b3pa':(0,-55),
    'b3pb':(0,-65),
    'b4pa':(10,-75),
    'b4pb':(10,-85),
    'b4pc':(8.5,-80),
    'b4pd':(11.5,-80),
    'b5pa':(11.5,-20),
    'b5pb':(10,-25),
    'b5pc':(8.5,-17)
}

def plotNetwork(edges, networks, bridges, bp, dp, rp):
    # set plot size
    plt.figure(3,figsize=(10,10)) 

    # draw graph
    G = nx.Graph()
    G.add_weighted_edges_from(edges)
    nx.draw_networkx_edges(G, pos=dict(dict(networks, **bridges), **ports), nodelist = [], edgelist = edges)
    nx.draw_networkx_nodes(G, pos=networks, nodelist=networks.keys(), node_color = 'lightblue', node_size=1000)
    nx.draw_networkx_nodes(G, pos=bridges, nodelist=bridges.keys(), node_color = 'red', node_shape='s', node_size=500)
    nx.draw_networkx_nodes(G, pos=ports, nodelist=dp, node_color='blue', node_size=250)
    nx.draw_networkx_nodes(G, pos=ports, nodelist=rp, node_color='green', node_size=250)
    nx.draw_networkx_nodes(G, pos=ports, nodelist=bp, node_color='black', node_size=250)
    nx.draw_networkx_labels(G, pos=dict(dict(networks, **bridges), **ports))
    
    # remove axis and plot
    plt.axis('off')
    plt.show()
    
plotNetwork(edges, networks, bridges, {}, {}, {})

a) [0.25 credits] What is the difference between a shortest path tree (SPT) and a minimum spanning tree (MST)?

• SPT: A shortest path tree (SPT) contains the shortest paths from one node (the tree’s root) to all other nodes.
• MST: A minimum spanning tree (MST) connects all nodes of the network in a way such that the sum of edge weights is minimized.

Both variants are spanning trees and neither tree is unique. The outcome of the spanning tree protocol is an SPT rooted at the root bridge.

b) [0.25 credits] Explain the problem that is being solved by using the spanning tree protocol in a switched network.

The STP is useful when there are loops on layer 2, which would cause a broadcast storm since bridges forward frames to broadcast or unknown destination addresses via all ports except the port from which the frame has been received. Creating a spanning tree ensures that frames are not forwarded back and forth indefinitely. The minimum spanning tree in addition guarantees that the minimum number of network segments (bridges) are traversed.

Remember, there is no TTL or MaxHops counter in Ethernet as there is for IP. Furthermore, the STP creates backup paths in case of link or bridge failures.

c) [0.5 credits] Explain the purpose of the root bridge and how it is elected.

The root bridge acts as reference point in the network as the resulting SPT depends on which bridge is chosen. The root bridge is determined via an election process:

• Initially, each bridge assumes it is the root bridge and starts transmitting bridge protocol data units (BPDUs). These contain the transmitters bridge ID, the root bridge ID, and the distance from the transmitter to the root bridge. The bridge ID itself consists of a (configurable) priority field and the bridge’s MAC address.
• Bridges listen for incoming BPDUs on all ports. BPDUs are not forwarded but evaluated:
• The port from where the BPDU with the lowest bridge ID is received (with the lowest path length) becomes the root port of a bridge.
• If two ports connect the networks to the root bridge the one with the higher cost, or in case of same costs the bridge with the higher id blocks its ports to this network.
• All other ports become designated ports

Given some time, the algorithm outlined above converges and leads to an SPT with the root bridge as root node. Note that any segment has precisely one designated port. In case of segments that have two or more bridges with identical path lengths to the root bridge, the bridge with the lower bridge ID will serve that segment. The other bridges set their ports to that segment into blocking mode. Otherwise, the root bridge with the unique lowest path length to the root bridge serves a segment.

d) [1 credits] How does the resulting spanning tree look like after the spanning tree algorithm has been applied to the given network topology?

# fill these lists with the names of the blocked/designated/root ports
# use the names already predefined e.g., blocked = ['b1pa'] for blocking port a of bridge b1

# take care that each port only occurs once
# if a port is assigned multiple times your answer will not be accepted

blocked = [
    # begin insert code
    'b5pb', 'b3pa'
    # end insert code
] 
designated = [
    # begin insert code
    'b1pb', 'b1pa', 'b1pc', 'b4pb', 'b4pc', 'b4pa', 'b5pc', 'b2pb'
    # end insert code
]
root = [
    # begin insert code
    'b5pa', 'b4pd', 'b3pb', 'b2pa'
    # end insert code
]
plotNetwork(edges, networks, bridges, blocked, designated, root)

e) [0.5 credits] What happens if bridge B1 fails?

If B1 fails, it stops transmitting BPDUs. When the neighboring bridges do not receive those BPDUs over a given time interval, they recognize that the root bridge is gone. According to the algorithm above a new bridge becomes the root bridge, in our example this will be B2.

As long as B1 is not available, netH will be disconnected from the network.

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