PCacheDS：一种基于主动缓存算法的发现服务

发现服务(Discovery Service, DS)通过提供一种查询服务,为用户提供物品射频识别(Radio Frequency Identification, RFID)标识与供应链中存储该物品信息的多个信息服务器地址之间的映射服务,以帮助用户获取物品在整个供应链中的信息。但是,当前已有的DS设计方案不能满足兼容不同的RFID编码标准、高效的系统性能和强大的抗拒绝服务(Denial of Service, DoS)攻击能力等需求。因此,针对已有DS研究的不足,基于结构化对等(Peer-to-Peer, P2P)网络和PCache主动缓存算法提出一种称为PCacheDS的DS设计方案。仿真实验的结果表明,与已有的DS研究相比,PCacheDS不仅能够兼容不同的RFID编码标准,而且具有更低的平均查询时延、更强的系统处理性能和强大的抗DoS攻击能力,能够更好的满足DS的应用需求。     

Performance analysis of in-network caching for content-centric networking

With the explosion of multimedia content, Internet bandwidth is wasted by repeated downloads of popular content. Recently, Content-Centric Networking (CCN), or the so-called Information-Centric Networking (ICN), has been proposed for efficient content delivery. In this paper, we investigate the performance of in-network caching for Named Data Networking (NDN), which is a promising CCN proposal. First, we examine the inefficiency of LRU (Least Recently Used) which is a basic cache replacement policy in NDN. Then we formulate the optimal content assignment for two in-network caching policies. One is Single-Path Caching, which allows a request to be served from routers only along the path between a requester and a content source. The other is Network-Wide Caching, which enables a request to be served from any router holding the requested content in a network. For both policies, we use a Mixed Integer Program to optimize the content assignment models by considering the link cost, cache size, and content popularity. We also consider the impact of link capacity and routing issues on the optimal content assignment. Our evaluation and analysis present the performance bounds of in-network caching on NDN in terms of the practical constraints, such as the link cost, link capacity, and cache size.     

Performance analysis of a client-side caching/prefetching system for Web traffic

Network congestion remains one of the main barriers to the continuing success of the Internet. For Web users, congestion manifests itself in unacceptably long response times. One possible remedy to the latency problem is to use caching at the client, at the proxy server, or within the Internet. However, Web documents are becoming increasingly dynamic (i.e., have short lifetimes), which limits the potential benefit of caching. The performance of a Web caching system can be dramatically increased by integrating document prefetching (a.k.a. “proactive caching”) into its design. Although prefetching reduces the response time of a requested document, it also increases the network load, as some documents will be unnecessarily prefetched (due to the imprecision in the prediction algorithm). In this study, we analyze the confluence of the two effects through a tractable mathematical model that enables us to establish the conditions under which prefetching reduces the average response time of a requested document. The model accommodates both passive client and proxy caching along with prefetching. Our analysis is used to dynamically compute the “optimal” number of documents to prefetch in the subsequent client’s idle (think) period. In general, this optimal number is determined through a simple numerical procedure. Closed-form expressions for this optimal number are obtained for special yet important cases. We discuss how our analytical results can be used to optimally adapt the parameters of an actual prefetching system. Simulations are used to validate our analysis and study the interactions among various system parameters.     

Design and analysis of a variable bit rate caching algorithm for continuous media data

In this paper, the problem of caching continuous media data in a (main) memory and disk caching system is addressed. Caching schemes can significantly reduce the load on the network as well as on the servers, also the retrieval of documents from the cache requires short response time. In interval-level caching algorithms, an interval of data between two adjacent streams is the basic caching entity. In this paper, we design a novel algorithm, referred to as variable bit rate caching (VBRC) algorithm, which belongs to the interval-level caching algorithms. The proposed VBRC algorithm can be used in the system for memory caching or disk caching. VBRC can handle variable retrieval bandwidth as well as constant retrieval bandwidth . In designing the VBRC algorithm, we propose the strategies of reducing the number of switching operation, which will probably cause discontinuity of retrieving data. Also, we propose a just-in-time scheme for resource allocation in our VBRC algorithm and show that the caching performance in comparison with the reservation scheme adopted in the resource-based caching (RBC) algorithm is significantly improved. Our simulation study compares the recent and most popular generalized interval caching, RBC, and VBRC, on several influencing factors such as cache space size, cache I/O bandwidth, request arrival rate, and percentage of requests for large documents, with respect to the byte hit ratio and the number of switching operations. The simulation result confirms our analysis.

