Chapter 1. Introduction

Internet

Network Edge: Hosts (主机) = End systems, e.g., phones, PC.

Normally, applications run only in network edge, rather than network core.

Network Core interconnects end systems, including:

  • Communication Links: Fiber, Copper, Radio, Satellite. Transmission rate: bandwidth (带宽).
  • Packet Switches: Routers (路由器), Switches (交换机).

Internet Service Provider (ISP, 互联网服务提供商): e.g., 中国电信, 中国移动.

Protocols (协议): HTTP (Web), streaming video, Skype, TCP/IP, WiFi, 4G, Ethernet.

  • Internet Standards:
    • RFC: Request for Comments
    • IETF: Internet Engineering Task Force

Layers & Protocols

Application: Supports network applications. e.g., FTP, SMTP, HTTP.

(Presentation): 允许应用程序解释数据的含义. e.g., Encryption, Compression, Machine-Specific Conventions.

(Session): 同步、检查点、数据交换恢复.

Transport: Provides process-to-process data transfer. e.g., TCP, UDP.

Network: Routes datagrams from source to destination. e.g., IP, Routing Protocols.

Link: Handles data transfer between neighboring network elements. e.g., Ethernet, 802.111 (WiFi), PPP.

Physical: Moves the individual bits within the frame from one node to the next. e.g., cables, switches.

Network Edge

Includes:

  • End systems (Hosts)
  • Clients (客户端): desktop, laptop
  • Servers: often in data centers

Two models:

  • Client/Server Model
  • Peer-Peer Model

Access Networks (接入网): The network that physically connects an end system to the first router (edge router).

  • Cable Network (有线电视网络): use TV’s. Cable Splitter (分线器, 区分电视信号和网络信号), Cable Modem (调制解调器, 转化为网络信号).
  • Digital Subscriber Line (DSL, 数字用户线路): use telephone’s. DSL Splitter, DSL Modem.
  • Wireless Access Networks:
    • Wireless LANs (无线局域网)
    • Wide-area wireless access (广域无线接入)
  • Enterprise Access Networks: Mix of wired, wireless link technologies, connecting a mix of switches and routers. e.g., Ethernet (以太网), WiFi.

Physical Media

Network Core

Forwarding & Routing:

  • Forwarding (转发): Data Plane. 路由器根据自己的转发表，决定把包扔给哪个端口。
  • Routing (路由): Control Plane. 路由协议在整个网络中收集信息，计算出最佳路径并发送给各个路由器。

Circuit Switching (电路交换):

  • Used by traditional telephone.

  • Mechanism: Reserve resources. 预留资源以保证速率。

    • Call setup is required to establish an end-to-end link. Resources are reserved for the duration of the communication.

  • Frequency Division Multiplexing (FDM, 频分复用)：把 400 Hz 的通道按频率分为 4 条 100 Hz 的通道，各自在自己的通道上说话。

    Time Division Multiplexing (TDM, 时分复用)：轮流周期性地使用整个通道说话。

电路交换中，如果电路段在某个时刻没有被使用，它将保持空闲，不会分配给其他通信。为处理突发性通信，现代网络多采用分组交换。

Packet Switching (分组交换):

  • Used by Internet.

  • Mechanism: Not reserve resources. 资源按需分配。

    • Hosts break long messages into packets. Packet forwarded independently. 排队存储转发。
    • Store-and-forward: 一个路由器必须完整地收到这一个包，检查无误后，才能把它发给下一个节点。
      • Transmission Delay: L/RL / R（包的大小 / 链路速度）
    • Each packet transmitted at full link capacity.

  • Pros:

    • Great for bursty data. 突发性数据。
    • Resources sharing. 资源共享。
    • Simpler, no call setup. 无需建立呼叫。

  • Cons:

    • Excessive congestion possible. 可能发生过度拥塞。
    • Causes packet delay and packet loss. 导致延迟、丢包。
    • Protocols needed for reliable data transfer and congestion control.

Performance Metrics

Delay, Packet Loss, Throughput

Delay

dnodal=dproc+dqueue+dtrans+dpropd_{\text{nodal}} = d_{\text{proc}} + d_{\text{queue}} + d_{\text{trans}} + d_{\text{prop}}

Processing Delay dprocd_{\text{proc}}:

  • check bit errors, and determine output link.
  • << msec (毫秒).

Queueing Delay dqueued_{\text{queue}}:

  • time waiting at output link.
  • depends on congestion level of router.

Transmission Delay dtransd_{\text{trans}}:

  • dtrans=L/Rd_{\text{trans}} = L / R, where LL is packet length (bits), and RR is transmission rate (bps).

Propagation Delay dpropd_{\text{prop}}:

  • dprop=d/sd_{\text{prop}} = d / s, where dd is length of physical link, and ss is propagation (传播) speed in medium (∼2×108\sim 2 \times 10^8 m/sec).

Sum-up:

  • 只有 Queueing Delay 延迟因数据包而异。

    Let aa be the average packet arrival rate (packets per sec):

    • La/R→0La / R \to 0, delay is low;
    • La/R→1La / R \to 1, delay is high;
    • La/R>1La / R > 1, delay is unlimited.

End-to-End delay:

  • Suppose dqueued_{\text{queue}} is negligible; N−1N - 1 routers between two hosts:

    dend-end=N(dproc+dtrans+dprop)d_{\text{end-end}} = N(d_{\text{proc}} + d_{\text{trans}} + d_{\text{prop}})

Packet Loss

Packet arriving to full queue (buffer) will be dropped (lost).

Throughput 吞吐量

Rate (bits / time unit) at which bits transferred between sender/receiver.

Bottleneck Link: Link with minimum transmission rate (RR) on end-end path constrains end-end throughput.

Network Security

Malware (恶意软件): Virus (requires user interaction), Worm (no user interaction required).

Denial of Service (DoS, 拒绝服务): 攻击者通过虚假流量淹没资源，使资源（服务器、带宽）无法用于合法流量

