Bjørn J Villa
email: bjorn.villa@item.ntnu.no

Poul E Heegaard
email: poul.heegaard@item.ntnu.no

Anders Instefjord
email: anders@vimond.com

Improving Fairness for Adaptive HTTP Video Streaming

Keywords: Fairness, Adaptive Streaming, Available Bandwidth Estimation

This paper presents an analysis of a suggested method for improving fairness among competing adaptive HTTP video streams. The metrics used as fairness indicators are differences in achieved average rate and stability among the competing streams. The method analyzed is based on changing a fixed and equal video segment request rate of each stream, to either a per session unique or random request rate. The analysis is done by means of measurements in a controlled environment using the Microsoft Smooth Streaming solution. The findings are considered very positive as they show that it is possible to achieve a significant improvement in fairness by applying the suggested method. The main novelty of the paper is that it demonstrates the potential of achieving such improvements without modifying either client or server algorithms.

Introduction

Internet services with video components have become a great success in terms of general usage and also as facilitator of new business models on the Internet. A significant part of these services is carried as best-effort traffic between a content provider and the end user. In order to make this possible in a way which is acceptable to the user, a new concept of adaptive video streaming has emerged. The concept is used in solutions from many vendors (Microsoft, Apple, Adobe et.al.)and they all share the same characteristic in terms of being able to adapt the video quality level during the session according to certain observed metrics (e.g. available bandwidth and CPU load). The main rationale behind this is to enable a video session to survive the varying conditions experienced on the Internet.

Even though the adaptive streaming solutions in the marketplace today share some important characteristics, they remain highly proprietary awaiting the successful completion and adoption of the ongoing active standardization effort known as MPEG DASH [START_REF]ISO: Dynamic adaptive streaming over http (dash)[END_REF]. The scope of the standard covers interfaces and message formats, which will enable future interoperability between client and servers from different vendors.

Although the new standard will resolve the important interoperability issue, it will not remove the competitive differences between the solutions offered which reflects their approach and set of priorities. As an example, one could look at the solutions from Apple and Adobe which to some extent represent two opposites [START_REF] Riiser | A comparison of quality scheduling in commercial adaptive http streaming solutions on 3G network[END_REF]. The Apple solution tries to maintain a more stable quality (minimize number of changes), at the expense of average quality level. The Adobe solution does it quite differently and almost continuously adjusts the quality level, giving a higher average quality level but at the expense of a potentially higher number of quality changes. The Microsoft solution [START_REF] Zambelli | IIS smooth streaming technical overview[END_REF] is somewhere between these two and tries to achieve stability and also a high average quality level, and this is the one used as reference point for the work reported in this paper.

Problem Statement

As the concept of adaptive streaming is becoming widely adopted for delivery of video services on the Internet there are weaknesses appearing. In fact, one could say that the success of the concept becomes its biggest problem. Reason being that the concept works best in a scenario when you are primarily concerned with one video service, and the rest of the traffic is of less importance. However, when multiple adaptive streaming sessions appear at the same timecompeting for the same access capacity their performance becomes quite questionable. Traditional topics like intra flow fairness become an issue as well as session stability.

The most likely reason for performance degradation under such conditions is that the algorithms controlling the streams were not made with this in mind. An important area where improvements could be made is with regard to how each session estimates available bandwidth. Ideally, each session should in some way be able to get a notion of all other traffic and thereby also an accurate view on available bandwidth. A candidate reason for why this is not working properly in current solution may be the strict periodic burst/idle nature of each adaptive streaming session (cf. Fig. 1).

Fig. 1. Burst and idle periods of adaptive http streaming

The periodic characteristic is given by the per session segment@quality request intervals while the burst part is given by the fact that the server always tries to deliver the next segment as fast as possible in order to maintain a high degree of client buffer filling. For the Microsoft Smooth Streaming solution, the typical segment@quality request interval T has a value of 2 seconds. Depending on which quality level a client session is running at it will then be receiving IP packets belonging to the next video segment only during parts of this period T. We call this part the burst period, and the remaining part of T the idle period.

A potential reason for errors made when calculating available bandwidth during each burst period is the fixed and identical periodic behavior of each session. In a situation where the competing traffic is of similar type, e.g. multiple adaptive video streamswe will have that each stream during its burst periods always will notice some of the other streams but at the same time always miss some others. This makes it challenging for the available bandwidth algorithm to provide quality input to the decision making process in the client. The result will be that in many cases the client will make a decision to go up in quality level, even though there is not enough available capacity. This again leads to an increased congestion with a potential overall session impact.

Research Approach

A suggested method of improving fairness among competing adaptive video streams was introduced in our previous work [START_REF] Villa | Improving perceived fairness and QoE for adaptive video streams[END_REF] and analyzed by means of simulations. This method was based on changing the fixed T parameter to a random T parameter according to some stochastic distribution.

In addition to this, we now also include new version of the method being the case where each competing stream is set to have a fixed but unique T value. The uniqueness applies among the group of streams competing for a specific amount of bandwidth, e.g. simultaneous streams delivered to members of a household. The purpose of both these suggested changes for the T value is to improve the accuracy of the available bandwidth estimation done by each session.

The approach taken in the work reported in this paper is to take the method validation one step further, by means of performing an experimental validation through a series of measurements in a controlled environment.

Paper Outline

The structure of this paper is as follows. Section 2 provides an overview of related work; Section 3 presents the measurement setup; Section 4 provides the results and an analysis; Section 5 provides the conclusions and an outline of future work is given in Section 6. Acknowledgements are given in Section 7.

Related Work

The amount of research in this field has been growing over the last years in parallel with commercial deployments and an ongoing standardization effort [START_REF] Sodagar | The mpeg-dash standard for multimedia streaming over the internet[END_REF]. The most related research is found in the area of streaming performance evaluation and how to enhance key functionality related to session quality control.

In [START_REF] Akhshabi | An experimental evaluation of rateadaptation algorithms in adaptive streaming over http[END_REF] the authors describe and evaluate selected commercial and open source players for adaptive streaming. They also perform an experimental evaluation of their performance. One of their interesting findings is that competing adaptive streams can cause unpredictable performance for each stream, both in terms of oscillations and ability to achieve fairness in terms of bandwidth sharing. In [START_REF] De Cicco | An experimental investigation of the Akamai adaptive video streaming[END_REF] the authors have investigated how well adaptive streaming performs when being subject to variable available bandwidth in general. Their findings were that the adaptive streams are performing quite well except for during some transient periods. These findings do not contradict the findings in [START_REF] Akhshabi | An experimental evaluation of rateadaptation algorithms in adaptive streaming over http[END_REF] as the type of background traffic used did not have the adaptive behavior itself. In [START_REF] Riiser | A comparison of quality scheduling in commercial adaptive http streaming solutions on 3G network[END_REF] the authors have performed an experimental evaluation of commercial adaptive streaming players in a challenging emulated 3G network environment. Their findings were that there are significant differences between the players in terms of behavior, which supports the findings in [START_REF] Akhshabi | An experimental evaluation of rateadaptation algorithms in adaptive streaming over http[END_REF] but under different network conditions.

In [START_REF] Liu | Rate adaptation for adaptive http streaming[END_REF] a rate adaptation algorithm which uses a smoothed HTTP throughput measure based on the segment fetch time is proposed and analyzed by means of simulation. This work was taken further by the same authors in [START_REF] Liu | Segment duration for rate adaptation of adaptive http streaming[END_REF] and then focusing on the importance of the video segment length and potential of choosing more optimal values for this. Further on, the same research group investigated the potential in using a parallel HTTP streaming approach [START_REF] Liu | Parallel adaptive http media streaming[END_REF] in order to provide a higher quality. Their simulation results demonstrated a significant potential in doing so. The authors of [START_REF] Mok | Qdash: a QoE-aware dash system[END_REF] have also suggested an enhanced method for performing available bandwidth estimation and verified it through experiments. The principle applied is the same as in [START_REF] Liu | Rate adaptation for adaptive http streaming[END_REF] in the sense that measurements are done based on the data received for each video segment in the stream.

While many publications focus on how to make the client side of an adaptive streaming session more intelligent, the authors of [START_REF] De Cicco | Feedback control for adaptive live video streaming[END_REF] has taken to opposite approach and suggested to make the server side of it more intelligent. Their approach is intended to maintain a low complexity in the player, while at the same time achieving a high degree of effectiveness in session control. Alternative approaches are described in [START_REF] Houdaille | Shaping http adaptive streams for a better user experience[END_REF] and [START_REF] Villa | Towards knowledge-driven QoE optimization in home gateways[END_REF] where the role of the home gateway is investigated in terms of ability to improve adaptive streaming performance.

Measurement Setup

In order to perform the required measurements a testbed was established in a controlled environment including all required components. As illustrated in Fig. 2 a number of clients behind an access congestion point were set up to access a Microsoft Smooth Streaming service. The clients were accessing the same adaptive stream from the server and run in a loop with intervals of 25 minute active streaming and then 5 minute break. For each scenario studied the loop was set to give 100 interval repetitions. An earlier developed tool for event reporting [START_REF] Villa | A monitor plane component for adaptive video streaming[END_REF] from each client (Monitor Plane event reports) is used in order to record interesting events on a per session basis and allow for post processing. The available quality levels for the video stream used were 350, 500, 1000, 1500, 2000, 3000, 4000 and 5000Kbps.

