Using AVL trees for fault-tolerant group key management

In this paper we describe an efficient algorithm for the management of group keys for group communication systems. Our algorithm is based on the notion of key graphs, previously used for managing keys in large Internet-protocol multicast groups. The standard protocol requires a centralized key server that has knowledge of the full key graph. Our protocol does not delegate this role to any one process. Rather, members enlist in a collaborative effort to create the group key graph. The key graph contains n keys, of which each member learns log₂n of them. We show how to balance the key graph, a result that is applicable to the centralized protocol. We also show how to optimize our distributed protocol, and provide a performance study of its capabilities. Published online: 26 October 2001     

Universal dynamic synchronous self–stabilization

Summary. We prove the existence of a “universal” synchronous self-stabilizing protocol, that is, a protocol that allows a distributed system to stabilize to a desired nonreactive behaviour (as long as a protocol stabilizing to that behaviour exists). Previous proposals required drastic increases in asymmetry and knowledge to work, whereas our protocol does not use any additional knowledge, and does not require more symmetry-breaking conditions than available; thus, it is also stabilizing with respect to dynamic changes in the topology. We prove an optimal quiescence time n+D for a synchronous network of n processors and diameter D; the protocol can be made finite state with a negligible loss in quiescence time. Moreover, an optimal D+1 protocol is given for the case of unique identifiers. As a consequence, we provide an effective proof technique that allows to show whether self-stabilization to a certain behaviour is possible under a wide range of models. Received: January 1999 / Accepted: July 2001     

Wait-free concurrent memory management by Create and Read until Deletion (CaRuD)

Summary. The acronym CaRuD represents an interface specification and an algorithm for the management of memory shared by concurrent processes. The memory cells form a directed acyclic graph. This graph is only modified by adding a new node with a list of reachable children, and by removing unreachable nodes. If memory is not full, the algorithm ensures wait-free redistribution of free nodes. It uses atomic counters for reference counting and consensus variables to ensure exclusive access. Performance is enhanced by using nondeterminacy guided by insecure knowledge. Experiments indicate that the algorithm is very suitable for multiprocessing. Received: July 1998 / Accepted: July 2000     

Local model checking and protocol analysis

This paper describes a local model-checking algorithm for the alternation-free fragment of the modal mu-calculus that has been implemented in the Concurrency Factory and discusses its application to the analysis of a real-time communications protocol. The protocol considered is RETHER, a software-based, real-time Ethernet protocol developed at SUNY at Stony Brook. Its purpose is to provide guaranteed bandwidth and deterministic, periodic network access to multimedia applications over commodity Ethernet hardware. Our model-checking results show that (for a particular network configuration) RETHER makes good on its bandwidth guarantees to real-time nodes without exposing non-real-time nodes to the possibility of starvation. Our data also indicate that, in many cases, the state-exploration overhead of the local model checker is significantly smaller than the total amount that would result from a global analysis of the protocol. In the course of specifying and verifying RETHER, we also identified an alternative design of the protocol that warranted further study due to its potentially smaller run-time overhead in servicing requests for data transmission. Again, using local model checking, we showed that this alternative design also possesses the properties of interest. This observation points out one of the often-overlooked benefits of formal verification: by forcing designers to understand their designs rigorously and abstractly, these techniques often enable the designers to uncover interesting design alternatives.     

Synchronized delivery and playout of distributed stored multimedia streams

Multimedia streams such as audio and video impose tight temporal constraints for their presentation. Often, related multimedia streams, such as audio and video, must be presented in a synchronized way. We introduce a novel scheme to ensure the continuous and synchronous delivery of distributed stored multimedia streams across a communications network. We propose a new protocol for synchronized playback and compute the buffer required to achieve both, the continuity within a single substream and the synchronization between related substreams. The scheme is very general and does not require synchronized clocks. Using a resynchronization protocol based on buffer level control, the scheme is able to cope with server drop-outs and clock drift. The synchronization scheme has been implemented and the paper concludes with our experimental results.     

Managing database server performance to meet QoS requirements in electronic commerce systems

