Yehuda Afek
email: afek@math.tau.ac.il

Anat Bremler-Barr

Yaron Koral
email: yaronkor@post.tau.ac.il

Efficient Processing of Multi-Connection Compressed Web Traffic

Keywords: pattern matching, compressed http, network security, deep packet inspection

Compressing web traffic using standard GZIP is becoming both popular and challenging due to the huge increase in wireless web devices, where bandwidth is limited. Security and other content based networking devices are required to decompress the traffic of tens of thousands concurrent connections in order to inspect the content for different signatures. The major limiting factor in this process is the high memory requirements of 32KB per connection that leads to hundreds of megabytes to gigabytes of main memory consumption. This requirement inhibits most devices from handling compressed traffic, which in turn either limits traffic compression or introduces security holes and other dysfunctionalities. In this paper we introduce new algorithms and techniques that drastically reduce this space requirement by over 80%, with only a slight increase in the time overhead, thus making real-time compressed traffic inspection a viable option for network devices.

Introduction

Compressing HTTP text when transferring pages over the web is in sharp increase motivated mostly by the increase in web surfing over mobile cellular devices. Sites such as Yahoo!, Google, MSN, YouTube, Facebook and others use HTTP compression to enhance the speed of their content download. In Section 6.2 we provide statistics on the percentage of top sites using HTTP Compression. Among the top 1000 most popular sites 66% use HTTP compression (see Figure 3). The standard compression method used by HTTP 1.1 is GZIP.

This sharp increase in HTTP compression presents new challenges to networking devices that inspect the content for security hazards and balancing decisions. Those devices reside between the server and the client and perform Deep Packet Inspection (DPI). When receiving compressed traffic the networking device needs first to decompress the message in order to inspect its payload. The two major performance penalties associated with this process are time and ⋆ Supported by European Research Council (ERC) Starting Grant no. 259085 space. The time it takes to decompress a packet is a small fraction of the time it then takes to inspect the packet in most DPI applications [START_REF] Bremler-Barr | Accelerating multi-patterns matching on compressed HTTP[END_REF]. However the space complexity cost of decompression is a major obstacle specially when the device is dealing with hundreds and thousands of concurrent connections. Notice that the techniques presented in [START_REF] Bremler-Barr | Accelerating multi-patterns matching on compressed HTTP[END_REF], while reducing the DPI time requirement, it still uses information within the compression, i.e., decompression is still required.

This high memory requirement leaves the vendors and network operators with three bad options: either ignore compressed traffic, forbid compression, or divert the compressed traffic for offline processing. Obviously neither is acceptable as they present security hole or serious performance degradation.

The basic structure of our approach to dealing with the memory problem is to keep the buffers of all the connections compressed, except for the data of the connection whose packet(s) is now being processed. Upon packet arrival, unpack its session buffer and process it. One may naïvely suggest to just keep the appropriate amount of original compressed data as it was received. However this approach fails since the buffer would contain pointers to data more than 32KB backwards. Our technique, called SOP, packs the buffer of a connection by combining information from both compressed and uncompressed 32KB buffer to create the new compressed buffer that contains pointers that refer only to locations within itself. We show that by using our technique on real life data we reduce the space requirement by a factor of 5 with a time penalty of 26%. Notice that while our method modifies the compressed data locally, it is transparent to both the client and the server.

We then design an algorithm that combines our SOP technique that reduces space with the ACCH algorithm that reduces time complexity. By using the designed algorithm we achieve improvement of 42% of the time and 79% of the space requirements. The time-space tradeoff presented by our technique provides the first solution that enables DPI on compressed traffic in wire speed.

Background

Compressed HTTP: HTTP 1.1 [START_REF]Hypertext transfer protocol -http/1.1[END_REF] supports the usage of content-codings to allow a document to be compressed. The RFC suggests three content-codings: GZIP, COMPRESS and DEFLATE. In fact, GZIP uses DEFLATE with an additional thin shell of meta-data. For the purpose of this paper they are considered the same. Currently the GZIP and DEFLATE compressions are the common codings supported by current browsers and web servers. 3The GZIP algorithm uses combination of the following compression techniques: first the text is compressed with the LZ77 algorithm and then the output is compressed with the Huffman coding. Let us elaborate on the two algorithms:

LZ77 Compression [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF]-The purpose of LZ77 is to reduce the string presentation size, by spotting repeated strings within the last 32KB of the uncompressed data. The algorithm replaces the repeated strings by (distance,length) pair, where distance is a number in [START_REF] Bremler-Barr | Accelerating multi-patterns matching on compressed HTTP[END_REF]32768] (32K) indicating the distance in bytes of the repeated string and length is a number in [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF]258] indicating the length. For example, the text: 'abcdeabc' can be compressed to: 'abcde(5,3)'; namely, "go back 5 bytes and copy 3 bytes from that point". LZ77 refers to the above pair as "pointer" and to uncompressed bytes as "literals".

Note that the LZ77 compression is a time consuming task, while the decompression is considerably light process (we use this observation later on as a motivation in the design of our algorithm). Experiments in Section 6 show that compression takes around 20 times more than decompression. Roughly speaking, the basic idea of the compression process goes as follows: at each point within the traffic, LZ77 tries to find the longest string that has already appeared in the text within the previous 32KB (the most recent if there are multiples). If such a string is found, LZ77 replaces the current string with a pointer to that occurrence. If no repetition longer than 2 bytes is found, than these bytes are not compressed. To decompress the traffic, one needs to reveal the referred bytes by the pointers which translates to a simple operation of consecutive memory copying directly from the 32KB buffer. Reading consecutive bytes has low per-byte read cost due to the good spatial locality in the cache, i.e., reading consecutive 32 bytes within a cache line costs one main memory access.

Huffman Coding [START_REF] Huffman | A method for the construction of minimum-redundancy codes[END_REF]-Recall that the second stage of GZIP is the Huffman coding, that receives the LZ77 symbols as input. The purpose of Huffman coding is to reduce the symbol coding size by encoding frequent symbols with fewer bits. The Huffman coding method assigns to symbols from a given alphabet a variable-size codeword (coded symbol). Dictionaries are provided to facilitate the translation of binary codewords to bytes.

The Huffman decoding process is relatively fast. Common implementation (cf. zlib [5]) extracts the dictionary, with average size of 200B, into a temporary lookup-table that resides in cache. Frequent symbols require only one lookuptable reference, while less frequent symbols require two lookup-table references.

Deep packet inspection (DPI): DPI is the main action taken to inspect traffic, by identifying signatures (patterns or regular expressions) in the packet payload. Today, the performance of security tools is dominated by the speed of the underlying DPI algorithms [START_REF] Fisk | An analysis of fast string matching applied to contentbased forwarding and intrusion detection[END_REF]. The two fundamental paradigms to perform string matching derive from Aho-Corasick (AC) [START_REF] Aho | Efficient string matching: an aid to bibliographic search[END_REF] and Boyer-Moore (BM) [START_REF] Boyer | A fast string searching algorithm[END_REF] algorithms. The BM algorithm does not have deterministic time and is prone to denial-of-service attacks using tailored input. Therefore the AC algorithm is the standard.The implementations need to deal with thousands of signatures. For example, ClamAV [START_REF]Clam antivirus[END_REF] virus-signature database consists of 27K patterns, and the popular Snort IDS [START_REF]Snort[END_REF] has 6.6K patterns; note that typically the number of patterns considered by IDS systems grows dramatically over time. Implementation of the traditional algorithm translates to dozens of megabytes and may even reach gigabytes of memory. The size of the signatures databases dictates not only the memory requirement but also the speed, since it forces the usage of a larger and slower memory on an order-of-magnitude such as DRAM, instead of using a faster one such as SRAM. That leads to an active research of reducing the memory requirement by compressing the corresponding DFA [START_REF] Lin | Pipelined parallel ac-based approach for multi-string matching[END_REF][START_REF] Van Lunteren | High-performance pattern-matching for intrusion detection[END_REF][START_REF] Tan | Architectures for bit-split string scanning in intrusion detection[END_REF]; however, all proposed techniques suggest pure-hardware solutions, which usually incur prohibitive deployment and development cost. Still the common case, definitely in a software solution, requires using a very large database of signatures for DPI. Moreover we note that the DPI solutions do not enjoy the spatial locality time boost. Each input byte requires one or two memory reads to different parts of the memory and thus the DPI solutions do not enjoy the benefits of caching.

