Transcript Queueing performance and traffic control in VoIP

Queueing performance and
traffic control in VoIP
transmission
By An T. Le
Major Professor:
Dr. Ravi Sankar
Committee Members: Dr. Tapas Das
Dr. Paris Wiley
Dr. Wilfrido Moreno
Dr. Richard Thompson
15 Dec 2006
The three basic parts of
Telecommunication

Switches
Channels to Terminals
 Channels to Channels

Terminals
 Transmissions

Switches

Any particular switching machine can be categorized as providing
one of the following functions:



Signaling – to monitor the activity of the incoming lines and forward
appropriate status or control information to the control element of the
switch.
Control – to process incoming signaling information an set up
connection accordingly.
Switching
Switching
Matrix
Signaling
Control
Signaling
Switches

Circuit Switches


Circuit based Switches include Time Slot
Switches
Non-Circuit Switches

Software based Switches,
PBX - Switches

PBX – Private Branch eXchange referes
generically to any switching system
owned or leased by a business or
organization to provide both internal
witching and access to the public
network
VoIP Queueing

Why queueing?


Congestion
Queueing in Telephone network

Calls queueing


Call waiting, Call parking…
Queueing in IP Network

Packets queueing

Buffering
VoIP Network
PBX
PBX
Analog Phone
Analog Phone
PSTN
T
T
Fax
Fax
AnalogFax/Phone
IAD
BACKBONES
NETWORK
IP Network
Gateway
PSTN-IP
IP
PBX
1
2
T
3
4
5
6
7
8
9
*
8
#
IP Phone
IP
(LAN)
PC
1
2
1
2
3
4
5
6
7
8
9
*
8
#
IP
(LAN)
Gateway
NAT
IP (WAN)
Gateway
NAT
1
2
1
3
3
IP Phone
1
2
PC
2
3
4
5
6
7
8
9
*
8
#
IP Phone
3
IP switching devices work at layer 1, 2,3
T
Time-slot switch
NAT
IAD
Network Address Translation
Integrated Access Device
AnalogFax/Phone
Gateway
IP-Analog
OVERVIEW OF VOICE OVER IP NETWORK
VoIP traffic limits

Thru a Physical Link
Capacity=BW.log2(1+SNR)
 Where:




Switches- Circuit or non-circuit


BW is the bandwidth of the transmission media.
SNR is the signal over noise ratio in dB
Limited by switch capability
Processes: CODEC, Packetizing

Limited by Processor speed, traffic volume,
protocol, CODEC etc…
Packet Switch Functions

NxN switch must support at least two functions:


Routing each packet to its destination output
Resolve the situation that two or more simultaneous packets arriving,
seek access to the same output.
An input slot (to output 3)
Input 1
6
7
N
3
1
2
NxN
Generic Time-Slot
Switch
Input N
2
N
6 1
7
3
t
1
1
1
1
1
1
Output 1
2
2
2
2
2
2
Output 2
3
3
3
3
3
3
Output 3
N
N
N
N
N
N
Output N
Lost packet performance in the absence of
smoothing buffer


If probability that the input has a packet arrived is p (offered load or input fill
factor) then probability of exact K input cells bound for the same output is:
N
Pn ( K  k )   ( p / N ) k (1  p / N ) N  k
k
N
N!
Where :   N C k 
k!( N  k )!
k
and
K  0,1,...N
Average number of packets lost L for a given output per a time slot is
L  p  (1  p / N ) N  1


Lim L  p  1  e  p
N 
Thus, output fill factor F is: F  p  L  1  (1  p / N )
and
The fraction of incoming cells that is lost by the switch FL is
N
FL 

Lim F  1  e  p
N 
L
1 1
 1   (1  p / N ) N
p
p p
Without smoothing buffer, the lost is more significant – (With buffer, K is smaller)
Queueing in Packet Switch
- Input Queueing

Input queueing switch
Input 1
1
N 1
Input N
1
6 1
1
1
Output 1
N
N
Output N
NxN
Time-Slot
Switch
FIFO 1
FIFO N
Input FIFO queued
N x N Time-Slot Switch

