Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 2, February -2012 1

ISS N 2229-5518

Analysis & Design of Congestion Avoidance Scheme for Active Queue Management Problem for Linear Systems

Asst. Prof Rakesh Mandal, Asst. Prof. Anirudh Mudaliar

Abs tract- The Kalman Filter (KF) is used to optimally estimate system states from the sequential noisy measurements of the outputs. On the other hand, real-time systems are of ten modeled w ith uncertainties and time-delays. Developing KF algorithms f or such systems is an important problem to obtain optimal state estimates by utilizing the inf ormation on uncertainties and time-delays. First, designing of KF f or nominal discrete-time systems is studied. Considering the covariance of the error in the estimation the KF algorith m is derived w hich is f urther tested on a numerical example . A designed KF is tested on a real-time problem i.e. Active Queue Management (AQM) problem. In Internet routers, Active Queue Management (AQM) is a technique that consists in dropping or Explicit Congestion Notif ication (ECN) marking packets bef ore a router's queue is f ull.

Ke ywords - AQM, ECN, Discrete time system, Time-delay, KF, RKF, Kalman gain

—————————— ——————————

1. INTRODUCTION

Basically the KF is an estimator w hich estimate the futur e state fr om the ser ies of noisy measur ement for the given system state. The KF pr ovides a method for constr ucting an optimal estimate of the system state. KF is an efficient r ecur sive filter that estimates the state of a linear dynamic system from ser ies of noisy measur ement.
The KF is a r ecur sive estimator means that only
the estimated state fr om the pr evious step and the curr ent measur ement ar e needed to compute the estimate for the curr ent state. The KF operates by pr opagating the mean and covar iance of the state thr ough time. Basically the KF has two distinct phase time update & measur ement update. The time update uses the state estimates fr om the pr evious time step to pr oduce an estimate of the state at the curr ent time step. The measur ement update infor mation at the curr ent time step is used to r efine this pr ediction at new . The Kalman filter is a tool that can estimate the var iables of a w ide range of pr ocesses.
The Kalman filter not only w or ks w ell in practice, but it is theor etically attr active because it can be shown that of all possible filters, it is the one that minimizes the variance of the estimation err or . Kalman filter s ar e often implemented in embedded contr ol syst ems because in order to contr ol a
————————————————
Asst. Professor Anirudh Mudaliar is currently pursuing masters degree program in Communication Enginee ring from CSVTU and working in Shri Shankaracharya Technical Campus, C.G, India, E-mail: anirudh2231@gmail.com
Asst. Professor Rakesh Mandal is currently working in Shri

Shankaracharya Technical Campus, C.G, India, E-mail:

atulmandal93@gmail.com
pr ocess, you first need an accur ate estimate of the pr ocess variables.
The Kalman filter is a mathematical pow er tool
that is playing an incr easingly impor tant r ole in computer graphics as w e include sensing of the r eal w or ld in our systems. The good news is you don’t have to b e a mathematical genius to under stand and effectively use Kalman filters. This tutor ial is designed to pr ovide developer s of gr aphical systems w ith a basic understanding
of this impor tant mathematical tool.
The pr ocess of finding the “b est estimate” fr om
noisy data amounts to “filtering out” the noise.
How ever a Kalman filter also doesn’t j ust clean up the data
measur ements, but also projects these measur ements onto the state estimate.

2. KALMAN FILTERING FOR LINEAR DISCRETE TIME SYSTEM

Kalman Filter (KF) is a numer ical method used to track a time-varying signal in the pr esence of noise. It is the pr oblem of estimating the instantaneous state of a linear system fr om a measur ement of outputs that ar e linear combinations of the states but corrupted with Gaussian white noise. The r esulting estimator is statically optimal with r espect to a quadratic function of estimation err or . Fr om the mathematical point view , the KF is a set of equations that pr ovides an efficient r ecursive computational solution of the linear estimation pr oblem. The filter is very pow er ful in several aspects. The KF is an extr emely effective and versatile pr ocedur e for combining noisy sensor outputs to estimate the state of the system with uncertain dynamics. When applied to a physical

IJSER © 2012

http :// www.ijser.org

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 2, February -2012 2

ISS N 2229-5518

system, the observer or filter will be under the influence of tw o noise sources: (i) Pr ocess noise, (ii) Measur ement noise. The estimate of the state is specified by its conditional pr obability density function. The purpose of a filter is to compute the state estimate, while an optimal filter minimizes the spr ead of the estimation err or pr obability finite time can be expr essed as the follow ing five st eps:
1.) State Estimate Extrapolation(pr opagation)
2.) Covar iance Estimate Extrapolation(pr opagation)
3.) Filter Estimate Update
4.) State Estimate Update
5.) Covar iance Estimate “Update”

