Transcript ppt

Advanced Computer Networks
cs538, Fall 2014 @ UIUC
Klara Nahrstedt
Lecture 8, September 18, 2014
Based on
Zheng Wang and Jon Crowcroft, “QoS Routing for Supporting Multimedia Applications”,
IEEE JSAC 1996
Announcements
• Next Reading for Thursday, September 26:
• X. Yang, D. Clark, A. Berger, “NIRA: A New Inter-Domain Routing Architecture”, IEEE/ACM
Transactions on Networking, Vol. 15, No. 4, August 2007
• Proposals for Final Projects
• Prepare project proposal
•
•
•
•
At most 1 page describing
Problem description
Steps you plan to take to address the problem
Related work (at least 3 full academic papers citations) and why your proposed problem is different than
those or why your proposed solution is better.
• Deadline for proposal: 11:59pm Tuesday, September 23, 2014
• No CLASS on Tuesday, September 23, 2014
• Submit project proposal via email to instructor:
[email protected] (with subject: cs538 – Final Project Proposal)
Outline
• QoS Concept
• Single Mixed Metric
• Multiple Metrics
• Bandwidth and Delay QoS Routing Problem
• Path Computation Algorithms
• Source Routing Algorithms
• Hob-by-Hop Routing Algorithms
Window of Resources
Requirements
sufficient
Insufficient Sufficient
But scarce
Interactive
HDTV-quality
multi-view video
Sufficient
To
abundant
insufficient
HDTV
High-quality
Audio
Sufficient but
Scarce to
Sufficient
abundant
insufficient
insufficient
Sufficient
Network
File access
Sufficient
But scarce
1980
CS 414 - Spring 2011
1990
2000
abundant
2010
2020
Hardware
support
Quality of Service (How to parameterize
services?)
• To manage resources, we need services over resources
• to schedule AV data, to shape access for AV data, to process AV data, to
move AV data, etc.
• Multimedia systems consist of set of AV-specific services
• Processing (media-related) services: retrieve audio/video, record
video/audio, compress audio/video, fast forward video, rewind video
• Transport (network) services: Stream video, fast forward video, rewind
video
• To provide multimedia services, services get parameterized with
quality levels called Quality of Service
CS 414 - Spring 2011
Layered Model for QoS
Quality of
Experience
Quality of
Service
CS 414 - Spring 2011
Application AV QoS Parameters
• QoS for Audio service:
• Sample rate – 8000 samples/second (8KHz), 44.1 KHz
• Sample resolution – 8 bits per sample, 16 bits per sample
• QoS for Video service:
• Video frame rate – 25 frames per second, 30 frames per second
• Frame Period – 40 ms, 30 ms, 25 ms, …
• Frame resolution – 320x240 pixels, 640x480 pixels, 1920x1080
pixels, …
• Pixel resolution – 24 bits per pixel, 8 bits per pixel
• Frame size – 64KB
• Compression rate – 8:1
CS 414 - Spring 2014
Network QoS
• Bandwidth – Rate of data transfer, Bit Rate
• e.g., 1 Gbps (Ethernet throughput) – level 1
• e.g., 100 Mbps (WiFi throughput) – level 2
• e.g., 128 kbps (ISDN throughput) – level 3
• measured in bits per second
• Throughput – rate of successful message delivery
over communication channel
• Measured in packets per second, data packets per time
slot, or bits per second
• 30 packets per second; 128 kbps, 10 packets per time slot
CS 414 - Spring 2014
Network QoS
• Connection setup time
• time how long it take to connect the sender and receiver
• e.g., 50 ms, 10 ms, …
• Error Rate
• Measures the total number of bits (packets) that were corrupted or
incorrectly received compared with the total number of transmitted bits
(packets)
• Bit Error Rate (BER) – at physical/MAC layer
• In fiber optics, bit error rate (BER) is of the order of 10-8 to 10-12.
• In satellite networks, BER is of the order 10-7
• Packet Error Rate (PER) – at IP/transport/application layer – also called Packet Loss Rate
CS 414 - Spring 2014
Network QoS
• Delay
• Latency
• End-to-end delay in telecommunication
• Response time
• Round-trip delay in telecommunication
• End-to-End Delay
• time interval from the time packet is sent from the sender until the
time it is received at the receiver (Treceive – Tsend)
• e.g., 80 ms, 100 ms, 160 ms
CS 414 - Spring 2014
Network QoS
• Response Time
• Measured as round-trip delay and is the total time
required for sender to send a packet and receive an
acknowledgement from the receiver. It can be described as
sum of network delay and interface delay.
• Network delay – composed of transit delay and transmission delay
• Transit delay is caused by time needed to send data on a physical connection
between sender and receiver
• Transmission delay is time needed to transmit packet through network as
result of processing delays (e.g., look up routing tables)
• Interface delay – incurred between the time a sender is ready to
begin sending and the time a network is ready to accept and
transmit the data (due to traffic policing and shaping)
CS 414 - Spring 2014
Other QoS Parameters
• Jitter
• Undesired deviation from true periodicity in telecommunication
• Also called packet delay variation – important QoS factor in assessment of network
performance
• Packet jitter – variation in latency as measured in the variability over time of
the packet latency across network.
CS 414 - Spring 2014
QoS Classes
• Guaranteed Service Class
• QoS guarantees are provided based on deterministic and
statistical QoS parameters
• Predictive Service Class
• QoS parameter values are estimated and based on the past
behavior of the service
• Best Effort Service Class
• There are no guarantees or only partial guarantees are
provided
CS 414 - Spring 2011
QoS Classes (cont.)
QoS Class determines: (a) reliability of offered QoS, (b) utilization of resources
CS 414 - Spring 2011
Deterministic QoS Parameters
• Single Value: QoS1 – average (QoSave), contractual
value, threshold value, target value
• Throughput – 10 Mbps
• Pair Value: <QoS1, QoS2> with
QoS1 – required value; QoS2 – desired value
<QoSavg,QoSpeak>; <QoSmin, QoSmax>
• Throughput - <8,12> Mbps
CS 414 - Spring 2011
Deterministic QoS Parameter Values
• Triple of Values <QoS1, QoS2, QoS3>
• QoS1 – best value
• QoS2 – average value
• QoS3 – worst value
• Example:
• <QoSpeak, QoSavg, QoSmin>, where QoS is network bandwidth
• Throughput <12, 10, 8> Mbps
CS 414 - Spring 2011
Guaranteed QoS
• We need to provide 100% guarantees for QoS values (hard
guarantees) or very close to 100% (soft guarantees)
• Current QoS calculation and resource allocation are based on:
1.
2.
Hard upper bounds for imposed workloads
Worst case assumptions about system behavior
1. Advantages: QoS guarantees are satisfied even in the worst
case case (high reliability in guarantees)
2. Disadvantage: Over-reservation of resources, hence
needless rejection of requests
CS 414 - Spring 2011
Predictive QoS Parameters
• We utilize QoS values (QoS1, ..QoSi) and compute
average
• QoSbound step at K>i is QoSK = 1/i*∑jQoSj
• We utilize QoS values (QoS1, , QoSi) and compute
maximum value
• QoSK = max j=1,…i (QoSj)
• We utilize QoS values (QoS1, , QoSi) and compute
minimum value
• QoSK = min j=1,…i (QoSj)
CS 414 - Spring 2011
Best Effort QoS
• No QoS bounds or possible very weak QoS bounds
• Advantages: resource capacities can be statistically multiplexed,
hence more processing requests can be granted
• Disadvantages: QoS may be temporally violated
CS 414 - Spring 2011
Quality-of-Service Routing
• Audio/Video Multimedia Applications
• Real-time requirement
• Throughput requirement
• Sustainable performance
• Routing: A Key Network Function to Support QoS
• Diverse QoS constraints (NP-complete problems)
• Best-effort traffic and QoS traffic
• Dynamic network state
QoS Routing – Single Metric Bandwidth
50Mbps
S
60 Mbps
30Mbps
40 Mbps
D
50 Mbps
100 Mbps
50 Mbps
120 Mbps
60 Mbps
Minimum Metric
b(S,D) = min(b1, b2, b3, …, bn)
QoS Routing – Single Metric Delay
30 ms
S
60 ms
40 ms
50 ms
D
50 ms
15 ms
100 ms
120 ms
60 ms
Additive Metric
d (S,D) = d1 + d2 + …. dn
QoS Routing with Single Mixed Metric
(50 Mbps, 30 ms, 0.02)
(30 Mbps, 35 ms, 0.5)
S
(40 Mbps, 40 ms, 0.4)
D
(60 Mbps, 25 ms, 01)
(50 Mbps, 30 ms, 0.2)
(100 Mbps, 20 ms, 0.01)
(50 Mbps, 35 ms, 0.1)
(120 Mbp, 15 ms, 0.01)
(30 Mbps, 40 ms, 0.2)
F(p) = B(P)/ (D(p) x L(p), where B is bandwidth, D is delay, L is loss probability for path p;
path with large value is
Multiple Metrics
•
•
•
•
•
Problem: Find path subject to multiple constraints
This is NP-complete problem
Simple problem with two constraints is called
“shortest weight-constrained path”
Definition:
• d(i,j) be a metric for link (i,j). For any path p = (i,j,….l,m), we say
• metric d is additive if d(p) = d(i,j) + d(j,k) +…+ d(l,m).
• Metric d is multiplicative if d(p) = d(i,j) x d(j,k) x … x d(l,m)
• Metric d is concave if d(p) = min[d(i,j), d(j,k), …, d(l,m)
Path Computation Algorithms – Source
Routing – Bandwidth-Delay Routing
• Consider directed graph G=(N, A) with N number of nodes (vertices) and A arcs
(edges).
• (i,j) is arc (edge)
• bij be available bandwidth
• dij be propagation delay
• p = (i,j,k,…, l,m)
• Bottleneck bandwidth of path is width (p) = min(bij, bjk,…., blm)
• Length of path is length (p) = dij + djk + … + dlm
• Given any two nodes i and m of the graph and two constraints W and D, the QoS
routing problem is then to find a path p* between i and m so that
• width (p*) ≥ 𝐵 and length(p*) ≤ 𝐷.
• Bandwidth-delay constrained paths
Routing Algorithm
(50 Mbps, 30 ms)
(60 Mbps, 35 ms)
S
(40 Mbps, 40 ms)
D
(60 Mbps, 25 ms)
(50 Mbps, 30 ms)
(100 Mbps, 20 ms)
(50 Mbps, 35 ms)
(50 Mbps, 40 ms)
Constraints: B = 50 Mbps, D = 55ms
Step1: find all paths that satisfy B
Step 2: find the final path that satisfies D
(120 Mbp, 15 ms)
Hop-by-Hop Routing
(50 Mbps, 30 ms)
(60 Mbps, 35 ms)
S
(40 Mbps, 40 ms)
D
(60 Mbps, 25 ms)
(50 Mbps, 30 ms)
(100 Mbps, 20 ms)
(50 Mbps, 35 ms)
(120 Mbp, 15 ms)
(50 Mbps, 40 ms)
With multiple metrics the best path with all parameters at their optimal values
may not exist at all!!!!
Hop-by-Hop Algorithm (1)
(50 Mbps, 30 ms)
(60 Mbps, 35 ms)
S
(40 Mbps, 40 ms)
D
(60 Mbps, 25 ms)
(50 Mbps, 30 ms)
(100 Mbps, 20 ms)
(50 Mbps, 35 ms)
(120 Mbp, 15 ms)
(50 Mbps, 40 ms)
Shortest-widest algorithm with distance vector approach
Step 1: find all widest path from node 1 to each node ‘i’. If there are more than one widest path found,
Step 2 chooses one with minimum length
Step 3 updates the width and length for the shortest-widest path from node 1 to node i (using distance vector approach)
Hop-by-Hop Algorithm (2)
(50 Mbps, 30 ms)
(60 Mbps, 35 ms)
S
(40 Mbps, 40 ms)
D
(60 Mbps, 25 ms)
(50 Mbps, 30 ms)
(100 Mbps, 20 ms)
(50 Mbps, 35 ms)
(120 Mbp, 15 ms)
(50 Mbps, 40 ms)
Shortest-widest algorithm based on link state
Step 1: find the nodes with maximum width among the tentatively labeled nodes if there are more than one node
found
Step 2 chooses one with minimum length and permanently labels
Step 3 updates the tentatively labeled nodes around the new permanently labeled node
Conclusion
• QoS Routing is integral part of resource management
• QoS routing might be integrated with path reservation
• Status
• QoS has been explored in routers, but not much used
• QoS has been used in ATM networks (backbone)
• QoS service class concept is now being explored by broadband providers for
multimedia services
• QoS in wireless challenging and statistical over unlicensed spectrum