Transcript PPT - EECS

Wireless and
Mobile Networks
EECS 489 Computer Networks
http://www.eecs.umich.edu/courses/eecs489/w07
Z. Morley Mao
Monday March 19, 2007
Acknowledgement: Some slides taken from Kurose&Ross
1
Mobile IP
 RFC 3220
 has many features we’ve seen:
 home agents, foreign agents, foreign-agent
registration, care-of-addresses, encapsulation
(packet-within-a-packet)
 three components to standard:
 indirect routing of datagrams
 agent discovery
 registration with home agent
2
Mobile IP: indirect routing
foreign-agent-to-mobile packet
packet sent by home agent to foreign
agent: a packet within a packet
dest: 79.129.13.2
dest: 128.119.40.186
dest: 128.119.40.186
Permanent address:
128.119.40.186
dest: 128.119.40.186
Care-of address:
79.129.13.2
packet sent by
correspondent
3
Mobile IP: agent discovery
 agent advertisement: foreign/home agents advertise
service by broadcasting ICMP messages (typefield = 9)
0
type = 9
24
checksum
=9
code = 0
=9
H,F bits: home
and/or foreign agent
R bit: registration
required
16
8
standard
ICMP fields
router address
type = 16
length
registration lifetime
sequence #
RBHFMGV
bits
reserved
0 or more care-ofaddresses
mobility agent
advertisement
extension
4
Mobile IP: registration example
home agent
HA: 128.119.40.7
foreign agent
COA: 79.129.13.2
visited network: 79.129.13/24
ICMP agent adv.
COA: 79.129.13.2
….
registration req.
COA: 79.129.13.2
HA: 128.119.40.7
MA: 128.119.40.186
Lifetime: 9999
identification: 714
encapsulation format
….
Mobile agent
MA: 128.119.40.186
registration req.
COA: 79.129.13.2
HA: 128.119.40.7
MA: 128.119.40.186
Lifetime: 9999
identification:714
….
registration reply
time
HA: 128.119.40.7
MA: 128.119.40.186
Lifetime: 4999
Identification: 714
encapsulation format
….
registration reply
HA: 128.119.40.7
MA: 128.119.40.186
Lifetime: 4999
Identification: 714
….
5
Components of cellular network architecture
recall:
correspondent
wired public
telephone
network
MSC
MSC
MSC
MSC
MSC
different cellular networks,
operated by different providers
6
Handling mobility in cellular networks
 home network: network of cellular provider you
subscribe to (e.g., Sprint PCS, Verizon)
 home location register (HLR): database in home
network containing permanent cell phone #,
profile information (services, preferences,
billing), information about current location
(could be in another network)
 visited network: network in which mobile currently
resides
 visitor location register (VLR): database with
entry for each user currently in network
 could be home network
7
GSM: indirect routing to mobile
home
network
HLR
2
home MSC consults HLR,
gets roaming number of
mobile in visited network
correspondent
home
Mobile
Switching
Center
1
3
VLR
Mobile
Switching
Center
4
Public
switched
telephone
network
call routed
to home network
home MSC sets up 2nd leg of call
to MSC in visited network
mobile
user
visited
network
MSC in visited network completes
call through base station to mobile
8
GSM: handoff with common MSC
 Handoff goal: route call via
new base station (without
interruption)
 reasons for handoff:
VLR Mobile
Switching
Center
old
routing
old BS

new
routing

new BS

stronger signal to/from new
BS (continuing connectivity,
less battery drain)
load balance: free up channel
in current BS
GSM doesn’t mandate why to
perform handoff (policy), only
how (mechanism)
 handoff initiated by old BS
9
GSM: handoff with common MSC
VLR Mobile
Switching
Center 2
4
1
8
old BS
5
7
3
6
new BS
1. old BS informs MSC of impending
handoff, provides list of 1+ new BSs
2. MSC sets up path (allocates resources)
to new BS
3. new BS allocates radio channel for use
by mobile
4. new BS signals MSC, old BS: ready
5. old BS tells mobile: perform handoff to
new BS
6. mobile, new BS signal to activate new
channel
7. mobile signals via new BS to MSC:
handoff complete. MSC reroutes call
8 MSC-old-BS resources released
10
GSM: handoff between MSCs
 anchor MSC: first MSC
visited during call
home network
correspondent
Home
MSC

