Transcript 3rd Edition, Chapter 5

Week 3
Virtual LANs, Wireless LANs,
PPP, ATM
1
Week 3
Virtual LANs
 It is the territory over which a broadcast
or multicast packet is delievered (also
known as a broadcast domain)
 The difference in a VLAN and a LAN, if
there is any, is in packaging
 Virtual LANs allow you to have separate
LANs among ports on the same switch
 For example, a switch might be told that
ports 1-32 are in VLAN A and ports 33-64
are in VLAN B
2
Week 3
Virtual and Physical LANs
VLAN A
A
Q
V
A
Q
V
J
J
R
M
B
D
K
VLAN B
M
B
D
K
3
Week 3
Why VLANs
 IP requires that all nodes on a LAN share the same




IP address prefix; therefore a node that moves to
a different LAN must change its address
Changing IP addresses manually is annoying
IP broadcasts traffic within a LAN, something
that can cause congestion in a large LAN
Routing IP (rather than bridging) was slow
It might be tempting to bridge everything making
your whole topology one giant LAN from the
perspective of IP and use layer 2 switches
4
Week 3
Disadvantages of one single
LAN
 Broadcast traffic (such as ARP) grows in




proportion to the number of stations
Users can snoop on the traffic of other users on
the same LAN, so it might be safer to isolate
groups of users onto different LANs
Some protocols are overly chatty or they get into
modes such as broadcast storms.
So it seems desirable for users that need to talk
to each other a lot to be in the same LAN but
keep other groups of users in separate LANs
A VLAN makes us broadcast domain as large as we
want it
5
Week 3
Mapping ports to VLANs
 The switch has ports 1 to k in one VLAN and has ports k+1 to




2k in another LAN
The switch can be configured with a port/VLAN mapping
The switch can be configured with a table of VLAN/MAC
address mappings. It then dynamically determines the
VLAN/port mapping based on the learned MAC address of the
station attached to the port.
The switch can be configured with a table of VLAN/IP prefix
mappings. It then dynamically determines the VLAN/port
mapping based on the source IP address from the station
attached to the port.
The switch can be configured with a table of VLAN/protocol
mappings. It then dynamically determines the VLAN/port
mappings based on the protocol type of the stations attached
to the port.
6
Week 3
VLAN forwarding with separate
router
a.b.c.H
f.g.k.Q
h
d
a.b.c.D
2
9
3
7
f
q
11 13
j
a.b.c.R1
x
f.g.k.X
f.g.k.R2
Router R
Router connects VLANs
7
Week 3
VLAN forwarding with switch
as router
a..b.c.H
2
VLAN A
3
Switch/
Router R
9
f.g.k.Q
VLAN B
12
a..b.c.D
f.g.k.X
 Router does not use up ports
 The switch must know that R’s mac address
on VLAN A is f and on VLAN B is j.
8
Week 3
Dynamic binding of links to
VLANs
X.B
Z.C
X.A
Q.F
c
Q.E
Z.D
a
b
Q.D
Q.F
The switch now learns that there are two VLANs on port a
If enough stations move around, advantage disappears
9
Week 3
VLAN Tagging
VLAN 2
VLAN 1
VLAN 2
VLAN 2
VLAN1
VLAN 1
Interswitch port;
Packets can belong in either
VLAN1 or VLAN2
VLAN 1
VLAN 2
IEEE standardized a scheme
for VLAN tagging
VLAN 1
10
Week 3
IEEE 802.11 Wireless LAN
 802.11b
 2.4-5 GHz unlicensed
radio spectrum
 up to 11 Mbps
 direct sequence spread
spectrum (DSSS) in
physical layer
• all hosts use same
chipping code
 widely deployed, using
base stations
 802.11a
 5-6 GHz range
 up to 54 Mbps
 802.11g
 2.4-5 GHz range
 up to 54 Mbps
 All use CSMA/CA for
multiple access
 All have base-station
and ad-hoc network
versions
11
Week 3
802.11 LAN architecture
 wireless host communicates
Internet
AP
hub, switch
or router
BSS 1
AP
BSS 2
with base station
 base station = access
point (AP)
 Basic Service Set (BSS)
