Dominik Klein

Thomas Zinner

Kathrin Borchert

Stanislav Lange

Vlad Singeorzan

Matthias Schmid

Evaluation of Video Quality Monitoring based on Pre-computed Frame Distortions

A large fraction of the current Internet traffic is caused by video streaming. Due to the growing expectations of video consumers, monitoring video applications is getting more and more important for network and service providers. In a previous work, we proposed a video quality monitoring solution which utilizes the full reference SSIM metric to improve the monitoring in the network by distributing pre-computed distortion information induced by frame losses. To improve scalability, we introduced a less complex algorithm which infers the distortion for higher loss scenarios from single loss scenarios and inter-frame dependencies. In this work, we evaluate the accuracy of our algorithm by comparing it with the exact calculation of the SSIM metric for different frame loss scenarios. We further consider different high definition test video sequences and group of picture structures and investigate the influence on the accuracy of our proposed approximation.

Introduction

Among the currently popular Internet applications, video streaming is responsible for the largest fraction of the global Internet traffic and is said to keep its pace within the next years [START_REF] Inc | Cisco visual networking index: Forecast and methodology, 2011-2016[END_REF]. This trend underlines the growing importance of video streaming in current and future networks. In parallel, technologies like software defined networking or network virtualization enable the development of application-specific virtual networks which fulfill the special requirements of applications like video streaming. Virtual networks introduce new management mechanisms [START_REF] Meier | Provisioning and Operation of Virtual Networks[END_REF] to optimize the virtual network towards the hosted application but require an accurate monitoring solution to assess the effects of applied management mechanisms with respect to the perceived service quality of end customers. In [START_REF] Klein | Video Quality Monitoring based on Precomputed Frame Distortions[END_REF], we proposed a monitoring solution that uses a full reference metric to pre-compute the distortion per group of pictures (GOP) for different frame loss scenarios. This pre-computed information is used to improve the accuracy of the monitoring in the network, which infers the video quality from lost frames. In particular, video dependencies are included in our approach as they are captured by the video quality assessment (VQA) metric, in our case the structural similarity (SSIM) [START_REF] Wang | Image Quality Assessment: From Error Visibility to Structural Similarity[END_REF] metric. However, including all possible frame loss combinations per GOP introduces a large number of frame loss scenarios and hence, excessive computing power is required. To achieve a better scalability of our approach, higher frame loss scenarios are approximated by adding the distortion of single frame loss scenarios. Hence, only the distortions for single frame loss scenarios need to be pre-computed. This approach however reduces the accuracy compared to the exact SSIM metric.

In this work, we evaluate the accuracy of our solution by comparing it with the exact calculation of the SSIM metric for different frame loss scenarios. We further consider different high definition test video sequences and GOP structures and investigate the influence on the accuracy of our proposed approximation. The remainder is structured as follows. In Section 2, we discuss similar approaches. Section 3 briefly introduces our proposed monitoring framework and in Section 4, we explain the setup of the evaluation. In Section 5, we assess the accuracy of our approach and investigate the influence of different video structures. Finally in Section 6, we conclude the paper and present future work.

Related Work

The quality of experience (QoE) of consumers has several influence factors like the physical and social context, the expectation and usage history of the human user, and the technical system itself [START_REF] Schatz | From Packets to People: Quality of Experience as New Measurement Challenge[END_REF]. Despite the technical network parameters, these factors are hard to measure. Another important factor is the video quality itself and there are several monitoring solutions which try to infer the video quality from technically measurable parameters. The most simple mechanisms is to define a packet loss threshold for the IPTV service and assume the video quality as acceptable as long as the threshold is not exceeded. This technique does not take any video and content information into account. While a lost packet will produce a large error in regions with medium motion, it may produce no sizable error in regions with low motion. The mechanism introduced by Reibman et al. [START_REF] Reibman | Quality monitoring of video over a packet network[END_REF] focuses on no reference methods which estimate the video quality on network level and, if possible, on codec level. The estimation on codec level includes for instance spatio-temporal information and effects of error propagation. Tao et al. [START_REF] Tao | Real-Time Monitoring of Video Quality in IP Networks[END_REF] propose a relative quality metric, rPSNR, which allows the estimation of the video quality against a quality benchmark provided by the network. The introduced system offers a lightweight video quality solution. Naccari et al. [START_REF] Naccari | No-Reference Video Quality Monitoring for H.264/AVC Coded Video[END_REF] introduce a no reference video quality monitoring solution which takes spatio-temporal error propagation as well as errors produced by spatial and temporal concealment into account. The results are mapped to SSIM and compared to results gained by computing the SSIM of the reference video and the distorted video. All these video quality monitoring mechanisms work on no reference or reduced reference metrics for estimating the video quality. A brief overview on current research questions within the area of IPTV monitoring can be found in [START_REF] Apostolopoulos | The Challenge of Estimating Video Quality in Video Communication Applications[END_REF].

Proposed Monitoring Solution

In this section, we give a brief overview to our proposed video monitoring solution. The idea of our proposed monitoring solution is to distribute pre-computed distortion information induced by losing frames to monitoring agents in the network. The agents monitor lost frames in the video streams and utilize the pre-computed distortion information to infer the distortion of multiple frame losses within a GOP based on the distortion of single frame losses and the frame dependencies. The distortion per frame for the single frame loss scenarios and the frame dependencies are extracted on a per GOP basis during a SSIM-based video analysis prior to the video streaming process. More details to the different building blocks are provided in the following.

Precomputation of Distortion

The distortion values are computed according to the SSIM metric and we define the distortion as the dissimilarity of two frames. For each frame within a GOP, the video analysis generates a loss scenario where only this specific frame is dropped and the resulting distortion on all frames within that group is investigated. Therefore, we directly compare the undistorted image f Good with the distorted image f Bad via the SSIM method and hence obtain, how different the undistorted and distorted image are. The SSIM metric yields values between 0 and 1 and the distortion value per frame d F rame is defined in Equation 1.

d F rame = 1 -SSIM (f Good , f Bad ) ( 1 )
The distortion value per single frame d F rame hence has a maximum of 1 which means two completely different pictures. However, only I-frames are completely independent of other frames and constitute fixed pictures. All other frame types are dependent on other frames and if these frames are lost, the dependent frames cannot be decoded. Hence, a single frame can have a much higher distortion value in case a lot of other frames are dependent on this frame. To normalize the distortion per group d GOP , we divide it by the number of frames per group. To get the dependencies between the frames in a GOP, we also investigate in the above emulated loss scenarios which other frames are also distorted in the currently considered GOP if a specific frame is lost.

Calculation of Video Distortion

The distortion value is calculated per GOP and once the agent sees the next GOP in the stream, the old distortion value of the former GOP is sent to the monitoring database and the value is reset to 0 for the next group. For each lost frame per group, the monitoring agent updates the distortion value d GOP . First, the monitoring agent checks whether the lost frame is dependent on other frames. If the lost frame is independent, the agent looks up the distortion value for the lost frame d F rame and adds this value to the distortion value of the currently considered GOP (d GOP ) and the update process is finished. If otherwise the lost frame is dependent on other frames, the agent needs to check whether these frames are also lost. If the currently considered frame requires another frame which is also lost, the distortion of the current frame is already included and can be ignored. In this case, no update of the d GOP value is required. If in contrast the required frame is not lost, the distortion of the currently considered lost frame is not yet included and hence, the distortion d F rame is added to the d GOP value.

Mapping from Distortion to Video Quality

After the distortion per GOP d GOP has been calculated, the monitoring needs to map the distortion to a proper metric showing the actual video quality. For our approach, the distortion is mapped to the MOS value according to [START_REF] Wang | Video quality assessment using structural distortion measurement[END_REF] and then to the video quality according to [START_REF] Schatz | From Packets to People: Quality of Experience as New Measurement Challenge[END_REF]. There the authors have shown via subjective tests for web services that 90 % of the users already accept a fair video quality (MOS 3). A distortion per GOP d GOP ≤ 0.12 corresponds to MOS values equal or larger than MOS 3. Hence, our monitoring solution rates GOPs with a distortion d GOP ≤ 0.12 as good or accepts the video quality and rates GOPs with a distortion d GOP > 0.12 as bad or rejects the video quality.