call remains routed
through anchor MSC
 new MSCs add on to end
anchor MSC
PSTN
MSC
MSC
MSC
(a) before handoff
of MSC chain as mobile
moves to new MSC
 IS-41 allows optional
path minimization step
to shorten multi-MSC
chain
11
GSM: handoff between MSCs
 anchor MSC: first MSC
visited during cal
home network
correspondent
Home
MSC

call remains routed
through anchor MSC
 new MSCs add on to end
anchor MSC
PSTN
MSC
MSC
MSC
(b) after handoff
of MSC chain as mobile
moves to new MSC
 IS-41 allows optional
path minimization step
to shorten multi-MSC
chain
12
Mobility: GSM versus Mobile IP
GSM element
Comment on GSM element
Mobile IP element
Home system
Network to which the mobile user’s
permanent phone number belongs
Home
network
Gateway Mobile
Switching Center,
or “home MSC”.
Home Location
Register (HLR)
Home MSC: point of contact to obtain
routable address of mobile user. HLR:
database in home system containing
permanent phone number, profile
information, current location of mobile
user, subscription information
Home agent
Visited System
Network other than home system where
mobile user is currently residing
Visited
network
Visited Mobile
services Switching
Center.
Visitor Location
Record (VLR)
Visited MSC: responsible for setting up
calls to/from mobile nodes in cells
associated with MSC. VLR: temporary
database entry in visited system,
containing subscription information for
each visiting mobile user
Foreign
agent
Mobile Station
Roaming Number
(MSRN), or
“roaming number”
Routable address for telephone call
segment between home MSC and
visited MSC, visible to neither the mobile
nor the correspondent.
Care-ofaddress
13
Wireless, mobility: impact on higher layer protocols
 logically, impact should be minimal …
best effort service model remains unchanged
 TCP and UDP can (and do) run over wireless, mobile
 … but performance-wise:
 packet loss/delay due to bit-errors (discarded
packets, delays for link-layer retransmissions), and
handoff
 TCP interprets loss as congestion, will decrease
congestion window un-necessarily
 delay impairments for real-time traffic
 limited bandwidth of wireless links

14
Chapter 6 Summary
Wireless
 wireless links:



capacity, distance
channel impairments
CDMA
 IEEE 802.11 (“wi-fi”)
 CSMA/CA reflects
wireless channel
characteristics
 cellular access
 architecture
 standards (e.g., GSM,
CDMA-2000, UMTS)
Mobility
 principles: addressing,
routing to mobile users



home, visited networks
direct, indirect routing
care-of-addresses
 case studies
 mobile IP
 mobility in GSM
 impact on higher-layer
protocols
15
MPLS is used today!
 % traceroute -q1 -w2 www.att.net























traceroute to www.att.net (204.127.135.135), 30 hops max, 46 byte packets
1 eecscomp2-4 (141.213.4.1) 0.291 ms
2 141.213.127.37 (141.213.127.37) 0.305 ms
3 ge-caen-bin-seb.r-bin-seb.umnet.umich.edu (192.122.183.53) 0.515 ms
4 pc-bin-arb-seb.r-bin-arb.umnet.umich.edu (192.122.183.193) 0.621 ms
5 ge-1-1-0x984.aa1.mich.net (192.122.183.45) 0.660 ms
6 65.77.89.177 (65.77.89.177) 2.002 ms
7 brvwil1wcx2-pos14-1.wcg.net (64.200.240.33) 8.129 ms
8 64.200.249.186 (64.200.249.186) 7.904 ms
9 te-4-4.car2.Chicago1.Level3.net (4.68.110.37) 8.259 ms
10 ae-14-53.car4.Chicago1.Level3.net (4.68.101.72) 215.627 ms
11 ggr2-p3110.cgcil.ip.att.net (192.205.33.185) 9.075 ms
12 tbr2-p033301.cgcil.ip.att.net (12.123.6.26) 32.783 ms
MPLS Label=32719 CoS=0 TTL=0 S=1
13 tbr2-cl3641.phlpa.ip.att.net (12.122.10.94) 33.031 ms
MPLS Label=31344 CoS=0 TTL=0 S=1
14 tbr1-cl9.wswdc.ip.att.net (12.122.2.85) 33.738 ms
MPLS Label=31295 CoS=0 TTL=0 S=1
15 gbr5-p10.wswdc.ip.att.net (12.122.11.170) 29.483 ms
MPLS Label=317 CoS=0 TTL=0 S=1
CoS:
16 gbr1-s83.mdtva.ip.att.net (12.122.4.81) 32.068 ms
Class of Service
17 12.122.247.254 (12.122.247.254) 32.438 ms
S: Stacking bit 16
18 *
Boeing Connexion Mobility Service
17
Example problem 1
 If all the links in the Internet were to