Input smoothing queued switch
1
Input 1
N 1
2
m
1
Input N
N 1
1
1
Output 1
N
N
Output N
Nm x Nm
Time-Slot
Switch
2
m
Input smoothing FIFO queued
N x N Time-Slot Switch
Input queueing (cont.)

The probability of a output to be filled PF
is
 N  1 
PF     
k 1  k  N 
N
k
1

1



 N
N k
1

 1  1  
 N
Lim PF  1  1 / e  63%
N 
N
Output queuing


Other end of the switch, the output could be in saturation, or if
output should wait until the link is available. Unlike input queuing
only need N queues, a output queuing needs N2 queues
Mean Delay for a Packet Switch with Output Queuing

p(1  1 / N ) 

D  T 1 
2(1  p) 


Where T is time slot length

When N= 1 the delay time is equal a time slot length
Queueing in Packet Switch (cont)

We are assuming:
1- The delay caused by time-slot switch is
very small and is voided. Delay is only
cause by queueing circuit (or process).
2- All arriving packets are none classified and
have the same priority.
3- Packet length and buffer size is fixed
Queuing Theory and application in Telephony
1- Queuing Theory Basics



Queueing is handled by control processes within switching devices, which can be
modeled using state equations.
Queueing systems use a particular form of state equations known as Markov
chains which model the system in each state.
Incoming traffic to these systems is modeled via a Poisson distribution and is
subject to Erlang’s queueing theory assumptions via:






Pure-Chance Traffic – Call arrivals and departures are random and independent events.
Statistical Equilibrium – Probabilities within the system do not change.
Full Availability – All incoming traffic can be routed to any other customer within the
network.
Congestion is cleared as soon as servers are free.
Classic queueing theory involves complex calculations to determine call waiting
time, service time, server utilization and many other metrics which are used to
measure queueing performance.
Queues can be chained to form queueing networks where the departures from
one queue enter the next queue.
Queuing Theory Basics (cont.)

Queueing networks can be classified into two
categories:


Open queueing networks: Networks have an
external input and an external final destination.
Closed queueing networks: Completely contained
and the customers circulate continually never
leaving the network
Little’s Theorem

Little's theorem states the average number of customers (call in
or arriving packet) (N) can be determined from the following
equation:
N  T


Where  is the average customer arrival rate, and T is the average
service time for a customer
From Little's Theorem, for more understanding characteristics of
a queuing system that impact its performance, we should extend
more definition of N, T and  . For example