Evaluation Setup

In this section, we first describe the test video sequences and GOP structures which have been considered for the evaluation. Second, we explain the evaluation setup and the used tools.

Test Video Sequences

In the following, we introduce the considered videos for the evaluation. The videos have been selected so that different amounts of temporal and spatial information are represented. Temporal information includes the motion between consecutive frames while spatial information includes the amount of details per single frame, as introduced in ITU-T Recommendation P.910 [START_REF] Union | ITU-T Recommendation P.910: Subjective video quality assessmentmethods for multimedia applications[END_REF]. Our evaluation was performed using free available high definition 1080p test video sequences from the Xiph.org Test Media website [START_REF]Derf's test media collection[END_REF]. The videos are listed in descending order according to the amount of temporal and spatial information and correspond to different content types such as high or low motion and high or low detail. The considered sequences are Park Joy, Ducks Take Off, and Old Town Cross. Screenshots for the three different videos are shown on the left-hand side in Figure 1.

Assessed GOP Structures

In addition to the influence of different types of videos, we also investigate how well our proposed monitoring solution behaves for different GOP structures. Therefore, we have analyzed the GOP structures currently used for live streaming of video content by two prominent German IPTV broadcasters, i.e. the German Telecom and the German public service broadcasters (ARD/ZDF). The German Telecom offers an IPTV service called T-Entertain which can be booked in addition to the DSL Internet connection. Entertain runs in a separate VLAN and provides access to various TV channels in high and standard definition quality. The GOP structure for Entertain in HD quality is M = 8, N = 64, whereas M denotes the distance between P-frames and N the distance between I-frames. Hence, for Entertain HD, there are 7 B-frames after an I-or P-frame and between two I-frames, there are 63 P-and B-frames. This kind of GOP structure reduces the amount of transmitted information but the encoding and playout order of frames is different which increases the complexity at decoder side. For the ARD/ZDF live TV stream in contrast, the GOP structure is different. There are no B-frames at all and also the length of the GOP is variable and not fixed. A possible explanation for the variable GOP length is that the length is adaptive to the video content to reduce the video bit rate. Such an approach is for example proposed in [START_REF] Zatt | Gop structure adaptive to the video content for efficient H.264/AVC encoding[END_REF]. Hence, the GOP structure for the ARD/ZDF life stream can be written as M = 1, N = variable. This kind of structure has an increased video bitrate compared to the structure with B-frames but the encoding and playout order of frames is the same.

Label Size Length

Structure IBP M=4 N=16 IBBBPBBBPBBBPBBB IPP M=1 N=16 IPPPPPPPPPPPPPPP For our evaluation, we use slightly adapted GOP structures considering the high definition video test sequences. The GOP length for both structures has been set to 16 frames and is not dependent on the video content anymore so that both structures are comparable. For the structure with B-frames, we have reduced the GOP size to 4 which results in 3 B-frames in between I-and Pframes. The resulting modified GOP structures can be seen in Table 1. For convenience, the structure with B-frames is denoted as IBP structure in the following and the structure without B-frames is denoted as IPP structure.

Evaluation Methods

For the evaluation of the accuracy of our proposed monitoring solution, we compare our approximated SSIM values with the exact SSIM values for different frame loss scenarios. The overall setup as well as the different steps during the evaluation can be seen in Figure 1. In the first step, the x264 tool [START_REF]h264/avc encoder[END_REF] is used to create a h.264 file with a specific GOP structure (see Table 1) for the three different input videos. In the second step, we use the MP4Box tool [START_REF]multimedia open source project[END_REF] and the MP4Trace tool from the EvalVid framework [START_REF] Klaue | EvalVid -A Framework for Video Transmission and Quality Evaluation[END_REF] to create a video stream which is dumped in the next step using either TcpDump [17] or WinDump [START_REF]windump/winpcap[END_REF]. To evaluate different frame loss scenarios, we create a lossy dump file in the next step by removing certain frames from the dump file. This way, we generate different dump files for loss scenarios where exactly one, two, three, or four frames are lost per GOP. This results in 16 i scenarios in case exactly i frames are lost per GOP. Evaluating all frame loss combinations results in a high number of scenarios which requires excessive computing power. Hence, we limit our evaluation to at most four frame loss scenarios and show that higher loss scenarios are not required to demonstrate the accuracy of our approach. After the different dump files have been created, we use the Etmp4 tool from the EvalVid framework [START_REF] Klaue | EvalVid -A Framework for Video Transmission and Quality Evaluation[END_REF] to reconstruct the MP4 file from the dump file and create raw video files by using the MEncoder tool [START_REF] Project | Mencoder[END_REF]. In the last step, we use the MSU tool [START_REF] Media | Msu video quality measurement tool[END_REF] to compare the lossy video file with the original video file by calculating the exact SSIM values. These values are then used as reference and we evaluate the induced error due to our approximation of the SSIM metric. Therefore, the information about the lost frames is used by our proposed monitoring solution to calculate the approximated SSIM values (see lower part of Figure 1). The approximated SSIM values are then compared with the exact SSIM values calculated by the MSU tool.

Evaluation of Video Quality Monitoring

In this section, we show the accuracy of our approach with respect to the exact SSIM metric. First, we investigate which frame loss scenarios are relevant and which higher scenarios cannot deliver a good video quality anymore. Second, we assess the influence of the different video types and GOP structures on our approach and show, how our metric can be optimized for certain GOP structures. Third, we further investigate the error due to our approximation and finally, we show the sensitivity of our approach with respect to the acceptance threshold for the video quality.

Relevant Frame Loss Scenarios

In this subsection, we investigate which loss scenarios lead to a large fraction of GOPs where the video quality is still acceptable. For these scenarios, our proposed monitoring solution needs to be accurate. For loss scenarios where a large fraction of GOPs has a high distortion and hence a very bad quality, accuracy is not that important. According to Section 3.3, our mapping rates the video quality of a GOP acceptable if the distortion per GOP d GOP ≤ 0.12.

The resulting percentage of GOPs with a distortion less than 0.12 for the three different videos is shown in Figure 2. Figure 2a shows the results for the IBP structure and Figure 2b shows the corresponding results for the IPP structure. In both figures, the x-axis shows the number of lost frames per GOP and the different colored bars denote the three different videos.

Concerning the IBP structure in Figure 2a, we see that the fraction of GOPs with acceptable quality decreases for the higher loss scenarios. This is in line with the expectations because the more frames are lost, the worse is the overall video quality per GOP. However, there are strong differences between the different types of video which can be explained due to the amount of spatial and temporal information. The Park Joy video sequence has the highest amount of information and is hence more susceptible to frame loss than the other two videos which have a higher number of acceptable GOPs in all loss scenarios. Even if four frames are lost within a GOP, about 40 % of the GOPs for the Old Town Cross test sequence still have an acceptable video quality. However, for five and six frame loss scenarios, the percentage of GOPs with good quality drops to 24.3 % and 13.32 % respectively. Hence, it would be necessary to take five and six frame loss scenarios into account. However, due to the high computational complexitiy we omit these scenarios for the video clip Old Town Cross.

For the IPP structure depicted in Figure 2b, similar observations are made. However, the fraction of acceptable GOPs is much smaller for all videos in the higher loss scenarios. Due to the absence of B-frames, the overall importance per frame is higher and hence, this structure is more susceptible to frame loss than the IBP structure. If we directly compare the number of accepted GOPs for the four frame loss scenario, we see that the IPP structure in the right figure has a much lower fraction as the IBP structure on the left figure. Overall, also for the IPP structure, it is sufficient to consider only loss scenarios where at most four frames are lost per GOP. For higher loss scenarios, our approach indicates an unacceptable video quality with a high probability.

Qualitative Evaluation of Accuracy