Fig. 2. Measurement testbed

A series of measurement scenarios were defined in order to study the effect of the suggested method under various conditions. The parameters describing a specific scenario was the access capacity shared between the competing adaptive streaming sessions and a specific segment@quality request interval approach (i.e. the T parameter). For the access capacity, values of 10, 15 and 20Mbps were used. This would all be cases with a high degree of congestion as the maximum per session video quality rate was 5Mbps. Thus, all sessions running at max quality rate would not be possible.

With regard to the T parameter, values between 1.6 and 2.5 sec with increments of 0.1 sec were available for use. This differs to some extent from the scenario studied in previous simulations [START_REF] Villa | Improving perceived fairness and QoE for adaptive video streams[END_REF] where increments of 0.01sec were available, but was the closest approximation the equipment used allowed for. The following cases were then considered, whereas the first is the reference point (Microsoft Smooth Streaming).

Results

The results are presented using a graphical view of the sample five-number summaries: the smallest observation, lower quartile, median (and mid 50% samples), upper quartile, and largest observation. The samples come from the measurement intervals as defined in section 3.

The samples for each interval are sorted and then grouped across all intervals according to their order. Statistics are then computed for a specific metric based on the grouped samples. This gives a view on the studied metrics to appear in a sorted manner from the worst to the best performing session, which implicitly also presents the differences between the sessions in a good way.

Average Session Rate

The distribution of average rate samples for the 5 competing sessions in the case of changing the fixed T value from its default value, to a higher or lower is presented in Fig. 3. The shared access capacity is 10Mbps.

The results show that the effect of changing the fixed T value to a lower or higher value does not have significant effect on the average session rate distributions. The sessions appear to spend most of their time at quality levels 1500Kbps/2000Kbps, and the best/worst performers are approximately within the same bounds as for the default case (T=2.0). The distribution of average rate samples for the competing sessions in the case of changing the fixed (and equal) T value from its default value, to either a unique T value or a random T value per session is presented in Fig. 4.

The results show that a unique or random T value give distributions for the best performers with lower medians and for the worst performers it gives higher medians.

The spread of the median part of the distributions are also smaller. Considering also the outliers in the distributions, it appears that the unique T is better than the random T approach.

Session Quality Reductions

The distribution of quality reduction samples for the competing sessions in the case of changing the fixed T value from its default value, to a higher or lower value is presented in Fig. 5. The results in Fig. 5 show that changing the fixed T value to a lower or higher value has a logical effect on the frequency of quality reductions. With a lower T value, we get more reductions and with a higher T value we get less. This makes sense as the lower T value sessions have the opportunity to change quality level more frequently than higher T value sessions.

The distribution of quality reduction samples for the competing sessions in the case of changing the fixed (and equal) T value from its default value, to either a unique T value or a random T value per session is presented in Fig. 6. The results in Fig. 6 show that the method of either using a unique or random T value give distributions for the best performing sessions with lower medians, and higher medians for the worst performing ones. The difference in medians for the best and worst performing sessions is higher for both the unique T and random T cases. However, the absolute values are small. In all cases, the number of quality reductions per minute is mainly between 1 and 3. Thus, the change is not considered significantly negative.

Session Fairness

The two metrics studied in the measurements are both relevant measures for intrasession fairness. The average rate metric is the traditional approach, where the optimal case is considered as the one where each session gets an equal share of the available bandwidth. The quality reduction metric is not so commonly used as a measure of fairness, but we have presented this as a candidate component of perceived fairness in our earlier work [START_REF] Villa | Improving perceived fairness and QoE for adaptive video streams[END_REF]. Based on this, we use both these metrics as basis for our evaluation of whether our suggested method of improving fairness for competing adaptive HTTP video streams is effective.

The measurement presented in section 4.1 and 4.2 were for the specific access capacity of 10Mbps as the shared resource for which the sessions as competing. In the following we present combined results including the access capacity levels of 15Mbps and 20Mbps.

In Fig. 7 an average rate fairness view is given by the spread of medians for each method (Unique T, Fixed T, Random T) at the three different access capacity levels. It is desirable to have a small difference between the median of the best performer and the worst performer, and also that they are close to the available quality level representing the optimal fair share. The capacity levels used in the measurements were chosen so that there would always be a valid quality level for the fair share as indicated in the figure. The results in Fig. 7 show that for both the unique T and random T methods a significant improvement in intra-flow fairness is achieved. The improvement is highest at the two lowest capacity levels where the best/worst performer median difference is reduced by more than 50% while remaining close to the optimal fair share. For the highest capacity level the improvement is lower but still between 20-30%. Looking at fairness among the sessions from a quality reduction per minute point of view, the Max-Min median difference for the unique T, fixed T and random T methods are very close to each other. Therefore, it does not seem as if the significant improvement in average rate fairness come at the expence of stability in general or increased differences among the sessions.

Conclusions

The results from the measurements clearly show that the suggested method has a positive effect on fairness among competing adaptive video streams in terms of reducing the difference in average rate per session among competing sessions, without increasing the amount quality reductions significantly. For the two alternative approaches for setting the T value (unique or random) the results are very close to each other, but the unique T approach are slightly better and at the same time a less demanding approach than the random T approach.

A potentially relevant aspect not included as a variable parameter in the measurements is the significance of granularity in video quality levels. Intuitively, having a fine granularity would be idealbut again this would increase production cost in terms of time and storage requirements.

The value of the findings should be considered most relevant for adaptive HTTP video streaming solutions which embed similar characteristics to the one used in the measurements from Microsoft, but also other adaptive services with a periodic and burst oriented nature. In terms of applying the findings to a real life solution, this is possible to do in different ways. One could of course make all video streams available with a range of different segment sizes and then communicate through the initial session manifest file [START_REF] Zambelli | IIS smooth streaming technical overview[END_REF] which one a specific client should use. However, this would be rather demanding from a content storage perspective. Alternatively, one could apply different segment sizes for different video streams and then get much of the same effect assuming that competing streams are not the exact same video stream. This is considered as a likely scenario for users in a home network, where users typically are somewhat different in terms of preferred content. This approach also has a benefit in terms of that it does not require duplication of the content and thereby no increase in storage requirements.

Future Work

For further enhancements of the performance for competing adaptive HTTP video streams it is likely that one should consider making available bandwidth estimations not only based on the data sent during each burst period, but also have some probing done during the idle periods. Looking closer into the potential effect of introducing some degree of memory in the algorithms controlling the adaptive streams may also provide interesting results. These issues are part of our planned future work, as well as making an integrated analysis of the suggested method using updated results from the earlier developed simulation model [START_REF] Villa | Improving perceived fairness and QoE for adaptive video streams[END_REF] together with measurement results.

Acknowledgements

The reported work is done as part of the Road to media-aware user-Dependant self-aDaptive NETWORKS -R2D2 project. This project is funded by The Research Council of Norway.

Fig. 3 .

 3 Fig. 3. Average Rate at 10Mbps and T=1.6/2.0/2.4

Fig. 4 .

 4 Fig. 4. Average Rate at 10Mbps and T= Unique/2.0/Random

Fig. 5 .

 5 Fig. 5. Quality Reductions at 10Mbps and T=1.6/ 2.0/ 2.4

Fig. 6 .

 6 Fig. 6. Quality Reductions at 10Mbps and T= Unique/2.0/Random

Fig. 7 .

 7 Fig. 7. Average Rate Fairness

Table 1 .

 1 Video segment request intervals used in experiments

	Fixed T	T=2 sec	default value
	Fixed T	T=1.6 sec	Lower than default
	Fixed T	T=2.4 sec	Higher than default
	Unique T	T 1 =1.6, T 2 =1.8 T 3 =2.0 T 4 =2.2 T 5 =2.4 Each session different
	Random T T i =Random{1.6-2.5}, steps of 0.1	Random select
	In order to support the objective of validating the effect on fairness among the
	competing streams, both per session average rate and average number of rate
	reductions per minute were collected.

Client MP Event Reports Adaptive Video Streaming Log server for MP reports from client

Table 2 .

 2 Quality Reductions view on Fairness

		10Mbps	15Mbps	20Mbps
	Median	Max-Min	Max-Min	Max-Min
	UniqueT	1,60	1,28	1,20
	FixedT	0,84	1,08	0,64
	RandomT	1,44	1,08	1,04


Ákos Milánkovich
email: milankovich@hit.bme.hu

Károly Lendvai
email: lendvai@hit.bme.hu

Sándor Imre
email: imre@hit.bme.hu

Sándor Szabó
email: szabos@hit.bme.hu

Radio Propagation Modeling on 433 MHz

Keywords: Radio propagation model, 433 MHz, smart metering, positioning

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

