Tutorial 1 - Introduction

Submission process:

Submission deadline is October 30, 14:00 CET (before the lecture) .
Commit and push your solution as separate notebook files per subtask via git as ./tutorial/tutorial1/tutorial1_4.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 4, 16: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 a separate file per subtask via git as ./tutorial/tutorial1/tutorial1_4.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 4, 16:00 CET eventually.
Please use acn@net.in.tum.de for questions regarding lecture, tutorial, and project of ACN.

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.

In [1]:

%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)
    'b1p-neth':(21.5,-60), 
    'b1p-netb':(20,-55), 
    'b1p-netf':(20,-65),
    'b2p-neta':(0,-15),
    'b2p-netc':(0,-25),
    'b3p-netc':(0,-55),
    'b3p-nete':(0,-65),
    'b4p-netd':(10,-75),
    'b4p-netg':(10,-85),
    'b4p-nete':(8.5,-80),
    'b4p-netf':(11.5,-80),
    'b5p-netb':(11.5,-20),
    'b5p-netd':(10,-25),
    'b5p-neta':(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, {}, {}, {})

No description has been provided for this image

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?

In [2]:

# fill these lists with the names of the blocked/designated/root ports
# use the names already predefined e.g., blocked = ['b1p-netb'] for blocking the port of bridge b1 connected to NetB 

# 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
    'b5p-netd', 'b3p-netc'
    # end insert code
] 
designated = [
    # begin insert code
     'b1p-netb','b1p-neth', 'b1p-netf', 'b4p-netg', 'b4p-nete', 'b4p-netd', 'b5p-neta', 'b2p-netc'
    # end insert code
]
root = [
    # begin insert code
    'b5p-netb', 'b4p-netf', 'b3p-nete', 'b2p-neta'
    # 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, Marcel Kempf, Lorenz Lehle, Nikolas Gauder, Patrick Dirks