In this subsection, we plot our approximated distortion values against the distortion values calculated by the exact SSIM metric to show the accuracy of our monitoring solution. The evaluation does only consider loss scenarios where exactly two, three, and four frames are lost. One frame loss scenarios are not considered as for those scenarios, our approximation yields the same results as the exact SSIM metric. The results for the different video test sequences and GOP structures can be seen in Figure 3. Figures 3a-3c show the results for the Park Joy sequence, Figures 3d-3f show the results for the Ducks Take Off sequence, and 3g-3i show the results for the Old Town Cross sequence. All figures are plotted as scatter plots where the x-axis denotes the exact distortion values and the y-axis denotes the estimated distortion values. All plots also contain the 0.12 threshold lines for the estimated and exact distortion values as well as the identity line through the origin. Estimated distortion values which lie on the line through the origin perfectly match the exact distortion values.

Considering the IBP structure (see Figures 3a,3d, and 3g) for the three different videos, we see that our approach performs best for the Old Town Cross video which has the lowest spatial and temporal information. For the other two video sequences, our approximation still performs very well in the critical area around the video quality acceptance threshold of 0.12 and only deviates in the higher distortion areas. There however, our monitoring does not accept GOPs with a bad video quality or a distortion value higher than the acceptance threshold and hence, no error occurs. A different observation can be seen for the IPP structure (see Figures 3b, 3e, and3h). For this structure, our proposed approximation does not perform well and underestimates the distortion in the critical area around the acceptance threshold for all three videos. For this structure, all subsequent frames are always dependent on their precedent frames and errors in earlier frames influence all subsequent frames. Our approximation however ignores the distortion values for frames which are dependent on earlier frames (see Section 3.2) as the distortion of dependent frames is included in the distortion value of their required frame. This is a good approximation for GOP structures with minor inter-frame dependencies like the IBP structure but not for IPP structure. Hence, to improve our approach, we modify the calculation of the distortion per GOP d GOP and always add the distortion of lost frames d F rame instead of ignoring the distortion of frames which are dependent on another lost frame. This is a very simple modification to our initial metric. But for the specific use case, the results prove the viability of this approach.

Figures 3c,3f, and 3i show the results for the modified version of our approximation. With the modified approach, we do not underestimate the distortion in the critical area. Accordingly, a large fraction of the estimations lies on the identity line through the origin. For the higher distortion area, our modified approach now overestimates the distortion. There however, our monitoring does not reject GOPs with a good video quality or an exact distortion smaller than 0.12 and hence, no error occurs.

Quantitative Evaluation of Accuracy

The scatter plots in the former section give a basic understanding about how our unmodified and modified metric perform for the different videos and GOP structures. However, for a quantitative statement, CDF plots are more suitable. Hence in Figure 4 and 5, we plot the CDF for the error e between the estimated and the exact distortion values. The error e is defined as the exact distortion minus the estimated distortion. A negative error means that our proposed approximation overestimates the distortion and positive error means an underestimation of distortion. From the perspective of a network provider, a positive error is more serious because the monitoring underestimates the distortion and hence recognizes a bad video quality too late or even not at all.

Regarding the IBP structure, we again see that our proposed monitoring solution performs best for the Old Town Cross sequence. For that video, all GOPs have an error e < 0.05. For the other two videos, about 80 % of the GOPs have an error e < 0.05. However, as we have seen in Figure 3, the larger error occurs in a distortion range where accuracy is less important.

For the IPP structure, it can be seen that the unmodified approach always significantly underestimates the distortion and hence is not suitable for this structure. In contrast, the modified approach mostly overestimates the distortion and only a very small fraction of GOPs has a positive error e. The modified approach is hence more suitable for the IPP structure as the GOPs with a high negative error e have a very high distortion and are rejected anyway.

Sensitivity with Respect to Acceptance Threshold

In the former evaluation of the accuracy of our proposed monitoring solution, we have used an acceptance threshold of 0.12 for the video quality. The video quality of GOPs is only accepted if the corresponding distortion is less than this threshold. However, this threshold was chosen according to [START_REF] Schatz | From Packets to People: Quality of Experience as New Measurement Challenge[END_REF], where the authors have shown via subjective tests for web services that 90 % of the users accept a fair service quality (MOS 3). If due to new findings in future work this threshold needs to be adapted, our monitoring solution should still be accurate. Hence in the following, we investigate how the percentage of correctly classified GOPs behaves for different acceptance thresholds. The corresponding results are shown in Figure 6. The x-axis shows different values for the acceptance threshold and the y-axis shows the percentage of correctly classified GOPs. The solid lines denote the results for the IBP structure and the dashed lines denote the results for the IPP structure. For the IPP structure, only the results with the modified approach are shown. For all structures and videos, a threshold close to 0 leads to 100 % correctly classified GOPs. In that case, both metrics always reject the video quality for a GOP if the distortion is larger than 0 which is not a reasonable approach as such a monitoring would be far to pessimistic. For the chosen threshold of 0.12, our monitoring classifies about 98 % of the GOPs correctly. Only the IBP structure for the Old Town Cross sequence experiences a slightly lower classification rate of 93 %. For an increasing threshold, the classification rate for nearly all videos and structures decreases. For the IBP structure, the classification rate does not drop below 90 % which is still an acceptable result. For the IPP structure, the classification rate drops to 80 % for the Old Town Cross video. Overall, our monitoring still achieves a high correct classification of GOPs even in the higher dirstortion range of about 0.2.

Conclusion

In this work, we presented an evaluation of our proposed monitoring solution for IP video streaming services which utilizes knowledge about the video content to predict the service quality. Our solution pre-computes the distortion induced by losing frames using the full reference metric SSIM. Due to the high complexity for computing all frame loss possibilities within a Group of Pictures (GOP), we introduce a less complex algorithm which computes the distortion of multiple frame losses within a GOP based on the distortion of single frame losses and the frame dependencies. We investigate the accuracy of the introduced approximated monitoring solution for two different video streaming configurations used by German broadcasting services and the Deutsche Telekom.

Our results indicate an accuracy of more than 95% correctly classified GOPs of the proposed approximative distortion computations as compared to the correct values. At the same time the number of required computation is significantly reduced, since only single frame losses within a GOP have to be computed. Future work will focus on the comparison of the proposed solution with other monitoring approaches from literature with respect to the trade-off between monitoring costs, scalability, and accuracy. This also includes subjective user surveys which can be used as a metric for the comparison, and also to improve the accuracy of the proposed video monitoring solution.

Fig. 1 .

 1 Fig. 1. Flow chart showing the different steps during the evaluation.

Fig. 2 .

 2 Fig. 2. Number of GOPs with distortion value less than 0.12.

  Old Town Cross with IPP structure -modified.

Fig. 3 .

 3 Fig. 3. Scatter plots showing estimated distortion against exact distortion values.

Fig. 4 .

 4 Fig. 4. Error depicted as CDF for IBP structure.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Error depicted as CDF for IPP structure.

Table 1 .

 1 Considered GOP structures.

Acknowledgment

The authors would like to thank Prof. Tran-Gia for the fruitful discussion and the support in this work.


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

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

A Measurement Study of Active Probing on Access Links

Keywords: Packet Pair probing, One-Way-Delay probing, Access links

This paper presents a measurement study of two different methods for active probing of cross traffic on access links. The categories used in the study are packet pair probing and one-way-delay probing. The first approach uses measured increase in packet spacing as indicator of cross traffic presence, while the latter uses increase in one-way-delay for probe packets as indicator. These methods have been chosen because they are fundamentally different in terms of requirements, benefits and challenges. The main novelty of this paper is the presentation and discussion of measurement results from an access network using an adaptive video service as cross-traffic. The findings clearly illustrate the potential strengths of a probing method based on one-way-delay measurements, under the condition that the required timing accuracy is achieved and delay characteristics is available for the involved network path. The benefit of using Precision Time Protocol instead of Network Time Protocol is illustrated, even in networks of limited size.

Introduction

