Skip to content

Latest commit

 

History

History
274 lines (264 loc) · 16.9 KB

com208.md

File metadata and controls

274 lines (264 loc) · 16.9 KB
Raw

COM208

GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.

Fall 2014: Computer Networks

[TOC]

Computer Networks and the Internet

  • end-system : car nabigator, heart pacemaker, smartphone, laptop, server
  • switch : connecting end-systems with cable TV lines, phones lines, wireless or fibers
    • forwarding table : store meta-data, where to send
    • buffer : store data
    • packet loss
    • queuing delay
    • packet switching : packets treated on demand
      • admission control & forwarding decision per packet
      • efficient use of resources
      • unpredictable performance
      • simpler to implement
      • congestion control
      • store-and-forward (wait until last bit for processing) vs cut-throught (start processing after H bits received)
    • connection switching : resources reserved in advance
      • admission control & forwarding decision per connection
      • predictable performance
      • inefficient use of resources
      • time division multiplexing : divide time in time slots and separate them per connection
      • frequency division multiplexing : divide frequency spectrum in frequency bands and separate them per connection
  • internet service provider (ISP) : cable compagny, phone compagny, university net
    • phone company : PC + telephone together (DSL modem) - phone line - unlink (DSLAM) switch + telephone network
      • digital subscriber line (DSL) : copper, 3 channel (10-100Mb downstream data, 1-10Mb upstream data, 2-way phone)
      • why phone lines ? already available
    • cable company : PC (cable modem) - cable line (from multiple homes) - (CMTS) switch
      • cable : copper/fiber, 10-100Mb downstream, 10Mb upstream, shared broadcast
    • univeristy net : PC - ethernet cable - local switch - switch
      • ethernet : copper, 1-10Gb each direction
    • more : cellular, satellite, fiber to home, optical carrier
  • application programming interface (API) : conventions used to dialog
  • organization ISP
    • access ISP
    • global/regional ISP sometimes "peered"
    • tier-1 ISP "peered" together
    • internet exchange point connecting everyone
    • content provider (i.e. Google)
    • multi-homing : when multiple regional ISPs connect to the same access ISP
    • modularity / hierarchy ?
  • communications layers : a part of a system with well-defined interfaces to other parts, layer interacts only with interface between it and above/below layer
    • application : exchange messages (HTTP, SMTP, FTP)
    • transport : transports segments between end-system (TCP, UDP)
    • network : moves datagrams around the network (IP)
    • link : moves frames across a link (ethernet, wifi, DSL, cellular)
    • physical : moves data across a physical medium (copper, fiber, wireless)
    • end user machines include all layers
    • switch only include network, link, physical
    • reduce complexity, improve flexibility
  • network evaluation ($F=bits$ is the filesize, $R=bits/s$ transmission rate)
    • transmission delay $\frac{L=bits}{R=bits/s}$ (diff. min. for largest and smallest packet) : time it takes to push all bits of a packet into a link
      • careful on bottleneck link
    • propagation delay $\frac{L=length=m}{speed=2\cdot 10^8 m/s}$ (min. delay for smallest packet) : time it takes to move one bit from one end to the other
    • queuing delay $(packetsize=bits)\frac{arrival}{R=bits/s}$ (diff. average and min. delay) : time it takes to a packet in the buffer to be processed
      • average queing delay / variance of queuing delay
      • depends on traffic pattern (arrival rate, burst, transmission outgoing link)
      • queuing delay upper bound : $N\frac{L}{R}$ where $N$ packets, $L=bits$ packet size, $R=bits/s$ transmission rate
    • processing delay : time it takes to process a packet
    • store-and-forward : entire packet must arrive at router before it can go further
    • delay : time it takes to send an entire packet from its source to its destination
    • loss : fraction of packets dropped
    • throughtput (receiver window/RTT) : rate the destination is receiving data from the source (bottleneck)
    • average throughput : data size over transfer time $F/R$ (+propagation)
    • security
      • eavesdropper : listen to communication and copies data (not quantum valid)
      • impersonator : pretend to be another end-system
      • (distributed) denial of service : overload to disrupt the communication (bandwidth, connection flooding)
      • malware : infect end-system (virus requires user interaction, worm does not)
      • botnet : army of compromised end-systems