We are accustomed to use various wirelessly communicating devices, which possess different transmission properties according to their application areas. There are devices operating at high bandwidth in short range, but can not percolate walls. On the contrary, other devices can penetrate all kinds of materials for long distances, but operate on lower bandwidth.

The transmission properties of these various technologies -beyond transmission power and antenna characteristics -are principally determined by the operating frequency range of the system. In addition, the operating frequency determines the amount of attenuation for the technology, caused by different media.

The ability of calculating the signal strength in a given distance from the transmitter is severely important in case of network planning, because such a model helps us to determine where to place the devices, so that the system operates properly. Another typical application area of propagation models is positioning. Having the information of visible transmitters' signal strength, the receiver can deduce its position.

For most of the widely used frequency bands there are different, usable propagation models, but these are not directly applicable for the 433 MHz ISM frequency, which has beneficial propagation properties in case of 1-2 kilometer range and low bandwidth systems, like sensor networks. This frequency can be advantageous for smart metering and environmental monitoring systems.

This article introduces radio propagation basics, then analyses available outdoor and indoor propagation models. Based on our research and measurements, a proposed propagation model is presented for 433 MHz in both outdoor and indoor conditions, applicable for scaling sensor networks, smart metering systems and for use in indoor positioning.

Radio Propagation

The quality and reliability of a connection depends on many parameters, among those factors the received signal strength is the most important. The packet loss and packet corruption is less likely on proper signal strength, if other destructive factors, like interference are minimal.

ℎ = ℎ + -
The transmission strength and gain values are depending on the antenna and the allowed radio regulations. The losses are site specific, but they can be predicted by models. The types of propagation models are the following:

• Empirical models are based on measurement data at various sites. According these measurements they provide a simplified general model (only using a few parameters), but not very accurate. • Semi-deterministic models are based on empirical models and use deterministic aspects, which are computed based on the site they are applied to. • Deterministic models are site-specific, they require enormous number of geometric information about the site, they are complicated (use many parameters and computations), but accurate.

The most of the radio propagation models are empirical, because of the impossibility of taking every possible factor of propagation into account in case of different complex scenarios. However, simplifications can be made, but the model has to be developed based on enough amount of collected data. Radio propagation models do not describe the precise behavior of a link, rather, they predict the most likely behavior according to the scenario. The path loss consists of propagation losses caused by the natural expansion of the radio wave front in free space (usually shaped as an ever-increasing sphere), penetration losses (also called absorption losses), diffraction losses (the wave is obstructed by an opaque obstacle), losses, caused by multipath effect (simultaneous paths arriving to the receiver), interference, and also losses caused by other phenomena.

The propagation models can also be distinguished by the type of environment they are valid.

The following propagation models are well known and used in telecommunications.

The models are presented based on the research of [START_REF] Seybold | Introduction to RF propagation[END_REF]. However these models are not applicable for 433 MHz frequency, they form good base for our proposed indoor and outdoor models.

Outdoor propagation

Outdoor propagation models are mainly developed for cellular communications purposes. Mobile companies required models to help them determine where to place their base stations. The radio signal in an outdoor environment is determined by the free path loss, the station heights and the canyon effect of the streets. The most common outdoor propagation models for urban areas are the following.

Young. The Young model [START_REF] Parsons | The Mobile Radio Propagation Channel[END_REF] was built on the data of 1952 in New York City, which is limited. The model is ideal for modeling the behaviour of cellular communications in large cities with tall structures. This model is valid in the frequency range from 150 MHz to 3700 MHz. The mathematical formulation for Young model is: Okumura. The Okumura model [START_REF] Blaunstein | Radio Propagation in Cellular Networks[END_REF] for Urban Areas is a Radio propagation model that was built using the data collected in the city of Tokyo, Japan in 1960. The model is ideal for using in cities with many urban structures but not many tall blocking structures. The model is purely empirical and served as a base for the Hata Model. Okumura's model prediction area is divided into terrain categories: urban, suburban and open areas. The model for urban areas was built first and used as the base for others. However, the application of all the correction factors is difficult. The Okumura model is formally expressed as:

= ! ! ℎ ! ℎ ! !
= !"#$ + !" -H ! -H ! -Σ !"##

Radio propagation modeling on 433 MHz

Where: L = Median path loss in dB, !"#$ = Free Space Path Loss in dB, calculated as:

!"#$ = 20 log !" + 20 log !" + 92.45 f = Frequency in GHz, !" = Median attenuation in dB, H ! = Mobile station antenna height gain factor in dB, H ! = Base station antenna height gain factor in dB, !"## = Correction factor gain (such as type of environment, water surfaces, isolated obstacle etc.).

