🌐 Computer Networking
Last modified on April 07, 2022

Datagrams (specific kinds of packets) contain the following elements:

• To address of a node (fully specified)
  
• text (~1 KB)
  
• From address of a node (fully specified)
  

Every computer is given an address that’s 32 bits* long. This is known as its IP address.

IP addresses are a way to “multiplex” the scarce resource of the Internet – multiple machines can communicate over the Internet, because routers know how to deliver packets based on their destination address.

*Problem: only \(2^{32}\) = ~4 billion addresses in ipv4, which we have essentially run out of. Thus, ipv6 addresses were created that are 128 bits long.

E.g. the IP address 104.196.238.229 simply represents a 32-bit number, separated into each of its 4 bytes.

print('{0:b}'.format((104 << 24) + (196 << 16) + (238 << 8) + 229))

1101000110001001110111011100101

Here’s 127.0.0.1, aka localhost, in binary:

print('{0:b}'.format((127 << 24) + (0 << 16) + (0 << 8) + 1))

1111111000000000000000000000001

Routers forward packets one at a time. They look at IP addresses, and then send the packets to a router closer to the destination.

traceroute google.com

ping yuba.stanford.edu -t 10

TTL: time to live – how long the packet has to reach its destination. if it expires, look at the FROM address, and tell the sender

The Internet provides best-effort delivery of datagrams, up to ~1.5KB.

“best-effort” means the datagram might be:

• lost completely
  
• delivered more than once, out of order
  
• delivered with some bytes changed
  
• delivered but truncated.
  

Users want reliability – reliable retrieval of data, reliable action, reliable byte stream, reliable delivery of a large file, reliable remote procedure call

A module behaves reliably when it:

• Provides some abstraction/interface
  
• Even in the face of underlying faults
  
• When it can’t do that, it signals failure
  

We want to do idempotent operations; i.e. operations that have the same effect in the world, even if called multiple times / out of order.

TCP in a nutshell:
Byte stream 0..2 is “A B C”.
Byte stream 4..6 is “E F G”.
“The next byte of the stream I need from you is #5”.
Byte stream ended at [index].

^idempotent operations.

In TCP, the two connectors to the byte stream are peers; they both can read/write from the bidirectional byte stream.

That said – there is a common pattern of usage of TCP, called the client-server model.

Client (Frankie):

TCPSocket sock;
sock.bind({"0", 3}); // this "binds" the socket to a local address: IP address and port number
sock.listen(); // "listen" for incoming connections on this socket

Server (Keith):

TCPSocket sock;
sock.connect( {"[frankie's remote IP address]", 3} ) //Connect to Frankie's IP address on port 3

This is known as the TCP 3-way handshake:

• sock.connect is where the first bytes get sent – Keith sends a TCP segment with SYN flag set 1 to start the server => client stream. This initiates the connection.
  
• Frankie responds to Keith with a SYN/ACK segment, simultaneously acknowledging Keith’s SYN bit and starting a client => server stream with the new SYN.
  
• Keith responds to Frankie’s SYN/ACK with another ACK (to acknowledge Frankie’s SYN.)
  

Note: Frankie can “accept” the connection:

TCPSocket sock_connected = sock.accept();

Note – this is not the only way a connection can be established! TCP’s rules are more general than that:

• Every stream sends: SYN, bytes, FIN
  
• Each byte, SYN, and FIN occupy 1 sequence number each
  
• Each segment that occupies a sequence number provokes an acknowledgment
  

This is fundamentally symmetrical: no reason why one peer has to initiate, and the other has to accept. Here’s a more symmetrical way of establishing connection:

• Peers both send SYN segments (initiating at the same time)
  
• Peers receive these SYN segments and send ACK segments
  

I.e.: If Frankie and Keith are both bound to a port number, and they both want to connect to each other at the same time, they can both call connect on each others’ IP address + port. Calling connect results in a SYN flag being sent

Could consider this “4-way handshake”: SYN, SYN, ACK, ACK. 99% of connections do 3-way handshake, but this is just because of the reality that the vast majority of connections on the Internet are between client and server.

• packet corruption – checksum ensures that the original data is intact.
  
• packet lost – TTL ensures that packets don’t wander/cycle for too long, and a timeout triggers the packet to be resent.
  
