Next: Performance Evaluation Laboratory Up: Department of Computer Previous: Operating Systems Laboratory

# Computer Networks Laboratory

/ V. B. Marakhovsky / Professor
/ Zi Xue Cheng / Assistant Professor
/ Kshirasagar Naik / Assistant Professor

The Computer Networks Laboratory is working in four directions within Research Projects and Top-Down Education Course-ware Development Projects:

• Self-timing and Event-driven Systems;
• Multi-media Communication and Synchronization;
• Protocol Engineering and Conformance Testing;
• Modeling of Autonomous Decentralized Cooperative Systems.

1. Self-timing and Event-driven Systems

1.1 Structural methods of self-timed device synthesis: A procedure of designing a self-timed device defined by the model of finite automaton is suggested.

1.2 Global Synchronization in massively parallel computing systems: The problem of global synchronization is solved for asynchronous processor arrays with an arbitrary interconnection graph. The solution is based on decomposing the system to the processor stratum and synchro-stratum. For the case of a synchronous system with two-phase master-slave synchronization, several simple implementations of the synchro-stratum for the corresponding asynchronous system are proposed.

1.3 Self-timed interfaces: The transition from synchronized working of the system to its globally asynchronous behavior requires that all local processes in the system should interact between each other on the base of asynchronous interfaces. The possibility of organizing single-wire bit handshake is demonstrated and self-timed circuits of transmission/reception are developed with throughput not worse than of double-wire circuits. Using single-wire bit handshake allows one to transmit n-bit binary code by n+2 communication lines.

1.4 Self-timing with current sensors: The idea of applying current indication of transient process completion to construct asynchronous blocks of CMOS VLSI systems is considered. We analyzed design principles and characteristics of the known current sensors, formulated stubborn problems of their using, suggested improved circuits and two ways of the interaction between blocks with current sensors.

2. Multi-media Communication and Synchronization

Fault-tolerance in Multi-media Synchronization: We proposed a presentation architecture suitable for network-based multi-media applications. The main idea in the architecture is to reduce and tolerate presentation faults. We showed how detailed design of such an architecture can be obtained from its requirement specification.

3. Protocol Engineering and Conformance Testing

3.1 Protocol Synthesis: To automate the development of protocols, we investigated a methodology to synthesize a protocol without logic errors such as deadlock based on formal description technique LOTOS.

3.2 Protocol implementation: Multi-Rendezvous is powerful concept in the abstract specification of communication protocols. However, implementing Multi-Rendezvous is a difficult task. We developed three distributed algorithms for implementing Multi-Rendezvous, which can be used as foundation of protocol implementations.

3.3 Distributed Group Resource Allocation Method: Recent new applications, such as supporting collaborative group work, distributed cooperative development of software, causes a new resource allocation problem that some resources are competed for by several groups of processes. We present a model to describe the new problem and a distributed algorithm as a solution to the problem.

3.4 Fault-tolerant State Verification Sequence: The idea of Unique Input/Output (UIO) sequences in a finite-state machine is an attractive way to verify a state of a machine. However, faults in an implementation make such verification a difficult task. We developed the idea of fault-tolerant UIO sequences that enables us to verify states in spite of some faults in an implementation.

4. Modeling of Autonomous Decentralized Cooperative Systems

Modelling for Autonomous Decentralized Systems: A model for negotiation among the various types of agents in autonomous decentralized systems was proposed based on the Transaction Analysis Theory. The model deals with the effect of attitude of agents in negotiation.

Refereed Journal Papers

1. K. Naik. Fault-tolerance and exception handling in multimedia synchronization (to appear). IEEE Journal on Selected Areas in Communication, January 1996.

This paper contributes toward exception handling and fault-tolerance in multi-media presentation. Our study is based on the well-known four phases in fault-tolerant computing: fault detection, damage assessment, error recovery, and continued service. We define a {\it fault} in multi-media synchronization and a simple fault detection mechanism. Using the concept of a partner set of a media stream, we assess the damage caused to media presentation due to a fault. From the point of error recovery and reducing synchronization failures, we introduce the ideas of a k-cycle virtual fault. A k-cycle virtual fault suggests the possibility of a failure in the future after $k$ presentation cycles. Detection of a possible presentation failure in the future gives lead time to take corrective measures to avoid the failure. In order to handle exception conditions during a synchronization failure, we define pinned and sliding semantics of media presentation. These two semantics allow us to define different levels of quality of presentation during a failure. Finally, we present the detailed design of a fault-tolerant presentation architecture and prove its properties. We discuss how the ideas of virtual fault and damage assessment can be used in generating useful information for the underlying data transfer protocol so that synchronization failures can be reduced.

