计算机网络原理 期末复习

Computer Network Final Notes

Some useful (maybe) facts are first shown.

• Protocal Stack

  

• Turing Award

  • Bob Metcalfe: Father of Ethernet
  • Vinton G. Cerf & Robert E. Kahn: TCP/IP
  • Tim Berners-Lee: Web & HTTP

Now comes the crazy things!

Introduction

Connect end systems to edge router

• Residential access networks
• Institutional access networks (school, company)
• Mobile access networks (WiFi, 4G/5G)
  • Wireless local area networks
    • 802.11 (WiFi)
  • Wide-area cellular access networks
    • 4G cellular networks

Links physical media

• Twisted pair (TP)
• Coaxial cable
• Fiber optic cable
  • high-speed operation
  • low error rate
• Wireless radio
  • no physical “wire”
  • broadcast, “half-duplex”
  • propagation environment effects

Packet switching

• On-demand allocation
  • Store-and-forward
  • Great for “bursty” data
  • Resource sharing

Circuit switching

• Reserved resources
  • Dedicated, no resource sharing
  • FDMA and TDMA

Network of networks

• Global Transit ISP

• Content Provider Network (bypassing tier-1, regional ISPs)

• Internet Exchange Point

• Regional ISP

• Access ISP

  

Performance

• Delay:

  $$d_{nodal}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$$

• Throughput: bottleneck link on end-end path that constrains throughput

Security

• Packet Sniffing:
  • broadcast media (shared Ethernet, wireless)
  • promiscuous network interface reads/records all packets
• IP spoofing:
  • injection of packet with false source address
• Denial of Service:
  • overwhelme resource with bogus traffic
  • make resources (server, bandwidth) unavailable

Application layer

Network app

• Run on end systems
• Not run on network-core devices
• (Network layer protocols in every Internet device: hosts, routers)

Client-server paradigm

• Server:
  • permanent IP address
  • often in data centers, for scaling
• Client:
  • intermittently connected
  • dynamic IP addresses
  • do not communicate directly with each other
• Examples: HTTP, IMAP, FTP

Peer-peer architecture

• Peer:
  • intermittently connected
  • dynamic IP addresses
  • arbitrary end systems directly communicate
  • self scalability – new peers bring new service capacity and service demands
• Example: P2P file sharing

TSL

• Application-layer protocal, Provides encrypted TCP connections

HTTP (Hypertext Transfer Protocol)

• Web’s Application-layer protocol, use TCP

  

• Stateless: server maintains no information about past client requests

• Developments:

  • HTTP 1.1:
    • persistent HTTP
    • multiple, pipelined GETs over single TCP connection
    • FCFS scheduling, HOL blocking
    • loss recovery stalls object transmission
  • HTTP/2:
    • transmission order based on client-specified priority, interleaved
    • divide objects into frames, mitigate HOL blocking
    • loss recovery stalls object transmission
  • HTTP/3:
    • adds security, per object error- & congestion-control (more pipelining) over UDP

Cookie

• Components:

  • header line of HTTP response message
  • header line in next HTTP request message
  • file kept on user’s host, managed by user’s browser

  • back-end database at web site

    

• Used for:

  • authorization
  • recommendations
  • user session state

• GDPR (EU General Data Protection Regulation)

Web caches

• Acts as both client and server

  

• Browser caching: Conditional GET

• Pros:

  • reduce end-end response time
  • reduce traffic on institution’s access link
  • enables content providers to effectively deliver content

SMTP (Simple Mail Transfer Protocol)

• E-mail’s Application-layer protocol, use TCP
• Use persistent connections
• Comparison:
  • HTTP
    • client pull
    • each object encapsulated in its own response message
  • SMTP
    • client push
    • multiple objects sent in multipart message
• Mail access protocol: retrieval from server
  • IMAP (Internet Mail Access Protocol)
  • POP
  • HTTP

DNS (Domain Name System)

• Application-layer protocol, distributed and hierarchical database

• Services:

  • hostname to IP address translation
  • host aliasing
    • canonical, alias names
  • mail server aliasing
  • load distribution
    • replicated IP addresses correspond to one name

• Decentralized:

  • single point of failure
  • traffic volume
  • distant centralized database
  • maintenance
• DNSSEC – provides security
• ICANN - manages root DNS domain
• Local DNS server:
  • local cache of recent translation pairs
  • doesn’t strictly belong to hierarchy
  • forwarding request into DNS hierarchy
  • TLD servers typically cached, allowing root server bypass