The Application Layer

  • design an application
    • architecture : which process does what
    • communication protocol : what sequence of messages can be exhanged
    • transport service : what delivery guarantees are needed
  • architecture
    • process : request, answer, always running, reachable at a fixed know process address
    • process address : 128.156.72.16 (IP), 80 (port)
    • client-server : client request server answer
      • clear separation of roles
      • dedicated infrastructure for server (one machine, datacenter)
    • peer-to-peer : client are server and vice versa
      • both roles
      • peer : personnally own-system
  • communication protocol (for example HTTP)
  • transport service
    • reliable message delivery (TCP) : complete or signals failure
    • guaranteed performance (not provided by transport-layer) : mimimum throughput (voice) or maximum end-to-end packet delay (voice)
    • guaranteed security (half-layer : SSL) : confidentiality, data integrity, authenticity
    • TCP : reliable, stateful (maintain state of communication)
    • UDP : no expectation, stateless
  • web
    • architecture : client-server
    • communication protocol : HTTP (GET, POST, PUT, DELETE to answer OK, Not Found, Moved permanently, Bad request)
    • transport service : TCP
      • persistent : less delay (client), fewer resources (server)
      • non-persistent (old) : create new TCP connection per HTTP request (GET->Connection: close)
      • one/multiple connections : parallel TCP connections
      • RTT : round-trip time
    • cookie : state kept by the server and links subsequent HTTP requests
    • web/proxy caching : copies of other web-server files, time expiration management (GET->If-modified-since: Fri, 3 OCt 2014 10:00:00)
    • url : address for web object (hostname + file name) translated to IP
  • FTP
    • transport service : TCP 21
    • new TCP connection at each transfer
  • SMTP
    • transport service : TCP 25
    • sender connect to receiver mail server
    • message must be 7-bit ASCI
    • POP3 (stateless) download and delete vs download and keep
    • IMAP (stateful) everything in one place (server)
  • DNS (Domain Name Service)
    • single DNS server does not scale -> does not work well with many users (failure, too much traffic, cannot be close, maintenance)
    • hierarchy : root servers, TLD (top-level domain) servers (.com, .ch), authoriative servers (epfl.ch, amazon.com)
    • request (recursive or iterative) : local DNS server -> root DNS server -> .ch TLD DNS server -> epfl.ch servers (each level talks only to one level down)
    • caching DNS answer at all levels to reduce delay
    • DNS queries and replies, Resource Records (RR : name, value, type, Time-To-Live)
    • different queries : A (hostname, IP), NS (domain, authoritative DNS hostname), CNAME (canonical hostname), MX (mail)
    • UDP port 53
    • attack : impersonate and send fake answer or DOS root server or poison the cache of a DNS server (multiple request on low access domains)
  • BitTorrent
    • client-server : linear $D_{CS}\ge max(\frac{NF}{u_s}, \frac{F}{d_{min}})$ where $N$ number of downloaders, $u_s$ server upload capacity, $d_{min}$ peer donwload capacity
    • p2p : sub-linearly $D_{P2P}\ge max(\frac{F}{u_s}, \frac{F}{d_{min}}, \frac{NF}{u_s+\sum u_i})$
    • sources of the metadata, IDs of peers : tracker (server, one node that keeps track of which peers have the given content) or set of peers (distributed hash table DHT : content key -> end-system identifiers, keeps track of which peers have what content)
    • sources of data : peers
    • scale
    • torrent : group of peers exchanging
    • tit-for-tat : selecting randomly new peer, send chunks to those currently sending its chunk at highest rate
    • unchoked : best four peers
    • rarest first

