Network Layer

The network layer (or internet layer) contains the Internet Protocol IP, in which data travels in datagrams, or packets, which travel over a series of interconnected networks (internet).

The application offers a data stream to the trasport layer, which is converted into an IP datadram for the network layer. This is then routed through the internet.

1. IP

The IP header contains:

1.1 Fragmentation

Routers must handle cases where the size of the datagram exceeds the maximum transmission unit (MTU) of the output link. In those cases, the datagram must be fragmented, and then reassabled by the destination. This pushes complexity out of the network.

Let's assume a non fragmented datagram of size .

  1. The sender assigns a 16-bit identifier to the datagram during identification.
  2. The fragment offset is set to , indicating the offset of the data in the original datagram.
  3. The more fragments flag is set to if there are more fragments to come.

The fragment offset field is in units of 8 bytes, so the offset is multiplied by 8 to get the byte offset. For example, assuming an MTU of 512 bytes, a datagram of B without headers would be fragmented into three fragments:

1.2 IPv4 Addressing

IPv4 addresses are 32-bit long (4-billion possible). Each IP address is associated with an interface (not host). These addresses are managed by ICANN, who delegate address spaces to various regional authorities, who then delegate to ISPs. This avoids conflits.

1.3 Subnet Masks

Hosts on the same network must share the same address, and be divided internally into subnet addresses and host IDs. This introduces a 3-level routing hierarchy:

  1. External routers only consider network addresses and forward packets to the correct network.
  2. Subnet routers apply the subnet mask, and look up if the destination is on their subnet.
  3. After a host is found, the router knows which interface to use to forward the packet.

All intercaes in the same subnet share a prefix. The network address and prefix length is written as a.b.c.d/x, where x is the number of bits in the prefix.

A network mask is written in the same notation, a.b.c.d/x.y.z.w, where x.y.z.w is the subnet mask. For example

The any-length prefix scheme is also called Classless Interdomain Routing (CIDR). This allows outside routers to ignore the specifics of each address, and treat all addresses as a single entity.

1.4 Longest Prefix Matching

Routers try to match the longest possible prefix in order to select the correct network. They (&) the IP address with its subnet masks, and if they know where this is, they forward the packet out of the correct port / interface. If not, it is handled differently depending on the router.

1.5 DHCP

How does a host safely obtain an IP address? The Dynamic Host Configuration Protocol (DHCP) allows for this:

  1. Each newly-botted machine broadcasts a DHCP discover message.
  2. DHCP server replies with the assigned IP address.
  3. DHCP server can either maintain static mappings or assign different addresses each time a host connects.

To prevent hosts from keeping addresses forever, we require a periodic refresh (leasing). This is how you receive an IP from your ISP.

1.6 NAT

Network Address Translation (NAT) partially solves IP shortage by translating a single public IP into multiple private ones. Within a subnet, every computer gets a unique local IP address used for internal traffic, and a single public IP address is used for external traffic. This is done by the NAT router. When a packet exits the local network, address translation takes place. Each datagram also has a header with the source and destination port.

The following address ranges are declared as private, to be used within a network:

We also define some special IP addresses:

However, NAT is critisiced as it violates the architectural IP model, and breaks the end-to-end principle. It also makes it harder to deploy new services, and breaks some applications.

1.7 ICMP

The Internet Control Message Protocol (ICMP) is used to send error messages and operational information. It is used by routers to communicate with each other, and by hosts to communicate with routers. It is also used to test connectivity. In essence, it encapsulates control messages in IP packets. Several message types exist, each specified by a code (e.g. 0 for echo reply, 3 for destination unreachable, etc.).

1.8 IPv6

IPv6 will support many more hosts, reduce the size of routing tables, simplify the protocol, provide improved security, support new services, multicasting and roaming hosts. Features include:

Unlike IPv4, IPv6 does not support:

Due to the large address space, we can also be less efficient with how we assign addresses. The basic idea is to keep the main header as simple as possible.

2. Routers

The fundamental component in the Network Layer. They have a finite set of input / output connections. It has interfaces or physical ports. They provide facilities for getting data from a source to a destination. This may require many hops at intermediate routers (routing). It must know the topology of the network to select paths. Load balancing among routers is required. It also has to deal with network heterogeneity.

2.1 Datagram Networks

They are a:

There are potentially multiple, asymmetric paths for the same source / destination.

When we send a datagram from to , we say the datagram is forwarded to . This can be seen as a function of , taking in a datagram destination and outputting a physical port. To do this, we must maintain a forwarding table.

