CS168 Computer Networking Notes

This note is based on slides and the textbook of UCB CS168 SP25. See the original course on https://sp25.cs168.io/.

§1 Layers of Internet

1.1 What is the Internet?

The Internet transfers data between computers.

The Internet:

• Is a federated system.
• Operates at enormous scale.
• Is constantly evolving.
• Has a tremendous range and diversity of users and devices.
• Operates asynchronously.
• Must handle failures at scale.

Protocol: A specification on how to communicate.

• Syntax: Format of messages.
• Semantics: What actions should I take in response to certain messages?

1.2 Layers of the Internet

Layer 1 - Physical: moving bits across space

Layer 2 - Link: create links in a local network

• Use physical technology to create a link between machines.
• Use links to connect all machines in a local area.
• Machines can exchange packets: A group of bits representing a message.

Layer 3 - Internet: connect local networks to form an Internet

• End hosts are the machines communicating over the Internet.
• Switches (aka routers) receive packets and forward them toward their destination.
• Modularity: In our design, we decomposed the system into layers of abstraction.
  • Each layer relies on services from the layer below.
  • Each layer provides services to the layer above.
• Layer 3 offers a best-effort service model.
  • Packets are limited in size.
  • Packets could get lost, reordered, corrupted, etc.
  • The network will try its best to deliver your packet, but no guarantee.
  • The network won’t tell you if the delivery failed.

Layer 4 - Transport: reliably deliver packets, forming connections

• Adds extra mechanisms (e.g. re-sending lost packets) for reliable packet delivery.
• Splits up large data into packets to send them. Reassembles received packets.
• Instead of individual packets, can think about flows (aka connections): A stream of packets exchanged between two endpoints.

Layer 7 - Application: Implement services on top of the Internet infrastructure.

1.3 Header

The packet header contains metadata describing how the data should be sent.

• Destination address: Required to deliver the packet.
• Source address: Useful if the recipient wants to send replies back.

The actual data in the packet is called the payload.

• Headers are added as the packet moves down the stack, and unwrapped as the packet moves up the stack.
• Hosts parse headers for Layers 1–7.
  Routers parse headers for Layers 1–3.

§2 Architecting the Internet

2.1 Internet Design Principle

Architecting the Internet

The Internet Design Principles:

1. Decentralized control

   Each network device (e.g. router) runs on its own. No central mastermind.

2. Best-effort service model

   At Layer 3, routers only offer best-effort delivery.

3. Route around trouble

   • Network must be resilient to failures.
   • If a router or link goes down, find a different path through the network.

4. Dumb infrastructure (with smart endpoints)

   Routers forward packets. They don’t care about what’s inside.

5. End-to-end principle

   Implement features at the end hosts, not at the routers.

6. Layering

   • Each layer relies on the layer below, and supports the layer above.
   • Allows us to innovate at one layer, without disturbing other layers.
   • Different communities can work on different layers.
     • Chip designers at Layers 1 and 2.
     • Application developers at Layer 7.

7. Federation via narrow-waist interface

   Federation works because all operators speak the same Layer 3 protocol.

Narrow Waist, Demultiplexing

Narrow waist: IP (Internet Protocol) is the only protocol at Layer 3.

• All hosts and routers understand IP.
• This unifies the Internet and enables federation.

Demultiplexing:

• Add a new header field that tells us what the next (higher) layer protocol is.
• Allows the IP code to pass the rest of the packet to the appropriate L4 code.
• Port numbers help us distinguish between applications on the same computer. Both end hosts in a connection have a port number.

End-to-End Principle

End-to-end principle: Certain application features (e.g. reliability) must be implemented at the end host for correctness.

2.2 Designing Resource Sharing

Statistical Multiplexing

Two ways to allocate resources to users:

• Static allocation: Give a fixed amount to each user.
• Statistical multiplexing: Dynamically allocate to users based on their demand.

Statistical multiplexing (dynamic) is more efficient than static allocation (fixed).

• Fixed: You have to give everyone enough for their peak demand.
• Dynamic: Give a user more when their demand peaks.

Circuit Switching VS Packet Switching

There are 2 canonical designs for implementing statistical multiplexing:

• Reservations via circuit switching:
  • At start of connection, end-hosts explicitly request and reserve resources.
  • During connection, use the reserved resources to send packets.
  • At end of connection, release resources.
• Best-effort via packet switching:
  • Just use the resources (send packets) and hope for the best.

Circuit switching pros:

• Reservations give applications better performance.
• Reservations are more predictable and understandable.

Packet switching pros: more efficient on bursty flows

• More efficient.
• Faster startup to first packet delivered.
• Easier recovery from failure.
• Simpler implementation.

§3 Links

3.1 Bandwidth & Propagation Delay

Bandwidth: Number of bits sent/received per unit time.

• “Width” of the link.
• Measured in bits per second (bps).

Propagation delay: Time it takes a bit to travel along the link.

• “Length” of the link.
• Measured in seconds.

Bandwidth-delay product: Bandwidth × delay.

• “Capacity” of the link.

Packet Delay = Transmission Delay + Propagation Delay

Packet Delay = (Packet Size / Bandwidth) + Propagation Delay

3.2 Pipe Diagrams

The pipe diagram is an alternate view of the link.

Pipe diagram shows the bits on the link at a frozen moment in time.

• Height = bandwidth. How many bits we can put in the pipe per unit time.
• Width = propagation delay. How long it takes for bits to travel through the pipe.
• Area = bandwidth-delay product. How many bits fit in the pipe at a given instant.

3.3 Overloaded Links

What happens if two packets arrive at the router simultaneously?

Transient overload: When there are no incoming packets, router can drain the queue.

Persistent overload: When not enough capacity to handle the incoming packets, operators can detect the overload and (manually) upgrade the link. Routers can tell the senders to slow down.

In this way, Packet Delay = Transmission Delay + Propagation Delay + Queuing Delay

§4 Routing Principles

4.1 Defining the Routing Problem

Routing: Finding paths through the network.

Router: An intermediate machine that can forward data.

• Pros: use fewer links than the full-mesh topology; have more capacity than just a single link; if a link goes down, traffic could use another path.
• Cons: less bandwidth.

Packet: The basic unit of data sent across the network.

• Packets have a header with metadata.
• Packets have a payload with the application data.

Routing is hard because:

• topology changes over time
• routers don’t have a global view of the network
• links are best-effort

Intra-domain routing protocols compute routes within a single network.

• Each network can choose their own intra-domain protocol based on their needs

Inter-domain routing protocols compute routes between networks.

• Everybody has to agree on the same protocol.

Classifying routing protocols by where they operate:

• Let individual networks choose how to route inside their network. (Intra-domain.)

• Have all networks agree on how to route between each other. (Inter-domain.)

4.2 Routing States

Destination-based forwarding: used by the Internet for routing decisions

• Each router keeps a table, mapping destinations to next hops.
• The decision only depends on the destination field of the packet.

Forwarding VS Routing

• Forwarding:

  • Look up packet’s destination in table, and send packet to neighbor.

  • Inherently local. Depends only on arriving packet and local table.

  • Occurs every time a packet arrives

• Routing:

  • Communicates with other routers to determine how to populate tables.

  • Inherently global. Must know about all destinations, not just local ones.

  • Occurs every time the network changes

A routing state is valid if packets actually reach their destinations. In this way, we can only tell whether a global routing state is valid or not.

A global routing state is valid if and only if there are no dead ends and no loops.

• Dead end: A packet arrives at a router, but there is no next hop to forward it.

• Loop: A packet cycles around the same set of routers.

A directed delivery tree shows how packets get forwarded toward one destination.

A valid directed delivery tree is an oriented spanning tree rooted at the destination.

Steps to verify routing state validity:

1. Pick a single destination.
2. For each router, draw an arrow to the next-hop.
3. Delete all links with no arrows.
4. State is valid if and only if the remaining graph is a valid directed delivery tree.
5. Repeat for every destination.

Least-cost routing: Assign costs to every edge, and find paths with lowest cost.

• Costs are local to a router. Each router knows the cost of its own links. In practice, generally configured by an operator.
• Costs are always positive integers.
• Costs are always symmetrical.

Static routes are hard-coded entries that we always want to be there.

The route is static because:

• It never changes.

• No routing protocol used to discover it.