The Transport Layer and Socket Programming

  • socket : interface between application and transport layer
  • transport layer (communication between processes) vs network layer (communication between hosts)
  • UDP (connectionless, unreliable, unordered delivery) vs TCP (connection-oriented, flow and congestion control)
  • no delay and bandwidth guarantees
  • multiplexing (at sender) : handle data from multiple sockets, add transport header
  • dexmultiplexing (at receiver) : use header info to deliver received segments to correct socket
    • IP-layer datagram : source IP, destination IP
    • segments format (TCP/UDP) : source port # | dest port # | other header fields | data
    • TCP socket identified : (source IP address, source port, destination IP address, destination port)
    • UDP socket identified : (IP adress, port)
  • server waits for connections on welcoming socket and creates new "communication socket"
  • UDP socket : unreliable, datagram, no handshake, sender explicitly attaches the address to each packet
  • TCP socket : reliable, byte-stream oriented, handshake, welcoming socket

The Transport Layer

  • reliable data delivery (RDT) : no lost data, no duplicate data
  • await data <-> await (N)ACK : send => make packet and send <-> receive and is NACK => send <-> receive and is ACK => -
  • await packet <-> corruption check : receive and is corrupt => send NACK <-> receive and is not corrupt => send ACK, extract and deliver
  • checksum : redundant information to check integrity and/or correct corruption
  • NACK : not acknowledge
  • ACK : acknowledge, feedback from receiver to sender to overcome data corruption
  • if no (N)ACK received then it is reemitted (timeout)
  • sequence numbers : identifier for segments included in each ACK, used to disambiguate between segments
  • timeout : an expected ACK is late, used to overcome data loss
  • RDT : checksum + ACK + retransmissions + timeouts
  • sliding-window request (pipelining) : multiple requests authorized better than stop/wait
  • go-back-N : receiver accepts 0 out-of-order segments, ACK are cumulative (all segment lower than # have been received) when retransmitting all the un-ACK-ed segments
  • selective repeat : receiver accepts $N-1$ out-of-order packets, ACK are selective (segment # only has been received), retransmitting only one segments when timeout
  • busy-time : $\frac{N\cdot sendtime}{RTT+sendtime}$
  • TCP : set of resources allocated at end-systems (sockets, buffers, variables)
    • 3-way handshake
    • reliability
      • sequence number (by sender, # of first byte of data)
      • ACK number (by receiver, # of oldest byte expected)
      • timeout ($estimatedRTT+4devRTT$ with $estimatedRTT=0.875estimatedRTT+0.125sampleRTT$ and $devRTT=variance(RTT)$) : retransmit the segment with oldest un-ACKed sequence number
      • fast retransmit : if 3 duplicate ACKs received
    • flow control
      • receiver window (provided by receiver) : free space in TCP buffer
    • end with FIN/FINACK,ACK (3-way)
    • security
      • impersonate : randomized sequence number
      • syn flooding : no syn buffer but use non-forgettable tickets
    • congestion control
      • bad congestion effects (long queuing delays, resource waste)
      • at network layer : packet switches send congestion signals to end-hosts
      • at transport layer : end-hosts signal congestion to each other
      • maximum send window : $R; bps \cdot RTT; s = b$ (bandwidth-delay product)
      • ACK = no congestion (increase window size) vs no ACK = congestion (reduce window size)
      • exponentially (slow start) by 1 MSS (maximum segment size) for every ACK
      • linearly (congestion avoidance) by 1 MSS every RTT (when congestion expected)
      • start with exponential increase : if timeout, reset window to MSS and set congestion threshold to last window size divided by 2
      • transistion to linear increase when window reaches congestion threshold

The Network Layer

  • forwarding : header values correspond to output link (inside router)
  • routing : network wide process that determines end-to-end path
    • centralized vs distributed routing algorithm
  • connection setup : connection state in routers
    • virtual circuit on demand (forwarding state, per connection)
  • possible network-layer services
    • guaranteed (in-order) delivery
    • guaranteed maximum delay
    • guranteed minimum throughput
    • security (confidentiality, authenticity)
  • datagram network (forwarding state) : scales better and simpler
  • IP prefix : range of IP adresses formatted by a mask
  • IP subnet : network area without any router included, all end-systems and router have the same IP prefix
  • IP are obtain from ISP or regulatory body
  • IP are distributed by network operator to router (manually) and to end-systems (mostly DHCP)
  • private address space : subnet with one single entry using a NAT (network address translation, requires per connection)
  • IP fragmentation : router can fragment packets
  • least-cost path routing
    • link-state routing algorithm : centralized either on router or on a separate machine (Dijkstra)
    • distance-vector routing algorithm : distributed, exchange of local link cost and neighbor messages
      • poisoned reverse if a connection is lost
  • internet routing challenges
    • scale : flooding, no convergeance
    • administrative autonomy : manipulate routing
  • autonomous systems : different administration with possible differences inside (routing)
    • intra-AS routing (RIP, OSPF) : run by all router inside the same AS
    • inter-AS (BGP border gateway protocol) : router distributes reachability information to external router through e-BGP, router distributes external reachability information to other local routers through i-BGP
    • BGP selects route that crosses fewer AS, fewer local routers, higthest local preference
  • security
    • encryption symetric (RC4, AES, Blowfish)
    • encryption asymetric public + vs private - key (RSA, DSA)
    • hashes
    • confidentiality message authentication code MAC : hash key with a message
    • authenticity : asymetric encryption of nonce and message hash
      • digital signature : private encrypt hash (can check correctness with public key)
      • nonce : random string shared (avoid replay attacks)
      • need a trusted certificate authority (CA)
    • integrity
      • control hashes
    • email : asymetric encryption on symetric key
    • SSL (3-handshake way) : sever send public key, client send back a shared master key, and then create 4 session keys (a encrypting key and a MAC for each part) included sequence number

The Link Layer

  • transfer data (frame) from one node (routers, switches, hosts) to a physically adjacent node : ethernet, frame relay, WiFi
  • link layer services
    • error dection : detect bit errors, drop frames with errors
      • single bit parity (single error)
      • two dimensional bit parity (correct single bit errors)
      • cyclic redundancy check (CRC)
    • reliable data delivery : error correction/retransmission
    • link access : share same link with other nodes
    • pacing between adjacent sending and receiving nodes
  • software and hardware implemented
  • types of links
    • point-to-point (ethernet)
    • broadcast (wifi)
  • multiple access protocols
    • collision and interference could occur
    • channel partitioning (inefficient at low load) : time slots, frequency bands
    • random access (inefficient at high load) : no division, try to detected and recover from collisions
    • taking turns (best of best world) : nodes are invited to transmit by master
    • CSMA Carrier Sense Multiple Access : sense before transmitting, defer if busy
  • Carrier Sense Multiple Access (CSMA)
    • senses, wait until idle for sending
    • transmits entire frame without detecting another transmission
    • if detects another, abort and sends jam signal then enter exponential backoff
  • *Eternet *** bus (shared collision domain) vs star (unique for each ends)
  • MAC addresses : 48 bit used to move frames between link-layer nodes
  • ARP address resolution protocol : broadcasts request for MAC address
  • switch : similar to router forwarding but self-learned table and based on MAC address (if no entry, flood)
  • switch vs router : network layer (3) vs link layer (2), store-and-forward, self-learning vs routing

A day on internet

  • connecting to internet
    • DHCP to get : IP address, subnet mask, IP first-hop router, IP dns server
    • DHCP discovery message encapsulated in UDP, IP, Ethernet
    • Ethnernet broadcast on LAN (MAC 0xF)
  • learning
    • ARP to requestion MAC address of the first-hop router
    • DNS query
    • TCP