Courses/Computer Science/CPSC 441.W2014/Chapter 6: Wireless and Mobile Networks

From wiki.ucalgary.ca
< Courses‎ | Computer Science‎ | CPSC 441.W2014
Revision as of 06:44, 29 April 2014 by Cmah (talk | contribs) (Section 6.3: IEEE 802.11 Wireless LANs (Wi-Fi))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Navigation

Course Overview

Application Layer

Transport Layer

Network Layer

Datalink Layer

Advanced Topics

Extra

Networking Basics

Chapter 2

Chapter 3

Chapter 4

Chapter 5

Chapter 7

Tutorials

Chapter 1

HTTP Over TCP

Chapter 6

Links

Quiz Review

Textbook Notes

Introduction

Hello, my name is Carrie Mah and I am currently in my 3rd year of Computer Science with a concentration in Human Computer Interaction. I am also an Executive Officer for the Computer Science Undergraduate Society. If you have any questions (whether it be CPSC-related, events around the city, or an eclectic of random things), please do not hesitate to contact me.

I hope you find my notes useful, and if there are any errors please correct me by clicking "Edit" on the top of the page and making the appropriate changes. You should also "Watch this page" for the CPSC 441 page to check when I upload notes. Just click "Edit" and scroll down to check mark "Watch this page."

You are welcome to use my notes, just credit me when possible. If you have any suggestions or major concerns, please contact me at cmah[at]ucalgary[dot]ca. Thanks in advance for reading!

Chapter 6: Wireless and Mobile Networks

  • Notes adapted from slides created by JFK/KWR and lectures held by Dr. Carey Williamson
  • All material copyright 1996-2012 © J.F Kurose and K.W. Ross, All Rights Reserved

Section 6.1: Introduction

  • Background:
  • Number of wireless (mobile) phone subscribers now exceeds number of wired phone subscribers (5-to-1)
  • Number of wireless Internet-connected devices equals number of wireline Internet-connected devices
  • Laptops, Internet-enabled phones promise anytime untethered Internet access
  • Two important (but different) challenges
  • Wireless: communication over wireless link
  • Mobility: handling the mobile user who changes point of attachment to network

Elements of a Wireless Network

BkCxIHA.png
  • Wireless hosts
  • Laptop, smartphone
  • Run applications
  • May be stationary (non-mobile) or mobile
  • Wireless does not always mean mobility
  • Base station
  • Typically connected to wired network
  • Relay - responsible for sending packets between wired network and wireless host(s) in its 'area'
  • E.g. cell towers, 802.11 access points
  • Cell towers are points of connectivity
  • Wireless link
  • Typically used to connect mobile(s) to base station
  • Also used as backbone link
  • Multiple access protocol coordinatse link access
  • Various data rates, transmission distance
  • Infrastructure mode
  • Base station connects mobiles into wired network
  • Handoff: mobile changes base station providing connection into wired network
  • Activate device in ad-hoc mode and send frames back and forth
o203ET8.png
  • Ad-hoc mode
  • No base stations
  • Nodes can only transmit to other nodes within link coverage
  • Nodes organize themselves into a network: route among themselves
  • Don't need internet, can send data directly to and from devices
Wireless Network Taxonomy
Single Hop Multiple Hops
Infrastructure
  • Host connects to base station (WiFi, WiMAX, cellular) which connects to larger internet
  • Host may have to relay through several wireless nodes to connect to larger Internet mesh net
No infrastructure
  • No base station, no connection to larger Internet (Bluetooth, ad hoc nets)
  • No base station, no connection to larger Internet. May have to relay to reach other a given wireless node MANET, VANET

Back to Navigation

Section 6.2: Wireless Links, Characteristics

Link characteristics

  • Important differences from wired link make communication across (even a point to point) wireless link more difficult
  • Decreased signal strength: radio signal attenuates as it propagates through matter (path loss)
  • Interference from other sources: standardized wireless network frequencies (e.g. 2.4 GHz) shared by other devices (e.g. phone); devices (motors) interfere as well
  • Multipath propagation: radio signal reflects off objects ground, arriving at destination at slightly different times