The dynamics of Internet traffic on different levels, ranging from per session, per user and up to backbone traffic aggregates is a topic of great interest in the research community. The reasons for performing such studies are diverse and so are also the techniques and methods applied. One obvious reason for studying Internet traffic dynamics on an aggregated level is the need for knowledge about how to best design and scale the future Internet as a whole. Another reason, on a lower level, is the growing amount of adaptive services on the Internet, which is characterized by their ability to change their requirements according to varying network conditions. Such services would obviously benefit from being able to obtain accurate views of different network-and traffic metrics in real-time.

Obtaining information about Internet traffic is best done by means of passive measurements performed in a non-intrusive way on the network links of interests. However, in some cases such passive measurements are not possible due to e.g. lack of access to the relevant links or involved equipment. In these cases, the use of active measurements is an alternative to consider. Such measurements are based on injecting probe traffic into the network between end-points and then study how this specific traffic is treated. Based on the findings for the probe traffic, one can then make some statements about the traffic conditions along the same path as the probe traffic followed. Examples of such statements could be related to e.g. packet loss or delay, described by basic mean value considerations or higher order statistical views.

In this paper we compare two active probing methods for estimating cross-traffic amount on access links by means of theoretical discussions and measurements in a controlled lab environment. The metric of interest describing the cross traffic amount is based on buffering time observations for injected probe traffic. These observations can then be analyzed over certain periods and used for different purposes. The methods used in our study are based on sequences of packet pairs and single packets, at different rates. The way buffering time observations are extracted for these two methods are quite different and will be further described later in this paper.

The measurement part of our study is done in a controlled lab environment reflecting a typical broadband access network, and using a high quality video streaming service as the cross traffic component. The reason for focusing on the access link part is that this is where we quite often encounter the bottleneck across a network path. The choice of video as cross traffic component is based on the growing popularity of this service type on the Internet. The structure of this paper is as follows. Section 2 provides an overview of related work; Section 3 describes the active probing methods; Section 4 presents the measurement setup; Section 5 provides the results and an analysis; Section 6 provides the conclusions and an outline of future work is given in Section 7.

Related Work

There is a lot of research in the field of active probing addressing different research questions ranging from the application layer down to the physical layer. In the context of our work, i.e. estimating the amount of cross traffic (measured by increased buffering time for probe traffic) on an access link -the most related research are found in the domain of methods for available bandwidth estimations. For this purpose there are several approaches, most of which fall into either the Probe Rate Model (PRM) or Probe Gap Model (PGM) categories [START_REF] Prasad | Bandwidth estimation: metrics, measurement techniques, and tools[END_REF]. The PRM approach is based on the principle of self-induced congestion and by this detecting available capacity, while the PGM approach uses observed inter-arrival time (IAT) variations [2][3] for probe packets to estimate the current level of cross traffic. However, the original idea of using probe packets as basis for active measurements was suggested in [START_REF] Keshav | A control-theoretic approach to flow control[END_REF] where back-to-back packets were sent to detect the capacity of bottlenecks.

The use of one-way-delay (OWD) observations [5][6] for probe packets through a network can also be used for estimating available bandwidth as per the PGM approach. However, as the computation of OWD is based on time information from different nodes in the network it has very strict requirements in terms of clock accuracy and synchronization [START_REF] Shin | Clock synchronization for one-way delay measurement: A survey[END_REF]. As described in [START_REF] Vito | One-way delay measurement: State of the art[END_REF] the main protocols for distributing clock information across as network, NTP (Network Time Protocol) and PTP (Precision Time Protocol) have different capabilities in this regard. The latter is stated to give accuracy in the order of µs, while the former in the order of ms. However, it should be noted that this depends a lot on the specific hardware and software used. In a recent work [START_REF] Kovacshazy | Performance evaluation of ptpd, a ieee 1588 implementation, on the x86 linux platform for typical application scenarios[END_REF] the performance of the Linux PTP daemon was evaluated and their findings were in line with [START_REF] Vito | One-way delay measurement: State of the art[END_REF]. What concerns NTP there are also improvements in this provided by the NTPv4 [START_REF] Mills | Network Time Protocol Version 4: Protocol and Algorithms Specification[END_REF] which could bring the accuracy down into the µs region in certain cases.

As presented in [START_REF] Hernandez | One-way delay measurement and characterization[END_REF] there are many sources of delay components along a network path and not all of them are influenced by cross traffic. This represents as source of error for all delay based probing methods.

Active Probing

The metric of interest to be measured by the active probing is amount of cross traffic present, represented by introduced additional buffering time for the probe traffic over some time interval. In Fig. 1 a simplified model for an access link as a basic queuing system is presented. The service rate λ out corresponds to access capacity (bits/s), the λ cross corresponds to the uplink capacity for the access node and V B is the configurable buffer size (bytes) for a specific access. The indicated time parameters t a and t b represents time between packets in a packet pair and time between packet pairs as sent, while t a*,i and t b*,i are the corresponding values when probe traffic is received on the client side. The t s,i and t r,i parameters are timestamps for when a packet was sent and received. In the zero cross-traffic case the client side will in theory receive the probe traffic with t a*,i = t a , t b*,i = t b and a constant t s,i -t r,i . When cross-traffic is introduced there will be time variations in the received probe traffic, caused by additional buffering time for the probe packets in the access link buffer.

When using packet pairs, the original time between the packets (t a , t b ) is assumed known by the receiver. Thus, any changes to this would be caused either by crosstraffic or fluctuations in processing load on involved network components. By calculating the difference between packet spacing as received and sent -a series of samples is produced. An important benefit of this method is that there is no need for accurate time synchronization of sender and receiver side. Another benefit is that an increasing amount of probe traffic does not lead to potentially an over-sampling scenario, i.e. the registration of a certain buffering time component more than once.

However, the method has a weakness in the sense that cross-traffic may delay the first packet in a pair, and thereby reduce the spacing between the packet pairs [START_REF] Hu | Evaluation and characterization of available bandwidth probing techniques[END_REF]. One way to handle this is to consider both packet pair spacing and the time between packet pairs by summarizing this into packet pair period samples t pp,i as given in Eq.1.

, * , * , (1)
In addition, some computation is required on the period sample time series as presented in our submitted work [START_REF] Villa | Estimating available bandwidth on access links by means of stratified probing[END_REF] in order to carry forward a time shift component to the next t a*,i or t b*,i observation. However, for the purpose of comparing the two active probing methods in this paper we have left this computational correction out. It is further important to note that for this method to be able to capture delay components higher than just the buffer output time of a single cross-traffic packet T p , it is a requirement that the arrival rate λ cross towards the bottleneck is higher than the service rate λ out . This can be seen from Eq. 2 where the maximum value for observed time between packets in a packet pair t a*,Max is expressed. * , , /

In a real life network the condition λ cross > λ out would normally apply since an access node typically is served by at least a gigabit connection and each customer connection would be in the order of tens of Mbps. One could also claim that the approach of using packet pairs has a drawback in the sense that is requires two probe packets to produce a single cross traffic sample. However, if both packet pair spacing and time between packet pairs are considered, this is no longer applicable.

When using a sequence of single probe packets it is the OWD for each packet which is used to obtain buffering time samples. The sender adds a time stamp to each packet when sent t s,i , and the receiver adds his own timestamp to the packet when received t r,i . If we then know the reference OWD during times of zero cross traffic T owd,0 , we can for each probe packet when received -compute a sample t owd,i for buffering time induced by cross-traffic.

This approach has the benefit of that each probe packet gives one cross-traffic sample, and all samples are independent. However, even though the samples are independent they may actually lead to a degree of oversampling if more than one probe packet is in the buffer at the same time. The reason is that each probe packet will be delayed according to the total amount of packets ahead of it in the buffer, even if there are other probe packets as well there. Investigation of the over-sampling issue is left for future work. Further on, as the method uses timestamps from different sources (sender and receiver) it requires a high degree of accuracy in time synchronization. The use of NTP or even PTP may not be accurate enough. The challenge of actually knowing the reference OWD when no cross-traffic is present is also a significant challenge.

Measurement Setup

