Medical, Pharma, Engineering, Science, Technology and Business

**Dr Riktesh Srivastava ^{*}**

Assistant Professor, Information Systems, Skyline University College, University City of Sharjah, Sharjah, PO 1797, UAE.

- *Corresponding Author:
- Dr Riktesh Srivastava

Assistant Professor

Information Systems

Skyline University College

University City of Sharjah Sharjah

PO 1797, UAE

**Email :**[email protected]

**Visit for more related articles at** International Journal of Advancements in Technology

Continuous boost in the number of Internet users has taken an exponential escalation over the years. It is becoming thorny to endow with services to all the Internet users because of infrastructural precincts of WWW. Caching data base objects at DB servers has proven to be one of the preeminent alternatives for fast services. Caching DB server improves the performance of overall web access. Since the introduction of DB servers, most of the evaluations studies are performed either on Web-replacement algorithms or methodologies of maintaining the data in cache. Only few of studies have been done assuring DB server cache size. This paper describes the methodology of estimating the cache size under high busty traffic situation. An investigational evaluation study applying M/M/1 Queuing Theory methodology is first appraised and then experimented. The study uses a trace-driven simulation framework, real traces containing approximately 1010 number of user's requests per unit time, and then evaluates the Optimal DB Cache Size (DBoptimal) using GI/G/n/k Queue Analysis.

Server, M/M/1 Queuing Model, GI/G/n/k Queuing Model, Optimal DB Cache Size.

By all indications, WWW continues its remarkable and seemingly unregulated growth [1]. There is rapid growth in the number of users and hosts [2], number of web servers, application servers and network traffic [3] thereby resulting in increase in network loads and users’ response time [4]. The performance of Gateway Servers was studied by [5],[6],[7] using comparative analysis of M/M/1 with M/G/1, G/M/1 and G/G/1 queuing theory. Number of research is being performed to improve the rate of data access and decrease the response time. [8],[9],[10],[11] have carried out the study on workloads of network and server performance under such traffic. [12],[14],[15] have used the mathematical analysis for Internet Servers performance analysis. [15],[16] defined the dynamic buffer management techniques by which the buffer space can be reduced for fast transmission of data. The study by [15] has used the case study of Media servers in order to conduct the experiments. In this paper, the author claims that the most prominent solution to problem is “DB cache”. In DB cache mechanism, the data requested by the users are accessed by web server and stored in the cache memory of DB server for further reference. Number of Web replacement algorithms, including FIFO (First In First Out), LRU (Least Recently Used) and MRU (Most Recently Used) were implemented to define the mechanism of data storage, data removal and data retrieval. Surprisingly, not much of the research is done to estimate the Optimal DB Cache Size (*DB _{optimal}*), under heavy traffic. This paper evaluates the

The paper devices the mathematical approach to resolve the size of cache, where λ is the arrival rate of users request at DB Server and μ defines the departure of accesses resources. Based on the values λ,μ, *DB _{optimal}* is calculated such that the rate of data access from cache increases. The paper evaluates the number of 15000 references to cache and later simulates the result for higher rate of arrivals, to the maximum extent of 10

The result of the paper divided as follows: Section 2 delineates the Internet architecture with DB Server and then defines the mathematical formulation of λ and μ. Section 3 elaborates the analytical study of M/M/1 Queue model for estimation of cache size mathematically. Section 4 gives the computation results and estimation of Cache size using the regression technique, for higher rate of users’ requests to estimate the *DB _{optimal}* for DB Server by means of GI/G/n/k Queuing model. Section 5 concludes the paper.

The architecture of Internet with DB Server is portrayed in **Figure 1**, given below:

If **Figure 1** is further consolidated, it will be condensed to a single request arrival and a single response departure processing system. In this structural design, the solutions to the query is first searched in the DB cache, if the data is obtained in DB Cache, the response is send back to the client, and otherwise, the query is send to the DB server to be processed, which is then stored in DB cache and response is then send to the requesting client. In this case, when the cache memory is full, we can even use web replacement algorithms are applied to place the new data in cache and obsolete data is replaced. As Arrival of request and Departure of responses are random in nature, the estimation of DB cache size (*DB _{optimal}*) becomes the issue for Data Base Designers. The mission of design should be:

1. No request from user should be overflowed / freezed out.

2. Cache Size should not be abnormally large.

3. There is “n” number of requests from users at a time. The architecture must be such designed that it should provide stable functioning.

These three problems are of prime importance for designing the complete Internet architecture with DB Server. The DB Server resembles the working of Queuing theory, where there are number of requests arriving in Web Server and number of resources generated at a single instance of time.