2. V. Varshavsky, V. Marakhovsky, and V. Smolensky. Design of self-timed non-autonomous devices specified by the model of finite automaton. IEEE Design & Test of Computers, 12(1):14--23, Spring 1995.

A procedure of designing a self-timed device defined by the model of finite automaton is suggested. In accordance with the chosen automaton standard implementation structure from the automaton transition/output graph one derives the Signal Graph Specification that then is processed by the formal synthesis procedure for self-timed implementation. The design procedure is illustrated by two examples: Stack Memory and Counter with Constant Acknowledge Delay.

3. V. Varshavsky, V. Marakhovsky, and R. Lashevsky. Self-timed data transmission in massively parallel computing systems (in printing). Integrated Computer Aided Engineering, 1995.

Local processes in MPCS can be coordinated by asynchronous system of global synchronization via handshake using current sensors for detection of the transient processes completion. The known current sensors are considered, the best one is analyzed and its shortcomings are revealed. Current sensor with wide range of the measured current is suggested. The principles of control in circuits with current sensors are developed. Self-timed data exchange between local processes of the system is discussed. Transmission/reception circuits with single-wire bit handshake are demonstrated. Their transmission rate is no worse than that of double-wire circuits. They allow one to transmit combinations of $n$-bit code by $n+2$ communication lines.

4. Bhed Bahadur BISTA, Zixue CHENG, Atsushi TOGASHI, and Norio SHIRATORI. A new approach for protocol synthesis based on LOTOS. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E77-A(10):1646--1655, October 1994.

This paper presents a new automatic synthesis algorithm to construct two communicating protocol entities. The specifications of entities are in LOTOS. We also give definitions of logic errors which are different from the logic errors in the protocol synthesis based on FSMs. The synthesized protocol is proved to be logic error free. The protocol synthesis algorithm is applicable to every structure of protocol layer which provides services to its upper layer. To show the effectiveness of the proposed synthesis algorithm, we have applied it to a simplified version of the protocol handler of the Transport Layer.

Refereed Proceeding Papers

1. K. Naik. Multimedia synchronization: From specification to logic gates. In 1st ISMM International Conference on Distributed Multimedia Systems. ISMM, August 1994.

The objective of this paper is to obtain a gate-level description of a multimedia synchronizer specified in a time interval notation. A synchronization requirement specification (SRS) is modeled as a Timed Petri Net from which a Timed Signal Transition Graph (TSTG) is obtained. An asynchronous circuit, who output satisfies the synchronization requirement, is derived from the TSTG.

2. K. Naik. Distributed implementation of multi-rendezvous in LOTOS using the orthogonal communication structure in Linda. In Eric Manning, editor, 15th International Conference on Distributed Computing Systems,. IEEE Press, June 1995.

We argue that the programming simplicity and message passing complexity of implementing LOTOS multi-rendezvous largely depends on the underlying communication structure. The programming simplicity and low complexity of our algorithm are due to our viewing the multi-rendezvous problem as a distributed mutual exclusion problem. Using the parallel programming environment of Linda, we present an efficient algorithm to easily implement multi-rendezvous in LOTOS. The orthogonal communication structure in Linda allows us to separate synchronization concerns in multi-rendezvous from concerns in interprocess communication in an implementation. The concept of Tuple Space in Linda and the associated $in$, $out$, and $rd$ primitives for managing the tuple space lead to an elegant programming style for distributed implementation of multi-rendezvous.

3. K. Naik. Fault-tolerant uio sequences in finite state machines. In 8th. International Workshop on Protocol Test Systems. IFIP, September 1995.

The central idea in the paper is to define the concept of strength of a UIO sequence in verifying a state in a faulty implementation. The strength of a UIO sequence is a quantitative measure of the number of output faults required to render the verification power of the sequence ineffective. Thus, UIO sequences of higher strengths can tolerate more output faults while verifying a state. We present an algorithm to compute all UIO sequences of maximal strength in a state machine. The UIO sequences of maximal strength give an idea about the upper limit on the fault detection capability of a UIO-based test sequence.

