Introduction

What is the Internet?

Different Views of Internet

“Nuts and Bolts” View

• Billions of connected computing devices
  • Hosts = end systems
  • Run network applications at the Internet’s edge
• Packet switches
  • Forward packets (chunks of data)
  • Routers, switches
• Communication links
  • Fiber, copper, radio, satellite
  • Transmission rate = bandwidth (bps)
• Networks
  • Collection of devices, routers, links
  • Managed by an organization

“Services” View

• Infrastructure that provides transport services to applications:
  • Web, email, streaming video, VoIP, games, e-commerce, social media
• Provides hooks (APIs) for applications to send/receive data

Internet as a Network of Networks

• Hosts connect to the Internet via access networks
• Access networks must be interconnected
  • So any two hosts (anywhere) can communicate
• Resulting network of networks is complex
  • Structure driven by economics and national policies

Internet Structure

Network Edge

• Hosts: clients and servers
• Servers often located in data centres

Access Networks

• Residential access networks
• Institutional access networks (schools, companies)
• Mobile access networks (WiFi, 4G/5G)

Network Core

• Interconnected routers
• Responsible for forwarding packets across the Internet

Scaling Problem: Directly connecting every access network to every other access network requires O(\(N^2\)) links. A hierarchical structure is required to make the Internet scalable.

Global Transit ISPs

• Access networks connect to a global transit ISP.
  • ISP: Internet Service Provider
• Transit service means the ISP carries traffic to and from any destination on the Internet.
• Relationship between access network and ISP is customer–provider, based on payment.

Multiple Global ISPs

• If a single global ISP is profitable, competitors will emerge.
• Multiple global ISPs must interconnect to ensure global reachability.
• Without interconnection, parts of the Internet would be unreachable.

Internet Exchange Points (IXPs)

• Physical infrastructure where ISPs interconnect.
• Enable peering, which is direct traffic exchange between networks.
• Peering reduces reliance on paid transit.
• Improves performance by shortening paths and reducing latency.

Regional ISPs

• Serve as intermediaries between access networks and global ISPs.
• Aggregate traffic from many access networks.
• Reduce cost and improve scalability.
• Access networks may connect to multiple regional ISPs for redundancy.

Content Provider Networks

• Large content providers operate their own private networks.
• Connect data centres directly to ISPs and IXPs.
• Bring content closer to users to reduce latency and improve performance.
• Often bypass traditional tier-1 and regional ISPs

Internet Core Summary

• At the centre of the Internet is a small number of highly connected networks.
• Includes:
  • Tier-1 ISPs with national and international coverage that do not purchase transit.
  • Content provider networks that directly interconnect with many ISPs.
• The Internet is not purely hierarchical; it combines hierarchy and peering.
• Structure continuously evolves due to economics, competition, and performance demands.

Packet switching

Different Views

Host View

• An application-layer message is divided into smaller packets.
• Each packet has length L bits.
• Packets are transmitted into the access network at rate R bps.
• Packetization enables efficient sharing of network resources.

Network View

• The network forwards packets from one router to the next.
• Each router receives a packet, determines the appropriate output link, and forwards it.
• No resources are reserved in advance.
• Packets may experience variable delay and may follow different paths.

Two Key Network-Core Functions

Forwarding

• Local action performed at each router.
• Moves an arriving packet from an input link to the correct output link.
  • Input link
    • The link on which a packet arrives at a router
    • Connects the previous node to this router
  • Output link
    • The link on which the packet leaves the router
    • Connects this router to the next node
• Uses a forwarding table.
  • Packet arrives on an input link
  • Router examines destination address in packet header
  • Router consults its forwarding table
  • Packet is sent on the appropriate output link
• Also called switching.
• Operates at very high speed for every packet.

Routing

• Global process that determines end-to-end paths.
• Uses routing algorithms and protocols.
• Computes paths based on network topology and policies.
• Populates forwarding tables used by routers.

Different Ways of Packet Switching

store-and-forward

packet transmission delay: takes L/R seconds to transmit (push out) L-bit packet into link at R bps

store and forward: entire package must arrive at router before it can be transmitted on next link

queueing

It occurs when work arrives faster than it can be serviced.

queueing and loss

Packet queuing and loss: if arrival rate (in bps) to link exceeds transmission rate (bps) of link for some period of time:

• packets will queue, waiting to be transmitted on output link
• packets can be dropped (lost) if memory (buffer) in router fills up

Circuit Switching

end-end resources allocated tom reserved for “call” between source and destination

circuit segment idle if not used by call (no sharing)

• Frequency Division Multiplexing (FDM): optical, electromagnetic frequencies divided into (narrow) frequency bands; each call allocated its own band, can transmit at max rate of that narrow band
• Time Division Multiplexing (TDM): time divided into slots; each call allocated periodic slot(s), can transmit at maximum rate of (wider) frequency band (only) during its time slot(s)

Comparison

Packet switching is great for bursty data, sometimes has data to send, but at other times not

