View on GitHub

CS475

Computer Networks

CS475: Computer Networks - Routing Protocols

Activity Goals

The goals of this activity are:

To describe the routing process for local area and wide area networks
To explain and differentiate between Distance Vector, Hierarchical, and BGP routing protocols

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

Kurose Notes

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity on the Class Activity Questions discussion board. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Classful Network Addressing

Class	Leading Bits	Number of Networks	Size of Each Network
A	0	128	16M
B	10	16K	64K
C	110	2M	256
D	1110	Multicast
E	1111	Reserved

Questions

How many bits make up the network and node address of a class A, B, and C network?
Using Classless Inter-Domain Routing, how many subnet bits would correspond to a Class A, B, and C network?
Does a router need to store forwarding information for every single host on the Internet? How might it group its routing table for efficiency? This is called Hierarchical Routing.

Model 2: Link-State Routing Algorithms: Open Shortest Path First (OSPF) and Dijkstra's Algorithm


let Q = []

for vertex in G:
    distance[vertex] = inf
    prev[vertex] = nil
    Q.append(vertex)

distance[source] = 0

while not Q.empty():
    let u = Q[distance.argmin] # the cheapest destination so far
    Q.remove(u)
    
    for v in u.neighbors:
        # proposed distance is the current cost to get to u by the 
        # cheapest means, plus the cost to get from u to v
        let dist = distance[u] + u.cost(v) 
        
        if dist < distance[v]: # is this chepaer than the current cost to v?
            distance[v] = dist
            prev[v] = u

Questions

Once a shortest path has been identified to a particular destination, how might it be communicated from router to router? In other words, what information is needed by each router in order to forward information to the next destination? Specifically, how is this information different from that used by a switch?
Initially, who is the cheapest destination, when nearly all of the nodes are infinite cost?
Dijkstra's Algorithm is called a "greedy algorithm"; why do you think this is?
Execute Dijkstra's Algorithm on the graph above, using node a as the source.
How many cost comparisons are required to execute this algorithm?

Model 3: Distance Vector Routing: Routing Information Protocol (RIP) and Bellman-Ford


distance = [inf] * N
prev = [null] * N
distance[source] = 0

for i in range(V.length):
    for (u, v, w) in edges:
        dist = distance[u] + v
        if dist < distance[v]:
            distance[v] = dist

Questions

What is the length of the longest path you can traverse after each iteration of the loop?
What would happen if the graph had a negative weight edge cycle?
Execute the Bellman-Ford Algorithm on the graph above, using node a as the source.
How many cost comparisons are required to execute this algorithm?

Model 4: The Count-to-Infinity Problem and Route Poisoning

Questions

Suppose the top right node learns that it can reach the bottom-most node by going through the node at top center. The node at top center knows that it can reach the node at the top right via a direct connection. If the connection from the node at the top center to the bottom-most node is severed, why might it believe that it can still reach it by routing traffic through the node at the top right? How would their network costs be affected? What would happen to the perceived cost from the perspective of the top-right node as the top-center node updates its own cost? This is called the Count-to-Infinity Problem.
How can we fix this? Some node should indicate that its cost has become infinite. Which one? This is called Route Poisoning
Alternatively, which link should stop advertising its route and to whom? This is called Split Horizon.

Model 5: Routing at Scale: Hierarchical Routing

Questions

What information needs to be shared among the edge routers, versus that information shared within each network cluster?

Submission

Submit your answers to the questions using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section.