• Iterated query & Recursive query
• DNS records:
  • type = A
    • hostname - IP address
  • type = CNAME
    • alias name - canonical name
  • type = NS
    • domain - hostname of authoritative name server
  • type = MX
    • name - name of SMTP mail server
• Example:
  • register name at DNS registrar
    • provide names, IP addresses of authoritative name server
    • inserts NS, A RRs into .com TLD server
      • (networkutopia.com, dns1.networkutopia.com, NS)
      • (dns1.networkutopia.com, 212.212.212.1, A)
  • create authoritative server locally with IP address 212.212.212.1
    • type A record for www.networkuptopia.com
    • type MX record for networkutopia.com

P2P

• File distribution time:

  • client-server: $\max\{NF/u_s,F/d_{min}\}$

  • P2P: $\max\{F/u_s,F/d_{min},NF/(u_s+\sum u_i)\}$

    

• File distribution: BitTorrent

  • tracker
  • torrent
  • churn
  • Sending chunks: tit-for-tat
    • sends chunks to four peers sending her chunks at highest rate
    • other peers choked
    • every 30 secs select another peer, starts sending chunks
    • optimistically unchoke this peer

Video Streaming and CDNs

• Challenges:
  • server-to-client bandwidth varies
  • changing network congestion levels
  • packet loss, delay due to congestion
• DASH (Dynamic, Adaptive Streaming over HTTP)
  • Application-layer protocol, use HTTP and TCP
  • Server:
    • divides video file into chunks, encoded at different rates
    • files replicated in various CDN nodes
    • provides URLs for different chunks (manifest file)
  • Client:
    • periodically estimates server-to-client bandwidth
    • consulting manifest, requests one chunk at a time
    • choose rates at different time and from different servers
    • “Intelligence” at client
• single, large “mega-server”:
  • single point of failure
  • point of network congestion
  • long path to distant clients
• CDN:
  • multiple copies of videos at geographically distributed sites
    • enter deep: push servers deep into many access networks
    • bring home: smaller number of larger clusters in POPs near access nets

Transport Layer

Services not available

• Delay guarantees
• Bandwidth guarantees

Demultiplexing

• Connectionless:
  • UDP: using destination port number (only)
• Connection-oriented:
  • TCP: using 4-tuple, IP addresses and port numbers
  • support simultaneous TCP sockets

UDP (User Datagram Protocol)

• Pros:
  • No connection establishment (which adds RTT delay)
  • No connection state at sender, receiver
  • Small header size
  • No congestion control, blast away as fast as desired
  • Helps with reliability (checksum)
• Used by:
  • streaming multimedia apps
  • DNS
  • DHCP
  • SNMP
  • HTTP/3

RDT (Reliable Data Transfer Protocol)

• Stop and Wait:

  

  

  

• Go-Back-N:

  

• Selective repeat:

  

TCP (Transfer Control Protocol)

• Retransmission:

  

  

• Flow control:

  • network layer delivers data faster than application layer removes data from socket buffers
  • receiver “advertises” free buffer space in rwnd in TCP header
  • sender limits amount of unACKed data to received rwnd

• Connection management:

  • 2-way handshake:

    • half open connection (no client)
    • dup data accepted

  • 3-way handshake:

    

Congestion control

• Costs of congestion:

  • needed retransmissions: more work for given receiver throughput
  • unneeded retransmissions: link carries multiple copies of a packet

  • packet dropped: upstream capacity and buffering wasted

    

• End-end congestion control:

  • no explicit feedback from network
  • congestion inferred from observed loss, delay
  • taken by: TCP

• Network-assisted congestion control:

  • routers provide direct feedback to hosts
  • taken by: TCP ECN, ATM, DECbit

AIMD (Additive Increase Multiplicative Decrease)

• Multiplicative decrease:

  • Cut in half on loss detected by triple duplicate ACK (TCP Reno)
  • Cut to 1 MSS when loss detected by timeout (TCP Tahoe)

• (1) TCP slow start:

  

• (2) TCP congestion avoidance:

  

• AIMD Summary:

  

Other congestion control methods

• TCP CUBIC

  • Increase W as function of cube distance between time and K

    

• Delay-based TCP congestion control

  • Minimum observed RTT (uncongested path)
  • Measured throughput close to uncongested throughput:
    • increase cwnd linearly
  • Measured throughput far below uncongested throughout:
    • decrease cwnd linearly
  • Without inducing/forcing loss

• ECN (Explicit congestion notification)

  • congestion indication carried to destination
  • destination sets ECE bit on ACK segment to notify sender
  • involves IP (header ECN bit) and TCP (header C, E bit)

