Coordinator log transaction execution protocol

The coordinator log transaction execution protocol proposed in this paper centralizes logging on a per transaction basis and exploits piggybacking to provide the semantics of a distributed atomic commit at a minimal cost. The protocol eliminates two rounds of messages (one phase) from the presumed commit protocol and dramatically reduces the number of log forces needed for distributed atomic commit. We compare the coordinator log transaction execution protocol to existing protocols, explain when it is desirable, and discuss how it affects the write ahead log protocol and the database crash recovery algorithm. Recommended by: Tamer Ozsu     

Theoretical analysis for communication-induced checkpointingprotocols with rollback-dependency trackability

Rollback-Dependency Trackability (RDT) is a property that states that all rollback dependencies between local checkpoints are on-line trackable by using a transitive dependency vector. In this paper, we address three fundamental issues in the design of communication-induced checkpointing protocols that ensure RDT. First, we prove that the following intuition commonly assumed in the literature is in fact false: If a protocol forces a checkpoint only at a stronger condition, then it must take, at most, as many forced checkpoints as a protocol based on a weaker condition. This result implies that the common approach of sharpening the checkpoint-inducing condition by piggybacking more control information on each message may not always yield a more efficient protocol. Next, we prove that there is no optimal on-line RDT protocol that takes fewer forced checkpoints than any other RDT protocol for all possible communication patterns. Finally, since comparing checkpoint-inducing conditions is not sufficient for comparing protocol performance, we present some formal techniques for comparing the performance of several existing RDT protocols     

Protocol interoperability in mobile IP enabled mobile ad hoc networks

A trend in future 4G wireless networks is the integration of MANETs into all-IP systems, which may enhance the flexibility and pervasiveness of 4G networks. One of the most crucial challenges in this field is the design of Protocol Interoperability to achieve the integration of MANET routing protocols and Mobile IP into the IP routing systems. This problem has not been effectively addressed by researches published thus far. This paper contributes solutions to solving this challenge. The protocol architecture and protocol interfaces are designed, which are suitable for gateways and mobile nodes in such Internet integrated MANETs supporting Mobile IP. Propagation methods of Mobile IP signalling messages with MANET routing information piggybacking are designed. Finally, an enhanced Mobile IP protocol suitable for MANET system is contributed. In summary, the contribution of this paper is a thorough scheme for establishing an IP/MIP/MANET integrated system.     

An energy-efficient,transport-controlled MAC protocol for wireless sensor networks

In wireless sensor networks (WSNs), one major cause of wasted energy is that the wireless network interface is always on to accept possible traffic. Many medium access control (MAC) protocols therefore adopted a periodic listen-and-sleep scheme to save energy, at sacrifice of end-to-end latency and throughput. Another cause is packet dropping due to network congestion, necessitating a lightweight transport protocol for WSNs. In this paper, we suggest a transport-controlled MAC protocol (TC-MAC) that combines the transport protocol into the MAC protocol with the aims of achieving high performance as well as energy efficiency in multi-hop forwarding. Although TC-MAC also works through a periodic listen-and-sleep scheme, it lowers end-to-end latency by reserving data forwarding schedules across multi-hop nodes during the listen period and by forwarding data during the sleep period, all while increasing throughput by piggybacking the subsequent data forwarding schedule on current data transmissions and forwarding data consecutively. In addition, TC-MAC gives a fairness-aware lightweight transport control mechanism based on benefits of using the MAC-layer information. The results show that TC-MAC performs as well as an 802.11-like MAC in end-to-end latency and throughput, and is more efficient than S-MAC in energy consumption, with the additional advantage of supporting fairness-aware congestion control.     

A cross-layer atomic commit protocol implementation for transaction processing in mobile ad-hoc networks

