Transcript Efficient Resource Management for Hard Real

Endpoint Admission Control :
Network Based Approach
Byung Kyu Choi
Riccardo Bettati
Apr. 17th, 2001
Dept. of Computer Science
Texas A&M University
{choib, bettati}@cs.tamu.edu
1
Introduction (1/2) : Integrated/Differentiated
Services Architectures
• Best-Effort Services
– No guarantee on timeliness or actual delivery
– No admission control
• Integrated Services
– Each flow is treated differently based on its requirement
– Available services :Guaranteed service, Controlled-load service
– Scalability ?
• Differentiated Services
– Edge routers : classify, police, shape, and schedule input packets
– Core routers : schedule packets based on aggregate behavior
– Available services : Premium service, Assured service
– Scalability ?
• Flow aggregation ---> Data plane !
• Bandwidth Broker ---> Control plane ?
2
Introduction (2/2) : Scalability in Real-Time
Communication Services
For traditional computer network
Best-Effort
For guaranteed real-time services
Integrated Services
For scalability
Data Plane
Packet forwarding
Flow Aggregation
Differentiated
Services
Control Plane
Admission control
Bandwidth Broker
3
Motivation (1/3) : Signaling Procedure and
Signaling Overhead
Service Network
Request Response
Service
Request
N1
N1
N2
N3
Network
Response
N2
B.B.
N5
N4
N5
N3
RSVP style
N4
Bandwidth Broker Approach
On-demand Premium Service : RFC 2638
4
Motivation (2/3) : Observations on signaling
• A core router can maintain hundreds of thousands of
flows !
– If a large number of real-time flows come on-demand, because the
user can be anywhere at anytime on the Internet ...
• Signaling explosion ?
– A huge amount of signaling activity is expected for establishment
and tear-down
• If the admission decision can be made at the entrance of
the network:
– The number of signaling messages is greatly reduced.
– The load of admission control is shared across ingress routers.
– As a result, the latency in setting up a flow is greatly reduced too.
• If resource can be reserved in a hard fashion:
– Refresh can be eliminated.
5
Motivation (3/3) : Endpoint Admission
Control and Hard Reservations
RSVP style
Bandwidth Broker
Approach
Hard Resource Reservation
Endpoint Admission
Control
6
This paper presents :
Design and evaluate an endpoint admission control for
real-time services in a single domain which supports :
Signaling
Low signaling overhead
Low admission decision time
Efficiency
High admission probability
High resource utilization
Fast flow set-up
7
Previous work (1/2) : Work on signaling overhead
• Host-based endpoint admission control
– Measurement-based admission control (packet probing)
– No signaling messages exchanged
– Nothing needs to be changed on router
• Hard to guarantee fast flow set-up : long probing time
• Hard to guarantee end-to-end delay & bandwidth for lifetime :
vulnerable allocation
• Light weight signaling protocols : RSVP, YESSIR, BGRP,
Boomerang, .. All IntServ rooted
– Soft reservation with refresh messages
– Hard to guarantee end-to-end delay,
– Hard to guarantee bandwidth
• Not appropriate for real-time applications
8
Previous work (2/2) : Scalable admission
control
• Our approach: Off-Line bandwidth assignment to classes and delay
verification during system (re-)configuration.
• Assign portion of link bandwidths to each class.
• Then, perform delay test for connections of each class in a flowunaware fashion.
• If delay test passes (less than the requirement), the bandwidth
allocation is a valid one.
• On-line end-to-end delay calculation: Eliminated by checking
available bandwidth only
• Publication1 : “Utilization-based Admission Control for Real-Time
Communication,” Accepted by Journal of Real-Time System, 2000.
• Publication2 : “Scalable QoS Guaranteed Communication Services for
Real-Time Applications, ICDCS 2000, pp. 180-187.
9
Sink-tree paradigm (1/5)
• Benefit : Endpoint admission control and hard reservation
• How ?
– Distribute admission control to ingress nodes
– Allocate bandwidth to links on trees one for each egress router
• Question : How to find such a set of sink trees ?
– Three constraints in bandwidth allocation
• Link Capacity
• Depth-aware Bandwidth Allocation
• Bounded Worst-case End-to-End Delay
• Finding such a set of sink-trees is NP-hard.
• Heuristic algorithm for finding a set of sink-trees for a
given network
– Use MST (Minimum Spanning Tree)
• Strictly partitioned resource ? ----> Resource sharing
10
Sink-tree paradigm (2/5) : sink-tree example
B : Bandwidth Allocated
N7
Root (Sink)
B=30
Core router : N5, N6
N5
Egress router : N7
B=70
N6
B=10
B=20
B=30
B=40
N1
N2
N3
N4
Ingress router : N1, N2, N3, N4
11
Sink-tree paradigm (3/5) : Operation example
Uniform Resource Allocation
Admission Blocking in Uniform
N1
B=10
N1
F=10
B=10
N4
N2
B=10
B=10
N3
Total bandwidth
allocated : 40
F=10
N4
N2
B=10
B=10
N3
Total real-time flows
admitted to N1 : 20
12
Sink-tree paradigm (4/5) : Operation example
Sink-tree Resource Allocation
Improved Admission in Sink-tree
N1
B=10
N1
F=10
B=20
N4
N2
F=20
N4
N2
B=10
F=10
N3
N3
Total bandwidth
allocated : 40
Total real-time flows
admitted to N1 : 30
13
Sink tree paradigm (5/5) : Resource Sharing
• Study on Resource Sharing in the sink tree
–
–
–
–
Fixed partitioning of resources will be inefficient
On-line re-computation of resource allocation will be expensive
Light weight method is needed for adaptive resource usage
We investigate performances in the four steps of resource sharing :
• No sharing, Path sharing, Tree sharing, Link sharing
Service
Request
N1
Service
Request
B=10
N2
Service
Request
B=20
N3
B=30
N4
14
Performance evaluation (1/5)
• For a single DS Domain
– Admission probability and resource utilization
– The worst-case end-to-end delays
• Comparison against “uniform resource allocation”
– Bandwidth allocation : uniform to each link
– Path selection : Shortest-Path-First Routing
– We call this “Flat-Fixed” system.
• Sink tree-based system
– Bandwidth allocation : sink-tree construction
– Path selection : pre-defined along sink-tree
15
Perf. evaluation (2/5) : Simulation spec.
• Call generation
– Call arrival : Poisson process with rate 
– Flow lifetime : exponentially distributed with 180 sec., in average
– Source and destination routers : chosen randomly
• Network : MCI backbone topology
– Homogeneous links : 155 Mbps
• Real-time application : Voice-over-IP
• Traffic characteristics
– Fixed packet length : 640 bits (RTP, UDP, IP headers + 2 voice frame.)
– Flow rate : 32 Kbps
– End-to-end delay requirement : 100 ms
16
Perf. Evaluation (3/5) :
Network topology for simulation
17
Perf. evaluation (4/5) : Admission probability
18
Perf. Evaluation (5/5) : Configuration effect
on admission probability
19
Conclusions
High admission probability
Endpoint
admission
control
based on
sink tree
Endpoint-limited
signaling
Ingress node
admission decision
Pre-determined
path & resource
allocation
Low signaling overhead
Fast flow set-up
Low routing overhead
20