In order to perform a comparison of the two active probing methods, an access network testbed was established (cf. Fig. 1). In order to minimize cross process impacts on the client and server side, both the probe generator and the probe receiver were put on dedicated nodes. In a real life, this may be more integrated at least on the client side -but this depends on the specific application.

Figure 1 Access Network Testbed

As probe traffic generator and receiver the Rude/Crude tool [START_REF] Laine | Real-time udp data emitter (rude) and collector for rude (crude)[END_REF] was used. This has the capability of generating IP packets according to trace files, describing both packet size and time between packets. It also provides application level time stamping which is easily available on the receiver side. The accuracy of this tool has been shown in [START_REF] Ubik | Low-cost precise qos measurement tool[END_REF] to be in the area of 2µs. The cross-traffic used in the measurements was a video stream operating at 5Mbps based on the MS Smooth Streaming platform [START_REF] Zambelli | IIS smooth streaming technical overview[END_REF]. In our earlier work [START_REF] Villa | Group based traffic shaping for adaptive http video streaming[END_REF] the nature of this traffic is described in more detail with special focus on its burst oriented nature. Based on this, we can state that a video server of this type connected on a 100Mbps link will send bursts of data towards the client at rates close to its link speed, independent of what the average video stream bitrate is. Thus, we have that the earlier stated λ cross > λ out requirement for packet probing method is met. The access capacity towards the client was configured using the QoS mechanisms provided by the Cisco switch used. This configuration gives the λ out and also the buffer size V B available for the specific access.

For the purpose of time synchronization of probe sender and receiver both NTPv4 and PTPv2 [START_REF]IEEE Standard for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems 1588-2008[END_REF] were used in the measurements. The NTP configuration was made so that the probe receiver used the probe sender as NTP server, in order to maximize timing accuracy when using this protocol. When using PTP as synchronization protocol, the same direct relationship between the probe sender and receiver was made. The probe sender in PTP master role and the probe receiver in PTP slave role.

The operating systems used on the video client and server side were MS Windows 7 Professional, while probe sender and receiver were using Linux Ubuntu 12.04.

All processing of measurement data was done post-experiment in order to keep the cross-process impact for each node as low as possible.

Measurement scenarios

A range of different probe traffic patterns was used in the measurements. The parameters subject for change were the intra-packet time values t a and t b , while the probe packet size was fixed at 100Byte in all cases. When using packet pair probing, t a was always smaller than t b , thus reflecting the time between packets in a pair. In the case with a sequence of single probe packets and measurement of OWD, t a was set equal to t b . The sum of t a and t b gives the period in the probe pattern and thereby also the probing rate in pps and bps. Ideally, the probing rate should be kept as low as possible, in order to minimize the chances of self-induced congestion or other undesirable service impact. The parameters given in Table 1 represent the range of different scenarios included in our measurements, for which we compared the two methods of active probing. For each scenario, measurements were done for a period of 10 minutes both with and without the cross-traffic (i.e. the 5Mbps video stream). The capacity on the access link was set to 10Mbps for all scenarios, but with different buffer (V B ) settings configured in the router.

Results

In this section, a selection of the measurement results is presented. The specific scenario for packet pair probing where V B =256/t a =0.55/t b =4.6, and for OWD probing where V B =256 / t a =t b =2.6 is presented in detail. The presentation of the results are mainly given by means of graphical summaries, and especially by estimated probability density function (PDF) plots and the corresponding cumulative distribution function (CDF). The differences in distributional properties for the received probe traffic with and without cross-traffic present are quite well presented by this. Whenever appropriate, interesting numerical indicators are also included.

The effect of time synchronization method used (NTP, PTP) is only presented for the OWD probing method. The reason for this is that the packet pair method only uses receiver side time information, and therefore is not affected by this.

Packet Pair probing results

For the packet pair probing method, the difference between the PDF for probe packets received when there is no cross-traffic present, and when the video stream is introduced is clear in terms of the reduced distribution peak for the latter case. In addition, it is interesting to note the appearance of a small peak in the distribution for t a*,i (cf. By viewing the same measurements using a CDF plot rather than PDF, it is even easier to see that the packet pair probing is able to detect the cross-traffic (cf. Fig 3). The CDF for t a*,i observations are lifted in the low region, and reduced in the high region. The similar effect is also seen in the CDF for t b*,i observations. Thus, both t a*,i and t b*,i observations detect cross-traffic, but at the same time they have a negative impact on each other (as indicated by the low region CDF lift). Common for both the PDF and CDF view of the packet pair method is that even in the no Cross-Traffic scenario the received probe traffic has some deviations from the original pattern. This represents a significant source of error, which could be critical depending on how the results of the probing are to be applied.

One-Way-Delay probing results

For the OWD probing method, the difference between the PDF for probe packets received with and without cross-traffic present is quite significant in terms of shape (cf. Fig 4,left side). The dominating peak is shifted upwards when cross-traffic is present, which also contributes to a higher mean value.

Effect of NTP versus PTP on One-Way-Delay results

The effect of using PTP as time synchronization protocol between the probe sender and receiver instead of NTP can be illustrated by a PDF and CDF plot for OWD observations as given in Fig. 5. The use of using PTP instead of NTP clearly gives a sharper peak in the PDF function and an increased function derivate in the mid region of the CDF function. These are both indications of more accurate sync. The difference in mean value for the observations when using NTP and PTP is about 6µS, which may increase the error in each probe sample value collected.

Cross traffic amount detection

The active probing methods generate samples for cross-traffic amount by measuring additional buffering time for the probe traffic caused by the cross-traffic. These samples are generated by either looking at the probe packet pair IAT or probe packet OWD. The difference between measured IAT or OWD values and their corresponding reference values generate a time series of buffering time samples (t pp,i or t owd,i ). By summarizing the time series for each method, over a 10 minute measurement period while the video stream is at 5Mbps, we get a view on each methods capability of cross-traffic amount detection (cf. Fig. 6).

Fig. 6. Comparison of probing methods

We can see that the method based on OWD measurements detects a higher crosstraffic amount for all probe rate levels, than the method based on packet pairs. It is also worth noticing that the two highest probe rate levels give distinct higher results for both methods. The amount of cross-traffic detected does not have the same linear increase as for the probing rate, but instead it seems to cross a threshold between the third and fourth probing rate level used. Although not further investigated, this threshold may indicate that the probe traffic has crossed a level where TCP mechanisms in cross-traffic are affected and thereby the nature of the traffic is changing.

For the packet pair method and the different t a values used (cf. Table 1) there are also quite noticeable differences. The highest t a value gives the higher cross-traffic amount detection across all probe rate levels.

For the OWD based method it is clear that the use of PTP for time synchronization instead of NTP has a significant effect, as it always gives a higher cross-traffic estimate. The graph for the PTP case also has a more logical profile than in the NTP case, as the cross-traffic volume consistently increases with increasing probing rate. The NTP graph starts with a moderate decrease, followed by a significant peak before dropping again. Repeated experiments shows that the results for the NTP case fluctuate more than in the PTP case, which is expected due to clock drift.

The presence of potential oversampling for the OWD measurements was not investigated. However, as the trend for both packet pair probing and OWD probing is quite similar across all probing rate levels we believe that this error factor did not contribute much to the measurement results.

Conclusions

The measurement based comparison of packet pair and OWD probing presented in this paper highlights strengths and weaknesses for both methods. The objective of the comparison was not to make a statement about which one is better, as this would have to be done in the context of a specific application. However, in a scenario such as the one we used in our measurements, it is clear that the OWD based method is able to detect more of the cross-traffic than the packet pair method.

Concerning the packet pair method, we believe that our findings related to dependencies between t a* and t b* observations have significance for a range of suggested probing methods based on the packet pair principle, e.g. in the area of available bandwidth estimation. To our knowledge, this specific dependency has not been documented earlier. We further believe that our findings related to sensitivity for parameter values t a and t b selected are of interest. Finding the optimal parameter selection for a complex traffic mix is foreseen to be quite challenging, but an approach where a range of values are used may be a beneficial approach.

The most interesting finding for the OWD method is the significant impact of using PTPv2 instead of NTPv4. Keeping in mind that our access network lab is of a much smaller size than what a real network would be, it clearly demonstrates the shortcomings of using a NTP based synchronization for purposes like this. Another interesting finding is the challenge to establish a reference point for OWD when no cross-traffic is present. The variations observed even in the small access network lab were higher than what we expected.

Future Work

To further analyze the capabilities of active probing methods it would be interesting to also make measurements using other tools than Rude/Crude, and also use different operating systems and even HW components. Reason being that one can never neglect the possibilities when doing measurements that some of the things which are being observed have underlying reasons not related to the topic investigated.

The implementation of time synchronization between probe sender and receiver should also be closer investigated. The specific implementation of NTPv4 in Ubuntu 12.04 may have flaws, or there could even be some not obvious configuration options with a positive impact on accuracy. In a scenario with at least µs accuracy of time synchronization between hosts on the Internet, active probing using OWD measurements becomes very attractive.

The cross-traffic used in our measurements was of a specific type, operated at a specific quality (bitrate) level. A more composed and potentially complex crosstraffic profile would also be interesting to include in a measurement study. However, the burst oriented nature of the video service used gives a very challenging traffic pattern. Thus, we do not think a more composed cross-traffic scenario will make the research question significantly harder.

Fig. 1 .

 1 Fig. 1. Access Link Buffer Model

Fig 2 ,

 2 left side) in the low value region in the case when cross-traffic is present. The source of this effect is the occurrence of t b*,i > t b samples, which delays the first packet in the next packet pair -as discussed in section 4. The result of this is the low value group of t a*,i < t a observations.

