cs144Lab6 | LiamY Blog

type

status

slug

date

summary

Intro

In this week’s lab checkpoint, you’ll implement an IP router on top of your existing NetworkInterface. A router has several network interfaces, and can receive Internet datagrams on any of them. The router’s job is to forward the datagrams it gets according to the routing table: a list of rules that tells the router, for any given datagram,

What interface to send it out

The IP address of the next hop

Your job is to implement a router that can figure out these two things for any given datagram. (You will not need to implement the algorithms that make the routing table, e.g. RIP, OSPF, BGP, or an SDN controller—just the algorithm that follows the routing table.)

Your implementation of the router will use the Minnow library with a new Router class, and tests that will check your router’s functionality in a simulated network. Checkpoint 6 builds on your implementation of NetworkInterface from Checkpoint 5, but does not use the TCP stack you implemented previously. IP routers don’t have to know anything about TCP, ARP, or Ethernet (only IP). We expect your implementation will require about 30–60 lines of code. (The scripts/lines-of-code tool prints “Router: 38 lines of code” from the starter code, and “89 lines of code” for our example solutions.)

Implementing the Router

In this lab, you will implement a Router class that can: • keep track of a routing table (the list of forwarding rules, or routes), and • forward each datagram it receives: – to the correct next hop – on the correct outgoing NetworkInterface. Your implementation will be added to the router.hh and router.cc skeleton files. Before you get to coding, please review the documentation for the new Router class in router.hh.

需要实现的接口：

1add_route

This method adds a route to the routing table. You’ll want to add a data structure as a private member in the Router class to store this information. All this method needs to do is save the route for later use.

The “action”: what to do if the route matches and is chosen. If the router is directly attached to the network in question, the next hop will be an empty optional. In that case, the next hop is the datagram’s destination address. But if the router is connected to the network in question through some other router, the next hop will contain the IP address of the next router along the path. The interface_num gives the index of the router’s NetworkInterface that should use to send the datagram to the next hop. You can access this interface with the interface(interface_num) method.

2route

void route();

Here’s where the rubber meets the road(关键时刻) . This method needs to route each incoming datagram to the next hop, out the appropriate interface. It needs to implement the “longest-prefix match” logic of an IP router to find the best route to follow. That means:

The Router searches the routing table to find the routes that match the datagram’s destination address. By “match,” we mean the most-significant prefix length bits of the destination address are identical to the most-significant prefix length bits of the route prefix.

Among the matching routes, the router chooses the route with the biggest value of prefix length. This is the longest-prefix-match route.

If no routes matched, the router drops the datagram.

The router decrements the datagram’s TTL (time to live). If the TTL was zero already, or hits zero after the decrement, the router should drop the datagram.

Otherwise, the router sends the modified datagram on the appropriate interface( interface(interface_num)->send_datagram() ) to the appropriate next_hop.

There’s a beauty (or at least a successful abstraction) in the Internet’s design here: the router never thinks about TCP, about ARP, or about Ethernet frames. The router doesn’t even know what the link layer looks like. The router only thinks about Internet datagrams, and only interacts with the link layer through the NetworkInterface abstraction. When it comes to questions like, “How are link-layer addresses resolved?” or “Does the link layer even have its own addressing scheme distinct from IP?” or “What’s the format of the link-layer frames?” or “What’s the meaning of the datagram’s payload?”, the router just doesn’t care.

Q&A

How do I convert an IP address that comes in the form of a raw 32-bit integer into an Address object?

Use the Address::from_ipv4_numeric() method.

How do I compare the most-significant N bits (where 0 ≤ N ≤ 32) of one 32-bit IP address with the most-significant N bits of another 32-bit IP address?

This is probably the “trickiest” part of this assignment—getting that logic right. It may be worth writing a small test program in C++ (a short standalone program) or adding a test to Minnow to verify your understanding of the relevant C++ operators and double-check your logic. Recall that in C and C++, it can produce undefined behavior to shift a 32-bit integer by 32 bits. The tests run your code under sanitizers that try to detect this. You can run the router test directly by running ./build/tests/router from the minnow directory.

If the router has no route to the destination, or if the TTL hits zero, shouldn’t it send an ICMP error message back to the datagram’s source?

In real life, yes, that would be helpful. But not necessary in this lab—dropping the datagram is sufficient. (Even in the real world, not every router will send an ICMP message back to the source in these situations.)