**Mathematical Evaluation of the System**

Consider that λ is the summation of request from the Application Server to the DB Server per unit time [5],

where,

*req*_{1, }*req*_{2}, *req*_{3},..........*req _{n}* are the number of requests arriving at DB Server, and,

Similarly, if the requested data is found in the cache of DB server, the resource is given back to the client. The rate of departure of resources from DB Server is defined as [5]:

where,

*res*_{1, }*res*_{2}, *res*_{3},..........*res _{n}* are total number of responses, and,

Based on equation (1) and (2), there can be 3 possibilities [6],[7]:

a) If rate of arrival of users request is greater than the departure rate, i.e.,

*λ* > *μ* **(3)**

This case is called Transient state. If arrival rate of users’ request is greater than the departure rate of resources, then, there are chances of more cache miss rather than cache hit, which makes the entire system unstable. Hence, it is concluded that under no circumstances equation (3) should prevail.

b) When arrival rate of users’ request is equal to departure rate of resources from DB Server, i.e.,

*λ* = *μ* **(4)**

This is a very typical case, often referred to as Null state. Such phenomenon randomly occurs. This case is typical for academic studies only. Practically, this neither occurs nor is desirable. c) When arrival rate of users’ request is less than departure rate of resources from DB Server, i.e.,

*λ* < *μ* **(5)**

This is case is called as Ergodic state. If this situation is maintained throughout the system, there were be not system failure and often it results in higher rate of cache hit and less cache miss.

The study is thus made for the estimation of *DB _{optimal}*, which provides all the randomly arriving
users’ request. In the present study, when a very huge amount of users’ request is arriving at the
DB Server for cache reference, and very huge random departure occurs after referring the cache.
The problem becomes very complicated to be solved analytically. This problem gets further
complicated when the rate of users arrival is huge in number from multiple sources. Had it been
arriving from a single source with similar type of requests, the queuing model would have been
proximate to

In this section, study is performed to evaluate the Cache Size mathematically using M/M/1
Queue model. Based on the mathematical formulation, *DB _{optimal}*, for high busty traffic using
GI/G/n/k model is evaluated in the next section of the paper.

**Assumptions for Mathematical Formulation of Cache Size**

For estimation of “n” number of requests arriving at the DB Server, certain assumptions have to be made. This can be given as follows:

1) Δ*t* is a very small time, in which only one process can occur, i.e., either arrival of
users’ requests or departure of resources from DB Server.

2) The Ergodic state is maintained throughout the study.

3) The state of arrival of users’ request is *λ* and state of departure from DB Server is *μ*

Probability of only one arrival of users’ request at DB Server = *λ*Δ*t*

Probability of only one departure of resource from DB Server =*μ*Δ*t*

Then, Probability of no arrival of users’ request from DB Server = 1 – *λ*Δ*t*

and,

Probability of no departure of resource from DB Server = 1 – *μ*Δ*t*