• packet arrives more than once / out of order – idempotence is ensured through the way that TCP keeps track of seqnos of received data, and signals for the next sequence number using the ackno.
  

A DNS request is a request for a hostname-to-IP address mapping. E.g., “tell me the IP address for tiktok.com.”

A client sends a DNS request to a DNS server – client has a list of DNS server addresses in `etc/resolve.conf`.

The DNS request is encapsulated in a user datagram, which is in turn encapsulated in an IP (Internet) datagram. It’s often said “DNS runs over UDP” – this means that DNS uses UDP as its transport protocol.

DNS hierarchy has a single domain at the top of the structure: the root domain (.)

Below this are the top-level domains (TLD): .com, .edu, .gov, .mil, .org, .net, .int.

Domains under the TLDs represent individual organizations or entities, e.g. Stanford (stanford.edu.) Certain organizations have domain delegation, which means that their network admin maintains the DNS database for that domain.

Can lookup the domain name through a recursive process, descending down the DNS hierarchy.

• First, we asked the root name server for “puffer.stanford.edu.”
  
  • The root name server said, “we don’t know anything about ”puffer.stanford.edu.“, but we do know the IP addresses of the name servers that have information about names with ”.edu“ suffixes
    
• Then, we asked one of those “.edu” servers for the IP address of “puffer.stanford.edu.”
  
  • This server said, “we don’t know anything about ”puffer.stanford.edu.“, but we do know the IP addresses of the servers that have information about names with ”stanford.edu“ suffixes
    
• So, we asked one of those servers, and we got the IP address of “puffer.stanford.edu.”
  

That said – that’s probably not what your computer does. DNS lookup tables are cached at many levels (even on the computer itself.)

Ask the root name server for puffer.stanford.edu. DNS servers cache things.

Person 1                               Person 3
        \                             /
        [Palo Alto] --------- [Austin]
        /                             \
Person 2                               Person 4

If too many people are on the “trunk” connection, it says the line is full.

Bad: this kind of network is locking us into one paradigm – phone calls. Also, other kinds of communications (e.g. email) don’t need to use the connection for long periods of time. This is inefficient.

Routers just handle packets. They don’t need circuits, reservations, permissions, etc. Don’t know anything about the contents of the packets – just datagrams being passed along.

Phone calls can happen over the internet – just packets flying around. Voice ove Internet Protocol (VoIP).

Question: is there historical similarity between the phone networks and computer networks?

We want this infrastructure to constantly be in use. This necessitates a “queue” of packets waiting to be sent.

A
 \
  [Router]
 /
B

A link is a connection between two nodes on the internet.

serialization delay = packet size [bits] / serialization rate [bits / sec] = x seconds

\(\text{delay}_{\text{serialization}} = \frac{p}{r_i}\)

q: does serialization / deserialization happen at every node?

propagation delay = link length [m] / propagation rate [m / sec] = x seconds

\(\text{delay}_{\text{progagation}} = \frac{l_i}{c}\)

Links are FIFO - first-come, first-serve. Packets that aren’t ready to be sent have to wait a bit.

This is the one that can be variable – sometimes the networks are busy, and your packet has to wait in line.
\(\text{delay}_{\text{queueing}} = Q_i(t)\)

Sum the serialization + propagation + queueing delays at each link \(i\).

\(\text{delay}_{\text{end-to-end}} = \sum_i (\frac{p}{r_i} + \frac{l_i}{c} + Q_i(t))\)

This is pretty cool.

Q(t): how many in queue
A(t): how many have arrived
D(t): how many have departed

Q(t) = A(t) - D(t)

Packets with certain “flows” are considered higher priority than others.

Solution: have several queues of packets. “High priority” and “low priority.”

Strict priority: always prefer high priority queue
Fair queueing: Packets are sent in the order they would complete in the bit-by-bit scheme.
Most it can be wrong: max length of packet * the rate.

TCP provides a flow-controlled bidirectional byte stream. Each sender respects its receiver’s capacity. BUT - this doesn’t take into account the network’s capacity.

Here’s a simplified diagram of the TCP infrastructure:

              [     ]
TCP Sender => [Queue] [    Link    ] => TCP Receiver
              [     ]

From sender’s POV, 3 places packets can be:

1. In the queue
   
2. On the link
   
3. “outstanding” – Got to the receiver, but don’t know yet (ack hasn’t come back)
   

The receiver’s window size caps the number of “outstanding” bytes (send but not acked, or judged lost.)

What if the receiver has a window size of 1? throughput = 1 byte / round trip time (RTT). Really slow.
What if the receiver has a larger window size? better. window keeps shifting forward as more ackno’s are received. not limited by window size, but by the link speed.

Bad scenario: slow link from sender to receiver, fast link from receiver to sender, receiver says it has a large window size. The sender will blindly send a bunch of packets, ignoring the fact that the queue will fill up.

bad because the queue fills up – it’s wasteful to send a bit that will later be dropped. (plus if the queue is full no one else can send to the link) => forcing routers to drop lots of packets, lead to congestion collapse. Lots of demand on the system, but it’s not doing useful work.

One way to control congestion: a second window, in addition to the receiver’s advertised window. Sender respects two windows: receiver window, and “congestion window” cwnd. So…how large should the congestion window be??

Routers look at IP addresses, and send the packet to a router closer to its destination.

The network topology is super complex. Trees can fall on power lines. Etc.

Three ways:

Recap: packet switch is a generic term for anything that forwards packets hop-by-hop. An Ethernet switch is a different kind of packet switch.

=> [ Lookup address ][ Update Header ] [ Queue Packet ]=>
     ^
     |
     v
   [Forwarding Table]

1. Examine header of each arriving frame.
   
2. If the Ethernet Destination Address (aka MAC address) is in the forwarding table, forward the frame to the correct output port(s).
   
3. if the Ethernet Destination Address is not in the table, broadcast the frame to all ports (except the one through which the frame arrived.) i.e. flooding.
   
4. Entries in the table are learned by checking to see if the Ethernet Source Address of arriving packets are already in the table. If not, add them.
   

Ethernet learns a spanning tree of the entire network.

1. If the Ethernet DA of the arriving frame belongs to the router, accept the frame. else drop.
   
2. Examine the IP version number + length of datagram.
   
3. Decrement TTL, update IP header checksum.
   
4. Check TTL == 0.
   
5. If the IP DA is in the forwarding table, forward to the next hop.
   
6. Else: If there is a Default Route entry, forward it there, otherwise drop + send ICMP message back to source.
   
7. Find Ethernet DA for the next hop router
   
8. Create new Ethernet frame + send.
   

1. Preamble:
   
2. Start of Frame Delimiter:
   
3. Destination Address:
   
4. Type:
   
5. Pad:
   
6. Cyclic Redundancy Check:
   

Ethernet is, or at least was originally, an example of multiple hosts sharing a common cable “medium”. With lots of people trying to talk, we need a protocol so things don’t get garbled. More concretely, we need to decide who gets to send, and when.

Specific protocol…

(note: historical - Ethernet doesn’t use this anymore b/c we have ethernet switches – but wireless protocols are pretty similar to this!)

When a host has a packet to transmit:

1. Carrier Sense: Check if the line is quiet
   
2. Collision detection: Detect collision as soon as possible. If a collision is detected, stop transmitting; wait a random time (but an exponentially-backing-off random time), then return to step 1.
   (Real life analogy: Sometimes both people start talking at the same time, then go quiet, then both start speaking…if you stagger the re-speaking, there’s less likely to be collision.)
   

[TCP/IP] computer--\                /--router - Google (e.g.)
                    \              /
                    modem ---- modem

We have a pair of socket connected to each other. Sending each other internet datagrams directly.

Socket addresses on home computer
local: 18.241.0.5:53050
peer: 172.217.0.36:50

Socket addresses at Google:
local: 172.217.0.36:50
peer: 18.241.0.5:53050

Totally fine to reuse the same local address, as long as each socket is connected to a different peer address.

Problem:

Now, the computers and modems talk with Ethernet – this means it’s faster, but also…

[TCP/IP/ computer--\                /--router - (...) -Google (e.g.)
Ethernet]           \              /
         [Ethernet] modem ---- modem

Benefit of Ethernet network: multiple computers can connect to the modem.

…it allows us to connect multiple computers to a modem, given an Ethernet switch.