Challenges in performing DPI on Compressed HTTP

This section provides an overview of the obstacles in performing deep packet inspection (DPI) in compressed HTTP traffic on a multi-connection environment.

As noted in [START_REF] Bremler-Barr | Accelerating multi-patterns matching on compressed HTTP[END_REF], there is no apparent "easy" way to perform DPI over compressed traffic without decompressing the data in some way. This is mainly because LZ77 is an adaptive compression algorithm.

One of the main problems with the decompression is its memory requirement; the straightforward approach requires a 32KB sliding window for each HTTP connection. Note that this requirement is difficult to avoid, since the back-reference pointer can refer to any point within the sliding window and the pointers may be recursive (i.e., a pointer may point to an area with a pointer). On the other hand, DPI of non-compressed traffic requires storing only a two (or four) bytes variable that holds the DFA state. Hence, dealing with compressed traffic poses a higher memory requirement by a factor of 8 000 to 16 000. Thus, mid-range firewall that handles 100K-200K concurrent sessions needs 3GB-6GB memory while a high-end firewall that supports 500K-10M concurrent sessions needs 15GB-300GB memory only for the task of session decompression. This memory requirement has implication on not only the price and feasibility of the architecture but also on the capability to perform caching or using fast memory chips such as SRAM. Thus reducing the space has also straight implication on the speed. This work deals with the challenges imposed by that space aspect.

Apart from the space penalty described above, the decompression stage also increases the overall time penalty. However, we note that DPI requires significantly more time than decompression, since decompression is based on consecutive memory reading and therefore enjoy the cache block architecture and has low per-byte read cost, where DPI employs a very large DFA that is accessed by reads to non-consecutive memory areas therefore requires main memory accesses. Our experimental results in section 6 show that the decompression is 10 times faster than the DPI process in a multi-connection environment.

Related Work

There is an extensive research on preforming pattern matching on compressedfiles, but very limited is on compressed traffic. Requirements posed in dealing with compressed traffic are: (1) on-line scanning (1-pass), (2) handling of thousands of sessions concurrently and (3) working with LZ77 compression algorithm (as oppose to most papers which deal with LZW/LZ78 compressions). [START_REF] Bremler-Barr | Accelerating multi-patterns matching on compressed HTTP[END_REF] is the first paper to analyze the obstacles of dealing with compressed traffic but it only accelerated the pattern matching task on compressed traffic and did not handle the space problem, and it still requires the decompression. We show in Section 5.3 that our paper can be combined with the techniques of [START_REF] Bremler-Barr | Accelerating multi-patterns matching on compressed HTTP[END_REF] to achieve a fast pattern matching algorithm for compressed traffic, with moderate space requirement.

There are techniques developed for "in-place decompression", the main one is LZO [START_REF] Oberhumer | LZO[END_REF]. While LZO claims to support decompression without memory overhead it works with files and assumes that the uncompressed data is available. We assume decompression of thousands of concurrent sessions on-the-fly, thus what is for free in LZO is considered overhead in our case. Furthermore, while GZIP is considered the standard for web traffic compression, LZO is not supported.

Packing technique

In this section we describe our packing technique to reduce the 32KB buffer space requirement per session. The basic idea is to keep the session buffer in its packed form until the time a new incoming packet arrives for that session. To achieve that we use packing technique to keep a correct updated buffer after each packet processing. It has two parts:

-Swap Out of boundary Pointers (SOP ) algorithm for packing the buffer.

-Our corresponding algorithm for unpacking the buffer. Whenever a packet is received, the buffer that belongs to the incoming packet session is unpacked. After the incoming packet processing is finished an updated buffer is packed using the SOP algorithm. The next subsections elaborates on those parts of the algorithm.

Buffer Packing: Swap Out of boundary Pointers (SOP)

In this subsection we describe our buffer packing technique. The first obvious attempt is to store the buffer in its compressed form using the original received traffic. However this attempt fails since the compressed form of the buffer contains pointers that point to positions prior to the 32KB boundary. Figure 1(a) shows an example of the original compressed traffic. Note that it contains pointer to a part that is no longer within the buffer boundaries. The conclusion from this attempt is that the solution must have the following property: A buffer must contain all information for its pointers extraction.

The second obvious attempt is to compress (each time from scratch) the 32KB buffer using some compression algorithm such as GZIP. That solution follows the above property since the compression is based only on information within the buffer. However, this solution performs compression which is an expensive task, while the memory saving is a negligible 1.5% as compared to SOP.

Our suggested solution, called Swap Out-of boundary Pointers (SOP ), solves the problems of the above two attempts. The technique uses information within the original compressed and uncompressed form of the buffer for a quick packing process. SOP changes the original GZIP compressed form related to the buffer, so that it contains pointers that refer only to information inside the buffer. To achieve this, SOP swaps all the pointers that point outside of the new boundary of the buffer with its referred literals. 4 Figure 1(c) shows an output of this algorithm. The pointer (300,5) that points prior to the buffer new boundary is replaced by the string 'hello' where the others remain untouched.

Since in every stage we maintain the invariant that pointers refer only to information within the buffer -the buffer can be unpacked. SOP still has a good compression ratio (as shown in Section 6) since most of the pointers are left untouched because they originally pointed to a location within the 32KB buffer boundary. SOP is also fast since it performs only one pass on the uncompressed information and the compressed buffer information, taking advantage of the GZIP compression that the source (server) did on the traffic.

The pseudocode is given in Algorithm 1. The algorithm consists of 4 parts. The first part performs Huffman decoding of the incoming packet in order to determine its uncompressed size which in turn determines the new boundary of the 32KB buffer. Note that pointers cannot be extracted at this point since oldPacked is still compressed. Therefore the decoding is kept within a linked-list data structure that contains either sequence of literals or pointer elements.

The other three parts consist of decoding either oldPacked or packet into new-Packed using unPacked. Part 2 decodes data that would not be packed again since it is located outside of the new boundary of the 32KB buffer (after receiving the new packet). Parts 3 and 4 decode the rest of oldPacked and packet respectively, and prepare the newPacked buffer along the decoding process.

Note that the output is not optimal in terms of space. Figure 2 shows a case where LZ77 algorithm (2(c)) outperforms SOP (2(d)). In that case, the original compression did not indicate of any direct connection between the second occurrence of the 'Hello world!' string to the string 'sello world'. The connection can be figured out if one follows the pointers of both strings and finds that both strings share common referred bytes. Since SOP performs a straightforward swapping without following the pointers recursively it misses this case. However, the loss of space is limited as shown in the experimental results section.

We also tried some other, more sophisticated variants of SOP to solve that problem by some kind of a recursive method. However, the complexity of those algorithms is much higher and the gained space reduction is limited.

Unpacking the buffer: GZIP decompression

SOP buffers are packed in a valid GZIP format, hence a regular decompression can be used for unpacking. The main difference is that most of the data is decompressed more than once since it is maintained compressed. Buffer decompression is performed upon each incoming packet. Each byte is decompressed on average 4.2 times (see Section 6) using SOP buffers as compared to only once in the original GZIP method.

