Here, we present a protocol for dynamically maintaining a degree-bounded delay sensitive spanning tree in a decentralized way on overlay networks. The protocol aims at repairing the spanning tree autonomously even if multiple node's leave operations or failures (disappearances) occur simultaneously or continuously in a specified period. It also aims at maintaining the diameter (maximum delay) of the tree as small as possible. The simulation results using ns-2 have shown that the protocol could keep reasonable diameters compared with the existing centralized static algorithm even if many node's participations and disappearances occur frequently.

In this paper, we propose a location-aware multicast protocol on MANET called MgCast (multiCAST or multiple geographical regions). Given a source node and a set of geographical destination regions, MgCast constructs and maintains a routing tree from the source to nodes which reside in the regions, in a decentralized manner. Our aim is to pursue trade-off between the route discovery ratio, the number of route request messages and the number of links of the tree. The experimental results have shown that MgCast could achieve a good balance between these metrics.

In this paper, we present a new application level multicast protocol called Emma (end-user multicast for multi-party applications) suitable for communication systems where multiple video sources are exchanged in real-time among end-hosts, such as video-conferencing. The primal feature of Emma is that video sources with the higher priority given by users are prioritized among others for the provision of quality of service at the user level and that all the operations in Emma are done in a distributed manner. Our experimental results have shown that Emma achieves reasonable performance on overlay networks with high user satisfaction.

In this paper, we propose a selection technique for replicated multicast video servers. We assume that each replicated video server transmits the same video source as different quality levels of multicast streams. Using an IGMP facility like m-trace, each receiver monitors packet count information of those streams on routers and periodically selects the one which is expected to provide low loss rate and to be suitable for the current available bandwidth of receivers. Moreover, collection of packet count information is done in a scalable and efficient manner by sharing the collected information across receivers. Our experimental results using the network simulator have shown that our method could achieve much higher quality satisfaction of receivers, under the reasonable amount of tracing traffic.

In this paper, we propose a technique to implement communication protocols as hardware circuits using a model of concurrent EFSMs with multi-way synchronization. Since use of multi-way synchronization enables simple and comprehensible specifications of recent communication protocols which frequently use complicated mechanisms such as mutual exclusion and dynamic job assignment, the proposed model is expected to reduce development cost in designing/developing such protocols. We implement specifications described in the model so that EFSMs work synchronously with the same clock, and that the synchronization mechanism for checking executability of each tuple of synchronizing transitions is implemented as a combinational logic circuit. Through some experiments, we have confirmed that the proposed technique can synthesize hardware circuits with relatively good performances for practical use.

In this paper, we propose a verification method for pipelined microprocessors with out-of-order execution. We define a class of pipelined microprocessors with out-of-order execution and give a sufficient condition that guarantees the correctness of implementation. Each microprocessor in this class has a pipeline stg/sub 1/,...,stg/sub n/ such that the stages stg/sub c/,...,stg/sub n/ are so-called "in-order pipeline" and changes the execution order of instructions within the stages of stg/sub 1/,...,stg/sub c-1/. Using our method, we carried out the correctness proof of a practical 6-stage pipelined microprocessor that has a so-called scoreboard. We used a verifier having a decision procedure for Presburger sentences. The total CPU time spent in the proof was about 8 hours.

In this paper, we propose a receiver-cooperative bandwidth management method for layered multicast streams, considering not only bandwidth requirements but also receivers' preference. In the method, we assume that each receiver has a preference value for each layer of streams. When a receiver requests an additional layer and required bandwidth is not available on links, it can let other receivers release a part of the layers of streams which they receive if it increases the sum of the satisfied preference values of all receivers as a total. We give an algorithm to calculate an optimal way of releasing layers in a polynomial time under some assumption. We did an experiment to transmit JPEG video over a private IP network and confirmed that the method could control bandwidth among the video streams within a second.

In this paper, we propose a new bandwidth allocation technique where a new stream can preempt an appropriate amount of bandwidth from other existing streams, considering both quality and priority requirements of users. The existing preemption-based technique has focused on the preemption among the streams with the same user. However, in multi-party multimedia applications, there would be a case where we would like to raise the quality of a specific stream (e.g. in a video conference, the video stream of a new chair may become more important than those of the existing participants). Therefore the preemption should be allowed among streams with different users and the best preemption in terms of their requirements should be provided. In our technique, using the algorithm for solving the minimum flow cost problem, the preemption is calculated so that the total loss of quality and priority of the existing streams can be minimized. We have implemented the proposed technique and evaluated it through the experiment using MPEG1 video streams, and have confirmed that our technique can keep a high frame rate for each existing MPEG1 video stream even when accommodating a lot of new streams.

Some methods for deriving protocol specifications from given service specifications with time constraints have been proposed. However, existing methods cannot treat the class of service specifications with both parallel synchronization and data values. They also assume that all clocks in the distributed system are synchronized. We propose an algorithm to derive a correct protocol specification automatically from a given service specification described in an extended model of time Petri nets where the above restrictions are eliminated. Using our method, we will be free from considering the details of communication delays on the design of real-time distributed systems.