x  n

W e use a KF to estimate the state k of a
discr ete time contr olled system. The system is descr ibed by a linear stochastic differ ence equation.
density. A r ecur sive optimal filter pr opagates the conditional pr obability density function fr om one sampling instant to the next, keeping in view the system dynamics and inputs, and it incor porates measur ements and measur ement error statistics in the estimate.
2. Measur ement update equation
The time update equations pr oj ect the curr ent state and the err or covar iance estimates forwar d in the time to obtain a pr iori estimates for the next time step. The measur ement update equations handle th e feedback. In other wor ds, it incor porates a new measur ement into the a prior i estimate to obtain a corr ected a posterior estimate. Ther efor e the time update equations ar e pr edicator equations, and the measur ement update equations ar e corr ector equations. That is, the KF is a pr edictor-corr ector algor ithm to pr ovide a r ecursive solution to the discr ete

xk 1 Axk Bwk

(2.1)
time linear system, as shown in Fig. 2.1 .

yk Cxk vk


(2.2)
wher e,

x  n

k is the system state,

q

y  m

k is the

p

measur ed output,

wk  is the pr ocess noise, vk 

TIME UPDATE

MEASUREMENT

v

is the measur ement noise. In the following k
and

wk will

be r egar ded as zer o mean, uncorr elated white noise

R Q

sequence w ith covar iance k and k .
FIGURE 2.1: Discr ete Kalman Filter Cycle

vk N 0, Rk

wk N 0, Qk .

A  nn

(2.3)
(2.4)
The time and measur ement update equations ar e pr esented below:
The time updates equations:
The matr ix
in the differ ence Equation (2.1) is the

xˆ

Axˆ

Bu

(2.5)
dynamics matr ix which r elates the sate at time step k to the

B  n1

k 1 k k

T

sate at time step k  1. The matrix
called noise

P AP A Q

(2.6)
matrix. The matr ix

C  mm

in the measur ement

k 1

k k k

y

Equation (2.2) r elates the state measur ement k .When the
The measur ements update equations:
The KF algor ithm can be seen as a for m of

T Y

1

feedback estimation. The set of the KF equation can be

K f Pk Ck

Ck Pk Ck

Rk

(2.7)
separ ated in tw o gr oups:

xˆk

xˆk K f yk Ck xˆk

(2.8)
1. Time update equations

Pk

I K f Ck k

(2.9)

IJSER © 2012

http :// www.ijser.org

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 2, February -2012 3

ISS N 2229-5518


The time-update equation proj ects the state estimate and covar iance from time step k to step k  1.
To compute the Kalman Gain (KG)

K f is the first

j ob in the measur ement update equations. Then yk is
obtained by actual measur ement of the system. Incor porating the actual measur ement and the estimated one in equation (2.7), w e generate a poster ior estimate. The last step is to compute a poster ior err or covar iance. This is the r ecur sive operation of the KF. A complete pictur e of the operation of the KF is illustrated in Fig. 2.2 , after each time and measur ement update pair , the r ecur sive algor ithm is r epeated w ith the pr evious a posterior estimates to pr edict the new a pr iori estimates. This r ecursive natur e is the biggest advantage of the KF. This makes the practical
implementation of the KF much easier and feasible then the
Figur e 3.1: A Sender Receiver Connection

4. RESULTS & SIMULATIONS

4.1 Simulation Result of Kalman Filter

Consider the following discr ete time system,
implementation of the W iener filter , because the W einer

x  0

0.5

x

 6 w

filter obtains its estimates by using all of the pr ecedent data

k 1

1 1  k

 1  k

dir ectly. In contrast, the KF only uses the immediately pr evious data to pr edict the curr ent states [9].

3. ACTIVE QUEUE MANAGEMENT PROBLEM

