\documentclass[12pt]{article}

\usepackage{fullpage,amsmath,amsfonts}
\usepackage{tikz,calc}
\usetikzlibrary{arrows,positioning,automata}

\begin{document}

\title{Foundations of Information Systems}
\author{Winter Semester 2024--25, Exercise 11}
\date{For discussion on Wednesday, January 22, 2024}
\maketitle

\begin{enumerate}

\item Compute the shortest path from node A to every other node in the
network, explicitly, using Dijkstra's algorithm.  State the routing
table for node A.

\begin{center}
\begin{tikzpicture}[>=stealth',shorten >=1pt,node distance=2cm,on grid,initial/.style    ={}]
  \node[state] (A)                    {A};
  \node[state] (C) [above right of=A] {C};
  \node[state] (B) [below right of=A] {B};
  \node[state] (D) [right of=C]       {D};
  \node[state] (E) [right of=B]       {E};
  \node[state] (F) [below right of=D] {F};
\tikzset{mystyle/.style={-}} 
\tikzset{every node/.style={auto}} 
\path (A) edge [mystyle] node {1} (C)
      (A) edge [mystyle] node {1} (B)
      (C) edge [mystyle] node {2} (D)
      (B) edge [mystyle] node {1} (D)
      (D) edge [mystyle] node {3} (F)
      (B) edge [mystyle] node {1} (E);
\end{tikzpicture}
\end{center}

\item Repeat Problem 1, but using distance-vector routing.  Draw, for
each router, a table of the form 
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
\textbf{Destination}$\vphantom{1^{1^1}}$ & 
  \textbf{Next Hop} & \textbf{Cost} \\
\hline
A$\vphantom{1}^{\vphantom{\tfrac11}}$ & \hspace*{2.5cm} & \hspace*{2.5cm}\\
B && \\
C && \\
D && \\
E && \\
F && \\
\hline
\end{tabular}
\end{center}
which you should update in steps until it no longer changes.

\item In distance-vector routing, a malicious router could advertise a
larger or smaller cost of sending packets to one or more destinations
than it actually occurs.  What could it gain?  What does this mean for
the network at large?

\item Consider a network using link state routing.  When one node of
the network broadcasts its link state packet, find an upper bound on
how many times it is transmitted in terms of the parameters of the network.


\end{enumerate}
\end{document}