Network characteristics

et3qKvz.png
  • Multiple wireless senders and receivers create additional problems (beyond multiple access):
  • Hidden terminal problem:
  • B, A hear each other
  • B, C hear each other
  • A, C can not hear each other; means A, C unaware of their interference at B
  • Signal attenuation:
  • B, A hear each other
  • B, C hear each other
  • A, C can not hear each other interfering at B

Code Division Multiple Access (CDMA)

  • Unique "code" assigned to each user; i.e. code set partitioning
  • All users share same frequency, but each user has own "chipping" sequence (i.e. code) to encode data
  • Allows multiple users to "coexist" and transmit simultaneously with minimal interference (if codes are "orthogonal")
  • Encoded signal = (original data) * (chipping sequence)
  • Decoding: inner-product of encoded signal and chipping sequence

Back to Navigation

Section 6.3: IEEE 802.11 Wireless LANs (Wi-Fi)

IEEE 802.11x Wireless LAN
802.11a 802.11b 802.11g 802.11n
  • 5-6 GHz range
  • Up to 54 Mbps
  • In less crowded: better data rates, lower interference, better signal quality
  • 2.4-5 GHz unlicensed spectrum
  • Up to 11 Mbps
  • Direct sequence spread spectrum (DSSS) in physical layer
  • All hosts use same chipping code
  • 2.4-5 GHz range
  • Up to 54 Mbps
  • Multiple antennae
  • 2.4-5 GHz range
  • Up to 200 Mbps
  • Has higher data rates
  • All use CSMA/CA for multiple access
  • All have base-station and ad-hoc network versions
  • Channel-access protocol:
  • Carrier sends multiple access with collision avoidance
  • 802.11 is a gateway – wireless on one side, and Ethernet/wired on the other interface (to hub, switch or router)
  • When deploying access points, can name them
  • Can have many access points with same logical name

802.11 LAN Architecture

aHjY10H.png
  • Wireless host communicates with base station
  • Base station = access point (AP)
  • Base Service Set (BSS) (aka 'cell') in infrastructure mode contains:
  • Wireless hosts
  • Access point (AP): base station
  • Ad hoc mode: hosts only

802.11: Channels, Association

  • 802.11b:
  • 2.4GHz - 2.485GHz spectrum divided into 11 channels at different frequencies
  • AP admin chooses frequency for AP
  • Interference possible: channel can be same as that chosen by neighboring AP
  • Host: must associate with an AP
  • Scans channels, listening for beacon frames containing AP’s name (SSID) and MAC address
  • Selects AP to associate with
  • May perform authentication [Chapter 8]
  • Will typically run DHCP to get IP address in AP’s subnet
  • Within frequency range assigned for 11b, can have 14 different channels but they can overlap
  • Channel 1, 6, 11 are main techniques
  • How typically deployed – configure one access point on 1, 6, 11; don’t interfere because they’re on different ports of frequency spectrum
  • CSMA/CA (CSMA with Collision Avoidance)
  • Can have many access points with same name
  • Allows you to have the same internet access/authenticate no matter where you go (e.g. airuc)

802.11: Scanning

yzmm5Cp.png
  • Passive scanning:
(1) Beacon frames sent from APs
(2) Association request frame sent: H1 to selected AP
(3) Association response frame sent from selected AP to H1
  • Typical access point sends a frame (broadcasting) to let devices know it exists and can be used (tells signal strength, MAC address, services it offers, etc.)
XHypZ5C.png
  • Active scanning:
(1) Probe request frame broadcast from H1
(2) Probe response frames sent from APs
(3) Association request frame sent: H1 to selected AP
(4) Association response frame sent from selected AP to H1
  • Query a network to see which access points are available (gets some information) and once it knows about existing APs then it requests access
  • Typical access point sends out beacon frames every 100 ms advertising its presence


