Named data networking (NDN) is a future Internet architecture that directly emphasizes accessible content by assigning each piece of content a unique name. Data transmission in NDN is realized via ...name-based routing and forwarding. Name-based forwarding information base (FIB) usually has much more and longer prefixes than IP-based ones, and therefore, name-based forwarding brings more challenges on the NDN router in terms of high forwarding throughput, low memory consumption, and fast FIB update. In this paper, we present an index data structure called BFAST for the name-based FIB. BFAST is designed based on a basic hash table, it employs a counting Bloom filter to balance the load among hash table slots, so that the number of items in each non-empty slot is close to 1, leading to low searching time in each slot. Meanwhile, the first-rank-indexed scheme is proposed to effectively reduce the massive memory consumption required by the pointers in all the hash table slots. Evaluation results show that, for the longest prefix match FIB lookup, BFAST achieves a speed of 2.14 MS/S using one thread, and meanwhile, the memory consumption is reasonably low. By leveraging the parallelism of today's multi-core CPU, BFAST arrives at an FIB lookup speed of 33.64 MS/S using 24 threads, and the latency is around 0.71 μs.
Collapsed forwarding has long been used in cache systems to reduce the load on servers by aggregating requests for the same content. Named Data Networking (NDN) as a future Internet architecture ...incorporates this technique through a data structure called Pending Interest Table (PIT). The request aggregation feature suggests that PIT can be viewed as a nonreset time-to-live (TTL) based cache. The Content Store (CS) is a content cache placed in front of the PIT on the NDN forwarding path, so they make up a tandem cache network. To investigate the metrics of interest in this network, like the hit probability for the PIT and the CS, the expected PIT size, non-zero download delay (non-ZDD) should be taken into consideration. Caching policies usually assume zero download delay (ZDD), i.e., request and object arrive simultaneously, and numerous analytical methods have been proposed to study the ZDD caching policies. In this paper, after dissecting the LRU policy, we for the first time propose two LRU variants considering non-ZDD by defining separate operations for the request and object arrivals. When CS adopts the proposed LRU variants, the analysis of the CS-PIT network can still take advantage of the existing models, so the metrics of interest can be computed. Especially, the distribution for the "inter-miss" time of this network can be derived, which has not been achieved by prior works. Finally, the analytical results are verified through simulations.
Named Data Networking (NDN) as an instantiation of the Content-Centric Networking (CCN) approach, embraces the major shift of the network function - from host-to-host conversation to content ...dissemination. The NDN forwarding architecture consists of three tables - Content Store (CS), Pending Interest Table (PIT) and Forwarding Information Base (FIB), as well as two lookup rules - Longest Prefix Match (LPM) and Exact Match (EM). A software-based implementation for this forwarding architecture would be low-cost, flexible and have rich memory resource, but may also make the pipelining technique not readily applicable to table lookups. Therefore, forwarding a packet would go through multiple tables sequentially without pipelining, leading to high latency and low throughput. In order to take advantage of the software-based implementation and overcome its shortcoming, we find that, a single unified index that supports all the three tables and both LPM and EM lookup rules would benefit the forwarding performance. In this paper, we present such an index data structure called BFAST (Bloom Filter-Aided haSh Table). BFAST employs a Counting Bloom Filter to balance the load among hash table buckets, making the number of prefixes in each non-empty bucket close to 1, and thus enabling high lookup throughput and low latency. Evaluation results show that, for solely LMP lookup, BFAST can arrive at 36.41 million lookups per second (M/s) using 24 threads, and the latency is around 0.46 μs. When utilized to build the NDN forwarding architecture, BFAST obtains remarkable performance promotion under various request composition, e.g., BFAST achieves a lookup speed of 81.32 M/s with a synthetic request trace where 30% of the requests hit CS, another 30% hit PIT and the rest 40% hit FIB, while the lookup latency is only 0.29 μs
NDN enables routers to cache received contents for future requests to reduce upstream traffic. To this end, various caching policies are proposed, typically based on some notion of content ...popularity, e.g., LFU. But these policies simply assume the availability of content popularity information without elaborating how that information is obtained and maintained in routers. Towards line-speed and accurate on-line popularity monitoring on NDN routers, we propose a Bloom filter-based method to continuously capture content popularity with efficient usage of memory. In this method, multiple Bloom filters are employed and each one is responsible for a particular range of popularity. Content objects whose popularities fall into a Bloom filter's range will be inserted into that Bloom filter. Meanwhile, a sliding window monitoring scheme is proposed to implement more frequent and real-time update of the popularities. Moreover, we put forward three optimization schemes to further speed up the monitoring operations. Using a real trace stored in off-chip memory as input and setting the monitoring time window to 30 min, this method achieves a monitoring speed of 20.92 million objects per second (M/s) with multiple threads. This speed is equivalent to 16.74 Gbps throughput assuming the content length is 100 Bytes in average, but only consumes around 32 MB memory. By simulating the environment on the line card using a real-time generated synthetic trace, this method even reaches a speed of 251.07 M/s (equivalent to 200.86 Gbps) because the trace is fetched from high speed on-chip memory, rather than the off-chip DRAMs. Furthermore, both theoretical and experimental analyses elucidate very low relative error of this method. At last, a real trace-driven comparison shows that LFU policy achieves higher hit rate than LRU with much less unnecessary cache replacements.
Fast name lookup for Named Data Networking Yi Wang; Boyang Xu; Dongzhe Tai ...
2014 IEEE 22nd International Symposium of Quality of Service (IWQoS),
05/2014
Conference Proceeding
Complex name constitution plus huge-sized name routing table makes wire speed name lookup a challenging task in Named Data Networking. To overcome this challenge, we propose two techniques to ...significantly speed up the lookup process. First, we look up name prefixes in an order based on the distribution of prefix length in the forwarding table, which can find the longest match much faster than the linear search of current prototype CCNx. The search order can be dynamically adjusted as the forwarding table changes. Second, we propose a new near-perfect hash table data structure that combines many small sparse perfect hash tables into a larger dense one while keeping the worst-case access time of O(1) and supporting fast update. Also the hash table stores the signature of a key instead of the key itself, which further improves lookup speed and reduces memory use.
Per-flow measurement can provide fine-grained statistics for advanced network management and thus has been studied extensively. As network line rate continues its rapid growth, wire-speed per-flow ...measurement meets great challenges, for large numbers of statistics counters are required to record flow information at extremely high speed. Most of the previous efforts are committed to elaborate excellent sampling algorithms to make counters' memory occupation as small as possible, so as to fit into off-chip SRAM(s), but the throughput is rigidly bounded by the speed of SRAM. To break the wall, we explore a new path by proposing CASE: a cache-assisted stretchable estimator, which uses the on-chip memory as the fast cache of the off-chip SRAM. In this way, most of the accesses to the counters will happen on cache, thanks to the heavy-tailed distribution of Internet traffic. In this paper, we present CASE's design and derive strict mathematical proof to its relative error bound. Extensive experiments on real-world traces are conducted and the evaluation results indicate CASE can achieve up to 300Gbps throughput when using on-chip memory with 128K entries (equivalent to 1.125MB). Meanwhile CASE is more accurate and stretchable than uncached approaches.
In Mobile Edge Computing (MEC), offloading tasks from mobile devices to edge servers may accelerate the processing speed and save the energy of the devices, hence improving device users’ quality of ...experience. Recently, reinforcement learning (RL) is increasingly used for offload decision making. RL seeks long-term cumulative benefits and is proved useful for a sequence of decisions, thus is well suited for the work. Due to privacy and security concerns, mobile devices may be unwilling to expose their local information, leading to a fully decentralized MEC environment. Independent RL (IRL) emerges as a promising solution for this scenario. However, IRL solutions are faced with the non-stationarity issue, which arises when the components are changing their policies. In this paper, we proposing adopting the Neural Fictitious Self-Play (NFSP) architecture for offload decision making. NFSP explicitly tackles the non-stationarity issue with the built-in self-play mechanism, and uses a mixed strategy consisting of deep RL and the past average strategy, which is approximated by supervised deep learning. Furthermore, we use the Proximal Policy Optimization (PPO) algorithm as the RL component and exploit the Gated Recurrent Unit (GRU) to deal with the partial-observability issue in fully decentralized MEC. We conduct extensive simulation experiment, the result of which shows that our method outperforms the raw IRL approaches, validating the effectiveness of our proposed method.
•Apply the Neural Fictitious Self-Play to task offloading in Mobile Edge Computing.•Deal with the non-stationarity and partial-observability issues.•Modify the original NFSP through adopting PPO and GRU.•Extensive experiment where D3QN, PPO, and GRU enhanced PPO are compared.
In this letter, we propose an efficient federated transfer learning (FTL) framework with client selection for intrusion detection (ID) in mobile edge computing (MEC). Specifically, we leverage ...federated learning (FL) to preserve privacy by training model locally, and utilize transfer learning (TL) to improve training efficiency by knowledge transfer. For FL, unreliable and low-quality clients should not be selected to participate in the training. Therefore, we integrate FTL with a reinforcement learning (RL)-based client selection scheme to achieve the highest ID accuracy within a budget limit on the number of participating clients. Experimental results show that the FTL significantly improves ID accuracy and communication efficiency as compared with the FL. Furthermore, the FTL framework with RL-based client selection can achieve the highest accuracy within budget, which improves performance while saving cost.
Internet has evolved to be content-oriented and its key usage focuses on content dissemination and retrieval, while Internet architecture is designed for host-oriented services. To address the ...challenge, Named Data Networking (NDN) has been proposed, where in-network caching becomes a new research topic due to its dominant position in NDN architecture. This work develops efficient caching schemes for Internet Service Providers (ISPs) so as to maximize the inter-ISP traffic savings. With the special goal, we design caching system according to the NDN network model and present coordinated caching algorithms which can dynamically determine cache placement along the forwarding path. Comprehensive simulation results show that our schemes outperform the widely used Leaving Copies Everywhere (LCE) both in inter-ISP traffic savings and the average number of access hops by up to 20%. In addition, we demonstrate good feasibility of the proposed caching algorithms in a set of simulations spanning a wide range of parameter values.
The virtual network embedding problem is embedding virtual networks (VNs) in a substrate network so that revenue or accept ratio is maximized. Previous study usually assumes disclosed communication ...demand among the virtual nodes in a VN, mismatching real-world cloud computing scenarios. In this paper, we propose a new VN abstraction based on the widely used Virtual Private Cloud model, where internal communication demand is unknown to cloud providers. In contrast with the majority of existing research, we allow the co-location of the virtual nodes belonging to the same VN, and introduce the concept of switching capacity for practical resource reservation. We categorize the substrate resources in cloud data centers into additive and non-additive for the first time, and devise our algorithms accordingly. After formulating the problem, we propose a solution framework named HA-D3QN (Heuristic Assisted Dueling Double Deep Q Network). Essentially, HA-D3QN selects the best responses to different system states by combining the D3QN deep reinforcement learning structure and the candidate actions, which are generated by our proposed heuristic algorithms for addressing the exponentially large action space. Finally, we conduct extensive simulation experiments, the results of which verify the effectiveness of our approach.
•Propose a novel virtual network abstraction based on Virtual Private Cloud.•Introduce the concept of switching capacity for practical resource estimation.•Categorize substrate resources into additive and non-additive for the first time.•Raise a deep reinforcement learning based framework for virtual network embedding.•Propose three heuristic algorithms for candidate action generation.