provide the reliable delivery service, would
the TCP reliable delivery service be
redundant? Why or why not?
18
Example problem 1
 If all the links in the Internet were to
provide the reliable delivery service, would
the TCP reliable delivery service be
redundant? Why or why not?
 Ans: TCP is still needed to ensure end-toend reliability. Packets may be lost due to
routing loops or equipment failures. TCP
also provide in-order delivery.
19
Example problem 2
 Suppose two nodes start to transmit at the
same time a packet of length L over a
broadcast channel of rate R. Denote the
propagation delay between the two nodes
as tprop. Will there be collision if tprop <
L/R? Why or why not?
20
Example problem 2
 Suppose two nodes start to transmit at the
same time a packet of length L over a
broadcast channel of rate R. Denote the
propagation delay between the two nodes
as tprop. Will there be collision
if tprop < L/R? Why or why not?
 Ans: Yes, there will be collision, because
while a node is transmitting it will start to
receive a packet from the other node.
21
Review:
Ethernet CSMA/CD algorithm
1. Adaptor receives datagram 4. If adapter detects
from net layer & creates
another transmission while
frame
transmitting, aborts and
sends jam signal
2. If adapter senses channel
idle (for 96 bit times), it
5. After aborting, adapter
starts to transmit frame.
enters exponential
If it senses channel busy,
backoff: after the mth
waits until channel idle (for
collision, adapter chooses
96 bit times), and then
a K at random from
transmits
{0,1,2,…,2m-1}. Adapter
3. If adapter transmits entire waits K·512 bit times and
returns to Step 2
frame without detecting
another transmission, the
adapter is done with frame!
22
Review:
Ethernet’s CSMA/CD (more)
Jam Signal: make sure all
other transmitters are
aware of collision; 48 bits
Bit time: .1 microsec for 10
Mbps Ethernet ;
for K=1023, wait time is
about 50 msec
Exponential Backoff:
 Goal: adapt retransmission
attempts to estimated
current load

heavy load: random wait
will be longer
 first collision: choose K
from {0,1}; delay is K· 512
bit transmission times
 after second collision:
choose K from {0,1,2,3}…
 after ten collisions, choose
K from {0,1,2,3,4,…,1023}
23
Example problem 3
 In CSMA/CD, after the fifth collision,
what is the probability that a node chooses
K=4? The result K=4 corresponds to a delay
of how many seconds on a 10 Mbps
Ethernet?
24
Example problem 3
 In CSMA/CD, after the fifth collision,
what is the probability that a node chooses
K=4? The result K=4 corresponds to a delay
of how many seconds on a 10 Mbps
Ethernet?
 Ans: After the fifth collision, the adapter
chooses from {0,1,2,…., 2^5-1}. The
probability that it chooses 4 is 1/32.
 It waits K· 512 bit transmission times

4x512bit/(10Mbps) = 204.8 microseconds.
25
Example problem 4
 Suppose nodes A and B are on the same
10Mbps Ethernet segment and the
propagation delay between the two nodes is
225 bit times. Suppose A and B send
frames at the same time, the frames
collide, and then A and B choose different
values of K in the CSMA/CD algorithm.
Assuming no other nodes are active, can
the retransmissions from A and B collide?
26
 Suppose nodes A and B are on the same 10Mbps
Ethernet segment and the propagation delay
between the two nodes is 225 bit times. Suppose A
and B send frames at the same time, the frames
collide, and then A and B choose different values of
K in the CSMA/CD algorithm. Assuming no other
nodes are active, can the retransmissions from A
and B collide?
 Ans: Assuming A chooses K=0, B chooses K=1,
basically we need to find out whether A’s
retransmission will reach B before B’s scheduled
retransmission time. (It’s unlikely that A can finish
retransmission before B retransmits.)
27
 Suppose nodes A and B are on the same 10Mbps Ethernet