MSs-MEC中基于DRL的服务缓存和任务迁移联合优化算法

多服务移动边缘计算（multiple-services mobile edge computing,MSs-MEC）能根据需求自适应调整服务缓存决策,使得部署在用户侧的边缘服务器能够灵活处理不同服务类型的任务。但在实际应用中,特定类型任务的成功迁移依赖于服务环境的提前安装。此外,同时进行任务迁移和服务缓存可能会因时间冲突而导致计算延时。因此,针对上述相关问题,首先将任务迁移和服务缓存决策进行解耦,针对深度强化学习（deep reinforcement learning,DRL）在具有高维的混合决策空间的性能提升不明显的缺点（例如资源分配时利用率不高）,将DRL与Transformer结合,通过在历史数据中学习,输出当前时隙的任务迁移决策和下一时隙的任务决策,保证任务到达边缘服务器时能立即执行。其次,为了提高资源分配问题中的资源利用率,将问题分解为连续资源分配问题和离散的任务迁移与服务缓存问题,利用凸优化技术求解资源分配最优决策。广泛的数值结果表明,与其他基线算法相比,提出的算法能有效地减少任务的平均完成时延,同时在资源利用率和稳定性方面也有优异的表现。     

Network caching strategies for a shared data distribution for a predefined service demand sequence

In this paper, we address the problem of minimizing the cost of transferring a document or a file requested by a set of users geographically separated on a network of nodes. We concentrate on theoretical aspects of data migration and caching on high-speed networks. Following the information caching paradigm introduced in the literature, we present polynomial time optimal caching strategies that minimize the total monetary cost of all the service requests by the users on a high-speed network. We consider a scenario in which a large pool of customers from one or more remote sites on a network demand a document, situated at some site, for their use. We also assume that the users can request the document at different time instants. This process of distributing the requested document incurs communication costs due to the use of communication resources and caching costs of the document at some server sites before it is delivered to the users at their desired time instances. We configure the network as a fully connected topology in which the service providers manage and control the distribution of the requested document among the users. For a high-speed network, we show that a single copy of the requested document is sufficient to serve all the user requests in an optimal manner. We extend the study to a homogeneous case in which the communication costs are identical and caching costs at all the sites are identical. In this case, we demonstrate the adaptability of the algorithm in generating more than one copy when needed by the minimization process. Using these strategies, the network service providers can decide when, where, and for how long the requested documents must be cached at vantage sites to obtain an optimal solution. Illustrative examples are provided to ease the understanding.     

Performance comparison of dynamic policies for remote caching

In a distributed system, data servers (file systems and databases) can easily become bottlenecks. We propose an approach to offloading data access requests from overloaded data servers to nodes that are Idle or less busy. This approach is referred to as remote caching, and the idle or less busy nodes are called mutual servers as they help out the busy server nodes on data accesses. In addition to server and client local caches, frequently accessed data are cached in the main memory of mutual servers, thus improving the data access time in the system. We evaluate several data propagation strategics among data servers and mutual servers. These include policies in which senders are active/passive and receivers are active/passive in initiating data propagation. For example, an active sender takes the initiative to offload data onto a passive receiver. Simulation results show that the active-sender/passive-receiver policy is the method of choice In most cases. Active-Sender policies are best able to exploit the main memory of other Idle nodes in the expected normal condition where some nodes are overloaded and others are less loaded. AH active policies perform far better than the policy without remote caching even in the degenerated case where each node is equally loaded.     

一种松竞争性缓存快速存取算法

在文件缓存调度中,每个文件都有固定的大小和被存取的消耗,为了响应对文件操作的一系列请求,把缓存中所有文件的大小维持在一个特定的k值之内,从而最小化文件存取的总消耗。给出一个简单明确的快速存取算法,该算法总结了许多有名的内存分页策略和加权缓存策略,证明了对于大多数k的选择,存取消耗可以忽略不计或者是最佳值的恒定倍数(与k值无关)。从而证明了在线分页算法的竞争比可视为一个常数。     

Performance analysis of a greedy algorithm for inferring Boolean functions

We analyzed average case performance of a known greedy algorithm for inference of a Boolean function from positive and negative examples, and gave a proof to an experimental conjecture that the greedy algorithm works optimally with high probability if both input data and the underlying function are generated uniformly at random.     

Refinement verification of the lazy caching algorithm

