Transcript link-mac - Zoo

Link Layer: MAC and Summary
11/30/2009
1
Admin.
 Exam 2
Covers network and link layers
 Format similar to exam 1; see samples of exam 2
from past offerings

2
Recap: Link Layer Services
 Framing
o encapsulate datagram into frame, adding header,
trailer and error detection/correction (e.g., CRC)
 Multiplexing/demultiplexing
o frame headers to identify src, dest
• different from IP address (ARP) !
 Flow control
 Link media access control (MAC)
 Reliable delivery between adjacent nodes
3
Recap: MAC Protocols
Goals
 efficient, fair, decentralized, simple
Three broad classes:
 channel partitioning

divide channel into smaller “pieces” (time slot, frequency,
code)
 Non-partitioning
 random access
• allow collisions
 “taking-turns”
• a token coordinates shared access to avoid collisions
4
Recap: Channel Partitioning
TDMA: Time Division Multiple Access
FDMA: Frequency Division Multiple
Access
CDMA: Code Division Multiple Access



Used mostly in wireless broadcast channels (cellular,
satellite, etc)
Unique “code” assigned to each user; i.e., code set
partitioning
All users share same frequency, but each user m has its own
“chipping” sequence (i.e., code) cm to encode data
• e.g. cm = 1 1 1 -1 1 -1 -1 -1
5
Recap: CDMA
 Each user uses its own code cm
 Assume original data are represented by 1 and -1
 Encoded signal = (original data) modulated by
(chipping sequence)


assume
cm = 1 1 1 -1 1 -1 -1 -1
if data is d, send d cm,
• if data d is 1, send cm
• if data d is -1 send -cm
 Decoding: inner-product (summation of bit-by-bit
product) of encoded signal and chipping sequence

if inner-product > 0, the data is 1; else -1
 If codes are orthogonal, multiple users can “coexist”
and transmit simultaneously with minimal
interference
6
Recap: Channel Partitioning
 Two codes Ci and Cj are orthogonal, if
 c j  ci  0 , where we use “.”
 to denote inner product,
e.g.
C1:
1
1 1 -1 1 -1 -1 -1
C2:
1 -1 1
1 1 -1
1
1
----------------------------------------C1 . C2 =
1 +(-1) + 1 + (-1) +1 + 1+ (-1)+(-1)=0
 If codes are orthogonal, multiple users can
“coexist” and transmit simultaneously with
minimal interference
7
Outline
 Recap
 Non-partitioning MAC protocols
 Random access
 Taking turns (we will not cover in class)
8
Random Access Protocols
 When a node has packets to send
 transmit at full channel data rate R
 no a priori coordination among nodes
 Two or more transmitting nodes -> “collision”
 Random access MAC protocol specifies:
 how to detect collisions
 how to recover from collisions
 Examples of random access MAC protocols:
 slotted ALOHA and pure ALOHA
 CSMA and CSMA/CD, CSMA/CA
9
Slotted Aloha
[Norm Abramson]
 Time is divided into equal size slots (= pkt trans.
time)
 Node with new arriving pkt: transmit at beginning of
next slot
 If collision: retransmit pkt in future slots with
probability p, until successful.
Success (S), Collision (C), Empty (E) slots
10
Slotted Aloha Efficiency
Q: What is the fraction of successful
slots?
suppose n stations have packets to send
suppose each transmits in a slot with probability p
- prob. of succ. by a specific node:
p (1-p)(n-1)
- prob. of succ. by any one of the N nodes
S(p) = n * Prob (only one transmits)
= n p (1-p)(n-1)
11
Goodput vs. Offered Load
Slotted Aloha
0.5
1.0
1.5
2.0
G = offered load = np
 when p n < 1, as p (or n) increases
 probability of empty slots reduces
 probability of collision is still low, thus goodput increases
 when p n > 1, as p (or n) increases,
 probability of empty slots does not reduce much, but
 probability of collision increases, thus goodput decreases
 goodput is optimal when p n = 1
