دانلود رایگان ترجمه مقاله مطابقت پیشوند نام با فیلتر بولوم پیش جستجو برای شبکه محتوا محور – الزویر 2016

تطبيق پيشوند نام با استفاده از پيش جستجوی فيلتر بلوم برای شبکه محتوی محور

Name prefix matching using bloom filter pre-searching for content centric network

1. Introduction

Emerging Internet applications such as social network services largely share image, video, and music files. As large and repeatedly requested contents, this traffic is not efficiently transferred in the current Internet, which has a host-based infrastructure. Content centric network (CCN) is a promising next-generation network designed to solve such issues of the current Internet. The CCN is also known as the information centric network (ICN) or named data network (NDN). While the current Internet uses host-to-host communication based on IP addresses, the CCN performs data communication based on content names (Jacobson et al., 2009; Vasilakos et al., 2015; Bari et al., 2012; Xu et al., 2014; Qiao et al., 2015; Wang et al., 2012; Esteve et al., 2008; Perino and Varvello, 2011). In Jacobson et al. (2009), basic CCN features are implemented and the resilience and the performance of CCN architecture are compared with the host-based communication in terms of file transfer, content distribution, and voice calls. Instead of the concept of source hosts or destination hosts, the CCN uses the concept of content generator and content consumer. Content generators produce contents, and content consumers receive and consume the contents. Routers perform routing using content names instead of IP addresses. Unlike conventional routers, CCN routers have an additional role of caching, which stores contents temporarily, and sends them to consumers requesting the contents. In this way, CCN consumers can rapidly acquire the desired contents, and the same contents are not repeatedly transferred over a network. CCN uses two types of packets: Interest and Data. The Interest is broadcasted by a consumer. The Data is produced by a content generator and transmitted by any node hearing the Interest and having the Data. A CCN router has three different tables: Contents Store (CS), Pending Interest Table (PIT), and Forwarding Information Base (FIB). The CS is a cache storing Data packets. The PIT is used to forward Data packets, and the FIB is used to forward Interest packets. For wire-speed packet forwarding, it is essential to have efficient lookup algorithms that perform the longest name matching for every incoming Interest packet. A trie is an ordered tree-based data structure, the name of which originates from the word retrieval. We differentiate the term trie from the tree as follows. In a trie structure, all the descendants of a node have a common prefix of the string associated with that node, while this is not always true in a tree structure. A name prefix trie (NPT) has been proposed as an extended trie for a name lookup (Wang et al., 2011). The NPT provides an intuitive way for the name lookup with the longest name matching, but has an issue in search performance, since an FIB table can have many millions of content names and each content name can be excessively long. The motivation of this paper is to propose a new approach for the longest name matching used in FIB lookups in CCN routers. The proposed approach is based on the name prefix trie. In order to solve the search performance issue of the NPT, we propose to add an on-chip Bloom filter which is queried before the access to the NPT, which is stored in an off-chip hash table. As a space-efficient probabilistic data structure used to test whether an element is a member of a set, Bloom filters have been popularly applied to network algorithms (Song et al., 2005; Tong et al., 2014; Mun and Lim, 2015; Lim et al., 2014a, 2014b). Since an access to an off-chip memory takes 10–20 times longer than an access to an on-chip memory (Panda et al., 2000), by pre-searching the on-chip Bloom filter, the off-chip hash table storing trie nodes is only accessed when there is a high possibility of a matching entry in our proposed approach. The earlier and shorter version of this paper was presented in (Lim et al., 2015). The performance of our proposed algorithms is evaluated through simulation. Since the format of CCN names is not yet defined, URL names that have hierarchical characteristics similar to CCN names are used for our simulation (Wang et al., 2011). Memory requirements for creating a Bloom filter and storing the NPT are also evaluated. Using inputs with 3 times the number of stored URLs, the search performance is also evaluated. This paper is organized as follows. Section 2 describes related works such as the name prefix trie, previous name lookup algorithms, and the Bloom filter theory. Section 3 introduces the building and searching procedures of the proposed algorithms. Section 4 shows the performance evaluation results, and Section 5 concludes the paper.