Shuo Guo
email: sguo@umn.edu

Haiyong Xie
email: haiyong.xie@ustc.edu

Guangyu Shi
email: shiguangyu@huawei.com

Collaborative Forwarding and Caching in Content Centric Networks

Keywords: content-centric network, name-based routing, collaborative forwarding and caching

Content caching plays an important role in content-centric networks. The current design of content-centric networks adopts a limited, en-route hierarchical caching mechanism, and caching and forwarding are largely uncoordinated. In this paper, we propose a novel collaborative caching and forwarding design. In this design, collaboration is guided by content popularity ranking, based on which we introduce a collaborative forwarding table to allow coordination between caching and forwarding. We also propose a self-adaptive dual-segment cache division algorithm to deal with dynamic inconsistent content popularity. We evaluate our design via extensive simulations and demonstrate that our design improves content access cost and cache miss rate by at least 30% in a diverse network settings.

Introduction

Content caching plays an important role in content-centric networks (CCN) [START_REF] Jacobson | Networking named content[END_REF] or named-data networks (NDN) [START_REF] Zhang | Named data networking (NDN) project[END_REF]. With routers being able to cache contents in such networks, it is likely that not only the content distribution costs incurred to the network but also the quality of service experienced by end users are significantly improved. Internet content caching, especially collaborative caching, has drawn much attention (e.g., [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF][START_REF] Chow | Distributed group-based cooperative caching in a mobile broadcast environment[END_REF][START_REF] Dilley | Globally distributed content delivery[END_REF][START_REF] Fan | Summary cache: a scalable wide-area web cache sharing protocol[END_REF][START_REF] Gadde | Web caching and content distribution: a view from the interior[END_REF][START_REF] Hefeeda | On the benefits of cooperative proxy caching for peer-to-peer traffic[END_REF][START_REF] Korupolu | Coordinated placement and replacement for largescale distributed caches[END_REF][START_REF] Ni | Large-scale cooperative caching and application-level multicast in multimedia content delivery networks[END_REF][START_REF] Sailhan | Cooperative caching in ad hoc networks[END_REF][START_REF] Wolman | On the scale and performance of cooperative web proxy caching[END_REF][START_REF] Yin | Supporting cooperative caching in ad hoc networks[END_REF]) and some have become commercially successful since more than a decade ago. This leads us to believe that collaborative caching in CCN is a key to success in that the network performance could be significantly improved by letting routers collaborate with each other to optimize overall caching performance. Furthermore, forwarding, if coordinated with caching, is likely to further optimize the network performance.

The current design of CCN adopts a hierarchical caching mechanism allowing only limited collaboration in content caching. More specifically, for a given content, caching in CCN takes place only at en-route routers (i.e., routers on the paths between a requesting host and one or multiple content origins), and thus forms a hierarchical caching mechanism. An en-route router that has the requested content will directly respond with the content from its local content store and then suppress further forwarding the request (i.e., Interest) to the next router in the routing hierarchy. With its unique name-based routing architecture and Interest forwarding, CCN advocates a "host-to-content" communication model differing from the "host-to-host" model in Internet. In CCN, where content comes from is no longer important to the requesting host4 . Additionally, not only en-route routers but also routers in the same administrative domain (particularly those nearby en-route routers) could have possibly cached a requested content. These observations suggest that collaborative caching beyond the current limited hierarchical mechanism is feasible and could be beneficial.

However, collaborative caching in CCN, if not well designed, could significantly increase the communication overhead. For instance, control messages exchanged among routers, as an example of such overhead, are necessary to enable collaborations. Such messages normally contain information about what contents are stored in a particular router; due to the enormously large number of distinct contents, such messages could consume a significant portion of the network bandwidth. Additionally, the extra latency of exchanging such messages may further slow down the collaborative decision making process and thus reduce the effectiveness. A naive approach to collaborative caching is to adopt a broadcast mechanism, i.e., each request is forwarded to all routers and only those with the requested content respond with the data. However, such an approach is too costly and inefficient. A key challenge to collaborative caching in CCN is how to make routers know what contents are available from other collaborative routers in an economic and efficient manner. Furthermore, since routers have knowledge about such availability information, routers should leverage it when making forwarding decisions; namely, forwarding and caching should be coordinated and collaborative.

In this paper, we go beyond the en-route caching mechanism and propose a novel name-based distributed collaborative forwarding and caching design (referred to as CFC for short) for content-centric networks. More specifically, collaboration is guided by content popularity, and content popularity is measured distributively by content routers. Each router maintains an Availability Information Base (AIB for short), estimating which content could be available from which router. Each router also generates a popularity ranking sequence periodically through local measurements and propagated such sequences; after aggregating sequences announced by other routers, each router is able to update its AIB and leverage it to optimize forwarding decisions. However, in practice content popularity is likely different when measured from different routers. In order to deal with such inconsistency seen by different routers, we are inspired by the PodNet Project [START_REF] Helgason | Podnet: A system architecture for opportunistic content distribution[END_REF] and propose a self-adaptive dual-segment cache division design, using an additional cache space to handle inconsistent content requests and dynamically adjusting cache division based on different levels of inconsistency.

We summarize our contributions as follows. Firstly, to the best of our knowledge, our popularity-ranking based collaborative forwarding and caching scheme for content-centric networks is the first to coordinate forwarding and caching decisions through the availability information base, allowing us to utilize the information of content popularity ranking to reduce the network cost for cache collaboration. When assuming consistent popularity, we theoretically prove the optimality of our design. Secondly, We propose a novel self-adaptive dual-segment cache design to deal with popularity inconsistency. Thirdly, we evaluate the performance of our design via extensive simulations and demonstrate that our design outperforms the hierarchical caching design significantly.

The rest of the paper is organized as follows: Section 2 summarizes the related work. Section 3 introduces the network model. Sections 4 and 5 present our collaborative caching design, followed by the evaluations in Section 6. Section 7 concludes the paper with future work.

Related Work

In recent years there has been a line of work on emerging future Internet architectures (see, e.g., [START_REF] Anand | XIA: An architecture for an evolvable and trustworthy internet[END_REF][START_REF] Anderson | NEBULA -a future internet that supports trustworthy cloud computing[END_REF][START_REF] Dannewitz | NetInf: An information-centric design for the future internet[END_REF][START_REF] Jacobson | Networking named content[END_REF][START_REF] Zhang | Named data networking (NDN) project[END_REF]). In such architectures, content caching becomes an inherent capability of network elements such as routers. Without specifying the details of content caching, these architectures are designed to allow flexible design and implementation of new caching schemes. However, they also pose new challenges to caching schemes; in particular, it remains unclear how content caching should be provisioned (independently or collaboratively), and how it should be implemented efficiently. To the best of our knowledge, our work is among the first attempts to investigate these issues and provide new insights through comparative evaluations.

