464 Exam 2 content

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

• Lacks collision detection by itself

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

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

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

CSMA (Carrier Sense Multiple Access)

• Listens to the channel before transmitting to avoid 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 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

• 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

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.