464 Final

Network Reference Model

1. Application (HTTP, DNS, IMAP, SMTP)

2. Transport (TCP, UDP, MPTCP, QUIC, End-to-end datagrams)

3. Network (IP, DSR, AODV, DSDV, ICMP)

4. Data Link (Ethernet, 802.11, Bluetooth)

5. Physical (Bits on wire)

TCP

• Reliable ordered delivery (with retransmission if necessary)

• Congestion Avoidance and Control

• ACK sent to sender as confirmation after data received by receiver

• Issues: Often guesses wrong reason for packet loss in wireless (mobility and interference usually are the reason more than congestion)

• Establish connection: Handshake 🙂 SYN (send open packet), SYN ACK (acknowledgement from dest), ACK (acknowledgement of dest ACK from src)

• Closing connection: FIN (Close and receive remaining bytes), FIN ACK (acknowledgement), RST (Reset to close and NOT receive remaining packets)

• ACKs is src’s sequence number + 1

• Sends acknowledgements to sender to confirm delivery

Window Size

• Amount of data sent per round trip time

• Receiver’s advertised window (available buffer space)

• Congestion window (determined by sender from network feedback)

Packet Loss

• Detected by Retransmission Time Out (RTO) and DUPACKs

• DUPACK: Fast Retransmission indicates packet loss if 3 DUPACKs received. Retransmit after.

• RTO: If ACK not received before RTO timer fires, packet lost. RTO doubles for each time-out.

Congestion Avoidance & Control

• Slow Start: Exponential cwnd

• Congestion Avoidance: Linear cwnd

• Slow Start Threshold (ssthresh) = max[min(min(cwnd, receiver’s adv. window / 2), 2 * Min Segment Size)]

• Fast Recovery after Fast Retransmit (No Slow Start needed)

• 3 dup acks trigger retransmission

MPTCP

• Implemented in the kernel

• Use sequence numbers to reassemble segments at the receiver

• Benefits: Higher throughput, failover from one path to another, seamless mobility

• Challenges: Out of order packets (RTT differences), hard to retransmit packet on different subflow

• Connection Established same way as TCP, except SYN ACK contains MP_CAPABLE

• ADD_ADDR and REMOVE_ADDR used to add/remove IP addresses to MPTCP connection

• MP_JOIN used to associate new subflow with existing MPTCP connection

• All subflows should add up to one TCP flow

• Contains congestion window for each subflow

• Picking a path depends. Least congested path has low loss, but high RTT, etc

• Uses key during connection setup to verify authenticity of created subflows

• Ex: Primary TCP Wifi connection, Backup TCP cellular connection

TLS/SSL (OpenSSL)

• Handshake done in clear text

• Transport Layer Security and Secure Socket Layer

• Standard for Internet Security

• Uses shared secret keys between client and sever

• Certificate Authorities (CA) verify public keys from websites

QUIC

• UDP is connectionless, so less reliable but faster than TCP

• Uses TCP congestion control

• Uses NON-blocking transport protocol

• Used for time-sensitive transmissions mostly

• Combines UDP speed with TCP reliability (hard to make changes in TCP, faster to implement new protocol on UDP)

• Lost packets only impact the individual resource

• Encrypted

• Helps with congestion control and loss recovery

Routing protocols

• Reactive (high latency, low overhead): DSR, AODV

• Proactive (low latency, high overhead): OLSR, DSDV

• Next-hop tables: AODV, OLSR, DSDV

• Floods control packets: DSR, AODV

Dynamic Source Routing (DSR)

• Route discovery

  • Src floods RREQ to each node up to Dest, each adding its own identifier when forwarding

  • Dest sends RREP through reverse route

  • Does not work for non-bidirectional routes

• Schemes reduce impact of Broadcast storm problem (multiple nodes broadcast the same message simultaneously, leading to collisions and redundancy)

• RERR received means broken link will be removed from from route cache.

• Large packet header (entire path)

• Intermediate nodes can send RREP if they already know path to dest

Ad Hoc On-Demand Distance Vector Routing (AODV)

• Maintains routing tables (with reverse path) at nodes to avoid large packet headers and improve performance.

• Uses destination sequence numbers to avoid loops

• Only maintains routes when necessary

• Doesn’t work with asymmetric routes

• Intermediate nodes can send RREP if they already know path to dest (less likely than in DSR)

• Timeout for routing tables to avoid stale routes

• Dest. Sequence numbers used to avoid old/broken routes and loop formation

Link State Routing (LSR)

• Nodes periodically floods the status of its links to all other nodes to maintain a complete view of the network (node id, cost of link to each neighbor)

• Routing table computed after LSP received for all nodes

• Uses Dijkstra’s Algorithm to find shortest path

• Not scalable

Optimized Link State Routing (OLSR)

• Optimized LSR which requires fewer nodes to forward LSP

• Multipoint relays used: each 2 step neighbor of src is a 1 hop neighbor of at least one MPR

Distance-Vector Protocol (DV)

• Nodes maintain a table (sent to neighbors periodically) of:

  • available destinations

  • next node to reach each destination

  • number of hops to each destination

• Broken links lead to loops and count to infinity

