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.

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, and compare with your group to prepare for our whole-class discussion. 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?

Embedded Code Environment

You can try out some code examples in this embedded development environment! To share this with someone else, first have one member of your group make a small change to the file, then click "Open in Repl.it". Log into your Repl.it account (or create one if needed), and click the "Share" button at the top right. Note that some embedded Repl.it projects have multiple source files; you can see those by clicking the file icon on the left navigation bar of the embedded code frame. Share the link that opens up with your group members. Remember only to do this for partner/group activities!

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] + w
        if dist < distance[v]:
            distance[v] = dist
            prev[v] = u

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?
Why might one use the Bellman-Ford Algorithm instead of Dijkstra's Algorithm for routing, when Dijkstra's Algorithm is more time efficient on a single host?
How does a node learn what the network topology looks like to facilitate these computations?

Embedded Code Environment

You can try out some code examples in this embedded development environment! To share this with someone else, first have one member of your group make a small change to the file, then click "Open in Repl.it". Log into your Repl.it account (or create one if needed), and click the "Share" button at the top right. Note that some embedded Repl.it projects have multiple source files; you can see those by clicking the file icon on the left navigation bar of the embedded code frame. Share the link that opens up with your group members. Remember only to do this for partner/group activities!

Model 4: The Count-to-Infinity Problem with Route Poisoning or Split Horizon

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?
Suppose a network has a route of 192.168.1.0/24 and 0.0.0.0/0 (known as a "default route"). The address 192.168.1.2 would match both of these. Which route should you choose, and why? How can you determine which routing table match is the "best" one?

Submission

I encourage you to submit your answers to the questions (and ask your own 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. You can find the link to the class notebook on the syllabus.