Packet Sniffing: 窃听

IP spoofing: 用虚假地址发包

Chapter 2. Application

Sockets (套接字): Interface between process and computer networks.

IP and Port Number

TCP UDP
Connection Connection-oriented Connectionless
Data Transfer Reliability Reliable transport: without error, in proper order, no duplicate bytes Unreliable data transfer
Congestion Control Throttles (限制) sender when network overloaded None

They do not provide Timing, Minimum Throughput Guarantee, Security.

UDP is commonly used in time-sensitive communications where occasionally dropping packets is better than waiting.

Web & HTTP

Round-Trip Time (RTT): Time for a small packet to travel from client to server and back.

Hypertext Transfer Protocol (HTTP):

  • Client/Server model using TCP.

  • Stateless: Server maintains no information about past client requests.

  • Connections:

    • Non-persistent HTTP (HTTP/1.0): At most one object sent over TCP connection. Requires 2 RTTs per object (1 for handshaking, 1 for request and response).
    • Persistent HTTP (HTTP/1.1): Multiple objects can be sent over single TCP connection.

  • Request Message Format:

    • GET: Request object.
    • POST: Input is uploaded in entity body (e.g., form submission).
    • HEAD: Asks server to leave requested object out of response (for testing).
    • PUT: (HTTP/1.1) Uploads file in entity body to path specified in URL field.
    • DELETE: (HTTP/1.1) Deletes file specified in the URL field.

  • Response Message Format:

    • 200 OK: Request succeeded, requested object later in this msg.
    • 301 Moved Permanently: Requested object moved, new location specified later in this msg.
    • 400 Bad Request: Server couldn’t understand msg.
    • 404 Not Found: Requested document not found on this server.
    • 505 HTTP Version Not Supported.

Cookies:

  • Solve the problem of HTTP being stateless.
  • 4 Components:
    1. Cookie header line of HTTP response message (Set-Cookie:).
    2. Cookie header line in next HTTP request message (Cookie:).
    3. Cookie file kept on the user’s host, managed by the browser.
    4. Back-end database at the Web server.
  • Workflow: Server sends Set-cookie: 1678 -> Client stores it -> Client sends Cookie: 1678 in later requests.

Web Caching (Proxy Server):

  • Goal: Don’t send object if cache has up-to-date cached version.
  • Conditional GET: Cache sends a GET request with an If-Modified-Since: <date> header. If the object has not been modified, the origin server returns 304 Not Modified with an empty body.

Electronic Mail

3 Major Components:

  • User Agents: “Mail reader” software like Outlook, etc.

  • Mail Servers: An always-on server, including Mailbox and Message Queue.

  • Simple Mail Transfer Protocol (SMTP): Uses TCP to reliably transfer email from client to server on port 25.

    It’s a push protocol; it cannot be used to pull mail!!!

    Sending server connects directly to receiving server.

    • Format:

      • Handshaking: Greeting (e.g., HELO, 220).
      • Transfer of messages: Sending the actual content.
      • Closure: Ending the connection (QUIT).

    • The entire msg must be in 7-bit ASCII.

Mail Access Protocols:

  • Post Office Protocol 3 (POP3):

    • Authorizes user and downloads all messages.
    • “Download and delete” mode is the default (deletes messages from the server). “Download and keep” is another option.
    • Stateless: Does not keep track of user state (e.g., read/unread) across sessions.

  • Internet Mail Access Protocol (IMAP):

    • Keeps all messages and allows users to organize messages in folders on the server.
    • Stateful: Synchronizes state (read/replied) across all devices.

  • HTTP: Used by web-based email clients (Gmail, Hotmail). The user agent is a web browser.

Domain Name System (DNS)

DNS:

  • Function: Translates hostnames to IP addresses. Runs on UDP port 53.
  • Architecture: A distributed, hierarchical (分层的) database.
    • Why not centralized? Single point of failure, traffic volume, distant database, maintenance nightmare. It doesn’t scale (扩展).
  • Hierarchy:
    • Root Name Servers.
    • TLD (Top-Level Domain) Servers: .com, .org, .edu, etc.
    • Authoritative DNS Servers: Hold the actual hostname to IP mapping records for an organization’s servers.
  • Local DNS Server: Not strictly part of hierarchy, provided by ISP. Acts as a proxy (caches).
  • Resolution Process:
    • Iterated Query (非递归查询): The contacted server replies with the name of the next server to contact (“I don’t know, but ask that guy”).
    • Recursive Query (递归查询): Puts the burden of name resolution on the contacted server (“Find this answer for me”).

Records & Caching:

  • Format: (name, value, type, ttl).
  • Common Types:
    • A: name = hostname, value = IP address.
    • NS: name = domain, value = hostname of Authoritative DNS Server (points to who knows the answer). e.g., (foo.com, dns.foo.com). Also a Type=A record is needed, providing the IP address of the Authoritative DNS Server.
    • CNAME: name = alias, value = canonical name (real name). e.g., (www.ibm.com, servereast.backup2.ibm.com).
    • MX: value = name of mail server. e.g., (@gmail.com, mail.google.com).
  • Caching: Once a server learns a mapping, it caches it. Entries disappear after TTL (Time To Live) expires.

Registration & Security:

  • Inserting Records: You need to provide names and IPs of your authoritative name server. DNS Registrar inserts Type=NS and Type=A records into the TLD server.
  • DDoS: Bombard root / TLD servers with traffic.
  • Redirect Attacks (Man-in-middle / Poisoning): Intercept queries or send bogus replies to redirect users to fake sites.

Peer-to-Peer (P2P) Applications

Architecture:

  • No always-on, central server. Arbitrary end systems (peers) communicate directly.
  • Self-scalability (自扩展性): New peers bring new service capacity.
  • Challenges: Intermittent connected, dynamic IP addresses.
  • Pros: Time is significantly less than Client/Server model for large N.