802.11: Multiple Access

  • Avoid collisions: 2+ nodes transmitting at same time
  • 802.11: CSMA - sense before transmitting
  • Don’t collide with ongoing transmission by other node
  • 802.11: no collision detection
  • Difficult to receive (sense collisions) when transmitting due to weak received signals (fading)
  • Can’t sense all collisions in any case: hidden terminal, fading
  • Goal: avoid collisions: CSMA/CA

802.11 MAC Protocol: CSMA/CA

  • 802.11 sender
1 if sense channel idle for DIFS then
transmit entire frame (no CD)
2 if sense channel busy then
start random backoff time
timer counts down while channel idle
transmit when timer expires
if no ACK, increase random backoff interval, repeat 2
when a station has a frame to send:
  listen to channel
  IF idle
  THEN transmit
  IF busy
  THEN defer
IF collision // absence of ACK for data sent
THEN wait random time and try again
  • 802.11 receiver
if frame received OK
return ACK after SIFS (ACK needed due to hidden terminal problem)
bTzNj6d.png
  • Connectionless model, but still have ACKs
  • SIFS (short interface frame) compared to large DIFS (distributed interface space)
  • When green is successful, SIFS is small
  • Station allowed to grab channel and send back ACK (first channel allowed after frame sent)
  • Timeout and retransmit data if no ACK received

IEEE 802.11 - Main MAC Protocols

(1) Distributed Coordination Function (DCF) aka CSMA/CA
  • Mandatory for 802.11 (access point, mobile device, wireless)
  • Participate with others as you share network with them
  • CSMA/CA mechanism
  • Wireless is half duplex (single antenna)
(2) Request to Send/Clear to Send (RTS/CTS)
  • Optional, all 802.11 products support DCF, but not all support RTS/CTS
(3) Polling Coordination Function (PCF)
  • Access point queries each station in turn to see if they have something to send
  • Timing guarantees, real-time
  • Optional (similar to RTS/CTS)
  • Most equipment supports 1 and 2, very little supports 3

Avoiding Collisions

  • Idea: allow sender to "reserve" channel rather than random access of data frames: avoid collisions of long data frames
  • Sender first transmits small request-to-send (RTS) packets to BS using CSMA
  • RTSs may still collide with each other (but they’re short)
  • BS broadcasts clear-to-send CTS in response to RTS
  • CTS heard by all nodes
  • Sender transmits data frame
  • Other stations defer transmissions
  • Avoid data frame collisions completely using small reservation packets
  • Permission-based variation that reserves the channel
  • Uses short control frames (RTS) and CTS to negotiate and tell other stations that you’re about to use the network and reserve it for a particular time period

RTS-CTS Collision Avoidance Exchange

I9nWTSS.png
  • Station A, B have big data frames to send over network
  • RTS/CTS says negotiating use of channel so bulk of time is used on successful transmission of frames
  • Control frames are short
  • Collision on tiny little frame – wastes a few ms
  • Timeout and retry, perhaps A goes first and RTS is successful and access point gives you permission as a CTS broadcast; access point tells station A they have some time to send data
  • Station B has to shut up for some ms so A can send data frame
  • Send data frame and when it’s done, get an ACK from receiver’s access point and A knows it was successful and B knows A is done

802.11 Frame Format: Addressing

p5qq86u.png
  • Address 1: MAC address of wireless host or AP to receive this frame
  • Address 2: MAC address of wireless host or AP transmitting this frame
  • Address 3: MAC address of router interface to which AP is attached
  • Address 4: Used only in ad hoc mode
  • Variable sized frames support larger frames than Ethernet
  • Payload in wireless frame – a couple of kb
  • Duration of reserved transmission time (RTS/CTS)
  • Frame control is 16 bits
  • To go out on internet infrastructure, or from internet, power management for polling access
  • Type: frame type (RTS, CTS, ACK, data)
  • Control frame: like an ACK, RTS/CTS (subtype tells you this)
  • Management: association frames when you’re connecting with wireless access point, have to do association request and grants; access point registering your device in its vicinity and updating cache to forward to link layer
  • Data: send actual data