[TCP/IP/ computer--\                /--router - (...) -Google (e.g.)
 Ethernet]     [switch]           |
              /  |                |
      computer    \               |
                   \              /
         [Ethernet] modem ---- modem

Same thing, but the switch became wireless.

[TCP/IP/ computer--\               /--router - (...) -Google (e.g.)
 Ethernet]     [WiFI AP]          |
              /  |                |
      computer    \               |
                   \              /
         [Ethernet] modem ---- modem

Problem: as it stands, ISP has to keep track of all these different computers on their router…

Solution: have a home network that hinges on a home router. Thus, rather than remembering each individual device, the ISP’s router just needs to know which part of the IP hierarchy corresponds to which home router.

[TCP/IP/ computer--\                /--router - (...) -Google (e.g.)
 Ethernet]     [Wi-Fi AP]           |
                   \                |
                   [router]         |
                     \              /
         [Ethernet] modem ---- modem

what’s the difference between a modem and a router? Modem doesn’t know anything about IP: it just translates Ethernet frames to and from electrical signals that can be sent over long distances. Router is thinking about IP, and, well, routing.

So…this is a good system, and this is basically how it works: for IPv6! But the huge problem with IPv4 is that we don’t have enough IP addresses to go around. And, as it stands, the world practically runs on IPv4. So…how can we distinguish computers in a home network, without requiring a unique IP for each device?

Here’s one potential solution: having one single computer that acts as as a proxy for all the home devices. This proxy will make all the TCP connections for us, and it routes stuff to the individual devices using ports.

[TCP/IP/ computer--\                 /--router - (...) -Google (e.g.)
 Ethernet]     [Wi-Fi AP]            |
                   \                 |
                   [TCP proxy]       |
                    \                |
                   [router]          |
                     \              /
         [Ethernet] modem ---- modem

Problem: it’s annoying to have to manually configure every device to use that specific proxy….

Solution: Make TCP proxy “transparent” / “pretend” to be Google. The proxy acts as a middleman.

[TCP/IP/ computer--\                /--router - (...) -Google (e.g.)
 Ethernet]     [Wi-Fi AP]
                   \
                   [TCP proxy]
                    \
                   [router]
                     \              /
         [Ethernet] modem ---- modem

Sidenote: Oftentimes, Wi-Fi AP, TCP proxy, router, and modem all in one box.

Problem: TCP proxy is burdened with doing non-lightweight TCP stuff, like reassembling byte streams, retransmitting, etc. We wanted the proxy just for its port numbers, not for it to do all the heavy lifting! So, now, moving on to Level 8…

NA(P)T doesn’t know most of TCP (e.g. reassembling byte stream, ACKs, retransmits) – just translates addresses inside TCP segments between local <=> Google.

[TCP/IP/ computer--\                /--router - (...) -Google (e.g.)
 Ethernet]     [Wi-Fi AP]           | [DHCP]
                   \                |
                   [NAPT] [DHCP]    |
                    \               |
                   [router]         |
                     \              /
         [Ethernet] modem ---- modem

NAT mapping: (local, peer) internal <=> (local, peer) external.

When is a NAT mapping created? When the local peer initiates the connection (sends SYN.)
Why does it map when local initiates, and not remote? When SYN sent from local, it’s fine (many-to-one) but ambiguous when remote sends SYN (Since there are many local devices, and “one” remote device.)
When is a NAT mapping deleted? NAT mapping deleted when we have a TCP clean shutdown.
NATs can have wildcards: mapping a hierarchy of IP addressses to a remote.
Note: NAT is not a security feature, not a firewall etc.

encrypt(counter, key, plaintext) => ciphertext + tag

counter: number that never repeats
key: random 256-bit number
plaintext: any bytes

ciphertext: same length as plaintext (but gibberish)
tag: short (256-bit authenticator that proves the message is legit)

Key idea: two parties that have nothing to do with each other can agree on a random key.

Useful because we want to connect securely to “strangers” (e.g. buying something on Amazon) all the time.

Each person has a public key and a private key that are mathematically related to each other (take an encryption class.) They announce their public keys to the world, and they can send each other a message that only the other can read since they encrypt it using the peer’s public key, and the peer has the corresponding private key.

There are organizations that “certify” that a certain public key really belongs to a certain entity. Then the key gets “signed” by that authority.