BitTorrent:

  • Chunks: File divided into 256Kb chunks.
  • Tit-for-tat (以牙还牙): You send chunks to peers who are sending chunks to you at highest rate (Top 4). Others are “choked”.
  • Optimistic Unchoking (乐观疏通): Randomly select a peer to send chunks to, hoping they become a top uploader.

Video Streaming

Dynamic Adaptive Streaming over HTTP (DASH):

  • Server: Divides video file into chunks encoded at different rates (quality levels, 高清, 标清, 流畅…).
    • Manifest File: provides URLs for different chunks encoded at
      different rates.
  • Client: Periodically measures server-to-client bandwidth and requests chunks one by one. Adaptive to network conditions.

Content Distribution Networks (CDNs)

CDN: Store copies of content at multiple sites.

  • Subscriber requests content from CDN.
    • Directed to nearby copy, retrieves content.
    • May choose different copy if network path congested.
  • Deployment Strategy:
    • Enter Deep (深入部署): Deploy server clusters deep into access ISPs (close to users).
    • Bring Home (本地部署): Deploy servers in IXPs (less maintenance).

Chapter 3. Transport

Network Layer: Logical communication between hosts.

Transport Layer: Logical communication between processes.

  • Relies on, enhances, network layer services.

Socket Programming

Socket: The “door” between the application process and the end-to-end transport protocol (TCP or UDP).

Socket Programming with UDP:

  • Type: SOCK_DGRAM (Datagram).
  • Characteristics:
    • Connectionless: No “handshaking” before sending data.
    • Unreliable: Data may be lost or arrive out-of-order.
  • Socket Identification: A UDP socket is identified by a 2-tuple: (Dest IP, Dest Port).
  • Key Functions (Python):
    • socket(AF_INET, SOCK_DGRAM): Create a UDP socket.
    • sendto(message, (IP, Port)): Send data (must attach address).
    • recvfrom(2048): Receive data and get sender’s address.

Socket Programming with TCP:

  • Type: SOCK_STREAM.

  • Characteristics:

    • Connection-oriented: Requires a 3-way handshake before data exchange.
    • Reliable: Delivers a “byte stream” (like a pipe).

  • Socket Identification: A TCP socket is identified by a 4-tuple: (Source IP, Source Port, Dest IP, Dest Port).

  • The “Two-Socket” Rule for Server:

    1. Welcoming Socket: Listens for incoming connection requests (e.g., the front desk).
    2. Connection Socket: A new socket created for each specific client after accept().

Multiplexing & Demultiplexing

Multiplexing (at sender): Gathering data from multiple sockets, enveloping data with header (later used for demultiplexing).

Demultiplexing (at receiver): Delivering received segments to the correct socket using header information.

  • Connectionless Demux (UDP): same Dest Port -> same socket.
  • Connection-oriented Demux (TCP): same Source & same Dest -> same socket.
    • Threaded Server: Modern servers create a new thread for each connection socket to handle multiple clients simultaneously.

User Datagram Protocol (UDP)

Format:

Checksum: 16 位回卷加法

  • Treat segment contents (including header and pseudo-header) as a sequence of 16-bit integers.
  • Sum them up (using 1’s complement sum).
  • Wrap-around: Any carry-out from the most significant bit is added to the result.
  • Take the 1’s complement (flip all 0s to 1s and 1s to 0s) to get the checksum.
  • Check: If the result is all 1s, no error detected.

Applications:

  • DNS: Needs speed, tiny messages.
  • Streaming Multimedia: Loss tolerant (it’s okay to miss a video frame), rate sensitive.
  • SNMP: Network management protocol.

Reliable Data Transfer (RDT)

RDT 1.0: Reliable Channel.

  • No control messages needed.

RDT 2.x: Channel with Bit Errors.

  • RDT 2.0:

    • Checksum: To detect errors.
    • ACK (Acknowledgement): Receiver tells sender “OK”.
    • NAK (Negative ACK): Receiver tells sender “Error, please repeat”.
    • Retransmission: Sender resends the packet upon NAK.

  • RDT 2.1 (序列号): What if ACK/NAK is corrupted? Sender adds Sequence Numbers (0, 1) to each packet to handle duplicates.

  • RDT 2.2 (无 NAK): Instead of NAK, the receiver sends an ACK for the last correctly received packet. A duplicate ACK at the sender acts like a NAK.

RDT 3.0: Channel with Errors and Loss.

  • Countdown Timer: If no ACK arrives within the limit (Timeout), then retransmit the packet.
  • Stop-and-Wait: Sender waits for one packet to be acknowledged before sending the next.
  • Performance: Utilization Rate (利用率): Usender=L/RRTT+L/RU_{\text{sender}} = \frac{L / R}{\text{RTT} + L / R}.

Pipelining (流水线): Allowing the sender to send multiple, “in-flight” packets without waiting for ACKs.

  • Requirments:
    • Increased range of Sequence Numbers.
    • Buffering at sender and/or receiver.
  • Go-Back-N (GBN): 一人犯错，全组重来
    • Sender Window: A range of NN consecutive unacknowledged sequence numbers.
    • Cumulative ACK: ACK(nn) means all packets up to and including nn have been correctly received.
    • Sender Timer: A single timer for the oldest transmitted but not yet ACKed packet. On timeout, the sender resends all packets in the current window (starting from the lost one).
    • Receiver:
      • Only sends ACKs for correctly received, in-order packets.
      • No Buffering: Discards out-of-order packets.
  • Selective Repeat (SR): 精准打击，谁丢补谁
    • Individual ACK: Receiver confirms each packet individually.
    • Sender Timers: Maintains a separate timer for each unACKed packet. Sender only resends the specific packet that timed out.
    • Receiver Buffering: Receiver keeps out-of-order packets in a buffer for later assembly.
    • Rule: Sequence Number Space≥2⋅Window Size\text{Sequence Number Space} \ge 2 \cdot \text{Window Size}.

Transmission Control Protocol (TCP)