NLk0bUI.png
  • Router has interface to wireless side called R1
  • Access point is boundary between wireless in leftmost bubble, and black wired Ethernet goes to the router
  • Frame being sent from H1 (address 2 is source addr)
  • Frame goes to address 1, destination, access point
  • Once access point gets the frame, it forwards it to MAC addr of this interface on router so the frame can go on the internet
  • Addr1: where it’s going
  • Addr2: who sent it
  • Addr3: how it’s going to traverse and get to the internet
  • When access point done with frame, send it on router

802.11: Mobility Within Same Subnet

b4MKwgl.png
  • H1 remains in same IP subnet: IP address can remain same
  • Switch: which AP is associated with H1?
  • Self-learning (Chapter 5): switch wil see frame from H1 and 'remember' which switch port can be used to reach H1
  • Fall out of range from one access point, and move within range of another access point
  • Go through dissociation with previous, association with new one; any time it sends frames to forward onto internet, switch through self-learning property, wireless device changes access points

Demo: IP Address and Moving Locations

  • What if you’re moving far away?
  • Everyone is an internet router, Carey is internet use connected to UofC network with IP address 136.159.62.12
  • Carey in Calgary, goes to Victoria, and issues arise
  • Suppose when he’s in Calgary, he has Internet chat app and sends packets to people
  • Internet routers send a packet to the UofC network, and UofC router queries for the IP address and Carey receives the packet
  • Carey travels to Victoria (in a minute) and he needs to be involved with the UVic router
  • Issue: from Calgary to Victoria, using DHCP to allocate an IP address in Victoria, receive that IP address; breaks the chat
  • Doesn’t know new IP – transport level endpoint has changed, and TCP connects those endpoints (IP address : port); broken TCP connection and an no longer receive IP packets
  • Issue: No reason for UofC to send to Victoria because IP address is in its own network
  • UofC has a cache from IP to MAC address – stick it in an Ethernet frame and send through Ethernet for device to receive. They’re not there, packet gets dropped
  • Transmitted in UofC network but Carey is in Victoria’s network
  • If not in cache, asks who has the IP
  • Solution: mobile IP
  • IP address and port changes (transport layer end point) and breaks TCP connection
  • Need to map MAC address for given IP address in ARP cache

Section 6.6: Mobile IP

  • IETF [RFC 3344]
  • Allows mobile host to keep its IP address wherever it goes
  • Keeps connections alive
  • Needs HA, FA, registration, etc.
  • Network device Home Agent (HA)
  • Not a router, another type of middlebox; software on work station to support mobile users
  • Foreign Agent
  • Another software functionality in Victoria to support mobile users
  • Start in Calgary with normal IP address, travel to Victoria
  • In Victoria, query/listen to network to find out where DHCP server is, where routers are, etc.
  • What services offered and register with FA – stay on network, register with the software with IP
  • Send message to HA – stay on network, register with the software with IP
  • Packets forwarded to UofC router and looks for the IP address – MAC address of Carey’s machine
  • Registered with HA, did a proxy ARP: ARP on Carey’s behalf – IP address associated with HA mac address, went into ARP cache and router sent to HA
  • HA uses in-IP encapsulation and send to FA
  • UofC gets that new packet and UCic gets the IP packet and opens it, addressed to FA
  • Delivers to FA and FA opens it and it’s addressed to Carey’s IP and MAC address registered with FA
  • When Carey goes back to UofC network, re-registers with them and unregisters with FA, any normal data is encapsulated in link layer frame


  • Has many features we've seen:
  • HA, FA, FA registration, care-of-addresses, encapsulation (packet-within-packet)
  • Three components to standard:
  • Indirect routing of datagrams
  • Agent discovery
  • Registration with home agent
  • Changing access points within the same subnet is easy - host can retain same IP address

Back to Navigation

Wireless Internet: The Good, The Bad, and The Ugly

  • Notes adapted from slides created by Dr. Carey Williamson with help from Guangwei Bai, Jean Cao, Mingwei Gong, Abhinav Gupta, Tianbo Kuang, Hongxia Sun, Ian Wormsbecker, Qian Wu, and the rest of his iCORE research team, and lectures held by Dr. Carey Williamson

