EPFL recap : Computer Networks

22 December 2013

Everything we learned in Computer Networks put together as we follow every byte of data on its journey through the network.

Scenario

You connect your computer to Ethernet and want to browse http://google.com.

Flowchart

Step 0 : Hosts, Switches and Routers.

To begin this we first have to understand how hosts, routers and switches handle packets.

a. Hosts and Routers

Hosts and Routers are both defined by link-layer addresses, called MAC addresses, besides their network-layer addresses, namely their IP addresses.

The behavior of hosts and routers upon receiving a frame is simple :

  • If the source MAC address of the frame does not match theirs, they ignore it.
  • If there is a match, they decapsulate the IP datagram and process it.

Therefore routers, as opposed to switches, forward packets using there IP addresses. When recievng a frame addressed to their MAC address they

  1. extract the IP datagram containing the destination IP address
  2. uses its forwarding table to find the correct interface to pass it to
  3. encapsulates the IP datagram inside a link-layer frame this time whith the destiantion MAC address of the destination IP (which it got using the Address Resolution Protocol)

Careful : Do not mix the forwarding table and the ARP table, both inside a router.

  1. The forwarding table matches IP addresses to interfaces.
  2. The ARP table matches IP addresses to MAC addresses.

b. Switches

The role of switches is to receive incoming link-layer frames and forward them onto outgoing links. This is done using the link-layer addresses. As for routers, the switch uses a forwarding table, which will automatically be populated over time using self-learning, to send the frame to the right interface.

The forwarding table inside a switch matches MAC addresses to interfaces.

Step 1 : Connect physically

You plug an ethernet cable into your computer. Suppose your MAC address is YOUR_MAC

Step 2 : Obtain an IP address

a. DHCP Discovery

We create a DHCP discovery message which we broadcast through the Network since we don't know the IP address of the DHCP server.

Encapsulation :

We create a UDP segment containing source port and destination port.

Src port Dst port Payload
68 67 DHCPDISCOVER

This segment will be encapsulated inside an IP datagram with source IP and destination IP. Since both are unknown we use the unknown 0.0.0.0 and the broadcast IP 255.255.255.255.

Src IP Dst IP Data
0.0.0.0 255.255.255.255 UDP segment

It will then be encapsulated inside an Ethernet frame with it's own MAC address and the broadcast MAC address FF:FF:FF:FF:FF.

Src MAC Dst MAC Data
YOUR_MAC FF:FF:FF:FF:FF IP datagram

b. Switch Broadcast

The frame will reach your switch. Since switches use MAC addresses to forward frames it will send the frame to all interfaces since the Dst MAC is FF:FF:FF:FF:FF. This is the first time the switch gets a frame with your YOUR_MAC address and therefore will save it along with your interface in its forwarding table.

c. Router Broadcast

The first-hop router connected to the previous switch (or maybe alot more) receives the frame and decapsulates the Link headers since its MAC address matches with the source broadcast address (which matches everything). We will assume that the DHCP server is running inside the router as is ofter the case.

Note : The DHCP server can not be outside the subnet or else the frame will have to pass through a router, in which case the source MAC address of the newly forwarded frames will be the one of the router and therefore all info about your computer will be lost.

d. DHCP offer

While all hosts receiving this frame will ignore it, the DHCP server will react to it by offering an IP address to your computer. Since you don't have one yet, it again uses the broadcast IP address 255.255.255.255. But it now knows your link layer MAC addresses.

Note : Packets will be simplified from now on.

The new packet looks like this :

Src MAC Dst MAC Src IP : port Dst IP : port Payload
DHCP_MAC YOUR_MAC DHCP_IP:67 255.255.255.255:68 DHCPOFFER

The switch will again receive the frame and now forward it directly to you as it previously recorded your MAC address. This time the switch will learn the routers MAC address.

Note : Since the router decapsulates the frame, doesn't your source MAC address get lost?

e. DHCP request