One may wonder if partial decompression of buffer areas is more affordable than the suggested method that decompresses the entire buffer upon each incoming packet. Since the pointers are recursive, the retrieval of the literals referenced by a pointer is a recursive process touching several locations in the buffer, and requiring to decode more symbols than its own length. For example: a pointer that points to another pointer which in turn points to a third pointer, requires decoding three different areas where the referred pointers and the literals reside. This property explains the poor results.

We designed a method for partially decompression, called SOP-Indexed. It is defined as follows:

-Split the buffer to fixed size chunks of bytes and keep indices that hold starting positions of each chunk. -Recursively extract each pointer and decode only the chunks that contain required information for extraction.

For example: if a 256B chunks are used, referring to the 500 th byte of the 32KB uncompressed buffer requires to decode the second chunk that corresponds to the [256-511] byte positions within the uncompressed buffer. If the pointer exceeds the chunk boundary of 511, the next chunk has to be decoded too.

Zero padding needs to be applied at the end of each chunk so the offset would be in terms of bytes and not in terms of bits. Each index is coded with 15 bits in order to represent offsets for up to 32KB. The chunk size poses a time-space tradeoff. Smaller chunks support more precise references and result in less decoding but require more indices that have to be stored along with the buffer, and more padding for each of the smaller chunks, hence cause larger space penalty. The results in Section 6 shows that only a limited time improvement of ratio 36% as compared to SOP, is gained by SOP-Indexed.

Combining SOP with ACCH algorithm

The algorithm, ACCH presented in [START_REF] Bremler-Barr | Accelerating multi-patterns matching on compressed HTTP[END_REF], reduces the time it takes to do pattern matching to less than 26% compared to doing it with Aho-Corasick (AC). The general idea is to take advantage of pointer information from LZ77 in order to skip and avoid scanning some bytes. Since most of the compressed bytes are represented as pointers, most of the byte scans can be saved. The data about previous byte scans is stored in a Status Vector [START_REF] Bremler-Barr | Accelerating multi-patterns matching on compressed HTTP[END_REF]. Each vector entry is 2 bit long and stores three possible state values: Match, in case that a pattern was located, and two other states; If a prefix longer than a certain threshold was located the status is Check, otherwise it is Uncheck. An important observation is that the status of pointer bytes can be determined based on the status of the referred bytes only, without further scanning.

The ACCH algorithm is somewhat orthogonal to the SOP algorithm, still there are two points that must be addressed. The first one is related to the fact that the Status Vector itself has 8KB space requirement which needs to be taken care off in order to continue and enjoy the space benefits of SOP. The second point is related to the fact that the SOP algorithm changes the structure of some of the pointers, therefore when a pointer is replaced by SOP, the vector needs to be efficiently adapted to the new structure.

We use two techniques to address the above points. The first is to mark only the status changes and the second is to use the pointers to figure out the status. We give here a sketch of the suggested method that handles both points due to space limitations. Let us start with the first point. The general idea is to store only status changes instead of the statuses themselves, among the packed buffer symbols. There is no need to store status changes within pointers since ACCH can restore most of the previous referred statuses from the pointer referred area. The rest of the statuses are maintained using extra bits.

Handling the second point means that whenever a pointer is replaced with literals, the symbols that resemble the statuses within it should remain valid. Achieving this is straightforward. The status symbols are maintained from the referred bytes when they are copied, hence no additional memory references are required for status update after pointer replacing.

Applying the combination of the methods described above enabled us to combine ACCH with SOP algorithms and gain space and time improvements. The combination achieves time performance of more than two times faster than performing SOP with regular AC (as demonstrated in the next section).

Experimental Results

Experimental Environment

Our time performance results are given relative to the performance of a base algorithm Plain, which is the decompression algorithm without packing, therefore the processor type is not an important factor for the experiments. The experiments were performed on a PC platform using Intel ® Core 2 Duo CPU running at 1.8GHz using 32-bit Operating System. The system uses 1GB of Main Memory (RAM), a 2MB L2 Cache and 2 × 32KB write-back L1 data cache.

We base our implementation on the zlib [5] software library for the compression/decompression parts of the algorithm.

Our experimental environment does not simulate packets from multipleconnections but only from a single connection at a time. Therefore we flush the entire system's cache upon each packet arrival to create the context switch effect between multiple connections. Note that by flushing the cache we are very conservative in our experimental environment and we suspect that in a real life scenario the time of SOP is even better. In the real life environment, some of the writing to the buffers could be performed in the background while handling a different section therefore most of the memory writing penalty could be avoided. Furthermore, sometimes we may receive several consecutive packets from the same flow, hence may be processed without flushing the cache.

Data Set

The data set consists of 2308 HTML pages taken from the 500 most popular sites that use GZIP compression. The web site list was constructed from the Alexa site [START_REF]Top sites[END_REF] that maintains web traffic metrics and top-site lists. Total size of the uncompressed data is 359MB and in its compressed form is 61.3MB.

While gathering the data-set from Alexa, we created an interesting statistics about the percentage of the compressed pages among the sites as shown on Figure 3. The statistics shows high percentage of compression, in particular among the top 1000 sites. As popularity drops the percentage slightly drops. Still, almost 1 out of every 2 sites uses compression.

Space and Time Results

This subsection reports results concerning the average space requirement for our algorithm as shown in Table 1. We define Plain as the basic algorithm that performs decompression and maintains a buffer of plain uncompressed data for each connection. Note that at the beginning of a connection the buffer stores less than 32KB since it stores only as much as was sent. Therefore the average buffer size of Plain is 29.9KB which is slightly lower than the maximum value of 32KB. We use Plain as a reference for performance comparison to the other proposed methods and set its time and space ratios to 1. We measure the size of the incoming compressed data representing the buffer and call it OrigComp. This data can not be used as a buffer for a multi-connection environment, since it contains pointers that point to positions prior to the 32KB buffer range. The average buffer size required by OrigComp is 4.54KB, which is considered as a space lower bound.

We define Deflate as the method that compresses each buffer from scratch using GZIP. This method represents the best practical space result but has the worse time requirements of more than 20 times higher than Plain. SOP takes 3.85 more time than Plain. This is a moderate time penalty as compared to Deflate, the space requirement of SOP is 5.17KB which is pretty close to the 5.04KB of Deflate. The small space advantage gained by Deflate in addition to the poor time requirement makes it irrelevant as a solution.

The last method we examined is the SOP-Indexed which maintains indices to chunk offsets within the compressed buffer to support a partial decompression of the required chunks only. We used a 256B chunks and got an average of 69% chunk accessed. The time ratio is improved to 3.49 as compared to Plain. The space penalty for maintaining the index vector and chunk padding is of 0.3KB.

Time Results Analysis

As explained in Section 5.2, SOP decompresses each byte on average 4.2 times. Hence one would expect SOP to take 4.2 times more than Plain. Still SOP takes only 3.85 times. This can be explained by inspecting the data structures that require main memory accesses by each of the algorithms. SOP maintains in main memory the old and new packed buffers (i.e., oldPacked and newPacked as in Algorithm 1) which are heavily accessed during packet processing. Plain on the other hand, uses parts of the 32KB buffer, taken from main memory. When processing a packet, Plain touches only parts of the 32KB buffer. We measured the relative part of the buffer which is accessed by Plain using a method similar to the one in 5.2 with chunks of 32B. An average 40.3% of the buffer is accessed. SOP also uses a 32KB buffer for the uncompressed data, but it keeps it only in the cache and most of it is never written back to the main memory. The key point is that a write-back cache is used, hence this buffer remains in cache. The unpacked 32KB buffer is maintained in a temporary variable and when SOP finishes processing the packet that variable is disposed and not written back to main memory. However, working in a write-through cache architecture may harm SOP performance. The main memory space used for SOP data structures is thus around 10KB upon each incoming packet where as the main memory space accessed by Plain is around 12KB (= .4 of the 32KB) which is 20% higher and explains why the time performance of SOP is better than the expected 4.2.

