Transcript PPT

A Mechanism for
Equitable Bandwidth Allocation
under QoS and Budget
Constraints
Sreenivas Gollapudi
Oracle Corporation /
SUNY at Buffalo
D. Sivakumar
IBM Almaden Research Center
Presented by:
Abdul Hasib
CPSC 601.43 Topics in Multimedia Networking
The TwelfthCPSC
IEEE International
Workshop
on Quality of Networking
Service IWQoS, 2004.
601.43 Topics
in Multimedia
Presentation outline
• Quality of Service (QoS)
– Integrated Service
– Differentiated Service
•
•
•
•
•
•
Objective and previous work
Desired Properties
Basic principle
Bandwidth allocation algorithm
Comparison parameter
Experimental Results
CPSC 601.43 Topics in Multimedia Networking
Quality of Service (QoS)
• Internet provides “Best effort” service
–
–
–
–
–
Simple
No admission control
No guarantee; no performance assurance
Single level of service
Not suitable for booming real time applications.
The capability to provide resource assurance and
service differentiation in a network is often
referred to as quality of service (QoS).
CPSC 601.43 Topics in Multimedia Networking
Technologies
• QoS parameters
– Throughput; Delay; Jitter; Data corruption etc.
• Developed technologies categorized by two key
QoS issues:
– Resource allocation
• Integrated Service
• Differentiated Service
– Performance optimization
• Multiprotocol label switching (MPLS)
• Traffic engineering
CPSC 601.43 Topics in Multimedia Networking
Integrated Services (Int-serv)
• Per-flow resource reservation.
• Steps:
– Application requests its required resource.
– The network uses a routing protocol to find a path
based on the requested resources.
– Reservation protocol (RSVP) is used to install the
reservation state along that path.
– At each hop, admission control checks whether
sufficient resources are available to accept the new
reservation.
– After reservation, the application can start to send
traffic over the path for which it has exclusive use of
the resources.
CPSC 601.43 Topics in Multimedia Networking
Int-serv (cont.)
• Two services level
– guaranteed (delay) service, controlled load service.
CPSC 601.43 Topics in Multimedia Networking
Int-serv (cont.)
• Disadvantage:
– Applicable to long lasting traffic (video conferencing);
– Scalability problem
• may not be able to cope with a very large number
of flows at high speeds
• requires the support of accounting and settlement
between different service providers
• Potential Application Area:
– IP telephony, video conferencing over corporate
intranets
CPSC 601.43 Topics in Multimedia Networking
Differentiated Service (Diff-serv)
Uses a combination of edge policing, provisioning, and
traffic prioritization to achieve service differentiation.
• Resource allocation to aggregated traffic rather than
individual flows.
• Traffic policing on the edge and class-based forwarding in
the core.
Ingress
Edge
Router
Interior
Router
Egress
Edge
Router
CPSC 601.43 Topics in Multimedia Networking
Router Functionality
• Network edge routers:
• Packet classification: service level agreement
(SLA) and traffic type.
• Responsible for mapping packets to their
appropriate forwarding classes, per-hop behavior
(PHB). Each PHB is represented by a 6 bit DSCP
• Set DSCP in packet header DS field, modified
TOS field.
• Nonconforming traffic may be dropped, delayed,
or marked with a different forwarding class.
• Interior routers: traffic classification and forwarding
 use DSCP as index into forwarding table
CPSC 601.43 Topics in Multimedia Networking
Router Functionality (cont.)
• Network
edge routers:
• traffic conditioning (policing, marking, dropping), SLA
negotiation.
PHB group
Meter
high
importance
Classifier
Marker
Shaper/
Dropper
real-time
PHB class
data
PHB class
PHB 11
PHB 21
low
importance
PHB 22
low delay
Traffic conditioning
CPSC 601.43 Topics in Multimedia Networking
high delay
Diff-serv
• Define forwarding behavior not end-to-end
services.
• Guarantee by provisioning rather than reservation:
– For each forwarding class, the amount of traffic that
users can inject into the network is limited at the edge
of the network.
• service providers can adjust the level of resource
provisioning;
• control the degree of resource assurance to the
users.
• Qualitative QoS scheme.
CPSC 601.43 Topics in Multimedia Networking
Presentation outline
• Quality of Service (QoS)
– Integrated Service
– Differentiated Service
•
•
•
•
•
•
Objective and previous work
Desired Properties
Basic principle
Bandwidth allocation algorithm
Comparison parameter
Experimental Results
CPSC 601.43 Topics in Multimedia Networking
Objective and previous work
• Fair and efficient bandwidth management.
• Allocation based on differential pricing scheme.
Previous work
• Allocation is based on a single preferred
bandwidth (A) request of user.
• Uniform allocation rule:
– Initially allocate an equal share (X) to every user,
– if A<X, user will receive exactly A.
– Excess bandwidth will be equally re-apportioned among
all remaining users.
CPSC 601.43 Topics in Multimedia Networking
Desired properties
• Feasibility:
• Efficiency:
a
i
i
 B ; ai=allocated bandwidth to user i
– If the sum of ideal allocations exceeds the supply, then
no user should receive more than his ideal allocation;
– if supply exceeds the sum of ideal allocations, then no
user should receive less than his ideal allocation.
• Strategy proof ness: Mis-reporting bandwidth
requirement should not give incentive to user.
• Envy-freeness: When the allocations have been
determined, no user would prefer other users
allocation to his.
CPSC 601.43 Topics in Multimedia Networking
Basic principle
• Network coordinator
– is used to deploy the bandwidth allocation
mechanism in a general network;
– handles the functions of admission control.
• Bandwidth allocation is based on:
– Service provider (vendor) parameter
• Cost function, c(b)= b ;  = constant
• Capacity and utilization information of all links
along path, P.
CPSC 601.43 Topics in Multimedia Networking
Basic principle (cont.)
• Bandwidth allocation is based on:
– User (agent) parameter:
• Utility function, u i (b) : [0,B]
i0 : minimum acceptable bandwidth;
i* : optimal bandwidth;
i1: maximum acceptable bandwidth
• Pricing level, li
- User can choose to pay more for a QoS requirement to
increase the likelihood of receiving the better service.
- ci (l, b) = li b, where, ci= cost function for agent I
 i li B  C
C= revenue goal
CPSC 601.43 Topics in Multimedia Networking
Utility function
welfare, wi (b)  ui (b)  ci (li , b)
CPSC 601.43 Topics in Multimedia Networking
Bandwidth allocation algorithm (M)
CPSC 601.43 Topics in Multimedia Networking
Bandwidth allocation algorithm (M) (cont.)
CPSC 601.43 Topics in Multimedia Networking
Bandwidth allocation algorithm (M) (cont.)
CPSC 601.43 Topics in Multimedia Networking
Comparison parameter
(1) Quality of Service: For an agent with optimal allocation
 *, an allocation b of bandwidth is defined to achieve a
QoS value of Q(  * , b) = b/ *
(2) Probability of allocation: Fraction of agents who receive
at least , their minimum acceptable allocation ( 0).
0

(3) Fairness rank, F(i) is proportional to i
li
CPSC 601.43 Topics in Multimedia Networking
Fairness rank vs. QoS
CPSC 601.43 Topics in Multimedia Networking
Fairness rank vs. Probability of allocation
CPSC 601.43 Topics in Multimedia Networking
Thank you
CPSC 601.43 Topics in Multimedia Networking