• resource sharing
• simpler, no call setup

but excessive congestion is possible, like packet delay and loss due to buffer overflow. So protocols needed for reliable data transfer, congestion control

Performance: delay, loss, throughput

4 sources of packet delay

\(d_\text{nodal}\) = nodal processing, including check bit errors, determine output link, typically < microseconds

\(d_\text{queue}\) = queueing delay, including time waiting at output link for transmission, which depends on congestion level of router

\(d_{trans}\) = transmission delay

• L: packet length (bits)
• R: link transmission rate (bps)
• = L/R

\(d_\text{prop}\) = propagation delay

• d: length of physical link
• s: propagation speed (~\(2\times 10^8\) m/sec)
• = d/s

Packet queueing delay

Traffic intensity

\[ \frac{L \cdot a}{R}: \frac{\text{arrival rate of bits}}{\text{service rate of bits}} \]

where

• a: average packet arrival rate
• L: packet length (bits)
• R: link bandwidth (bit transmission rate)

if ~ 0: avg. queueing delay small

if = 1: avg. queueing delay large

if > 1: more “work” arriving is more than can be serviced - average delay infinite!

It has to be less than 1 to work!

traceroute program

Traceroute measures round-trip time (RTT) using probe packets.

For each hop along the path, traceroute sends 3 probe packets with the same TTL value. Each probe travels toward the destination until a router discards it (when TTL reaches zero) or the destination responds.

How TTL is set and used

• TTL (Time To Live) is a field in the IP header.
  • The IP header is the network-layer control information attached to every IP packet. It contains fields such as the source and destination IP addresses and TTL, which routers use to forward packets toward their destination and prevent infinite looping. Routers read the IP header to make forwarding decisions but do not inspect the application data inside the packet.
  • The IP header is added by the network layer at the sending host, and together with the payload (usually a TCP or UDP segment) forms an IP packet (IP datagram) that is forwarded hop-by-hop across the Internet.
• traceroute manually sets the TTL value of probe packets.
• TTL starts at 1 and is incremented by 1 for each hop:
  • TTL = 1 → reaches the first router
  • TTL = 2 → reaches the second router
  • TTL = 3 → reaches the third router
• Each router that forwards a packet decrements TTL by 1.
• When TTL reaches 0, the router:
  • Discards the packet
  • Sends an ICMP Time Exceeded message back to the source

RTT measurement

• The source records the time a probe is sent.
• The source records the time the ICMP reply is received.
• The difference is the RTT.

This is why traceroute output shows three RTT values per hop, one for each probe, and why traceroute can discover the sequence of routers along the path.

In traceroute output, * * * means that no reply was received for the probe packets sent to that hop within the timeout. This usually happens because the router blocks or rate-limits ICMP replies, or due to probe lost or router not replying, or due to temporary congestion. It does not necessarily mean the router or path is down, since later hops may still respond.

Packet loess

• queue (aka buffer) preceding link in buffer has finite capacity
• packet arriving to full queue dropped (aka lost)
• lost packet may be retransmitted by previous node, by source end system, or not at all

Throughput

• throughput: rate (bits/time unit) at which bits are being sent from sender to receiver
  • instantaneous: rate at given point in time
  • average: rate over longer period of time
    • "average throughput" does not refer to the mathematical average (mean) of the different link speeds. Instead, it refers to the sustained rate of data transfer observed over a period of time.
    • If you have a fast link (e.g., 100 Mbps) connected to a slow link (e.g., 1 Mbps), your transfer speed won't be the average of the two (50.5 Mbps). It will be 1 Mbps. The fast link spends most of its time waiting for the slow link, so your "average rate over time" effectively becomes the speed of the slowest part.

Throughput is the rate at which data is successfully transferred from a sender to a receiver. It is always limited by the slowest part of the path.

• Case 1 (Slow Sender): If the sender's link (\(R_s\)) is slower than the receiver's link (\(R_c\)), the average throughput is \(R_s\).
• Case 2 (Slow Receiver): If the sender's link (\(R_s\)) is faster than the receiver's link (\(R_c\)), the average throughput is \(R_c\).

The Bottleneck Link

• Definition: The Bottleneck Link is the specific link on the end-to-end path that constrains the total throughput.
• Analogy: It acts like the narrowest section of a pipe; no matter how wide the rest of the pipe is, water can only flow as fast as the narrowest point allows.

Complex Scenario: Shared Backbone

In a real network, multiple connections often share a single central link (backbone).

• Scenario: 10 connections are sharing a backbone link with capacity \(R\).
• Throughput Formula: The end-to-end throughput for a single connection is the minimum of three factors: \(\min(R_c, R_s, R/10)\)
  • \(R_c\): The Client's link speed.
  • \(R_s\): The Server's link speed.
  • \(R/10\): The connection's "fair share" of the backbone bandwidth.
• Real-world Observation: In practice, the backbone (\(R\)) is usually very fast. The bottleneck is typically found at the "edge" of the network (either the client's home wifi \(R_c\) or the server's upload link \(R_s\)) rather than in the core.