DPI of Compressed Traffic

In this subsection we analyze the performance of DPI. We focus on pattern matching, which is a lighter DPI task than the regular expression matching. We show that the processing time taken by SOP is minor compared to the processing time taken by the pattern matching task. Since the regular expression matching task is even more expensive (than pattern matching), the processing time of SOP is even less important. Table 2 summarizes the overall time and space requirements for the different methods that implement pattern-matching of compressed traffic in multiconnection environment. The time parameter is compared to performing Aho-Corasick (AC) on uncompressed traffic, as implemented by snort [START_REF]Snort[END_REF]. Recall that AC uses a DFA and basically performs one or two memory references per scanned byte. The other pattern matching algorithm we use for comparison is ACCH which is based on AC and uses techniques that are adjusted to GZIP compressed input making the pattern matching process work faster. However, the techniques used by ACCH are independent from the actual AC implementation. The space per buffer parameter measures the memory required for every session upon context switch that happens after packet processing is finished, i.e., in SOP after packing.

The offline-processing method (Offline) represents the only option supported by current network tools, that deals with compressed traffic. The space requirement is calculated by rough estimate of average compressed and uncompressed When used in combination with AC as used today, it presents an enormous space requirement in terms of mid-range security tool.

We measured the time ratio of performing Plain as compared to pattern matching using AC, both on single and multi-connection environment. On the single-connection environment the ratio is as low as 0.035 where on the multiconnection environment the ratio is 0.101. The difference is due to the context switch upon each packet on the multi-connection environment that harms the decompression spatial locality property. Note that SOP is compared to performing Plain on a multi-connection environment.

As explained in 5.3, ACCH improves the time requirement of the pattern matching process. Recall that in order to apply the ACCH algorithm we need to store on memory an additional data structure called Status Vector. Applying the suggested compression algorithm for the Status Vector compressed it to 1.03KB. Therefore the total space requirement of SOP combined with ACCH is 6.19KB.

The best time is achieved using Plain with ACCH but the space requirement is very high as compared to all other methods apart from Offline. It occurs that combining SOP and ACCH achieves almost 80% space improvement and above 40% time improvement comparing Plain with AC.

As we look at the greater picture that involved also DPI, we need to refer to the space requirement applied by its data structures. As noted before, the DPI process too has large memory requirements. As opposed to the decompression process which its space requirement is proportional to the number of concurrent sessions, the DPI space requirements depend mainly on the number of patterns that it supports. Therefore, the DPI large space requirement is applied from the first session. Hence, assuming that DPI space requirements are at the same order as those of decompression for mid-range network tools, the 80% space improvement for the decompression buffers is translated to a 40% space improvement for the overall process.

Conclusion

With the sharp increase in cellular web surfing, HTTP compression becomes common in today web traffic. Yet due to its high memory requirements, most security devices tend to ignore or bypass the compressed traffic and thus introduce either a security hole or a potential for a denial of service attack. This paper presents SOP , a technique that drastically reduces this space requirement (by over 80%) with only a slight increase in the time overhead. It makes realtime compressed traffic inspection a viable option for network devices. We also present an algorithm that combines SOP with ACCH, a technique that reduces the time required in performing DPI on compressed HTTP [START_REF] Bremler-Barr | Accelerating multi-patterns matching on compressed HTTP[END_REF]. The combined technique achieves improvements of almost 80% in space and above 40% in the time requirement for the overall DPI processing of compressed web traffic. Note that ACCH algorithm (thus the combined algorithm) is not intrusive to the Aho-Corasick (AC) algorithm, and it may be replaced and thus enjoy the benefit of, any DFA based algorithm including recent improvements of AC [START_REF] Lin | Pipelined parallel ac-based approach for multi-string matching[END_REF][START_REF] Van Lunteren | High-performance pattern-matching for intrusion detection[END_REF][START_REF] Tan | Architectures for bit-split string scanning in intrusion detection[END_REF].

Fig. 1 .

 1 Fig. 1. Sketch of the memory buffer in different scenarios. Each solid box represents a packet. Dashed frame represents the 32KB buffer. Each arrow connects between a pointer and its referred area.

Fig. 2 .

 2 Fig. 2. Sketch of the memory buffer in different scenarios.

Fig. 3 .

 3 Fig. 3. Statistics of HTTP Compression usage among the Alexa [15] top-site lists

Table 1 .

 1 Comparison of Time and Space parameters of different algorithms

	Packing Method Average	Compression Ratio	Average
		Buffer Size	per Buffer	Time Ratio
	Plain	29.9KB	1	1
	OrigComp	4.54KB	0.1518	-
	Deflate	5.04KB	0.1576	20.77
	SOP	7.33KB	0.245	3.91
	SOP	6.28KB	0.211	3.89
	SOP	5.17KB	0.172	3.85
	SOP-Indexed	5.47KB	0.183	3.49

Table 2 .

 2 Overview of Pattern Matching + GZIP processing size of 27KB and 156KB respectively. The compressed form is stored during session arrival and the uncompressed data is stored during pattern matching phase.

	Algorithms in Use	Average Time Ratio Space per Buffer
	Packing Pattern Matching
	Offline AC	-	170KB
	Plain AC	1.1	29.9KB
	Plain ACCH	0.36	37.4KB
	SOP	AC	1.39	5.17KB
	SOP	ACCH	0.64	6.19KB

Analyzing captured packets from last versions of both Internet Explorer, FireFox and Chrome browsers shows that accept only the GZIP and DEFLATE codings.

Note that pointers can be recursive, i.e., pointer A points to pointer B. In that case we replace pointer A by the literals that pointer B points to.

Acknowledgment

The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)/ERC Grant agreement n°259085.


Ioannis Psaras
email: i.psaras@ee.ucl.ac.uk

Richard G Clegg
email: r.clegg@ee.ucl.ac.uk

Raul Landa
email: r.landa@ee.ucl.ac.uk

Wei K Chai
email: w.chai@ee.ucl.ac.uk

George Pavlou
email: g.pavlou@ee.ucl.ac.uk

Modelling and Evaluation of CCN-caching Trees ⋆

Keywords: Content-Centric Networks, Packet Caching, Markov Chains

Networking Named Content (NNC) was recently proposed as a new networking paradigm to realise Content Centric Networks (CCNs). The new paradigm changes much about the current Internet, from security and content naming and resolution, to caching at routers, and new flow models. In this paper, we study the caching part of the proposed networking paradigm in isolation from the rest of the suggested features. In CCNs, every router caches packets of content and reuses those that are still in the cache, when subsequently requested. It is this caching feature of CCNs that we model and evaluate in this paper. Our modelling proceeds both analytically and by simulation. Initially, we develop a mathematical model for a single router, based on continuous time Markov-chains, which assesses the proportion of time a given piece of content is cached. This model is extended to multiple routers with some simple approximations. The mathematical model is complemented by simulations which look at the caching dynamics, at the packet-level, in isolation from the rest of the flow.

Introduction