Routers cooperate to find best routes between all pairs of nodes. They collablorate to build a sink tree for each node: a tree that connects contains the optimal routes towards a specific host, without any loops.

2.2 Flood Routing

Forward incoming packet across every outgoing link, except the original source. How do we avoid drowning by packets?

Flooding always chooses the shortest path because all paths were explored in parallel. However, it introduces a lot of overhead. It makes sense only when robustness is needed.

2.3 Distance Vector Routing

This is a dynamic protocol. Now, we:

  1. Consider costs that direct neigbours are advertising to get packet to destination.
  2. Select neighbour whose advertises cost, added with own cost to get to that neighbour, is lowest.
  3. Advertise new cost to other neighbours.

We can express this idea with the bellman-ford equation:

Find the cost of the least cost path from to xu$. This will be the minimum sum of:

The problem with distance vector routing is the count-to-infinity problem. This occurs when a link goes down, and the cost to a destination is increased by one at each hop. The packet will hop within a loop of routers, increasing the cost each time.

2.4 Link State Routing

This is meant to broadcast information about network topology to all routers. Each router calculates a sink tree to other routers. To achieve this, each router:

  1. Discovers network addresses of direct neighbours.
  2. Calculates cost for sending packet to each neighbour.
  3. Constructs Link State Advertisement (LSA) packet.
  4. Sends / collects that packet to / from all other routers (not just neighbours).
  5. Runs Dijkstra's algorithm to find shortest path to each destination.

We are now storing information about, our neighbours, the entire network and the routing table you generated.

We identify neighbours by sending a HELLO packet through each interface, and router on the other end responds with its address. We measure a link cost by sending an ECHO packet through each interface ,and measure the round trip delay.

Every router uses flooding to send its LSA to all other routers. Once we have all LSAs from every router, we have complete knowledge of the network and can run Dijkstra's algorithm locally.

2.5 Hierarchical Routing

However, this algorithm cannot scale. We cannot store all LSAs in a single router, and we cannot run Dijkstra's algorithm on a large network. We could go for suboptimal routes by introducing regions, and have sperate algorithms for intra-region and inter-region routing. Two or three levels are generally sufficient.

2.6 Broadcast Routing

We have to send a message to almost every host on the network. Sending each one individually is not efficient. Using flood routing would be acceptable, provided that we limit the flood. We could use a multi-destination routing approach, by using a list that is sent with the packet. The oruter checks destination and splits list when forwarding it to different interfaces. But, this requires the message to contain all destinations. Instead, we could build a sink tree at the source, and use a multicast route - but the sink tree must be a spanning tree, and all routers must somehow agree on a tree.

What if we don't know the spanning tree? How can we construct one at low cost? We use a reverse path forwarding (RPF) broadcast:

2.7 Multicast Routing

A message shoul;d only go to a subset of nodes. We can construct a spanning tree at each router, and use a group-id to prune paths to nodes that do not contain members of the group. However, this will not scale - as we need to maintain a spanning tree per source.

Instead, we could use core-based trees, with a single spanning tree per node group, with root (core) near the middle of the group. To send a multicast message, the host sends it to the core, which performs multicast along the tree. This may not be optimal for all sources, but it drastically reduces storage and maintenance costs.

3. The Network Model

The internet is organized in autonomous systems: independent administrative domains, and gateway routers interconnect autonomous systems. Within a single AS, we use interior gateway protocols:

Border gateway protocols run between different ASs:

Routers within AS exchange intra-AS routing information, and gateway routers discover inter-AS routing information. Both routing informations are used to populate forwarding tables.

3.1 OSPF

Open Shortest Path First is a link state routing protocol, replacing RIP. It requires that:

The protocol abstracats a collection of networks into a directed graph, each edge with cost. A serial link between two routers is prepresented by a pair of arcs, one in each direction. Multi-access network is represented for a node for the network itself, plus a node for each router. It computes the shortest path from every router to every other router.

OSPF allows dividing large ASs into areas, with area border routers, and a single backbone area.

3.2 BGP

The Border Gateway Protocol is an inter-AS routing protocol used by all ASs on the internet. Neighbouring routers maintain a connection to simplify reliability. This:

It determines all good routes to all outside subnets, based on reachability information and policies. It is a path-vector protocol, based on distance vector routing. A router decides on the entire path and hence does not suffer from the count-to-infinity problem.

A BGP advertisement has destinations denoted by address prefixes. AS may or may not forward advertisement for a foreign network, doing so means willingness to carry traffic for that network. Routers may also aggregate prefixes with supernetting. This contains:

Routers are ranked according to preference value, shortest AS-PATH, and closest NEXT-HOP router.

Back to Home