How do the calls or packets arrive in the system? Are calls or data
packet arrivals more during certain times?
What length of call or packet (time to serve for call or arriving
packet?
How many switches or processors and what is the volume of each?
A/S/n queuing system

Where A is the arrival process, S is the switching process and n is the
number of links. A and S are can be any of the following




M (Markov ): Exponential probability density
D (Deterministic): All call or packet have the same value
G (General): Any arbitrary probability distribution
Examples of queuing systems that can be defined with this convention
are:



M/M/1: This is the simplest queuing system to analyze. Here the arrival and
switching service time are negative exponentially distributed (Poisson
process). The system consists of only one links. This queuing system can be
applied to a wide variety of problems as any system with a very large number
of independent calls can be approximated as a Poisson process.
M/D/n: The arrival process is Poisson and the service time distribution is
deterministic. The system has n links.
G/G/n: This is the most general queuing system where the arrival and service
time processes are both arbitrary. The system has n links. No analytical
solution is known for this queuing system.
Poisson arrival process

Probability of seeing n arrivals in a period from 0 to t.
(  t ) n  t
Pn (t ) 
e
n!


Where:
 t is used to define the interval 0 to t
 n is the total number of arrivals in the interval 0 to t.
  is the total average arrival rate in arrivals
The channel is idle (no call or packet arrive in) if n=0
then
P0 (t )  e  t
Markov’s chain

A Markov chain is a sequence of random variables X1, X2, X3, ...
with Markov property, namely that, given the present state, the
future and past states are independent. Formally
Pr( X n 1  x | X n  xn , ..., X 1  x1 , X 0  x0 )  Pr( X n 1  x | X n  xn )
Markov’s chain (cont) - example

The probabilities of channel busy (a packet arrived), given the channel status on
the preceding time slots, can be represented by a transition matrix:
0.9 0.1
P

0.5 0.5



(P)i j is the probability that, if a given slot is of type i, it will be followed by a slot of type j.
Notice that the rows of P sum to 1: this is because P is a stochastic matrix.
The time slot 0 is known to be occupied. This is represented by a vector in which
the "busy" entry is 100%, and the "idle" entry is 0%:
x ( 0)  1 0



The status on time slot 1 can be predicted by:
0.9 0.1
x (1)  x ( 0) P  1 0 
  0.9 0.1
0
.
5
0
.
5


Thus, there is a 90% chance that slot 1 will also be busy.
The time slot 2 can be predicted in the same way:
2
0
.
9
0
.
1


x ( 2)  x (1) P  x ( 0) P 2  1 0 
  0.86 0.14
0
.
5
0
.
5


General rules for slot n are:
x( n)  x( n 1) P  x(0) P n
Markov’s chain (cont) – birth-death process

birth-death process: The states represent the current size of a
population and where the transitions are limited to births and
deaths. When a birth occurs, the process goes from state n to
n+1. When a death occurs, the process goes from state n to state
n-1. The process is specified by birth rates{i }i  0.. and death
rates {i }i  0.. .
Modeling of queueing system of VoIP network

M/M/1 Queue

consider a system consisting of a single channel and an associated queue

Assume that the arrival process is Poisson, with rate. The service times of
process are independent identically distributed random variables, with
exponential distribution with mean.
Assume that Fist Come First Serve (FCFS) scheduling is done at the
channel. If N(t) denotes the number of sources in the system, the {N(t), t>0} is
a birth death process with k   (k  0) and  k   (k  0).
Using the expressions derived for a birth death process we have the following


and
Where
is called the traffic intensity of the system and has units as Erlangs

M/M/1 Queue (cont)
The expected number of packets in the system is given by:
Use Little’s Formula to calculate the response time E[R] of the system. Little’s formula gives:
hence
Using the expression for we get
Other measures could also be found easily. If W denotes the random variable denotes the waiting
time in the queue i.e W=R-S , then,
Hence,
Also by applying Little’s Formula to the queue, we can get the expected number of packets in the
queue as E[Q] given by :
In a similar fashion many other queues such as the M/M/m, the M/M/1/n, etc can be
Open end Closed queueing
networks

Open queueing networks have an external input and an external final destination.

Closed queueing networks are completely contained and the customers circulate continually
never leaving the network
Other queueing modeling systems


Beside of Markov-chain modeling, others proposed Wavelet
Multi-fractal Modeling for Network Traffic and Queueing, which
exhibits multi-fractal character. The discovery of the multi-fractal
nature of traffic has made new models and analysis tools for
traffic essential, since self-similar or Long-Range Dependence
(LRD) models are far too optimistic in their predictions of
performance. Short-range Dependence (SRD) is must be
considered especially in flow control (FC) and CRC design.
Wavelet-based model can capture important fractal properties like
multi-scale variability and bursting that deleteriously affect
performance. This model has a disadvantage on computing the
wavelet transform.
Autoregressive Input Process, Weilbull Distributed Inter-arrival
Time Process, Pareto Distributed Inter-arrival Time Process,
Fractional Brownian Motion Process are also among of proposed
queueing models. These modes underestimate the loss
probability.
Queueing and delay
VoIP stream is considered as real-time
stream
 End to End delay expected not greater
than 400ms
 Queueing buffer size is limited.

VoIP traffic control

Traffic control at generic IP devices and at VoIP servers.

Most IP traffic control takes place
at lower layer (Network, data link)
VoIP protocol stack
Traffic control at generic IP devices

Traffic control:


Different traffice rout for different priority
Reduce Traffice Jam (congestion)





“Take another route”
Get a waiting ticket
Cut-off low priority services
Remove the “dead” vehicle
In computer networking, DiffServ or Differentiated Services is an
architecture that specifies a method of providing quality of service (QoS)
guarantees to network traffic on modern IP networks. DiffServ can, for
example, be used to provide low-latency, guaranteed service to critical
network traffic such as voice or video while providing simple best-effort
traffic guarantees to non-critical services such as Web traffic or file
transfers. So among of IP packets, voice packets could be served first.
The big disadvantage of DiffServ is packet drop. Since DiffServ is simply
a mechanism for deciding which packets to delay or drop at the expense
of others in a situation where there is not enough network capacity,
consider that when DiffServ is working by dropping packets selectively,
traffic on the link in question must already be very close to saturation.
Traffic control at IP PBX servers or VoIP gateways



Most processes at layer 7,6,and 5 are done by terminal (IP phone).
Depending on how a VoIP server is featured; traffic may be processed by VoIP server as
following:

Process signaling, check the service required

Look up destination IP call, then replace new header with new destination IP.

Forward or translate signaling packet

Forward or re-encoding voice stream

Re-packetizing
Gateway
Gateway
Media stream (RTP)

Route the packet to new destination
Gatekeeper routed call signaling

The idea that keeps the voice stream from end
to end as fast as possible is the basis of using
Address translation
Admission control
a gatekeeper.
Bandwidth control
A Gatekeeper is used mostly in H.323 protocol. (RAS)
Call signaling
Call control
H323 includes H.255- Call Signal Carrier and
provide Registration, Administration, and Status
Gatekeeper
Channel (RAS) ).
Traffic control at IP PBX servers or VoIP gateways (cont)



