Network Routing
Download
Report
Transcript Network Routing
Datalink Layer: Examples
4/21/2008
Recap: Summary of MAC Protocols
How do you access a shared media?
channel partitioning, by time, frequency or code
random
access,
• ALOHA, S-ALOHA, CSMA, CSMA/CD
“taking-turns”
• polling
• token passing
2
Recap: Aloha Protocol
Behaviors of Aloha on a LAN
a total of m stations
fixed transmission rate p for a backlogged station
to transmit in a slot
pa for each un-backlogged station
3
Outline
Admin. and recap
MAC Examples
4
Example MAC Protocols
Example MAC protocols
GSM
Ethernet
Wireless LAN
Bluetooth
There are many more link technologies
e.g., ATM, DOCSIS, FDDI, Frame relay, IEEE
802.5 Token Ring, PPP, WiMax, X.25, xDSL
if you are interested, please see schedule page for
a link to a set of optional slides
Key
factors: traffic services
5
Outline
Admin. and recap
MAC Examples
GSM
6
http://wireless.fcc.gov/uls/index.htm?job=home
GSM - TDMA/FDMA
935-960 MHz
124 channels (200 kHz)
downlink
890-915 MHz
124 channels (200 kHz)
uplink
time
GSM TDMA frame
1
2
3
4
5
6
7
8
4.615 ms
GSM time-slot (normal burst)
guard
space
tail
3 bits
user data
S Training S
user data
57 bits
1 26 bits 1
57 bits
S: indicates data or control
guard
tail space
3
546.5 µs
577 µs
7
Many Types of Logical Channels
Control channels
Broadcast control channel
(BCCH)
• From base station, announces
cell identifier, synchronization
Common control channels
(CCCH)
• Paging channel (PCH):
Base
transceiver station (BTS) pages a
mobile host (MS)
• Random access channel
(RACH): MSs for initial access,
using slotted Aloha
• Access grant channel
(AGCH): BTS informs an MS its
allocation
Dedicated control channels
•
Example: call setup from an MS
BTS
MS
RACH (request signaling channel)
AGCH (assign signaling channel)
SDCCH (request call setup)
SDCCH message exchange
SDCCH (assign TCH)
Communication using TCH
Standalone dedicated control channel
(SDCCH): signaling and short
message between MS and an MS
Traffic channels (TCH)
8
GPRS: GSM Data Services
Using GSM, an MS can use a (logical) traffic channel to send
data
data rate standardized at 9.6 kbps
General Packet Radio Service (GPRS)
allocate multiple slots from the same frame; by reserving different
number of slots and using different coding scheme, an MS achieves
different rate (kbps)
Coding
scheme
1 slot
2 slots
3 slots
4 slots
5 slots
6 slots
7 slots
8 slots
CS-1
9.05
18.2
27.15
36.2
45.25
54.3
63.35
72.4
CS-2
13.4
26.8
40.2
53.6
67
80.4
93.8
107.2
CS-3
15.6
31.2
46.8
62.4
78
93.6
109.2
124.8
CS-4
21.4
42.8
64.2
85.6
107
128.4
149.8
171.2
simplified signaling process: still uses a random channel to request
frequency and time slot
9
GPRS Signaling
PRACH: Pkt. Random Access Channel; PAGCH: Pkt. Access Grant Channel; PTCH: Pkt. Traffic Channel
10
USF: uplink state flag
UMTS: Enhancements of GSM
UMTS (Universal Mobile Telecommunications
System)
Use CDMA for channel partitioning
o less fragmented channels
o additional requirement: allocate different
amount of bw to mobile stations
W-CDMA
chipping rate: 5 MHz, 3.840 Mchip/s
11
Orthognal Variable Spreading Factor (OSVF)
By assigning a code with a low spreading
factor, a node receives higher bw.
1,1,1,1,1,1,1,1
...
1,1,1,1
1,1,1,1,-1,-1,-1,-1
1,1
1,1,-1,-1,1,1,-1,-1
X,X
1,1,-1,-1,-1,-1,1,1
1
X
...
1,1,-1,-1
1,-1,1,-1,1,-1,1,-1
X,-X
...
1,-1,1,-1
1,-1,1,-1,-1,1,-1,1
SF=n
SF=2n
1,-1
1,-1,-1,1,1,-1,-1,1
...
1,-1,-1,1
1,-1,-1,1,-1,1,1,-1
SF=1 SF=2
SF=4
SF=8
12
Outline
Admin. and recap
Example MAC protocols
GSM
• Channel partitioning (time, freq., code) and slotted Aloha
Ethernet
13
Ethernet
“Dominant” LAN technology:
First widely used LAN
technology
Kept up with speed race: 10 Mbps, 100 Mbps,
1 Gbps, 10 Gbps
Metcalfe’s Ethernet
sketch
14
Ethernet Frame Structure
Sending adapter encapsulates IP datagram (or other network
layer protocol packet) in Ethernet frame
8
6
6
2
46-1500 (including padding)
4
Preamble: 8 bytes
7 bytes with pattern 10101010 followed by one byte with
pattern 10101011 (why the preamble?)
Source and dest. addresses: 6 bytes
Type: indicates the higher layer protocol, mostly IP but
others may be supported such as Novell IPX and AppleTalk)
CRC: CRC-32 checked at receiver, if error is detected, the
frame is simply dropped
15
The Basic MAC Mechanisms of Ethernet
get a packet from upper layer;
K := 0; n := 0; // K: control wait time; n: no. of collisions
repeat:
wait for K * 512 bit-time;
while (network busy) wait;
wait for 96 bit-time after detecting no signal;
transmit and detect collision;
if detect collision
stop and transmit a 48-bit jam signal;
n ++;
m:= min(n, 10), where n is the number of collisions
choose K randomly from {0, 1, 2, …, 2m-1}.
if n < 16 goto repeat
else give up
16
Ethernet’s Exponential Backoff:
Goal: adapt retransmission attempts to
estimated current load
compared with CSMA, 1/2m can be considered as p
not a static p---adjusted using exponential
backoff
• first collision: choose K from {0,1}; delay is K x 512 bit
transmission times
• after second collision: choose K from {0,1,2,3}…
• after ten or more collisions, choose K from
{0,1,2,3,4,…,1023}
17
Ethernet: From Bit to Electrical Signal
Use Manchester encoding
One voltage change per bit
for a “1”, a voltage change from 1 to 0
for a “0”, a voltage change from 0 to 1
Example
18
Ethernet Technologies: 10Base2
10: 10Mbps; 2: under 200 meters max cable
length
Thin coaxial cable in a bus topology
Issues of such connectivity?
19
10BaseT and 100BaseT
10/100 Mbps rate; latter called “fast ethernet”
T stands for Twisted Pair
Hub to which nodes are connected by twisted pair,
thus “star topology”
there is a bus inside the hub; boost signal from one port to
all other ports
20
Interconnecting with hubs
Multiple hubs interconnect to form a larger Ethernet
network
extends max distance between nodes; more ports
Issue: individual segment collision domains become
one large collision domain
21
Ethernet Bridges
Link layer device
stores and forwards Ethernet frames
examines frame header and selectively forwards
frame based on MAC dest address
segments become separate collision domains
collision
domain
collision
domain
bridge
LAN segment
= hub
= host
LAN segment
LAN (IP network)
22
Bridge Forwarding
Key issue: How do determine to which LAN segment
to forward frame?
23
Ethernet Bridge Self Learning
A bridge has a bridge table
Entry in bridge table:
(Node LAN Address, Bridge Interface, Time Stamp)
stale entries in table dropped (TTL can be 60 min)
Bridges
learn which hosts can be reached through
which interfaces
when frame received, bridge “learns” location of
sender: incoming LAN segment
records sender/location pair in bridge table
24
Filtering/Forwarding
When bridge receives a frame:
index bridge table using MAC dest address
if entry found for destination
then {
if dest on segment from which frame arrived
then drop the frame
else forward the frame on interface indicated
}
else flood
forward on all but the interface
on which the frame arrived
25
Ethernet Bridge: Example
Suppose C sends frame to D and D replies back with
frame to C.
Bridge receives frame from C to D
notes in bridge table that C is on interface 1
because D is not in table, bridge sends frame into
interfaces 2 and 3
frame received by D
26
Bridge Learning: Example
D generates frame for C, sends
C | 1
Bridge receives frame
notes in bridge table that D is on interface 2
bridge knows C is on interface 1, so selectively forwards
frame to interface 1
27
Bridges Spanning Tree
For increased reliability, desirable to have
redundant, alternative paths from source to dest
With multiple paths, cycles result - bridges may
multiply and forward frame forever
Solution: organize bridges in a spanning tree by
disabling subset of interfaces
Disabled
28
Bridges vs. Routers
both store-and-forward devices
routers: network layer devices (examine network layer
headers)
bridges are link layer devices
routers maintain routing tables, implement routing
algorithms
bridges maintain bridge tables, implement filtering,
learning and spanning tree algorithms
29
Routers vs. Bridges
Bridges + and + Bridge operation is simpler
+ Bridge tables are self learning
- All traffic confined to spanning tree, even when
alternative bandwidth is available
- Bridges do not offer protection from broadcast
storms (flooding of packets)
30
Routers vs. Bridges
Routers + and + arbitrary topologies can be supported
+ provide protection against broadcast storms
- require IP address configuration (not plug and play)
- require higher packet processing
bridges do well in small (few hundred hosts) while
routers used in large networks (thousands of hosts)
31
Gbit Ethernet and
Ethernet Switches
Gbit Ethernet typically use
Ethernet switches
Essentially a multi-interface
bridge
layer 2 (frame) forwarding,
filtering using LAN addresses
Switching: A-to-A’ and B-toB’ simultaneously, no collisions
cut-through switching: frame
forwarded from input to
output port without awaiting
for assembly of entire frame
32
Not an atypical LAN (IP network)
Dedicated
Shared
33
Summary: Comparison
hubs
bridges
routers
switches
traffic
isolation
no
yes
yes
yes
plug & play
yes
yes
no
yes
optimal
routing
cut
through
no
no
yes
no
yes
no
no
yes
34
Outline
Admin. and recap
Example MAC protocols
GSM
• Channel partitioning and slotted Aloha
Ethernet
• Random MAC protocol (CSMA/CD + Exponential backoff)
Wireless LAN
35
802.11 – Traffic Services and Access Methods
Two types of traffic services
Asynchronous Data Service (mandatory)
• exchange of data packets based on “best-effort”
• implemented by random access
Time-Bounded Service (optional)
Two types of coordination function (aka MAC)
DCF (Distributed Coordination Function)
PCF (Point Coordination Function)
• access point polls
36
IEEE 802.11 Wireless LAN
Basic Service Set (BSS)
(a.k.a. “cell”) contains:
wireless station (WS)
access point (AP): base
station
BSS’s combined to form
distribution system (DS)
Two operation modes:
infrastructure mode
• everything through AP
peer-to-peer mode
• called ad hoc network
37
Random Access Carrier Sense in
802.11
A
B
C
The hidden-terminal problem
A is sending to B, but C cannot receive from A
• Friis Law (power decay proportional to distance squared)
Therefore C sends to B, without detecting the
transmission from A to B
In summary, A is “hidden” for C
38
The Exposed Terminal Problem
A
B
C
D
B is sending to A, C intends to send to D
C senses an “in-use” medium, thus C waits
But A is outside the radio range of C,
therefore waiting is not necessary
In summary, C is “exposed” to B
Implication: false carrier sense
39
Summary of Problems of Wireless MAC
How to achieve carrier sense?
in Ethernet, we use carrier sense to avoid and
detect potential collision
for wireless networks, the hidden-terminal, and
the exposed-terminal problems make carrier sense
(i.e., listen before talk) neither sufficient nor
necessary
• not detected transmission at the sender does not imply
no current transmission to the receiver
• detected transmission at the sender does not imply
transmission will cause collision
How to integrate random access (DCF) and
taking turns (PCF)?
40
Basic Solution: Using RTS/CTS to
Address the Carrier Sense Problem
Short signaling packets---virtual carrier
sense
RTS
(request to send) and CTS (clear to send)
• to avoid collision at the receiver, any station who
hears a CTS should not transmit
• frames need to contain sender address, receiver
address, transmission duration
RTS
F
E
Example: A sends to B
RTS
A
CTS
B
CTS
C
D
41
Basic Solution: Using Inter Frame
Spacing to Prioritize Access
Different inter frame spacing (IFS): if the required IFS of a
type of message is short, the type of message has higher
priority
SIFS (Short Inter Frame Spacing)
• highest priority, for ACK, CTS, polling response
PIFS (Point Coordination Function Spacing)
• medium priority, for time-bounded service using PCF
DIFS (Distributed Coordination Function Spacing)
• lowest priority, for asynchronous data service
DIFS
DIFS
medium busy
PIFS
SIFS
contention
next frame
t
Access point access if
medium is free DIFS
random direct access if
medium is free DIFS
42
Basic Control Flow of RTS/CTS
Sender sends RTS with NAV (Network allocation Vector, i.e.
reservation parameter that determines amount of time the data
packet needs the medium) after waiting for DIFS
Receiver acknowledges via CTS after SIFS (if ready to receive)
CTS reserves channel for sender, notifying possibly hidden stations;
any station hearing CTS should be silent for NAV
Sender can now send data at once
DIFS
sender
data
RTS
SIFS
receiver
other
stations
CTS SIFS
NAV (RTS)
NAV (CTS)
defer access
DIFS
new contention
data
t
43
802.11: RTS/CTS + ACK
802.11 adds ACK in the signaling to improve reliability
implication: to avoid conflict with ACK, any station hearing RTS should
not send for NAV
thus a station should not send for NAV if it hears either RTS and CTS
Note: RTS/CTS is optional in 802.11, and thus may not be
always turned on---some network interface cards turn it on
only when the length of a frame exceeds a given threshold
DIFS
sender
data
RTS
SIFS
receiver
other
stations
CTS SIFS
SIFS
NAV (RTS)
NAV (CTS)
defer access
ACK
DIFS
new contention
data
t
44
802.11: PCF for Polling
PIFS
point
coordinator
D
D
SIFS
U
polled
wireless
stations
NAV
SIFS
NAV
medium
busy
contention free period
contention
period
t
D: downstream poll, or data from point coordinator
U: data from polled wireless station
45
802.11 - Frame Format
Before the MAC header are
an 80-bit preamble of alternating 0 and 1 for clock sync.
a physical layer header (PLCP) which is always transmitted at 1
Mbps, including signaling fields such as sending rate
Duration ID: NAV
The four addresses are used to encode various addresses
e.g., Addr 1 is always the recipient address (i.e., the immediate
recipiet of the frame), Addr 2 is always the transmitter addr
CRC: check sum
46
802.11 Frame Control Field
47
Outline
Admin. and recap
Example MAC protocols
GSM
• Channel partitioning and slotted Aloha
Ethernet
• Random MAC protocol (CSMA/CD + Exponential backoff)
Wireless LAN
• Random MAC protocol (CSMA/CA + RTS/CTS) + Polling
Bluetooth
48
Bluetooth Design Objective
Design objective: a cable replacement
technology to connect a small number of
devices
1 Mb/s
range 10+ meters
single chip radio + baseband (means digital part)
• low power
• low price point (target price $5)
Traffic Services
SCO: Synchronous connected link (fixed
periodical traffic)
ACL: Asynchronous connectionless link
49
Bluetooth
Nodes in Bluetooth form
piconet: one master and upto 7
slaves
Each radio can function as a
master or a slave
A piconet
SCO: a slave reserves with the
master a slot for a synchronous
connected link
ACL: The master polls slaves
for asynchronous
connectionless traffic
50
Bluetooth Links
51
Coexistence of Bluetooth and 802.11
Bluetooth shares the same freq. range as of
802.11
There are can be multiple piconets in close
range, causing inteference (how about
multiple 802.11?)
Question: how to share among piconets and
with 802.11?
52
Bluetooth Frequency Hopping
Divide spectrum into 79 frequencies
Master conducts pseudorandom frequency
hopping
The slaves follow the pseudorandom jumping
sequence of the master
53
Bluetooth Frequency Hopping
54
MAC: Summary
In practical protocols, various MAC
techniques are often combined to achieve
objectives
GSM
• Channel partitioning and slotted Aloha
Ethernet
• Random MAC protocol (CSMA/CD + Exponential backoff)
Wireless
LAN
• Random MAC protocol (CSMA/CA + RTS/CTS) + Polling
o Bluetooth
o Time partitioning, polling, and random hopping
For physical layer, please see the optional
slides linked on the schedule page
55
Backup
56
Comparisons of Different Ethernet Standards
10Base2 10BaseT 100BaseT 1000BaseT
Bandwidth 10 Mbps 10 Mbps 100 Mbps 1000 Mbps
Topology
Bus
Star
Star
Min frame 64 byte 64 byte
size (not
including
preamble)
64 byte
64 byte (min
slot time 512
byte, packet
bursting)
Network
Diameter
~200m
~200m
~200m
Star
~2km
57