The performance of electronic commerce systems has a major impact on their acceptability to users. Different users also demand different levels of performance from the system, that is, they will have different Quality of Service (QoS) requirements. Electronic commerce systems are the integration of several different types of servers and each server must contribute to meeting the QoS demands of the users. In this paper we focus on the role, and the performance, of a database server within an electronic commerce system. We examine the characteristics of the workload placed on a database server by an electronic commerce system and suggest a range of QoS requirements for the database server based on this analysis of the workload. We argue that a database server must be able to dynamically reallocate its resources in order to meet the QoS requirements of different transactions as the workload changes. We describe Quartermaster, which is a system to support dynamic goal-oriented resource management in database management systems, and discuss how it can be used to help meet the QoS requirements of the electronic commerce database server. We provide an example of the use of Quartermaster that illustrates how the dynamic reallocation of memory resources can be used to meet the QoS requirements of a set of transactions similar to transactions found in an electronic commerce workload. We briefly describe the memory reallocation algorithms used by Quartermaster and present experiments to show the impact of the reallocations on the performance of the transactions. Published online: 22 August 2001     

Deterministic broadcasting in ad hoc radio networks

We consider the problem of distributed deterministic broadcasting in radio networks of unknown topology and size. The network is synchronous. If a node u can be reached from two nodes which send messages in the same round, none of the messages is received by u. Such messages block each other and node u either hears the noise of interference of messages, enabling it to detect a collision, or does not hear anything at all, depending on the model. We assume that nodes know neither the topology nor the size of the network, nor even their immediate neighborhood. The initial knowledge of every node is limited to its own label. Such networks are called ad hoc multi-hop networks. We study the time of deterministic broadcasting under this scenario. For the model without collision detection, we develop a linear-time broadcasting algorithm for symmetric graphs, which is optimal, and an algorithm for arbitrary n-node graphs, working in time . Next we show that broadcasting with acknowledgement is not possible in this model at all. For the model with collision detection, we develop efficient algorithms for broadcasting and for acknowledged broadcasting in strongly connected graphs. Received: January 2000 / Accepted: June 2001     

Self-stabilizing depth-first token circulation in arbitrary rooted networks

Abstract. We present a deterministic distributed depth-first token passing protocol on a rooted network. This protocol uses neither the processor identifiers nor the size of the network, but assumes the existence of a distinguished processor, called the root of the network. The protocol is self-stabilizing, meaning that starting from an arbitrary state (in response to an arbitrary perturbation modifying the memory state), it is guaranteed to reach a state with no more than one token in the network. Our protocol implements a strictly fair token circulation scheme. The proposed protocol has extremely small state requirement – only states per processor, i.e., bits per processor, where is the degree of the network. The protocol can be used to implement a strictly fair distributed mutual exclusion in any rooted network. This protocol can also be used to construct a DFS spanning tree. Received: July 1998 / Accepted: April 2000     

ScholOnto: an ontology-based digital library server for research documents and discourse

The internet is rapidly becoming the first place for researchers to publish documents, but at present they receive little support in searching, tracking, analysing or debating concepts in a literature from scholarly perspectives. This paper describes the design rationale and implementation of ScholOnto, an ontology-based digital library server to support scholarly interpretation and discourse. It enables researchers to describe and debate via a semantic network the contributions a document makes, and its relationship to the literature. The paper discusses the computational services that an ontology-based server supports, alternative user interfaces to support interaction with a large semantic network, usability issues associated with knowledge formalisation, new work practices that could emerge, and related work. Published online: 22 September 2000     

RCSP and stop-and-go: a comparison of two non-work-conserving disciplines for supporting multimedia communication

To support emerging real-time applications, high-speed integrated services networks must provide end-to-end performance guarantees on a per-connection basis in a networking environment. Resource management algorithms must accommodate traffic that may get burstier as it traverses the network due to complex interactions among packet streams at each switch. To address this problem, several non-work-conserving packet-service disciplines have been proposed. Non-work-conserving servers may be idle and hold packets under certain conditions, to reconstruct, fully or partially, the traffic pattern of the original source inside the network and prevent the traffic from becoming burstier. We compare two non-work-conserving service disciplines. Stop-and-go uses a multilevel framing strategy to allocate resources in a single switch and to ensure traffic smoothness throughout the network. Rate controlled static priority (RCSP) decouples the server functions with two components: (1) a regulator to control traffic distortion introduced by multiplexing effects and load fluctuations in previous servers, and 2) a static priority scheduler to multiplex the regulated traffic. We compare the two service disciplines in terms of traffic specification, scheduling mechanism, buffer space requirement, end-to-end delay characteristics, connection admission-control algorithms, and achievable network utilization. The comparison is first done analytically, and then empirically by using two 10-min traces of MPEG compressed video.     

