Transcript Evaluation of Signal Processing Resource Management Algorithms

Implementing Integrated Services
in Network Simulator
Author: Yaohui Li
Supervisor: Raimo Kantola
Instructor: Lic.Sc. Mika Ilvesmäki
1
Table of Contents
• Overview of Integrated Services
• Overview of NS2(Networking Simulator
version 2)
• Tasks definition
• Tools
• Modeling designing and implementation
• Testing and results
• Conclusion
Overview of IntServ (1)
• Internet only offers a best effort service,
which can meet the traditional non-real-time
Internet traffics.
• For real-time traffic, it needs a new scheme
to make reservation for the traffic.
• IntServ(Integrated Services) can provide
resource allocation to meet the requirement
of real-time application.
• IntServ is per-flow service.
Overview of IntServ (2)
• IntServ Implementation Framework
Routing
Protocols
Routing
Table
Reservation
Protocol
Admission
Control
Management
Agent
Traffic Control
Database
QoS Queue
Input Traffic
Classifier
Packet
Scheduler
Best-effort Queue
Forwarding
Table
•packet classifier: maps each incoming packet into corresponding class.
•packet scheduler: implements resource allocation.
•Admission control: determines a new reservation request is allowed or
denied.
Overview of IntServ (3)
• IntServ Service Models
– Best efforts (BE)
no any guarante
– Controlled Service(CL) (RFC2211)
provides service intended to predictive or delay-adaptive
real-time class, or better than BE.
– Guaranteed Service(GS) (RFC2212)
provides a deterministic bound of end-to-end delay and
bandwidth guarantee
Overview of IntServ (4)
•
Before a network entity
can be enable to invoke or
select a specific service, it
needs a set of parameter:
• Traffic Specification
(TSpec)
– describes the traffic characteristics
for which the service is being
requested. for example: it can be a
token bucket filter.
– GS and CL needs it
Overview of IntServ (5)
• RSpec (request specification)
– describes the quality of service that application
wishes to request from the network.
– GS needs RSpec, but as for CL: no RSpec is
requested.
Overview of IntServ (6)
• The Resource Reservation Model
– RSVP is one of the protocols to implement the
purpose.
– It is a signalling protocol
– be responsible for install and maintain
reservation state in each router by transferring
the parameters.
– Receiver oriented.
– Soft state.
Overview of IntServ (7)
• RSVP Messages
Path
Path
Resv
D1
D1
Resv
R2
R2
Resv
Path
D2
D2
Resv
S1
S1
R1
R1
Path
Path
Resv
R3
Path
R3
Resv
D3
D3
Other message types include reservation confirmation messages,
error report messages and reservation and path teardown messages.
Overview of IntServ (8)
• RSVP object Classes
• A Path message contains the following important
objects:
RSVP Header, INTEGRITY, SESSION,
RSVP_HOP, TIME_VALUES, POLICY_DATA,
SENDER_TEMPLATE, SENDER_TSPEC and
ADSPEC.
• A Resv message contains the following objects:
RSVP Header, INTEGRITY, SESSION,
RSVP_HOP, TIME_VALUES, RESV_CONFIRM,
SCOPE, POLICY_DAT, STYLE, FLOWSPEC and
FILTER_SPEC.
Overview of NS-2 (1)
Network simulator version 2
• Simulates various networking
models, used for researches
for example: simulation in TCP,
routing, and multicast
protocols, mobile networks,
satellite networks, and so forth.
Hierarchy of NS2
•OTcl: Object-oriented support
•tclcl: C++ and otcl linkage
•Discrete event scheduler
•Data network (the Internet) components
Overview of NS2 (2)
• Ns2 is writtten in two programming languages C++
and Tcl
• C++: Detailed protocol simulations require systems
programming language
– byte manipulation, packet processing, algorithm implementation
– C++ is fast to run so that it is used in the core of ns2.
– Turn around time (run simulation, find bug, fix bug, recompile, re-run) is
slower
• Tcl: Simulation of slightly varying parameters or
configurations
– OTcl is a scripting language as a front-end or interface in ns2.
– quickly exploring a number of scenarios
– iteration time (change the model and re-run) is more important
• In sum, C++ is for data, aiming at per packet action;
tcl is for control, aiming at periodic or triggered action.
Overview of NS2 (3)
• NS2 package stucture
Overview of NS2 (4)
• The binding of member
variables from C++ to
OTcl.
For example: In C++
• The correspondence of
member functions
between C++ and OTcl:
• In C++ and Otcl
TcpAgent::TcpAgent(){
Bind(“window_”, $wind_)
}
In Otcl :
Agent/TCP set window_ 100
•OTcl to call C ++ : command(), tcl.result()
•C++ to call otcl: tcl.eval()
Thesis Task Definition
In current Ns2
• there are very few modules for IntServ
only control load service was implemented, by using simple
three-way handshake algorithm for signalling and a simple
priority queue with two kinds of services (BE and CL)
• The task is Adding Guaranteed Service
module into NS2 by making use of RSVP as
a signalling protocol
Tools used in the work
• Design language: UML
• Programming language: C++ and OTcl
• NS2 package NS-2.1b9a on the Solaris
platform
• CVS
Modeling designing and implementation(1)
• Preconditions and assumptions in GS
implementation
– To use RSVP as the signalling protocol to set up
reservations.
– We have to assume that every service element (a router,
or a subnet, etc) in the path supports GS or mimics GS.
However, this requirement does not mean that GS must
be deployed throughout the Internet.
– Routing protocols or other network management
functions are outside the scope of this implementation.
– The network elements must ensure that the service to be
implemented approximates the “Fluid Model Service”.
Modeling designing and implementation(2)
• The new architecture of IntServ implementation in ns-2
Estimator
1
Admission
Control
Simple
Scheduler
for CL
packets
Classifier1
Signaling
Support
(Simple
RSVP)
Estimator
2
CL
Measurement
for class 1
GS
Measurement
for class 2
Classifier2
Scheduler
WFQ for GS
Best Effort traffic
Delay
Link
Modeling designing and implementation(3)
The relationship of classes to be implemented between C++ and OTcl
C++
OTcl
Agent
GSSAAgent
Agent/GSSA
Connector
GSSAChecker
GSSAChecker
GSSAmessage
SENDER_ADSPEC
FILTER_SPEC
FLOWSPEC
ERROR_SPEC
GSSAObject
GSSA_HOP
SENDER_TEMPLATE
SENDER_TSPEC
SESSION
STYLE
TIME_VALUES
RESV_CONFIRM
SALink
GSSALink
GSSALink
Queue
WFQ
Queue/WFQ
WFQClass
WFQClass
TclClass
PacketHeaderClass
Modeling designing and implementation(4)
•
the class diagram of signaling part implementation
GSSAObject
SENDER_
ADSPEC
ERROR_
SPEC
GSSAmessage
FILTER_
SPEC
TCSB
FLOWSPEC
RESV_
CONFIRM
GSSA_HOP
RSB
SENDER_
TEMPLATE
SENDER_
TSPEC
STYLE
SESSION
•
RSB(Reservation
State Block)
•
TCSB (Traffic
Control State Block)
•
PSB (Path State
Block)
TIME_
VALUES
PSB
Agent
session
GSSAAgent
RNG
Modeling designing and implementation(5)
• The extended class diagram in NS2
Estimator_
Timer
Connector
SALink
GSSAChecker
GSSALink
GSSAAgent
MeasureMod
ADC
ACTO_ADC
Queue
WFQ
Hashtable
WFQClass
Param_ADC
Estimator
HB_ADC
MS_ADC
Modeling designing and implementation(6)
• Signalling module (GSSA GS signalling)
Senders
(source)
Packet
Classifier
Control plane
Data plane
PATH
GSSA
Deamon
Packet
Scheduler
Admission
Control
GSSA Message
Generator
RESV
PATH
RESV
Receivers
(sink)
Modeling designing and implementation(7)
The signalling process and the role of each participator
Sender: the initiation
state of sender
• Sender: the waiting
state diagramof sender
Wait_Ack
Init
Resv_msg
Reset t;
Sender_Idle
ResvConf
Path_msg
A connection set
up and send
data
Set t;
Wait_Ack
Path_Tear
Sender ends process
or timeout
Sender_Idle
Modeling designing and implementation(8)
For the intermediate router (complex)
• path message processing
• Resv message processing
Router_Idle
Router_Idle
Resv
Path_message
No
Exists session
(Dest, fid)?
Resv_Err
Yes
LOOP
Router_Idle
No
Exists session
(dest, fid)?
No
Exists PSB
(session, sender)
Create new
session
(dest, fid)
Yes
Resv_Err
Yes
No
No
Yes
exists PSB
(session, sender)?
Create a
new PSB
state and
forward it
Update the
old PSB
state and
forward it
Exists RSB
(session, Flowspec)
Yes
Update the
old RSB
state and
forward it
Create a
new RSB
state and
forward it
No
Exists Resv_conf
Yes
Update
traffic_control
Copy
Resv_Conf
into RSB
Forward to
next router
No
Flowspec is null?
Yes
Router_Idle
Forward to
next router
Router_Idle
Modeling designing and implementation(9)
• Path_Err message process
• Resv_Err message process
Router_Idle
Router_Idle
Resv_Err
Path_Err
Exists
session(Dest, fid)
Exists session
(Dest, fid)
No
Yes
Yes
Router_Idle
LOOP
No
Make
error_upcall
Yes
Filter_spec is
NULL?
Marked RSB
Forward
Path_Err
Make
error_upcall
Router_Idle
Forward
Resv_Err to next
router marked
RSB
Router_Idle
No
Router_Idle
Modeling designing and implementation(10)
•
Path_Tear message process
• Resv_Tear message process
Router_Idle
Resv_Tear
Exists session
(Dest, fid)
Router_Idle
Yes
Path_Tear
LOOP
No
Exists session
(Dest, fid)
No
Yes
Exists PSB
(session, Dest)
Delete RSB
Router_Idle
Yes
No
Filter_spec
is null
Update
traffic_control
Yes
Yes
Rsb_list
is null
No
Router_Idle
Router_Idle
Drop RSB for
corresponding
PSB
Remove PSB
No
Forward to
next router
Router_Idle
Forward
Resv_Tear
Rsb_list
is null
Yes
Drop all
RSBs
Router_Idle
No
Modeling designing and implementation(11)
• Resv_Conf message process
No
• the state diagram of receiver
Router_Idle
Receiver_Idle
Resv_Conf_msg
Path_msg
IP address of router
exists in Resv_Conf msg
Receiver computing an
optimum bandwidth using
info from Path message
Yes
Exists session
(Dest, fid)
Yes
No
Resv
Make
confirmation_
upcall
Receiver ends
process or resv
timeout
Forward Resv_Conf to
next router marked
RSB
Resv_Tear
no
Wait_Confirm
and receive data
Router_Idle
yes
Receiver_Idle
Modeling designing and implementation(12)
data structures
• session
• PSB (Path State Block)
Modeling designing and implementation(13)
data structures
• RSB
• TCSB
Modeling designing and implementation(14)
Guaranteed Services
Flows
• Scheduling module
WFQ
Σ
New Flows
Best Efforts
Flows
FIFO
Admission Control
Modeling designing and implementation(15)
• WFQ
– one of the popular scheduling algorithms
– IETF adopted it for IntServ networks
– an approximation of GPS (generalized
processor sharing)
Modeling designing and implementation(16)
• Admission control
making use of measurement-based algorithm
It includes four control algorithms:
– Measured Sum (MS). The MS algorithm admits a new flow if the sum of
the token rate of the new flow and the estimated rate of existing flows is
less than a utilization target times the link bandwidth .
– Hoeffding Bounds (HB). The HB algorithm admits a new flow if the sum
of the peak rate of the new flow and the measured equivalent bandwidth is
less than the link utilization.
– Tangent at Origin (TO). The TO uses a tangent to the equivalent
bandwidth curve at the origin to satisfy the specific formula if a new flow
is admitted
– Tangent at Peak (TP). The TP is based on the tangent at the peak of an
equivalent bandwidth curve computed form the Chernoff Bounds
Testing and Results (1)
• The topology of simulation test
there are eleven CBR sources nodes
n(1), n(2), n(3)…n(11) over UDP
connection and their corresponding
sink agents sink1, sink2, sink3
…sink(11).
The bandwidth of n12 and n13 is
2.8Mbps
The bandwidth of each source node
n1—n11 to n12 is 1Mbps
We will guarantee that the traffic of
source n(11) can be received at the
sink whenever how many sources
are added (best effort or controlled
services traffics).
Testing and Results (2)
• Before add GS module into ns2
Testing and Results (3)
• test result after adding GS module into ns2
Testing and Results (4)
• The simulation test after adding GS and CL into traffic nodes (the
same prerequisite)
Conclusion (1)
• The GS implementation makes use of RSVP as the
signaling protocol, and takes advantage of the part
of integrated services in ns2 as the skeleton which
includes admission control algorithms, estimation
and measurement methods.
• On the basis of the result of the test cases, some
basic function of GS can almost be implemented
in the ns2.
Conclusion (2)
However, there are still a lot of work to do for
improving the implementation to realize the
GS strictly according to [RFC2212]
[RFC2205] and [RFC2210]. For example,
in the RSVP, several objects which
influence less to the implementation in ns2
were ignored, such as INTEGRITY, SCOPE
AND POLICY_DATA.
Conclusion (3)
• Guaranteed services provide high-quality
QoS.
• IntServ/GS is not likely to be the widely
implemented QoS solution because of the
well known reason:
the complexity in routers and limited
scalability.
Questions?
Thanks for your attention!