segment and the propagation delay btw. the two nodes is
225 bit times. Suppose A and B send frames at the same
time, the frames collide, and then A and B choose different
values of K in the CSMA/CD algorithm. Assuming no other
nodes are active, can the retransmissions from A and B
collide?
 Draw a time line:
 t=0
 t=225
 t=225+48=273
 273+225=498
A and B begin transmission
A and B detect collision
A and B finish sending Jam signal
B’s last bit arrives at A; A detects
an idle channel
 498+96=594
A starts transmitting
 273+512=785
B returns to step2, B must sense idle
channel for 96 bit times: 785+96=881
 594+225=819
A’s transmission reaches B
28
 819<881: A’s retransmission reaches B before B can send.
Example problem 5
 Why are link layer acknowledgements used
in 802.11 but not in wired Ethernet?
29
Example problem 5
 Why are link layer acknowledgements used
in 802.11 but not in wired Ethernet?
 Ans: Two reasons why 802.11 uses ACKs: (1)
wireless channel’s bit error rate is much
higher. (2) in wired Ethernet, a
transmitting station can detect when there
has and hasn’t been a collision, but in
802.11 a station cannot detect a collision
due to hidden terminal problem.
30
Example problem 6
 Suppose the IEEE 802.11 RTS and CTS
frames were as long as the standard DATA
frames. Would there be any advantage to
using the CTS and RTS frames? Why and
why not?
31
Example problem 6
 Suppose the IEEE 802.11 RTS and CTS
frames were as long as the standard DATA
frames. Would there be any advantage to
using the CTS and RTS frames? Why and why
not?
 Ans: No, there wouldn’t be any advantage.
Suppose there are two stations that want to
transmit at the same time, and they both use
RTS/CTS. If the RTS frame is as long as a
DATA frame, the channel would be wasted
for as long as it would have been wasted for
colliding DATA frames. Thus, the RTS/CTS
exchange is only useful when they are
significantly smaller than DATA frames.
32
Example problem 7
 Consider three LANs
C
A
E
B
interconnected by two routers
 Assign IPs to all the interfaces.
Subnet 1 uses addresses of the
form 111.111.111.xxx, subnet 2 uses Subnet 1
addresses of the form
122.222.222.xxx, and subnet 3 uses
addresses of the form
133.333.333.xxx
 Assign MAC addresses (arbitrarily).
 Consider sending an IP datagram
from Host A to Host F, suppose all
the ARP tables are up-to-date.
Enumerate all the steps.
F
D
Subnet 3
Subnet 2
33
Example problem 7
122.222.222.001
44-44-44-44-44-44
111.111.111.001
00-00-00-00-00-00
A
C
111.111.111.002
22-22-22-22-22-22
133.333.333.001
77-77-77-77-77-77
B
122.222.222.002
33-33-33-33-33-33
111.111.111.003
11-11-11-11-11-11
Subnet 1
122.222.222.003
55-55-55-55-55-55
E
F
133.333.333.002
88-88-88-88-88-88
D
122.222.222.004
66-66-66-66-66-66
133.333.333.003
99-99-99-99-99-99
Subnet 3
Subnet 2
34
122.222.222.001
44-44-44-44-44-44
A
B
111.111.111.001
C
00-00-00-00-00-00
111.111.111.003
11-11-11-11-11-11
Subnet 1
Subnet 3
111.111.111.002
22-22-22-22-22-22
133.333.333.001
77-77-77-77-77-77
122.222.222.002
33-33-33-33-33-33
122.222.222.003
55-55-55-55-55-55
DSubnet 2
122.222.222.004
66-66-66-66-66-66
E
F
133.333.333.002
88-88-88-88-88-88
133.333.333.003
99-99-99-99-99-99
1. Forwarding table in A determines that the datagram should be routed to interface
111.111.111.002
2. Host A uses ARP to determine the LAN address for 111.111.111.002, namely 22-2222-22-22-22.
3. The adapter in A creates an Ethernet packet with destination address of 22-22-2222-22-22
4. The first router receives the packet and extracts the datagram. The forwarding
table in this router indicates that the datagram is to be routed to 122.222.222.003.
5. The first router then uses ARP to obtain the associated Ethernet address: 55-5555-55-55-55.
6. The process continues until the packet has reached host F.
35