Dr Riktesh Srivastava*
Assistant Professor, Information Systems, Skyline University College, University City of Sharjah, Sharjah, PO 1797, UAE.
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 . There is rapid growth in the number of users and hosts , number of web servers, application servers and network traffic  thereby resulting in increase in network loads and users’ response time . The performance of Gateway Servers was studied by ,, 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. ,,, have carried out the study on workloads of network and server performance under such traffic. ,, have used the mathematical analysis for Internet Servers performance analysis. , defined the dynamic buffer management techniques by which the buffer space can be reduced for fast transmission of data. The study by  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 (DBoptimal), under heavy traffic. This paper evaluates the DBoptimal by first evaluating the results for M/M/1 Queue Model and then implements the results for GI/G/n/k Queue Model.
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 λ,μ, DBoptimal 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 1010 number of requests.
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 DBoptimal 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 (DBoptimal) 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 ,
req1, req2, req3,..........reqn are the number of requests arriving at DB Server, and, T =Total time in which the request has arrived at DB Server.
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 :
res1, res2, res3,..........resn are total number of responses, and, T = Total time in which the resources has departed from DB Server.
Based on equation (1) and (2), there can be 3 possibilities ,:
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 DBoptimal, 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 M / M / 1, where first M describes the arrival process of users request to be Markovian. Markovian arrival process is nothing but Poisson arrival where inter-arrival distribution is negative exponential. The second M , describes the departure process with processing unit 1 (one in number). In case of multiple users’ requests arriving at a single instance of time, this assumption does not fit in. Under this condition when arrival of users request or departures of responses, both are considered multi-channel, the appropriate model becomes GI/G/n/k. It is worth to start with M / M / 1 queue model have been analytically studied for the estimation of average cache size. However, for multiple requests and responses, the study is carried for GI/G/n/k model to compute the DBoptimal. The M / M / 1 model is studied analytically in the next segment.
In this section, study is performed to evaluate the Cache Size mathematically using M/M/1 Queue model. Based on the mathematical formulation, DBoptimal, 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
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 Pn(t) . If the time is increased from "t " to "t + Δt "and at the end of this time, then, this state can be arrived at from the states as given below:
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 +Vt) . 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 DBoptimal 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 a1 ,a2 and a3 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 xi represents the rate of arrivals for the computation and then the value of Cache Size will be represented by yi . It is represented as given below:
where a0 ,a1 and a3 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 a0 ,a1,a3 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 (DBoptimal) 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:
DBoptimal=DBav+Standard Deviation of DB (27)
The Standard Deviation is given as:
Standard Deviation=DBav (28)
Hence, the desired cache size to meet the eventualities, the optimal cache size is:
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.
 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
 Grey, M., Growth of the World-Wide Web, 1994 Available via URL:http://www.mit.edu:8001/afs/sipb/user/mkgray/ht/comprehensive.html
 Merit NIC, NSFNET Statistics, 1994. Available via URL: gopher://nic.merit.edu:7043/11/nsfnet/statistics/1994
 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.
 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.
 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.
 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.
 P. Barford and M. Crovella, Generating representative web workloads for network and server performance evaluation, Measurement and Modeling of Computer Systems, 1998.
 D. Menasce and V. Almeida, Capacity Planning for Web Services: Metrics, Models, and Methods. Prentice Hall PTR, 2001.
 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.
 T. F. Abdelzaher, C. Lu, Modeling and Performance Control of Internet Servers, Invited Paper, 39th IEEEConference on Decision and Control, Sydney, Australia,December 2000.
 Jim W. Roberts, Traffic Theory and the Internet, IEEE Communications, January 2001.
 Xiangping Chen, Prasant Mohapatra, Performance Evaluation of Service Differentiating Internet Servers, Vol. 51, No. 11, 2002.
 Steven H. Low, R. Srikant, A Mathematical Framework for Designing a Low-Loss, Low-Delay Internet, IEEE transaction on Communications, 2002.
 Lei Ying, G. E. Dullerud and R. Srikant, Global Stability of Internet Congestion Controllers with Heterogeneous Delays, IEEE Transactions on Communications, 2003.
 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.
 Darrell Anderson, Ken Yocum, Jeff Chase, A Case for Buffer Servers, IEEE Seventh Workshop on Hot Topics in Operating Systems, 1999.