Hata models. The Hata Model [START_REF] Seybold | Introduction to RF propagation[END_REF] for Urban Areas, also known as the Okumura-Hata model for being a developed version of the Okumura Model, is the most widely used radio frequency propagation model for predicting the behavior of cellular transmissions in built up areas. This model also has three varieties for transmission in urban, suburban areas and open areas. This model is suited for both point-to-point and broadcast transmissions and it is based on extensive empirical measurements taken. Frequency is valid from 150 MHz to 1500 MHz. Mobile Station Antenna Height: between 1 m and 10 m. Base station Antenna Height: between 30 m and 200 m. Link distance: between 1 km and 20 km. The Hata Model for urban areas is formulated as following: = 69.55 + 26.16 log !" -13.82 log !" ℎ ! -! + [44.9 -6.55 log !" ℎ ! ] log !"

For small or medium sized city,

! = 0.8 + (1.1 log !" -0.7)ℎ ! -1.56 log !"
For large cities, COST 231. The COST 231 model [START_REF] Report | GENERATION SYSTEMS COST 231[END_REF] in an enhanced version of the Hata model with the 1800-1900 MHz included. This model consists of three components: the Free Space model, taking the general attenuation between Base Station (BS) and Mobile Terminal (MT) into account; one over rooftops, accounting for the multiple diffraction on the rooftops of the buildings in between the BS and the street where the MT is located; and the inside street one, considering the propagation from the rooftop to the MT, where the walls form a canyon. The second component, and this general approach, originated from the research group led by Henry Bertoni, while the third is taken from Ikegami et al., The development of the COST 231 involved the measurement campaigns, performed by several groups participating in the project, in several European cities. The model was finalized in 1991. Nowadays, the model still needs improvements [START_REF] Luis | A View of the COST 231-Bertoni-Ikegami Model[END_REF], [START_REF] Mardeni | Optimised COST-231 Hata Models for WiMAX Path Loss Prediction in Suburban and Open Urban Environments[END_REF]. The COST-Hata-Model is formulated as: = 46.3 + 33.9 log !" -13.82 log !" ℎ ! -! + 44.9 -6.55 log !" ℎ ! log !" + C Analysis of outdoor propagation models. For further analysis, the Young and Okumura model was omitted. The Young model was used with a clutter factor of 100 and failed to provide accurate values for distances smaller than one kilometer. The Okumura model was omitted, as the Hata model is its extended version. The Hata Urban and the COST 231 models were calculated at f=433 MHz, and with ℎ and ℎ = 1 meter. This setting modifies the models' ability to take canyon effects into account. However, 433 MHz frequency is not suitable for cellular-like ISM band). Possible applications, like positioning or smart metering use the sensors in near to the ground (height is less than 5 meters). The Hata Urban CH parameter is set according to large cities to 1.113. The COST 231 model's C correction factor was set to zero, as the measurement was not at a metropolitan area. The Hata Suburban and Open models are derived from the original Hata Urban model and provide no further accuracy in this case. The previously described models were applied to our measurement site, which took place in a suburban area in Hungary, at (46°44'5.47"N, 17°32'10.54"E). One of the sensors was placed next to the electricity meter (marked as meter), the other is placed at the marked positions. The signal was lost at the distance of 354 meters at marker M. The map of the measurement scenario is presented on Figure 1. Our measurement was conducted with Texas Instruments CC1101 radio module [7] on 10 mW power, at the height of 1 meter, and with no additional amplification on the standard λ/4 antenna. All the path loss values of the models are subtracted from the original CC1101 signal strength, which is calculated as 14.3 dB to get the result of signal strength. The results are calculated by 5 measurement values as the following: omit the lowest and highest values and the mean of the remaining 3 values is the result. The measured and the calculated signal strengths are summarized in Table 1. The Hata and COST 231 models are not significantly different in their structure. Both consider the same parameters only some constants are modified. The comparison diagram of the models for the suburban area is presented on Figure 2. The results show that the summed square errors are around 300 for both the Hata and the COST 231 model, the latter is slightly less. Our proposed outdoor propagation model, which is presented in the next section had about half the error than these models. Also the error mean is significantly less. The minimal and maximal errors however are roughly the same. The maximal error occurs for all models at marker F, which means, that there might be a considerable obstacle.

! = 8.29(log !" 1.54ℎ ! ) ! -1.1 , if 150 ≤ ≤ 200 3.2(log !" 11.75ℎ ! ) ! -4.

Marker

Dis

Proposed outdoor propagation model

Our measurements did not show significant difference between the Hata and COST 231 models (the latter is based on the Hata model). We decided to take the COST 231 as the base for our outdoor model, because it performed a little better. For the possible application areas of 433 MHz ISM band (smart metering and positioning), the height of the nodes is usually less, than 5 meters. Our calculations confirmed, that when using the models at 5 meter base height, they tend to underestimate path loss. The models were the most precise at the height of 1 meter.

Remark: The height of the mobile station only altered the mobile station gain factor component.

Both Hata and COST 231 models consider the heights logarithmically, which means, that if the height is 1 meter, then the logarithmic expression is 0. This enables to simplify the COST 231 model by omitting the use of the height factor and the calculated expressions with it. At 1 meter, this does not modify the results, we get the same. After stripping the model of the base station height factor, the path loss is calculated as:

= 46.3 + 33.9 log !" 433.92 -! + 44.9 log !"

The abstracted version of this formula is:

= ! + log !" -! + log !"
The ! value contains the mobile station height, which in case of 1 meter is -1.1. This can be contracted with the ! parameter.

= + log !" + log !"

Radio propagation modeling on 433 MHz

This model has the following parts: log !" is the frequency dependent part, log !" is the distance dependent part and the parameter is the clutter factor for the site. To determine the exact value of the α, β, γ parameters, the methods of Nonlinear Programming [START_REF] Bertsekas | Nonlinear Programming[END_REF] were employed. The objective function was to minimize the summed square error by the measurement. Formally expressed, as:

min ( -! !"" !"#$%&"!"'( !"#$%&
The α, β, γ parameters were constrained to be positive.

The GRG Nonlinear algorithm [START_REF] Abadie | The GRG Method for Nonlinear Programming[END_REF] Remark: The first two components can be summed, if the frequency is fixed. This formula scored 170.64 of summed square error calculated by our measurements, which is about half of the Hata and the original COST 231 model. Although this result is optimal for this particular measurement site. To create a general empirical outdoor model, more measurements are needed and the proposed method can be applied to fine-tune the parameters.

Indoor Propagation

Radio propagation in an indoor environment is different from outdoor propagation, because multipath fading is much more present and line of sight propagation is limited. In addition, in indoor environment the range is less because of the various obstacles. In this case, signal consists of reflected, diffracted and scattered waves.

ITU indoor model. The ITU indoor model [START_REF]Propagation Data and Prediction Methods for the Planning of Indoor Radiocommunication Systems and Radio Local Area Networks in the Frequency range 900 MHz to 100 GHz[END_REF] is a modified power law that uses empirical building data to predict the path loss. The ITU model also provides a model for the impulse response of the indoor channel to account for delay spread, again using empirical data.

The ITU indoor path loss model is formally expressed as:

= 20 log !" + log !" + ! (n) -27.54
Where: f = Frequency of transmission in MHz (in the range from 900 MHz to 5.2 GHz), N = Empirical distance power loss coefficient for residential, office and commercial areas, n = Number of floors between the transmitter and receiver, ! (n) = Empirical floor loss penetration factor, dependent on the number of floors the waves need to penetrate (ranging from 1 to 3) for residential, office and commercial areas.

Log-distance path-loss. The Log-distance path loss model [START_REF] Rappaport | Wireless Communications Principles and Practice[END_REF] is another sitegeneral model with a modified power law with a lognormal variability, similar to lognormal shadowing. The Log-distance path loss model is frequency independent, and it is based on an initial measurement, which is not always available. In that case, the theoretical free-space path loss is calculated to set the model curve to the proper gradient.

= !"# + log !" ! + !
Where:

!"# is the path loss at the reference distance, usually taken as (theoretical) free-space loss at 1 m, N/10 is the empirical path loss distance exponent, ! is a Gaussian random variable with zero mean and standard deviation of ơ in dB.

There are also foliage, terrain, and sky-wave propagation models, but they are not relevant in the case of positioning.

Analysis propagation models.

For the calculation of the ITU indoor model the N parameter (empirical power loss coefficient) was set to 33 according to [START_REF] Rappaport | Wireless Communications Principles and Practice[END_REF] Table 2. The n (floor indicator) parameter was set to zero (A, B), 9 (C, D) and 19 (E, F) according to floor distance.

For the calculation of the Log-distance path loss model, the !"# parameter is set to 14 dB according to our measurement at point A as the reference path loss. The N parameter is set to 30 and ! is set to 11.5 (calculated from the ơ of 7) according to Table 4.6 from [START_REF]Propagation Data and Prediction Methods for the Planning of Indoor Radiocommunication Systems and Radio Local Area Networks in the Frequency range 900 MHz to 100 GHz[END_REF].

Remark. If the parameter N was set to 40, the results were much better, reaching a final summed square error of 370. The previously described models were applied to our indoor measurement site. The measurement took place at the I building of BUTE in Hungary (47°28'21.69"N, 19°3'35.97"E). The measurement scenario is presented on Figure 3. This measurement was also conducted with Texas Instruments CC1101 radio module on 10 mW power with no additional amplification. This example calculation for this particular measurement scenario showed, that the empirical values used in each model are not optimal (generalized parameters are usually sub-optimal). Both models had the summed square error around 700. Our proposed model produced only 7.929 for the summed square error. Also the error mean by the measurements and the maximum error (marked with red) is significantly less. The comparison between the models is presented on

= log !" + +
Where, is the distance dependent scale factor, is the general clutter factor, and is the floor/wall parameter. The constant is depending on the number of walls or floors the signal has to penetrate. In this model, 30 cm ferro-concrete walls are considered as one unit. Walls and floors are treated equally, because the antenna loses signal strength in vertical dimension quickly. According to Figure 3, the number of walls in case A and B is 0. In case C and D, the obstacle class is 1, in E and F it is 2, as there are two walls between the nodes. The constant values of , and were determined by NLP GRG algorithms: = 40.447, = 27.029. The values of are depending on obstacle classification and summarized on Table 3. Our model scored 7.929 in summed square error, which means it fits our measurement curve (Figure 4) visibly well. This score is two orders of magnitude better, than the original ITU indoor and Log-distance path loss models. Similarly, as in the outdoor model, in this indoor case, more measurements are needed to fine tune the parameters and create a general indoor propagation model for 433 MHz based on the proposed methods. Moreover, our model is specially developed for 433 MHz, while other models are supporting a wide range of frequencies, which makes them less precise for a particular frequency.

Obstacle class parameter Marker on

Conclusions

During our research we collected the factors and their properties that affects radio propagation, then analyzed the functioning of indoor and outdoor models, especially the Cost 231 and ITU indoor models. Afterwards based on the models and our measurements we developed an indoor and outdoor propagation model optimized for 433 MHz and compared the error with other models. The proposed model performed significantly better than others in the inspected environment. The exact values can be studied on Table 1 and2.

Future work has to be done for refining our model, by many measurements in various environments. Using the proposed method of this article the model will be usable more generally. The presented models of this article can be applied for scaling sensor networks and smart metering systems, or for indoor positioning.

  loss in dB, ! = Gain of base transmitter in dB, ! = Gain of mobile transmitter in dB, ℎ ! = Height of base station antenna in meters, ℎ ! = Height of mobile station antenna in meters, d = Distance in kilometers, = Clutter factor. These parameters are defaults in almost every model. If no further explanations are give, the parameters are considered to represent the default meanings as above.

  97 , if 200 < ≤ 1500 Where: ! = Antenna height correction factor. d = Distance between the base and mobile stations in kilometers.

= 0 3

 3 Where: L = Median path loss in dB, f = Frequency of Transmission in MHz (valid from 1500 to 2000 MHz), ! = Mobile station Antenna height correction factor as described in the Hata Model for Urban Areas.

Figure 1 -Figure 2 -

 12 Figure 1 -Outdoor measurement map

Figure 3 -Figure 4 -

 34 Figure 3 -Indoor measurement scenario

Table 1 -

 1 Outdoor measurement and calculations

		-tance (km)	Hata Urban (dB)	Diff	Cost 231 (dB)	Diff	Pro-posed (dB)	Diff	Measured (dB)
	A	0.192	-93.178	8.178	-90.342	5.342	-90.50	5.502	-85
	B	0.149	-88.234	5.234	-85.397	2.397	-86.62	3.624	-83
	C	0.077	-75.361	2.361	-72.525	0.475	-76.52	3.525	-73
	D	0.019	-48.074	5.926	-45.237	8.763	-55.12	1.118	-54
	E	0.079	-75.861	2.139	-73.025	4.975	-76.92	1.083	-78
	F	0.107	-81.777	9.223	-78.941	12.059	-81.56	9.442	-91
	G	0.195	-93.480	0.520	-90.644	3.356	-90.74	3.261	-94
	H	0.266	-99.535	1.535	-96.699	1.301	-95.49	2.551	-98
	I	0.305 -102.203	5.203	-99.366	2.366	-97.58	0.582	-97
	J	0.336 -104.090	4.090	-101.254	1.254	-99.06	0.937	-100
	K	0.289 -101.152	5.152	-98.316	2.316	-96.76	0.758	-96
	L	0.316 -102.894	6.894	-100.057	4.057	-98.12	2.124	-96
	Σsquared error and error mean	345.1	4.705	323.42	4.055	170.64	2.872	0

  provided the following results for the parameters: =46.614, =31.635, =35.224 As a result, the proposed formula is: = 46.614 + 31.635 log !" + 35.224 log !"

Table 2 .

 2 The models are compared on a diagram on Figure4. Our proposed indoor propagation model is presented in the next section.

	Mar-ker	Dis-tance (m)	ITU indoor (dB)	Diff	Log-dist. (dB)	Diff	Proposed (dB)	Diff	Measure-ment (dB)
	A	1	-10.908	3.092	-25.500	11.500	-12.729	1.271	-14
	B	25	-52.846	10.960	-67.438	0.562	-69.271	1.271	-68
	C	30	-64.222	17.347	-69.813	16.186	-84.223	1.777	-86
	D	3	-34.222	6.347	-39.813	2.186	-43.777	1.777	-42
	E	6	-53.253	14.413	-48.844	21.155	-70.000	0	-70
	F	40	-77.970		-73.561		-103.324		No signal
	Σsquared error & error mean	678.599	10.432	714.648	10.318	7.929	1.219	0

Table 2 -

 2 Indoor measurement and model comparison

Table 3 -

 3 Obstacle classification


Jakub Marszałkowski
email: jakub.marszalkowski@cs.put.poznan.pl

Prototype of high performance scalable advertising server with local memory storage and centralised processing

Keywords: internet advertising, ad server, performance

Advertising servers play an important role in the entire contrary e-business. In this paper an approach for a high performance ad server is proposed. A prototype of a new architecture is presented: system achieving scalability by multiplication of ad servers with separate local memory storage and single managing server for entire cluster of those, providing data processing and ads preparation. The paper includes benchmarks of alternate technologies possible at the design stage, results of the stress tests of the prototype, as well as the data from its performance with real web traffic. Limitations of the proposed solution are discussed. Although the prototype is created on a specific platform, all technologies used are widely available or have replacements on other platforms, granting generality to the proposed solution.

Adserver

Advertising server or ad server is a system specialised in serving advertisements. It operates by receiving HTTP request and sending appropriate file to client terminal [START_REF] Langheinrich | Unintrusive customization techniques for web advertising[END_REF]. Ad server can provide many additional functions, e.g. use of business rules for ad serving, tracking of internet user and/or web pages and targeting ads with this data, income optimisation based on earlier results, dynamic creation of ad units, calculation of statistics of users and/or pages, and many more. Moreover, providing ads as quickly and foolproof as possible is of greatest importance. Advertisements loading too long will not be noticed by user, and cannot sell [START_REF] Charlton | Eight second rule for e-commerce websites now halved[END_REF] [START_REF] Kohavi | Online experiments: Lessons learned[END_REF].

There are numerous research papers with concern in ad servers subsystems providing optimisation or targeting. Most up to date surveys of these are offered by [START_REF] Hunter | Pricing banner advertisements in a social network of political weblogs[END_REF] and [START_REF] Boskamp | Maximizing revenue with allocation of multiple advertisements on a web banner[END_REF]. This paper will be dedicated to the matter of ad server performance. Proposed solution is designed to work in a single HTTP request model: client receives from ad server a single file with personalised content. This can be a dynamically created graphic file, like a banner containing some of the page usage statistics, as offered by numerous rankings and services providing statistics measurement [START_REF] Marszałkowski | The importance of advertising exchange for marketing browser games[END_REF]. Alternatively it can be JavaScript code, with some personalised variables included, like applets showing how many users read or liked an article. Graphical look of the last one can be either HTML/CSS generated or raster image embedded in JS with base64-encoding [START_REF] Mclaren | Embedding base64 image data into a webpage[END_REF]. If an additional image file has to be loaded by JS code, it will be assumed, that it comes from a separate static content server and is easily cached by browser. This takes it out of scope of this paper.

Efficient techniques used for serving static files, without server side scripts and Database Management System (DMBS ), cannot be used for ad serving. These disallow inclusion of page usage statistics or user specific variables into ad code, as well as gathering statistical data. For ad serving on each request a script must be run that will communicate with some data storage twice: to read personalised ad data and to write data of this event for statistics gathering. Efficient method of solving this problem is proposed in this paper.

For the prototype realisation, most popular open source platform LAMP [START_REF] Lawton | Lamp lights enterprise development efforts[END_REF] was selected, although ideas presented can be used on any platform. All tests were performed on computer with Intel Pentium Dual E2180 2.00GHz processor and 2GB RAM operating under FreeBSD v8.1 64 bit, that also serves as hardware for the prototype. As HTTP server Apache v1.3.42 with PHP v5.2.14 was used. DMBS used was MySQL v5.1.49.

System architecture

The proposed architecture is presented in Fig. 1. Its part of greatest importance is the ad serving component, the only one that communicates with the client supposed to receive an ad. This component is using two local storage systems as described earlier: ads storage and stats storage. The managing component is working on the statistical data from ad servers and other data from the main database. It generates the ad codes for serving, and sends them to the feeder component that places them in the ad servers local storage. Aside of this part, there can be a website, making use of the gathered statistical data, or being a back-end for ad server, allowing to set ad campaign parameters.

Such a structure offers good scalability, where more network traffic can be covered by introducing an additional cluster of several ad servers with single managing server. For this, a load balancer that directs users to the specific ad servers according to IP addresses, will be also necessary. "Servers" in this architecture can be separate machines, virtual machines or cores of a processor and in the low end scale even processes multitasking within single core. In the last, managing component can contain the feeder within itself and will be separated from ad servers rather by manner of time, for example working for a second every minute.

Ad serving component

Ad serving component is separated from the main database. For best performance both of its storage systems should be RAM operating. In case of building clusters of ad servers, machines running them do not need hard drives at all. As both storage systems differ in requirements, it is possible that separate technologies should be used to serve them. Ad serving component performance is achieved by simplicity, its algorithm, almost without simplifications, could be like this:

1. From ad storage fetch ad code appropriate for client or web page, as received in HTTP request. 2. Send code of graphic file or script with proper HTTP headers. 3. Write data of this event to the stats storage.

The most important refinement here is that ad serving component assumes that appropriate ad code always is in ad storage. Memory serves as storage, not as cache. Common solutions work oppositely. Facebook code [START_REF] Nealan | Facebook performance caching[END_REF] checks if data is in L1 cache, then in L2 cache and then even reads it from the database, at the end writing both caches. This handles many general purposes well, but not necessarily ad serving. With proposed build there are no cache misses and no pessimistic scenarios. The ad serving component never does anything except simplest possible fetching ad code and serving it. Obviously, the feeder component must be run properly to ensure that the ad code truly is in the ad storage.

Centralised processing

For the best performance, the ad serving component does not operate neither on the ad code, nor on the event data gathered for statistic. Both of these parts of the process are performed by the managing component. At best, for many events and a number of ad servers at one time. Exact functions of the managing component will vary according to requirements of website or advertisement optimisation and targeting used. The presented version is designed for website where prototype is presently tested, i.e, a ranking of websites that is generating banners with usage statistics:

1. Init, connect to DBMS. 2. Read stats storage. Erase it. 3. Do sanitization on entire input data read from stats storage. 4. Aggregate data grouping it by user visits. 5. Check in database which visits are unique. 6. Create lists of visits to insert or update. 7. Create list of member websites for stats update. 8. Read list of all member sites with their stats and scores. For each:

(a) Calculate new statistical data and ranking position. (b) Generate new ad codes where required. 9. Update the database. 10. Send all the new ad codes to appropriate feeder components.

On each step from 3. to 9. the data processing is moved from the ad server to the managing server. This allows performance gain both on such an ad server and globally. Performance gains come from aggregation of event data before processing, especially before any DBMS operations. For example with creation of a key from IP adress and web page identifier, visits can be effectively summarised under such keys. The gain there will reflect the ratio of views per visit on the operated websites.

If no DBMS is used as stats storage, writing there input data without sanitisation, can also provide a huge performance gain. Data from all events can be sanitised as one string in one operation in step 3. Otherwise for each ad served at least the IP address of a client and the referrer address should be sanitised. It was measured that such single operations was taking 40-120 µs, while only ca. 7 000 µs when done globally for 20 000 ads displayed. Another boost can be achieved, by limiting bottleneck in form of numerous operations competing for access to database: like at least two or three queries with each ad served. Presented managing component will perform four queries per run, manipulating all the necessary rows at once. Sometimes programming tricks have to be used for that. No SQL standard known to author, allows to update many rows each with different data in one query. Usually there will be need to update hundreds or thousands of rows containing visits or websites statistics. Walk-around is achieved with insertion of all update data with appropriate keys to temporary MEMORY table and then doing single update from this table.

If the ad server is using graphical banners, process of generating them takes time, especially compression of used graphical format. Thus, it should be performed as rarely as possible. Additional marker of actualisation time should be assigned for each member website according to its average popularity. There is no need to generate new banners every minute for a website that has 48 visitors a day.

Local memory storage systems

Choice of technologies for the storage systems is highly dependant on their requirements. Ad storage requires a possibility of reading the ad code quickly. Size of the ad code can differ. For graphical banners this can achieve even 100kb each, and this has to be stored for several thousands of websites. The client related data for JS file will be rather limited to hundreds of bytes, but has to be stored for tens of thousands of users. On the other hand, stats storage requires the ability to quickly add current event data to the data already stored. Sizes of stats data can vary again, for example: the IP address, website identifier and the referrer address take together 280 bytes. This data will be stored for up to hundreds of thousands of events before they get processed. Still, contemporary computers have enough RAM to provide space for all this storage.

The realisation of both reading of ad code from ad storage, and putting the event data in the stats storage require achieving a lock on the container, as there are other processes that might be writing it. For stats storage numerous separate containers can be used instead of a single one, to reduce access conflicts. Efficient method of selecting container can be for example taking last digit of IP address.

Following technologies allowing for RAM storage in PHP were identified during research: System V shared memory support (shm) [START_REF] Dovgal | Php manual[END_REF], Alternative PHP Cache (APC ) [START_REF] Dovgal | Php manual[END_REF], Memcached [START_REF] Fitzpatrick | Distributed caching with memcached[END_REF], MySQL MEMORY Storage Engine [14], MySQL Cluster [14] and tmpfs [START_REF] Snyder | tmpfs: A virtual memory file system[END_REF]. All with exception of APC can be used in numerous other programming languages.

First two are shared memory systems available for PHP. Shm allows creation of data segments of given size. To read a variable from a segment a connection by appropriate identifier must be achieved. Numeric variable identification used is important difficulty. Parameters like the website names would need to be hashed to read the stored data. Shm has no locking mechanism, usually System V semaphores (sem) would be used for this. APC is an opcode cache for PHP, preventing compilation of scripts on each request. It also offers shared memory system working simpler than the shm. There are no segments, variables are accessible by string identifiers, and it has built-in collection of locking mechanisms. From the last the fastest: spin Locks [START_REF] Shire | apc@facebook[END_REF] was taken into account. For both technologies there is no possibility to append anything to data already stored in RAM. It would require reading of entire variable and then rewriting it.

Memcached is a distributed memory caching system working in client-server model. It was widely tested and proven that locally working Memcached is slower than APC [17] [4]. Also Facebook uses APC as faster L1 cache and Memcached as slower L2 cache [START_REF] Nealan | Facebook performance caching[END_REF]. This project does not need Memcached distributed functionality, scalability is introduced by its own architecture. On this basis, finally Memcached was excluded from speed comparison. MySQL's MEMORY Storage Engine option creates db tables entirely in RAM (with few limitations). MySQL Cluster is distributed database system largely using memory storage. For both of them DBMS connection is required to access to data storage. Preliminary measurements for DBMS connection acquisition showed times unacceptable in comparison to entire data access for alternative methods (cf. Tab. 1). Thus, both technologies were excluded from more detailed tests. Please note that MEMORY tables are still used by managing component to fasten DBMS operations.

Tmpfs is a temporary file storage, working like a mounted file system, but stored entirely in RAM, namely a RAMDisc. Variable storage is difficult here, as it primarily stores files. It allows opening files in append mode and adding data at the end of the file, without reading entire contents. Tmpfs has no locking mechanism, usually file locking (flock ) would be used for this.

For every time measurement PHP function microtime() returning unix timestamp with microsecond resolution [START_REF] Dovgal | Php manual[END_REF] was used. Despite most obvious connections of technologies and locking mechanisms, shm can be used with flock, and tmpfs can be used with sem. Although semaphores are of very limited number (only 10 in FreeBSD) and thus cannot be used for locking access to ad storage containing thousands of variables. Both locking mechanisms can be used for stats storage. For flock, a handler of a file located in tmpfs was used to achieve maximum performance. Tests for ad storage were performed with real graphic banner of size of 5557 bytes. Tests for stats storage were performed with appending 280 bytes to 500kb of data already gathered. Additional tests, not included here, confirm that these choices had no matter, and choice of fastest technologies is doubtless. Results achieved are presented in Table 1.

APC's read time was absolutely unrivalled, on average it was more than twice as fast as only achieving a lock with semaphores. Things look completely different for stats storage. APC and shm had to read entire variable, large one for their standards and then rewrite it. APC also required external locking: reading and then writing such a variable cannot be considered an atomic operation. Both their times prove to be unacceptable. Tmpfs with flock unexpectedly achieved slightly better results than with sem, although flock is almost two times slower than sem. This can be explained by considering operation of obtaining file handle, flock requires it, but same is tmpfs file opening operation, and there come savings. Also for tmpfs time of performing append will be completely unrelated to capacity of data already gathered. That would increase robustness. Choices are obvious: APC should be used for ad storage while tmpfs with flock locking for stats storage.

Last matter to discuss here are limitations of volatile memory. APC is lost with Apache restart. This causes no real issue, just upon Apache start-up feeder component has to be run. Tmpfs is lost on system down, and there partial statistical data can be lost. Power failures can be easily covered by backup power solutions, seconds are needed to process entire data and store it in DBMS. For the same reason at worst statistics from dozens of seconds would be lost.

Uncommon HTTP server and DBMS configuration

Ad server, even a typical one, works differently from standard www server. It is serving web traffic of different characteristics with different files. In normal www serving, after first request for HTML file, next ones for graphic files and other includes come in a short time. To maintain such traffic standards of persistent connections were created in HTTP 1.1. In case of ad server subsequent query comes only when client loads another web page connected to this ad server. That would be at delayed or will not happen at all. First cases of stress testing performed on prototype, until default setting allowing persistent connections was disabled, lead to crash of Apache in a dozen of seconds. For the same reasons as described abovem, within the same load Adserver is operating much more unique clients, requiring more connections to get one file. Thus Apache had to be recompiled to limit of 2048 processes.

Size of files sent by ad servers can be often well known, or at least distribution of these sizes. On prototype server most used size was small graphical banners all below 5600 bytes. According to this sent buffer can be set to a size, that will fit entire such files at once. Also for small graphical files and even smaller JS scripts even size of HTTP headers sent by server can matter. Using shortest forms of server signatures can give gain of even 200 bytes. For smallest file used by prototype, being 2400 bytes large, this makes 8% difference.

In presented architecture DBMS will work only with managing component. Even if there is a website connected to it, it can have separated DBMS. Queries performed by managing component are limited, and quite specific, i.e., are very large both in number of affected rows as well as in sheer length, due to very spacious lists of parameters.

The queries will never repeat, so query cache can never score a hit. Thus it should be either turned off, or have strictly limited memory, and the queries should me marked as noncacheable. On the other hand to efficiently operate on a database with millions of visitors, indexes are necessary. And these work best if keys are read from memory cache. Also performing sorting and merging operations with such a long queries rather in RAM, requires increasing of some buffers. Finally in the prototype, settings for key buffer, both of the sort buffers and the temporary table memory limit, were all greatly increased. Exact numbers will depend on the network traffic served, as well as hardware/platform and can be found with profiling tools. All presented tweaks were made accordingly on Apache and MySQL. However, as numbers and names my be software specific, the concepts are more general. Corresponding competitive software packages usually have similar solutions, and will require similar adjustments.

Prototype performance

Ready built prototype was tested with stress tests, being most accurate ones. For it ab [1] (also know as ApacheBench) was used. Remote terminals emulation was run from second computer connected to the prototype with local network. Tests were performed with 20 000 requests for a 5619 bytes banner. The concurrency was changed to find maximum performance. Results are presented in Tab. 2.

The achieved performance is very good for the economy hardware used, but it is difficult to analyse such a result or compare it to anything. For this reasons, reference tests were performed. Firstly a 'hello world' like script was build as measure of platform maximum capabilities. It does not perform any operations, especially no reads, and only outputs same amount of data, that it has hardcoded inside. This shows that the prototype achieves 92% of platform highest possible performance. Next is a script that reads same banner from disc and outputs it. The read is actually satisfied from cache in memory. Still it achieves performance below the prototype, even without storing data in any form of stats storage. Finally script that only connects to DBMS, and then outputs hard-coded banner. It does not perform any queries to avoid a dispute on storage types or table structure. Regardless, there is clearly visible performance loss that would only increase with any additional operations.

The centralised processing is causing some delay in actuality of statistical data or user data on the ad server. There is a classic trade-off. The delay can be decreased at the cost of performance. This would demand more managing servers per ad server, allowing processing data more often. As this needs to be discussed with some numbers, please note that these will vary with regards of numerous aspects mentioned before. The claims are made on assumption that managing server has same computational capabilities as ad servers and these serve ads on maximum (peek) performance. Data from both experimental and real settings of the prototype are used.

To process statistical data every second, on average, one managing server will be needed per four ad servers. One second delay should be acceptable for enforcing virtually all of the business rules for ads display or optimisation algorithms. Oppositely, for websites offering rankings and statistics any delay measured in seconds is still way better of what is usually offered there now. Thus, one managing server can work even with as much as fifty ad servers and delay would be kept way below 100 seconds. Also strength of the architecture is that any peeks can be partially covered by increase of delay, for every use that can accept it.

The prototype is under real life testing for several months now. It provides ad serving for a website that ranks other websites, and offers them banners with statistical data. For this purpose, on mentioned earlier hardware, ad server was set together with managing server, as well as database server and website server. In this limited architecture it was serving up to 10 millions banners a day, never showing any performance problems. The managing component is processing every 120 seconds and 99.76%, of its run times are below two seconds. While running, managing component reduces ad server performance to ca. 900 req/s. Data from these tests, shows that average load is ca. half of peak load. This allows to calculate that the prototype can serve safely even 70 millions banners a day.

Summary

Presented benchmark data shows that the prototype is efficient and probably approaching the hardware/platform limits. Currently it is working on 10% of its possible workload, while author has no possibilities to stress it with more internet traffic than 10 millions banners a day.

There are not many limitations of presented architecture, and most of these were already discussed. The technologies used for the prototype are not such a limitation -of them operating system, HTTP server and database can be switched for almost any other. Only for PHP programming language there are used elements and technologies that would require finding a replacement, although this should not be difficult. The concept and the solution are quite general in their nature.

The last difficulty that should be mentioned is running ad optimisation algorithms in this ad server architecture. Putting heavy computations inside of an ad server component would reduce its performance. It can be reduced to the point where any remaining gains would be anyway covered by the computation time. This however creates interesting research area for ad optimisation algorithms that could be run on managing server and would work on aggregated data. By performing calculations for many users at same time, or using some caching techniques for partial or final results huge performance gains can occur.

Fig. 1 .

 1 Fig. 1. Proposed ad sever architecture scheme.

Table 1 .

 1 Time measurements (µs) from tests of technologies for data storage.

	measurement	avg std	measurement	avg std
	Database connection 505.0 22.6	For stats storage:
				tmpfs+flock	79	11
				tmpfs+sem	82	11
	For ad storage:			APC+sem	642 214
	APC	7.4	0.8	APC+flock	671 205
	shm+flock	58.6 41.4	shm+sem	2353 427
	tmpfs+flock	81.2	7.3	shm+flock	2389 226

Table 2 .

 2 Prototype performance results.

	Platform capabilities ('Hello world')	1919 req/s	100%
	The prototype	1761 req/s	92%
	Hard Disc read (no write)	1739 req/s	91%
	DBMS connection (no read/write)	1406 req/s	73%

This research was partially supported by a grant of National Science Centre NN519643340.


Stefan Türk

Ying Liu

Rico Radeke

Ralf Lehnert

Network Migration Optimization using Genetic Algorithms

This paper introduces the problem of communication network migration for backbone networks. Heuristic solutions for this problem can be determined by the application of genetic algorithms to the problem. A description of the system model is presented, as well as the used algorithmic approaches and optimization results. Our main goal is the optimization of migration costs, by respecting increasing demands over the migration period, while device costs per bit are decreasing. We will present Crowded DPGA as best found GA to solve the network migration problem.

Introduction

The traffic demand in optical backbone networks is expected to increase rapidly in the next years [START_REF] Cisco | Cisco visual networking index: Forecast and methology, 2008-2013[END_REF]. Also the income of network providers is not proportionally increasing to the consumption of network resources due to shrinking tariffs for end users. These forecasts demand a significant cost reduction by strategic planning optimization.

This paper describes how network operators can cope with the increase of backbone traffic in the next years. Network migration describes a technical process of upgrading and exchanging existing hardware/software (infrastructure) to another network technology, which generate calculable cost savings for its owner. The shift from classical Synchronous Digital Hierarchy (SDH) technology towards cost efficient Ethernet services is currently under way, i.e. for high data rate Internet access or global interconnection of company locations [START_REF] Michaelis | Network planning, control and management perspectives on dynamic networking[END_REF][START_REF] Türk | Network migration using ant colony optimization[END_REF][START_REF] Türk | Optimization of energy efficient network migration using harmony search[END_REF]. The introduction of Carrier Ethernet services is heavily investigated by most providers, since it promises significant cost savings and a simplification in terms of administration and maintenance [START_REF] Ciena | The value of otn for network convergence and ip/ethernet migration[END_REF].

In this paper we will focus on the heuristic solution for the specific problem formulation of the migration problem with Genetic Algorithms (GA). This meta heuristic is part of the group of evolutionary algorithms and has been effectivly used for various other optimization problems already [START_REF] Sivanandam | Introduction to genetic algorithms[END_REF][START_REF] Popov | Genetic algorithms for optimization[END_REF].

The migration is being considered as an multi-period multi layer backbone optimization problem.

The start architecture of our migration approach is an IP/ MPLS/ SDH/ DWDM network. A possible future scenario and migrated network is an IP/ MPLS/ ETH/ DWDM architecture. Node architectures are discussed in detail in [START_REF] Türk | Approaches for the migration of optical backbone networks towards carrier ethernet[END_REF].

The remaining paper is structured as follows. Chapter 2 describes our network migration model. In chapter 3 GAs are introduced and applied to the migration, followed by the presentation of a reference network in capter 4. Then our calculation results are shown in chapter 5 and a short conclusion is given in chapter 6.

Network Migration Model

Introduction

The process of network migration can be described as the stepwise insertion, replacement or removement of components in a network. In our current approach (multi layer migration) Optical Cross Connects (OXCs), Carrier Grade Ethernet swichtes and IP routers can be added to a network to satisfy the increasing demands of the next years [START_REF] Türk | Optimization of energy efficient network migration using harmony search[END_REF]. Within our migration method potential future traffic can be considered in the planning process, giving the advantage of an all period migration optimization.

Our network migration model implements for instance two important marketdriven factors: on the first hand the network demand increase (40% annual traffic increase [START_REF] Cisco | Cisco visual networking index: Forecast and methology, 2008-2013[END_REF]) and on the other hand a cost erosion of devices (20% yearly Capital Expenditures (CAPEX) decrease [START_REF] Verbrugge | Strategic planning of optical telecommunication networks in a dynamic and uncertain environment[END_REF]). The detailed description of this cost model can be found in [START_REF] Türk | Approaches for the migration of optical backbone networks towards carrier ethernet[END_REF].

Solution Model

To solve network migration using algorithms, the appropriate solution to this problem is considered as shown in fig. 1. Each horizontal row represents the information about a specific year, each vertical rank represents the information about a specific node. Every square (or solution element) is regarded as the "gene" inside the solution. It therefore contains information about one node within one year. Elements hold various information, like cost, power consumption, port cards used and slots.

Genetic Algorithms

GA optimization methods take inspiration from natural evolution and have been widely applied in various fields. In the next sections this meta heuristics will be shortly introduced and the mapping to the migration problem will be shown. Improvements in terms of algorithm performance for our specific problem will be discussed.

Classic Genetic Algorithms

Evolutionary Algorithmss (EAs) are population-based metaheuristic optimization algorithms. They are inspired by biological evolution using methods such as natural selection, crossover, mutation and survival of the fittest. GAs are the major representatives of EAs, which were firstly researched by John Holland and his student DeJong in 1975. These are capable of a fast convergence to the optimal solution, which can also be a local optimal solution. This is also the major drawback of this meta-heuristic. It can be minimized using several optimizations, discussed later in this chapter. Basic GA is characterised by the following steps shown in fig. 2a:

Encoding Individual
The given problem is encoded into a set of individuals.

Each individual represents a solution to the given problem, in our case a Migration Solution (MS) S. An individual can be regarded as a chromosome in a genetic system. Each chromosome consists of genes, which are decision variables for the migration problem. These variables decide the performance of the migration solution or the cost of the individual [START_REF] Popov | Genetic algorithms for optimization[END_REF].

Fitness Function The quality of new individuals needs to be measured. Since every S can be evaluated in terms of cost (min) and energy (min) the evolution of the algorithm can be measured using the enhancement of solutions in the designated metric with a fitness function f . For this paper we chose a cost metric to evaluate the fitness of a solution S, which is more detailed explained in [START_REF] Türk | Optimization of energy efficient network migration using harmony search[END_REF].

Selection After each generation a decision has to be made which individuals survive to the next generation. This process is usually performed using generalized replacement, steady state replacement or a fitness based decision (i.e. roulette wheel method [START_REF] Popov | Genetic algorithms for optimization[END_REF]). Two individuals S 1 , S 2 are then choosen from the new solution pool according to a randomized selection method.

Crossover Crossover means interchanging parts of two genotypes, or the exchange of several parts within two solutions. In literature [START_REF] Sivanandam | Introduction to genetic algorithms[END_REF] three types are classified:

single-point crossover: exactly one crossover between two genes two-point crossover: exactly two crossovers between two genes multi-point crossover: multiple crossovers between two genes

For the crossover of both migration solutions S 1 and S 2 we define a randomly chosen crossover point (uniformly distributed within the length of the migration solution). Whether a crossover happens or not is controlled by the crossover probability P c (see tab. 1).

Mutation Mutation can be seen as a low probability random change of genes within an individual. In the context of migration this is a random device change within a migration element. The probability of a mutation occurance is P m (see tab. 1). The process of selection, crossover and mutation is illustrated in fig. 3. Two different solutions P 1 , P 2 are selected and a crossover point is defined at migration year two and node three. Afterwards child C 2 is mutated in three elements. We only modify devices of a solution element, routing and traffic flows are not affected by mutation.

Crowding

Crowding is a GA enhancement. It is also related to nature and gives the individuals the option to "exploite different niches (resources) in the environment" [START_REF] Horn | The nature of niching: Genetic algorithms and the evolution of optimal, cooperative populations[END_REF]. The usage of crowding reduces that drawback in comparison to a classic GA, whose individuals very likely converge into one local optimum. The process is described in fig. 2b [START_REF] Yuan | Deterministic crowding, recombination and self-similarity[END_REF]. After the generation of the initial population all individuals are paired and one pair is chosen. The new offspring is generated by crossover and mutation within this pair. According to a pairing rule each child is paired with one parent to decide if the child should replace the parent.

Pairing Rule In [START_REF] Mengshoel | Generalized crowding for genetic algorithms[END_REF] pairing describes the process to decide which parent-child pairs are chosen for further improvement. The hamming distance between each child and each parent is taken as criterion for the decision. Having two parents P 1 , P 2 and two children C 1 , C 2 the pairing decision is made according to eq. 1: (b) Crowding GA [START_REF] Yuan | Deterministic crowding, recombination and self-similarity[END_REF] Replacement Rule After pairing a deterministic or randomized replacement rule is applied to the closest pairs. This phase is used to find the individual within each pair that replaces the old parent [START_REF] Mengshoel | Generalized crowding for genetic algorithms[END_REF]. After calculation of fitness values f (p) and f (c) for parent and child, replacement rules are applied determining the probability p r (that the child replaces the parent). The rule for the deterministic case is given in eq. 2. A rule for a randomized replacement is given in eq. 3 [START_REF] Mengshoel | Generalized crowding for genetic algorithms[END_REF]. These equations should be only applied to minimization problems.

if d(P 1 , C 1 ) + d(P 2 , C 2 ) ≤ d(P 1 , C 2 ) + d(P 2 , C 1 ) (1)
p r,DET =    1 if f (c) < f (p) 1/2 if f (c) = f (p) 0 if f (c) > f (p) (2) p r,RAN D = 1 - f (c) f (c) + f (p) (3)

Dual Population GA

Another approach for improving GA is the multi-population algorithm which generates two or more subpopulations, providing more individuals to maintain overall diversity. Dual-Population GA (DPGA) is one branch of multi-population GAs, which are shortly introduced in [START_REF] Park | A dual-population genetic algorithm for adaptive diversity control[END_REF]. We implemented the DPGA to solve the migration problem using a main and a reserve population (denoted M and R). M is used to find the solution with minimal solution cost. R is necessary to store individuals that strongly differs from the ones in M .

Recombination Since both populations work independent of each other (having their own crossover/inbreeding and mutation phases) a method to exchange information between both populations is necessary. A normal crossover between one individual of each population is applied here (crossbreeding). Fitness Function Since main and reserve population have different use, their candidates are evaluated using different objective functions. The fitness function for the candidates O M of the new main population f m is the same as for the classic GA. Every element x of the candidates O R of the reserve population is evaluated within this paper using the fitness function f r eq. 4 [START_REF] Park | Adjusting population distance for the dualpopulation genetic algorithm[END_REF].

min : f r (x) = d(m best , x) (4)
with: m best : best individual in M d(m best , x) : distance between two individuals m and x DPGA Workflow Figure 4 presents the steps of the DPGA, basing on Park et al. [START_REF] Park | Adjusting population distance for the dualpopulation genetic algorithm[END_REF]. Their idea is shortly explained in the following. In a first step M and R are initialized, afterwards two individuals are selected from each population: P m1 , P m2 and P r1 , P r2 . Inbreeding and crossbreeding are applied to generate the new offsprings C m1 , C m2 ,C r1 , C r2 and C c1 , C c2 . Within crossbreeding phase one of the parent individuals (P m1 or P m2 ) is chosen from M , the other (P r1 or P r2 ) is selected from R (the one with min(d(P r , P m )). Two groups O M and O R hold the candidates for the next generation of M and R. The two fittest indiviuals of each group are added to the new main and reserve population.

Crowded DPGA

Since crowding and DPGA both improve the performance of the basic GA it is our idea to combine those methods and apply them to the migration problem. Its workflow is similar to DPGA, but the inbreeding phase of M is replaced by the pairing rule already introduced in section 3.2. Taking advantage of this rule we decide if a child individual replaces a parent after internal crossover and mutation. After this step we take the candidates out of O M and O R for the new populations. We calculate the fitness of their elements and judge if the stop criterion is already reached (the original size of the main population). The best element of this new M marks the best found suboptimal solution. A more detailed description of crowded DPGA can be found in [START_REF] Liu | Network migration optimization using genetic algorithms[END_REF].

Reference Network

As reference scenario for our migration we use the German 17-node (fig. 5a) backbone network. The traffic model (fig. 5b) is based on a population investigation that has been described more detailled in [START_REF] Türk | Network migration using ant colony optimization[END_REF]. The total migration period is set to 5 years.

All our results are produced on a 64Bit Linux System with 8 Cores and 16GB RAM. The influence of main population size setting S M was investigated in 7. It can be seen that a semioptimal number of 150 elements performed best in our specififc migration scenario. This parameter has to be evaluated more in detail in future experiments using different topologies and node amounts to derive valid statments regarding network migration. Generally a too high S M forces the algorithm to work more exploratively, a too low choice tends to a low diversity and therefore to a high addiction to the initial solution.

Fig. 8 presents the dependence of crowding DPGA from mutation probability P m . We can obtain that a too high P m drops the algorithm into a more random working state, which results in a lower convergence rate. An optimal value of P m = 0.02 was found here.

A detailed cost distribution is presented in fig. 9, CAPEX, Implementation Expenditures (IMPEX) and Operational Expenditures (OPEX) values are presented for the optimal result, as well as for the different optical (OP), IP and Ethernet (ETH) basic nodes (BN) and port cards (PC). A high need for ETH equipment can be estimated for the migration years 3 and 4. The negative values for IPBNs mark the disposal of these devices, since these basic nodes can be reduced in size due to more traffic flows on layer two instead of layer three.

The best performance was achieved using the crowded GA with a main population of 150 elements, a P c of 0.7, a P m of 0.02 and a randomized selection method.

Conclusion and Perspective

Within this paper the network migration problem was solved using classic GA, crowding GA, DPGA and crowded DPGA algorithms. The modeling of the problem was presented as well as a short introduction to used algorithms and algorithm improvements. Our experiments revealed that the migration problem can be adapted to the needs of GAs and that a further investigation regarding GA is useful for migration since different algorithms behave very differently for our scenario. As best algorithm crowded DPGA was suggested, due to better convergence rate in terms of migration cost.

In the future work more scenarios (i.e. european 67-node backbone network) will be investigated to derive general statements which parameters for GA have to be used under which circumstances. Furthermore other solution mappings will be discussed, since the gene structure strongly influences the ability to manipulate solutions using crossover, mutation, etc. Calculation periods will be measured and compared to iterative figures 6 to 8. Afterwards comparisons to other meta heuristics (i.e. PSO) will be presented. A multi-objective investigation using cost and energy factors for the migration should also be provided in future.

Fig. 1 .

 1 Fig. 1. Network migration solution S

then use pairs P 1 and C 1 ,Fig. 2 .

 12 Fig.2. (a) Basic GA[START_REF] Popov | Genetic algorithms for optimization[END_REF] (b) Crowding GA[START_REF] Yuan | Deterministic crowding, recombination and self-similarity[END_REF]

Fig. 3 .

 3 Fig. 3. Visualizaion of selection, crossover, mutation and distance in the context of network migration

Fig. 4 .

 4 Fig. 4. Flowchart of DPGA [11] (one iteration)

Fig. 5 .

 5 Fig. 5. German 17 (GER-17) (a) node backbone scenario (b) and traffic model [8]NameParameter Range

Fig. 6 .Fig. 7 . 8 PFig. 8 .Fig. 9 .

 67889 Fig. 6. Comparison of different GA migration implementations

Table 1 .

 1 Heuristic parameters

	Population size of M	SM	[2,300]
	Crossover probability	Pc	[0,1]
	Mutation probability	Pm	[0,1]
	Iteration number	I	10000
	Confidence sample number C	80
	5 Results
	Figures 6 to 8 show the performance results of the German 17-node backbone
	network migration. In fig. 6 the presented algorithms are compared for the GER-
	17 backbone. A bad convergence for random optimization (RO) can be seen, GA
	and especially crowding DPGA performed best within our experiment.