(aka “cell”) in infrastructure
mode contains:
 wireless hosts
 access point (AP): base
station
 ad hoc mode: hosts only
12
Week 3
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
 will typically run DHCP to get IP address in AP’s
subnet
13
Week 3
IEEE 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/C(ollision)A(voidance)
A
C
A
B
B
C
C’s signal
strength
A’s signal
strength
space
14
Week 3
IEEE 802.11 MAC Protocol: CSMA/CA
802.11 sender
1 if INITIALLY 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
802.11 receiver
- if frame received OK
sender
receiver
DIFS
data
SIFS
ACK
return ACK after SIFS (ACK needed due
to hidden terminal problem)
15
Week 3
Avoiding collisions (more)
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
 RTS heard by all nodes
 sender transmits data frame
 other stations defer transmissions
Avoid data frame collisions completely
using small reservation packets!
16
Week 3
Collision Avoidance: RTS-CTS exchange
A
AP
B
reservation collision
DATA (A)
defer
time
17
Week 3
802.11 frame: addressing
2
2
6
6
6
frame
address address address
duration
control
1
2
3
Address 1: MAC address
of wireless host or AP
to receive this frame
2
6
seq address
4
control
0 - 2312
4
payload
CRC
Address 4: used only
in ad hoc mode
Address 3: MAC address
of router interface to
which AP is attached
Address 2: MAC address
of wireless host or AP
transmitting this frame
18
Week 3
802.11 frame: addressing
R1 router
H1
Internet
AP
R1 MAC addr AP MAC addr
dest. address
source address
802.3 frame
AP MAC addr H1 MAC addr R1 MAC addr
address 1
address 2
address 3
802.11 frame
19
Week 3
802.11 frame: more
frame seq #
(for reliable ARQ)
duration of reserved
transmission time (RTS/CTS)
2
2
6
6
6
frame
address address address
duration
control
1
2
3
2
Protocol
version
2
4
1
Type
Subtype
To
AP
6
2
1
seq address
4
control
1
From More
AP
frag
1
Retry
1
0 - 2312
4
payload
CRC
1
Power More
mgt
data
1
1
WEP
Rsvd
frame type
(RTS, CTS, ACK, data)
20
Week 3
802.11: mobility within same subnet
 H1 remains in same IP
subnet: IP address
can remain same
 switch: which AP is
associated with H1?
 self-learning
(Ch. 5):
switch will see frame
from H1 and
“remember” which
switch port can be
used to reach H1
router
hub or
switch
BBS 1
AP 1
AP 2
H1
BBS 2
21
Week 3
Point to Point Data Link Control
 one sender, one receiver, one link: easier than
