Transcript Snoop Agent

无线网络
• 3G标准
• Bluetooth
• WiFi
3G
3G：全称为3rd Generation，中文含义就是指第三代
数字通信。
 1995年问世的第一代模拟制式手机（1G）只能进行语音
通话(FDMA)；
 1996到1997年出现的第二代GSM、TDMA等数字制式手
机（2G）便增加了接收数据的功能，如接收电子邮件或
网页；
 国际电联ITU在2000年5月确定WCDMA、CDMA2000、
TD-SCDMA以及WiMAX四大主流无线接口标准，写入
3G技术指导性文件《2000年国际移动通讯计划》（简称
IMT—2000）
3G
• WCDMA，全称为Wideband CDMA，也称为CDMA Direct
Spread，意为宽频码分多路存取，这是基于GSM网发展出
来的3G技术规范，是欧洲提出的宽带CDMA技术，它与日
本提出的宽带CDMA技术基本相同，目前正在进一步融合。
• CDMA2000是由窄带CDMA(CDMA IS95)技术发展而来的宽
带CDMA技术，也称为CDMA Multi-Carrier，它是由美国高
通北美公司为主导提出，摩托罗拉、Lucent和后来加入的韩
国三星都有参与，韩国现在成为该标准的主导者。
3G
• Time Division - Synchronous CDMA(时分同步CDMA)，该
标准是由中国大陆独自制定的3G标准，1999年6月29日，
中国原邮电部电信科学技术研究院（大唐电信）向ITU提出。
该标准将智能无线、同步CDMA和软件无线电等当今国际领
先技术融于其中，在频谱利用率、对业务支持具有灵活性、
频率灵活性及成本等方面的独特优势。
• WiMAX 的全名是微波存取全球互通(Worldwide
Interoperability for Microwave Access)，又称为802.16无线
城域网，是又一种为企业和家庭用户提供“最后一英里”的
宽带无线连接方案。2007年10月19日，WiMAX正式被批准
成为继WCDMA、CDMA2000和TD-SCDMA之后的第四个
全球3G标准。
Bluetooth
• Bluetooth 技术在 2.4 GHz 波段运行，该波段是一种无需
申请许可证的工业、科技、医学 (ISM) 无线电波段；
• 蓝牙目前暂时共有四个版本 V1.1/1.2/2.0/2.1；
• 以通讯距离可分为 Class A(1)/Class B(2)，ClassA通讯
距离大约在 80~100M 距离之间，ClassB 8~30M 之间；
• UWB超宽带版本，版本于2008年中发布。整合了UWB技
术的新版蓝牙将使用户能够对大量数据同速进行和传输，
UWB技术在10米的有效范围内速率可达到480Mbps，超
过了许多应用中最高要求的200Mbps，将MP3播放器或
高画质数码相机的同速进行即是此技术的应用实例。
Wireless Networking(802.11)
wifi常见标准有以下几种：
IEEE 802.11a ：使用5GHz频段，传输速度54Mbps，与
802.11b不兼容
IEEE 802.11b ：使用2.4GHz频段，传输速度11Mbps
IEEE 802.11g ：使用2.4GHz频段，传输速度主要有
54Mbps、108Mbps，可向下兼容802.11b
IEEE 802.11n草案：使用2.4GHz频段，传输速度可达
300Mbps，目前标准尚为草案，但产品已层出不穷
目前IEEE 802.11b最常用，但IEEE 802.11g更具下一代标
准的实力，802.11n也在快速发展中。
Overview
• Physical layer
• Link layer challenges
• Internet mobility
Physical layer
• 规定工作频段
• 数据收发时的调制方法
Cellular Reuse
• Transmissions decay over distance
• Spectrum can be reused in different areas
• Different “LANs”
• Decay is 1/R2 in free space, 1/R4 in some situations
Overview
• Physical layer
• Link layer challenges
• Internet mobility
WiFi工作模式
从形成的无线网络是否存在中心访问节
点来看，分为机会网络（Opportunity
Network）和基础设施网络
（Infrastructure Network）两种类型。
机会网络（Opportunity Network ）
STA
STA
STA
无线终端自主形成通信网络
Ad Hoc Mode
和 Delay Tolerate Network
CSMA/CD Does Not Work
• Carrier sense problems
• Relevant contention at the receiver, not sender
• Hidden terminal
• Exposed terminal
A
C
B
Media access control
Why not use CSMA/CD?
CSMA/CA
(a) The hidden station problem.
(b) The exposed station problem.
MACA
• Multiple Access Collision Avoidance
• Sender send RTS (require to send) with a time to
use the radio media
• Receiver send CTS (clear to send) to sender
• Any other terminal who get the CTS will not send
data
• Multi-RTS Collision： Senders can’t receive the
CTS
MACA
工作模式（基础设施模式）
分布式系统DS
AP
AP
BSS1
BSS2
STA
STA
STA
STA
STA
无线终端通过AP接入有线网络
Infrastructure Mode
AP Finding-Active Scanning
• Host broadcast Probe
• All APs which get that Probe return a Probe
Response
• Host select a AP as its associate AP and
send Association Request
• The selected AP returns a Associate
Response
Overview
• Physical layer
• Link layer challenges
• Internet mobility (Mobility IP)
Mobility IP Addressing
• Dynamic Host Configuration (DHCP)
• Host gets new IP address in new locations
• Problems
• Host does not have constant name/address  how
do others contact host
• Naming
• Use DHCP and update name-address mapping
whenever host changes address
Mobile IP (RFC 2290)
• Interception
• Typically home agent – hosts on home network
• Delivery
• Typically IP-in-IP tunneling
• Endpoint – either temporary mobile address or
foreign agent
• Terminology
• Mobile host (MH), correspondent host (CH),
home agent (HA), foreign agent (FA)
• home address
Mobile IP (MH at Home)
Packet
Correspondent Host (CH)
Internet
Home
Mobile Host (MH)
Visiting
Location
Mobile IP (MH Moving)
Packet
Correspondent Host (CH)
Internet
Visiting
Location
Home
Home Agent (HA)
I am here
Mobile Host (MH)
Mobile IP (MH Away – Foreign
Agent)
Packet
Correspondent Host (CH)
Mobile Host (MH)
Internet
Visiting
Location
Home
Encapsulated
Home Agent (HA)
Foreign Agent (FA)
Overview
• Physical layer
• Link layer challenges
• Internet mobility
• 无线网络的传输距离与那些因素相关?
802.11b的蜂窝半径？
• 3G标准中三种标准（TDSCDMA,WCDMA,CDMA2000)的工作频段？
The end of wireless
• END
Challenge #1: Wireless Bit-Errors
Router
Computer 1
Computer 2
3
2
22
1
Burst losses lead to coarse-grained timeouts
Result: Low throughput
0
Wireless
Performance Degradation
Sequence number (bytes)
2.0E+06
Best possible
TCP with no errors
(1.30 Mbps)
1.5E+06
TCP Reno
(280 Kbps)
1.0E+06
5.0E+05
0.0E+00
0
10
20
30
40
50
60
Time (s)
2 MB wide-area TCP transfer over 2 Mbps Lucent WaveLAN
Proposed Solutions
• End-to-end protocols
• Selective ACKs, Explicit loss notification
• Split-connection protocols
• Separate connections for wired path and
wireless hop
• Reliable link-layer protocols
• Error-correcting codes
• Local retransmission
Approach Styles (End-to-End)
• Improve TCP implementations
• Not incrementally deployable
• Improve loss recovery (SACK, NewReno)
• Help it identify congestion (ELN, ECN)
• ACKs include flag indicating wireless loss
• Trick TCP into doing right thing  E.g. send extra
dupacks
Wired link
Wireless link
End-to-End: Selective Acks
4 3
6 5
Correspondent
Host
Base Station
X2
1
Mobile Host
End-to-End: Selective Acks
Correspondent
Host
ack 1
Mobile Host
Base Station
ack 1,3
ack 1,3-4
ack 1,3-5
ack 1,3-6
Approach Styles (Split Connection)
• Split connections
• Wireless connection need not be TCP
• Hard state at base station
• Complicates mobility
• Vulnerable to failures
• Violates end-to-end semantics
Wired link
Wireless link
Split Connection
3 2
X
Correspondent
Host
ack 0
X
1
D C B
Mobile Host
Base Station
ack 0
sack A
A
sack
A,B
sack
A,B,D
Congestion Window (bytes)
Split-Connection Congestion
Window
60000
Wired connection
Wireless connection
50000
40000
30000
20000
10000
0
0
20
40
60
80
100
120
Time (sec)
• Wired connection does not shrink congestion window
• But wireless connection times out often, causing sender to
stall
Approach Styles (Link Layer)
• More aggressive local rexmit than TCP
• Bandwidth not wasted on wired links
• Adverse interactions with transport layer
• Timer interactions
• Interactions with fast retransmissions
• Large end-to-end round-trip time variation
• FEC does not work well with burst losses
Wired link
Wireless link
ARQ/FEC
Hybrid Approach: Snoop Protocol
• Transport-aware link protocol
• Modify base station
• To cache un-acked TCP packets
• … And perform local retransmissions
• Key ideas
• No transport level code in base station
• When node moves to different base station,
state eventually recreated there
Snoop Protocol: CH to MH
4 3 2 1
6 5
Correspondent
Host
Snoop Agent
1
Base Station
Mobile Host
• Snoop agent: active interposition agent
• Snoops on TCP segments and ACKs
• Detects losses by duplicate ACKs and timers
• Suppresses duplicate ACKs from FH sender
Snoop Protocol: CH to MH
Snoop Agent
65 3 2
4 1
Correspondent
Host
Base Station
• Transfer of file from CH to MH
• Current window = 6 packets
Mobile Host
Snoop Protocol: CH to MH
65
Snoop Agent
4
3
2
Correspondent
Host
• Transfer begins
1
Base Station
Mobile Host
Snoop Protocol: CH to MH
4 3 2 1
6 5
Correspondent
Host
Snoop Agent
1
Base Station
Mobile Host
• Snoop agent caches segments that pass by
• Difference #1 from pure link-layer – does not add
a new header uses existing TCP header to
identify losses
Snoop Protocol: CH to MH
4 3 2 1
6 5
Correspondent
Host
• Packet 1 is Lost
Snoop Agent
3 2 1
Base Station
Mobile Host
1
Lost Packets
Snoop Protocol: CH to MH
5 4 3 2 1
6
Snoop Agent
4 3
2
ack 0
Correspondent
Host
Base Station
• Packet 1 is Lost
• Duplicate ACKs generated
Mobile Host
1
Lost Packets
Snoop Protocol: CH to MH
6
5 4 3 2 1
Snoop Agent
6
5
4
3
2
1
ack 0
Correspondent
Host
Base Station
ack 0
Mobile Host
1
Lost Packets
• Packet 1 is Lost
• Duplicate ACKs generated
• Packet 1 retransmitted from cache at higher
priority
Snoop Protocol: CH to MH
6
5 4 3 2 1
Snoop Agent
6
5
1
4
3
2
ack 4
Correspondent
Host
Base Station
ack 0
Mobile Host
X
• Duplicate ACKs suppressed
• Difference #2 from pure link-layer – tries to
prevent sender from noticing loss
• Sender may still timeout though – fortunately timeouts
are typically long (500ms+)
Snoop Protocol: CH to MH
6
5
Snoop Agent
6
5 1
4
3
2
ack 5
Correspondent
Host
Base Station
ack 4
• Clean cache on new ACK
Mobile Host
Snoop Protocol: CH to MH
6
ack 4
Correspondent
Host
Snoop Agent
6 51
4
3
2
ack 6
Base Station
ack 5
• Clean cache on new ACK
Mobile Host
Snoop Protocol: CH to MH
Snoop Agent
9
8
Correspondent
Host ack 5
7
Base Station
ack 6
• Active soft state agent at base station
• Transport-aware reliable link protocol
• Preserves end-to-end semantics
6 51
4
3
2
Mobile Host
Snoop Data Processing
Packet arrives
New pkt?
No
Sender retransmission
Yes
In-sequence?
1. Forward pkt
2. Reset local rexmit
counter
No
Yes
1. Cache packet
2. Forward to
mobile
Common case
1. Mark as cong. loss
2. Forward pkt
Congestion loss
Snoop ACK Processing
Ack arrives (from mobile host)
New ack?
Yes
No
Discard
No
Spurious ack
Discard
1. Free buffers
2. Update
RTT estimate
3. Propagate
ack to sender
Common case
Dup ack?
Yes
No
Later dup acks
for lost packet
> threshold
Yes
Retransmit
lost packet
Next pkt lost
Overview
• Link layer challenges
• Internet mobility
• TCP Over Noisy Links
• Adapting Applications to Slow Links
Adapting Applications
• Applications make key assumptions
• Hardware variation
• E.g. how big is screen?
• Software variation
• E.g. is there a postscript decoder?
• Network variation
• E.g. how fast is the network?
• Reason why we are discussing in this class 
• Basic idea – distillation
• Transcode object to meet needs of mobile host
Transcoding Example
• Generate reduced
quality variant of Web
page at proxy
• Must predict how much
size reduction will result
from transcoding
• How long to transcode?
• Send appropriate
reduced-size variant
• Target response time?
Source Adaptation
• Can also just have source
provide different versions
• Common solution today
• No waiting for transcoding
• Full version not sent across
network
• Can’t handle fine grain adaptation