Fig. 2 .

 2 Fig. 2. PDF view of Packet Pair Results at t a =0.55ms, t b =4.6ms and V B =256

Fig. 3 .

 3 Fig. 3. CDF view of Packet Pair Results at t a =0.55ms, t b =4.6ms and V B =256

Fig. 4 .

 4 Fig. 4. PDF and CDF view of OWD results at t a =t b =2.6ms, V B =256 and NTP The effect on the CDF (cf. Fig 4, right side) illustrates the difference even better, as the two graphs follow each other up to the ~90% level and then the cross-traffic graph flattens out. This indicates that the high ~10% amount of values differ significantly in magnitude. Same as for the packet pair probing method, both the PDF and CDF view of the measurements show variations even in the no Cross-Traffic scenario.

Fig. 5 .

 5 Fig. 5. PDF and CDF view of OWD results at t a =t b =2.6ms and no Cross-Traffic, NTP and PTP

Table 1 .

 1 Configuration parameters

	V B [MB]	t a [ms]	Packet Pair t b [ms]	One-Way-Delay pps t a [ms] t b [ms] pps
	256/500/1000 0.55/0.65/0.75 4.6/4.5/4.4 388 2,60	2,60	383
	256/500/1000 0.55/0.65/0.75 3.7/3.6/3.5 470 2,13	2,13	468
	256/500/1000 0.55/0.65/0.75 3.0/2.9/2.8 562 1,78	1,78	559
	256/500/1000 0.55/0.65/0.75 2.5/2.4/2.3 654 1,53	1,53	650
	256/500/1000 0.55/0.65/0.75 2.1/2.0/1.9 752 1,33	1,33	747


Petr Velan

Tomáš Jirsík

Pavel Čeleda

Design and Evaluation of HTTP Protocol Parsers for IPFIX Measurement

Keywords: HTTP, protocol, parser, traffic, measurement, flow, IPFIX

In this paper we analyze HTTP protocol parsers that provide a web traffic visibility to IP flow. Despite extensive work, flow meters generally fall short of performance goals due to extracting application layer data. Constructing effective protocol parser for in-depth analysis is a challenging and error-prone affair. We designed and evaluated several HTTP protocol parsers representing current state-of-the-art approaches used in today's flow meters. We show the packet rates achieved by respective parsers, including the throughput decrease (performance implications of application parser) which is of the utmost importance for high-speed deployments. We believe that these results provide researchers and network operators with important insight into application visibility and IP flow.

Introduction

Flow monitoring technologies, such as NetFlow or IPFIX, are widely used in large-scale networks to provide situational awareness. They provide information about who communicates with whom, when, how long, using what protocol and service and also how much data was transferred. Acquired flow data is based on IP headers (network and transport layer) and it does not include any payload information. On the other hand, we observe that HTTP protocol [START_REF] Fielding | Hypertext Transfer Protocol -HTTP/1.1[END_REF] became a "new Transmission Control Protocol" (TCP). More and more applications rely on HTTP protocol, e.g. Web 2.0 content, audio and video streaming, instant messaging etc. HTTP traffic (TCP port 80) can usually pass through most firewalls and therefore presents a standard way of transporting/tunneling data. The versatility, ubiquity and amount of HTTP traffic makes it easy for an attacker to hide malicious activities. Missing application layer visibility renders standard NetFlow and IPFIX to be ineffective for HTTP monitoring.

Network and security devices use application layer analysis to provide application visibility, monitoring and traffic control. For example, Cisco Application Visibility and Control (AVC) [START_REF]Application Visibility and Control[END_REF] solution uses next-generation deep packet inspection (NBAR2) and flexible NetFlow to identify, classify and report on over 1,000 applications. HTTP information elements are supported by YAF [START_REF] Inacio | YAF: Yet Another Flowmeter[END_REF] and nProbe [START_REF] Deri | nProbe: an Open Source NetFlow probe for Gigabit Networks[END_REF] flow meters and are exported in IPFIX format. Most intrusion detection systems extract application layer data for in-depth analysis.

Deep Packet Inspection (DPI) predominates for application layer analysis. While it is possible for small and medium sized networks to effectively deploy the DPI, the amount of traffic in large (10+ Gb/s) networks makes the inspection of every packet a challenging problem. The performance and results that can be achieved depend on a number of factors including flow meter configuration and analyzed traffic distribution. Due to the complexity and sheer number of application protocols, it is hard to compare different environments/platforms and derive conclusions on which solution is the best.

Our research attempts to answer following question: What are the impacts of application layer analysis of HTTP protocol on flow meters and flow monitoring process? The contribution of our work is threefold: (i) We designed and evaluated several HTTP protocol parsers representing current state-of-the-art approaches used in today's flow meters. (ii) We introduced a new flex-based HTTP parser. (iii) We report on the throughput decrease (performance implications of application parser) which is of the utmost importance for high-speed deployments.

The paper is organized as follows. Section 2 describes related work. Section 3 contains a description of the HTTP inspection algorithms and the framework that was used to test the algorithms. Section 4 describes the methodology used for HTTP parsers performance comparison. Section 5 presents the performance evaluation of the individual algorithms. Finally, Section 6 contains our conclusions.

Related Work

Application layer protocol parsers are an integral part of many network monitoring tools. We explored the source code of the following frameworks to see how the HTTP parsing is implemented. nProbe uses standard glibc [START_REF]The GNU C Library[END_REF] functions like strncmp (compare two strings) and strstr (locate a substring). YAF uses Perl Compatible Regular Expressions (PCRE) [START_REF]PCRE -Perl Compatible Regular Expressions[END_REF] to examine HTTP traffic. Suricata [START_REF]Open Information Security Foundation: Suricata -network IDS, IPS and network security monitoring engine[END_REF] and Snort [START_REF] Roesch | Snort -Lightweight Intrusion Detection for Networks[END_REF] are both written in C. Suricata uses LibHTP [START_REF] Qualys | LibHTP -security-aware parser for the HTTP protocol[END_REF] library which does HTTP parsing using custom string functions while Snort does its parsing using glibc functions. httpry [START_REF] Bittel | httpry -HTTP logging and information retrieval tool[END_REF] is another HTTP logging and information retrieval tool which is also written in C and uses its own built-in string functions. These HTTP parsers are hand-written.