• Doesn’t do well with mobility

Destination-Sequenced Distance-Vector (DSDV)

• Uses sequence numbers to prevent loops

• Routing table:

  • Next hop

  • Cost path to each dest

  • Dest. seq num

  • Seq num

• Each time table is advertised, sequence number increases to next even number

• If dest num received from another node is greater, we change our sequence number to it and that node is the next hop
  

Routing packets

• IP address: Must be unique on the network layer

• MAC address: Must be unique only on the link layer

IP Address Autoconfiguration

• DHCP: method for dynamically assigning IP addresses to devices on a network using DAD.

• Random address selection: Useful for when there is no DHCP available but leaves potential for duplicate addresses.

• Perkins: Host picks address randomly and performs route discovery to check for duplicate address.

DAD (Duplicate Address Detection)

• Ensures address is unique within the network

• Strong DAD: Uses proactive Request - Response mechanism. Impossible to do with unbounded delays (which are common in mobile/dynamic networks)

• Weak DAD: Simple check by listening for duplicate addresses before assigning (using route discovery: DSR, RREQ and RREP sent with (IP, Key) pair and checked for mismatch)

DNS (Domain Name System)

• Used to map name to IP address using a distributed database

• Cannot be centralized because:

  • traffic volume

  • maintenance needs

  • doesn’t scale

• Root name server: gets mapping from authoritative server and returns it to local name server “idk but here’s someone that might know/here’s what someone that knows told me”

• TLD servers: .org, .net, .com, .edu

• Authoritative servers: org’s own DNS server managed by them or their service provider

• Local Name server: Forwards query to hierarchy

• Recursive query: Makes contacted name server responsible for name resolution instead of the local name server

• Caching: once a mapping is learned, it is cached

• DNS protocol/message format: Includes identification and flags for query/reply, recursion, and authoritativeness

Zeroconf

• Seamless automatic network configuration solution

• 3 requirements:

  • IP address assignment without DHCP

    • Random assignment + DAD

  • Host name resolution without DNS

    • mDNS (devices can communicate and discover each other by resolving hostnames to ip addr without DNS)

  • Local service discovery without rendezvous server

    • DNS-SD running on mDNS

    • Airplay, Chromecast

ALOHA

• Basic distributed MAC protocol (Doesn’t provide reliability)

• Lacks collision detection by itself

• Throughput = np(1-p)^(n-1)

• Window of Vulnerability: Time frame a packet is being transmitted

• Throughput decreases = Window of Vulnerability decreases

• Unslotted ALOHA: Window of vulnerability is 2L and Throughput is 1/2e

• Slotted ALOHA: Window of vulnerability is L and Throughput is 1/e

• Ideally, slot size is L, but usually it needs to be more than L for better performance

CSMA (Carrier Sense Multiple Access)

• Listens to the channel before transmitting to avoid collisions.

• Can be challenging on wireless communication because there’s limits to how the transmitter can communicate with the receiver to see if there is interference/collisions

• Can sample signal periodically or detect waveform to see if transmission is occurring

• Carrier Sense Threshold (Pcs)

• If Pr < Pcs, channel is idle

• Larger Pcs means more transmissions, greater spatial reuse, and more interference

• Smaller Pcs means increased incidence of exposed terminals

• Impact on interference:

  • Icb = Pt * gcb <= Pcs * (gcb / gac))

• Retransmission protocol (stop and wait)

  • Send packet

  • Start timer

  • Wait for ACK

  • If no ACK before timer ends, retransmit

RTS (Request to Send) and CTS (Clear to Send)

• Control messages used to reserve channel before transmitting data (reducing collision cost)

• Used when data packets are large and collisions frequent

• Other hosts will be quiet for the duration of the proposed transmission indicated in RTS/CTS

• Part of virtual carrier sensing

Busy Tone mechanism

• A transmits to B. B produces busy tone while receiving data. Helps to reduce collisions by informing other devices not to use the channel until the busy tone stops. C will transmit iff:

  • Icb = Pt * gcb <= Pcs

• Issues: Large overhead

Physical vs Virtual Carrier Sensing

• Can be used simultaneously

• Physical carrier sensing detects channel status through direct measurement, while virtual carrier sensing uses control messages like RTS/CTS to reserve the channel.

p-persistence

• Used in slotted ALOHA where a station transmits with a probability p if the channel is idle and defers if the channel is busy.

DCF (Distributed Coordination Function)

• MAC protocol that uses

  • CSMA-CA

  • Physical and virtual carrier sensing

  • CW with backoff interval [0, cw - 1]

    • Large cw = large overhead

    • Small cw = more collisions

  • Exponential backoff after packet loss

  • Avoids hidden terminal problem (Nodes can’t listen to each other and start transmitting at the same time) using RTS/CTS

• Need to manage changes in transmitting nodes?

  • Binary Exponential backoff: When node fails to receive CTS, cw is doubled and then reset after successful data transfer

PCF (Point Coordination Function)

• MAC protocol that polls of stations to grant transmission opportunities.

• More deterministic service than DCF.

IFS (Inter Frame Spacing)