In general, the services of a distributed system are provided by some cooperative protocol entities. The protocol entities must exchange some data values and synchronization messages in order to ensure the temporal ordering of the events which are described in a service specification of the distributed system. It is desirable that a correct protocol entity specification for each node can be derived automatically from a given service specification. In this paper, we propose an algorithm which synthesizes a correct protocol entity specification automatically from a service specification in a Petri Net model with Registers called PNR model. In our model, parallel events and selective operations can be described naturally. The control flow of a service specification must be described as a free-choice net in order to simplify the derivation algorithm, however, many practical systems can be described in this class. In our approach, since each protocol entity specification is also described in our PNR model, we can easily understand what events can be executed in parallel at each protocol entity.

In this paper, we propose a method to synthesize protocol specifications automatically from service specifications written in a time-extended LOTOS called LOTOS/T+. In LOTOS/T+, structured descriptions, such as parallelism and interruption are allowed to describe service specifications, and time-constraints among non-adjacent actions can be described using Presburger formulas. Here we assume that there is a reliable communication channel between any two nodes and the maximum communication delay for each channel is bounded by a constant. Moreover we assume service specifications have no deadlocks. Under our simulation policy, a specification S' is derived from a given service specification S and a given maximum communication delay of each channel. In S', time-constraints necessary for exchanging synchronization messages are added. If S and S' can carry out the same behaviour, i.e., if S and S' are bisimulation equivalent when time is ignored, then a correct protocol specification for simulating S is derived from S' automatically.

In this paper, we propose a method for visualizing LOTOS specifications using multi-rendezvous mechanism. For visualization, we have extended LOTOS by introducing some primitive animation events. Using the extended LOTOS, we describe a visualization scenario for events where we would like to visualize their execution. Then, we execute the original specification and its visualization scenario in parallel under LOTOS multi-rendezvous mechanism so that the corresponding animation is activated when each event is executed. The pair of the original specification and its visualization scenario is converted into the multi-threaded object code using our LOTOS compiler. In our visualization method we can specify the visualization scenario without modifying the original specification, and we can derive an object code which animates the original specification in real time. We have tried to visualize a LOTOS specification of "Dijkstra's dining philosophers", and evaluated the usefulness of our approach.

The authors propose a synthetic technique to derive a correct protocol specification from a given service specification modeled as a nondeterministic extended finite state machine (EFSM). Each EFSM has a finite state control and a finite number of registers. In the model, the next state and the next values of the registers are determined depending on not only the current state and input but also the current values of the registers. The registers correspond to the system resources and they are allocated to some of the protocol entities in a distributed system. The derived protocol entities' specifications satisfy the resource allocation specified by the designer. A procedure solving 0-1 integer linear programming problems is used to reduce the number of the messages exchanged among the protocol entities.>

It is well known that algebraic specification methods are promising for specifying programs and for verifying their various properties formally. In this paper, an algebraic specification of information transfer procedures of high-level data link control (HDLC) procedures is presented and some of the main properties of the specification are shown. First, we introduce abstract states, state transition functions, and output functions corresponding to elementary notions extracted from the description of HDLC procedures in ISO 3309-1979 (E) and ISO 4335-1979 (E). Second, we show axioms which represent the relations between the values of functions before and after the state transitions. Then, it is proved that the specification is ``consistent,'' ``sufficiently complete,'' and ``nonredundant.'' Also it is shown that an implementation which realizes the specification is naturally derived. In the last section, verification of various properties of HDLC procedures is formulated in the same framework as the algebraic specification, and some verification examples are presented.

Two decision problems related to multivalued dependencies in a relational database are considered. In this paper, an algorithm is presented for deciding whether or not a multivalued dependency can be derived from sets F of functional dependencies and M of multivalued dependencies on a set U of attributes, whose running time is proportional to min $(k^2 |U|,||F \cup M||^2 )$ where k and $|U|$ are the numbers of dependencies in $F \cup M$ and attributes in U, respectively, and $||F \cup M||$ is the size of description of F and M. A related algorithm is also considered which decides whether or not there exists a nontrivial multivalued dependency that is valid in a projection of the original relation.

This paper presents a systematic procedure for finding optimum error-correcting group codes for the binary symmetric channel with m check digits and a minimum distance not less than do, where m and do are given integers. Some new schemes for reducing the computing time are used. The search procedure is readily programmable for computer execution and several programs were carried out on an IBM 7044. The newly found seven optimum triple-error-correcting group codes and six optimum double-error-correcting group codes including five quasi-perfect double-error-correcting codes are tabulated. Also, a list of optimum shortened cyclic codes found by a similar procedure is presented. The efficiency of the search procedure is demonstrated by the fact that the program yielded the new codes in a fairly short time.