Advanced Network Technologies Multimedia 2/2
Dr. Wei Bao | Lecturer School of Computer Science
Network support for Multimedia
Network support for multimedia
Three broad approaches towards providing network-level support for multimedia apps
Approach
Granularity
Guarantee
Mechanisms
Complex
Deployed?
1. Making best of best effort service
All traffic treated equally
None
No network support(all at app)
low
everywhere
2. Differentiated service
Traffic class
None or soft
Packet mark, scheduling, policing
medium
some
3. Per- connection QoS
Per- connection flow
Soft or hard after flow admitted
Packet mark, scheduling policing
high
Little to none
Providing multiple classes of services
› thus far: making the best of best effort service – one-size fits all service model
› alternative: multiple classes of service
– partition traffic into classes
– network treats different classes of traffic differently (analogy: VIP service versus regular service)
› granularity: differential service among multiple classes, not among individual connections
› How: ToS bits
0111
Multiple classes of services: scenarios
H1
R1
H3
H2
R1 output interface queue
R2
1.5 Mbps link
H4
Scenario 1: mixed HTTP and VoIP
› example: 1Mbps VoIP (Video and Voice), HTTP share 1.5 Mbps link. – HTTP bursts can congest router, cause video/audio loss
– want to give priority to audio over HTTP
R1
Principle 1
R2
packet marking needed for router to distinguish between different classes; and new router policy to treat packets accordingly
Principles for QOS guarantees
› what if applications misbehave (VoIP sends higher than declared rate) – policing: force source adherence to bandwidth allocations
› marking, policing 1 Mbps
phone
Principle 2
provide protection for one class from others
R1
R2
1.5 Mbps link packet marking and policing
Principles for QOS guarantees (con’t)
› allocating fixed (non-sharable) bandwidth to flow: inefficient use of bandwidth if flows doesn’t use its allocation
1 Mbps logical link
R2
1.5 Mbps link
0.5 Mbps logical link
Principle 3
while providing protection, it is desirable to use resources as efficiently as possible
1 Mbps
phone R1
Scheduling and policing mechanisms
› scheduling: choose next packet to send on link
› FIFO (first in first out) scheduling: send in order of arrival to queue
– real-world example?
– discard policy: if packet arrives to full queue: who to discard?
– tail drop: drop arriving packet
– priority: drop/remove on priority basis – random: drop/remove randomly
packet arrivals
queue link
packet departures
(waiting area)
(server)
Scheduling policies: priority
priority scheduling: send highest priority queued packet
non-preemptive
› multiple classes, with different priorities
– class may depend on marking or other header info, e.g. IP source/dest, port numbers, etc.
– real world example?
high priority queue (waiting area)
arrivals
departures
classify link
low priority queue (server)
(waiting area)
2 1345
arrivals
packet in service
departures
1
3
2
4
5
1324 5
Scheduling policies: priority
arrivals departures
classify link
low priority queue (server) (waiting area)
Scheduling policies: priority
arrivals departures
classify link
low priority queue (server) (waiting area)
Scheduling policies: priority
arrivals departures
classify link
low priority queue (server) (waiting area)
Scheduling policies (con’t)
Round Robin (RR) scheduling:
› multiple classes, with equal priority
› cyclically scan class queues, sending one complete packet from
each class (if available)
2 1345
arrivals
packet in service
departures
1
3
2
4
5
1334 5
Scheduling policies: RR
arrivals departures
classify link
low priority queue (server) (waiting area)
Scheduling policies: RR
arrivals departures
classify link
low priority queue (server) (waiting area)
Scheduling policies: RR
arrivals departures
classify link
low priority queue (server) (waiting area)
Scheduling policies: RR
arrivals departures
classify link
low priority queue (server) (waiting area)
Scheduling policies (con’t)
Weighted Fair Queuing (WFQ):
› generalized Round Robin
› each class gets weighted amount of service in each cycle
Scheduling policies (con’t)
Weighted Fair Queuing (WFQ):
› Each class i is assigned a weight wi
› Guarantee: if there are class i packets to send (during some interval) then class i receives a fraction of service which is
wi / ( ∑wj )
› On a link with transmission rate R, class i achieves throughput Rwi / ( ∑wj )
› WFQ is part of routers QoS [Cisco 2012]
2
1 3
Scheduling policies (con’t)
Example:
One link has capacity 1 Mbps. Three flows: Flow 1 is ensured with 0.5 Mbps data rate; Flow 2 is ensured with 0.25 Mbps; Flow 3 is ensured with 0.25 Mbps.
Weighted queue: w1=2, w2=1, w3=1
Efficiency:
When flow 3 has nothing to transmit, but flow 1 and flow 2 have many packets to send
Flow 1: 2/3 Mbps Flow 2: 1/3 Mbps
Marking and Policing
Policing mechanisms
goal: to limit traffic to not exceed declared parameters (the rate at which a class or flow is allowed to inject packets into the network)
› Three important policing criteria (differing on the time scale):
› 1. (long term) average rate: how many pkts can be sent per unit of time (in
the long run)
– e.g., 6000 packets per min
– 2.peak rate: limit the number of packets can be sent over a relatively shorter period of time, e.g., 6000 pkts per minute (ppm) in average but 3000 packets per 5 second peak rate max.
– 3. (max.) burst size: max number of pkts sent “instantaneously” into the networks, e.g., 1500 packets.
Policing mechanisms: implementation
token bucket: limit input to specified burst size and average rate (useful to police the flow)
› bucket can hold b tokens
› a packet must remove a token from bucket to be transmitted into the network
› tokens generated at rate r token/sec unless bucket full (token ignored)
› over interval of length t: number of packets admitted less than or equal to (rt + b) › Token-generation rate r limits the rate at which packets enter the network
t->0, b packets t->∞, (rt+b)/t = r packets/second
Policing and QoS guarantees
› Combining token bucket and WFQ to provide guaranteed upper bound on delay, i.e., QoS guarantee!
arriving traffic
token rate, r1
bucket size, b1
per-flow
WFQ rate, R
D =Lb /(Rw /(∑w))
arriving traffic
› Packets arrive while the bucket is full (b1). The last packet has a maximum delay of Dmax. L packet size.
max
11j
Differentiated services in reality
› want “qualitative” service classes
– relative service distinction: Platinum (VIP), Gold, Silver
› scalability: simple functions in network core, relatively complex functions at edge routers (or hosts)
maDrkififnsgerv architecture
r
b
.
scheduling
edge router:
› per-flow traffic management › marks packets as differently
› E.g. Alice’ traffic: high › Bob’s traffic: high
› Chris’s traffic: low
core router:
› per class traffic management
› buffering and scheduling based on
marking at edge
› Red packets vs green packets
Edge-router packet marking
› profile: pre-negotiated rate r, burst (bucket) size b › packet marking at edge based on per-flow profile
rate r
b
Example:
user packets
› class-basedmarking:packetsofdifferentclassesmarkeddifferently
› intra-classmarking:conformingportionofflowmarkeddifferentlycomparedwithnon-conformingone
› Bobagreestotransmitat1Mbps,butheistransmittingat2Mbps
› Halfofthem(conforming)aremarkedgreen.
› Others(non-conforming)aremarkedred(lowerpriority)ordropped.
Edge-router packet marking
› Example
› green > yellow >red .
› 2Mbps link, Bob, telephone traffic, declare 1 Mbps
› Green if conforming, red if not conforming › Chris, web browsing traffic
› Yellow
› Priority queue in the core network
› Bob can guarantee 1Mbps data rate › If Bob transmits >1Mbps
› If Chris transmits at 1Mbps, all red will be dropped. Bob gets 1Mbps › If Chris transmits at <1Mbps, some red will still get through.
Classification, conditioning
› user declares traffic profile (e.g., rate, burst size)
› traffic metered, shaped if non-conforming
› the meter compares the incoming flow to the negociated traffic profile. Network administrator can decide whether to remark, forward, delay, or drop a non- conforming packet
Per-connection QoS guarantees
› basic fact of life: cannot support traffic demands beyond link capacity
1 Mbps phone
R1
R2
1.5 Mbps link
Reject!
Principle 4
1 Mbps phone
call admission: flow declares its needs, network may block call (e.g., busy signal) if it cannot meet needs
Wireless and mobile networks
Elements of a wireless network
wired network infrastructure
Wireless and Mobile Networks: 7- 33
Elements of a wireless network
wireless hosts
laptop, smartphone, IoT run applications
may be stationary (non-mobile) or mobile • wireless does not always mean mobility!
wired network infrastructure
Wireless and Mobile Networks: 7- 34
Elements of a wireless network
base station
typically connected to wired network
relay - responsible for sending packets between wired network and wireless host(s) in its “area”
• e.g., cell towers, 802.11 access points
wired network infrastructure
Wireless and Mobile Networks: 7- 35
Elements of a wireless network
wired network infrastructure
wireless link
typically used to connect mobile(s) to base station, also used as backbone link
multiple access protocol coordinates link access
various transmission rates and distances, frequency bands
Wireless and Mobile Networks: 7- 36
C
haracteristics of selected wireless links
802.11ax
802.11ac
802.11 af,ah
802.11g
802.11b
Bluetooth
802.11n
5G
4G LTE
14 Gbps 10 Gbps
3.5 Gbps 600 Mbps
54 Mbps 11 Mbps
2 Mbps
Indoor Outdoor 10-30m 50-200m
Midrange outdoor
200m-4Km
Long range outdoor
4Km-15Km
Wireless and Mobile Networks: 7- 37
IEEE 802.11 WiFi
IEEE 802.11 standard
Year
Max data rate
Range
Frequency
802.11b
1999
11 Mbps
30m
2.4 Ghz
802.11a
1999
54 Mbps
30m
5 Ghz
802.11g
2003
54 Mbps
30m
2.4 Ghz
802.11n (WiFi 4)
2009
600 Mbps
70m
2.4, 5 Ghz
802.11ac (WiFi 5)
2013
3.47Gpbs
70m
5 Ghz
802.11ax (WiFi 6)
2020 (exp.)
14 Gbps
70m
2.4, 5 Ghz
802.11af
2014
35 – 560 Mbps
1 Km
unused TV bands (54-790 MHz)
802.11ah
2017
347Mbps
1 Km
900 Mhz
all use CSMA/CA for multiple access, and have base-station and ad- hoc network versions
Wireless and Mobile Networks: 7- 38
Elements of a wireless network
wired network infrastructure
infrastructure mode
base station connects mobiles into wired network
handoff: mobile changes base station providing connection into wired network
Wireless and Mobile Networks: 7- 39
Elements of a wireless network
ad hoc mode
no base stations
nodes can only transmit to other nodes within link coverage
nodes organize themselves into a network: route among themselves
Wireless and Mobile Networks: 7- 40
Wireless network taxonomy
single hop
multiple hops
infrastructure (e.g., APs)
no infrastructure
host connects to base station (WiFi, cellular) which connects to larger Internet
no base station, no connection to larger Internet (Bluetooth, ad hoc nets)
host may have to relay through several wireless nodes to connect to larger Internet: mesh net
no base station, no connection to larger Internet. May have to relay to reach other a given wireless node MANET, VANET
Wireless and Mobile Networks: 7- 41
Wireless link characteristics
Wireless Link Characteristics (1)
important differences from wired link ....
- decreased signal strength: radio signal attenuates as it
propagates through matter (path loss)
- interference from other sources: standardized wireless network frequencies (e.g., 2.4 GHz) shared by other devices (e.g., phone);
- multipath propagation: radio signal reflects off objects ground, arriving at destination at slightly different times
.... make communication across (even a point to point) wireless link much more “difficult”
dB decibel
› logarithmic unit used to express the ratio of two (power) values › 10*log10(PS/PN)
› PS/PN=10
› PS/PN=100
› PS/PN=1000 › PS/PN=10000 ›...
10 dB 20 dB 30 dB 40 dB
Wireless Link Characteristics (2)
› SNR: signal-to-noise ratio
- larger SNR – easier to extract
10-1 10-2 10-3
signal from noise (a “good thing”) - BER: bit error rate
10-4 › SNR versus BER tradeoffs 10-5
- given physical layer modulation: increase power -> increase SNR -> decrease BER
– Different physical layer modulation: Quadrature amplitude modulation
Binary Phase-shift keying Higher data rate -> Higher BER
10-6 10-7
10 20 30 40
SNR(dB)
QAM256 (8 Mbps) QAM16 (4 Mbps)
BPSK (1 Mbps)
BER
Wireless Link Characteristics (2)
› SNR: signal-to-noise ratio
– larger SNR – easier to extract
10-1 10-2 10-3
signal from noise (a “good thing”) – BER: bit error rate
10-4 › SNR versus BER tradeoffs 10-5
– given SNR, BER requirement: choose modulation to achieve highest throughput
– 15 dB, require 10-3 BER – Which modulation?
– QAM16
10-6 10-7
10 20 30 40
SNR(dB)
QAM256 (8 Mbps) QAM16 (4 Mbps)
BPSK (1 Mbps)
BER
Wireless network characteristics (3)
Multiple wireless senders and receivers create additional problems (beyond multiple access):
AB A’s signal
strength
space
Signal attenuation:
C
C’s signal strength
C
Hidden terminal problem
B, A hear each other
B, C hear each other
B
A
A, C can not hear each other means A, C unaware of their interference at B
B, A hear each other
B, C hear each other
A, C can not hear each other interfering at B
CDMA
Code Division Multiple Access (CDMA)
› unique “code” (chipping sequence) assigned to each user;
› all users share same frequency, but each user has own “chipping” sequence
(i.e., code) to encode data
– length of sequence: M
– allows multiple users to “coexist” and transmit simultaneously with minimal interference (if codes are “orthogonal”)
– orthogonal:
– inner product of ci,1 ci,2 …ci,M and cj,1 cj,2 …cj,M is Σm ci,m.cj,m
– inner product(user i’s chipping sequence, user j’s chipping sequence) =0 – inner product(user i’s chipping sequence, user i’s chipping sequence) =M
› encoded signal = (original data) X (chipping sequence)
› decoding: inner-product of encoded signal and chipping sequence
CDMA encode/decode
data bits
code
Zi,m= di.cm
channel output Zi,m
slot 0 channel output
1
1
1
1
1
d1 = -1
d0 = 1
sender
slot 1 channel output
M
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
1
1
1
1
1
-1
slot 1
slot 0
-1
-1
-1
-1
-1
-1
-1
1
1
1
M
Di = ΣZi,m.cm m=1
received input
code
receiver
slot 1
slot 0
slot 1 channel output
slot 0 channel output
1
1
1
1
1
1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
d1 = -1
1
1
1
1
1
1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
d0 = 1
User i receives user i‘s signals
sender di
receiver Inner product
1 -1
cm Zi,m
-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 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 1 -1 -1 -1 -1 -1 -1 1 -1 1 1 1
M
Di = ΣZi,m.cm m=1
M
Di
uses its chipping sequence to send and to receive: receive the correct bits
8/8=1
-8/8=-1
User 2 receives user 1‘s signals
sender 1’s bits
receiver 2 Innerproduct
di 1 -1
cm Zi,m
-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-11 11-11
-1-1+1+1-1+1-1+1=0!
0/8=0
-1 -1 -1 1 -1 1 1 1 1 1 1 -1 1 -1 -1 -1
1 1 1 -1 1 -1 -1 -1
11-1 11 1-1 1
0/8=0
M
Di = ΣZi,m.c’m m=1
M
Di
Use 1’s chipping sequence to send and use 2’s chipping sequence to receive: receive nothing!
Reason: 1’s chipping sequence is orthogonal to 2’s chipping sequence.
Sender 1 Sender 2
x x
+
inner product (
1’s bit * 1’s chipping sequence
+2’s bit * 2’s chipping sequence
+… +…
+N’s bit * N’s chipping sequence, 1’s chipping sequence)/M
1’s chipping sequence
1’s chipping sequence
2’s chipping sequence
… …
Sender N
x
N’s chipping sequence
Sender 1 Sender 2 … Sender N
x x
x
…
+
= 1’s bit * inner product (
1’s chipping sequence,
1’s chipping sequence)/M
+ 2’s bit * inner product (
2’s chipping sequence,
1’s chipping sequence)/M 0 +…
+ N’s bit * inner product ( 0 N’s chipping sequence,
1’s chipping sequence)/M
1’s chipping sequence
1’s chipping sequence
2’s chipping sequence
N’s chipping sequence
Sender 1 Sender 2 … Sender N
x x
x
…
+
= 1’s bit * inner product ( 1’s chipping sequence, 1’s chipping sequence)/M =1’s bit
1’s chipping sequence
1’s chipping sequence
2’s chipping sequence
N’s chipping sequence
Sender 1 Sender 2
CDMA: two-sender interference
channel sums together transmissions by sender 1 and 2
using same code as sender 1, receiver recovers sender 1’s original data from summed channel data!