broadcast link:
 no Media Access Control
 no need for explicit MAC addressing
 e.g., dialup link, ISDN line
 popular point-to-point DLC protocols:
 PPP (point-to-point protocol)
 HDLC: High level data link control (Data link
used to be considered “high layer” in protocol
stack!
22
Week 3
PPP Design Requirements [RFC 1557]
 packet framing: encapsulation of network-layer




datagram in data link frame
 carry network layer data of any network layer
protocol (not just IP) at same time
 ability to demultiplex upwards
bit transparency: must carry any bit pattern in the
data field
error detection (no correction)
connection liveness: detect, signal link failure to
network layer
network layer address negotiation: endpoint can
learn/configure each other’s network address
23
Week 3
PPP non-requirements
 no error correction/recovery
 no flow control
 out of order delivery OK
 no need to support multipoint links (e.g., polling)
Error recovery, flow control, data re-ordering
all relegated to higher layers!
24
Week 3
PPP Data Frame
 Flag: delimiter (framing)
 Address: does nothing (only one option)
 Control: does nothing; in the future possible
multiple control fields
 Protocol: upper layer protocol to which frame
delivered (eg, PPP-LCP, IP, IPCP, etc)
25
Week 3
PPP Data Frame
 info: upper layer data being carried
 check: cyclic redundancy check for error
detection
26
Week 3
Byte Stuffing
 “data transparency” requirement: data field must
be allowed to include flag pattern <01111110>
 Q: is received <01111110> data or flag?
 Sender: adds (“stuffs”) extra < 01111101> byte
before each < 01111110> data byte
 Receiver:
 01111101 and 01111110 bytes in a row: discard
first byte, continue data reception
 single 01111110: flag byte
27
Week 3
Byte Stuffing
flag byte
pattern
in data
to send
flag byte pattern plus
stuffed byte in
transmitted data
28
Week 3
PPP Data Control Protocol
Before exchanging networklayer data, data link peers
must
 configure PPP link (max.
frame length,
authentication)
 learn/configure network
layer information
 for IP: carry IP Control
Protocol (IPCP) msgs
(protocol field: 8021) to
configure/learn IP
address
29
Week 3
Link Layer
 5.1 Introduction and




services
5.2 Error detection
and correction
5.3Multiple access
protocols
5.4 Link-Layer
Addressing
5.5 Ethernet
 5.6 Hubs and switches
 5.7 PPP
 5.8 Link Virtualization:
ATM and MPLS
30
Week 3
Virtualization of networks
Virtualization of resources: a powerful abstraction in
systems engineering:
 computing examples: virtual memory, virtual
devices
 Virtual machines: e.g., java
 IBM VM os from 1960’s/70’s
 layering of abstractions: don’t sweat the details of
the lower layer, only deal with lower layers
abstractly
31
Week 3
The Internet: virtualizing networks
1974: multiple unconnected
nets
 ARPAnet
 data-over-cable
networks
 packet satellite network (Aloha)
 packet radio network
ARPAnet
"A Protocol for Packet Network Intercommunication",
V. Cerf, R. Kahn, IEEE Transactions on Communications,
May, 1974, pp. 637-648.
… differing in:
 addressing
conventions
 packet formats
 error recovery
 routing
satellite net
32
Week 3
The Internet: virtualizing networks
Internetwork layer (IP):
 addressing: internetwork
appears as a single, uniform
entity, despite underlying local
network heterogeneity
 network of networks
Gateway:
 “embed internetwork packets in
local packet format or extract
them”
 route (at internetwork level) to
next gateway
gateway
ARPAnet
satellite net
33
Week 3
Cerf & Kahn’s Internetwork Architecture
What is virtualized?
 two layers of addressing: internetwork and local
network
 new layer (IP) makes everything homogeneous at
internetwork layer
 underlying local network technology
 cable
 satellite
 56K telephone modem
 today: ATM, MPLS
… “invisible” at internetwork layer. Looks like a link
layer technology to IP!
Week 3
34
Generic connection – oriented
network
 For A to talk to B, there must be a special call setup packet





that travels from A to B, specifying B as the destination.
Each router along the path must make a routing decision
based on B’s address
This is the identical problem in IP
In addition to simply forwarding the call setup packet, the
goal is to assign the call a small identifier, which we now call
the CI (connection identifier)
CIs can be small because they are handed out dynamically
and are significant only on a link
They only need to be large enough to distinguish between
the total number of calls that might simultaneously be
routed on the same link
35
Week 3
A wants to talk to B and use CI
57
A
57 c,33
a
X
b
79c,22
33  a,57 33d,79
79a,33
c
R2
R1
c
a
R4
b
22b,79
c
B
R5
a
R3
 Why does the CI have to change hop by hop?
 The answer is that it would be very difficult to
choose a CI that was unused on all the links along
the path
Week 3
36
ATM and MPLS
 ATM, MPLS separate networks in their own
right

different service models, addressing, routing
from Internet
 viewed by Internet as logical link connecting
IP routers

just like dialup link is really part of separate
network (telephone network)
 ATM, MPLS: of technical interest in their
own right
37
Week 3
Asynchronous Transfer Mode: ATM
 1990’s/00 standard for high-speed (155Mbps to
622 Mbps and higher) Broadband Integrated
Service Digital Network architecture
 Goal: integrated, end-end transport of carry voice,
video, data
meeting timing/QoS requirements of voice, video
(versus Internet best-effort model)
 “next generation” telephony: technical roots in
telephone world
 packet-switching (fixed length packets, called
“cells”) using virtual circuits

38
Week 3
ATM architecture
 adaptation layer: only at edge of ATM network
data segmentation/reassembly
 roughly analagous to Internet transport layer
 ATM layer: “network” layer
 cell switching, routing
 physical layer

39
Week 3
ATM: network or link layer?
Vision: end-to-end
transport: “ATM from
desktop to desktop”
 ATM is a network
technology
Reality: used to connect
IP backbone routers
 “IP over ATM”
 ATM as switched
link layer,
connecting IP
routers
IP
network
ATM
network
40
Week 3
ATM Adaptation Layer (AAL)
 ATM Adaptation Layer (AAL): “adapts” upper
layers (IP or native ATM applications) to ATM
layer below
 AAL present only in end systems, not in switches
 AAL layer segment (header/trailer fields, data)
fragmented across multiple ATM cells
 analogy: TCP segment in many IP packets
41
Week 3
ATM Adaptation Layer (AAL) [more]
Different versions of AAL layers, depending on ATM
service class:
 AAL1: for CBR (Constant Bit Rate) services, e.g. circuit emulation
 AAL2: for VBR (Variable Bit Rate) services, e.g., MPEG video
 AAL5: for data (eg, IP datagrams)
User data
AAL PDU
ATM cell
42
Week 3
ATM Layer
Service: transport cells across ATM network
 analogous to IP network layer
 very different services than IP network layer
Network
Architecture
Internet
Service
Model
Guarantees ?
Congestion
Bandwidth Loss Order Timing feedback
best effort none
ATM
CBR
ATM
VBR
ATM
ABR
ATM
UBR
constant
rate
guaranteed
rate
guaranteed
minimum
none
no
no
no
yes
yes
yes
yes
yes
yes
no
yes
no
no (inferred
via loss)
no
congestion
no
congestion
yes
no
yes
no
no
43
Week 3
ATM Layer: Virtual Circuits
 VC transport: cells carried on VC from source to dest
 call setup, teardown for each call before data can flow
 each packet carries VC identifier (not destination ID)
 every switch on source-dest path maintain “state” for each
passing connection
 link,switch resources (bandwidth, buffers) may be allocated to
VC: to get circuit-like perf.
 Permanent VCs (PVCs)
long lasting connections
 typically: “permanent” route between to IP routers
 Switched VCs (SVC):
 dynamically set up on per-call basis

44
Week 3
ATM VCs
 Advantages of ATM VC approach:
QoS performance guarantee for connection
mapped to VC (bandwidth, delay, delay jitter)
 Drawbacks of ATM VC approach:
 Inefficient support of datagram traffic
 one PVC between each source/dest pair) does