QUIC (Quick UDP Internet Connections)

• Application-layer protocol, use UDP
  • increase performance of HTTP
  • deployed on many Google servers, apps
  • parallelism streams, no HOL blocking

Network Layer: Data Plane

Input port functions

• Decentralized switching:
  • Using header field values, lookup output port using forwarding table in memory (“match plus action”)
  • destination-based forwarding: based on destination IP address
  • generalized forwarding: based on any set of header field values

Switching fabrics:

• Switching via memory:
  • speed limited by memory bandwidth (2 bus crossings per gram)
• Switching via bus:
  • switching speed limited by bus bandwidth
• Switching via interconnection network:
  • n$\times$n switch from multiple stages of smaller switches

Output port functions

• Queueing and loss due to output port buffer overflow
• Buffer management: drop and marking
• Packet scheduling: which packet to send next on link
  • FCFS
  • Priority: FCFS within priority class
  • Round Robin (RR): cyclically, repeatedly scans class queues
  • Weighted Fair Queueing (WFQ): minimum bandwidth guarantee

IP addressing

• Subnets: device interfaces reaching each other without passing a router
• CIDR (Classless InterDomain Routing)
• DHCP (Dynamic Host Configuration Protocol)
  • Application-layer protocal, use UDP
  • Pros:
    • can renew its lease on address in use
    • allows reuse of addresses (hold address while connected/on)
    • support for mobile users who join/leave network
• Hierarchical addressing:
  • route aggregation
  • allows efficient advertisement of routing information
• ICANN: allocates IP addresses

NAT (Network Address Translation)

• Devices in local network share one IPv4 address as outside is concerned
• Pros:
  • just one IP address needed from provider ISP for all devices
  • change address of host in local network without notifying outside
  • change ISP without changing addresses of devices in local network
  • security: devices inside local net not directly addressable by outside
• Remember in NAT translation table
• Violates end-to-end argument (port manipulation by network-layer)

Tunneling

• IPv6 datagram as payload in IPv4 datagram among IPv4 routers

  

Generalized forwarding

• “match plus action” abstraction: match bits in packet header in any layers, take action
  • matching over many fields (link-, network-, transport-layer)
  • drop, forward, modify, or send matched packet to controller
  • “program” network-wide behaviors

Architectural Principles of the Internet

• Three cornerstone beliefs:
  • simple connectivity
  • IP protocol: that narrow waist
  • intelligence, complexity at network edge

Network Layer: Control Plane

Routing protocols

• Link state:
  • centralized
  • iterative
  • link costs depend on traffic volume, route oscillations possible
• Distance vector:
  • distributed
  • iterative
  • asynchronous
  • self-stopping
  • good news travels fast, bad news travels slow (count-to-infinity)

Intra-ISP routing

• Focus on performance

• Aggregate routers into regions as autonomous systems (AS)

  • Routers in same AS run same intra-AS protocol
  • Routers in different AS run different intra-AS protocols
  • Gateways perform inter-AS as well as intra-AS routing

• Forwarding table configured by intra- & inter-AS routing algorithms

• RIP (Routing Information Protocol)

  • Application-layer protocal, use UDP
  • classic DV
  • no longer widely used

• EIGRP (Enhanced Interior Gateway Routing Protocol)

  • Network-layer protocal
  • DV based

• OSPF (Open Shortest Path First)

  • Network-layer protocal, use IP

  • LS routing

  • IS-IS protocol (ISO standard) essentially same as OSPF

  • Hierarchical:

    • two-level hierarchy: local area, backbone.

    • each node has detailed area topology (only direction to others)

      

Inter-ISP routing

• Policy dominates over performance

• BGP (Border Gateway Protocol)

  • Application-layer protocal, use TCP

  • path vector protocol

  • policy-based routing: AS1 gateway router 1c chooses path AS3,X

    

  • Route selection:

    • local preference value attribute: policy decision
    • shortest AS-PATH
    • closest NEXT-HOP router (hot potato routing)

SDN (Software defined networking)

• Logically centralized control plane:

  • easier network management: avoid misconfigurations, greater flexibility of flows
  • table-based forwarding allows easier centralized “programming”
  • open implementation of control plane

• Components:

  • Data-plane switches
  • SDN controller: distributed for performance, scalability, robustness
  • Network-control apps: unbundled

• SDN controller:

  • interface layer to network control apps: abstractions API
  • network-wide state management: a distributed database
  • communication: communicate between controller and switches

• OpenFlow protocol:

  • operates between controller and switch
  • Application-layer protocal, use TCP to exchange messages
  • distinct from OpenFlow API (specify generalized forwarding actions)