The Internet today operates in a machine-resolution fashion, that is to say, content is accessed via requests to given hosts. However, the user is not usually interested in a host, but in specific content. Users are essentially interested in content-resolution, or service-resolution. Recently, the influential paper [START_REF] Jacobson | Networking Named Content[END_REF] introduced the Networking Named Content (NNC) overlay paradigm as a means to realise Content-Centric Networks (CCN). The paper suggests numerous architectural changes to networks based upon the CCN paradigm. For example, according to the NNC approach, names are hierarchical, can be aggregated, are structured, and also human-readable, at least to a certain extent. The approach also brings certain security benefits with named content being signed and secure. The present paper models just one of those proposed changes: the caching strategy used in CCN. This is modelled in isolation from the other proposals within [START_REF] Jacobson | Networking Named Content[END_REF], i.e., security, content-resolution scalability and routing are subject to different modelling and evaluation approaches and therefore, of different studies.

The NNC scheme proposed in [START_REF] Jacobson | Networking Named Content[END_REF] changes the whole Internet flow model from a sender-driven, TCP-like buffering/congestion controlled environment to a receiver-driven, caching (instead of buffering) scheme. In particular, by exploiting the fact that each data packet can now be identified by name, CCN can take advantage of forwarding the packet to many interested recipients. That is, instead of buffering a packet until it is forwarded to the interested user and then discarding it, as happens today, CCN first forwards the packet to the interested user and then "remembers" the packet, until this packet "expires" [START_REF] Jacobson | Networking Named Content[END_REF].

The "remembering" and "expiration" of packets is accomplished using caching techniques at the packet level. The model requires that every CCN-compatible router is equipped with a cache, which holds all packets for some amount of time; in [START_REF] Jacobson | Networking Named Content[END_REF] and in the present study, Least Recently Used (LRU) policies [START_REF] Jelenković | Least-recently-used caching with dependent requests[END_REF] are used, but alternative designs are also possible. If two or more subsequent requests for the same content arrive before the content expires at any one of the routers/caches along the way, the packet is forwarded again to the new interested user, instead of having to travel back to the content server to retrieve it. Clearly, this will benefit popular content (e.g., reduced delivery delay) and will reduce network resource requirements (e.g., bandwidth and server load).

In this study, we focus on the new flow model introduced in [START_REF] Jacobson | Networking Named Content[END_REF] and attempt to quantify the potential gains that the paradigm shift will bring with it. To achieve this goal and in order not to violate the semantics in [START_REF] Jacobson | Networking Named Content[END_REF], we study the caching part of the CCN paradigm isolated from the rest of the proposed architecture. We carry out a packet-level analysis, instead of a flow-level one, since it is our opinion that given the totally unexplored research field, investigations on packetlevel dynamics should precede flow-wide conclusions. This study attempts to determine how long a given packet, which is referred to as the Packet of Interest, PoI, remains in any of the caches along the path from the user back to the server (i.e., not in a single cache), given a system topology and rates of requests. The contributions of the present study to this new field of research are as follows: an analytical model is developed for a single and then multiple caches; the validity of various modelling assumptions is discussed and a Monte-Carlo simulation is used to check some assumptions; a Java model is built based upon the analytical model; this is compared against model-simulator results from ns-2.

Our findings indicate that, as expected, there is a clear network-wide performance gain for popular content, but this gain: i) goes down to almost zero for unpopular content and this will be the more common case, ii) depends heavily on the size of the router-cache and iii) is different between routers distant from the original server of the data and those close to the server.

Macro-vs Micro-Caching

Strategic content replication techniques to reduce response time and the amount of network resources (e.g., bandwidth and server load) needed to send the content back to the user have been investigated in the form of i) Web Proxy Caching (e.g., [START_REF] Rosensweig | Breadcrumbs: Efficient, Best-Effort Content Location in Cache Networks[END_REF] [3], [START_REF] Fujita | Coarse-grain replica management strategies for dynamic replication of web contents[END_REF]) and ii) Content Delivery Networks (CDNs) (e.g., [START_REF] Pallis | Insight and perspectives for content delivery networks[END_REF]).

In both cases, the issue of utmost importance is the choice of the best possible network location to (either statically or dynamically) replicate content. In the case of Web-Proxy caches, the ISP is responsible for deciding where to replicate, while in the case of CDNs, this role is taken by the corresponding company that owns the network of surrogate servers. In both cases, however, the location of the proxy/surrogate server is always known and fixed in advance.

Furthermore, IP-multicast has been proposed and investigated (e.g., [START_REF] Ratnasamy | Revisiting IP multicast[END_REF], [START_REF] Floyd | A reliable multicast framework for light-weight sessions and application level framing[END_REF]) to serve multiple users that are simultaneously interested in the same content. However, IP-multicast serves users that belong to the same group only and are prepared to receive all of the content that the group wants to receive (i.e., not necessarily the parts of it that individual users are interested in).

CCNs, as proposed in [START_REF] Jacobson | Networking Named Content[END_REF], constitute the conceptual marriage of the above technologies, but in the "micro-level". We classify Web-Caching and CDNs as "macro-caching" approaches, since they target caching of entire objects, be it web-pages, or entire files; we consider CCNs as a "micro-caching" approach, since caching here is done at the packet-level1 . Moreover, in the above technologies the setup is fixed and predefined. In contrast, in CCNs content is cached and multicast "on-the-fly", wherever it is requested or is becoming popular.

Single-vs. Multi-cache System Modelling

Web-caching and the properties of the LRU (and other similar) replacement policies have been extensively studied in the past, e.g., [START_REF] Breslau | Web caching and zipf-like distributions: Evidence and implications[END_REF][START_REF] Jelenković | Least-recently-used caching with dependent requests[END_REF][START_REF] Jelenkovic | Asymptotic approximation of the move-to-front search cost distribution and least-recently-used caching fault probabilities[END_REF]. However, most of these studies focus either on single caches, e.g., [START_REF] Jelenković | Least-recently-used caching with dependent requests[END_REF], or chains of well-known and pre-defined caching points [START_REF] Che | Analysis and Design of Hierarchical Web Caching Systems[END_REF]. These studies can model many issues in detail, such as the correlation between subsequent requests, the request frequencies of the various packets in the system and the cache size [START_REF] Jelenković | Critical sizing of lru caches with dependent requests[END_REF][START_REF] Jelenković | Least-recently-used caching with dependent requests[END_REF][START_REF] Jelenkovic | Asymptotic approximation of the move-to-front search cost distribution and least-recently-used caching fault probabilities[END_REF].

Generally speaking, single-cache modelling has to consider mainly: i) the number of requests for a specific content at a specific cache, ii) the number of requests for other contents at this specific cache, iii) the size of the cache and iv) correlations between packet requests.

According to the authors in [START_REF] Jacobson | Networking Named Content[END_REF], "CCN caches are the same as IP buffers, but have a different replacement policy". Trying to model multi-cache systems, where no hierarchy ([3]) exists is not trivial. The problem of modelling the caching system now comprises a multi-dimensional problem, where the above parameters still have to be considered, but they need to be considered simultaneously for all the routers/caches along the path from the content client to the content server.

For example, there is some pre-existing work on multiple cache situations. In [START_REF] Che | Analysis and Design of Hierarchical Web Caching Systems[END_REF], the authors develop models that apply to LRU caches which are two levels deep (that is, one cache feeds into a second cache). In [START_REF] Dan | An approximate analysis of the lru and fifo buffer replacement schemes[END_REF] and [START_REF] Rosensweig | Approximate models for general cache networks[END_REF] the authors develop a system which can approximate cache miss ratios for hierarchical cache systems using a solution which converges to a solution iteratively. However, the complexity for a single cache is O(KB), where B is the buffer size and K is the number of independent items that have distinct access possibilities. There remains a need for a simple approximate model to estimate loss rates on a system when both B and K may be extremely large. This is where we focus on in this study. We propose a single-cache model, which is simple enough in order to remain valid when extended to multiple caches along the end-to-end path.