4. V. Varshavsky and V. Marakhovsky. Fault-tolerant self-timed system mono-channel. In Technical Report of IEICE. CPSY94-14 26, volume 94 No.15, pages 80--85, Tokyo, Japan, March 1994. The Institute of Electronics, Information and Communication Engineers.

The problems of designing self-timed circuitry based fault-tolerant ring communication channel for multi-computer control systems are discussed. The technical solutions suggested are the basis of the logic project of a communication channel adapter designed for a fault-tolerant airborne multi-computer system with the local area network architecture. The basic element of such an adapter is a mono-channel controller consisting of the protocol automaton and the automaton of control and recovery. The approaches to self-timed realization of these automata and the principles of mono-channel self-recovery organization are stated.

5. V. Varshavsky, V. Marakhovsky, and T. A. Chu. Logical timing (global synchronization of asynchronous arrays). In N. Mirenkov, Q. P. Gu, S. Peng, and S. Sedukhin, editors, International Symposium on Parallel Algorithm/Architecture Synthesis, pages 130--138, Aizu-Wakamatsu, Japan, March 1995. The University of Aizu, IEEE CS Press.

The problem of global synchronization is solved for asynchronous processor arrays and multiprocessor systems with an arbitrary interconnection graph. Global synchronization of asynchronous systems is treated as a homomorphic mapping of an asynchronous system behavior in logical time onto the behavior of the corresponding synchronous system with a common clock functioning in physical time. The solution is based on decomposing the system to the processor stratum and synchro-stratum; the latter plays the role of a global asynchronous clock. For the case of a synchronous system with two-phase master-slave synchronization, a simple implementation of the synchro-stratum for the corresponding asynchronous system is proposed. It is shown that, depending on the local behavior of the processors, the synchro-stratum is able to perform two types of global synchronization: parallel synchronization and synchronization that uses a system of synchro-waves.

6. V. Varshavsky, V. Marakhovsky, and R. Lashevsky. Asynchronous interaction in massively parallel computing systems. In V. L. Narasimhan, editor, IEEE First International Conference on Algorithms and Architecture for Parallel Processing ICA 3PP-95, volume 2, pages 481--492, Brisbane, Australia, April 1995. The University of Queensland, IEEE CS Press.

The problems are discussed that arise when designing massively parallel computer systems. The transition from globally synchronized working of such systems to globally asynchronous behavior resolves most of them. The problems of asynchronous interaction of local processes with the system of their global coordination on the base of handshake are considered as well as the problems of self-timed data transmission between processes. If the system modules that realize local processes are not asynchronous and implemented in CMOS-technology, then, to detect the moments of the transient processes completion in them, the idea of current indication is used. A circuit of a current sensor is suggested with wide range of permissible changes of the measured current and with admissible characteristics. Two ways of organizing the interaction between circuits with current sensors are developed. The principles of self-timed data exchange between local processes of the system and data transmission by means of a dual-rail code and binary code with handshake for every bit are considered. The possibility of organizing single-wire bit handshake is demonstrated and its self-timed implementation is developed with the transmission rate no worse than that of double-wire bit handshake.

7. A. Yakovlev, V. Varshavsky, V. Marakhovsky, and A. Semenov. Asynchronous pipeline token ring interface. In 2nd Working Conference on Asynchronous Design Methodologies, London, UK, pages 32--41. IEEE Comp. Society Press, N. Y, May 1995.

We describe the design of a speed-independent communication channel based on a pipeline token-ring architecture. We believe that this approach can help reduce some negative "analogue" effects inherent in asynchronous buses (including on-chip ones) by means of using only "point-to-point" interconnections. We briefly outline the major ideas of the channal's organization, protocol and our syntax-driven implementation of the channel protocol controller. The protocol has been recently verified for deadlock-freedom and fairness.

8. V. Varshavsky, V. Marakhovsky, and R. Lashevsky. Critical view on the current sensor application for self-timing in VLSI systems. In Proceeding of the ASP-DAC'95/CHDL'95/VLSI'95 Conference, pages 743--750, Tokyo, Japan, August 1995. IEEE Press.