not scale (N*2 connections needed)
 SVC introduces call setup latency, processing
overhead for short lived connections

45
Week 3
ATM Layer: ATM cell
 5-byte ATM cell header
 48-byte payload
Why?: small payload -> short cell-creation delay
for digitized voice
 halfway between 32 and 64 (compromise!)

Cell header
Cell format
46
Week 3
ATM cell header
 VCI: virtual channel ID
will change from link to link thru net
 PT: Payload type (e.g. RM cell versus data cell)
 CLP: Cell Loss Priority bit
 CLP = 1 implies low priority cell, can be
discarded if congestion
 HEC: Header Error Checksum
 cyclic redundancy check

47
Week 3
ATM VCs
 Advantages of ATM VC approach:
 QoS
performance guarantee for
connection mapped to VC (bandwidth,
delay, delay jitter)
 Drawbacks of ATM VC approach:
 Inefficient support of datagram traffic
 One PVC between each source/dest pair)
does not scale (N*2 connections needed)
 SVC introduces call setup latency,
processing overhead for short lived
Week 3
connections
48
Virtual Path Concept
 The connection identifier in the ATM cell header has
two complexities:



It’s hierarchical and divided into two subfields VPI (Virtual
Path Identifier) and VCI (Virtual Circuit Identifier)
VCI is 16 bits
VPI is 12 bits
 What’s a VPI? There might be very high speed
backbone carrying many millions of calls
 The split between VPI and VCI saves the switches in
the backbone from requiring that their call mapping
database keep track of millions of calls
49
Week 3
Virtual Path Concept
 The backbone routers only use the VPIU
field then if needed
 Outside the backbone, the switches treat