Now, consider that there are "*n*" number of users’ request at any time "*t* " . This, will be
represented by *P _{n}*(

or,

Thus, the R.H.S. of equation 8 becomes

To solve, equation 9, we need to consider the initial condition, i.e., there is 0 (nil) presence of
users’ requests at time (*t* +V*t*) . This can be obtained from the states as given under:

Thus, L.H.S. of equation 10 becomes

Hence, equation 11 becomes

From equation 9 and equation 12, following can be easily derived as:

Summation of all the equations in equation 13 is given as under:

Based on limiting condition, when , L.H.S. becomes 1 and R.H.S. becomes

Thus equation 14 becomes

If equation 14 is substituted in equation 13, then

Hence, the probability for the presence of "*n*"data can be computed at any time "*t*" provided rate
of users’ request and rate of resources from the DB Server is known.

*Estimation of Cache Size for M/M/1 Queuing Model*

In section 3.1, the probability density function for the existence of "*n*" data has been derived as:

For variable "*n*" the average value can be written as:

where DB is Cache Size.

The equation 17 measures the Cache size of DB server mathematically for M/M/1 Queue model.

The random arrival of users’ requests at DB Server can be assumed either disciplined distribution
or it can be assumed undisciplined arrival or departure. Estimation of *DB _{optimal}* becomes a case of
GI/G/N/K Queue model, as there are multiple requests arriving at DB Server at a time, and
multiple resources are transferred at a time. Initially, the experiment was conducted for

*λ* = 5000,7500,10000,12500,15000 and for the worst case of cache size is *μ* = *λ*+1 based
becomes *μ* = 5001,7501,10001,12501,15001. The average computed Cache Size is given in **table
1**.

The Cache Size computed is for the lower rates of arrivals. It is not possible to have very high
arrival rate for computation of models. It is therefore proposed to carryout study for higher
values of arrival rates by employing"*curve* – * fitting techniques*" . Curve-fitting technique, also
known as "*Regression Techniques*" thus, gives the extrapolation for the average queue values at
high rate of users’ requests.

**Extrapolation of Cache Size Length at High rate of users’ request using
Regression/Curve Fitting technique**

In case of M/M/1 model, the equation is plotted between rate of users’ requests and Cache Size, it is then expressed as:

For the worst case of Data Base Cache Size, the equation can be derived using:

The equation 20 is a linear equation with slope of unity. In case of other models, if we observe the plot, we find that GI/G/n/k models have curves. The curves are smooth and can be assumed to be a second order polynomial, which is close to first order polynomial formed by model M/M/1.

The equation of the plots can be assumed:

This equation can be fitted in all the cases of plots. However, the coefficients in each model will
be different. What is required to find out is the values of *a*_{1} ,*a*_{2} and *a*_{3} for the best fitted curve
which has minimal error. For this reason, we have to express error, differentiate it and equate to
zero for calculation of coefficients.

**Coefficients of GI/G/N/K model**

It is observed from **Figure 2**, that the curve of GI/G/N/K represents a polynomial equation for
representing plot of Cache Length w.r.t. rate of arrival of users’ requests and Cache Size. To
have minimal error in regression, mean square error is made minimal to give good result. Let *x _{i}* represents the rate of arrivals for the computation and then the value of Cache Size will be
represented by

where *a*_{0} ,*a*_{1} and *a*_{3} are coefficients of polynomial for GI/G/N/K model.

The equation 22 is valid for larger rates of arrival of users’ requests, which includes *CAUSAL EFFECT* . This cannot be employed for lower rates of arrival.

Let "*S*"represents the error in computation and real values of Cache Size, then, "*S*", which is
square of derivation, is given as:

If be differentiate S w.r.t *a*_{0} ,*a*_{1},*a*_{3} and setting each of these coefficients equal to zero, we get

where "*n*"represents the degree of polynomials as "*n*" equations are formed for the summation.
These are three linear equations in three unknowns. These are called *normal equations* for
quadratic regression. These may be solved using Gauss Elimination procedure.
Upon calculating, following set of equation were obtained:

Gaussian elimination and using back substitution, we obtain:

**Optimal Data Base Cache Size ( DB_{optimal}) using GI/G/n/k Queuing Model**

It is to note that computation of Cache size was for average value. The actual Cache size will
deviate from average value at every instance. Sometimes, Cache size is lower than average and
at other times it is higher average value. The estimation of cache size should be such that cache
hit should be higher that than the average value. Thus, it indicates that positive deviations are to
be incorporated in the estimation of cache size. Standard deviation, which is positive square root
of variance, is required to be added in the average value of cache size. Standard deviation in
many statistical distributions is equal to average value. **Table 2** measures the cache size at DB
Server.

Using equations, the expected Cache size are computed

The optimal value for memory size is given as:

DB_{optimal}=DB_{av}+Standard Deviation of DB ** (27)**

The Standard Deviation is given as:

Standard Deviation=DB_{av} **(28)**

Hence, the desired cache size to meet the eventualities, the optimal cache size is:

DB_{optimal}=2.DB_{av }**(29)**

The calculated cache size(s) are depicted in **table 3**.

The study confirms that the proposed model be such that it should follow the condition λ<μ [ERGODIC CONDITION]. This will guarantee more number of cache hit resulting in stability of the system implementation. The cache size estimated by queuing theory will ensure that there is minimal cache miss by evaluating the optimal size of Data base cache size.

[1] Pitkow & Recker, A Simple Yet Robust Caching Algorithm Based on Dynamic Access Patterns, Proceedings of the Second International WWW Conference 7 GVU Technical Report: VU-GIT-94-39

[2] Grey, M., Growth of the World-Wide Web, 1994 Available via URL:http://www.mit.edu:8001/afs/sipb/user/mkgray/ht/comprehensive.html

[3] Merit NIC, NSFNET Statistics, 1994. Available via URL: gopher://nic.merit.edu:7043/11/nsfnet/statistics/1994

[4] Viles, C. and French, J, Availability and Latency of World-Wide Web Information Servers, 1994, University of Virginia Department of Computer Science Technical Report CS-94-36.

[5] Riktesh Srivastava, LK Singh, Design and Implementation of G/G/1 Queuing Model Algorithm for its Applicability in Internet Gateway Server, The International Arab Journal of Information Technology, Vol. 5, No. 4, 2008.

[6] Riktesh Srivastava, LK Singh, Memory Estimation of Internet Server using Queuing Theory: Comparative Study between M/G/1, G/M/1 and GI/G/N/K Queuing Model, International Journal of Computer and Information Science and Engineering (IJCISE), Volume 1 Number 2, 2007.

[7] Riktesh Srivastava, LK Singh, Estimation of Buffer Size of Internet Gateway Server via G/M/1 Queuing Model, International Journal of Applied Science, Engineering and Technology, Volume 19, , 2007.

[8] P. Barford and M. Crovella, Generating representative web workloads for network and server performance evaluation, Measurement and Modeling of Computer Systems, 1998.

[9] D. Menasce and V. Almeida, Capacity Planning for Web Services: Metrics, Models, and Methods. Prentice Hall PTR, 2001.

[10] E. D. Lazowska, J. Zahorjan, G. S. Graham, and K. C. Sevcik, Eds., Quantitative system performance: computer system analysis using queueing network models. Prentice-Hall, Inc., 1984.

[11] T. F. Abdelzaher, C. Lu, Modeling and Performance Control of Internet Servers, Invited Paper, 39th IEEEConference on Decision and Control, Sydney, Australia,December 2000.

[12] Jim W. Roberts, Traffic Theory and the Internet, IEEE Communications, January 2001.

[13] Xiangping Chen, Prasant Mohapatra, Performance Evaluation of Service Differentiating Internet Servers, Vol. 51, No. 11, 2002.

[14] Steven H. Low, R. Srikant, A Mathematical Framework for Designing a Low-Loss, Low-Delay Internet, IEEE transaction on Communications, 2002.

[15] Lei Ying, G. E. Dullerud and R. Srikant, Global Stability of Internet Congestion Controllers with Heterogeneous Delays, IEEE Transactions on Communications, 2003.

[16] Yeon Seung Ryu, Kern Koh, A Dynamic Buffer Management Technique for Minimizing the Necessary Buffer Space n a Continuous Media Server, IEEE International Conference on Multimedia Computing and System (ICMCS), 1996.

[17] Darrell Anderson, Ken Yocum, Jeff Chase, A Case for Buffer Servers, IEEE Seventh Workshop on Hot Topics in Operating Systems, 1999.

Select your language of interest to view the total content in your interested language

- ACS Nano
- AI Algorithm
- Advanced Materials
- Animation
- Antenna Design
- Architect
- Architectural Drawing
- Architectural Engineering
- Architecture
- Artificial Intelligence
- Automated Mining
- Automation
- Behavior-based systems
- Bioinformatics Techniques
- Biomechanics
- Biomechanics and Robotics
- Bionics
- Building design
- Communication Systems
- Computational Neuroscience
- Computer Networking
- Computer Networks
- Concrete
- Construction
- Construction Engineering
- Construction Estimating Software
- Cordless
- Cyber Physical System
- Cyber Security
- Cyber Technologies
- Data Engineering
- Datamining
- Digital Image Processing
- Digital Signal Processing
- Engineering Drawing
- Fabric Formwork
- Fluid Engineering
- Fuzzy Logic
- Gaming Technology
- Genomics
- Graphic design
- Graphic designing
- Image Processing
- Industrial Robotics
- Information Science
- Information Theory
- Intelligent Robotics
- Interior Design
- Interior Designing
- Landscape Architecture
- Lovotics
- Machine Vision
- Manufacturing
- Medical Device
- Medical Robotics
- Mobile Device
- Mobile Repots
- Modeling
- Motion picture
- Multimedia Network
- Neural Networks
- Neurorobotics
- Product Modeling
- Radar Imaging
- Radio Waves
- Robotic Rehabilitation
- Satellite Communication
- Search Engine Design
- Sensors
- Simulation
- Simulation and Visualization
- Simulation and Visualization Effects
- Smart Grid
- Social Robots
- Sociology of Architecture
- Soft Computing
- Spatial Database
- Telecommunications Journal
- Telerobotics
- Tribology
- Urban Design
- Urban Planner
- Virtual Reality
- Virtual Reality Technology
- Wave Length
- Web Developer
- Wireless Journals
- swarm intelligence and robotics

- Total views:
**11407** - [From(publication date):

December-2012 - Dec 14, 2017] - Breakdown by view type
- HTML page views :
**7671** - PDF downloads :
**3736**

Peer Reviewed Journals

International Conferences
2017-18