Transaction processing leads to new challenges in mobile ad-hoc networks, which, in comparison to fixed-wired networks, suffer from problems like node disconnection, message loss, and frequently appearing network partitioning. As the atomic commit protocol is that part of transaction processing in which failures can lead to the most serious data blocking, we have developed a robust and failure-tolerant distributed cross-layer atomic commit protocol called CLCP that uses multiple coordinators. In order to reduce the number of both, failures and messages, our protocol makes use of acknowledgement messages for piggybacking information. We have evaluated our protocol in mobile ad-hoc networks by using several mobility models (i.e. Random Waypoint, Manhattan, and Attraction Point), and compared CLCP with other atomic commit protocols, i.e. 2PC and Paxos Commit, each implemented in 3 versions, i.e. without sending message acknowledgements, with a Relay Routing technique, and with Nearest Forward Progress Routing. Special to our simulation environment is the use of the quasi-unit-disc model, which assumes a non-binary message reception probability that captures real-world behavior much better than the classical unit-disc-model, often used in theory. Using the quasi-unit-disc model, our evaluation shows the following results. CLCP and “2PC without acknowledgement messages” have a significantly lower energy consumption than the other protocols, and CLCP is able to commit significantly more distributed transactions than all the other atomic commit protocols for each of the mobility models.     

两种VPRN实现机制的比较

虚拟专用路由网（VPRN，Virtual Private Routed Network)是一种重要的虚拟专用网类型。现阶段有两种实现VPRN的机制：一种是集成模式（Piggybacking Mode)；另一种是叠加模式（Overlay Mode)。对这两种机制的实现进行了研究，并对两者进行了比较，得出了两种机制在体系结构、管理和安全等方面的不同特点。     

Adaptive Piggybacking Schemes for Video-On-Demand Systems

A critical issue in the performance of a video-on-demand system is the I/O bandwidth required in order to satisfy client requests. A number of techniques have been proposed in order to reduce these bandwidth requirements. In this paper we concentrate on one such technique, known as adaptive piggybacking. We develop and analyze piggyback merging policies which are optimal over large classes of reasonable methods.     

An efficient joint channel assignment and QoS routing protocol for IEEE 802.11 multi-radio multi-channel wireless mesh networks

With the emerging of video, voice over IP (VoIP) and other real-time multimedia services, more and more people pay attention to quality of service (QoS) issues in terms of the bandwidth, delay and jitter, etc. As one effective way of broadband wireless access, it has become imperative for wireless mesh networks (WMNs) to provide QoS guarantee. Existing works mostly modify QoS architecture dedicated for ad hoc or sensor networks, and focus on single radio and single channel case. Meanwhile, they study the QoS routing or MAC protocol from view of isolated layer. In this paper, we propose a novel cross-layer QoS-aware routing protocol on OLSR (CLQ-OLSR) to support real-time multimedia communication by efficiently exploiting multi-radio and multi-channel method. By constructing multi-layer virtual logical mapping over physical topology, we implement two sets of routing mechanisms, physical modified OLSR protocol (M-OLSR) and logical routing, to accommodate network traffic. The proposed CLQ-OLSR is based on a distributed bandwidth estimation scheme, implemented at each node for estimating the available bandwidth on each associated channel. By piggybacking the bandwidth information in HELLO and topology control (TC) messages, each node disseminates information of topology and available bandwidth to other nodes in the whole network in an efficient way. From topology and bandwidth information, the optimized path can be identified. Finally, we conduct extensive simulation to verify the performance of CLQ-OLSR in different scenarios on QualNet platform. The results demonstrate that our proposed CLQ-OLSR outperforms single radio OLSR, multi-radio OLSR and OLSR with differentiated services (DiffServ) in terms of network aggregate throughput, end-to-end packet delivery ratio, delay and delay jitter with reasonable message overheads and hardware costs. In particular, the network aggregate throughput for CLQ-OLSR can almost be improved by 300% compared with the single radio case.     

The look-ahead-maximize-batch batching policy

This paper introduces a new batching policy, called look-ahead-maximize-batch (LAMB), for reducing the bandwidth demand of video servers. LAMB maximizes the number of users admitted in a window, which includes the reneging time of all pending requests at that scheduling time. LAMB admits a greater number of users than other existing batching policies. Furthermore, the benefits of integrating batching and piggybacking is analyzed     

VOD服务器中共享I/O流的关键技术

VOD服务器的I/O带宽是影响VOD系统性能的关键因素。如何通过使多个用户请求共享一个I/O流,减少对I/O带宽的要求是VOD研究领域中的研究热点之一。文章对VOD服务器中共享I/O流的基本技术Batching、AdaptivePiggybacking、Bridging和Chaining进行了全面的讨论,并对当前的研究现状进行介绍。     

Use of analytical performance models for system sizing and resourceallocation in interactive video-on-demand systems employing data sharingtechniques