The lazy caching algorithm of Afek et al. (ACM Trans. Program. Lang. Syst. 15, 182–206, 1993) is a protocol that allows the use of local caches with delayed updates. It results in a memory model that is not atomic (linearizable) but only sequentially consistent as defined by Lamport. In Distributed Computing 12 (1999), specifying and proving sequential consistency for the lazy caching algorithm was made into a benchmark for verification models. The present note contains such a specification and proof. It provides a simulation from the implementation to the abstract specification. The concrete verification only relies on the state space and the next-state relation. All behavioural aspects are treated in theories independent of the specific algorithm. The proofs of the underlying theories and of the concrete algorithm have been verified with the proof assistant PVS.     

Context-based caching and routing for P2P web service discovery

In modern heterogeneous environments, such as mobile, pervasive and ad-hoc networks, architectures based on web services offer an attractive solution for effective communication and inter-operation. In such dynamic and rapidly evolving environments, efficient web service discovery is an important task. Usually this task is based on the input/output parameters or other functional attributes, however this does not guarantee the validity or successful utilization of retrieved web services. Instead, non-functional attributes, such as device power features, computational resources and connectivity status, that characterize the context of both service providers and consumers play an important role to the quality and usability of discovery results. In this paper we introduce context-awareness in web service discovery, enabling the provision of the most appropriate services at the right location and time. We focus on context-based caching and routing for improving web service discovery in a mobile peer-to-peer environment. We conducted a thorough experimental study, using our prototype implementation based on the JXTA framework, while simulations are employed for testing the scalability of the approach. We illustrate the advantages that this approach offers, both by evaluating the context-based cache performance and by comparing the efficiency of location-based routing to broadcast-based approaches. Recommended by: Zakaria Maamar     

Web search results caching service for structured P2P networks

This paper proposes a two-level P2P caching strategy for Web search queries. The design is suitable for a fully distributed service platform based on managed peer boxes (set-top-box or DSL/cable modem) located at the edge of the network, where both boxes and access bandwidth to those boxes are controlled and managed by an ISP provider. Our solution significantly reduces user query traffic going outside of the ISP provider to get query results from the respective Web search engine. Web users are usually very reactive to worldwide events which cause highly dynamic query traffic patterns leading to load imbalance across peers. Our solution contains a strategy to quickly ease imbalance on peers and spread communication flow among participating peers. Each peer maintains a local result cache used to keep the answers for queries originated in the peer itself and queries for which the peer is responsible for by contacting the Web search engine on-demand. When query traffic is predominantly routed to a few responsible peers our strategy replicates the role of “being responsible for” to neighboring peers so that they can absorb query traffic. This is a fairly slow and adaptive process that we call mid-term load balancing. To achieve a short-term fair distribution of queries we introduce a location cache in each peer which keeps pointers to peers that have already requested the same queries in the recent past. This lets these peers share their query answers with newly requesting peers. This process is fast as these popular queries are usually cached in the first DHT hop of a requesting peer which quickly tends to redistribute load among more and more peers.     

Performance analysis of a retransmission control algorithm for local area networks

Algorithms for the control of the transmission procedure in multiaccess schemes must ensure simplicity in the implementation, stability of the system operation and high efficiency for all traffic conditions. A control algorithm suitable for slotted multiaccess schemes based on monitoring the channel transmissions is proposed. A model is presented and the algorithm is analysed in detail. The performance of the algorithm is evaluated, and comparisons are made with multiaccess protocols.     

Performance analysis of a dual-tree algorithm for computing spatial distance histograms

Many scientific and engineering fields produce large volume of spatiotemporal data. The storage, retrieval, and analysis of such data impose great challenges to database systems design. Analysis of scientific spatiotemporal data often involves computing functions of all point-to-point interactions. One such analytics, the Spatial Distance Histogram (SDH), is of vital importance to scientific discovery. Recently, algorithms for efficient SDH processing in large-scale scientific databases have been proposed. These algorithms adopt a recursive tree-traversing strategy to process point-to-point distances in the visited tree nodes in batches, thus require less time when compared to the brute-force approach where all pairwise distances have to be computed. Despite the promising experimental results, the complexity of such algorithms has not been thoroughly studied. In this paper, we present an analysis of such algorithms based on a geometric modeling approach. The main technique is to transform the analysis of point counts into a problem of quantifying the area of regions where pairwise distances can be processed in batches by the algorithm. From the analysis, we conclude that the number of pairwise distances that are left to be processed decreases exponentially with more levels of the tree visited. This leads to the proof of a time complexity lower than the quadratic time needed for a brute-force algorithm and builds the foundation for a constant-time approximate algorithm. Our model is also general in that it works for a wide range of point spatial distributions, histogram types, and space-partitioning options in building the tree.     