Now that you were offered an IP address you have to request (accept) this IP. So you sent a DHCP request, this time the destination MAC address will be the one of the DHCP interface of the router.

Src MAC Dst MAC Src IP : port Dst IP : port Payload
YOUR_MAC DHCP_MAC 0.0.0.0:68 255.255.255.255:67 DHCPREQUEST

Note : Why is the DHCP_MAC known but the IP address not? (see page 374)

Now the switch knows the according interface and will forward it directly.

f. DHCP ACK

When the DHCP receives the request it still has to acknowledge it.

Src MAC Dst MAC Src IP : port Dst IP : port Payload
DHCP_MAC YOUR_MAC DHCP_IP:67 255.255.255.255:68 DHCPACK

This last payload contains very essentials information about the network :

  1. Your IP address
  2. The subnet mask
  3. The default gateway router IP address
  4. The local DNS server IP address

Step 3 : Obtaining the Gateway MAC address

Now everytime we want to send a frame outside of our subnet we need to address it to the gateway router's MAC address or else it will be ignored. We therefore need to resolve its IP address we recieved in the step before to its MAC address.

For this task we will use ARP : Address Resolution Protocol. The idea is simple : we broadcast a message saying "Who has this IP ?" and wait for a response saying "I do!".

Src MAC Dst MAC Src IP : port Dst IP : port Payload
YOUR_MAC FF:FF:FF:FF:FF YOUR_IP:xx ip:yy Who has this ip ?

We will then receive a response message from the router with its MAC address in the frame :

Src MAC Dst MAC Src IP : port Dst IP : port Payload
GATEWAY_MAC YOUR_MAC YOUR_IP:xx ip:yy I do !

ARP is heavily used by hosts and routers of a network which need to know the MAC address of there destiantion.

Now we can send where ever we want. Using the subnet mask received in step 2 we can determine if our destination IP address is inside the subnet or not.

  • If it is, we use ARP to get its MAC address to send him the frame
  • If not we send it to the gateway router with his MAC address

Step 4 : DNS request for google.com

Now we want to get the IP address for www.google.com. This means we have to send a DNS request to our local DNS server and let him handle the rest (which might be recursive queries or iterative queries through the DNS hierarchy).

Let's consider two cases :

a. Local DNS inside our subnet

If the local DNS server is inside our subnet (which our computer figures out uisng the subnet mask), we need its MAC address. This is once again done using ARP.

Once that is completed we create a UDP segment with our DNS request, encapsulate it inside a IP datagram with our IP address and the local DNS IP address. Then we send it to our link-layer interface (here ethernet) were the frame headers with the MAC addresses will be added to the datagram :

Src MAC Dst MAC Src IP : port Dst IP : port Payload
YOUR_MAC DNS_MAC YOUR_IP:xx DNS_IP:53 DNS www.google.com

b. Local DNS outside our subnet

As seen before, if the local DNS is outside our subnet we need to send the frame through the default gateway router of our subnet. Luckily we recieved its MAC address in the step before.

Src MAC Dst MAC Src IP : port Dst IP : port Payload
YOUR_MAC GATEWAY_MAC YOUR_IP:xx DNS_IP:53 DNS www.google.com

The gateway router will decapsulate it and pass it along to one of its other interfaces connected to the right subnet using its forwarding table. Note here that this forawrding-table was populated using a intra-domain routing algorithm like Distance-Vector or Link-State, and a the inter-domain routing algorithm that is BGP (Border Gateway Protocol).

Now the router either has the MAC address for DNS_IP in his forawring ARP table or he uses ARP to get it. Either way the final frame sent to the local DNS server will be :

Src MAC Dst MAC Src IP : port Dst IP : port Payload
GATEWAY_MAC DNS_MAC YOUR_IP:xx DNS_IP:53 DNS www.google.com

Note : The local DNS server could be in even another subnet, in which case our gateway router was to send the frame to another gateway router connected to the right subet, with is again chosen using his forwarding table thanks to BGP.