In designing cost-effective video-on-demand (VOD) servers, efficient resource management and proper system sizing are of great importance. In addition to large storage and I/O bandwidth requirements, support of interactive VCR functionality imposes additional resource requirements on the VOD system in terms of storage space, as well as disk and network bandwidth. Previous works have used data sharing techniques (such as batching, buffering, and adaptive piggybacking) to reduce the I/O demand on the storage server. However, such data sharing techniques complicate the provision of VCR functions and diminish the amount of benefit that can be obtained from data sharing techniques. The main contribution of this paper is a simple, yet powerful, analytical modeling approach which allows for analysis, system sizing, resource allocation, and parameter setting for a fairly general class of data sharing techniques which are used in conjunction with the providing of VCR-type functionality. Using this mathematical model, we can determine the proper amount of resources to be allocated for normal playback as well as for service of VCR functionality requests while satisfying predefined system performance requirements. To illustrate the usefulness of our model, we focus on a specific data sharing scheme which combines the use of batching, buffering, and adaptive piggybacking, as well as allows for the use of VCR functions. We show how to utilize this mathematical model for system sizing and resource allocation purposes     

Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony

The topic of this paper is the study of information dissemination in mobile ad-hoc networks by means of deterministic protocols. We assume a weak set of restrictions on the mobility of nodes, parameterized by α, the disconnection time, and β, the link stability time, such that the mobile ad-hoc networks considered are connected enough for dissemination. Such a connectivity model generalizes previous models in that we assume much less connectivity, or make explicit the assumptions in previous papers. The protocols studied are classified into three classes: oblivious (the transmission schedule of a node is only a function of its ID), quasi-oblivious (the transmission schedule may also depend on a global time), and adaptive. The main contribution of this work concerns negative results. Contrasting the lower and upper bounds derived, interesting complexity gaps among protocol-classes are observed. These results show that the gap in time complexity between oblivious and quasi-oblivious (hence, adaptive) protocols is almost linear. This gap is what we call the profit of global synchrony since it represents the gain the network obtains from global synchrony with respect to not having it. We note that the global synchrony required by the efficient quasi-oblivious protocol proposed is simply achieved by piggybacking in the messages sent the time at the source node, as a global reference.     

DHT网络中的多维复杂查询处理方法研究

DHT网络中的高级查询处理是关系其应用领域拓展的重要问题,也是学术界与工业界共同关注的研究热点。基于Kademlia协议提出一种DHT网络中的多维复杂查询处理方法,其索引结构考虑了用户的查询偏好,使同类数据的存储位置具有相关性,同时巧妙地利用了Kadcmlia路由表的特点与更新方法,避免了索引维护过产生额外的 通信开销,并且通过多点存储、沿路缓存改善了系统的容错性与负载均衡性。分析和实验表明,该方法以O(logN)的路由跳数复杂度和较低的开销实现了资源的多维复杂查询。     

Zeus: A Distributed Timed Model-Checker Based on Kronos

In this work we present Zeus, a Distributed Model-Checker that evolves from the tool Kronos [8] and that currently can handle backwards computation of TCTL-reachability properties [1] over timed-automata [2].Zeus was developed following a software architecture centric approach. It introduces some interesting features such as a priori graph partitioning, a sophisticated machinery to reach optimum performance (communication piggybacking and delayed messaging) and dead-time utilization, where every processor uses time intervals of inactivity to perform auxiliary, time-consuming tasks that will later speed up the rest of the computation.Although some good results have been obtained, early experiments pinpointed the difficulties of getting speedups using a parallel asynchronous version. We also propose some paths to overcome those obstacles.     

Adaptive piggybacking: a novel technique for data sharing in video-on-demand storage servers

Recent technology advances have made multimedia on-demand services, such as home entertainment and home-shopping, important to the consumer market. One of the most challenging aspects of this type of service is providing access either instantaneously or within a small and reasonable latency upon request. We consider improvements in the performance of multimedia storage servers through data sharing between requests for popular objects, assuming that the I/O bandwidth is the critical resource in the system. We discuss a novel approach to data sharing, termed adaptive piggybacking, which can be used to reduce the aggregate I/O demand on the multimedia storage server and thus reduce latency for servicing new requests.     

Issues in distributed timed model checking