Due to complexity inflexibility and hard to keep RAS channel in secure, H.323 has
become the not popular VoIP protocol
In SIP (Session Initiation Protocol), voice
stream also traverse from host to host and
SIP signaling handles by a proxy server
Signaling
Signaling
Proxy
and very similar to HTTP.
Server
The SIP signaling is simpler than H.323.
Media stream (RTP)
All control signaling is handling by Proxy
servers. Address translation in SIP is more
INVITE F1
INVITE F2
complicate than in H.323
100 Trying F3
180 Trying F4
180 Trying F5
200 OK F6
200 OK F7
ACK
RTP Media session
BYE
200 OK
SIP session setup with single Proxy server
Traffic control at IP PBX servers or VoIP gateways (cont)

SIP session setup with multi-Proxy servers
Signaling
Signaling
Proxy
Server A
Proxy
Server B
Signaling
Media stream (RTP)
SIP phone

SIP phone
After the “hand sake” process is done, the media stream can be lost somewhere
during NAT mistranslation but the proxy may not recognize it. The most popular
solution is using a signal similar with “ping” to monitor not only connectivity but
also traffic and delay. There also is more special packet sending along with voice
via RTP stream for additional queueing and routing monitoring (This will be a
issue with IPv6)
Traffic control at IP PBX servers or VoIP gateways (cont)

Using single port for both signaling and voice stream





Example: Proposed by Mark Spencer, so called IAX2 protocol
Use UDP port 4569
Resolve NAT (Network Address Translation) problem
Easy to lost a call.
Other Traffic control that can reduce lost a call:




Call waiting
Call parking
Call queueing (different with packet queueing)
Music on hold
Optimizing in Queueing
performance and Traffic Control
Queueing length (delay time) vs. packet
lost
 Packet length vs. end-end delay
 Use of Segmental CODEC

Summary and Future works

Besides scheduling queuing based on statistical data such as traffic by hour of day, day of
week and week of year, Markov, Poisson real-time queuing system is also being used. VoIP
queuing modeling study is more focused on a general packetized network rather than a
specific TDM network. Therefore, most traffic control and modeling is based on fixed packet
length only, and future studies will be based on non-fixed packet length.

Queueing length must be short for VoIP but may not apply for other data queueing. The
network device may have dynamic or multi queueing schemes. A packet classifier or filter
could be used to re-route the packet to other queueing schemes.

Queueing at a CODEC processor is not considered since we assume CODEC is placed at the
terminal (phone).

Since the loss of a packets impact is significant to VoIP QoS, more study should be done in
comparison with other optimization processes.

Additional, voice messaging over IP system could be optimized with the use of a dedicated
sub-scheme, since real-time is not needed.