Protocol layers, service models

• Protocols define the format, order of messages sent and received among network entities, and actions taken on message transmission, receipt
  • controls sending, receiving of messages
  • e.g., HTTP (Web), streaming video, Skype, TCP, IP, WiFi, 4/5G, Ethernet
• Internet Standard
  • RFC: Request for Comments
  • IETF: Internet Engineering Task Force

Layered Internet protocol stack

The network is organized into a stack of five layers, each providing services to the layer above it.

• Application Layer: Source and destination applications exchange Messages (M) to implement an application service.
• Transport Layer: Transfers messages (process-to-process).
  • Header: since a computer can run many programs (processes) at once, an IP address isn't enough. You need a Port Number to specify which program (like a web browser vs. an email client) the data is for.
• Network Layer: Transfers segments (host-to-host).
  • Header: to find a computer across the entire global internet, you need a logical address that locates the machine in the network structure. That is the IP Address.
• Link Layer: Transfers datagrams (host-to-neighbor).
  • Header: this layer only cares about moving data to the next physical device connected by a wire or Wi-Fi. It uses the MAC Address (burnt into the network card) to identify that physical hardware on the local wire.
• Physical Layer: Transfers raw bits.

Host-to-Host (Network Layer)

• Definition: This means delivering data from one physical computer (Host A) to another physical computer (Host B) somewhere else on the internet.
• The Limit: The Network Layer (IP) only cares about getting the packet to the correct machine. It stops at the "front door" of the computer. It doesn't care which specific application inside that computer needs the data.
• Analogy: It is like the post office delivering a letter to "123 Main Street." They get it to the correct building, but they don't know which person inside the building the letter is for.

Process-to-Process (Transport Layer)

• Definition: This means delivering data from a specific running program (Process) on the sender to a specific running program (Process) on the receiver.
• The Job: Once the data arrives at the host, the Transport Layer takes over. It looks at the packet to decide, "Does this go to the Web Browser? Or the Email Client? Or the Game?"
• Analogy: This is like the mailroom clerk inside the building taking that letter from "123 Main Street" and handing it specifically to "Bob in Office 405."

Host-to-Neighbor (Link Layer)

• Definition: This means delivering data between two devices that are directly connected by a physical medium (like a wire or Wi-Fi).
• The Scope: The Link Layer only cares about moving the data to the very next device in the chain. It doesn't look at the final destination address; it just focuses on crossing the single wire to get to the next "hop" (like your computer sending a frame to your router).
• Analogy: This is like the mail truck driver who picks up the letter from your mailbox and drives it to the local sorting center. They don't fly the letter all the way to its final destination; their only job is to drive it safely to the next facility down the road.

Encapsulation

As data moves down the stack at the source, each layer wraps the data from the layer above inside its own envelope (Header + Data).

1. Transport Layer (Segment):
   • Takes the Application Message (M).
   • Encapsulates it with a Transport Header (\(H_t\)).
   • Result: Transport-layer Segment [\(H_t\) | M].
2. Network Layer (Datagram):
   • Takes the Transport Segment [\(H_t\) | M].
   • Encapsulates it with a Network Header (\(H_n\)).
   • Result: Network-layer Datagram [\(H_n\) | \(H_t\) | M].
3. Link Layer (Frame):
   • Takes the Network Datagram [\(H_n\) | \(H_t\) | M].
   • Encapsulates it with a Link Header (\(H_l\)).
   • Result: Link-layer Frame [\(H_l\) | \(H_n\) | \(H_t\) | M].

End-to-End View

• Source: Data goes DOWN the stack (Application \(\rightarrow\) Physical), getting wrapped at each step.
• Routers/Switches:
  • Switches: Only process up to the Link Layer (Physical \(\leftrightarrow\) Link).
  • Routers: Process up to the Network Layer (Physical \(\leftrightarrow\) Link \(\leftrightarrow\) Network) to make routing decisions, then send it back down.
• Destination: Data goes UP the stack (Physical \(\rightarrow\) Application), with each layer stripping off its corresponding header to reveal the data for the layer above.

Is there a switch between hops? Physically yes, but logically no.

• Physically: A switch sits between the source and the router to connect the cables.
• Logically (Hops): It does not count as a hop. A "hop" is a Network Layer (Layer 3) concept involving IP addresses. Since switches only read up to the Link Layer (Layer 2), they are invisible to the IP protocol, making the connection look like a direct line to the router.

A switch operates up to the Link Layer to facilitate local data delivery between directly connected devices, such as linking a source computer to a router. Unlike a router, it does not process the Network Layer or IP addresses; instead, it reads the Link Layer header (Hl) to forward frames to the correct physical neighbor. This makes the switch a transparent connector that moves data across the local physical medium without altering the higher-level logical path.

Terminology

RTT: Round Trip Time

TTL: Time To Live

ICMP: Internet Control Message Protocol