Configuring and Traversing Networks

Topics Covered: ICMP, DHCP, Routing Algorithms

Where We Left Off

We have subnets which are accessible by router(s). These routers could be equipped with NAT, which allows them to direct inward and outward traffic to/from a private network. Every host or router interface is identified by an IP address. IPv4 addresses are running out, so we are trying to migrate to IPv6. IP addresses are hierarchical, and CIDR specifies a network ID by the first n bits, in the /n format. The remaining bits are available addresses, with two of them reserved (broadcast and network addresses). IP tunneling allows IPv6 hosts to communicate with each other over IPv4 network (backbone routers/subnets for example may use IPv4). It also allows for VPN connection between two private networks.

ICMP

ICMP (Internet Control Messaging Protocol) resides inside of an IP packet payload.

So our IP header here would be either IPv6 or IPv4 with all its relevant fields, and the payload would contain the above fields. Despite the fact that it resides in a payload of a network layer packet, it is still a network layer protocol, and as such it is best-effort. This protocol is used mainly for checking network availability status (no process on some port, forwarding table entry nonexistent or expired, looping). For example, take the ping command. It is comprised of two parts, a request and a reply. These are done over the network layer using ICMP.

• The echo request has type 8, code 0.
• The echo reply has type 0, code 0.
• The "type-specific encoding" for ping also includes an identifier and sequence number to match requests to replies, and some variable length data (the payload).

DHCP

We've so far covered DNS, the functionality of a router, and subnets. But the issue is, let's say you have a new host on a network. You bought a computer and plugged it into your office and want to access the Internet.

1. How do you know where your DNS server (caching resolver) is? What is its IP address?
2. What's your default router? Which interface are you using? What is its IP address? What subnet are you on?

There are two solutions, either hard code this information in a config file, or use DHCP (Dynamic Host Configuration Protocol). DHCP runs over UDP.

1. Client will broadcast a DHCP discover. Remember what the broadcast address is? Last address in the subnet, but since we don't know what subnet we're in yet, it's 255.255.255.255. DHCP servers will run on port 67.
2. DHCP server will offer the client an IP address. The client now knows the IP address of the DHCP server, since it will set the source header to its IP address, and broadcast the offer. So far both messages need to be broadcast.
3. Client then sends a DHCP request, which essentially asks to confirm the IP address given. The source header is 0.0.0.0, and destination can either be the broadcast address, or we can unicast, since we know the DHCP server's IP.
4. Server will ACK the DHCP request, and this can also be unicast instead of broadcast (destination address being the yiaddrr in the above image).

Routing Algorithms

I really don't want to go super in-depth on either of these, because this is a networking class, not an algorithms class. CS 180 will give you more than enough info on both of these. On exams you'll probably be fine knowing how to work it out given a simple topology, and choosing which one OSPF uses and why, and likewise for BGP. Also note: these are algorithms, not protocols (what's the difference?).

Link State (Dijkstra's) Algorithm

Say we're given the following network topology. The nodes are routers, and edges are links, each with a certain positive cost. More cost, more time it should take to forward a packet. After

$k$ iterations, we will know the shortest path to

$k$ destinations. This algorithm is done per-router, and aims to find the shortest path to all other routers within a network. In our case, we want to find the best paths from

$A$ to the others.

Step	Visited	$D(B),p(B)$	$D(C),p(C)$	$D(D),p(D)$	$D(E),p(E)$	$D(F),p(F)$
0	A	2,A	5,A	1,A	$\mathrm{\infty }$	$\mathrm{\infty }$
1	AD	2,A	4,D	1,A	2,D	$\mathrm{\infty }$
2	ADE	2,A	3,E	1,A	2,D	4,E
3	ADEB	2,A	3,E	1,A	2,D	4,E
4	ADEBC	2,A	3,E	1,A	2,D	4,E
5	ADEBCF	2,A	3,E	1,A	2,D	4,E

For the above table, here's some FAQ.

$D(C)$ is the total cost of the best path from

$A$ to

$C$.

$p(C)$ is the "path" to

$C$. Since

$p(C)=A$, then the optimal route to

$C$ involves

$C$ as the next hop from

$A$. So we can build the whole path recursively. So in the case of path from

$A$ to

$E$, we have

$p(E)=D$. We can then look up

$p(D)=A$. So we know the best path is

$A\to D\to E$, with total cost

$D(E)=2$. The order of the visited nodes is also given by the current shortest next edge. So we visit

$D$ first since the cost is 1, then visit

$E$ since its cost is also 1, which is shorter than that to

$B$ which is 2. Given this info, the table should be straightforward for you to fill out as well.

Distance Vector (Bellman-Ford) Algorithm

In the previous algorithm, each router needs to know the complete network topology. In this case, we only know of our neighbors, and we take the info they give us as truth. It's a dynamic programming problem, with the following recurrence relation.

Let

$d_x(y)$ be the least cost path from

$x$ to

$y$. We have that

$d_x(y)=\underset{v}{min}(c(x,v)+d_v(y))$. Meaning that the cost of the best path from

$x$ to

$y$ is the minimum over all

$x$'s neighbors

$v\in V$ of the cost from

$v$ to

$x$ link plus the best path from

$v$ to

$y$.

The default initialization is just the cost to each neighbor for each node. Each iteration, the node

$x$ will send it's distance vector (a vector of all the least cost paths to all the other nodes in the topology) to it's neighbors, and the neighbors will use that vector to update their own distances. After some number of iterations, we will reach a steady state. Note that this is an asynchronous and distributed approach. We propagate after we observe some change.

Count-To-Infinity Problem

Let's say we have this steady state after some iterations of DV algorithm. We're trying to send a packet to D. We can see A has a path of cost 3 (3 hops), B 2, C 1. Let's say the connection between C and D goes down. Now C knows that it cannot reach D with cost 1 anymore, so it looks at its neighbors information. B advertises that it has a path to D with cost 2. Cool! One problem, that path was through C, but no longer exists. C takes this for truth though. C's new cost will be 3, 2 (from the path B advertises) plus 1 for C to B. C then advertises this updated distance vector to B.

B takes a look at C's new vector and sees the cost is updated to 3. Sounds good. B updates it's own vector with the new path to D from C (which is apparently 3) plus it's own to C, making the new cost 4. See the problem? A and C get this updated distance vector with B's cost increasing to 4, and update theirs to 5 using similar logic. B then updates to 6, and this continues with no end toward infinity. The solutions are:

Split Horizon with Poison Reverse

If C-D link goes down, A and B will contact each other trying to reach D (not C), but advertising that their path is infinity while doing so. Since both are doing so, then each will realize there is no path to D. Why? Work it out with the DV algorithm update step.

Path-Vector Routing

Instead of advertising the costs, advertise the paths. A will therefore announce it's path as being A -> C -> D, B advertises B -> C -> D. So if C's connected to D goes down, then B can inspect A's path and seeing C will be enough to realize that there is no path through A either. This also prevents loops. This is what BGP uses, and you'll see why in the next week's notes.

Next Week's Topics: Autonomous Systems, OSPF, BGP