12
Maximum Efficiency vs. n
0.4
1/e = 0.37
maximum efficiency
0.35
0.3
0.25
0.2
At best: channel
use for useful
transmissions 37%
of time!
0.15
0.1
0.05
0
2
7
12
17
n
13
Pure (unslotted) Aloha
 Unslotted Aloha: simpler, no clock synchronization
 Whenever pkt needs transmission:
 send without awaiting for the beginning of slot
 Collision probability increases:
 pkt sent at t0 collide with other pkts sent in [t0-1, t0+1]
14
Pure Aloha (cont.)
Assume a node transmit with probability p in one unit of time
P(success by a given node) = P(node transmits)
* P(no other node transmits in [t0-1,t0]
* P(no other node transmits in [t0, t0+1]
= p . (1-p)n-1 . (1-p)n-1
= p . (1-p)2(n-1)
P(success by any of N nodes) = n p . (1-p)2(n-1)
- Bound: 1/(2e) = .18
15
Goodput vs. Offered Load
protocol constrains
effective channel
throughput!
0.4
0.3
Slotted Aloha
0.2
0.1
Pure Aloha
0.5
1.0
1.5
2.0
G = offered load = Np
16
Dynamics of (Slotted) Aloha
 In reality, the number of stations
backlogged is changing

we need to study the dynamics when using a fixed
transmission probability p
 Assume we have a total of m stations (the
machines on a LAN):
n of them are currently backlogged, each tries
with a (fixed) probability p
 the remaining m-n stations are not backlogged.
They may start to generate packets with a
probability pa, where pa is much smaller than p

17
Model
n backlogged
each transmits with prob. p
m-n: unbacklogged
each transmits with prob. pa
18
Dynamics of Aloha: Effects of Fixed
Probability
desirable stable point
dep.
and
arrival
rate
of
backlogged
stations
0
successful
transmission rate at
offered load
np + (m-n)pa
- assume a total of
m stations
- pa << p
- success rate is the
departure rate, the
rate the backlog is
reducing
new arrival rate:
(m-n) pa
undesirable
stable point
offered load = 1
Lesson: if we fix p, but n varies, we may have an
undesirable stable point
m
n: number of
backlogged
stations
19
Summary of Problems of Aloha Protocols
 Problems


slotted Aloha has better efficiency than pure Aloha but
clock synchronization is hard to achieve
Aloha protocols have low efficiency due to waste of
collision or empty slots
• when offered load is optimal (p = 1/N), the goodput is about
37%
• when the offered load is not optimal, the goodput is even
lower

undesirable steady state at a fixed transmission rate,
when the number of backlogged stations varies
 Thus problems to be addressed:
 approximate slotted Aloha without clock synchronization
 reduce the penalty of collision or empty slots
 infer optimal transmission rate
20
CSMA: Carrier Sense Multiple Access
CSMA: listen before transmit
Objective: approximate slotted Aloha (compared with
pure Aloha)
 If backlogged, wait until channel sensed idle, then
transmit pkt with prob. p
 human analogy: don’t interrupt others !
21
CSMA Collisions
propagation delay means
two nodes may not
hear each other’s
transmission
A
B
C
D
t0
time
collisions can still
occur:
spatial layout of nodes along Ethernet
Collision:
entire packet transmission
time wasted; still not very
efficient!
22
CSMA/CD (Collision Detection)
 Human analogy: the polite conversationalist
CSMA/CD:

observations:
• collisions can be detected within short time
• if colliding transmissions are aborted, we can reduce
channel wastage
carrier sensing, deferral as in CSMA
 collision detection:

• easy in wired LANs: measure signal strengths, compare
transmitted, received signals
• difficult in wireless LANs: receiver shuts off while
transmitting
23
CSMA/CD: Collision Detection
spatial layout of nodes along Ethernet
spatial layout of nodes along Ethernet
C
D
A
t0
t0
time
B
time
A
B
C
B detects
collision,
aborts
D
D detects
collision,
aborts
instead of wasting the whole packet
transmission time, abort after detection.
24
Efficiency of CSMA/CD
 Given collision detection, instead of wasting the
whole packet transmission time (a slot), we waste
only the time needed to detect collision.
P/C
P: packet size, e.g. 1000 bits
C: link capacity, e.g. 10Mbps
 Use a contention slot of 2 T, where T is one-way
propagation delay (why 2 T ?)
 When the transmission probability p is approximately
optimal (p = 1/N), we try approximately e times
before each successful transmission
25
Efficiency of CSMA/CD
 The efficiency (the percentage of useful time) is
approximately
P
C
P  e 2T
C

1
1 5PT

1
15 a
, where a 
TC
P
C
 The value of a plays a fundamental role in the
efficiency of CSMA/CD protocols.
 Question: you want to increase the capacity of a link
layer technology (e.g., , 10 Mbps Ethernet to 100
Mbps), but still want to maintain the same efficiency,
what can you do?
26
Summary of Problems to be Addressed

Approximate slotted Aloha
Reduce the penalty of collision or
empty slots


Infer optimal transmission rate
27
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
28
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}
29
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
30
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
31
Physical Layer
32
Internet Bandwidth Growth
Source: TeleGeograph Research
What Determines Transmission Rate?
 Service: transmit a bit stream from a sender
to a receiver
sender
input
bit stream
Encoding
receiver
channel
Decoding
output
bit stream
Question to be addressed: how much can we send through the channel ?
Basic Theory: Channel Capacity
 The maximum number of bits that can be
transmitted per second (bps) by a physical
media is:
W log 2 (1  )
S
N
where W is the frequency range, S/N is the
signal noise ratio. We assume Gaussian noise.
Fourier Transform
 Suppose the period of a data unit is f (=1/T),
then the data unit can be represented as the
sum of many harmonics (sin(), cos()) with
frequencies f, 2f, 3f, 4f, …
 A reasonably behaved periodic function g(t),
with minimal period T, can be constructed as
the sum of a series of sines and cosines:


n 1
n 1
g (t )  12 c   an sin( 2nft )   bn cos( 2nft )
 f  1/ T

T
c  2 g (t )dt
T 

0


T

2
an  T  g (t ) sin( 2nft ) dt
0

T

bn  T2  g (t ) cos( 2nft ) dt

0

char “b”
rmsn  an  bn
Signal Attenuation
W log 2 (1  NS )
 The quality of signal will degrade when it travels
 loss, frequency passing
Frequency Dependent Attenuation
 The received signal will be distorted even when
there is no interference and the transmitted signal
is “perfect” square waveform
Example: Voltageattenuation magnitude
ratios of Category 5
cable. For example, 500
feet of cable
attenuates a 10-MHz,
1-V signal to 0.32 V,
which corresponds to
about –9.90 dB
(= 20 log 1/0.32)
Example
V.34 (33.6kbps Dialup Modem)
channel
sender modem
input
bit stream
3Khz
Modem
bandwidth
Modulation
(add
white noise)
(digit->analog)
telephone network
Analog to Digital
quantization
for transmitting through
the digital telephone
backbone
ISP modem
ISP
demodulation
output
bit stream
Example: W=3000Hz, S/N  4000
max bandwidth  3000 log 2 (1  4000)  36kbps
Example: ADSL
 Spectrum allocation:
divided into a total of
256 downstream and
32 upstream tones, where
each tone is a standard
4kHz voice channel
 During initial negotiation, a tone is used only
if the S/N is above 6 db (4)
down  256 * 4000 log 2 (1  4)  2.4 Mbps
up  32 * 4000 log 2 (1  4)  297kbps
Course Summary
 The Internet is a general-purpose, large-scale,
distributed computer network
 Major design features
 packet switching for simplicity and efficiency
 hour-glass architecture
 end-to-end principle
 distributed system considering social/economical structures



resource allocation principle and framework (e.g.,
optimization framework and AIMD)
stable, adaptive control (e.g., sliding window self
clocking, CSMA/CD/Expo)
hierarchical, distributed routing
Evolution
 Driven by Technology, Infrastructure, Policy,
Applications, and Understanding:

technology
• e.g., wireless/optical communication technologies and device
miniaturization (sensors)

infrastructure
• e.g., cloud computing

applications
• e.g., content distribution, game, tele presence, sensing, grid
computing, VoIP, IPTV

understanding
• e.g., resource sharing principle, routing principles, mechanism
design, and optimal stochastic control (randomized access)
Many Issues
 How to make it faster
 How to make it more efficient
 How to make it more reliable/robust/secure
44
Faster
45
The Wire: Fiber
 A look at a fiber
A graded index fiber
 How it works?
The Wire: Fiber
 Wide spectrum at low loss:
~0.3db/km
(c.f. copper ~190db/km @100Mhz),
30-100km without repeater
 Bandwidth of a single fiber
 theoretical: 100-200Tbps
http://www.trnmag.com/Stories/080101/
Study_shows_fiber_has_room_to_grow_
080101.html
 Lightweight: 33 tons of copper
to transmit the same amount
of information carried by ¼
pound of optical fiber
Advantages of Fibers
How to Do Switching?
 Optical-Electrical-Optical
 Optical switch: optical micro-electro-mechanical systems (MEMS)
Optical path
One optical switch
http://www.qwest.com/largebusiness/enterprisesolutions/networkMaps/preloader.swf
Example: MEMS Optical Switch
 Using mirrors, e.g. Lambda Router
Implications
 Fine-grained switching may not be feasible
 What is the architecture of optical
networks: packet switching, circuit
switching, or others?
More Efficient
52
Problem: Inefficient Interactions
 Large deployment of highly adaptive,
multipoint applications
 An iterative process between two sets of
adaptation:
 ISP: traffic engineering to change routing
to shift traffic away from higher utilized
links
• current traffic pattern  new routing matrix

App: direct traffic to better performing
end points
• current routing matrix  new traffic pattern
ISP Traffic Engineering+ App Latency Optimizer
- red: App adjust alone; fixed ISP routing
- blue: ISP traffic engineering adapt alone; fixed App communications
ISP optimizer interacts poorly with App.
The Fundamental Problem
 Traditional Internet architectural feedback
to application efficiency is limited:
routing (hidden)
 rate control through coarse-grained TCP
congestion feedback

 To achieve better efficiency, needs explicit
communications between network resource
providers and applications
P4P Framework – Design Goals
 Performance improvement
 Scalability and extensibility: support diverse
ISP objectives and applications scenarios in
large networks
 Privacy preservation
 Ease of implementation
 Open standard: any ISP, provider,
applications can easily implement it
Current Status
 P4P-WG
 Next step
 wider integration
 IETF standard
• AT&T
• Bezeq Intl
• BitTorrent
• CacheLogic
• Cisco Systems
• Grid Networks
• Joost
• LimeWire
• Manatt
• Oversi
• Pando Networks
• PeerApp
• Telefonica Group
• VeriSign
• Verizon
• Vuze
• Univ of Washington
• Yale University
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Abacast
AHT Intl
Akamai
Alcatel Lucent
CableLabs
Cablevision
Comcast
Cox Comm
Juniper Networks
Microsoft
MPAA
NBC Universal
Nokia
RawFlow
Solid State Networks
Thomson
Time Warner Cable
Turner Broadcasting
Reliability
Is the Internet Reliable?
 A key design objective
of the “Internet” (i.e.,
packet-switched
networks) is robustness
 Does the Internet
infrastructure achieve
the target reliability
objective of a highly
reliable system
(99.999%)?
Perspective
 911 Phone service (1993 NRIC report +)
29 minutes per year per line
 99.994% availability

 Std. Phone service (various sources)
 53+ minutes per line per year
 99.99+% availability
 …what about the Internet?
 Various
studies: about 99.5%
 Need to reduce down time by 500 times to
achieve five nines; 50 times to match phone
service
Unreachable Networks: 10 days
Internet Disaster Recovery Response
 Why slow response?


the cable repairing is slow: not until 21 days
after quake
BGP is not designed to create business
relationship
 Objective
 a meta-BGP to facilitate discovery and creation
of BGP business relationship
63
Backup Slides
64
The P4P Framework
 Data plane
 control plane
 P4P server: a portal for each network service
provider
 A P4P server provides multiple interfaces so that
others can interact
•
each provider decides the interfaces it provides
The Virtual Topology Interface
 An interface to guide peer selection
 An interface as an optimization decomposition
interface
 guidance
through “virtual costs”
The Virtual Topology Interface: Network
 PID: set of Points
of Presence (PoP)
 E: set of links
connecting PoPs
 ce: the link capacity of link e
 Ie(i, j): indicator if link e is on the route from
PoP i to PoP j
 be: amount of background traffic on link e
The Virtual Topology Interface: App
 Assume K applications running inside the ISP
 Let Tk be the set of acceptable demands for
app k
 tk
in Tk specifies traffic demand tkij from each
pair of source-destination PoPs (i,j)
The Virtual Topology Interface
 Consider an example: ISP wants to minimize
utilization of the highest utilized link

the utilization of the highest utilized link is called
the Maximum Link Utilization (MLU)
min max (be   t I (i, j )) / ce
eE
i j
k
s.t. k : t  T
k
k
k
ij e
ISP MLU: Transformation
min
s.t.

e : be   t I (i, j )  ce
k
k
ij e
i j
k : t  T
k
k
ISP MLU: Dual
 Introducing pe (≥ 0) for the inequality of
each link e
D(pe )  mink k    pe (be   t  ce )
k
e
 ;k :t T
e
 To make the dual finite, need
p c
e e
e
1
k
ISP MLU: Dual
 Then the dual is
k
D(pe )  min
p
(
b

t
)


e
e
e
k
k
k :t T
  pebe   min
pt
k
k
e
e
k
e
t T
k
e e
k
  pebe   min
pt
k
k
e
k
e
k
t T
k
e e
e
k
  pebe   min
p
t
ij ij
k
k
t T
i j
where pij is the sum of pe along the path from
PoP i to PoP j
ISP MLU Dual : Interpretation
D (pe )   pebe   min
pt
k
k
e
k
t T
i j
k
ij ij
 Each App k chooses tk in Tk to minimize
weighted sum of tij
 The interface between an App and the ISP is
the “shadow prices” {pij}
Topology with Costs (Illustration)
PID1
70
PID2
30
10
PID6
PID5
60
20
PID3
Each PID has:
• IP “prefix”
PID4
Each link has
•“Price”
Prices are directional
ISP Update
 At update m+1,
calculates
pe (m  1)  [ pe (m  1)   ( m) (m)]S
 : step size
 : supergradi ent of D({p e })
[]S : projection to set S
S : {p e :  pe ce  1; pe  0}
e
App Operations
 Each app. optimizes its own performance,
then picks ISP-friendly peering
 For example, selects
where  is tolerance, say 80%.
Example: Multihoming
Multihoming
ISP 1

User
ISP 2
ISP K
Internet
A common way of
connecting to Internet
Smart routing
Intelligently distribute
traffic among multiple
external links
 Improve performance
 Improve reliability
 Reduce cost

Interdomain Topo
PID1
70
Cost?
PID2
30
Provider1
20
Cost?
10
PID6
PID3
Cost?
PID5
60
PID4
Provider 3
Provider 2
Integrating Cost Min with P4P
min
s.t.

e  E0 : be   t I (i, j )  ce
k
i j
k
ij e
e  Ee : be   t I (i, j )  ve
k
i j
k
k
ij e
k : t  T
k
Field Test: Traffic within Verizon
Average Hop Each Bit Traverses
 Why less than 1: many transfers are in the
same metro-area; also same metro-area peers
are utilized more by tit-for-tat.
App Perspective: App Rates