{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "355fb33d2ebd37e586efea15f9624f11",
     "grade": false,
     "grade_id": "cell-fdd9aaf71771f5cc",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<div style=\"background-color:rgba(100, 160, 200, 0.33);\">\n",
    "\n",
    "<h1>Tutorial 1 - Introduction</h1>\n",
    "\n",
    "<p>\n",
    "Submission process:\n",
    "</p>\n",
    "<ul>\n",
    "<li>Submission deadline is November 5, 14:00 CET (before the lecture) .</li>\n",
    "<li>Commit and push your solution as separate notebook files per subtask via git as <span style=\"font-family: monospace\">./tutorial/tutorial1/tutorial1_4.ipynb</span>. Please take care of the correct subfolder/filename since submission is denied otherwise.</li>\n",
    "<li>During the first lecture after the deadline we will discuss a sample solution in class.</li>\n",
    "<li>Afterwards, you have time until November 10, 16:00 CET (before the lecture) to submit a corrected version of your submission:</li>\n",
    "<ol>\n",
    "  <li>Rework your solution according to our discussion in class.</li>\n",
    "  <li>Commit and push the corrected version as a separate file per subtask via git as <span style=\"font-family: monospace\">./tutorial/tutorial1/tutorial1_4.ipynb</span>. Please take care of the correct filename since submission is denied otherwise.</li>\n",
    "</ol>\n",
    "</ul>\n",
    "\n",
    "<p>\n",
    "Remarks:\n",
    "</p>\n",
    "<ul>\n",
    "<li>Grading is done based on both versions of your submission.</li>\n",
    "<li>If the first submission is missing or contains major flaws a deduction of up to 50% of the achieved points will be applied</li>\n",
    "<li>A sample solution is provided after November 10, 16:00 CET eventually.</li>\n",
    "<li>Do NOT duplicate cells or change the type of cells, otherwise you might receive zero points for your submission</li>\n",
    "<li>\n",
    "Please use <a href=\"mailto:acn@net.cit.tum.de\">acn@net.cit.tum.de</a> for questions regarding lecture, tutorial, and project of ACN.\n",
    "</li>\n",
    "</ul>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "6f7c435b17e86ea6a72ffe9d89cf3ccd",
     "grade": false,
     "grade_id": "cell-cf1bf85852242b36",
     "locked": true,
     "points": 0,
     "schema_version": 3,
     "solution": false,
     "task": true
    }
   },
   "source": [
    "<div style=\"background-color:rgba(200, 100, 100, 0.33);\">\n",
    "    <p>This cell is used to verify the structure of the submission </p>\n",
    "    DO NOT DELETE OR CHANGE THIS CELL, otherwise the task will be graded with 0 points\n",
    "    </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "c77d583c9e85ee76525d4211ac489190",
     "grade": false,
     "grade_id": "cell-1fc6c0f476977aa8",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<div style=\"background-color:rgba(100, 160, 200, 0.33);\">\n",
    "<h3>Problem 4 Spanning Tree Protocol (2.5 credits)</h3>\n",
    "\n",
    "<p>\n",
    "We consider the network topology shown in the following figure.\n",
    "The bridge IDs of B1 to B5 correspond to their number, i. e., B1 has ID 1, B2 has ID 2, etc.\n",
    "For the sake of simplicity, we assume equal costs for each bridge port.\n",
    "The network segments are labeled by letters A to H. \n",
    "</p>\n",
    "    \n",
    "<p>\n",
    "    To visualize the graph we use the <span style=\"font-family: monospace\">networkx</span> module,\n",
    "    which probably needs to be installed.\n",
    "</p>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "b4d649c6b448cff63bcb53d8414872bd",
     "grade": false,
     "grade_id": "cell-189b1d6fc9d517ce",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "\n",
    "edges = [\n",
    "         # (src, dst, weight)\n",
    "         ('netA', 'B2', 1),\n",
    "         ('netA', 'B5', 1),\n",
    "         ('netB', 'B5', 1),\n",
    "         ('netB', 'B1', 1),\n",
    "         ('netC', 'B2', 1),\n",
    "         ('netC', 'B3', 1),\n",
    "         ('netD', 'B5', 1),\n",
    "         ('netD', 'B4', 1),\n",
    "         ('netE', 'B3', 1),\n",
    "         ('netE', 'B4', 1),\n",
    "         ('netF', 'B1', 1),\n",
    "         ('netF', 'B4', 1),\n",
    "         ('netG', 'B4', 1),\n",
    "         ('netH', 'B1', 1),\n",
    "         \n",
    "         ]\n",
    "\n",
    "\n",
    "networks = {\n",
    "    # 'name':(posX, posY)\n",
    "    'netA':(0,0),\n",
    "    'netB':(20,-20),\n",
    "    'netC':(0,-40),\n",
    "    'netD':(10,-60),\n",
    "    'netE':(0,-80),\n",
    "    'netF':(20,-80),\n",
    "    'netG':(10,-100),\n",
    "    'netH':(30,-60)\n",
    "}\n",
    "bridges = {\n",
    "    # 'name':(posX, posY)\n",
    "    'B1':(20,-60), \n",
    "    'B2':(0,-20),\n",
    "    'B3':(0,-60),\n",
    "    'B4':(10,-80),\n",
    "    'B5':(10,-20)\n",
    "}\n",
    "ports = {\n",
    "    # 'name':(posX, posY)\n",
    "    'b1p-neth':(21.5,-60), \n",
    "    'b1p-netb':(20,-55), \n",
    "    'b1p-netf':(20,-65),\n",
    "    'b2p-neta':(0,-15),\n",
    "    'b2p-netc':(0,-25),\n",
    "    'b3p-netc':(0,-55),\n",
    "    'b3p-nete':(0,-65),\n",
    "    'b4p-netd':(10,-75),\n",
    "    'b4p-netg':(10,-85),\n",
    "    'b4p-nete':(8.5,-80),\n",
    "    'b4p-netf':(11.5,-80),\n",
    "    'b5p-netb':(11.5,-20),\n",
    "    'b5p-netd':(10,-25),\n",
    "    'b5p-neta':(8.5,-17)\n",
    "}\n",
    "\n",
    "def plotNetwork(edges, networks, bridges, bp, dp, rp):\n",
    "    # set plot size\n",
    "    plt.figure(3,figsize=(10,10)) \n",
    "\n",
    "    # draw graph\n",
    "    G = nx.Graph()\n",
    "    G.add_weighted_edges_from(edges)\n",
    "    nx.draw_networkx_edges(G, pos=dict(dict(networks, **bridges), **ports), nodelist = [], edgelist = edges)\n",
    "    nx.draw_networkx_nodes(G, pos=networks, nodelist=networks.keys(), node_color = 'lightblue', node_size=1000)\n",
    "    nx.draw_networkx_nodes(G, pos=bridges, nodelist=bridges.keys(), node_color = 'red', node_shape='s', node_size=500)\n",
    "    nx.draw_networkx_nodes(G, pos=ports, nodelist=dp, node_color='blue', node_size=250)\n",
    "    nx.draw_networkx_nodes(G, pos=ports, nodelist=rp, node_color='green', node_size=250)\n",
    "    nx.draw_networkx_nodes(G, pos=ports, nodelist=bp, node_color='black', node_size=250)\n",
    "    nx.draw_networkx_labels(G, pos=dict(dict(networks, **bridges), **ports))\n",
    "    \n",
    "    # remove axis and plot\n",
    "    plt.axis('off')\n",
    "    plt.show()\n",
    "    \n",
    "plotNetwork(edges, networks, bridges, {}, {}, {})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "b57fd919016f620842a3c665978a3631",
     "grade": false,
     "grade_id": "cell-6ca4bde8eee8d3eb",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<div style=\"background-color:rgba(100, 160, 200, 0.33);\">\n",
    "<p>\n",
    "<b>a) [0.25 credits]</b>\n",
    "What is the difference between a shortest path tree (SPT) and a minimum spanning tree (MST)?\n",
    "</p>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "5bff600d4b48b5463bb1e27d1d98e16f",
     "grade": true,
     "grade_id": "cell-3d5322a99e86958c",
     "locked": false,
     "points": 0.25,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "8c5fb957db4e859b1a218c62046f63f9",
     "grade": false,
     "grade_id": "cell-d61a298d4fd0880d",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<div style=\"background-color:rgba(100, 160, 200, 0.33);\">\n",
    "<p>\n",
    "<b>b) [0.25 credits]</b>\n",
    "Explain the problem that is being solved by using the spanning tree protocol in a switched network.\n",
    "</p>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "3c3cc81fc540f807a0dea7a41f0be33b",
     "grade": true,
     "grade_id": "cell-ae0bf6b814698b10",
     "locked": false,
     "points": 0.25,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "f5d3cf93fb8a2112de47452e153a7502",
     "grade": false,
     "grade_id": "cell-b189f048109dd67c",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<div style=\"background-color:rgba(100, 160, 200, 0.33);\">\n",
    "<p>\n",
    "<b>c) [0.5 credits]</b>\n",
    "Explain the purpose of the root bridge and how it is elected.\n",
    "</p>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "24ee34a568a4f47ce9d72051e87b2d24",
     "grade": true,
     "grade_id": "cell-bbf214a485d409da",
     "locked": false,
     "points": 0.5,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "75cafdb503e62729bd44bd6019bc8407",
     "grade": false,
     "grade_id": "cell-9e1198a18f172cd2",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<div style=\"background-color:rgba(100, 160, 200, 0.33);\">\n",
    "<p>\n",
    "<b>d) [1 credits]</b>\n",
    "How does the resulting spanning tree look like after the spanning tree algorithm has been applied to the given network topology?\n",
    "</p>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "91d4029b428ec37a012a39f9382bc6d4",
     "grade": false,
     "grade_id": "cell-2b3ba65d6f89eb4a",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# fill these lists with the names of the blocked/designated/root ports\n",
    "# use the names already predefined e.g., blocked = ['b1p-netb'] for blocking the port of bridge b1 connected to NetB \n",
    "\n",
    "# take care that each port only occurs once\n",
    "# if a port is assigned multiple times your answer will not be accepted\n",
    "\n",
    "blocked = [\n",
    "    # begin insert code\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()\n",
    "    # end insert code\n",
    "] \n",
    "designated = [\n",
    "    # begin insert code\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()\n",
    "    # end insert code\n",
    "]\n",
    "root = [\n",
    "    # begin insert code\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()\n",
    "    # end insert code\n",
    "]\n",
    "plotNetwork(edges, networks, bridges, blocked, designated, root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "fcd16c9ec1b0203753f2fe0ba1577955",
     "grade": true,
     "grade_id": "cell-58e937907fbe173c",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Cell is used for automatic Testing\n",
    "# DO NOT DELETE OR CHANGE THIS CELL, otherwise the task will be graded with 0 points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "f4a7e2a1edb0ef2b71864ada8700eaf3",
     "grade": false,
     "grade_id": "cell-aa906d2682a70716",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "<div style=\"background-color:rgba(100, 160, 200, 0.33);\">\n",
    "<p>\n",
    "<b>e) [0.5 credits]</b>\n",
    "What happens if bridge B1 fails?\n",
    "</p>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "ac2461db1e2cd08bc8225ebdefa00f37",
     "grade": true,
     "grade_id": "cell-8a4c1b864182a2b0",
     "locked": false,
     "points": 0.5,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "98175e258e37ad6f23951e183434b81f",
     "grade": false,
     "grade_id": "cell-9d0b2555f8ed32c3",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<div style=\"background-color:rgba(100, 160, 200, 0.33);\">\n",
    "<p><b>Advanced Computer Networking by Prof. Dr.-Ing. Georg Carle</b></p>\n",
    "Teaching assistants: Christian Dietze, Sebastian Gallenmüller, Marcel Kempf, Lorenz Lehle, Patrick Dirks, Oliver Dürer\n",
    "</div>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}