基于WCF的服务缓存设计与研究

为了更好地解决Client/Server结构的遗留系统向SOA系统移植中的问题,分析了.NET3.0框架下的WPF(Windows pre-seatation foundation)图形系统和WCF(Windows communication foundation)服务技术,重点研究了WCF服务原理,提出了基于WCF的服务缓存系统结构模型.该模型采用对象池技术扩展WCF服务行为,有效地解决了服务端的性能问题.在实践项目的实验中,比较了直接连接服务和通过对象池访问服务两种方式下服务响应时间和内存占用的数据,结果表明了该服务缓存结构的有效性.     

A novel cooperative caching algorithm for massive P2P caches

For an ISP (Internet Service Provider) that has deployed P2P caches in more than one ASs (autonomous systems), cooperative caching which makes their caches cooperate with each other can save more cost of carrying P2P traffic than independent caching. However, existing cooperative caching algorithms only use objects’ popularity as the measurement to decide which objects should be cached, and cost on intra-ISP links that has great impact on the benefits of cooperative caching is not considered. In this paper, we first model the cooperative caching problem as a NP-Complete problem, which is based on our analysis about the cost of serving requests with consideration of both the objects’ popularity and the cost on intra-ISP links. Then we propose a novel cooperative caching algorithm named cLGV (Cooperative, Lowest Global Value). The cLGV algorithm uses a new concept global value to estimate the benefits of caching or replacing an object in the cooperative caching system, and the global value of each object is evaluated according to not only objects’ popularity in each AS but also cost on intra-ISP links among ASs. Results of both synthetic and real traces driven simulations indicate that our cLGV algorithm can save the cost of carrying P2P traffic at least 23 % higher than that of existing cooperative caching algorithms.     

Design and analysis of a merging algorithm for multipoint-to-point ABR service in ATM networks

In this paper, we propose a merging algorithm, which can provide efficient support for multipoint-to-point ABR service in ATM networks. By forwarding the FRM cells belonging to the VC with the largest FRM-cell arrival rate in a merge point, the proposed algorithm can achieve better link utilization than existing merging algorithms. In addition, the proposed algorithm reduces the number of FRM cells forwarded by a merge point. As a result, it can reduce the control overhead of ABR service. Most importantly, it does not incur extra complexity in switches. We also discuss the impact of different network topologies on our algorithm. Simulation results show that the proposed algorithm is able to achieve better performance while requiring significantly fewer RM cells.     

ERGRID中网格服务的性能分析

在基于因特网的教育资源网格体系结构和服务理论研究中,建立了教育资源网格平台ERGRID,该平台实现了基于Web的可视化网格服务.通过和Web Services以及Java Servlets进行性能对比,证明了服务大数量级的数据时,网格服务会比Web Services和Java Servlets更快一些.     

Performance analysis of a threshold based distributed channel allocation algorithm for cellular networks

Rapid advances of the handheld devices and the emergence of the demanding wireless applications require the cellular networks to support the demanding user needs more effectively. The cellular networks are expected to provide these services under a limited bandwidth. Efficient management of the wireless channels by effective channel allocation algorithms is crucial for the performance of any cellular system. To provide a better channel usage performance, dynamic channel allocation schemes have been proposed. Among these schemes, distributed dynamic channel allocation approaches showed good performance results. The two important issues that must be carefully addressed in such algorithms are the efficient co-channel interference avoidance and messaging overhead reduction. In this paper, we focus on our new distributed channel allocation algorithm and evaluate its performance through extensive simulation studies. The performance evaluation results obtained under different traffic load and user mobility conditions, show that the proposed algorithm outperforms other algorithms recently proposed in the literature.     

Performance analysis of the AntNet algorithm

A number of routing algorithms based on the ant-colony metaphor have been proposed for communication networks. However, there has been little work on the performance analysis of ant-routing algorithms. In this paper, we compare the performance of AntNet, an ant-routing algorithm, with Dijkstra’s shortest path algorithm. Our simulations show that the performance of AntNet is comparable to Dijkstra’s shortest path algorithm. Moreover, under varying traffic loads, AntNet adapts to the changing traffic and performs better than shortest path routing.