VoIP needs a standard routing agent
Referennce
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
Anthony S. Acampora, “An Introduction to Broadband Networks” ISBN 0-306-44558-1 – Plenum – 1994
Michael G. Hluchyj, Mark J. Karol, “ Queueing in high-Perfomance Packet Switching”, IEEE Journal on selected areas in communication, vol.
6, No.9, page(s) 1587-1596, 1988
Harrison, P.G.; Zhang, Y., “Delay analysis of priority queues with modulated traffic”, Modeling, Analysis, and Simulation of Computer and
Telecommunication Systems, 2005. 13th IEEE International Symposium, Page(s):280 – 287, 2005
Li Zheng; Liren Zhang, “Modeling and performance analysis for IP traffic with multi-class QoS in VPN”, MILCOM 2000. 21st Century Military
Communications Conference Proceedings, Volume 1, Page(s):330 – 334, 2000
Huebner, F.; Liu, D.; Fernandez, J.M, “Queueing performance comparison of traffic models for Internet traffic’, Global Telecommunications
Conference, 1998. GLOBECOM 98. The Bridge to Global Integration. IEEE, Volume , Page(s):471 – 476, 1998
Klepec, B.; Kos, A., “Performance of VoIP applications in a simple differentiated services network architecture”, EUROCON'2001, Trends in
Communications, International Conference on. Volume 1, Page(s):214 – 217, 2001
Lu Xin; Wang Ke; Dou Huijing, “Wavelet multifractal modeling for network traffic and queuing analysis”, Computer Networks and Mobile
Computing, 2001. Proceedings. 2001 International Conference on, Page(s):260 – 265, 2001
Goode, B., “Voice over Internet protocol (VoIP)”, Proceedings of the IEEE
Volume 90, Issue 9, Page(s):1495 – 1517, 2002
Gotoh, F.; Uno, S., “User modeling and uplink scheduling in IP-based ITS network”, Vehicular Technology Conference, 2001. VTC 2001
Spring. IEEE VTS 53rd, Volume 4, Page(s):3027 – 3031, 2001
Chengchen Hu, Xuefai Chen, Wenjie Li, Bin Liu, “Fixed-Length Switching vs. Variable-length Switching in Input-Queued IP Switches”, IP
Operations and Management, 2004. Proceedings IEEE Workshop on, Page(s):117 – 122, 2004
San-Qi Li; Mark, J.; “Performance of Voice/Data Integration on a TDM System”, Communications, IEEE Transactions on, Volume 33,
Page(s):1265 – 1273, 1985
Xi Zhang; Shin, K.G.; “Markov-chain modeling for multicast signaling delay analysis”, Networking, IEEE/ACM Transactions on, Volume
12, Issue 4, Page(s): 667 – 680, 2004
Flood, J.E. “Telecommunications Switching, Traffic and Networks, Chapter 4”: Telecommunications Traffic, New York, Prentice-Hall, 1998.
Richard Parkinson, “Traffic Engineering Techniques in Telecommunications”, http://www.tarrani.net
Michael J. Neely Eytan Modiano, “Logarithmic Delay for N × N Packet Switches”, IEEE Workshop on High Performance Switching and
Routing, 2004
Wei Wang; Liew, S.C.; Qixiang Pang; Li, V.O.K., “A multiplex-multicast scheme that improves system capacity of voice-over-IP on wireless
LAN”, Computers and Communications, 2004. Proceedings. ISCC 2004. Ninth International Symposium on, Page(s):472 - 477 Vol.1, 2004.
Hussian, A.; Sobraby, K.; Ali, M.A., “A novel two-queue model for ATM networks”, Global Telecommunications Conference, 1997.
GLOBECOM '97., IEEE, Page(s):758 - 765 vol.2, 1997
Shankar, S.; del Prado Pavon, J.; Wienert, P., “Optimal packing of VoIP calls in an IEEE 802.11 a/e WLAN in the presence of QoS
constraints and channel errors”, Global Telecommunications Conference, 2004. GLOBECOM '04. IEEE, Page(s):2974 - 2980 Vol.5, 2004
Cisco, “IP Telephony/ Voice over IP” http://www.cisco.com/en/US/tech/tk652/tk701/tsd_technology_support_protocol_home.html