On improving resistance to Denial of Service and key provisioning scalability of the DTLS handshake

DTLS is a transport layer security protocol designed to provide secure communication over unreliable datagram protocols. Before starting to communicate, a DTLS client and server perform a specific handshake in order to establish a secure session and agree on a common security context. However, the DTLS handshake is affected by two relevant issues. First, the DTLS server is vulnerable to a specific Denial of Service (DoS) attack aimed at forcing the establishment of several half-open sessions. This may exhaust memory and network resources on the server, so making it less responsive or even unavailable to legitimate clients. Second, although it is one of the most efficient key provisioning approaches adopted in DTLS, the pre-shared key provisioning mode does not scale well with the number of clients, it may result in scalability issues on the server side, and it complicates key re-provisioning in dynamic scenarios. This paper presents a single and efficient security architecture which addresses both issues, by substantially limiting the impact of DoS, and reducing the number of keys stored on the server side to one unit only. Our approach does not break the existing standard and does not require any additional message exchange between DTLS client and server. Our experimental results show that our approach requires a shorter amount of time to complete a handshake execution and consistently reduces the time a DTLS server is exposed to a DoS instance. We also show that it considerably improves a DTLS server in terms of service availability and robustness against DoS attack.     

A self-stabilizing quorum-based protocol for maxima computing

The goal of decentralized consensus protocols is to exchange information among nodes so that each node acquires the information held by every other node in the system. This paper presents a quorum-based, self-stabilizing maxima finding protocol which is based on a decentralized consensus protocol. The protocol exchanges information with less delay than existing ring-based, self-stablizing protocols. Furthermore, quorums can be composed, and the resulting composite quorums can be used to efficiently obtain a solution for any internetwork. Received: October 1999 / Accepted: June 2001     

Dynamic batching policies for an on-demand video server

In a video-on-demand environment, continuous delivery of video streams to the clients is guaranteed by sufficient reserved network and server resources. This leads to a hard limit on the number of streams that a video server can deliver. Multiple client requests for the same video can be served with a single disk I/O stream by sending (multicasting) the same data blocks to multiple clients (with the multicast facility, if present in the system). This is achieved by batching (grouping) requests for the same video that arrive within a short time. We explore the role of customer-waiting time and reneging behavior in selecting the video to be multicast. We show that a first come, first served (FCFS) policy that schedules the video with the longest outstanding request can perform better than the maximum queue length (MQL) policy that chooses the video with the maximum number of outstanding requests. Additionally, multicasting is better exploited by scheduling playback of the most popular videos at predetermined, regular intervals (hence, termed FCFS-). If user reneging can be reduced by guaranteeing that a maximum waiting time will not be exceeded, then performance of FCFS- is further improved by selecting the regular playback intervals as this maximum waiting time. For an empirical workload, we demonstrate a substantial reduction (of the order of 60%) in the required server capacity by batching.     

Multiresolution volume visualization with a texture-based octree

Although 3D texture-based volume rendering guarantees image quality almost interactively, it is difficult to maintain an interactive rate when the technique has to be exploited on large datasets. In this paper, we propose a new texture memory representation and a management policy that substitute the classical one-texel per voxel approach for a hierarchical approach. The hierarchical approach benefits nearly homogeneous regions and regions of lower interest. The proposed algorithm is based on a simple traversal of the octree representation of the volume data. Driven by a user-defined image quality, defined as a combination of data homogeneity and importance, a set of octree nodes (the cut) is selected to be rendered. The degree of accuracy applied for the representation of each one of the nodes of the cut in the texture memory is set independently according to the user-defined parameters. The variable resolution texture model obtained reduces the texture memory size and thus texture swapping, improving rendering speed.     

