$(2)$ Consider the following network where each link has cost $1.$ Assume $1$ is the destination

node and nodes calculate the shortest paths using the Bellman$-$Ford algorithm.

$1234$

$($a$)$ Run the Bellman$-$Ford algorithm till convergence.

$($b$)$ Now imagine that the link between node $1$ and $2$ dies $($i$.$e$.$ the link cost on that

link is now $.)$ Run the Bellman$-$Ford algorithm but initialize the costs with

those found in part $($a$).$ Show that the costs slowly increase to infinity.

$(3)$ Consider the following maximum flow problem:

$12$

s d

$34$

Where the capacity of each link is as follows:

c $($s$,3)=$ c $(2,$d$)=15$

c $($s$,1)=$ c $(1,2)=$ c $(1,4)=$ c $(3,2)=$ c $(3,4)=$ c $(4,$d$)=5$

and all other links have zero capacity.

$($a$)$ Determine the maximum flow.

$($b$)$ Identify a minimal cut $($a minimal cut is a cut with the smallest cut capacity.$)$

$(4)$ Consider the following variant of the congestion control problem, called AIAD $($addi$-$

tive increase, additive decrease$),$ on a link of capacity c with two users:

x $1($t $+1)=$

$\{$ x $1($t$)+1$ if x $1($t$)+$ x $2($t$)$ c

x $1($t$)1$ if x $1($t$)+$ x $2($t$)>$ c

x $2($t $+1)=$

$\{$ x $2($t$)+1$ if x $1($t$)+$ x $2($t$)$ c

x $2($t$)1$ if x $1($t$)+$ x $2($t$)>$ c

Show that this algorithm does not converge to the fair solution if the initial conditions

are arbitrary.