The model works from the point of view of estimating how long a particular content packet, the Packet of Interest, PoI, remains in any of the caches along the path. It outputs the proportion of time that PoI is nowhere cached, essentially reflecting the cache miss ratio for PoI.

2 Modelling CCN using Markov chains 2.1 A simple model for a single router Assume that for a single router requests for the PoI arrive as a Poisson process with rate λ. Whenever such a request arrives, it moves this packet to the top slot in the cache. Assume that requests which will move the PoI further down the cache (either requests for packets not in cache or requests for packets in cache, but further down than the PoI ) also arrive as a Poisson process with rate µ.

This process can be simply modelled as a continuous time homogeneous Markov chain, where the state of the chain represents the exact slot that the packet currently occupies in the cache. Number the Markov chain states as follows. State 1 is when the PoI is at the "top" of the cache (just requested), state N is when our packet is at the bottom of the cache (any request for a packet not already in cache will push our packet out of the cache). State N + 1 represents the state where our packet is not in the cache. The chain and cache are shown in Fig. 1

(left).

All states (except state 1) have a transition to state 1 with rate λ (another request for the packet arrives and the packet moves to the top of the cache). All states i in 1 ≤ i ≤ N have a transition to state i + 1 with rate µ (a packet arrives which moves our packet lower in the cache). Now let π = (π 1 , π 2 , . . . , π N +1 ) be the equilibrium probabilities of the chain -these have the simply physical interpretation of being the proportion of the time the PoI spends at that cache position (or for π N +1 the proportion of the time the packet is not in cache). The chain can be trivially shown to be ergodic and hence, these probabilities exist for µ, λ > 0 and finite N .

The balance equations can be easily solved to give

π i = λ µ µ µ+λ i for i < N +1 and π N +1 = µ µ + λ N .
(1) This equation gives the proportion of the time that the PoI is not in cache (and also the proportion of requests for the PoI that get a cache miss). Naturally, the proportion of the time our packet gets a "cache hit" is one minus this. Therefore, the mean rate of requests that propagate upstream is:

λ λ λ λ λ µ µ µ µ µ µ F (λ1) F (λ2) F (µ1) F (µ2) F (φ1) F (φ2)
λπ N +1 = λ µ µ+λ N
. The next question is how can this be extended for the onward process when there are multiple caches in the system. The situation is shown in Fig. 1 (right). Router R1 has N 1 memory slots and R2 has N 2 memory slots. The notation F (x) means an arrival process (not necessarily Poisson) with a rate x. The processes F (λ i ) and F (µ i ) are Poisson by assumption. The remaining processes F (φ i ) are those requests for the packet of interest corresponding to cache misses in router Ri. These onward processes can be shown to have a phase distribution (see [START_REF] Neuts | Matrix-Geometric Solutions in Stochastic Models: an Algorthmic Approach Chapter 2: Probability Distributions of Phase Type[END_REF] for a general discussion of the phase distribution) derivable from a simple transform to the chain transition probabilities but it is not analytically tractable.

Modelling the multiple router system as a Markov chain

Consider again the diagram of two CCN routers in Fig. 1 (right). Note, however, that from [START_REF] Breslau | Web caching and zipf-like distributions: Evidence and implications[END_REF] we have that the rate φ 1 = λ 1 γ N1 1 , where γ 1 = µ 1 /(λ 1 + µ 1 )the rate of requests passed upstream from router R1 for the PoI is the rate of incoming requests times the proportion of time spent in the cache miss state. This trivially follows since the Poisson arrival process at rate λ 1 is memoryless, so a proportion γ N1 1 of them are passed upstream. The total arrival rate at router 2 is λ 1 γ N1 1 + λ 2 , call this λ ′ 2 . Now the question is what proportion of the time is the packet in cache at R2. The proportion of time at R1 is still given by [START_REF] Breslau | Web caching and zipf-like distributions: Evidence and implications[END_REF]. The problem can again be formulated as a Markov chain, this time with states numbered in N 1 × N 2 , where the state number (i, j) refers to the position of the packet of interest in cache at R1 and R2, respectively. If i = N 1 + 1, then the packet is not in cache at router R1 and if j = N 2 + 1, then the packet is not in cache at router R2. Let π (i,j) be the equilibrium probability that the PoI is in state i at R1 and state j at R2. Let π (i,•) = j π (i,j) be the equilibrium probabilities of the states of R1, independent of R2. It can be trivially shown that these are exactly those probabilities as for the single router model -that is, the presence of the second router does not affect the first as expected. Calculating π (•,j) = i π (i,j) has proved more difficult and the only result obtained so far is that

π (•,1) = λ ′ 2 -λ 2 C/(µ 2 + λ 2 ) µ 2 + λ ′ 2 -C
, where λ ′ 2 is the adjusted arrival rate discussed earlier and

C = λ 1 (µ 1 /(λ 1 + µ 1 )) N1 -(µ 1 /(λ 1 + λ 2 + µ 1 + µ 2 )) N1 .
From this we can see that C is positive and that π (•,1) will tend to

π (•,1) = λ ′ 2 /(µ 2 +λ ′ 2 )
as N 1 increases. This is the equation obtained when the non Poisson nature of the arrival stream is ignored. It can be easily seen that C tends to zero when N 1 increases as both terms inside the brackets are less than one and raised to a positive power.

For the other states, the Markov chain can be explicitly simulated (Monte-Carlo simulation) and the proportion of time spent in each of the states explicitly measured and summed to produce an estimate of the true equilibrium probabilities. One million iterations are performed with results from the first half a million iterations being discarded as "warm up". To ensure convergence, small values for N 1 and N 2 are used. The first simulation was with N 1 = 6, N 2 = 4 and λ 1 = λ 2 = µ 1 = µ 2 = 1.0. The results for π (•,j) were in agreement with the Poisson approximation to within ±0.002. A more rigorous test is provided when the value φ 1 is high compared to λ 2 . Again with N 1 = 6 and N 2 = 4 the theory is tested against experiment, but this time with λ 1 = 100.0, µ 1 = 10, 000, λ 2 = 0.1 and µ 2 = 100.0. For these parameters, the agreement with the Poisson assumption was weaker but all probabilities agreed within ±0.008. This was the highest level of disagreement found with any of many sets of test tried. We also note that these tests are with N 1 very low compared with the figures which will be used in real runs (small numbers of states were used because Markov chains with fewer states converge better in Monte Carlo simulation).

This section, therefore, provides good evidence that a pair of CCN caches feeding from one to another can be reasonably approximated by the simple single cache model presented before. The low error rate in assuming that the misses from one cache can be used as the input to a second (and the violation of the Poisson assumption ignored) leads us to our final multiple router model. In this model, the miss rates for the PoI are calculated by assuming that the input rate to a router is a combination of the rates of requests made directly at that cache and those cache misses passed upstream from previous routers.

Investigating the µ process further

In this section we investigate further the nature of the process µ. It is a subtle but very important point that the PoI can be moved down the cache by two related processes. The first possibility is that a packet arrives which is not in cache.

Assume requests for all other packets (cached or uncached) arrive at rate ν and that these arrivals are Poisson. However, not all arrivals of the rate ν will move the PoI further down the cache. Split ν into ν c and ν n for those requests, which are in cache and not in cache respectively -so the rate will sum to ν = ν c + ν n . Arrivals in ν n will always move the PoI further down (or out of) the cache, if it is in the cache. Arrivals in ν c will only move the packet further down the cache, if they are requests for a packet which is at a lower cache position. For example, if the PoI is at cache position n, a request for any packets in positions 1, . . . , nwill not move the position of the PoI in the cache, but will simply reshuffle those packets above it.

The next step is to assume that packets are equally likely to be found in any position in the cache. This is an unlikely assumption in real life but allows us to calculate an upper bound for the PoI cache miss rate. The reason this is an upper bound will be discussed later.