Other approach is taken by Bro [START_REF] Paxson | Bro: a system for detecting network intruders in real-time[END_REF] authors. They use binpac [START_REF] Pang | binpac: A yacc for Writing Application Protocol Parsers[END_REF], a declarative language and compiler designed to simplify the task of constructing robust and efficient semantic analyzers for complex network protocols. They replaced some of Bro existing analyzers (handcrafted in C++) and demonstrated that the generated parsers are as efficient as carefully hand-written ones.

In this paper, we try to determine whether these approaches to HTTP parsing can handle large traffic volumes. Besides the above approaches, we propose to use the Fast Lexical Analyzer (Flex) [START_REF] Levine | Flex & Bison[END_REF] to design a new HTTP parser. Flex converts expressions into a lexical analyzer that is essentially a deterministic finite automaton that recognizes any of the patterns. The algorithm that converts a regular expression directly to deterministic finite automaton is described in [START_REF] Lesk | Lex -a Lexical Analyzer Generator[END_REF] and [START_REF] Mcnaughton | Regular Expressions and State Graphs for Automata[END_REF].

There are other works that inspect the HTTP protocol headers. In [START_REF] Schneider | The new web: characterizing AJAX traffic[END_REF] the authors use statistical flow analysis to differentiate traditional HTTP traffic and Web 2.0 applications. In [START_REF] Torres | Identifying sessions to websites as an aggregation of related flows[END_REF] the authors identify HTTP sessions based on flow information. In both cases a ground truth sample is needed, which is a topic addressed by [START_REF] Torres | Strategies for automatic labelling of web traffic traces[END_REF]. In [START_REF] Gehlen | Uncovering the big players of the web[END_REF] and [START_REF] Mahanti | Characterizing the file hosting ecosystem: A view from the edge[END_REF] the authors use DPI to obtain information from the HTTP headers. Our approach is orthogonal to these works, since we are interested in extending IP flow records with HTTP data.

Parser Design

HTTP protocol [START_REF] Fielding | Hypertext Transfer Protocol -HTTP/1.1[END_REF] has a number of properties that can be monitored and exported together with IP flow data. The most commonly monitored ones are present in almost every HTTP request or response header. Based on the properties monitored by the state-of-the-art DPI tools we selected the following ones for our parsers: HTTP method, status code, host, request URI, content type, user agent and referer. Keeping track of every bidirectional HTTP connection is too resource consuming on high speed networks, thus we focus on evaluation of each individual packet. This approach is more common for flow meters since it is more resistant to resource depletion attacks.

We implemented and evaluated three different types of parsing algorithms. The first algorithm (strcmp approach) loops the HTTP header line by line and searches each line for given fields. It uses standard glibc string functions like memchr, memmem and strncmp. The simplified pseudocode is shown in Algorithm 1. The second algorithm (pcre approach) uses several regular expressions taken from YAF to search the packet for specific patterns indicating HTTP header fields. The pseudocode for the pcre algorithm is shown in Algorithm 2. We designed the third algorithm (flex approach) to handle each packet as a long string. It uses finite automaton to find required HTTP fields and the Flex lexer is used to process the packets. The automaton design is shown in Fig. 1.

Since the Flex is a generic tool, its initialization before scanning each packet is quite an expensive operation. Therefore we decided to remove all unnecessary dynamic memory allocations and costly initializations to see whether the performance can be increased. We named the new version optimized flex. The disadvantage of Flex is that it has to keep the data in its own writable buffer. Therefore the received data must be copied to such a buffer, which adds to the processing costs significantly. The advantage of the flex parser is its simple maintenance and extension possibilities. The framework can be modified to parse any other application layer protocol just by changing the set of regular expression rules. The strcmp parser would have to be rewritten from a scratch.

The strcmp implementation also offers a space for further improvement. Algorithm 3 shows an optimized strcmp version of the code that features a better Algorithm 1 strcmp 1: if first line contains "HTTP" then 2:

while not end of HTTP header do

3:

for every parsed HTTP field do

4:

if field matches the line then

5:

store the value of the line processing logic. The optimized version searches for specific strings by comparing several bytes at once, which is done by casting the character pointer to integer pointer. The number that is compared to the string is computed from ASCII codes of the characters and converted to network byte order. The size of the used integer depends on the length of the string; longer integers offer better performance.

To focus only on the HTTP parsing algorithms we decided to let the FlowMon exporter [START_REF]INVEA-TECH: FlowMon Exporter -Community Program[END_REF] handle the packet preprocessing. We used a benchmarking (input) plugin that reads packets from PCAP file to memory at start-up. Then it supplies the same data continuously for further processing. This approach allows us to focus on benchmarking the algorithms without the necessity of considering the disk I/O operations. We provide the source code of implemented algorithms and used packet traces at the paper homepage [START_REF] Šíma | FlowMon -Plugins for HTTP Monitoring[END_REF].

Evaluation Methodology

In this section we define a methodology of HTTP protocol parsers evaluation. We focus on parsing performance (number of processed packets per second) of the algorithms described in Section 3 from several different perspectives.

The first perspective focuses on the performance comparison with respect to analyzed traffic structure. The second perspective covers the impact of the number of HTTP fields supported by parser. The third perspective describes the effect of a Carriage Return (CR or '\r') and a Line Feed (LF or '\n') control characters distribution in packet payload.

A common technique of increasing network data processing performance is processing only important part of each packet. Therefore, we perform each of the tests in two configurations. In the first configuration the parsers are given whole packets. This is achieved by setting limit on packet size to 1500 bytes, which is the most common maximum transmission unit value on most Ethernet networks. In the second configuration the parsers are provided with truncated packets of length 384 bytes, which is the minimum packet length recommended for DPI by authors of the YAF exporter [START_REF] Inacio | YAF: Yet Another Flowmeter[END_REF].

To test the performance of the parsers, we created an HTTP traffic trace (testing data set). Our requirements on the data set were as follows: preserve the characteristics of HTTP protocol, reflect various HTTP traffic structures and have no side effects on the flow meter. In order to meet these requirements we decided to create synthetic trace.

The HTTP protocol is a request/response protocol. To preserve the characteristics of HTTP protocol during the testing a random request, response and binary payload packet was captured from the network. To omit the undesirable bias of the measurement only these three packets were used to synthesize test trace. The final test trace consists of 200 packets. In order to reflect various traffic structures, we suggested following ratio:

r = #request packets + #response packets #all packets * 100 (1)
where r ∈ [ 0, 100 ] and created a test set for each integer ratio from the interval. Further, we created two packets with modified payload. One packet contained the CR and LF control characters only at the very beginning of the packet payload, the other one only at the end. For both of the modified packets and for the unchanged packet the test trace for each integer ratio was created.

Having defined the test trace, we propose the following case studies to cover all evaluation perspectives. The case studies are carried out for both full and truncated packets. Moreover, we measure the performance of the flow meter without an HTTP parser (no HTTP parser). This way we can estimate the performance decline caused by increased application layer visibility.

1. Performance Comparison: This case study compares the parsing performance of implemented parsers. Moreover, we report on the flow meter performance without an HTTP parser (no HTTP parser). 2. Parsed HTTP Fields Impact: This case study shows a parser performance with respect to the number of supported HTTP fields. We incrementally add support for new HTTP fields and observe the impact on the parser performance.

Packet Content Effect:

The result of this study presents the influence of the CR and LF control characters position in a packet payload on the parser performance. The test traces containing modified payload packets are used to perform the measurement.

The performance evaluation process employs the benchmarking input plugin (see Section 3) to obtain the number of processed packets per second. In order to avoid influencing the results, the plugin uses separate thread and CPU core for the accounting. The plugin counts the number of the processed packets in ten second interval and then computes the packets per second rate. We have operated the benchmark plugin for fifty seconds for each test trace and computed a number of packets processed and a standard error of the measurement. The parsed HTTP header fields impact and packet content effect was assessed in a similar way. All measurements were conducted on a server with the following configuration: Intel Xeon E5410 CPU at 2.33 GHz, 12 GB 667 MHz DDR2 RAM and Linux kernel 2.6.32 (64 bit).