In Internet r outers, Active Queue Management (AQM) is a technique that consists in dr opping or Explicit Congestion Notification (ECN) mar king packets befor e a r outer 's queue is full [8].
An Inter net r outer typically maintains a set of queues, one per inter face, that hold packets scheduled to go out on that inter face. Histor ically, such queues use a dr op- tail discipline: a packet is put onto the queue if the queue is shorter than its maximum size (measur ed in packets ar e in bytes), and dr opped otherwise. Active queue disciplines dr op or mar k packets befor e the queue is full. Typically, they oper ate by maintaining one or mor e dr op/mar k pr obabilities, and pr obabilistically dr opping or mar king packets even when the queue is short. The uniqueness of our appr oach comes fr om the use of a r ecently developed dynamic model of the transmission contr ol pr otocol (TCP) which enables application of contr ol pr inciples to addr ess the basic feedback natur e of AQM [6].

   

yk 100 10xk vk

Note that the above system is of the form of system with

1 0

P S    ,W  1,V  1

 

FIGURE 4.1: No. of Iteration vs. True State and

Estimated State

FIGURE 4.2:

No. of Iteration vs. Eigen Value of Covariance Matrix

IJSER © 2012

http :// www.ijser.org

Inte rnatio nal Jo urnal o f Sc ie ntific & Eng inee ring Re se arc h, Vo lume 3, Issue 2, February -2012 4

ISS N 2229-5518

4.2 State Estimation using Kalman Filter in active queue management problem

FIGURE 4.3: Number of iteration and true state &

estimated state

FIGURE 4.4: Number of iteration Eigen values of covariance matrix

5. CONCLUSION

KF is a pow er ful tool to estimate states of a system under noisy output measur ements. In this chapter , a formulation has been pr esented for the design of KF for linear systems without consider ing the time-delay and some basic ideas on KF. For estimation, pr ediction & r eduction of err or the KF per formance is satisfactory. The KF is the most widely used filter for its better per for mance. It is a very simple and intuitive concept w ith good computational efficiency. But when uncertainty and time delay is included then the per formance of KF may degr aded, so RKF is consider ed which is r obust against lar ge parameter uncertainty and time delay. In coming chapter a per formance comparison betw een RKF and KF is obtained for linear discr ete-time uncertain system. Secondary, a r eal time pr oblem i.e. AQM is consider ed. Initially the system was in continuous time domain then it is converted to discr et e time domain. And the discr etized form is tr ansfor med to another model for
easy implementation of KF. Fr om the Fig. 4.3 and 4.4 we see that the estimated state is appr oximate to the true state and with the incr eases of number of iter ation the err or will be r educe.

8. REFERENCES

[1] Antonis Papachr istodouluo and Ali Jadb aaie, “Delay Robustness of Nonlinear Inter net Congection Control Schemes”, IEEE Tr ansaction on aytomatic contr ol, Volume
55, pp- 1421-1427,(2010).
[2] Mital A Gandhi, and Lamine Mili, “Roust Kalman Filter based on a Generalized Maximum- Likegood-Type Estimator ”, IEEE Tr ansaction on Signal Pr ocessing, Volume
58, pp-2509-2520,(2010).
[3] Rodrigo Fontes Souto and Joao Yoshiyuki Ishihara, “Robust Kalman Filter for Discr ete-Time Systems W ith Corr elated Noise”, Aj accio, France, 2008.
[4] Ashvin Lakshmikantha, Car olyn L. Beck, and R. Sr ikant, “Robustness of Real and Virtual Queue- Based Active Queue Management Schemes”, IEEE/ACM Tr ansaction on networ king, Volume 13, pp- 81-93,(2005).
[5] X.Lu, H.Zhang and W .Wang, “Kalman Filter ing for
Multiple Time Delay System”, Automatica, Volume 41, pp-
1455-1461 (2005).
[6] Tansu Alpcan, and Tamer Basar , “A Gloally Stab le Adaptive Congestion Contr ol Scheme for Internet -Style Networ ks With Delay ”, IEEE/ACM Tr ansaction on networ king, Volume 13, pp-1261-1274,(2005).
[7] Z.W ang, J.Lam and X.Liu, “Rob ust Kalman filtering for Discr ete-Timr Mar kovian Jump Delay Sustem”, IEEE Signal Pr ocessing Letter s, Volume 11, pp- 659-662 (2004).
[8] C.V.Hollot, V.Mishr a, D.Tow sley, and W .Gong “Analysis and Design of Controllers for AQM Routers Suppor ting TCP Flows”, IEEE Tr ansactions on Automatic Contr ol, Volume 47, pp- 954-959, (2002).
[9] V.Mishra, W .Gong, and D.Tow sley, “Fluid based analysis of a netw or k of AQM r outers suppor ting TCP flow s w ith an application to RED”, Pr oceeding ACM/SIGCOMM, (2000).

IJSER © 2012

http :// www.ijser.org