In this work we present Zeus, a distributed timed model checker that evolves from the TCTL model checker Kronos [13] and that currently can handle backwards computation of reachability properties [2] over timed automata [3].Zeus was developed following a software architecture-centric approach. Its conceptual architecture was conceived to be sufficiently modular to house several features such as a priori graph partitioning, synchronous and asynchronous computation, communication piggybacking, delayed messaging, and dead-time utilization.Surprisingly enough, early experiments pinpointed the difficulties of getting speedups using asynchronous versions and showed interesting results on the synchronous counterpart, although being intuitively less attractive.     

基于DOCSIS HFC网络MAC协议的性能仿真

DOCSIS协议已经成为HFC网络前端和用户端之间透明地双向传输IP业务事实上的标准。为了深入研究DOCSIS协议中参数配置对系统性能的影响,本文利用OPNET提供的CSF13仿真工具分析了协议中捎带请求、分块和串联对系统性能的影响,比较了截断二进制指数回退算法中各种回退窗口设置的性能差异;最后,在系统负载和CM个数不变的前提下,探讨了MAP（上行信道带宽分配帧）大小、竞争时隙CS的个数以及设置优先级与上行信道接入延时之间的关系,获得了较佳的性能参数,并对今后复杂的性能仿真提供了重要的参考价值。     

Efficient Garbage Collection Schemes for Causal Message Logging with Independent Checkpointing

This paper presents three garbage collection schemes for causal message logging with independent checkpointing. The first scheme allows each process to autonomously remove useless log information in its volatile storage by piggybacking only some additional information without requiring any extra message and forced checkpoint. Additionally, it supports faster output commit than traditional schemes. The second scheme enables each process to remove a part of log information in the storage if more empty space is required. It reduces the number of processes participating in the garbage collection by using the size of the log information of each process. The third scheme is a hybrid scheme having the advantages of the two proposed schemes. Simulation results show that the third scheme significantly reduces the garbage collection overhead compared with the traditional schemes regardless of specific communication patterns of distributed applications.     

Error detection and diagnosis for fault tolerance in distributed systems

The early error detection and the understanding of the nature and conditions of an error occurrence can be useful to make an effective and efficient recovery in distributed systems. Various distributed system extensions were introduced for the implementation of fault tolerance in distributed software systems. These extensions rely mainly on the exchange of contextual information appended to every transmitted application specific message. Ideally, this information should be used for checkpointing, error detection, diagnosis and recovery should a transient failure occur later during the distributed program execution. In this paper, we present a generalized extension suitable for fault-tolerant distributed systems such as communication software systems and its detection capabilities are shown. Our extension is based on the execution of message validity test prior to the transmission of messages and the piggybacking of contextual information to facilitate the detection and diagnosis of transient faults in the distributed system.     

On the optimization of schedules for MapReduce workloads in the presence of shared scans

We consider MapReduce clusters designed to support multiple concurrent jobs, concentrating on environments in which the number of distinct datasets is modest relative to the number of jobs. In such scenarios, many individual datasets are likely to be scanned concurrently by multiple Map phase jobs. As has been noticed previously, this scenario provides an opportunity for Map phase jobs to cooperate, sharing the scans of these datasets, and thus reducing the costs of such scans. Our paper has three main contributions over previous work. First, we present a novel and highly general method for sharing scans and thus amortizing their costs. This concept, which we call cyclic piggybacking, has a number of advantages over the more traditional batching scheme described in the literature. Second, we notice that the various subjobs generated in this manner can be assumed in an optimal schedule to respect a natural chain precedence ordering. Third, we describe a significant but natural generalization of the recently introduced FLEX scheduler for optimizing schedules within the context of this cyclic piggybacking paradigm, which can be tailored to a variety of cost metrics. Such cost metrics include average response time, average stretch, and any minimax-type metric—a total of 11 separate and standard metrics in all. Moreover, most of this carries over in the more general case of overlapping rather than identical datasets as well, employing what we will call semi-shared scans. In such scenarios, chain precedence is replaced by arbitrary precedence, but we can still handle 8 of the original 11 metrics. The overall approach, including both cyclic piggybacking and the FLEX scheduling generalization, is called CIRCUMFLEX. We describe some practical implementation strategies. And we evaluate the performance of CIRCUMFLEX via a variety of simulation and real benchmark experiments.