To solve the problem of global synchronization in massively parallel VLSI systems, it is necessary to organize asynchronous interaction between system blocks. The possibility of applying current sensors for detection of the end of signal transitions to construct asynchronous blocks in CMOS-technology is discussed. For known current sensors, their design principles and characteristics are analyzed. Two ways of organizing the interaction between circuits with current sensors are suggested. Stubborn problems of using the known current sensors that appear due to the imperfection of their characteristics are formulated. A current sensor is suggested that removes the major of these problems but is capable of working only with a particular circuit class. However, simulation results indicated that using even such sensors is not efficient enough.

9. Zixue CHENG, Tongjun HUANG, and Norio SHIRATORI. A new distributed algorithm for implementation of LOTOS multi-rendezvous. In Dieter Hogrefe and Stefan Leue, editors, Formal Description Techniques VII: Seventh International Conference on Formal Description Techniques for Distributed Systems and Communications Protocols, pages 493--504. CHAPMAN & HALL, October 1994.

LOTOS is a high level specification language which incorporates the Multi-Rendezvous. Multi-Rendezvous is a powerful communication mechanism that allows a set of processes to execute an event in synchronous way. Besides the multi-synchronous property, Multi-Rendezvous has nondeterministic and exclusion properties. It is not a trivial problem to implement Multi-Rendezvous in a network system. The implementation has to maintain the properties mentioned above, be fair and make progress. In this paper, we propose a new efficient distributed algorithm, based on the concept of coterie, for implementing Multi-Rendezvous with $O(N\sqrt{N})$ message passes. Our algorithm is fully distributed and does not use manager processes and auxiliary resources.

10. Bhed Bahadur BISTA, Zixue CHENG, Atsushi TOGASHI, and Norio SHIRATORI. A synthesis algorithm of a protocol model from a single entity. In Dieter Hogrefe and Stefan Leue, editors, Seventh International Conference on FORMAL DESCRIPTION TECHNIQUES for Distributed Systems and Communications Protocols, pages 477--492. CHAPMAN & HALL, October 1994.

Protocol entities,in communication protocols, behave under sets of communication rules (protocols). Thus it is desirable to concentrate on the design of one protocol entity and generate the corresponding protocol entity automatically by exploiting the communication rules. A protocol is desired to be formal, precise and unambiguous, in other words, it is described using FDTs (Formal Description Techniques). In this paper, we propose a protocol synthesis algorithm in which a peer protocol entity is generated from a single given entity. Unlike previous works, where FSMs (Finite State Machines) were used to synthesize partial protocols, we use LOTOS, which is one of FDTs developed by ISO, in our proposed synthesis algorithm. We prove that the resultant protocol consisting of the given entity and the generated peer entity is logical errors free, collectively represented as deadlock free, if the given entity is in certain forms which are natural in the context of communication protocols. We also present that the protocol is bisimulated by both the given entity and the peer entity to show that the protocol maintains the behaviors of the entities.

11. Zixue CHENG, Tongjun HUANG, and Norio SHIRATORI. A distributed algorithm for resource allocation among process groups. In The 9th International Conference on Information Networking (ICOIN-9), Osaka, Japan, December 1994.

Distributed resource allocation is an important problem in developing distributed systems. Many works have been done on the problem. However recent new applications, such as supporting collaborative group work, distributed cooperative development of software, cause some new problems. One of them is that some resources are competed for by several groups of processes. There may exist deadlock or starvation among groups. We call them " group deadlock'' and " group starvation''. In this paper, we first define the new resource allocation problem: Distributed Resources Allocation among Process Groups. This problem is an extension of the Distributed Resource Allocation problem. Then we present a new distributed algorithm as a solution to the problem. Our algorithm can allocate resources to groups of processes without group deadlock and group starvation.

12. Pairoj TERMSINSUWAN, Zixue CHENG, and Norio SHIRATORI. ADT specification support based on reuse of similar ADT. In The 9th International Conference on Information Networking (ICOIN-9), Osaka, Japan, December 1994.

Abstract Data Type (ADT) is a powerful method which can be used to specify data part of protocol in a implementation independent way. It also allows to conduct verification and validation. However, practically ADT is rarely used because it is difficult for a non ADT expert to specify. Due to this reason, in order to promote the spread use of ADT, support method for ADT specification is necessary, Unfortunately, there are almost no such a support method so far. We propose an ADT specification support method based on Case Base Reasoning. The support system can prevent user from spending too much time and effort in specifying the whole ADT from the beginning.