the entire VPI:VCI field as one
nonhierarchical unit
 VP switch looks at only the VPI portion
 VC switch looks at both
50
Week 3
Example
S2
a
b
S1
D
S3
e
c
S5
S4
S1 is to receive a call setup on port b with CI 17 for destination D
• Normal VP switching inside the core with the CI being the
12 bit VPI
• Switches outside the core do normal VC switching with the CI
being 28 bits
• Switches at the border also do VC swiching but the outgoing CI
must be chosen so that the VPI portion of the outgoing CI is
to the outgoing VPI
51
Week 3
Example
S8
a
89c,187.42
S1
c
S2
S9
d
S5
e
S3
S4
187.  d,13
13.  e,57
S6
d
57.42 d,83
64000 VCs can be carried within a single VP
dramatically reducing the switch table sizes
52
Week 3
Virtual Path and Virtual Channels
Virtual Channels (VC)
ATM Physical Link
Virtual Channel Connection (VCC)
Virtual Path (VP)
E3
OC–12
Virtual Path (VP)
Virtual Channels (VC)
Virtual Channel Connection
(VCC)
Contains Multiple VPs
Virtual Path
(VP)
Contains Multiple VCs
Virtual Channel
(VC)
Logical Path
Between ATM End Points
Connection Identifier = VPI/VCI
53
Week 3
ATM Switches
Input
Output
Port VPI/VCI Port
45
VPI/VCI
1
29
2
45
2
45
1
29
1
64
3
29
3
29
1
64
29
64
2
1
3
29
 ATM switches translate VPI/VCI values
 VPI/VCI value unique only per interface—
eg: locally significant and may be re-used elsewhere in
network
54
Week 3
VP and VC Switching
VC Switch
VCI 1
VCI 2
VPI 1
VP Switch
VCI 3
VPI 3
VCI 4
Port 2
VPI 2
VPI 2
Port 1
VCI 1
VCI 2
VCI 1
VCI 2
VPI 1
VPI 3
VPI 4
VPI 5
Port 3
Week 3
55
Virtual Channels
and Virtual Paths
Virtual Channel Connection (VCC)
Virtual Path
Connection (VPC)
UNI
UNI
NNI
VC
Switch
VPI = 1
VCI = 1
NNI
VP
Switch
VPI = 2
VCI = 44
VC
Switch
VPI = 26
VCI = 44
VPI = 20
VCI = 30
 This hop-by-hop forwarding is known as cell relay
56
Week 3
Virtual Path and Virtual Channels
Virtual Channels (VC)
ATM Physical Link
Virtual Channel Connection (VCC)
Virtual Path (VP)
E3
OC–12
Virtual Path (VP)
Virtual Channels (VC)
Virtual Channel Connection
(VCC)
Contains Multiple VPs
Virtual Path
(VP)
Contains Multiple VCs
Virtual Channel
(VC)
Logical Path
Between ATM End Points
Connection Identifier = VPI/VCI
57
Week 3
ATM Switches
Input
Output
Port VPI/VCI Port
45
VPI/VCI
1
29
2
45
2
45
1
29
1
64
3
29
3
29
1
64
29
64
2
1
3
29
 ATM switches translate VPI/VCI values
 VPI/VCI value unique only per interface—
eg: locally significant and may be re-used elsewhere in
network
58
Week 3
VP and VC Switching
VC Switch
VCI 1
VCI 2
VPI 1
VP Switch
VCI 3
VPI 3
VCI 4
Port 2
VPI 2
VPI 2
Port 1
VCI 1
VCI 2
VCI 1
VCI 2
VPI 1
VPI 3
VPI 4
VPI 5
Port 3
Week 3
59
Virtual Channels
and Virtual Paths
Virtual Channel Connection (VCC)
Virtual Path
Connection (VPC)
UNI
UNI
NNI
VC
Switch
VPI = 1
VCI = 1
NNI
VP
Switch
VPI = 2
VCI = 44
VC
Switch
VPI = 26
VCI = 44
VPI = 20
VCI = 30
 This hop-by-hop forwarding is known as cell relay
60
Week 3
Example
61
Week 3
ATM Physical Layer (more)
Two pieces (sublayers) of physical layer:
 Transmission Convergence Sublayer (TCS): adapts