With these assumptions the position of the PoI can again be calculated as a Markov chain, but this time, the rate of moving from a state j to a state j + 1 is given by ν n + ν c (N + 1 -j)/N , where the first part represents the arrival of a request for a packet not in the cache and the second part represents the arrival of request for a packet which is in the cache, in a position lower than the PoI (currently in position j) -impossible if the packet is in position N and always the case for a request for a packet in the cache, if the packet is in position 1. The derivation of equilibrium probabilities π j can proceed in a similar manner to the previous section, however, while λ remains the same, the µ is replaced by

ν n + ν c (N + 1 -j)/N .
With these assumptions then

π N +1 = Γ [1+N (νc+νn+λ)/νc] Γ [N +N (νc+νn+λ)/νc] ,
where Γ is Euler's gamma function. Now, using the well-known formula

Γ [z+a] Γ [z+b] = z a-b [1 + O(z -1 )] then π N +1 = ν c + ν n ν c + ν n + λ N 1 + O ν c N (ν c + ν n ) 1 + O ν c N (ν c + ν n + λ) . (2)
The order terms become small as N becomes large, or as ν c becomes small with respect to ν n . It should also be noted that the time spent out of cache must be greater than if only the ν n arrivals were considered. Therefore, the proportion of time the PoI is not in cache is π N +1 ≃ νc+νn νc+νn+λ N when ν n ≫ ν c (only a small proportion of requests are in cache). In those circumstances, the fact that the µ process in Section 2.1 is a good approximation for the model that takes more careful account of whether arriving packets are in cache, or not and the approximation µ = ν n + ν c can be used. In other words, the rate µ is equal to the rate of requests for all packets other than the packet of interest (which is requested at rate λ).

The question remains how (2) alters if the assumption is dropped that arriving non PoI packets are equally likely to be at any position within the cache.

This assumption is true only when the non-PoI packets are requested with equal frequency. For non-equal distributions then the term ν n + ν c (N + 1 -j)/N would always be larger for lower numbered states and π N +1 is hence smaller than [START_REF] Cairano-Gilfedder | A decade of internet research: Advances in models and practices[END_REF]. No lower bound for π N +1 exists (indeed π N +1 can be arbitrarily close to zero for a given ν c , ν n , N and λ). Therefore, (2) is an upper bound which occurs in the case when non-PoI packets are requested with equal frequency and the lower bound is zero. It is worth remembering, however, that the definition of the µ process would, in that case, give the µ process an arrival rate near zero (it is explicitly defined as the arrival rate of packets which move the PoI further down the cache).

Summary of mathematical results

The reality of the Poisson assumptions may be questioned. It is well known for example, that Internet traffic is long-range dependent (for a recent review see [START_REF] Clegg | A critical look at power law modelling of the Internet[END_REF]). However, that is the traffic process as a whole, not the process of requests, which can look very different. Also, it may be argued that nobody knows what traffic statistics in a CCN-based Internet would look like. Many request processes (for example www, ftp and smtp) today can, in fact, be modelled perfectly well with Poisson processes (e.g., Table 3 in [START_REF] Cairano-Gilfedder | A decade of internet research: Advances in models and practices[END_REF]).

Section 2.1 showed a simple closed form solution when requests for the PoI are Poisson with rate λ and requests which move the PoI further down the cache are Poisson with rate µ. In Section 2.2, it was shown experimentally that certain deviations from Poisson for the requests for the PoI make only small differences to the proportion of time spent in cache. In Section 2.3 the assumption of Poisson was relaxed slightly for the µ process by considering requests for packets in cache and requests for packets not in cache separately, however, it was necessary to make strong assumptions about the distribution of packets within the cache. Further work in this direction would require an explicit model of the request frequencies (heavy tailled models would be a good candidate). This would bring the simple model presented here closer to those detailed single cache models discussed in previous sections.

Finally, therefore, the single cache model of Section 2.1 can be used to model a tree of caches by assuming that the misses from caches propagate towards the original holder of the content and that requests for the PoI arriving at a cache are a Poisson process with a total rate which is the sum of the rate of requests directly to that cache and the rate of missed requests to all caches which directly pass on to this cache. This situation is directly amenable to simple simulation even for situations with many caches and large router memories.

Simulation Results

Scenario Setup and Parameter Settings

Two simulation models are evaluated. The first directly encodes the analytical model from Section 2, while the second model is developed on ns-2 and is presented in Section 3.4.

Our first model takes as input the caching tree topology and, for each cache, the values of λ (request rate for PoI ), µ (rate at which other requests move the PoI down the cache) and N (cache size in packets). For simplicity, results are presented in terms of the ratio λ/µ, referred to as the Content Popularity Ratio (R CP ). The larger this measure is, the longer the PoI will stay in cache. For each router the simulation outputs the Proportion of Time Not in the Cache for the PoI from Eq. ( 1) and the proportion of requests that have to be forwarded further on towards the content server, referred to as λ Output and given in Section 2.1. The two topologies tested are given by Fig. 2; here, we are interested in scenarios where end-users request content from professional content-providers, or data-centers, i.e., we are not interested in peer-to-peer scenarios. It is reasonable to assume that routers which get more requests have more cache and therefore reasonable to assume that µ is proportional to N . For simplicity, the constant of proportionality is set to 1 for most results presented here, unless explicitly stated differently. This reduces the number of parameters to test in the system.

Scenario 1: Content Popularity and Cache Size

We initially assess the properties of requested content with regard to its popularity, as CCNs were originally proposed to deal with popular content and flash crowds [START_REF] Jacobson | Networking Named Content[END_REF]. This scenario uses the topology of Fig. 2(a) and experiments with different values for R CP . Values for R CP range from 0.000125 to 0.01 -all of these values represent very popular content but the experiment shows how the popularity affects the time in cache. The buffer size N is set to 200 packets. Fig. 3 presents the proportion of time the PoI is not in any of the caches along the path. Two conclusions can be drawn from this scenario. First, unpopular content spends very little time in the cache. This time is comparable to the life-cycle of an IP packet in the forwarding buffer in the prevailing networking model. This would be the case for most packets. Second, there is a clear difference between caching times for popular content in the core and leaf routers. Caching at the leaf nodes can reverse the expected effect on popular content nearer the server with the data source. That is, more caching at the leaf leads to less caching nearer to the data source for very popular content. (Note that the requesters and the data sources are all likely to be "edge" nodes in traditional Internet terms).

We go one step further to investigate the cache-size properties of the CCN paradigm. The buffers in small IP routers can serve the purpose of implementing CCNs, but the gain against today's end-to-end model will be marginal (i.e., even popular content is going to be "forgotten" very quickly). Hence, bigger amounts of memory may have to be considered in order to obtain gains from the paradigm shift. Using the same settings as the previous simulation, and keeping µ = N , the cache size N is varied from 100 to 64,000 packets (rounding packet sizes to 1KB, this is 100KB to 6.4MB). In Fig. 4(a), we see that for larger caches, even the less popular content has the chance to stay cached for longer times, as would be expected. Above 6MB of cache, even the less popular content is in cache at the leaf node for more than 50% of the time. Again, caching at leaf nodes has reduced the proportion of time spent in cache nearer to the content source. Fig. 4(b) shows the request rates for the PoI at each router (λ Input ) as well as those requests passed upstream towards the content server (λ Output ). The results agree with Fig. 4(a) and confirm that leaf nodes are passing less traffic upstream when caching levels are higher. This causes this specific content to become less popular nearer the packet source (see Fig. 4(b)).

Scenario 2: More Complex Tree Topologies