Internet Protocol Stack

  • Application: supporting network applications and end-user services
  • FTP, SMTP, HTTP, DNS, NTP, ...
  • Transport: end to end data transfer
  • TCP, UDP, RTP, SCTP, XTP
  • Network: routing of datagrams from source to destination
  • IPv4, IPv6, BGP, RIP, routing protocols
  • Data Link: frames, channel access, flow/error control
  • PPP, Ethernet, IEEE 802.11a/b/g
  • Physical: raw transmission of bits
  • Wireless lives at layers 1 and 2 only
  • Data link: LLC (interface to the upper layer protocols, 802.2) and MAC (802.11)
  • Physical layer: LAN (10BaseT, 10Base2, 10BaseFL), WLAN (FHSS, DSSS, IR)

Wireless Networking

  • The use of infra-red (IR) or radio frequency (RF) signals to share information and resources between devices
  • A hot computer industry buzzword:
  • Wireless Broadband, 3G wireless, 4G, WAP, iMode, Bluetooth, WiFi, WiMax,...
  • Enabler for Mobile Internet, M-Commerce, Pervasive Computing, Nomadic Computing
  • Ubiquitous; Global; Revolutionary

Selected Features of 802.11

  • Infrastructure mode and "ad hoc" mode
  • Access Point (AP) sends "beacons"
  • Choose AP based on signal strength
  • Multiple channel access protocols allowed
  • CSMA/CA (DCF) and RTS/CTS
  • MAC-layer can provide error control, retransmission, rate adaptation, etc.
  • Direct Sequence Spread Spectrum (DSSS)
  • Signal spread across 14 22-MHz channels

The Good

  • WiFi is convenient and flexible
  • Supports tetherless computing, mobility
  • WiFi is widely available, easy to use, and cheap (often free!); becoming social norm
  • Email on the go: airports, hotels, coffee shops, etc.
  • Innovative ways of deploying/using WiFi
  • Guerilla.net: power to the people!
  • Portable networks, Community Nets, WiMesh, etc.
  • WiFi is an enabling technology
  • Especially in developing regions
  • Economical solution for Internet deployment
Wireless Community Networks vs Portable Networks
Wireless Community Networks Portable Networks
  • Install wireless AP at home
  • Offer free public Internet access for neighbors, colleagues, visitors...
  • "Open networks": owned and operated by the people that use them
  • Popular grass roots movement started in Boston, San Francisco...
  • Cheap (free) access and reciprocity
  • Classroom area network (e.g. 'legacy classroom')
  • Press conferences, media events
  • Conventions and trade shows
  • Disaster recovery sites
  • Schools
  • Voting

The Bad

  • Wireless is a Broadcast Technology
  • Your Network is My Network
  • Wireless Users are Naïve
  • Vulnerability of Personal Data
  • WEP is Useless
  • Security issues, performance issues, weird things that could happen

Broadcast Technology

  • Broadcast means "shared channel"
  • All stations see all transmissions
  • In normal use, stations simply ignore and discard frame transmissions that are not addressed to them
  • In malicious use, stations can easily capture copies of all packet traffic seen using "promiscuous mode"
  • Transmission range not easily limited (signals can pass through walls!)

Wired Equivalent Privacy

  • WEP weaknesses well documented:
  • Can determine WEP key in 15 minutes
  • Tools available on Internet (e.g. AirAsnort)
  • 802.11i should improve the situation

The Ugly

(1) Inefficiencies of IEEE 802.11b WLANs
(2) TCP over Wireless Networks
(3) Wireless TCP Fairness Issues
(4) TCP over Mobile Ad Hoc Networks
(5) The Wireless "Bad Apple" Phenomenon
  • Weird things – composing things across different layers, cracks emerge