ATM layer above to PMD sublayer below
 Physical Medium Dependent: depends on physical
medium being used
TCS Functions:
 Header checksum generation: 8 bits CRC
 Cell delineation
 With “unstructured” PMD sublayer, transmission
of idle cells when no data cells to send
62
Week 3
ATM Physical Layer
Physical Medium Dependent (PMD) sublayer
 SONET/SDH: transmission frame structure (like a
container carrying bits);
 bit synchronization;
 bandwidth partitions (TDM);
 several speeds: OC3 = 155.52 Mbps; OC12 = 622.08
Mbps; OC48 = 2.45 Gbps, OC192 = 9.6 Gbps
 TI/T3: transmission frame structure (old
telephone hierarchy): 1.5 Mbps/ 45 Mbps
 unstructured: just cells (busy/idle)
63
Week 3
IP-Over-ATM
Classic IP only
 3 “networks” (e.g.,
LAN segments)
 MAC (802.3) and IP
addresses
IP over ATM
 replace “network”
(e.g., LAN segment)
with ATM network
 ATM addresses, IP
addresses
ATM
network
Ethernet
LANs
Ethernet
LANs
64
Week 3
IP-Over-ATM
app
transport
IP
Eth
phy
IP
AAL
Eth
ATM
phy phy
ATM
phy
ATM
phy
app
transport
IP
AAL
ATM
phy
65
Week 3
Datagram Journey in IP-over-ATM Network
 at Source Host:
 IP layer maps between IP, ATM dest address (using ARP)
 passes datagram to AAL5
 AAL5 encapsulates data, segments cells, passes to ATM layer
 ATM network: moves cell along VC to destination
 at Destination Host:
AAL5 reassembles cells into original datagram
 if CRC OK, datagram is passed to IP

66
Week 3
IP-Over-ATM
Issues:
 IP datagrams into
ATM AAL5 PDUs
 from IP addresses
to ATM addresses
 just like IP
addresses to
802.3 MAC
addresses!
ATM
network
Ethernet
LANs
67
Week 3
ATM Layer
Service: transport cells across ATM network
 analogous to IP network layer
 very different services than IP network
Guarantees ?
layer Service
Congestion
Network
Architecture
Internet
Model
best effort
ATM
CBR
ATM
VBR
ATM
ABR
ATM
UBR
Bandwidth Loss Order Timing feedback
none
no
no
no
constant
rate
guaranteed
rate
guaranteed
minimum
none
yes
yes
yes
yes
yes
yes
no
yes
no
no (inferred
via loss)
no
congestion
no
congestion
yes
no
yes
no
no
68
Week 3
Traffic Management
 Why traffic management?
 Traffic control techniques
 AAL5/ABR congestion feedback
 Buffers are your friend
69
Week 3
Why Traffic Management?
 Proactively combat congestion
 Provision for priority control
 Maintain well-behaved traffic
70
Week 3
Why Traffic Management?
Cell Loss—Data’s Critical Enemy
Ethernet (1500 Bytes) = 32 Cells
FDDI (4470 Bytes) = 96 Cells
IP over ATM–1577 (9180 Bytes) = 192 Cells
TCP/IP Packet
X
 Lose one cell and the rest are useless
 Need to re-transmit 32+ cells for one cell lost
 Congestion collapse is the result
 PPD (Partial Packet Discard)
 EPD (Early Packet Discard)
71
Week 3
Traffic Control Techniques
 Connection management—Acceptance
 Traffic management—Policing
 Traffic smoothing—Shaping
72
Week 3
Traffic Control Techniques
Connection Management
Contract
Contract
Contract
ATM Network
• Traffic Parameters
Peak cell rate
Sustainable cell rate
Burst tolerance
Etc.
• Quality of Service
Delay
Cell loss
73
Week 3
Traffic Descriptors
 Peak Cell Rate(PCR) = 1/T in units of cells/second,
where T is the minimum intercell spacing in
seconds(i.e., the time interval from the first bit of
one cell to the first bit of the next cell)
 Sustainable Cell Rate(SCR) is the maximum
average rate that a bursty, on-off traffic source
can be sent at the peak rate
 Maximum Burst Size(MBS) is the maximum number
