CS 6250 ACTUAL FINALS ANSWERS AND QUESTIONS
SET A+
✔✔What is the main idea behind a link state routing algorithm? - ✔✔Also called
Dijkstra's Algorithm. In link state routing, the link costs and the network topology are
known to all nodes (for example by broadcasting these values).
✔✔● What is an example of a link state routing algorithm? - ✔✔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? - ✔✔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
✔✔● What is the computational complexity of the link state routing algorithm? - ✔✔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).
✔✔What is the main idea behind the distance vector routing algorithm? - ✔✔The
Distance Vector algorithm is based on the Bellman Ford algorithm, which states each
node exchanges their distance vectors to its neighbors which update their own view of
the network. It is an iterative that loops until the neighbors do not have new updates to
send to each other. It's also asynchronous which means it does not require the nodes to
be synchronized with each other (not requiring the latest updates when they are not
ready, while still ensuring convergence). Finally it's distributed which means direct
nodes send information to one another, then they resend their results back after
performing the calculation locally on that node, this means that each node has its own
computing power and is not a centralized network.
Helpful hint: There are videos on Udacity from the previous classes at Georgia Tech
that explain this, and other concepts, in more detail. I found these videos extremely
helpful to further understand several concepts in the chapters covered. Here is the
video I found:
https://classroom.udacity.com/courses/ud436/lessons/1729198657/concepts/64909948
90923[1]
Thanks, this was more helpful and added additional insight.
✔✔● Walk through an example of the distance vector algorithm. - ✔✔Each node x
updates its own distance vector using the Bellman Ford equation: Dx(y) = minv{c(x,v) +
Dv(y)} for each destination node y in the network. A node x, computes the least cost to
reach destination node y, by considering the options that it has to reach y through each
of its neighbor v. So node x considers the cost to reach neighbor v, and then it adds the
least cost from that neighbor v to the final destination y. It calculates that quantity over
all neighbors v and it takes the minimum.
✔✔● When does the count-to-infinity problem occur in the distance vector algorithm? -
✔✔When two or more nodes keep updating their values and informs the neighbors of
the change and they in turn update their values causing the original root to update its
value again. This continues for a long time in a constant loop.
SET A+
✔✔What is the main idea behind a link state routing algorithm? - ✔✔Also called
Dijkstra's Algorithm. In link state routing, the link costs and the network topology are
known to all nodes (for example by broadcasting these values).
✔✔● What is an example of a link state routing algorithm? - ✔✔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? - ✔✔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
✔✔● What is the computational complexity of the link state routing algorithm? - ✔✔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).
✔✔What is the main idea behind the distance vector routing algorithm? - ✔✔The
Distance Vector algorithm is based on the Bellman Ford algorithm, which states each
node exchanges their distance vectors to its neighbors which update their own view of
the network. It is an iterative that loops until the neighbors do not have new updates to
send to each other. It's also asynchronous which means it does not require the nodes to
be synchronized with each other (not requiring the latest updates when they are not
ready, while still ensuring convergence). Finally it's distributed which means direct
nodes send information to one another, then they resend their results back after
performing the calculation locally on that node, this means that each node has its own
computing power and is not a centralized network.
Helpful hint: There are videos on Udacity from the previous classes at Georgia Tech
that explain this, and other concepts, in more detail. I found these videos extremely
helpful to further understand several concepts in the chapters covered. Here is the
video I found:
https://classroom.udacity.com/courses/ud436/lessons/1729198657/concepts/64909948
90923[1]
Thanks, this was more helpful and added additional insight.
✔✔● Walk through an example of the distance vector algorithm. - ✔✔Each node x
updates its own distance vector using the Bellman Ford equation: Dx(y) = minv{c(x,v) +
Dv(y)} for each destination node y in the network. A node x, computes the least cost to
reach destination node y, by considering the options that it has to reach y through each
of its neighbor v. So node x considers the cost to reach neighbor v, and then it adds the
least cost from that neighbor v to the final destination y. It calculates that quantity over
all neighbors v and it takes the minimum.
✔✔● When does the count-to-infinity problem occur in the distance vector algorithm? -
✔✔When two or more nodes keep updating their values and informs the neighbors of
the change and they in turn update their values causing the original root to update its
value again. This continues for a long time in a constant loop.
