Which part of a network layer address does the router use during path determination?

Summary: lower layers of the network should be as dumb as possible, because higher layers need to be smart anyway.

Each layer should do the minimum effort needed to satisfy its interface.

Some examples:

• acknowledgement and retransmission is only done at the transport layer

• fragments are only reassembled at the endpoint, not inside the network

The network layer (also called the internet or IP layer) is responsible for delivering packets between hosts on different local area networks.

Analogy: the mail room in the department is like a local area network, the postal service routes packets (letters) from the CS department mailroom to mailboxes all over the world. The postal service is analogous to the network layer.

The Internet Protocol (IP) is the network-layer protocol that runs the internet. There are two versions of IP in use: version 4 and version 6. We will describe version 4.

Each host on the internet has a 32-bit IP address (typically written as four decimal numbers separated by periods; IPv6 uses 64-bit addresses). An IP packet contains a destination IP address; the goal of the IP layer is to deliver packets to their destinations, by routing them through many networks. A router is a machine that reads packets from one network interface and forwards them on another.

One way to accomplish this is to use source routing: before sending a packet the sender examines the network and selects a path, encoding the path into the packet. Source routing is impractical for a number of reasons:

• end hosts need to know the topology of the network to compute paths

• network topology may change

• network topology may be private

Instead, IP uses path routing. With path routing, the packet contains only the destination address; routers decide which "next hop" to forward each packet on to get it closer to its destination. Each router makes this decision locally, based only on the destination address and its local configuration.

routing tables

One way to store this configuration is using routing tables. A routing table contains several entries, each containing a destination network and a next hop. The destination network is specified by an address / netmask pair. An IP address x is in the network y/m if x & m = y (here & is bitwise and). For example, the address 192.168.3.4 is in the network 192.0.0.0/255.0.0.0, and is also in the network 192.168.0.0/255.255.0.0, but is not in the network 192.0.0.0/255.255.255.0.

To determine the next hop for a given packet, the router will compare it to each of the entries in the routing table (by anding it with the netmask and comparing it to the network address). It will forward the packet to the first next-hop that matches.

For example, suppose a router is connected to four networks, n1, n2, n3, and n4, and that it has the following routing table:

While routing a packet destined for 1.2.3.4, it will compare it to the first row, and find that it matches (because 1.2.3.4 & 255.255.255.0 = 1.2.3.0), so the packet will be routed to n1. If the packet is destined for 1.2.5.6, the first row will not match, but the second will, so it will be forwarded to n2.

Similarly, a packet destined for 1.4.6.5 will be routed to n1, while a packet destined for 1.4.6.2 will be routed to n4.

Routing tables are a very primitive method for configuring networks. They work well for a small network, but are error prone, and don't handle routing packets across multiple paths (for example to split a stream of traffic across two different paths). Modern routers have much more sophisticated methods for deciding how to route traffic.

Where do routing tables come from?

Good routing tables require that packets are forwarded "closer" to their destinations. Routers can discover this information by communicating with their neighbors.

One such algorithm proceeds as follows. Each router maintains a local table containing the distance and next hop to each destination network. Periodically, each router r shares its entire table with its neighbors n. Each neighbor n compares this table to its own, to see if there is a shorter path to each destination d that passes through r. If so, n updates its entry, recording that the next hop to get to d is r (and that the distance from n to d is one plus the distance from r to d).

By iterating this process, each router will converge on a routing table that will give the shortest path to each destination network.

The Border Gateway Protocol (BGP) is an application-layer protocol that uses an algorithm similar to this, and is used to configure routing information on the internet.

Fragmentation

Network layer protocols (like IP) also have to deal with the fact that different networks have different transmission properties. In particular, different physical layers can have different maximum transmission units (MTUs): the maximium size of a single packet. This may mean that the IP layer needs to split large packets into smaller packets so that they can be sent along the next hop. Splitting packets is referred to as fragmentation.

Each IP header contains an identifier to indicate which original packet it is a fragment of, as well as its offset within the packet. When the end host receives a fragmented packet, it waits until it receives all fragments, and then reassembles them and delivers them to the next layer.

Which of these network layer address does the router use during path determination?

Which portion of the network layer address does a router use to forward packets?

What is path determination in networking?

What addressing structure is used in routing at the transport layer?