of cells that can be sent at the peak rate
74
Week 3
QoS Expectations
Applications have service requirements on:
Throughput
Maximum Delay
Variance of Delays(Delay Jitter)
Loss Probability
Network has to guarantee the required
Quality of Service(Traffic Contract)
Major Problem: Bursty Traffic,
 i.e., Peak Traffic Rate >> Average Traffic
Rate
75
Week 3
Traffic Control Techniques
Connection Management
Connection Admission Control (CAC)
I want a VC:
X Mbps
Y Delay
Z Cell Loss
CAC
Can I Support this
Reliably without
Jeopardizing Other
Contracts
Guaranteed QoS Request
No
or
Yes, Agree to a
Traffic Contract
Contract
ATM Network
76
Week 3
Connection Admission Control
 The primary function of the CAC is to accept a
new connection request only if its stated QoS can
be maintained without influencing the QoS of the
already accepted connections.
 It is very likely that certain calls will require
more than one connection (e.g., teleconferencing)
CAC procedure must be performed for each
requested VCC or VPC.
 CAC must
 Decide whether connections can be accepted or
not.
 Provide parameters required by the UPC.
 Perform routing and resource allocation.
Week 3
77
Bandwidth Allocation
 Peak Allocation
– Suppose a source has an average BW of 20 Mbps and a
peak BW of 45 Mbps. Peak BW allocation requires that
45 Mbps be reserved at the output port for the specific
source independent of whether or not the source
transmits continuously at 45 Mbps.
– Peak BW allocation is used for CBR services. The
advantage of peak BW allocation is that it is easy to
decide whether to accept a new connection or not.
– The new connection is accepted, if the sum of the peak
rates of all the existing connections plus the peak rate of
the new connection is less than the capacity of the
output link.
– The disadvantage of the Peak BW allocation is that the
output port link will be underutilized if the sources do
not transmit at their peak rates.
Week 3
78
Bandwidth Allocation
Statistical Allocation
The allocated BW is less than the peak rate of
the source.
The sum of all peak rates may be greater than
the capacity of the output link.
An equivalent capacity is allocated between the
peak rate and the mean rate
Call admission: if the sum of the equivalent
capacities is less than the capacity, reject the
incoming call
79
Week 3
Source BehaviorCell
Interarrival
Time
CBR
time
VBR
Burst Duration
Cell
Interarrival
Time
Burst to Burst
Interval
time
Call Duration
Call Tear-Down
Call Set-up
VBR Source Description:
ON
OFF
or
Burst Length Distribution
Interarrival Distribution
During Burst
Idle (silent) Length Distribution
Peak Arrival Rate
Average Arrival Rate
Mean Burst Length
< Bp, Bm, T >
80
Week 3
End-to-end Model
CAC is based on an abstract
performance model of the
network.
Multiplexing
Entering
Entering
Entering
Cross Traffic Cross Traffic Cross Traffic
Demultiplexing
Departing
Departing
Departing
Cross Traffic Cross Traffic Cross Traffic
- FINITE BUFFERS
- DETERMINISTIC SERVICE TIMES
Modeling Problems
Challenges
- Arrival streams are non-Poisson
- Finite buffers at the multiplexers and switches
- Correlated cell arrivals
- Large state-space of the resulting system
- Simulations of such systems take very long to converge
81
Week 3
Traffic Control Techniques
Traffic Management
Usage Parameter Control (UPC) aka Policing
Contract
REBEL
APPLICATION
You are
Not in Conformance
with the Contract.
What Should the
Penalty Be??
?DECISION?
• PASS
ATM Network • MARK CLP BIT
• DROP
82
Week 3
Traffic Control Techniques
Traffic Management
UPC
Marked
0
0
0
D
r
o
p
0
1
0
?DECISION?
• PASS
• MARK CLP BIT
• DROP
 CLP Control—When congested drop marked cells
 Public UNI—Generic Cell Rate Algorithm (GCRA)
83
Week 3
Policing
 The operation of the CAC and the correct allocation of resources
depend heavily on the guarantee that the traffic source will behave as
expected, i.e., as described by the traffic descriptor.
 Thus a monitoring/policing function is needed to force the traffic to