Example: TCP

  • The Transmission Control Protocol (TCP) is the protocol that sends your data reliably
  • Used for e-mail, Web, FTP, telnet, etc.
  • Makes sure that data is received correctly: right data, right order, exactly once
  • Detects and recovers from any problems that occur at the IP network layer
  • Mechanisms for reliable data transfer:
  • Sequence numbers, ACKs, flow control, timers, retransmissions, congestion control...

(1) WiFi Inefficiency

  • For an 11 Mbps IEEE 802.11b WLAN, the achievable effective throughput at the user-level is about 5.2 Mbps
  • Assumes single user, bulk data transfer, fast laptop, no collisions, no errors
  • Theoretical maximum is about 60%
  • Practical configurations rarely achieve more than about 50% efficiency
  • Similar observations apply for 802.11a/g


  • Which is faster? 11 Mbps or 10 Mbps
  • Depends - bandwidth size for a given connection
  • Two solutions to network setup (connection between two computers)
  • 11 Mbps IEEE 802.11b (recall wireless)
  • FTP ~6 Mbps
  • 10 Mbps Classic Ethernet
  • FTP ~9 Mbps
  • Why?
  • In 11, you wait for different times to ensure channel is empty
  • Other side after receiving frame waits and shifts the time
  • In 11, lots of overhead - lose about 50% of bandwidth efficiency/throughput over wireless
  • Wireless has adaptive rate, depending on signal strength; if signal is strong then data can be sent at full capacity

(2) TCP Over Wireless

  • Wireless TCP performance problems
  • Wireless access - low capacity (data rate), high error rate
  • Wired internet - high capacity (data rate), low error rate
  • Hard to distinguish losses in wireless access from losses in wired
  • TCP gets confused when packets get lost
  • Solution: "Wireless-aware TCP" (I-TCP, ProxyTCP, Snoop-TCP, split connections...)
  • The assumption that loss = congestion no longer applies

(3) Fairness Issues

  • Wireless bottleneck
  • Loss of ACK =/= loss of data
  • Uploader vs downloader
  • Uploader wins
  • Connection at internet is a lot faster than internet network (faster to send out data than to bring it in)

(4) TCP over Ad Hoc

  • Mobile 'ad hoc' networking
  • Problem: TCP vs Dynamic ad hoc routing
  • Node movement can disrupt the IP routing path at any time, disrupting TCP connection
  • Yet another way to lose packets
  • Route discovery delays are unpredictable
  • Can vary from 10 ms to 5 s or more [Gupta 2004]
  • Possible solutions:
  • Explicit Loss Notification (ELN) [Balakrishnan et al.1998]
  • Wireless loss inference techniques [Liu et al. 2003]
  • Fast TCP handoffs [Tan et al. 1999]

(5) Wireless Streaming

  • "Bad apple" phenomenon
  • One user with poor or transient wireless connectivity in the WLAN disrupts performance for everyone
  • Why?
  • Shared broadcast WLAN
  • Lots of MAC-layer retransmissions
  • Never gets ACKs from someone who left; server thinks they're not getting data
  • FIFO server queue (from video server)
  • Point when Carey's packet is at the front of the queue, waiting for ACKs, retransmit, repeat; eventually drops packets
  • Transmits to other uses, then Carey's packet shows up again
  • Essentially slows down
  • Head of Line (HOL) blocking
  • Packet at front of queue causes blocking
  • Solutions
  • Disable MAC-layer retransmissions
  • Can do this, not recommended
  • Multiple queues and packet scheduling
  • Station-based adaptation
  • Separate queues, one for each station/user
  • Recommended, as server queues independently
  • If one doesn't 'work' just shut it off
  • Possible to have a separate queue solely for retransmissions

Summary

  • Wireless Internet is wonderful!
  • Affordable, convenient, and easy to use
  • Widely available, useful, exciting, and fun
  • Wireless Internet is scary
  • Security risks, naïve users, vulnerable data
  • "Wireless Security" is an oxymoron
  • Wireless Internet ain’t perfect
  • Slow, inefficient, inconsistent, and unfair
  • Subtle and unique performance anomalies

Back to Navigation