Simulation is now carried out on the extended tree topology of Fig. 2(b). In this scenario we apply different λs on each of the leaf routers. The purpose is to evaluate heterogeneity in requests. The request ratios for PoI, λ Input , together with the corresponding output λs for each one of the participating routers, are shown in Fig. 5(a). Fig. 5(b) shows the proportion of time that the PoI is not in the cache for each of the caches of Fig. 2(b). Results are given for two different cache sizes (0.2MBs and 3.2MBs). The R CP for the content of interest ranges between 0.0001 and 0.005. We observe the following:

1. Even extremely popular content is "forgotten" quickly by routers near the data source. Given a tree topology, similar to the one in Fig. 2(b) (a loose reflection of the topology of the Internet), these servers nearer to the data source receive many requests, much of which is for unpopular content. Given that many requests have to be forwarded up the chain to the content server -see Fig. 5(a), routers R1 and R2) -even popular content gets forgotten quickly -see Fig. 5(b) routers R1 and R2. 2. Leaf routers "remember" popular content for longer time. In Fig. 5(a), we see that λ Input ≃ 0.4 for router R22, while it is more than 0.8 for core router R2. Although both routers forward upwards a fairly big percentage of these requests, in Fig. 5(b) we see that the proportion of time not in cache for router R22 still drops lower than for core router R2. The basic functionality of caching using the CCN paradigm [START_REF] Jacobson | Networking Named Content[END_REF] is implemented in ns-2. Close approximations to the scenarios from the previous section were tested to estimate the agreement between theoretical modelling and ns-2 simulation. The full CCN paradigm as stated in [START_REF] Jacobson | Networking Named Content[END_REF] cannot easily be implemented in ns-2. Some of the reasons why are listed below.

-CCN Router. The structure of the CCN router influences several parts of the networking stack. Several designs are possible. It is not clear yet, for example, how traffic from different flows is multiplexed before it enters the outgoing link. -Cache Size. In case of small caches, similar to the IP buffers we have today, the network-wide gain will be limited. On the other hand, larger caches will increase the routers' computational burden and will complicate the collaboration between outgoing interfaces and the cache. -Transport Protocol. The CCN router structure will influence massively the design of the CCN transport entity. The initial proposal focuses on a receiverdriven transport protocol [START_REF] Jacobson | Networking Named Content[END_REF]. Therefore, flow rate adjustments and retransmission timers will have to be implemented on the receiver side. This constitutes a role-and functionality-swap from the current situation. This will heavily influence simulations and results at the flow level.

The experiments here attempt to minimise the above effects. The topology used is that of Fig. 2(a); the setup includes a simple constant bit rate (CBR) application over UDP that sends requests for 1KB-packet responses. By using UDP and CBR the issues of implementing a CCN-friendly transport protocol (which is yet to be defined) are avoided. Requests arrive as Poisson distributions to the leaf routers R2, R3 and R4. The rate of request for the PoI over each leaf node can be set and normalised against the total number of requests. This is similar to the R CP defined in the previous section. However, the exact implementation of µ is hard to achieve in a simulation environment -the effect of the PoI being pushed further down the cache is achieved by requesting packets other than the PoI, but here, the rate of requests equal to a given value of µ for a given router will be a function of N . The cache size is a fraction of the total number of packets in our pool; this fraction was initially set to 0.5. The simulation time was long enough to guarantee statistically stable results 2 . Simulations were carried out for different values of the cache-size fraction with regard to the number of packets in our pool. Although these results are not presented here, due to space limitations, we report that they follow similar trends.

Initially, R CP = 0.001 (for R2), R CP = 0.003 (for R3) and R CP = 0.01 (for R4) and N = 200. Arrivals for other packets are set to a rate of 200 per unit time, to approximate µ = 200. The ns-2 simulation outputs λ Input and λ Output as in the previous section.

Fig. 6(a) shows λ Input and λ Output for each one of the routers involved. It can be seen that simulation-routers tend to "forget" content more readily than model-routers (i.e., NS λ Output is larger than the Model one). Indeed, even for popular content (e.g., router R4), the simulation result shows "forgetfulness" of around 30% more than the model result. Differences between the simulator and the model were expected, because of the difficulties of tuning µ. However, it is encouraging the fact that both show results, which are broadly speaking, very similar. The curve shape for both simulations for λ Output follows the same trend.

2 This time varies depending on the RCP and the cache size. In Fig. 6(b), we increase the cache-size and observe the effect on λ Output for the NS and the model simulator, respectively. For small cache sizes, the results are largely in agreement, although there are small differences that cannot be seen here due to the Fig. scale. These differences do not exceed the threshold of 10%. As cache size increases to 3.2MB, the ns-2 λ Output follows the modelsimulator input, instead of the model-simulator output (i.e., λ Output ). The results are closer to the model-simulator when the cache size increases to 6.4MBs. The disagreement between results in the 3.2MB case could again be attributed to difficulties tuning the µ parameter. In the 6.4MB case, there is better agreement between the results, due to the fact that there are very few cache misses for the PoI (i.e., the proportion of time not in the cache for PoI very small, as we have also shown in Fig. 4(a)).

While the results from the two simulators are not directly comparable it is clear they are giving the same indications about the systems being studied.

Conclusions

This paper approaches the unexplored area of Content-Centric Networking, proposed in [START_REF] Jacobson | Networking Named Content[END_REF] from the viewpoint of a packet, or message (i.e., not a flow) and its corresponding caching dynamics. The approach involved a Markov-chain analysis, followed by model and ns-2 simulations. To the best of our knowledge, this is the first study to investigate this new networking paradigm.

The analytical model presented for the caching system presents a simple and tractable model for the time that a packet spends in cache. While the model began with strong assumptions of Poisson behaviour, subsequent analysis shows that many of these assumptions can be weakened and the analytical model remains valid. By necessity, the ns-2 implementation made some simplifying assumptions as the detailed protocol of a CCN network is as yet unknown. Results from the model and the ns-2 simulation were in broad agreement, but with some differences due to the different nature of the approaches.

In summary, the simulation findings indicate that: i) popular content tends to be cached at the leafs of the network. Content servers may receive a large number of requests for different content and hence forget more easily than leaf routers. ii) Sizing CCN caches is not a trivial task, since it depends on the distribution of arrival rates and the flows of requests from upstream. Smaller cache sizes may bring very little gain as only extremely popular content will spend significant time in cache.

Much future work remains to be done. The analytical model can be further developed and in particular the nature of the µ parameter needs to be refined to enable direct and fair comparison with simulation models. More features have to be integrated in both the mathematical model and the simulators when mechanisms for the transport layer are clarified in more detail and the router design is further elaborated. This will allow a rich vein of future investigation for this new networking research field.

Fig. 1 .

 1 Fig. 1. Models for a single cache (left) and two caches (right)

Fig. 2 .

 2 Fig. 2. Simulation Topologies: Simple and Extended Tree

Fig. 3 .

 3 Fig. 3. Scenario 1, Topology I -Increasing Content Popularity

Fig. 4 .

 4 Fig. 4. Scenario 1, Topology I -Cache Size

3 .Fig. 5 .

 35 Fig. 5. Scenario 2, Topology II

Fig. 6 .

 6 Fig. 6. Scenario 3: Model Simulator vs ns -2

In fact, CCN[START_REF] Jacobson | Networking Named Content[END_REF] uses the term "message" to refer to both interests (request for data) and "content" (the data itself). Here we are specifically looking at the caching of addressable data messages. Whether multiple packets fit in one "message", or multiple "messages" fit in one packet does not affect much our modelling herein.

⋆ The research leading to these results has received funding from the EU FP7 COMET project -Content Mediator Architecture for Content-Aware Networks, under Grant Agreement 248784.