Networks on which hot-potato routing does not livelock

Summary. Hot-potato routing is a form of synchronous routing which makes no use of buffers at intermediate nodes. Packets must move at every time step, until they reach their destination. If contention prevents a packet from taking its preferred outgoing edge, it is deflected on a different edge. Two simple design principles for hot potato routing algorithms are minimum advance, that advances at least one packet towards its destination from every nonempty node (and possibly deflects all other packets), and maximum advance, that advances the maximum possible number of packets. Livelock is a situation in which packets keep moving indefinitely in the network without any packet ever reaching its destination. It is known that even maximum advance algorithms might livelock on some networks. We show that minimum advance algorithms never livelock on tree networks, and that maximum advance algorithms never livelock on triangulated networks. Received: March 1999 / Accepted: August 1999     

Assigning labels in an unknown anonymous network with a leader

We consider the task of assigning distinct labels to nodes of an unknown anonymous network in a distributed manner. A priori, nodes do not have any identities, except for one distinguished node, called the source, and do not know the topology or the size of the network. They execute identical algorithms, apart from the source which plays the role of a leader and starts the labeling process. Our goal is to assign short labels, as fast as possible. The quality of a labeling algorithm is measured by the range from which the algorithm picks the labels, or alternatively, the length of the assigned labels. Natural efficiency measures are the time, i.e., the number of rounds required for the label assignment, and the message and bit complexities of the label assignment protocol, i.e., the total number of messages (resp., bits) circulating in the network. We present label assignment algorithms whose time and message complexity are asymptotically optimal and which assign short labels. On the other hand, we establish inherent trade-offs between quality and efficiency for labeling algorithms. Received: July 2000 / Accepted: February 2001     

Formalization and validation of the General Inter-ORB Protocol (GIOP) using PROMELA and SPIN

The General Inter-Orb Protocol (GIOP) is a key component of the Common Object Request Broker Architecture (CORBA) specification. We present the formal modeling and validation of the GIOP protocol using the Promela language, Linear Time Temporal Logic (LTL) and the Spin model checker. We validate the Promela model using ten high-level requirements which we elicit from the informal CORBA specification. These requirements are then formalized in LTL and the Spin model checker is used to determine their validity. During the validation process we discovered a few problems in GIOP: a potential transport-layer interface deadlock and problems with the server migration protocol. We also describe how property specification patterns helped us in formalizing the high-level requirements that we have elicited.     

{\cal SMDP}: minimizing buffer requirements for continuous media servers

Excessive buffer requirement to handle continuous-media playbacks is an impediment to cost- effective provisioning for on-line video retrieval. Given the skewed distribution of video popularity, it is expected that often there are concurrent playbacks of the same video file within a short time interval. This creates an opportunity to batch multiple requests and to service them with a single stream from the disk without violating the on-demand constraint. However, there is a need to keep data in memory between successive uses to do this. This leads to a buffer space trade-off between servicing a request in memory mode vs. servicing it in disk-mode. In this work, we develop a novel algorithm to minimize the buffer requirement to support a set of concurrent playbacks. One of the beauties of the proposed scheme is that it enables the server to dynamically adapt to the changing workload while minimizing the total buffer space requirement. Our algorithm makes a significant contribution in decreasing the total buffer requirement, especially when the user access pattern is biased in favor of a small set of files. The idea of the proposed scheme is modeled in detail using an analytical formulation, and optimality of the algorithm is proved. An analytical framework is developed so that the proposed scheme can be used in combination with various existing disk-scheduling strategies. Our simulation results confirm that under certain circumstances, it is much more resource efficient to support some of the playbacks in memory mode and subsequently the proposed scheme enables the server to minimize the overall buffer space requirement.     

工业以太网控制系统中网络节点位置信息自动绑定协议研究

在DHCP协议基础上提出p_DHCP协议。p_DHCP继承DHCP的传输协议,具体化DHCP的地址分配机制。在现场维护人员按照规定的流程为控制系统更换和添加网络节点的情况下,p_DHCP协议能够实现工业以太网控制系统中网络节点逻辑位置信息的自动绑定。