comply to the traffic descriptor.
 This monitoring/policing function is performed by the UPC (policer).
 The UPC is in the form of preventive congestion control.
 It enforces a certain cell arrival rate or “shape”, such that it does not
exceed certain values that would cause network elements to overload
and lead to congestion.
 A UPC usually consists of a counter-based mechanism that drops or
marks data units when they are found in violation of a certain
agreement between end-user and the communication system.
 It does not use information from remote network elements.
84
Week 3
Generic Cell Rate Algorithm (I, L)
The GCRA is reference algorithm for a cell rate which determines if a cell is conforming.
Arrival of a cell k at time ta (k)
TAT  ta(k)
Non
Conforming
Cel
YES
YES
X’=X-(ta(k)-LCT)
TAT = ta(k)
X’< 0
TAT < ta(k) + L
NO
Non
Conforming
Cell
X’>= L
X’=0
X=X’+I
LCT = ta(k)
Conforming Cell
TAT = TAT + I
Conforming Cell
VIRTUAL SCHEULING
ALGORITHM
TAT Theoretical Arrival Time
ta(k) Time of arrival of a cell
YES
YES
I : Increment
L : Limit
Virtual Scheduling Algorithm
TAT:= ta(1) initially
CONTINUOUS-STATE
LEAKY BUCKET ALGORITHM
X : Value of the Leaky Bucket counter
X’ : auxiliary variable
LCT Last Compliance Time
Leaky Bucket Algorithm
X := 0
LCT := ta(1) initially
85
Week 3
Traffic Contact and
Performance Definitions
 CBR
 GCRA(T0+1 , CDVT) in relation to the PCR0+1
 T0+1 is the inverse of PCR0+1
 Nonconformant cells are dropped
 VBR (one of the standardized definitions)
 GCRA(T0+1 , CDVT) in relation to the PCR0+1
 GCRA(Ts0 , BT0 + CDVT) in relation to the SCR of the CLP
= 0 cell stream
• BT = (MBS – 1) (1/SCR - 1/PCR)


If CLP = 0 cell conforms to (1) and (2), that cell is
conformant
If CLP = 0 cell is not conforming to (2) but is conforming
to (1) then it will be remarked as CLP = 1
Week 3
86
Example
• Consider a Video-on-Demand service where the negotiated PCR = 50kcells/s
and the CDV Tolerance ( ) =50sec.
• The cells arrive at times as indicated by t(k).
Note: GCRA(I,L) where I = T = 1/PCR = 20sec/cell and L = t = 50  sec.
GCRA(T,)
Figure: Example of the GCRA
LCT(k)
0
T(k)
0s
X(k)
X'(k)
0s
0s
0s
Yes
1
20s
0s
20s
0s
Yes
2
25s
20s
20s
15s
Yes
3
30s
25s
35s
30s
Yes
4
35s
30s
50s
45s
Yes
k
Co nforming
40s
35s
65s
60s
No
5
6
45s
35s
65s
50s
No
7
50s
35s
65s
50s
No
8
55s
50s
70s
65s
No
9
80s
50s
70s
40s
Yes
10
100s
80s
60s
40s
Yes
22
87
Week 3
Traffic Control Techniques
Traffic Management
UPC
Marked
0
0
0
D
r
o
p
0
3
1
0
2
 Intelligent Packet Discard—IPD
 Discard cells from same ‘bad’ packet
 Tail packet discard
 Maximize “Goodput”
88
Week 3
Traffic Control Techniques
Traffic Smoothing
I Want to
Comply With My
Contract. So, I Will
Smooth/Shape
My Traffic
Shaper
Go Ahead,
Make My Day
Actual Data
Shaped Data
Private ATM Network
Public ATM Network
 Traffic shaper at customer site
 Changes traffic characteristics
 Leaky bucket algorithm
89
Week 3
Traffic Control Techniques
Buffers Are Your Friend
 Absorb traffic bursts from
simultaneous connections
 Switches schedule traffic based on priority
of traffic according to QoS
 Switch must reallocate buffers as the traffic mix changes
 Effective buffering maximizes throughput
of usable cells as opposed to raw cells
(aka goodput)
90
Week 3