CS6250 Computer Networks Exam 1 |
100% Correctly Answered and Rated
A+ | Latest 2025/2026
What is the main idea behind a link state routing algorithm?
- Correct Answer - 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?
- Correct 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?
- Correct 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?
- Correct 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).
What is the main idea behind the distance vector routing algorithm?
- Correct Answer - 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/6490994890923[1]
Thanks, this was more helpful and added additional insight.
Walk through an example of the distance vector algorithm.
- Correct Answer - 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?
- Correct Answer - 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.
This happens primarily when a neighbor's advertised path includes the
present node's path as a loop.
How does poison reverse solve the count-to-infinity problem?
100% Correctly Answered and Rated
A+ | Latest 2025/2026
What is the main idea behind a link state routing algorithm?
- Correct Answer - 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?
- Correct 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?
- Correct 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?
- Correct 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).
What is the main idea behind the distance vector routing algorithm?
- Correct Answer - 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/6490994890923[1]
Thanks, this was more helpful and added additional insight.
Walk through an example of the distance vector algorithm.
- Correct Answer - 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?
- Correct Answer - 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.
This happens primarily when a neighbor's advertised path includes the
present node's path as a loop.
How does poison reverse solve the count-to-infinity problem?
