CS6250 COMPUTER NETWORKS EXAM 1
COMPREHENSIVE TEST PAPER WITH
SOLVED QUESTIONS
◉ TCP throughput calculation.
Answer: P = Probability of packet loss
MSS = Maximum Segment Size
RTT = Round-Trip Times
BW = data per cycle / time per cycle
BW = MSS/RTT * C / sqrt(P)
◉ Forwarding vs Routing
Answer: Forwarding - transferring a packet from an incoming link
to an outgoing link within a single router.
Routing - routers work together using routing protocols to
determine the good paths (or good routes as we call them) over
which the packets travel from the source to the destination node.
,◉ Link State Routing Algorithm
Answer: Also called Dijkstra's Algorithm.
In ___________________ the link costs and the network topology are
known to all nodes
(for example by broadcasting these values).
◉ Link State Routing Algo Example
Answer: Link state routing consists of:
Initialization step:
All currently known least-cost paths from (u) source node to its
direct attached neighbors.
Loop (Iterations): A loop is executed for every destination to (v)
every other node in the network.
During each iteration we're looking for sets of nodes that are NOT
included in the initialization and identify the node (w) with the
least cost path from the previous iteration.
Exit: It exits by returning the shortest paths and their costs from
the source node to every other node in the network.
,◉ ● Walk through an example of the link state routing
algorithm.[1] [2] [3] [4]
I wonder if it's meant for us to go through an iteration instead of
giving the logic behind the algorithm.
Maybe, I wasn't entirely sure how to answer that one.
I'll post a comment in piazza later today. It would be good to know
if we are going to be given some values and have to go through an
iteration.
Did you ever get an answer?
Answer: Initialization:
N' (set only including source node u) = {u}
for all nodes v:
If v is a neighbor of u:
Then D(v) = c(u,v)
Else:
D(v) = ∞
Loop:
Find w not in N' such that D(w) is a minimum:
Add w to N'
Update D(v) for each neighbor v of w and NOT in N':
D(v) = min( D(v), D(w) + c(w,v) )
/* new cost to v is either old cost to v or known least path cost to
w plus cost from w to v */
Exit:
, Until N' = N
◉ Computational Complexity of the Link State Routing Algorithm
Answer: In other words, in the worst case, how many
computations are needed to find the least-cost paths from the
source to all destinations in the network?
In the first iteration we need to search through all nodes to find
the node with the minimum path cost.
But as we proceed in the next iterations, this number decreases.
So in the second iteration we search through (n-1) nodes.
This decrease continues at every step.
So by the end of the algorithm, after we go through all the
iterations, we will need to search through n(n+1)/2 nodes.
Thus the complexity of the algorithm is in the order of n squared
O(n^2).
◉ Distance Vector Routing Algorithm?
COMPREHENSIVE TEST PAPER WITH
SOLVED QUESTIONS
◉ TCP throughput calculation.
Answer: P = Probability of packet loss
MSS = Maximum Segment Size
RTT = Round-Trip Times
BW = data per cycle / time per cycle
BW = MSS/RTT * C / sqrt(P)
◉ Forwarding vs Routing
Answer: Forwarding - transferring a packet from an incoming link
to an outgoing link within a single router.
Routing - routers work together using routing protocols to
determine the good paths (or good routes as we call them) over
which the packets travel from the source to the destination node.
,◉ Link State Routing Algorithm
Answer: Also called Dijkstra's Algorithm.
In ___________________ the link costs and the network topology are
known to all nodes
(for example by broadcasting these values).
◉ Link State Routing Algo Example
Answer: Link state routing consists of:
Initialization step:
All currently known least-cost paths from (u) source node to its
direct attached neighbors.
Loop (Iterations): A loop is executed for every destination to (v)
every other node in the network.
During each iteration we're looking for sets of nodes that are NOT
included in the initialization and identify the node (w) with the
least cost path from the previous iteration.
Exit: It exits by returning the shortest paths and their costs from
the source node to every other node in the network.
,◉ ● Walk through an example of the link state routing
algorithm.[1] [2] [3] [4]
I wonder if it's meant for us to go through an iteration instead of
giving the logic behind the algorithm.
Maybe, I wasn't entirely sure how to answer that one.
I'll post a comment in piazza later today. It would be good to know
if we are going to be given some values and have to go through an
iteration.
Did you ever get an answer?
Answer: Initialization:
N' (set only including source node u) = {u}
for all nodes v:
If v is a neighbor of u:
Then D(v) = c(u,v)
Else:
D(v) = ∞
Loop:
Find w not in N' such that D(w) is a minimum:
Add w to N'
Update D(v) for each neighbor v of w and NOT in N':
D(v) = min( D(v), D(w) + c(w,v) )
/* new cost to v is either old cost to v or known least path cost to
w plus cost from w to v */
Exit:
, Until N' = N
◉ Computational Complexity of the Link State Routing Algorithm
Answer: In other words, in the worst case, how many
computations are needed to find the least-cost paths from the
source to all destinations in the network?
In the first iteration we need to search through all nodes to find
the node with the minimum path cost.
But as we proceed in the next iterations, this number decreases.
So in the second iteration we search through (n-1) nodes.
This decrease continues at every step.
So by the end of the algorithm, after we go through all the
iterations, we will need to search through n(n+1)/2 nodes.
Thus the complexity of the algorithm is in the order of n squared
O(n^2).
◉ Distance Vector Routing Algorithm?