• Example:

  

• ODL controller:

  • Service Abstraction Layer: interconnects internal, external applications and services

ICMP (Internet Control Message Protocol)

• Communicate network-level information
• Network-layer protocal, carried in IP datagrams.

Network management

• Components:

  • Managing server
  • Managed device
  • Network management protocol

• SNMP (Simple Network Management Protocol):

  

  • Application-layer protocol, use UDP
  • SMI (Structure of Management Information): data definition language

Link Layer and LANs

Services

• implemented in network interface card (NIC) or on a chip
• combination of hardware, software, firmware
  • framing
  • link access
  • reliable delivery
    • seldom used on low bit-error links
  • flow control
  • error detection & correction
    • CRC: used in Ethernet, 802.11 WiFi

Multiple Access Protocols

• Channel Partitioning

  • TDMA, FDMA

• Random Access: detect and recover from collisions

  • ALOHA, slotted ALOHA

  • CSMA, CSMA/CD, CSMA/CA

    

• Taking Turns

  • Polling, Token Passing

ARP (Address Resolution Protocol)

• Network-layer - Link-layer protocal
• MAC flat address:
  • portability
  • move interface from one LAN to another
• Routing within a subnet or to another subnet

Ethernet

• Physical topology:

  • bus
  • switched

• Ethernet frame

  

  • receive frame with matching destination address or with broadcast address (ARP packet), pass data in frame to network layer protocol
  • otherwise discard frame

• Unreliable, connectionless, unslotted CSMA/CD with binary backoff

Switch

• Store and selectively forward
• Transparent, no collisions
• Plug-and-play, self-learning

VLANs

• Reasons:
  • scaling: all layer-2 broadcast traffic must cross entire LAN
  • efficiency, security, privacy, efficiency issues
• Port-based VLAN:
  • multiple virtual LANS over single physical LAN infrastructure
  • traffic isolation
  • dynamic membership
  • forwarding between VLANS via routing
  • trunk port:
    • carry frames between VLANS over multiple physical switches
    • frames must carry VLAN ID info
    • 802.1Q protocol adds/removed additional header fields

MPLS (Multiprotocol label switching)

• Between Ethernet and IP
• high-speed IP forwarding among network of label-switched router
• MPLS forwarding table distinct from IP forwarding tables
• Flexibility
  • traffic engineering: use destination and source addresses to route flows to same destination differently
  • fast reroute: pre-computed backup paths in case of link failure

Datacenter networks

• Network elements:
  • Border routers
  • Tier-1 switches
  • Tier-2 switches
  • Top of Rack (TOR) switch
  • Server racks
• Load balancer
  • application-layer routing
  • hiding data center internals from client

Wireless and Mobile Networks

Wireless network taxonomy

Wireless link characteristics

• Differences from wired link:
  • decreased signal strength
  • interference from other sources
  • multipath propagation
• SNR (signal-to-noise ratio)
  • given physical layer: increase power $\rightarrow$ increase SNR $\rightarrow$ decrease BER
  • given SNR: choose physical layer to meet BER requirement, giving highest throughput
• Hidden terminal problem & Signal attenuation

IEEE 802.11 Wireless LAN

• BSS (Basic Service Set)

  • wireless hosts
  • access point: base station

• Active scanning:

  • Probe Request frame broadcast from H1
  • Probe Response frames sent from APs
  • Association Request frame sent to selected AP
  • Association Response frame sent from selected AP to H1

• Passive scanning:

  • Beacon frames sent from APs
  • Association Request frame sent to selected AP
  • Association Response frame sent from selected AP to H1

• CSMA/CA

  

  

  • difficult to sense collisions: weak received signal due to fading
  • can’t sense all collisions in any case: hidden terminal, fading

• 802.11 frame

  

  

• Advanced capabilities:

  • Rate adaptation
    • dynamically change transmission rate as mobile moves
    • BER becomes too high, switch to lower transmission rate but with lower BER
  • Power management
    • beacon frame contains list of mobiles with AP-to-mobile frames waiting to be sent

• Bluetooth (Personal area networks)

  • replacement for cables
  • ad hoc: no infrastructure
  • master polls clients, grants requests for client transmissions
  • parked mode: clients can park and later wakeup
  • bootstrapping: nodes self-assemble into piconet (plug and play)

4G LTE Network

• LTE data plane protocol stack
  • Packet Data Convergence: header compression, encryption
  • Radio Link Control Protocol: fragmentation/reassembly
  • Medium Access: requesting, use of radio transmission slots