In this section, we present results of HTTP parser evaluation. First we describe the parser performance comparison, then we investigate the impact of supported HTTP header fields. Finally, the effect of the packet content on HTTP parsing performance is shown.

Performance Comparison. This case study uses the standard version of each parser that supports seven HTTP fields. The data set containing the unmodified payload packets is used and the parsers are tested both on full and truncated packets. Fig. 2 shows the result for full packets case study and Fig. 3 shows performance evaluation for truncated packets.

First we discuss the Fig. 2. The no HTTP meter is capable of parsing more than 11 million packets per second. This result is not influenced by the application data carried in the packet, since the data is not accessed by the no HTTP parser. Employing event the fastest of the HTTP parsing algorithms the performance drops to the nearly one half of parsed packets per second. All of the HTTP parsers show the decrease in the performance as the ratio r increases since the amount of request and response packets, which are more time demanding to parse, grows. The best performance is achieved by optimized strcmp parser, which uses application protocol and code level optimizations. The parser takes into account the HTTP header structure, the difference between HTTP request and response headers and looks only for header fields that can be found in the specific header type. The code level optimizations include converting static strings into integers and matching them against several characters at once, which can be done in one processor instruction. The strcmp parser performance is the second best, although the throughput is less than half of the optimized strcmp parser.

The main difference between flex and optimized flex parsers is in the automaton initialization process. By rewriting the initialization process we achieved slight performance improvement, which is noticeable mainly in the 0 %, 20 % interval, where the actual HTTP parsing time is short. There is one other important factor affecting the flex parser performance. The flex automaton is designed to work with its own writable buffer, since it marks end of individual parsed tokens directly into the buffer. For this reason a copy of the packet payload must be created before the actual parsing can start. To measure the impact of the copying, we created another two parser plugins called empty and copy. First we measured the flow meter throughput with empty plugin which performs no data parsing, then with copy plugin which only copies packet payload to static buffer. From the results we estimate the throughput the optimized flex parser would have without the memory copying. The performance of the optimized flex parser would be about 2.4 million packets per second for 0 % and 0.33 million packets per second for 100 % HTTP packets. This shows that the actual HTTP parsing, when compared to strcmp parser, is slightly faster for binary payload packets and slower for HTTP header packets.

The performance of the pcre parser is the lowest. The PCRE algorithm converts the regular expression to a tree structure and then performs a depth-first search while reading the input string. In case there is no match in current tree branch, the algorithm backs up and tries another one. Therefore, for a complex regular expression the pattern matching is not that fast as simple string search using functions like strcmp. Another reason why the pcre parser is not fast is that it performs all searches on whole packet payload. The other algorithms are processing the data sequentially.

Fig. 3 shows the results for truncated packets. The optimized strcmp and no HTTP are only slightly faster since the truncating of the packets has positive impact on CPU data cache utilization. The strcmp algorithm is flawed since its throughput on HTTP packets deteriorates rapidly. This shows the disadvantage of hand-written parsers, as they are more error-prone than the generated ones. The pcre parser performance is almost doubled, as the repeatedly processed data are truncated. Flex based parser also achieve performance increase, since the memory copying costs are reduced for smaller data.

Parsed HTTP Header Fields Impact. This case study was designed to show the impact of a number of parsed HTTP header fields on the parser performance.

When payload packets are detected, they do not have their content parsed for additional HTTP header fields. Therefore, a test set containing only HTTP request and response packets was used. The case study starts with an empty plugin, that does not parse HTTP header fields and just labels the HTTP pack- ets. In the next steps we cumulatively add an additional header field to parse until we parse all of the seven supported fields. We run the tests for both full and truncated packets. The average performance of the parsers for each of the added field is shown in Fig. 4.

Only the request and response packets are parsed, thus the values for the seven fields parsed in the Fig. 4 correspond to the 100 % packet/s values in the Fig. 2 and Fig. 3. For the same reason the parsed packets per second numbers are lower in comparison with the Fig. 2 and Fig. 3. The performance of strcmp and pcre parsers drops with each additional parsed HTTP header field. The optimized strcmp parser implementation details attentional fluctuation affect on performance shown in Fig. 4. An example is the performance increase when adding a (4) request URI or a (3) status code. It is caused by extra code snippet that extracts the URI so that this line is not processed by the more generic code designed for parsing other header fields. Due to the usage of finite automaton the data is always processed in one pass by the flex-based algorithms. Therefore, they retain the same level of performance for all additional fields. This feature could be used to automatically build powerful parsers, when the large number of parsed application fields would make it ineffective to create hand-written parsers.

Same as in the previous case study, the parsers processing truncated packets show better performance than the parsers working on full packets.

Packet Content Effect. This case study investigates the possible effects of the position of the CR and LF control characters in the packet payload on the parser performance. The mentioned ASCII characters represent the end of line in the HTTP header. Some of the proposed algorithms use these characters as the trigger to stop parsing. Therefore the position of these characters affects the parsers performance. The packets with the CRLF characters at the very beginning should be parsed faster than the packets having the CRLF at the end since the algorithm terminates as soon as it identifies the CRLF characters. The test sets with modified binary payload packets (see Section 4) enables us to compare the algorithms taking in account this perspective. We used the modified binary payload packets to test the parsers. The parsing algorithms, except the strcmp algorithm, show insignificant difference in their performance for all variants of the modified packets. The pcre and optimized strcmp parsers do not search for end of line characters in order to label the packet, therefore this test does not affect them. The flex-based algorithms are not significantly affected since they stop parsing on first character that is not expected in HTTP header and therefore stop at the first character in any case. The strcmp parser depends on the search for end of line characters, which is confirmed by Fig. 5. The sooner the characters are found, the faster the algorithm terminates.

The scenario with truncated packets is different, since the performance on end data set is greater than on unchanged data. This is caused by removing the end of packet payload together with the end of line character. When the strcmp algorithm cannot find the character, it terminates immediately without trying to search the data. Therefore it terminates sooner than on unchanged data set, where the end of line character is found and the search continues.

Conclusions

This paper has assessed the impacts of HTTP protocol analysis on flow monitoring performance. We implemented the state-of-the-art approaches to HTTP protocol parsing. Moreover, the new flex-based HTTP parser was designed and its performance was compared to the other approaches.

The evaluation shows that in our case the hand-written and carefully optimized parser performs significantly better than implementations with automated parsing. It also shows that the new flex-based implementations handles the increasing number of parsed HTTP fields without significant performance loss. Truncating the packets prior to HTTP protocol parsing can increase the parser throughput. The performance comparison of no HTTP parser with HTTP parsers shows that providing an application visibility is a demanding task. Current approaches to the application protocol parsing may not be effective enough to process a high-speed network traffic.

Although we focused on HTTP header parsing in this paper, measuring overall performance of flow meters is also essential. We will address performance evaluation and runtime requirements of entire flow meter frameworks in our future work. This research will allow us to compare existing frameworks and new prototypes under equal conditions. Monitoring HTTP application protocol expose new challenges for flow meters. In particular, an increased number of exported fields, large flow record length and their impact on transport protocol requires further research.

Fig. 1 :

 1 Fig. 1: flex algorithm schema

Fig. 2 :

 2 Fig. 2: Parser performance comparison with respect to HTTP proportion (0 %no HTTP, 100 % -only HTTP headers) in the traffic -full packets 1500 B.

Fig. 3 :

 3 Fig. 3: Parser performance comparison with respect to HTTP proportion (0 %no HTTP, 100 % -only HTTP headers) in the traffic -truncated packets 384 B.

Fig. 4 :

 4 Fig. 4: An HTTP parser throughput for 1500 B packets; supported fields -(0) none -HTTP protocol labeling, (1) +host, (2) +method, (3) +status code, (4) +request URI, (5) +content type, (6) +referer, (7) +user agent.

Fig. 5 :

 5 Fig. 5: Packet content effect -packet length 1500 B.

Acknowledgments. This material is based upon work supported by Cybernetic Proving Ground project (VG20132015103) funded by the Ministry of the Interior of the Czech Republic.