Step 5 : Receiving the DNS response

Eventually the IP datagram arrives at the local DNS server. This one may or may not have to ask other DNS servers (starting with the root DNS, then Top Level Domain and finally the Authoritative servers) depending on his cache. These details are ommitted here.

The DNS server will decapsulate the UCP segment and translate www.google.com into its IP address using the DNS resource records inside his DNS database. Now this mapping will be encapsulated into yet another UDP segment, and sent all the way back to you.

Src MAC Dst MAC Src IP : port Dst IP : port Payload
DNS_MAC GATEWAY_MAC DNS_IP:53 YOUR_IP:xx GOOGLE_IP

Now you finally know the IP address of google.com

Step 6 : TCP Connection setup

Now we are ready to setup a TCP connection with Google.com using the TCP three-way-handshake.

a. SYN message

To establish a connection we first have to create a TCP socket on our side, let's say on port yy.

Then we send a TCP SYN message through that newly created socekt to the welcoming HTTP port 80. This connection-establishement request has a the SYN flag set to 1.

Since the server is outside our subnet the frame header will contain the gatway router's MAC address.

Src MAC Dst MAC Src IP : port Dst IP : port Payload
YOUR_MAC GATEWAY_MAC YOUR_IP:yy GOOGLE_IP:80 SYN=1, SEQ=4321

This frame will then be routed through the inter-domain links using the routers forwarding table (which were populated using GBP) all the way to the Google HTTP server.

b. SYNACK message

When the SYN message arrives at www.google.com it will be demultiplexed to the welcoming socekt listening on port 80, and a new TCP socket is created for the connection between us and the Google HTTP server at some port zz.

Then a SYNACK segment is sent back to our computer.

Src MAC Dst MAC Src IP : port Dst IP : port Payload
GOOGLE_MAC SOME_GATEWAY_MAC GOOGLE_IP:zz YOUR_IP:yy SYN=1, ACK= 4322, SEQ=1234

This SYNACK segment is again forwarded through the network back to our computer, where it will be demultiplexed to the socket created in the step before, which was still awaiting a connection-establishement acknowledgment.

Note here that this socket is in a special stage since normally sockets are identified by the four-tuple (source IP, source port, destiantion IP, destiantion port).

Note : We will ignore SYN cookies (necessary against SYN flooding).

c. ACK message

This final ACK message we send to the TCP socket at Google HTTP server dedicated to our connection could already contain some payload (like a HTTP GET request). For simplicity we will only send an ACK.

This time the segment is fully identified by (YOUR_IP, yy, GOOGLE_IP, zz).

Src MAC Dst MAC Src IP : port Dst IP : port Payload
YOUR_MAC GATEWAY_MAC YOUR_IP:yy GOOGLE_IP:zz SYN=0, ACK=1235

Step 7 : Make a HTTP request

a. HTTP request

Ok now that on both sides there is a TCP socket ready to handle requests, we can finally send the HTTP GET message with the URL to be fetched : http://www.google.com/.

This HTTP message is sent through our TCP socket and delivered to the socket at Google, following the same route as before :

Src MAC Dst MAC Src IP : port Dst IP : port Payload
YOUR_MAC GATEWAY_MAC YOUR_IP:yy GOOGLE_IP:zz HTTP/1.1
GET http://www.google.com/

b. HTTP reponse

Once the frame is decapsulated and the TCP segmemnt is demultiplexed to the TCP socket dedicated to our connection, the HTTP server will sent back a HTTP response message.

Src MAC Dst MAC Src IP : port Dst IP : port Payload
GOOGLE_MAC SOME_GATEWAY_MAC GOOGLE_IP:zz YOUR_IP:yy source code stuff

It is then forwarded through the network to our computer.

Step 8 : The End

And finally the part you have all been waiting for : the HTTP response arrives at our TCP socket and the browser extracts the html for the Webpage from the TCP segment payload and displays the page !