Format:

  • Sequence Numbers (Seq #): Byte stream “number” of the first data byte in the segment.
  • Acknowledgement Numbers (Ack #): Seq # of the next byte expected from the other side (Cumulative ACK).
  • Flags (UAPRSF):
    • ACK: Ack # is valid.
    • SYN/FIN: Used for connection setup/teardown.
    • RST: Reset connection.
    • PSH/URG: Push/Urgent (rarely used).
  • Receive Window: Number of bytes the receiver is willing to accept (for Flow Control).

RTT Estimation:

  • EstimatedRTT=(1−α)⋅EstimatedRTT+α⋅SampleRTT\text{EstimatedRTT} = (1 - \alpha) \cdot \text{EstimatedRTT} + \alpha \cdot \text{SampleRTT}. (typically α=0.125\alpha = 0.125)
  • DevRTT=(1−β)⋅DevRTT+β⋅∣SampleRTT−EstimatedRTT∣\text{DevRTT} = (1 - \beta) \cdot \text{DevRTT} + \beta \cdot |\text{SampleRTT} - \text{EstimatedRTT}|. (typically, β=0.25\beta = 0.25)
  • TimeoutInterval=EstimatedRTT+4⋅DevRTT\text{TimeoutInterval} = \text{EstimatedRTT} + 4 \cdot \text{DevRTT}​.

RDT:

  • Retransmissions triggered by: timeout events / duplicate ACKs.

  • Fast Retransmit: If sender receives 3 duplicate ACKs for the same data (total 4 ACKs), it resends the unacked segment with the smallest Seq # before the timer expires.

  • Flow Control:

    • Receive Window (rwnd\text{rwnd}): Prevent sender from overflowing the receiver’s buffer.
    • rwnd=RcvBuffer−[LastByteRcvd−LastByteRead]\text{rwnd} = \text{RcvBuffer} −[\text{LastByteRcvd} − \text{LastByteRead}]​.
    • Sender guarantees LastByteSent−LastByteAcked≤rwnd\text{LastByteSent} − \text{LastByteAcked} \le \text{rwnd}​.

Connection Management:

  • 3-Way Handshake (Establishment):

  • 4-Way Handshake (Closing):

  • RST: Sent when a host receives a segment that does not match any existing socket.

Congestion Control:

  • Additive Increase Multiplicative Decrease:

    • Increase cwnd\text{cwnd} by 11 MSS every RTT until loss is detected.
    • Cut cwnd\text{cwnd} in half after a non-timeout loss (3 duplicate ACKs).

  • 3 Major Components:

    • Slow Start: Start with cwnd=1\text{cwnd} = 1 MSS. Double cwnd\text{cwnd} every RTT.
    • Congestion Avoidance: When cwnd≥ssthresh\text{cwnd} \ge \text{ssthresh}, increase cwnd\text{cwnd} by 1 MSS per RTT.
    • Fast Recovery: When 3 duplicate ACKs received, TCP stays in a higher sending rate without dropping to 1 MSS.
      • TCP Tahoe: Whether timeout or 3 duplicate ACKs, cwnd=1\text{cwnd} = 1 MSS, enters Slow Start.
      • TCP Reno: ssthresh=cwnd/2\text{ssthresh} = \text{cwnd}/2, cwnd=ssthresh+3\text{cwnd} = \text{ssthresh} + 3​ MSS, enters Fast Recovery (then Congestion Avoidance).

  • Average Throughput:

    34⋅WRTT bytes/sec\frac{3}{4} \cdot \frac{W}{\text{RTT}} \text{ bytes/sec}

    where WW​ is the windows size (in bytes) where loss occurs.

    • Long, Fat Pipes Problem: Traditional TCP performs poorly on very high-speed networks because even a tiny drop causes the window to halve.

  • Fairness: Fair. 趋于平分带宽。

  • Explicit Congestion Notification (ECN, 显式拥塞通知): Routers can set 2 bits in the IP header to explicitly tell the sender “the network is getting congested” before packets are actually dropped.

Chapter 4. Network

Data Plane:

  • Local function within each router.
  • Determines how a datagram arrives on an input port and is moved to an output port.
  • Implemented in Hardware.

Control Plane:

  • Network-wide logic.
  • Determines how a datagram is routed along the end-to-end path.
  • Implemented in Software.

Two Approaches to Control Plane:

  • Traditional: Each router has its own routing algorithm that talks to others.
  • Software-Defined Networking (SDN): A remote Centralized Controller tells each router what to do.

Network Service Model: No guarantees. “Best Effort”.

Routers

2 Major Components:

  • Routing Processor (Control Plane): Software-based, operates in ms timeframe. Handles routing protocols (RIP, OSPF, BGP).
  • Switching Fabric & Ports (Data Plane): Hardware-based, operates in ns timeframe. Handles forwarding.

Input Ports:

  • Decentralized Switching: Each input port has a copy of the forwarding table to avoid a central bottleneck. “match plus action”
  • Longest Prefix Matching (LPM): When searching the table, use the longest address prefix that matches the destination. 匹配多个范围，选描述最精确（最长）的。

Switching Fabrics:

Output Ports:

  • Buffering: Required when datagrams arrive from fabric faster than the output line rate. Packet Loss occurs when the buffer (queue) overflows.
  • Scheduling: Deciding which packet to send next.
    • FIFO: First-in, first-out. (Simple)
    • Priority: Send the highest priority packet first (e.g., voice over email).
    • Round Robin (RR): Cyclically scan class queues, one from each class.
    • Weighted Fair Queuing (WFQ): Each class gets a weighted amount of service (e.g., Class A gets 60%, Class B gets 40% of bandwidth).

Internet Protocol (IP)

Format:

Fragmentation (碎片化) & Reassembly (重组):

  • Maximum Transmission Unit (MTU): The largest possible link-level frame (e.g., Ethernet is 1500 bytes).
  • Fragmentation: Large IP datagrams are divided into smaller ones when the next link’s MTU is too small.
  • Reassembly: Done only at the final destination to reduce router load.

IPv4 Addressing & Subnet:

  • IPv4 Address: 32-bit identifier for a specific interface (not the whole host).

  • Subnet: Device interfaces that cam physically reach each other without an intervening (介入) router.

  • IP Address Allocation:

    • Internet Corporation for Assigned Names and Numbers (ICANN): Global organization that allocates IP addresses, manages DNS, assigns domain names, and resolves disputes (争议).
    • A subnet/network gets its IP block by being allocated a portion of its provider ISP’s address space.

  • Classless Inter-Domain Routing (CIDR): Address format a.b.c.d/x, where x is the number of bits in the subnet portion.

    • Calculation: Determine the block size based on host requirements using powers of 2n2^n (e.g. 28→2528 \to 2^5, 62→2662 \to 2^6).

  • Route Aggregation (路由聚合): An ISP can advertise one single large prefix (e.g., 200.23.16.0/20) to the Internet instead of many small individual prefixes. This keeps global routing tables small and efficient.

  • Dynamic Host Configuration Protocol (DHCP):

    • Goal: Allow a host to dynamically obtain an IP address when it joins the network. “plug-and-play (即插即用)”

    • Process: Discover, Offer, Request, ACK. (DORA)

Network Address Translation (NAT):

  • Reserve blocks of IP address for LANs.

  • Mechanism: Use Port Numbers, recorded in the NAT Translation Table.

  • Pros:

    • Saves IPs: Only one ISP-allocated address needed for all devices.
    • Flexibility: Can change internal IPs or change ISPs without notifying the outside world.
    • Security: Devices inside the LAN are not directly addressable/visible from the internet.

  • Cons:

    • Port Limit: The port field is 16-bit, allowing ~60,000 simultaneous connections per public IP.
    • Layer Violation: Routers should only process up to layer 3.
    • End-to-End Argument Violation: Applications like BitTorrent or Skype struggle because peers cannot initiate connections into a NATed network directly (they don’t have a public IP).

IPv6:

  • Format:

    • Fixed Header: Fixed length of 40 bytes (Simpler than IPv4’s variable 20+ bytes).
    • Priority (Traffic Class): Identify priority (e.g., voice vs. email).
    • Flow Label: Identify datagrams in the same “flow” (for QoS).
    • Next Header: Identifies the upper layer protocol (TCP/UDP) OR an extension header.
    • Hop Limit: Same as TTL in IPv4 (decremented at each router)…

  • Differences:

    • No Checksum: Removed to reduce processing time at each hop. (Reliability is handled by Link Layer and Transport Layer).
    • No Fragmentation: Routers do not fragment packets.
      • If a packet is too big for the link: The router drops it and sends an ICMP “Packet Too Big” error back to the sender.
      • Sender must use smaller packets.
    • No Options: Moved outside the base header to the “Next Header” chain.

  • Tunneling (隧道): IPv6 datagram is carried as payload in an IPv4 datagram among IPv4 routers.

Generalized Forwarding

Traditional Forwarding: Based only on destination IP address.

Generalized Forwarding (广义转发): Based on multiple header fields (IP src/dest, MAC src/dest, TCP/UDP ports, etc.).

  • Match: Look at various fields in the packet header.
  • Action: Drop, forward, modify, or send to controller.
Device Match Action
Router Longest destination IP prefix Forward out a link
Switch Destination MAC address Forward
Firewall IP addresses and TCP/UDP port numbers Permit or deny
NAT IP address and port Rewrite address and port

Chapter 5. Network - Control Plane

2 Approaches of Control Plane:

  • Per-Router Control (traditional)
  • Logically Centralized Control (SDN)

Routing Protocols

Link-State (LS): Dijkstra’s Algorithm:

  • Characteristics:
    • Global Information: All routers have complete topology, link cost info.
    • Link State Broadcast: Every node broadcasts its link costs to all other nodes so everyone has the same view of the network.
  • Oscillation Problem: 如果路越堵，代价越高，大家就会一窝蜂避开堵的路去走空的路，结果空路瞬间堵死，大家又一窝蜂回来。

Distance Vector (DV): Bellman-Ford:

  • Characteristics:
    • Distributed: Each node communicates only with neighbors.
    • Iterative: Continues until no more information is exchanged.
    • Asynchronous (异步的): Nodes don’t need to operate in lockstep.
  • Bellman-Ford Equation: dx(y)=min⁡v{c(x,v)+dv(y)}d_x(y) = \min_v\{c(x, v) + d_v(y)\}​.
  • Count-to-Infinity Problem: 假设 A-B-C 连成线。A 断网了。B 发现 A 不见了，但 C 还没反应过来，C 告诉 B：“我有去 A 的路（其实是 C->B->A）”。结果 B 和 C 互相指着对方说“走你那边”，距离在 2, 3, 4, 5… 中无限增加，直到加到无穷大（通常是 16）才发现路不通。
    • Partial Solution: Poisoned Reverse: C 在给 B 发路由表时会撒个谎：“虽然我有去 A 的路，但因为我是经由你 B 去的，所以我骗你说我去 A 是无穷远”。这样 B 就不会傻乎乎地想走 C 这条回头路了。
Feature Link State (LS) Distance Vector (DV)
Message Complexity High. O(nE)O(nE) messages sent (nn nodes, EE links). Low. Exchange between neighbors only.
Speed of Convergence Fast. O(n2)O(n^2) algorithm complexity. Slow. Time varies; susceptible to routing loops and the count-to-infinity problem.
Robustness Strong. Nodes may advertise incorrect link cost. Each node computes its own table (errors stay local). Weak. Nodes may advertise incorrect path cost. Errors propagate through the network (tables used by others).

Intra-AS Routing: Interior Gateway Protocols (IGP)

Autonomous Systems (AS, Domains): Aggregated routers.

  • Gateway Router: at “edge” of its own AS, has link(s) to router(s) in other AS.
  • Interior Router: No link to other AS.

Common Intra-AS Routing Protocols:

  • RIP: Routing Information Protocol (distance vector-based).
  • OSPF: Open Shortest Path First (link state-based).
  • IS-IS protocol essentially same as OSPF.
  • IGRP: Interior Gateway Routing Protocol (Cisco proprietary for decades, until 2016).

Open Shortest Path First (OSPF):

  • “Open”: Publicly available.

  • Algorithm: Uses Link-State algorithm (Dijkstra).

    • Each router constructs a complete topological map of the entire AS.
    • Each router locally runs Dijkstra’s algorithm to find the shortest path.

  • Flooding: Router floods OSPF link-state advertisements (LSA) to all other routers in the entire AS.

  • Transport: OSPF messages are carried directly over IP (not TCP or UDP).

  • Advanced Features:

    • Security: All OSPF messages are authenticated. This prevents malicious intrusion (bad guys injecting fake routes).
    • Multiple Paths: Allows multiple same-cost paths (RIP only chooses one). This helps with load balancing.
    • Integrated Multicast: Multicast OSPF (MOSPF) uses the same topology database.
    • Hierarchical: Supports hierarchical OSPF in large domains.

  • Hierarchical OSPF:

    • Solution: Two-Level Hierarchy: Local Area & Backbone.

Inter-AS Routing: Border Gateway Protocol (BGP)

  • Transport: Messages exchanged over TCP connections (Reliable).
  • 2 Flavors:
    • eBGP (External): Obtain subnet reachability information from neighboring ASes.
    • iBGP (Internal): Propagate (传播) reachability information to all internal routers within the AS.
    • Gateway Routers run both protocols to bridge the internal network with the outside world.
  • Path Attributes:
    • AS-PATH: Lists the ASes the advertisement has passed through (e.g., AS2, AS3). This is critical for loop detection—if a router sees its own AS number in the path, it rejects the route.
    • NEXT-HOP: The IP address of the router interface that begins the AS-PATH. This links the inter-AS path (BGP) with the intra-AS forwarding (OSPF).
  • Route Selection Rule: Order:
    • Local Preference (Policy): Highest value wins. This represents the admin’s commercial/political preference.
    • Shortest AS-PATH: The route passing through the fewest number of ASes.
    • Closest NEXT-HOP (“Hot Potato” Routing, 烫手山芋): Choose the gateway that has the least intra-domain cost (via OSPF/RIP). The router wants to dump the packet out of its AS as quickly as possible.
  • IP Anycast:
    • Mechanism: Assign the same IP address to multiple servers in different geographic locations and advertise it via BGP from all those locations.
    • Result: Routers naturally route distinct users to the closest server (based on BGP hop counts). Used heavily by DNS and CDNs.

Software-Defined Networking (SDN)

SDN: Logically centralized control plane.

SDN Perspective:

  • Network-Control Applications (Top):

    • The “brains”. Programs that implement control logic (Routing, Access Control, Load Balancing).
    • Unbundled (分离的) from the hardware.
    • Communicates via Northbound API.

  • SDN Controller (Middle):

    • The Network OS. Maintains network state information (topology, link status).
    • Implemented as a distributed system for reliability (physically distributed, logically centralized).
    • Interacts with switches via Southbound API and apps via Northbound API.

  • Data Plane Switches (Bottom):

    • Fast, simple, commodity (必需) hardware.
    • Executes Generalized Forwarding (Match + Action) based on flow tables computed by the controller.
    • Communicates via Southbound API (e.g., OpenFlow).

OpenFlow Protocol:

  • Role: The standard protocol for the Southbound Interface.
  • Message Types:
    • Controller-to-Switch: Configure, Modify-State (add/delete rules), Read-State, Packet-Out (send this packet).
    • Switch-to-Controller: Packet-In (I don’t know what to do with this packet, help!), Flow-Removed, Port-Status (Link up/down).

The Internet Control Message Protocol (ICMP)

ICMP:

  • Role: Error reporting, Echo request/reply (ping).

  • ICMP messages are carried inside IP datagrams (Protocol field = 1).

  • Message Structure: Type + Code + Payload (the header and the first 8 bytes of IP datagram causing error).

Traceroute:

  • Goal: Trace the route (sequence of routers) from source to destination.

  • Mechanism:

    1. Source sends a series of UDP segments to the destination.
    2. Sets TTL = 1 for the 1st set, TTL = 2 for the 2nd set, etc.
    3. Uses an unlikely port number (so the destination will reject it).

    When the packet finally arrives (TTL is sufficient), the destination sees the weird (怪异的) port number and sends back an ICMP Type 3 Code 3 (Port Unreachable).

Chapter 6. Link

Terminology:

  • Nodes: Hosts and routers
  • Links: Communication channels that connect adjacent nodes along the communication path (e.g., wired, wireless, LANs).

Services:

  • Framing (成帧):
    • Encapsulate (封装) datagram into frame, adding header (use MAC addresses rather than IP!) and trailer.
  • Link Access:
    • Media Access Control (MAC) protocol specifies rules for transmitting onto the link (e.g., “don’t talk when others are talking”).
  • Reliable Delivery:
    • Guarantees to move each datagram across the link without error (via ACKs and retransmissions).
    • Seldom used on low bit-error links (fiber, coax) to save overhead; mostly used on wireless links (high error rates).
  • Flow Control:
    • Pacing between adjacent sending and receiving nodes to prevent buffer overflow.
  • Error Detection:
    • Detects bit errors caused by signal attenuation (衰减) or noise.
    • Hardware implemented (e.g., CRC). Receiver drops the frame or asks for retransmission.
  • Error Correction:
    • Receiver identifies and corrects bit error(s) without resorting to retransmission.

Implementation: In each and every host.

  • Hardware: Implemented in the Network Interface Card (NIC) or on a chip (Network Adaptor).
  • Software: Attaches into host’s system buses (总线); drivers handle interrupts and interaction with the OS.

Error Detection & Correction

  • Error Detection and Correction bits (EDC): Extra bits added to the frame header/trailer.
  • D (Data): The payload being protected.
  • Trade-off: Larger EDC field yields better detection/correction, but creates larger overhead.
  • Reality: Error detection is not 100% reliable! (Though protocol designers make the probability of missed errors negligible).

Parity Checking:

  • Single Bit Parity:
    • Mechanism: Add one bit to make the total number of 1s even (Even Parity) or odd (Odd Parity).
    • Limit: Can detect single bit errors, but fails if an even number of bits flip (e.g., two bits flip, the count remains even).
  • Two-Dimensional Bit Parity
    • Mechanism: Arrange data in a matrix (rows and columns). Calculate parity for each row AND each column.
    • Feature: Can detect and correct a single bit error. (The intersection of the bad row and bad column pinpoints the error).

Internet Checksum:

  • Mostly used in Transport Layer.
  • Mechanism: Treat data as 16-bit integers, sum them up (1’s complement sum).

Cyclic Redundancy Check (CRC):

  • 选择长度为 r+1r + 1 的除数 GG (Generator)，用 D⋅2rD \cdot 2^r (Data bits) 做逐位异或除法得到 rr 位的 RR (CRC bits)。接收方用 ⟨D,R⟩\langle D, R \rangle 再做逐位异或除法，得到余数如果为 00，则无误，反之有误。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
               101011
         -------------
    1001 )  101110000      <-- 补零后的 D
            1001           <-- 被除数首位是 1，用 G 做异或
            ----
             0101          <-- 结果
             0000          <-- 首位是 0，不够除（商 0），移位
             ----
              1010         <-- 拉下来一位，首位是 1，可以除
              1001         <-- 用 G 做异或
              ----
               0110        <-- 结果
               0000        <-- 首位是0
               ----
                1100       <-- 拉下来，首位是 1
                1001       <-- 用 G 做异或
                ----
                 1010      <-- 结果
                 1001      <-- 首位是 1，用 G 做异或
                 ----
                  011      <-- 余数 R

  • Widely used in practice (Ethernet, 802.11 WiFi, ATM).

Multiple Access Protocols

Channel Partitioning:

  • TDMA (Time Division): Access to channel in “rounds”. Each station gets a fixed slot (length = packet time).
    • Con: Unused slots go idle (wasteful at low load).
  • FDMA (Frequency Division): Channel spectrum divided into frequency bands.
    • Con: Unused bands go idle.

Random Access:

  • Transmit at full rate RR​. No a priori (先验) coordination. If collision occurs, wait a random time and retransmit.
  • Slotted ALOHA: Time is divided into slots. Nodes only start at the beginning of a slot. If collision occurs, retransmit in subsequent slots with probability pp until success.
    • Efficiency: E=N⋅p⋅(1−p)N−1→1e≈37%E = N \cdot p \cdot (1 - p)^{N - 1} \to \frac{1}{e} \approx 37\% (p=1Np = \frac{1}{N}​).
  • Pure ALOHA: No synchronization. Transmit immediately. Node ii succeeds if no one transmits in [t0−1,t0][t_0 - 1, t_0] AND no one transmits in [t0,t0+1][t_0, t_0 + 1].
    • Efficiency: E=N⋅p⋅(1−p)2(N−1)→12e≈18%E = N \cdot p \cdot (1 - p)^{2(N - 1)} \to \frac{1}{2e} \approx 18\% (p=1Np = \frac{1}{N}).
  • CSMA (Carrier Sense Multiple Access): “Listen before transmit”. If channel idle, transmit; If channel busy, defer.
    • Collision exists due to propagation delay.
  • CSMA/CD (Collision Detection): “Listen while talking”. If a collision detected, stop immediately (Abort), send a Jam Signal and enter Binary Exponential Backoff:
    • After mm-th collision, choose a random wait time KK from {0,1,⋯ ,2m−1}\{0,1,\cdots,2m−1\}. Wait K×512K \times 512​​ bit times.
    • Used in Ethernet.

Taking Turns:

  • Polling (轮询): Master node “invites” slave nodes to transmit in turn.
  • Token Passing: A control Token is passed around. Only the holder can speak.
  • Concerns: Token overhead; Single point of failure.

LANs

MAC Address (48-bit):

  • Link Layer address.
  • Burned into the NIC ROM.
  • Unique, administered by IEEE.

Address Resolution Protocol (ARP):

  • Resolves addresses only for interfaces on the same subnet.
  • ARP Table: Stored in each host/router. Contains < IP address; MAC address; TTL >.
  • Steps (Same LAN): Broadcast Query; Unicast Reply; Cache.
  • Different LANs: IP Addresses (Source & Dest) do NOT change from source to destination; MAC Addresses (Source & Dest) change at every hop.

Ethernet:

  • Physical Topology:

    • Bus (总线型, Out-of-date): all nodes in same collision domain.
    • Star (星型, Modern): Active switch in center. Each “spoke” runs a separate Ethernet protocol. No collisions between nodes.

  • Service: Connectionless. Unreliable.

  • Protocol: CSMA/CD with binary backoff.

  • Frame Structure:

    • Preamble (前导码, 8 bytes): Used to synchronize receiver/sender clock rates. (7 bytes of 10101010 + 1 byte of 10101011).
    • Dest Address (6 bytes): Destination MAC.
    • Source Address (6 bytes): Source MAC.
    • Type (2 bytes): Indicates higher layer protocol (mostly IP, but could be ARP, etc.).
    • Data (Payload, 46-1500 (MTU) bytes): IP datagram.
    • CRC (4 bytes): Error check. If error detected, frame is dropped.

  • 802.3 Ethernet Standards.

Switches:

  • Layer: Link-layer device (Layer 2). It sees MAC addresses, not IP addresses.
  • Role: Store and forward Ethernet frames.
  • Transparent: Hosts are unaware of the switch’s presence.
  • Plug-and-play: No configuration needed (unlike routers).
  • Star Topology: Hosts have dedicated, direct connections to the switch.
  • No Collisions: Switches buffer packets. Full duplex. A-to-A’ and B-to-B’ can transmit simultaneously.
  • Switch Table: (Self-learning) Contains entries (MAC Address, Interface, Time Stamp).

VLANs:

  • Port-based VLAN: Switch ports are grouped by software.
  • Trunking: Spanning multiple switches.
    • Trunk Port: A port carrying frames for multiple VLANs between switches.
    • 802.1Q: Protocol that adds a VLAN Tag to the Ethernet frame header so the receiving switch knows which VLAN the frame belongs to.

Chapter 7. Wireless Networks

3 Elements:

  • Wireless Hosts: End-system devices (laptops, smartphones, IoT).
  • Base Station: Cell towers, 802.11 Access Points (APs).
  • Wireless Link: Connects mobiles to the base station (or to each other).

2 Modes:

  • Infrastructure Mode (基础设施模式, Most Common):
    • Base station connects mobiles into the wired network.
    • Handoff (切换): Occurs when a mobile device changes the base station providing connection into the wired network.
  • Ad Hoc Mode (自组织模式):
    • No base stations.
    • e.g., Bluetooth Network.

Taxonomy (分类):

  • Single Hop + Infrastructure:
    • Host connects to base station which connects to Internet.
    • Examples: WiFi (802.11), Cellular (4G/5G/WiMAX).
  • Single Hop + No Infrastructure:
    • No base station, no connection to larger Internet.
    • Examples: Bluetooth, simple Ad hoc networks.
  • Multiple Hops + Infrastructure:
    • Host relays through several wireless nodes to connect to the Internet.
    • Examples: Wireless Mesh Networks.
  • Multiple Hops + No Infrastructure:
    • No base station. Nodes rely on each other to reach a destination node.
    • Examples: MANET (Mobile Ad Hoc Networks), VANET (Vehicular Ad Hoc Networks).

Characteristics

3 Challenges:

  • Path Loss (信号衰减)
  • Interference (大家都在吵)
  • Multipath (回音太重)

Signal-to-Noise Ratio (SNR): The ratio of signal power to noise power.

Bit Error Rate (BER): The probability that a transmitted bit is received in error.

  • Higher SNR -> Lower BER.

Rate Adaptation:

  • High SNR (Good signal): Use aggressive modulation (e.g., QAM256) for High Speed.
  • Low SNR (Bad signal): Switch to conservative modulation (e.g., BPSK) for Low Speed but High Reliability.

Code Division Multiple Access (CDMA)

  • Concept: All users share the same frequency at the same time.
  • Chipping Sequence (Code): Each user is assigned a unique code (e.g., 1, 1, 1, -1).
  • Encoding: Signal = Original Data ×\times Chipping Sequence.
  • Orthogonality (Key Math): The codes are orthogonal. The inner product of two different codes is 0.
  • Decoding: Receiver calculates the inner product of the received signal and the sender’s code.
    • If multiplied by Sender A’s code →\to Recovers A’s data.
    • If multiplied by Sender B’s code →\to Result is 0 (Noise is filtered out).

IEEE 802.11 Wireless LAN (Wi-Fi)

Architecture:

  • Basic Service Set (BSS): The fundamental building block (“Cell”). Contains Wireless Hosts + Access Point (AP).
  • Channels: 2.4GHz spectrum is divided into 11 channels. Neighbors can interfere.

Association (Connecting): Host must associate with an AP.

  • Passive Scanning: Host listens for Beacon Frames (advertisements) sent by APs.
  • Active Scanning: Host broadcasts Probe Request frames; APs respond with Probe Response.

MAC Protocol: CSMA/CA (Collision Avoidance):

  • Why not Collision Detection (CD)?
    1. Fading: The signal fades over distance. The sender might be too far to hear the collision at the receiver.
    2. Overwhelmed: The sender’s own transmitting signal is much stronger than any incoming signal. It can’t “hear” while “talking”.
  • Mechanism:
    1. Sense: Listen to channel.
    2. DIFS (等一小会再确认发送): If idle for DIFS time, transmit.
    3. Backoff: If busy, pick a random backoff time and count down.
    4. ACK: Receiver MUST send an ACK after receiving data (because sender can’t detect collision itself). ACK is sent after SIFS (Short Inter-frame Spacing).

Service: Connectionless. Reliable.

Collision Avoidance: RTS/CTS:

  • The Hidden Terminal Problem: A, C 都能与 B 交流，但彼此不知道对方，于是同时说话产生干扰。
  • Solution: Reserve the channel using small packets.
    1. Sender transmits RTS (Request to Send) to AP. “Can I reserve the channel?”
    2. AP broadcasts CTS (Clear to Send). “Yes, Sender A can talk. Everyone else, BE QUIET.”
    3. All nodes hear the CTS and defer transmission.
  • Benefit: Collisions only happen on small RTS packets, not long Data packets. 别人看到 A 在与 AP 传输自动等待。

Cellular Internet Access 蜂窝网络接入

  • Cell: Geographical area covered by a Base Station.
  • Base Station (BS): Interface between wired network and wireless hosts (like an AP).
  • Mobile Switching Center (MSC): The “Brain” of legacy networks.
    • Connects cells to the wired telephone network.
    • Manages call setup and mobility (handoffs).
  • Air Interface (First Hop): Protocol between mobile and BS.
    • FDMA/TDMA.
    • CDMA.

Architecture Evolution:

Generation 2G (Voice) 3G (Voice + Data) 4G LTE (All IP)
Core Concept Circuit Switched (Voice only) Parallel Networks (Overlay) Packet Switched (All IP)
Radio Access BTS (Tower) →→ BSC (Controller) NodeB →→ RNC (Controller) eNodeB (Smart BS, no controller)
Core Network MSC handles everything. Voice →→ MSC; Data →→ SGSN & GGSN Separation of Control & Data Plane.
Key Nodes - SGSN: Serves user locally. GGSN: Gateway to Internet. MME: Control (Mobility/Auth). S-GW/P-GW: Data Tunneling.