13. Zixue CHENG, Tongjun HUANG, and Norio SHIRATORI. An efficient distributed implementation for {LOTOS} multi-rendezvous. In The 9th International Conference on Information Networking (ICOIN-9), Osaka, Japan, December 1994.

In this paper, we propose a new efficient distributed algorithm for implementing Multi-Rendezvous with $2Nm$ message passes for a Multi-Rendezvous, without using auxiliary resources. Here, $N$ is the number of processes which participate in a Multi-Rendezvous, $m$ is the number of possible Multi-Rendezvous within a system. A formal specification of the algorithm in LOTOS is included in the paper.

14. Zixue CHENG, Miriam A. M. Capretz, and Minetada Osano. A model for negotiation among agents based on the transaction analysis theory. In The Second International Symposium on Autonomous Decentralized Systems ISADS 95, Phoenix, Arizona, USA, April 1995.

In this research work, interactions among the various types of agents in autonomous decentralized systems are based on the theory of Transaction Analysis (TA) of psychology. Human beings are considered one particular type of autonomous agents. Hence, the agent's structure as well as interactions among them are defined and performed much the same as human behavior and attitudes. Cooperation among agents is negotiated by exchanging {\it strokes}. After the cooperation among agents is established, each of them has a specific role to perform in order to reach a particular goal. This paper presents the definition of the inner structure of an agent along with the negotiation process occurred among them until the cooperation is established.

15. Tongjun HUANG, Zixue CHENG, Minetada Osano, and Norio SHIRATORI. A decentralized social algorithm for committee coordination problem. In The Second International Symposium on Autonomous Decentralized Systems ISADS 95, Phoenix, Arizona, USA, April 1995.

In this paper, we consider an extended committee coordination problem in an autonomous decentralized social environment. The basic committee coordination problem and a distributed algorithm, as a solution to this problem in distributed environment, are presented by K.M.Chandy and J.Misra in. The algorithm guarantees the synchronous and exclusion properties of the problem and is fair (i.e. starvation-free) and makes progress (i.e. deadlock-free). In an autonomous decentralized social environment, besides the above mentioned properties, some social properties, such as individual preference, privacy protection, and stable assignment are required to be considered and guaranteed. In this paper, we extend the committee coordination problem by introducing some social properties, such as individual preference and stable assignment and give a decentralized social algorithm as a solution to this extended problem. The algorithm guarantees not only the synchronous and exclusion properties but also individual preference and stable assignment properties.

Unrefereed Papers

1. Naka Tajima, Kazuhiko Satoh, Shinichi Saitoh, Takao Saitoh, Tongjun Huang, and Zixue Cheng (The 1st to 4th authors are students in U. of Aizu). Efficient rock-scissors-paper on distributed environment. The 50th convention of information Processing Society of Japan, 1995.

Technical Reports

1. Zixue Cheng, Miriam A. M. Capretz, and Minetada Osano. A model for negotiation among agents based on the transaction analysis theory. The University of Aizu, Software Department, 1994.

2. Tongjun HUANG, Zixue CHENG, Minetada OSANO, and Norio SHIRATORI. Design of a coordinator for the committee coordination problem. Information Systems and Technology Center, The University of Aizu, 1995.

Grants

1. Zi Xue Cheng. Ministry of education scientific research fund: Development of a support environment for generating communication software from protocol specifications. Encouragement Research (A) 06750398, 424, 1994.

1. Kshirasagar Naik, Membership of IEEE, 1994.

2. Kshirasagar Naik, Membership of ACM, 1994.

3. Kshirasagar Naik, Reviewed two papers for The Computer Journal", 1994.

4. Vyacheslav B. Marakhovsky, Membership in New York Academy of Science, 1994.

5. Vyacheslav B. Marakhovsky, Reviewed one paper for The First Aizu International Symposium on Parallel Algorithms/Architecture Synthesis"IEEE, January 1994.

6. Vyacheslav B. Marakhovsky, Membership in IEEE, 1994.

7. Vyacheslav B. Marakhovsky, Membership in ACM, 1994.

8. Zi Xue Cheng, Membership of Information Processing Society, 1994.

9. Zi Xue Cheng, Membership of IEEE, 1994.

10. Zi Xue Cheng, Membership of ACM, 1994.

Next: Performance Evaluation Laboratory Up: Department of Computer Previous: Operating Systems Laboratory

www@u-aizu.ac.jp
January 1996