There is also a large body of literature on content caching in traditional network architectures (see, e.g., [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF][START_REF] Chow | Distributed group-based cooperative caching in a mobile broadcast environment[END_REF][START_REF] Dilley | Globally distributed content delivery[END_REF][START_REF] Dykes | A vaibility analysis of cooperative proxy caching[END_REF][START_REF] Fan | Summary cache: a scalable wide-area web cache sharing protocol[END_REF][START_REF] Gadde | Web caching and content distribution: a view from the interior[END_REF][START_REF] Hefeeda | On the benefits of cooperative proxy caching for peer-to-peer traffic[END_REF][START_REF] Korupolu | Coordinated placement and replacement for largescale distributed caches[END_REF][START_REF] Ni | Large-scale cooperative caching and application-level multicast in multimedia content delivery networks[END_REF][START_REF] Sailhan | Cooperative caching in ad hoc networks[END_REF][START_REF] Sarkar | Hint-based cooperative caching[END_REF][START_REF] Wolman | On the scale and performance of cooperative web proxy caching[END_REF][START_REF] Yin | Supporting cooperative caching in ad hoc networks[END_REF]). Content caching has been an integral component of Internet-based services for many years, and this has been reflected by the proliferation of content delivery networks (e.g., [3,4,11,27,28,[START_REF] Pathan | Content delivery networks: State of the art, insights, and imperatives[END_REF]). Collaborative caching (or cooperative caching) has been a long-lasting research topic. Researchers have not only investigated the effectiveness of collaborative caching (see, e.g., [START_REF] Gadde | Web caching and content distribution: a view from the interior[END_REF][START_REF] Wolman | On the scale and performance of cooperative web proxy caching[END_REF]), but also proposed numerous collaborative caching schemes for both general networks and networks with specific structures (see, e.g., [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF][START_REF] Chow | Distributed group-based cooperative caching in a mobile broadcast environment[END_REF][START_REF] Erman | To cache or not to cache: The 3g case[END_REF][START_REF] Fan | Summary cache: a scalable wide-area web cache sharing protocol[END_REF][START_REF] Hefeeda | On the benefits of cooperative proxy caching for peer-to-peer traffic[END_REF][START_REF] Korupolu | Coordinated placement and replacement for largescale distributed caches[END_REF][START_REF] Ni | Large-scale cooperative caching and application-level multicast in multimedia content delivery networks[END_REF][START_REF] Sailhan | Cooperative caching in ad hoc networks[END_REF][START_REF] Sarkar | Hint-based cooperative caching[END_REF][START_REF] Yin | Supporting cooperative caching in ad hoc networks[END_REF]); for instance, general Internet-based content distribution (see, e.g., [START_REF] Fan | Summary cache: a scalable wide-area web cache sharing protocol[END_REF][START_REF] Korupolu | Coordinated placement and replacement for largescale distributed caches[END_REF][START_REF] Wessels | Internet cache protocol (icp)[END_REF]), delivering content of special types (e.g., [START_REF] Ni | Large-scale cooperative caching and application-level multicast in multimedia content delivery networks[END_REF]), content caching in networks with special topological structures (e.g., [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF]), and content caching in special networks such as ad hoc networks (e.g., [START_REF] Helgason | Podnet: A system architecture for opportunistic content distribution[END_REF]), content-centric networks (e.g., [START_REF] Carofiglio | Modeling data transfer in content-centric networking[END_REF][START_REF] Psaras | Modelling and evaluation of ccn-caching trees[END_REF][START_REF] Xie | TECC: Towards collaborative in-network caching guided by traffic engineering[END_REF], and peer-to-peer networks (e.g., [START_REF] Hefeeda | On the benefits of cooperative proxy caching for peer-to-peer traffic[END_REF]),

Our work clearly differs from the above work in that we take advantage of the unique properties of content-centric networks, propose the Availability Information Base guided by the popularity ranking sequence to achieve coordinated forwarding and caching for content routers, and propose the self-adaptive dual-segment division algorithm to deal with inconsistent popularity.

Network Model

We consider an autonomous system managed by an administrative domain. The network consists of N content routers. Each router i has a local Content Store (CS) that can cache up to C i content objects ("contents" for short). The size of each content is u at the largest. We assume that content can be chunked into pieces 5 , and each piece fits one cache unit (i.e., the size of each piece is no greater than u). Then, the entire network can cache at most Cu of data, where C = N i=1 C i . Users send requesting packets of "Interest" to their nearest routers (see, e.g., [START_REF] Jacobson | Networking named content[END_REF]).

We use a ranking sequence {r 1 , r 2 , ..., r C } to denote the most popular C contents, sorted in descending order of popularity. This ranking sequence can be measured in real time as routers receive Interests. All routers may not see the same distribution of content popularity; however, we assume that the ranking sequence {r 1 , r 2 , ..., r C } measured by different routers have a certain percentage of mismatches or shifts, refer to as the popularity inconsistency.

In intradomain, topological information, e.g., link status information and link costs between any pair of adjacent routers i and j (denoted by d ij ), is typically distributed by intradomain routing protocols such as OSPF and ISIS. Link costs can correspond to IGP link weights, or other metrics that the contentoriented network cares (e.g., distance, latency). When other metrics are used, they can be distributed across the whole domain via OSPF TLV messages. Other topological information including sizes of Content Stores (C i 's) and the average rate of arriving Interests (Received Interest Rate for short), denoted by I i for router i, can also be distributed in the same way as link costs.

Note that an Interest contributes to a router's Received Interest Rate only if it is sent to this router by a client, rather than another router. We assume that a router can easily distinguish (by, e.g., adding an additional flag bit in the Interest packets) if an Interest comes from a user, or instead from a collaborative router.

Ranking-Based Collaborative Forwarding and Caching

In this section we present our design for the collaborative forwarding and caching scheme.

Overview

We introduce a new component, the Availability Info Base (AIB for short), to allow us coordinate forwarding and caching in content routers, as shown in Fig. 1. AIB keeps track of content availability information. More specifically, AIB can be thought of as a table, where each entry has two columns, Name and RouterID, suggesting that a given named content is available from a router. Note that we assume that each router in the network has a name and routers' names are propagated through the network via intradomain routing protocol such as OSPF. As a result, routers' names are treated in the same way as content names and put in FIB. For instance, the outbound face to reach Router R3 is face 3, and content /c/d is available from R3, as shown in Fig. 1.

Each content router periodically announces the pairwise link cost and collaborative forwarding/caching related metrics via OSPF or ISIS intradomain routing protocols. Each router also measures the ranking of incoming Interests, namely, examine the received Interests from the users, and generates its local ranking sequence of the most popular C contents. Each router implements the collaborative forwarding and caching mechanism, namely, a distributed mechanism to make joint decisions for forwarding and caching. Additionally, each router measures the miss rate of the interests in order to further improve the caching/forwarding efficiency.

Upon receiving an Interest, a router first checks whether the content is available and fresh in its local CS. If yes, the router responds with the locally cached content. Otherwise, it looks up the Pending Interest Table (PIT), and either this Interest should not be forwarded if it is already pending in PIT, or it should be forwarded and PIT be updated accordingly. In the latter case, the router looks up AIB to check whether the content is available from other collaborative routers. If not, the Interest should be forwarded using the default policy in content-centric networks (e.g., look up the outbound face in FIB and forward to the designated face; if FIB lookup fails, use a broadcast-like approach to forward the Interest). Otherwise, the Interest should be forwarded to the designated collaborative router. In order to do so, the router needs to look up FIB to determine the outbound face to reach the designated router. Note that most likely retrieving contents from collaborative routers within an autonomous system saves a noticeable time than getting it from the origin, as the latter typically requires traversing multiple autonomous systems and multiple interdomain links.

Collaborative Forwarding and Caching Mechanism

We next describe the collaborative forwarding and caching mechanism. In our design, each content router keeps track of the most popular C contents. We now assume a consistent popularity model where the most popular C contents at each router results in the same ranking sequence {r 1 , r 2 , ..., r C }; under this assumption, we need to understand how to optimally distribute these C contents in the N caches in the corresponding N routers, whose sizes are C 1 , C 2 , ..., C N , so that the average content access cost can be minimized in the network.

Recall that I i denotes the average number of interests received by router i and d ij denotes the link cost of nodes i and j (d ij becomes the cost of accessing content from the local Content Store when i = j). Such costs can correspond to either intradomain routing weights or other performance-related metrics such as distance and latency. Then, for any cache unit in router i, the average cost of accessing this content requested by users is

costi = N k=1 I k d ki N k=1 I k , (1)
where cost i is the weighted sum of pair-wise access costs from all N routers. The following theorem states how contents should be optimally distributed to minimize the average content access cost: Theorem 1. Suppose the average cost for accessing the content in a cache unit of router i is cost i . Without loss of generality, assume that after sorting, cost 1 ≤ cost 2 ≤ ... ≤ cost N . Also, suppose the ranking sequence is r 1 , r 2 , ...r C in descending order of popularity. Then, the solution that minimizes the average cost of accessing the most popular C contents in the network is to let the more popular content be cached at a place that has a lower cost, i.e., router 1 caches r 1 , ..., r C1 , router 2 caches r C1+1 , ..., r C1+C2 , and so on.

Proof. The proof is straightforward using contradiction. Suppose in the optimal solution that minimizes the average cost of accessing the C most popular contents, there exists two contents r i < r j (r i is more popular than r j ) stored at routers p and q, respectively. Routers p and q follows cost p > cost q . Then, by swapping content r i and r j , we get a smaller average content access cost because the frequency of accessing r i is higher than r j .

Theorem 1 sheds light on how we should design the distributed collaborative mechanism. More specifically, with the help of intradomain routing protocol, topological information is generally available to each router; as a result, each router can calculate {cost i |i ∈ [1, N ]} for all collaborative routers in the network and sort all routers using these values. Following Theorem 1, the most popular contents should be stored by the router with the least cost, and the less popular contents by the router with a larger cost. Therefore, for any top-C popular content, each router knows not only which contents it should keep in its local Content Store, but also which collaborative router it can request this content from, if not locally available. Such availability information for the top-C contents is stored in AIB.

Example 1 We illustrate our design using a simple example shown in Fig. 2. In the example, there are three collaborative routers R1, R2 and R3. These routers can cache 10 contents in total (the size of these three caches are 3, 4, and 3, respectively). The most popular 10 contents measured by these routers are consistent. Suppose cost 1 ≥ cost 2 ≥ cost 3 . Based on Theorem 1, the most popular 3 contents should be cached in router R3, the next 4 contents should be cached in R2, and the next 3 contents should be cached in R1. As shown in the figure, for any incoming Interest requesting for the most popular C contents, AIB tells where it should be forwarded to (the content is either available from the router's local CS or other collaborative routers).

Dealing with Inconsistent Popularity Ranking

In practice, popularity rankings seen by different routers are more likely inconsistent. In such cases, the efficiency of our CFC scheme will be degraded.

Example 2 We illustrate inconsistency in popularity ranking through an example shown in Fig. 3. In this example, router R2's ranking sequence is slightly different from R1's and R3's. In R2's ranking sequence, the positions of content h and f are swapped and content k replaces j. As a result, router R2 caches contents {d, e, h, g}; however, routers R1 and R3 expect that R2 caches {d, e, f, g} instead. Whenever R1 and R3 forward Interests for content f to R2, such Interests have to be further forwarded towards the origin by R2 (not shown in the figure). Similarly, R2 always forwards Interests for content f and k to R1, resulting in cache misses and further forwarding.

To address the above problem resulted by inconsistent popularity, we adopt a dual-segment cache design, namely, divide a router's Content Store into two segments: (1) the Advertised Content Store (ACS for short), denoted by C ′ i , is the regular collaborative cache that is operated the same way as described in the preceding subsection assuming consistent popularity; and (2) the Complementary Content Store (CCS for short), denoted by C ′′ i , is the cache space used for adapting to the inconsistency of popularity distribution. The rationale behind this dual-segment design is to leverage CCS to absorb contents that are supposed to be store at a router but are missing in its ACS due to inconsistent popularity.

Upon receiving an Interest, if the requested content is available locally, the router directly responds with the data. Otherwise, if the Interest comes from another collaborative router, the router forwards the Interest towards the content origin and stores the returned data into its Complementary Content Store when the data comes back; if the Interest comes from a requesting host directly, the router applies its knowledge of popularity-ranking sequence and checks whether the ranking of the requesting content is less than C; If yes, it forwards the Interest to the collaborative router designated by the sequence; otherwise, it forwards the Interest towards the origin.

Example 3 Fig. 4 shows an example of this design for router R2 in the previous example. With the single-segment design shown in Fig. 4(a), content f , which is supposed to be cached in R2, is always missing due to the inconsistency of R2's ranking statistics. However, with the dual-segment design shown in Fig. 4(b), R2 only advertise 3 as its cache size. As a result, an extra cache unit can be used to store the missing content f . Therefore, future Interests requesting for f forwarded from routers R1 and R3 can be fulfilled by R2.

Adaptive Content Store Division

The impact of the preceding dual-segment design on the performance of collaborative forwarding and caching in content-centric networks could be subtle. On the one hand, a sufficiently large CCS is more favorable to adapt to the popularity inconsistency; and on the other hand, when the total size of the Content Store is fixed, a smaller CCS is more favorable, as the ACS could be larger to store more frequently requested contents in the network. Clearly there exist trade-offs when determining their sizes.

A straightforward solution is fixed division of ACS and CCS, e.g., 90% dedicated to ACS and the remaining to CCS. However, the problem of fixed division is one size does not fit all, namely, routers may experience different levels of popularity inconsistency, and a fixed size may either over-estimate or underestimate the inconsistency level, thus resulting an inefficient use of the cache space. This can be observed in the examples in Fig. 3 and Fig. 4. Router R1 and R3 experience less popularity inconsistency than R2 does. In fact, they have no cache misses after R2 switches to the dual-segment cache as shown in Fig. 4. As a result, there is no need to allocate any space for CCS in router R1 and R3.

We note that the cache miss rate plays an important role in the efficiency of dual-segment collaborative caching. On the one hand, when the miss rate is low, it implies a potentially oversized CCS and thus a waste of cache space. On the other hand, when the miss rate is high, then contents supposed to be stored in a designated collaborative router are actually not stored in it, resulting in additional costs to forward Interests to the designated router and then towards the origin.

We design a distributed, self-adaptive algorithm to address the above division problem; specifically, we adjust the division of ACS and CCS based on the dynamics experienced by the content routers. We define the Locking Miss Rate (LMR for short) to characterize the maximum miss rate (corresponding to a maximum level of popularity inconsistency) that a router would like to tolerate. Every router distributively adjusts its size of CCS to make its miss rate closely approach to LMR.

More specifically, a router starts with a pre-configured initial cache division, e.g., 90% for the Advertised and 10% for CCS. It then begins measuring the cache miss rate for all Interests received from other collaborative routers. Recall that the size of ACS and CCS are denoted by C ′ i and C ′′ i respectively. We denote the measured cache miss rate by MR. If MR ≤ LMR, it is likely that the router experiences less popularity inconsistency than expected, we may have an oversized CCS, so the size of CCS C ′′ i is halved so that we increase the size of ACS C ′ i to cache more contents in the network. If MR > LMR, the popularity inconsistency is likely under-estimated; therefore we should reduce the size of ACS to have a larger CCS in order for accommodating the inconsistency. However, instead of reducing the size of ACS C ′ i aggressively, we linearly reduce it and allocate more space to CCS C ′′ i based on the following equation:

C ′ i ← (C ′ i -∆C ′ i ), (2)
where ∆C ′ i is the size reduced by ACS C ′ i and increased by CCS C ′′ i . In this equation, the right hand side is a rough estimation of the number of contents expected to be missed (with the current size of CCS C ′′ i unchanged) after the size of ACS

C ′ i is reduced to (C ′ i -∆C ′ i ).
Ideally, these missed contents are expected to store at the extra space allocated to CCS C ′′ i . With this equation, the percentage the size of ACS C ′ i is reduced can be calculated by

∆C ′ i C ′ i = MR 1 + MR , (3)
And as a result, the new ACS size should be

C ′ i 1+MR
. This algorithm is shown in Algorithm 1.

Algorithm 1 Self-Adaptive Division Algorithm

1: Initialize C ′ i and C ′′ i such that C ′ i + C ′′ i = Ci. 2:
τ is a pre-determined threshold, e.g., τ ∈ [0, 0.5]. 3: while TRUE do 4:

Measure MR for interests from other collaborative routers 5:

if

(MR < (1 -τ ) • LMR ) then 6: C ′′ i ← 0.5C ′′ i . 7: C ′ i ← Ci -C ′′ i . 8: else if (MR > (1 + τ ) • LMR) then 9: C ′ i ← C ′ i /(1 + M R). 10: C ′′ i = Ci -C ′ i . 11:
end if 12: end while

Evaluations

In this section we systematically evaluate the collaborative forwarding and caching design via simulations.

Simulation Setup

Network topologies. We use the pop-level network topology of Abilene [START_REF]Abilene: Internet2 IP IGP Metrics[END_REF] in simulations. Link costs are approximated by the measured end-to-end average latencies using PlanetLab and are in the range of [START_REF] Carofiglio | Modeling data transfer in content-centric networking[END_REF]40]. Note that we also run simulations on other network topologies (e.g., CERNET [START_REF]Cernet: Cernet Topology[END_REF]); however, the results are consistent and thus we omit them here due to space limit. We include two additional nodes to represent content origins in Europe and Asia. For each of these additional nodes, we choose the geographically closest node in each network and connect them. Thus we have a trans-Atlantic link and a Trans-Pacific link. We refer to the topology with these additional nodes and links as the extended topology. In this extended topology, the Trans-Atlantic link cost is 120 and the Trans-Pacific link cost is set to 200. Unless otherwise specified, the cache size of each node is 100 units; we assume contents are chunked into unit-sized pieces, and the total number of content pieces varies from 2000 to 20,000. We assume a 5% LM R by default, and the initial splitting ratio is 90%-10%, i.e., 10% of the cache space is used as the Complementary Cache in the beginning.

Content popularity and requests. To generate inconsistent content popularity distribution, we use a single ranking sequence following the Zipf distribution [START_REF] Breslau | Web caching and zipf-like distributions: evidence and implications[END_REF][START_REF] Cheng | Statistics and social network of youtube videos[END_REF][START_REF] Gill | Youtube traffic characterization: a view from the edge[END_REF] and randomly inject noises to 10% of the contents by shifting them to new positions up to a distance of 100 from their original positions in the sequence. We also evaluate different levels of inconsistency by shifting a different percentage of nodes in the original sequence in Section 6.4.

Interests are generated following the Zipf distribution. The number of interests each router receives directly from users per unit time is randomly chosen from 100 to 500. The adaptive cache division algorithm is run every 50 unit time. The simulation duration in total is 1000 unit time.

Algorithms. We evaluate three schemes using simulations. The first is our collaborative forwarding and caching scheme, referred to as the global collaborative forwarding and caching (GCC). The second is a hierarchical caching approach [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF], denoted as HIE, where nodes are divided into two clusters based on their locations and there are two additional nodes serving as the upper-level caches whose size is three times of the size of lower-level caches. The third is a locally clustered variant of GCC, referred to as the local collaborative forwarding and caching (LCC), where nodes are divided into two clusters (in the same way as HIE) and each cluster run its own GCC independently.

Note that when evaluating these algorithms, all nodes have an identical caching size in order to make the comparison fair. However, due to the extra two upper-level caching nodes, the total cache size of HIE is larger than that of GCC and LCC.

Performance Metrics. We quantify the performance using two metrics. The first metric is the average cumulative link costs of accessing content by a user, referred to as the Average Access Cost. The second metric is the percentage of interests received by each cache that are not fulfilled locally, referred to as the Cache Miss Ratio.

Impacts of Number of Contents

We first quantify the performance by varying the number of delivered contents. Fig. 5 summarizes the results of average content access cost in the Abilene networks. We make the following observations. Firstly, as the number of delivered contents increases, the average access cost increases monotonically. This is because with more contents, the percentage of the contents that can be accessed from caches decreases and more contents have to been accessed directly from content sources, leading to higher costs.

Secondly, our design, GCC, outperforms HIE and cuts the cost by more than 30%. The reason is that GCC can take full advantage of peer caches, while HIE allows only very limited collaboration between the low-tier and high-tier nodes.

Thirdly, the localized collaborative scheme, LCC, enforces a clustered structure, therefore fewer nodes are collaborating with each other, resulting approximately 10% higher cost on average than the global collaborative scheme.

Fig. 6 summarizes the results of average cache miss rate. We observe that with HIE, the cache miss rate increases as the total number of contents increases, and that the miss rates are almost an order of magnitude higher than GCC and LCC. HIE does not use popularity information to guide forwarding and caching; instead, it searches local cache and upper-level cache only. As the number of contents increases, the miss rate increases since the percentage of contents can be stored in cache is limited by the size of cache storage. This explains why we see an increasing curve for HIE. For GCC and LCC, we observe that the miss rates largely remain the same, due to LM R being fixed to 5%.

Impact of Adaptive Cache Division

We next evaluate the impact of the adaptive cache division algorithm. More specifically, we quantify the performance of global and local collaborative caching by varying LMR. Fig. 7 plots the impact of cache adaptation on average access cost. Note that the cost is normalized and the total number of contents is 10000 in this figure. We observe that the best performance can be achieved when LM R is approximately 5%. Note that when LM R is in the range of [0.025, 0.1], the average access cost is within 4% of the best performance, suggesting that the performance of GCC and LCC are not sensitive to LM R.

Fig. 8 plots the results of cache miss rate. We observe an increasing miss rate as LM R increases, however, it increases slower when LM R is larger than approximately 10%. With a larger LM R, the cache division algorithm tries to keep the cache miss rate around LM R, in order to make the most efficient use of the cache space. When LM R increases from 10% to 20%, the cache miss rate only slightly increases because the miss rate is mainly contributed by the inconsistency of content popularity, which is generated by shifting 10% of contents from a given ranking sequence.

Impact of Popularity Inconsistency

We next evaluate the impact on the average access cost when the inconsistency in popularity changes. More specifically, we change the percentage of popularity inconsistency from 1% to 30%, while setting the total number of contents to 10000 and keeping all the other network settings the same as in Fig. 5. We summarize the results in Fig. 9.

We make the following observations. Firstly, the higher the percentage of inconsistency, the higher the average access cost for GCC and LCC. We note that when the percentage of inconsistency is higher, each node allocates larger space to the Complementary Content Store in order to handle requests for contents that are not stored in its Advertised Content Store. The reason these contents are not stored in the Advertised Content Store is that different routers see different sets of contents for a given ranking range. With an increasing percentage of contents shifting from their original positions in the ranking sequence, the union of these different sets becomes larger, leading to a larger Complementary Content Store and a smaller Advertised Content Store, which eventually increases the average content access cost due to the reduced number of unique contents stored in the network.

Secondly, the average access cost of HIE remains almost the same. The reason is that HIE does not rely on consistency of popularity seen by different nodes, and thus is not affected by popularity inconsistency. However, even when the percentage of inconsistency is as high as 30%, GCC and LCC still improve the average access cost by approximately 30%, due to the reason that HIE does not take full advantage of cache available from other routers nearby, leading to an inefficient use of caching.

Conclusion

In this paper we propose a novel distributed, popularity-guided collaborative forwarding and caching design for content-centric networks, where we introduce an Availability Information Base to allow coordination between forwarding and caching in content routers. In order to deal with popularity inconsistency in realistic networks, we also propose a self-adaptive dual-segment cache division algorithm. We evaluate our design via extensive simulations and demonstrate that our design improves content access cost and cache miss rate by at least 30% in a diverse network settings.

There are many avenues to future work. We plan to implement a prototype based on CCNx [1] and conduct medium-to large-scale experiments. This also gives us opportunities to investigate the complexity and feasibility of the proposed framework. We also plan to theoretically model and analyze the impacts of popularity inconsistency on the effectiveness of the proposed design.

Fig. 2 .Fig. 3 .

 23 Fig.2. A design for collaborative forwarding and caching.

Fig. 4 .

 4 An example of cache space division.

Fig. 5 .Fig. 6 .Fig. 7 .

 567 Fig. 5. Average content access cost.

Fig. 8 .Fig. 9 .

 89 Fig. 8. Average cache miss rate vs. LM R.

  Fig. 1. Content router with collaborative forwarding and caching.

	Content Store		Forwarding Info Base	Face 0
	Name ...	Data ...		Name Destination List ... ...
	... /a/b		...	Index Ptr Type	/e/f ... R3 ...	2 ... ... 3	Face 1
				CS
				PIT
				AIB			Face 2
				FIB
	Pending Interest Table		Availability Info Base
	Name ...	Requesting Faces ...		Name ...	... Router ID	Face 3
	/e/f ...		0,1 ...		/c/d ...	R3 ...

CCN architecture has measures to ensure content security, which is beyond the scope of this paper.

Content objects are segmented into pieces in many content-centric networks (e.g.,[START_REF] Jacobson | Networking named content[END_REF][START_REF] Zhang | Named data networking (NDN) project[END_REF]) as well as in many content-oriented overlay networks (e.g.,[7, 18]).

Acknowledgements. This work was partially supported by the National Natural Science Foundation of China under Grant No. 61073192, by the Grand Fundamental Research Program of China (973 Program) under Grant No. 2011CB302905, by the New Century Excellent Talents Program, and by the Fundamental Research Funds for Central Universities under Grant No. WK0110000014.

Availability Info Base

Availability Info Base R3 R1


Udi Ben-Porat

Anat Bremler-Barr

Hanoch Levy
email: hanoch@cs.tau.ac.il

Bernhard Plattner
email: plattner@tik.ee.ethz.ch

On the Vulnerability of Hardware Hash Tables to Sophisticated Attacks

Peacock and Cuckoo hashing schemes are currently the most studied hash implementations for hardware network systems (such as NIDS, Firewalls, etc.). In this work we evaluate their vulnerability to sophisticated complexity Denial of Service (DoS) attacks. We show that an attacker can use insertion of carefully selected keys to hit the Peacock and Cuckoo hashing schemes at their weakest points. For the Peacock Hashing, we show that after the attacker fills up only a fraction (typically 5% -10%) of the buckets, the table completely loses its ability to handle collisions, causing the discard rate (of new keys) to increase dramatically (100 -1, 800 times higher). For the Cuckoo Hashing, we show an attack that can impose on the system an excessive number of memory accesses and degrade its performance. We analyze the vulnerability of the system as a function of the critical parameters and provide simulations results as well.

Introduction

Modern high speed networks pose a challenge for routers, Firewalls, NIDS (Network Intrusion Detection System) or any other network devices that have to route, measure or monitor a network without slowing it down. Such network hardware elements are highly preferable targets for DDoS (Distributed Denial of Service) attacks since their failure can severely slow the network and, in the case of security systems, their failure can allow an attacker to conduct an attack on a critical system they are meant to protect. Equipped with knowledge about how the system works, an attacker can perform a low-bandwidth sophisticated DDoS attack, targeting weak points in the system, rather than just flooding it (which takes more efforts and can be detected and countered more easily).

For example, Crosby and Wallach [START_REF] Crosby | Denial of Service via Algorithmic Complexity Attacks[END_REF] demonstrated attacks on Open Hash table implementations in the Squid web proxy and in the Bro intrusion detection system. They showed that an attacker can design an attack that achieves worst case complexity of O(n) elementary operations per insert operation (instead of the average case complexity of O(1)), causing, for example, the Bro server to drop 71% of the traffic (without increasing the volume of the traffic).

In another example, Smith et al. [START_REF] Smith | Backtracking Algorithmic Complexity Attacks Against a NIDS[END_REF] describe a low bandwidth sophisticated attack on a NIDS system, in which the attack disables the NIDS of the network by exploiting the behavior of the rule matching mechanism and sending packets which require very long inspection times.

Hash tables play an important role in the operations of the most important and time consuming tasks these systems have to perform. Using hashing techniques which allow constant operation complexity is therefore highly desirable. Multiple-choice Hash Tables (MHT), and in particular Peacock [START_REF] Kumar | Peacock Hash: Fast and Updatable Hashing for High Performance Packet Processing Algorithms[END_REF] and Cuckoo [START_REF] Pagh | Cuckoo Hashing[END_REF] Hashing, are easy to implement and are currently the most efficient and studied implementations for hardware network systems such as routers for IP lookup (for example [START_REF] Mitzenmacher | Using Multiple Hash Functions to Improve IP Lookups[END_REF], [START_REF] Song | Fast Hash Table Lookup Using Extended Bloom Filter: An Aid to Network Processing[END_REF] and [START_REF] Waldvogel | Scalable High Speed IP Routing Lookups[END_REF]), network monitoring and measurement (for example, [START_REF] Estan | Building a Better NetFlow[END_REF]) and Network Intrusion Detection/Prevention Systems (NIDS/NIPS) [START_REF] Thinh | Massively Parallel Cuckoo Pattern Matching Applied for NIDS/NIPS[END_REF]. For more information about hardware-tailored hash tables we recommend the recent survey by Kirsch et al. [START_REF] Kirsch | Hash-Based Techniques for High-Speed Packet Processing[END_REF].

A Peacock hash table consists of a large main table (which typically holds 90% of the buckets) and a series of additional small sub-tables where collisions caused during insertions are resolved. Its structure is based on the observation that only a small fraction of the keys inserted into a hash table collide with existing keys (that is, hashed into an occupied bucket) and even a smaller fraction will collide again, etc. These backup tables are usually small enough for their summary (implemented by bloom filters) to be saved on fast on-chip memory which dramatically increases the overall operation performance in Peacock Hashing.

A Cuckoo Hashing is made of two (or more) sub-tables of the same size. Every key can be placed in one bucket (to which it hashes) in each sub-table. When a key k finds all its buckets occupied, one of the keys residing in those buckets is then moved to one of its alternate locations to free the bucket for k. Cuckoo Hashing, therefore, allows achieving a higher table utilization than that achieved by alternative MHT schemes that do not allow moves, while maintaining O(1) amortized complexity of an Insert operation (although the complexity of a single Insertion is not bounded by a constant).

In this work we expose the weak points of the Peacock and Cuckoo Hashing and the system parameters that affect them. To evaluate the vulnerability of Peacock and Cuckoo we refer to [START_REF] Ben-Porat | Evaluating the Vulnerability of Network Mechanisms to Sophisticated DDoS Attacks[END_REF] which observed that an attack on a hash table data structure can damage the performance of the system in two ways: 1. In-attack damage -Insertions of keys that require excessive number of memory accesses; 2. Post-attack damage -Insertion of keys that are placed in the table in a way that causes future insertions of keys to take excessive memory accesses and/or reduce their probability to find an empty bucket. Using this classification, we show that Peacock is resilient against in-attack damage and explain how such an attack can be countered easily. On the other hand we show that it is vulnerable to post-attack damage. We propose a sophisticated attack that can dramatically increase the discard probability of a newly inserted key after the attack has ended. We show that after the attacker inserts keys into the table, it brings the table into an irreversible state in which the discard probability for a newly inserted key can be 100 to 1, 800 times higher than the discard probability after the same amount of keys are inserted by regular users.

For Cuckoo hashing we explain why post-attack damage is irrelevant and analyze its in-attack vulnerability. We show that an attacker can slow the system by inserting keys that require 4 times more memory accesses than regular keys in a typical settings. We further analyze the vulnerability with respect to two key design parameters -the number of sub-tables and the number of moves allowed per insertion; we show that while the utilization in the table increases with either of these parameters, the vulnerability decreases with the former while increases with the latter. In addition to mathematical analysis, we also provide simulation results for a use case in which a system designer plans to design Cuckoo and Peacock hash tables which comply with the same requirements. In addition, we discuss the feasibility of the attack by evaluating the complexity of finding keys suitable for a sophisticated attack and show for both Peacock and Cuckoo Hashing that high number of sub-tables makes it harder for the attacker to find suitable keys.

The structure of the rest of the work is as follows: In Section 2 we explain the nature of sophisticated attacks against hash tables and the Vulnerability metric used in this work. Then, the main body of the work consists of sections 3 and 4 which are dedicated to the Peacock and Cuckoo Hashing, respectively. Both sections have a similar structure. Each is divided into five parts covering the following topics: 1. The hashing algorithm; 2. Attack strategy; 3. Feasibility of the attack; 4. Vulnerability analysis and simulation results and 5. The resilience to in-attack (Peacock) or post-attack (Cuckoo) damage. Finally, Section 5 concludes the key results. In addition, a glossary of the key notations used throughout the work can be found at the Appendix.

Sophisticated Attacks on Multiple Hash Tables

In multiple hash table schemes, such as Peacock and Cuckoo Hashing, every key can be placed only in a small fraction of the buckets. While it allows performing Search and Delete operation with no more than a predefined constant number of memory references, it also poses a challenge: As the load in the table grows, both the insertion complexity (measured by the number of probed buckets) and the discard probability -the probability for an inserted key to not find an available bucket to be stored in -increases. In order to keep these variables bounded by acceptable values, the utilization (maximal load) in the table is limited. Therefore, a simple flooding attack where the attacker simply inserts a large number of (random) keys cannot degrade the system performance beyond its acceptable limits. Note that a flooding attack can be handled by forwarding the keys to another table/device or by blocking the attacker since it can then be detected. Using knowledge about the table, an attacker can perform a sophisticated attack that degrades the system performance beyond its acceptable values (with which it was designed to comply) using just a small number of keys and hence avoid reaching the maximal load in the system.

The vulnerability metric we use in this work has been proposed in [START_REF] Ben-Porat | Evaluating the Vulnerability of Network Mechanisms to Sophisticated DDoS Attacks[END_REF] and is defined as the maximal performance degradation (damage) that malicious users can inflict on the system using a specific amount of resources (budget) normalized by the performance degradation attributed to regular users using the same amount of resources. Formally, according to [START_REF] Ben-Porat | Evaluating the Vulnerability of Network Mechanisms to Sophisticated DDoS Attacks[END_REF], the effectiveness of an attack is defined by

E st (budget = K) = ∆Perf (M st , K) ∆Perf (R, K) , ( 1
)
where ∆Perf (M st , K) and ∆Perf (R, K) are the performance degradations caused by inserting additional K keys to the table (in the context of hash tables) by malicious and regular users, respectively, where st is the attack strategy used by the attacker. Then, the Vulnerability V of a system is defined by the effectiveness of the strategy that causes the maximal damage:

V (budget = K) = max st {E st (K)}. (2)
Therefore, when an attack strategy is not proved to be the optimal, its effectiveness is considered as a lower bound for the vulnerability of the system.

Note that in order to perform the sophisticated attacks analyzed in this work, the attacker is assumed to gain knowledge of the structure of the table (number of tables and their sizes, but not how many keys are already stored in the table and where). In addition, the attacker is assumed to be able to compute or guess the hash values of keys. This knowledge can be achieved by reverse engineering of similar products acquired by the attacker, various guessing methods or due to the use of open source algorithms. For more information see [START_REF] Ben-Porat | Evaluating the Vulnerability of Network Mechanisms to Sophisticated DDoS Attacks[END_REF].

Peacock Hashing

Insertion Algorithm

In Peacock Hashing [START_REF] Kumar | Peacock Hash: Fast and Updatable Hashing for High Performance Packet Processing Algorithms[END_REF] the buckets are divided into d sub-tables {T i } d i=1 and d corresponding hash functions {h i } d i=1 . The sizes of the sub-tables follow a decreasing geometric sequence M i+1 = M i /r where r is the proportion between the table sizes 4 . The first sub-table T 1 is called the main table, while the rest are called the backup tables. T 1 is the largest table and it is where the insertion algorithm first tries to store a key. Every backup table handles the collisions in the sub-table that precedes it. The insertion algorithm probes the sub-tables {T i } d i=1 one after the other until finding a table where the bucket to which the key hashes is free. In the rare case where a key cannot find its place in any of the tables -it is dropped. In addition, a summary of the keys stored in every backup table is maintained (implemented by Bloom filters stored on the on-chip memory). It is used to avoid checking all the sub-tables when making sure an inserted key does not already exist in the table. Note that due to lack of space, in this work we follow the original Peacock and Cuckoo models and exclude the case in which a bucket can hold more than one key; this case is discussed in a technical report [START_REF] Ben-Porat | On the Vulnerability of Hardware Hash Tables to Sophisticated Attacks[END_REF].

Key k h 2 (k) h 1 (k) h 4 (k) d = 4 h 3 (k) T 1 T 2 T 3 T 4 M 1 =8 M 3 =2 M 2 =4 M 4 =1
Fig. After a long series of insertions and deletions (of keys) from the hash table, it becomes unbalanced. That is, the load in the smaller sub-tables is higher than in the bigger tables and this increases the discard probability of a new insertion [START_REF] Kumar | Peacock Hash: Fast and Updatable Hashing for High Performance Packet Processing Algorithms[END_REF]. This state can be prevented by re-balancing the table after a key is deleted as follows. After a key was deleted from bucket b in T i , if there is a key k that is stored in T j>i such that h i (k) = b, then k is moved back from T j to the now-free bucket in T i . The attack we propose and analyze below brings the hash table to an unbalanced state that cannot be solved by re-balancing (unlike a natural unbalanced state that occurs over time).

Post-Attack Damage: Attack on Peacock Hashing

As already explained, [START_REF] Kumar | Peacock Hash: Fast and Updatable Hashing for High Performance Packet Processing Algorithms[END_REF] showed that when the keys are concentrated in the backup tables (the table is unbalanced) the discard probability increases. The malicious user can artificially create an extreme case of this scenario by flooding the backup tables. A simple example of such an attack can be done by inserting K keys that all hash into the same bucket b at T 1 . Every inserted key (except possibly for the first one) will collide with an existing key in b and then, according to the insertion algorithm, will be rehashed into a bucket in one of the backup tables. After the attack has ended the table is unbalanced, because the keys inserted by the malicious user are concentrated in the backup table while almost none are in the main table. This causes Post-Attack damage, measured by the increase in the discard probability.

Normally, Peacock hash table maintains a desired low discard probability by limiting the maximal load in the table. Nevertheless, an attacker using the above sophisticated attack algorithm can cause the discard probability to exceed its desired value by inserting only a small number of keys that do not cause the table to reach its maximal load. Unlike a Peacock table which became unbalanced naturally, a re-balancing routine cannot bring items back into the main table after such an attack, because the bucket to which they all hash in T 1 can contain only one of them but not all. So not only the table becomes unbalanced, there is also no way to re-balance it until the keys are flushed out from the table or the table is reconstructed with a new set of hash functions 5 .

Denote the set of buckets to which a key is hashed in all sub-tables as the pool of the key in the table. The insertion algorithm discards a new key only if all the buckets in its pool are already occupied. Every key is hashed into one bucket in each table, therefore, a bucket b in a table of size M i , belongs to the pools of 1/M i of the keys in the key space. In simple words, a key placed in a high table T i "gets in the way" of more potential keys than if it was placed in a bucket in a lower table T j (j < i) (since 1/M i > 1/M j ). Therefore, the basic idea behind the attack is to insert keys that will be placed in the upper tables. Following is the formal description of the attack algorithm, generalizing the simple attack described earlier. An attack in depth j is an attack to which the attacker inserts keys that not only hash into the same bucket in T 1 , but also hash into the same buckets in T 2 , ..., T j . This will lead to the flooding of the most upper tables T j+1 , ..., T d . That is, the simple attack we described above is an attack in depth 1. Due to lack of space, the complexity of finding the keys is excluded from this work (and can be found in [START_REF] Ben-Porat | On the Vulnerability of Hardware Hash Tables to Sophisticated Attacks[END_REF]). Note just that for large tables (M ) and for deeper attacks (larger j) -it is harder for the attacker to find the keys for the attack.

Post-Attack Damage: Vulnerability of Peacock Hashing

We use the Vulnerability factor (described in Section 2) to measure the proportion between the increase in the discard probability caused by additional keys inserted by an attacker and regular users. Let DP I , DP R and DP A ('I' -Initial, 'R' -Regular, 'A' -Attacker) be the expected discard probabilities of newly inserted keys at the following states: 1. DP I -when the load in the table is α, before any additional key is inserted; 2. DP R -after K regular (random) additional keys were inserted; 3. DP A -after K additional keys were inserted by a sophisticated attacker. Note that due to their length, we exclude from this work the proofs and the full discussion of the following claims and they can be found in our technical report [START_REF] Ben-Porat | On the Vulnerability of Hardware Hash Tables to Sophisticated Attacks[END_REF].

Lemma 1. The drop probability after regular key insertion is approximated by

DP R (K) ∼ (α + R IN /M ) d , ( 3
)
where

R IN = ∑ K s=1 p s , p 1 = 1 -α d and p i = 1 -(α + ∑ i-1 s=1 p s /M ) d .
Lemma 2. The drop probability after a sophisticated attack is approximated by

DP A (K) ∼ [ j ∏ l=1 (α + (1 -α)/M l )](α + A IN /M ′ ) d ′ , ( 4
)
where

A IN = ∑ K ′ s=1 p ′ s , K ′ = K -⌊(1 -α)j⌋, M ′ = ∑ d i=j+1 M i , d ′ = d -j, p ′ 1 = 1 -α d ′ and p ′ i = 1 -(α + ( ∑ i-1 s=1 p ′ s )/M ′ ) d ′ .
Theorem 1. The vulnerability of the discard probability is given by

V DP (K) = DP A (K) -DP I DP R (K) -DP I , ( 5
)
where

DP I = α d .
R IN (Eq. 3) and A IN (Eq. 4) can be roughly described as the number of keys that remain in table after the K keys were inserted by regular users and an attacker, respectively. Practically, the values of R IN and A IN are very close to each other and to K. The major factor that makes the value of DP A (K) (Eq. 4) significantly higher than DP R (K) (Eq. 3) is that R IN is divided by M while A IN is divided only by M ′ . This is because keys inserted by attacker are spread among the M ′ of the attacked backup tables while keys inserted by regular users are spread among all the M buckets in the table. Since

M i = r d-i , M ′ = ∑ d i=j+1 M i is only a small fraction of M = ∑ d i=1 M i
and this is the major factor behind the differences between DP A (K) and DP R (K) as seen in Figure 2(a).

Evaluation of the Vulnerability and the Analysis:

To evaluate the vulnerability of the system as a function of the system parameters and to evaluate the quality of the approximations (lemmas 1 and 2) we next conduct a set of simulations. The simulations we conducted follow a scenario in which the system designer examines the option of using Peacock Hashing for hardware that can support approximately 10 5 buckets in the table. Building a table consisted of d = 5 sub-tables with sub-tables proportion of r = 10 results in a table of size M = 11, 111 buckets. As mentioned before, in Peacock Hashing (as well in Cuckoo Hashing and other modern hashing schemes) the probability for a key to be dropped during an insertion increases with the load in the table. Therefore, the maximal load in the table is decided by the Acceptable Loss Fraction, that is, the maximal percentage of inserted keys that the system can afford to lose. It is important to note that Discard Probability (Figure 2(a)) that is used to measure the vulnerability and Loss Fraction that is used to set the maximal load are two different metrics. Discard Probability measures the probability to drop an inserted regular key after additional keys were inserted by malicious or regular users while Loss Fraction measures the percentage of the inserted (regular) keys that are dropped during an insertion and is used to set the maximal load of the table. In this example, we assume that the desired maximal Loss Fraction allowed is 1%. Our simulations showed that such a Peacock table with d = 5, r = 10 and M = 11, 111 is suitable for the insertion of up to 0.3M = 3, 333 keys (the table utilization is 30%) before exceeding loss fraction of %1.

In the simulations, the attack was conducted on a table with an existing load α = 0.1 and the attack by the malicious user is in depth j = 1. Recall that an attack in depth j = 1 on target the upper 4 tables that hold together only 1, 111/11, 111 = 9.9% of the buckets that some of which are already occupied prior the attack. Therefore, an attacker would insert no more than 10% of additional load. Therefore, the range of the x-axis in Figures 2(a) and (b) was chosen accordingly. Note that the additional 0.1 load together with the existing load α = 0.1 does not exceed the maximal load in the table which is 0.3. We can see in Figure 2(a) that when the additional load is 7%, the discard probability remains very low (below 0.1%), while the sophisticated attack causes the discard probability to increase to values between 5.5% (when the additional load is 0.07) and 7.2% (when the additional load is 0.1), a discard probability that is achieved by regular insertions only with load which is 3.5 times larger. In addition we can see that, as expected, the approximation curves in Figure 2(a) reflect the behavior of DP R and DP A although do not imitate them precisely (see [START_REF] Ben-Porat | On the Vulnerability of Hardware Hash Tables to Sophisticated Attacks[END_REF] for more details).

We can see a significant difference in the discard probability after a malicious attack and after regular insertions. This difference is expressed by the extremely high vulnerability values, depicted in Figure 2(b), where the results show that the discard probability after the attack has ended caused by the attacker is between 100 and 1, 800 times larger than the discard probability after the insertion of the same load of keys by regular users. This drives the discard probability of the hash table far beyond the discard probability in which it is assumed to be operating. This result emphasizes the fundamental vulnerability of Hashing schemes, such as the Peacock Hashing, that dedicate specific range of buckets (the upper sub-tables) for collision resolution.

Resilience to In-Attack Damage (and Improving Performance Using Bitmaps)

As already mentioned in Section 1, we analyze an attack focused at creating post-attack damage. We avoided analyzing attacks aiming at in-attack damage by inserting keys that require excessive number of memory accesses during the attack, since we believe such attacks can be countered easily. Our suggestion is to keep a bitmap summary of the occupied buckets for every backup table. Since the total size of the backup tables is small (about 10% of M when r = 10), these bitmaps are compact enough to be stored in the fast on-chip memory.

Hence, the complexity of accessing a key is negligible. Then, when handling an insertion of a new key which cannot find its place in the main table, its final bucket (in a backup table) can be found directly by checking its hash values against the fast bitmap summary. This way, no insertion has to probe more than two buckets (one in the main table, and one in the final destination). Note that it will not cause a mistaken insertion of a key that already exists, since (as mentioned earlier) in addition to the bitmap summary, there are also on-chip key summaries (commonly implemented in bloom filters [START_REF] Kumar | Peacock Hash: Fast and Updatable Hashing for High Performance Packet Processing Algorithms[END_REF]) which are used to make sure the key does not already exist in the sub-tables (before checking the bitmap summary to locate a free bucket for the key).

Cuckoo Hashing

Algorithm Description

According to the original definition by and Rodler [START_REF] Pagh | Cuckoo Hashing[END_REF] a Cuckoo hash table is made of two sub-tables, equal in size. Every key k hashes into one bucket in each of them using two hash functions h 1 (k), h 2 (k). If during an insertion, both of the possible buckets are occupied, the key is placed in one of them, causing the key placed in the occupied bucket to move to its alternative bucket in the same manner. Therefore, every insertion of a new key consists of a series of one or more moves. The complexity of a new insertion is measured by the number of moves it triggers. The expected complexity of an insertion is proved to be bounded by O(1) as long the maximal capacity of the table is not reached. Figure 3 depicts an example of an insertion of k 2 into a Cuckoo hash table with 4 sub-tables. When k 2 is inserted, the buckets into which it hashes (dark left arrows) are all occupied. Then, the insertion algorithm chooses to eject k 1 (from T 4 ) and place k 2 in its place. k 1 is then relocated to an alternative free bucket to which it hashes in T 3 . Note that as already explained in Section 3.1, we discuss the model in which a bucket can hold only one key.

For the original Cuckoo hash table consisting of two sub-tables, Pagh and Rodler [START_REF] Pagh | Cuckoo Hashing[END_REF] showed that the complexity of an insertion is O(1 + 1/ϵ) where M = 2N (1 + ϵ), M is the total number of buckets (in both tables) and N is the maximal number of keys the table is meant to hold. In [START_REF] Fotakis | Space Efficient Hash Tables With Worst Case Constant Access Time[END_REF]

M = (1 -ϵ)N buckets d = 4 T 1 T 2 T 3 T 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 k1

Key k 1 Key k 2 Movement of k 1 when inserting k 2 h 2 (k 2 ) h 2 (k 1 ) h 1 (k 2 ) h 3 (k 2 ) h4(k2) h1(k1) h3(k1) h 4 (k 1 )
Fig. 3. A move of key k1 during the insertion of k2 into a Cuckoo hash table with 4 sub-tables. The white (right) and the dark (left) arrows mark the hash values of k1 and k2 in the different sub-tables, respectively.

for any constant ϵ > 0. They showed that Search and Delete operations take6 O(ln(1/ϵ)) and proved the generalized Cuckoo Hashing has a constant amortized insertion time. Following [START_REF] Fotakis | Space Efficient Hash Tables With Worst Case Constant Access Time[END_REF], Frieze and Mitzenmacher [START_REF] Frieze | An Analysis of Random-Walk Cuckoo Hashing[END_REF] suggested a more efficient insertion method with a polylogarithmic upper bound. In later studies (such as [START_REF] Frieze | An Analysis of Random-Walk Cuckoo Hashing[END_REF], [START_REF] Fotakis | Space Efficient Hash Tables With Worst Case Constant Access Time[END_REF] and [START_REF] Kirsch | The Power of One Move: Hashing Schemes for Hardware[END_REF]) different insertion algorithms have been proposed. They mainly differ in the way they choose the key that will be relocated (in order to free a bucket for an inserted key that all his possible d locations are occupied). Note that the attack efficiency is independent of the way the key (to be moved) is chosen, hence we do not discuss here the variations of the insertion algorithm and for our work one can assume the moved key is chosen randomly. In addition, since the exact insertion complexity of the various insertion algorithms is not fully analyzed, we use the fact that it is proved to take an amortized O(1) time when we approximate the vulnerability. In addition, we use simulations to give precise results for selected examples.

In-Attack Damage: Attack on Cuckoo Hashing

The basic idea behind the attack is to insert K keys that all hash into the same small set of buckets B, such that K > |B|. Except for the first |B| keys, every attack key causes an insertion loop in which every move triggers another. Formally, the attacker inserts K keys such for every key k, {h i (k)} d i=1 ⊂ B where B is a set of buckets such that K > |B|. Such attack creates insertion loops and cause the insertion algorithm to require excessive number of memory accesses. Note that the size of B can be is as low as d (when B contains exactly one bucket from each sub-table) but a large bucket set B allows the attacker to find keys for the attack more easily. Note that a general algorithm that will detect every possible loop can be proved impractical, especially in hardware. Therefore, the most popular approach to address this issue is to limit the number of moves to a predefined fixed value W since their vast majority is very low 7 .

In our technical report [START_REF] Ben-Porat | On the Vulnerability of Hardware Hash Tables to Sophisticated Attacks[END_REF] we describe the algorithm used by the attacker to find the keys for the attack and its complexity is analyzed. Our main result on this subject is that it is harder to find Cuckoo attack keys than to find the Peacock attack keys 8 . However, on the other hand, in contrast to the Peacock attack, the attacker can use the same keys over and over again and sustain his attack until it is mitigated, if at all.

In-Attack Damage: Vulnerability of Cuckoo Hashing

Using the vulnerability measure described in Section 2, we now evaluate the system vulnerability due to new-key insertion complexity (measured by the number of moves it triggers). Let IC R and IC A ('R' -Regular, 'A' -Attacker) denote the overall number of operations performed during the insertion of K keys, by the attacker and by regular users, respectively. Note that regardless of the strategy of the attacker, the vulnerability cannot exceeds W (V IC(K) = ICA(K) ICR(K) ≤ W ) since trivially IC R (K) >= K and since the system enforces IC A (K) <= KW .

Theorem 2. The system vulnerability due to insertion complexity is

V IC(K) = IC A (K) IC R (K) = |B|/K + (1 -|B|/K) W c , (6)
where c ≥ 1 is the average time complexity of a regular key insertion and B is the group of buckets into which all the attack keys hash.

Proof. Since the insertion time of a random regular key has an amortized O(1) complexity we can conclude that IC R (K) = Kc where c ≥ 1 is a constant (very close to 1 in practice) denoting the insertion complexity of a random key. The first |B| keys inserted by the attacker might not cause insertion loops since they all can possibly find an empty bucket. Therefore the complexity of their insertion is |B|c. Each of the remaining K -|B| keys inserted by the attacker triggers an insertion loop that is terminated only after W moves. Then IC A (K) = |B|c + (K -|B|)W . To conclude, the values of IC R (K) and IC A (K) lead to the result in Eq. 6.

⊓ ⊔

Evaluation of the Vulnerability and the Analysis: In the same way as we did for Peacock Hashing, we aim to construct (and then attack) hash table that can hold up to 3333 keys with an Acceptable Loss Fraction of 1%. As a system designer would do, we used simulations to measure the loss fraction with different values of d, W and M and decided to use a system with d = 3, W = 4 and M = 6000. Note that higher values of d and W allow higher utilization of the table 9 . That is, smaller value of M is required in order to accommodate up to 3333 keys with the required loss fraction. Figures 4(a) and 4(b) depict the simulation results on a table with (arbitrarily chosen) existing load of α = 0.1. The x-axis in both figures corresponds to the additional load of keys that was added to the table. The x-axis ends at 0.45 since the maximal allowed load in the table is 3333/6000 = 0.55% (and it already contains 0.1).

According Theorem 2 the vulnerability is mainly defined by W/c (since |B|/K is expected to be very small, especially when |B| = d). Note that using c = 1 gives an upper bound on the estimated vulnerability which is then approximated by W . As we can see in Figure 4(a), the lower curve which depicts IC R (K)/K (the average complexity of regular insertion) -c is indeed very close to 1 in the simulation results. Therefore, as also shown in Figure 4(b), setting the moves limit W practically decides the vulnerability of the system. In addition, one can observe that, unlike Peacock Hashing, in Cuckoo Hashing the size of the table M has no role in the vulnerability (Theorem 2).

The following table summarize the results so far, including those from the attack feasibility analysis which is excluded from this paper and can be found in a technical report [START_REF] Ben-Porat | On the Vulnerability of Hardware Hash Tables to Sophisticated Attacks[END_REF]. The arrows marks how different properties of a Cuckoo hash table are affected when increasing W , d and M . ⇑, ⇓ and ⇔ mark that a property is increased, decreased or do not chance (respectively).

High W High d High M Table Utilization ⇑ ⇑ ⇓ Vulnerability ⇑ ⇓ ⇔ Attack Feasibility ⇔ ⇓ ⇓
As explained above, from the efficiency point of view the system designer has to choose between higher complexity of the hash operations (high values of d and W ) and lower utilization (large M ). Our work, shows through the above analysis and simulation results the security implications of setting W and d. The results show that W is a key factor in the vulnerability of Cuckoo Hashing. Therefore, from the vulnerability point of view, it is preferable to increase the number of sub-tables d in order to keep the moves limit W as low as possible. Increasing d not only decreases the vulnerability but also decrease the feasibility by forcing the attacker to invest more effort in finding a suitable attack keys set (see [START_REF] Ben-Porat | On the Vulnerability of Hardware Hash Tables to Sophisticated Attacks[END_REF]).

Resilience to Post-Attack Damage

There is no general way to cause post attack damage (In contrast to Peacock Hashing, see Section 3.2) since there is no specific layout of elements in the table that Cuckoo is vulnerable to more than other; This is true since it is impractical to assume the attacker knows where new keys will hashed to after the attack has ended.

Summary

In this work we exposed the weak points of the Peacock and Cuckoo Hashing. We showed that Peacock is resilient against in-attack damage. Nevertheless, we showed that it is highly vulnerable to an attack that aims at driving the system to high post-attack discard rates; such an attack can increase these rates by a factor of 100-1, 800 in comparison to normal behavior. For Cuckoo hashing we showed that an attacker can slow the system by inserting keys that require 4 times more memory accesses than regular keys in a typical settings. We also provided simulation results for a use case in which a system designer plans to design a Cuckoo and Peacock hash tables which comply with the same requirements.

Fig. 2 .

 2 Fig. 2. Figure (a): The discard probability after insertions by regular (DPR) and malicious (DPA) users as a function of the load they add (K/M ). Figure (b): The vulnerability simulation results (V ) of a table with proportion r = 10 and d = 4 with an existing load of 10% as a function of the additional load.

  Fotakis, Pagh et al. generalized Cuckoo Hashing to d-ary Cuckoo Hashing where d ≥ 2 sub-tables are used. They showed how N keys can be stored in

Fig. 4 .

 4 Fig. 4. Plot (a): The average insertion complexity of keys inserted by an attacker ICA(K)/K and a regular user ICR(K)/K in a system with W = 4. Plot (b): The vulnerability (V = ICA(K)/ICR(K)) as a function of the additional load (K/M ). In both plots the existing load is α = 0.1.

In[START_REF] Kumar | Peacock Hash: Fast and Updatable Hashing for High Performance Packet Processing Algorithms[END_REF] the authors recommended to use r = 10.

Which if possible at all, will undoubtedly consume a huge amount of resources.

Their experiments showed that 4 probes suffice for ϵ ≈ 0.03.

W suppose to be set to alog(n) where n is the number of keys the table can hold and a is appropriately chosen constant[START_REF] Frieze | An Analysis of Random-Walk Cuckoo Hashing[END_REF].

Since keys have to hash to the same buckets in all sub-tables.

However, high values of d and W also increase the complexity of the different operations in the table.

A Appendix

Glossary of Notations