• SIFS (Short IFS): Sent by receiver to sandwich CTS, ACK, polling responses. High priority.

• PIFS (PCF IFS): For time bounded service using PCF. Medium priority.

• DIFS (DCF IFS): For asynchronous data service. Sent by transmitter before RTS. Lowest priority.

• Example Process:

  • Station ready to send

  • Sense medium (Clear channel assessment)

  • If medium is free for duration of IFS, start sending

  • Else, wait for DFS + random backoff time (for collision avoidance)

  • If another station gets on medium during our backoff time, timer restarts for fairness

Infrastructure

• STA (Station): Terminal with access to wireless and contact with AP

• AP (Access Point): Station integrated into WLAN and distribution system

• BSS (Basic Service Set): Group of stations using some radio frequency

  • Adhoc networks have Independent BSS (IBSS) with interconnected stations.

• Portal: bridge to other networks

• Distribution System: forms one logical network with various BSS

  • Mesh networks include mesh gates

FEC (Forward Error Correction)

• Hamming distance: number of bits by which codewords differ

• Distance of a code: min(Hamming Distance)

• Single Error Correcting Code (SEC): More than one error results in decoding error or no error detection

• Double error detecting code: data bits and parity bits

• Issues: May not detect/correct all errors and incurs overhead

Transmit/Received Power

• W to mW = * 10³

• Power[dBW] = 10log_10 (Power[W])

• Power[dBm] = 10log_10 (Power[mW])

• Path Gain = Pr / Pt

• Path Loss = 1 / Gain

• PL[dB]=10log_10 (PL)

• SNR (Signal to Noise Ratio) = 10log_10 (Signal Power / Noise Power)

  • Low SNR = Harder to extract signal from noise

• Path Loss Model: PL(d) = PL(d0) + 10log_10 (d / d0)

• Pt / Pr = (4pi * d)^2 / lambda^2, lambda = c / f

• Ldb = 20log(f) + 10nlog(d) - 147.56

• Additive White Gaussian Noise (AWGN) Model:

  • Capacity = Wlog_2(1+SINR), SINR = Interference power + Noise Power

Signals

• Analog signal: Intensity varies smoothly over time. Less path loss than digital. Can propagate both analog and digital data.

• Digital signal: Intensity is constant and then changes to another constant. Cheaper and less sensitive to noise than analog. Can propagate both analog and digital data.

• Period signal: signal pattern that repeats

• Signal representations:

  • Amplitude vs Frequency

  • Amplitude vs Time

  • Period = 1/f

  • Phase = relative position in time with a single period

  • Wavelength (lambda) = distance of a single cycle

  • A*sin(2pi*ft + phi), A = amplitude, f = frequency, phi = phase shift

Multiplexing

• The process of carrying multiple signals over one medium.

• For protection against interference:

  • Time + Frequency Multiplexing, where a channel gets a certain frequency band for a certain time. Needs precise coordination.

Modulation (Shift Keying)

• Digital: Digital data translated into analog signals. Can be done through:

  • Amplitude Shift Keying (ASK): Inefficient. Bit 1: Constant Amp (MHz / 10 = # of cycles). Bit 0: Nothing.

  • Frequency Shift Keying (FSK): Better than ASK. Bit 1: f1 (normal). Bit 0: f2 (f1 / 2).

  • Phase Shift Keying (PSK): More Robust. Bit 1: freq. Bit 0: -freq.

• Analog: shifts center frequency of signal up Frequency Division Multiplexing

• Quadrature PSK: 2 bits encoded as 1 symbol. Needs less bandwidth.

• Quadrature Amplitude Modulation: Combines ASK and PSK. Less errors.

LTE Network

• Mobile devices interact with base stations (eNodeB) via radio signals

• Telephony subsystem: LTE radio, SIM cards (UICC), baseband processor

  • UICC: runs Java app USIM which interfaces with cell radio and mobile network. Has secret keys.

  • IMSI: Used to identify mobile subscribers.

  • RAN = Now E-UTRAN, is a mesh network of eNodeBs which UEs connect to for sending/receiving IP packets from EPC (Evolved Packet Core)

  • LTE Air Interface Protocols: Radio link between UE and eNodeB

  • Handover:

    • eNodeBs exchange Handover requests and ACKs

    • Handover command sent to UE

    • Status transfer occurs between eNodeBs

    • Handover completed

    • Path switch requests occur and ACKs with MME/S-GW

Ping pong effect

• UE has 2 equally strong signals going back and forth between towers (like a ping pong ball)

• Solve by having a handover timer, so that when measuring the difference between the signals, if it has a sustained difference, then a handover is triggered.

Zigbee

• Combats sensor network challenges

• Less complexity, power, and cost than WiFi and Bluetooth

• Great for monitoring and control operations with periodic/intermittent data

• Can support large amount of nodes and has extended battery life

• Comparable range to WiFi

• Needs 10-50% of software that WiFi and Bluetooth use

• Can use different topologies (mesh, peer-to-peer)

• Uses IEEE 802.15.4 (low rate WPAN) and CSMA-CA

• Reduced Function Devices pass data to Full Function Devices which pass data to Coordinator.