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

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

1. Logical-timing and Decentralized Control in Computing Systems;
2. Network-based Computing;
3. Protocol Engineering and Conformance Testing;

1. Logical-timing and Decentralized Control in Computing Systems

1. 1.1 Asynchronous Interaction in Massively Parallel Computing Systems: 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.
2. 1.2 Asynchronous interfaces:} The design of a speed-independent communication channel based on a pipeline token-ring architecture is described.
3. 1.3 Asynchronous Event Control Design Using Simulating Circuits: An approach to design asynchronous systems that coordinate concurrent discrete events is discussed. The method of direct translation of interact specifications using Petri nets is being improved. Modifications of the known modules, a number of new modules modeling fragments of Petri nets and minimization procedures are developed.
4. 1.4 Asynchronous Timing of Arrays with Synchronus Proto-type: We developed the idea of decomposing an asynchronous array to the automata stratum (close to the synchronous prototype array with cells modified to organize timing handshake) and synchronization stratum which functions as a distributed asynchronous clock. Various disciplines of prototype timing and the corresponding synchro-stratum implementations are considered.
5. 1.5 Data-Controlled Delays in the Asynchronous Design: Asynchronous design technique has an approach of using padding delays to produce signals of transient process completion. To increase the efficiency of this approach, we suggested to use data-controlled incorporated delays. The approach is illustrated by an example of asynchronous adder design.

2. Network-based Computing

1. 2.1 Specification and Design of Multimedia Synchronizers We showed how detailed implementations of synchronizers for multimedia presentation can be derived from their high-level requirement specifications. We selected a time interval notation to specify synchronization requirements, and suggested a scheme to obtain timed Petri nets from the notation. The timed Petri net for a requirement specification is further simplified to obtain a hardware design of corresponding synchronizer.

2. 2.2 Algorithm Development for Mobile Computing Mobility of computers while still being connected to networks will add a new dimension to the computing problems. We focus on the specification and verification aspect of software systems in a mobile environment.
3. 2.3 Testing of Distributed Software Systems Testing and debugging distributed softwares is a challenging task. One major step in testing distributed softwares is evaluating global conditions. We focus on how to efficiently evaluate global conditions by structuring the set of processes in a distributed application.

3. Protocol Engineering and Conformance Testing

1. 3.1 Protocol Specification Support: In order to automate the development of protocols, we investigated methods to support the development of protocol specification based on formal description technique LOTOS.
2. 3.2 Protocol implementation: First Order Multiparty Interactions is powerful concept in the abstract specification of communication protocols. However, implementing First Order Multiparty Interactions is a difficult task. We developed a distributed algorithm for implementing First Order Multiparty Interactions, which can be used as foundation of protocol implementations.
3. 3.3 Protocols for distributed problems: We have developed some protocols for distributed ranking, sorting, and consensus problems in distributed systems.

Refereed Journal Papers

1. K. Naik. Automatic hardware synthesis of multimedia synchronizers from high-level specifications. IEICE Trans. on Information and Systems, E79-D(6):160--168, July 1996.

In this paper, we show that by suitably selecting a notation to construct synchronization requirement specifications (SRS) for multimedia presentation we can express the timing characteristics at an abstract level, verify the specification, and obtain a hardware implementation through a sequence of transformations of the specification. First, we introduce the notion of a well-formed SRS and its hardware model. Second, we model an SRS as a timed Petri net and interpret the transitions of the net as hardware signals. To obtain logic functions from the SRS, we simplify the net and obtain a signal transition graph satisfying the unique state coding property. Finally, we show how to obtain a logic-level design of synchronizers.

2. V. Varshavsky, V. Marakhovsky, and V. Smolensky. Design of self-timed non-autonomous devices specified by the model of finite automaton. IEEE Design and Test of Computers, Vol.12(1):14--23, 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, 1996.

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. P. Termsinsuwan, Zixue CHENG, and N. Shiratori. A new approach to adt specification support based on reuse of similar adt by the application of case-base reasoning. International Journal: Information and Software Technology, Vol. 38(09):555--568, 1996.

In this paper, we first propose an ADT specification Model which defines a data carrier part of an ADT as a combination of constructors of four patterns. Based on the specification model, a similarity definition is given. Furthermore we have designed the support system. Finally, in order to evaluate the effectiveness of the system, we experimented with data types of service and protocol in data communication field. From the evaluation, the effectiveness of the system is ensured.

5. Pairoj TERMSINSUWAN, Zixue CHENG, and Norio SHIRATORI. Asse: A support environment for adt specification based on reuse of similar adt. Journal of Information Processing Society of Japan, 1996.

No abstract.

Refereed Proceeding Papers

1. K. Naik and Z. Cheng. Agents and coordinators: A scheme for distributed implementation of the disabling operator in lotos. In Cheeha Kim, editor, 10th. International Conference on Information Networking, pages 177--184, January 1996.

In this paper, we propose a scheme for distributed implementation of the disabling operator in LOTOS. Our main contribution lies in transforming the operational semantics of the disabling operator to a distributed implementation. The distributed implementation is specified as a hierarchy of finite-state machines (FSM) which communicate among themselves by message passing. We define an agent process for each behavior expression not containing any disabling operator and a coordinator process for each instance of the disabling operator. After selecting an event, an agent process requests a coordinator process whether it can execute the event. The coordinator processes collectively keep track of the status of all the agent processes and accordingly allow or disallow an agent to execute the event. A three-way interaction mechanism between an agent and a coordinator and between two coordinators is defined. Detailed behaviors of the agent and coordinator processes are specified as communicating FSMs, which are easy to implement.

2. V. Varshavsky and V. Marakhovsky. Asynchronous control device design by net model behavior simulation. In Lecture Notes in Computer Science 1091. Application and Theory of Petri Nets 1996. Proceedings of the 17th International Conference, volume 1091, pages 497--515, Osaka, Japan, June 1996. Sprinder.

We discuss the problem of designing asynchronous control devices for discrete event coordination specified by a Petri net model. The design is based on the compilation of standard circuit modules corresponding to PN fragments into a net modeling PN behavior and on the semantic interpretation of the modeling circuit. The impossibility of asynchronous implementation of the indivisible operation of marking change at the circuit level leads to the necessity of modeling PN with modified rules of marking change. Modifications of the known modules, a number of new module types, the rules of the module connections, and the procedures of minimization are given that considerably improve the quality of the obtained solutions in terms of both speed and area. The design reefs'' are fixed. The minimization procedures are usually associated with a change of marking change rules producing the problems of providing the equivalence of the initial and modified PNs.

3. V. Varshavsky and V. Marakhovsky. Hardware support of discrete event coordination (accepted). In The 3rd Workshop on Discrete Event Systems (WODES'96), Edinburgh, UK, August 1996.

An approach to design asynchronous systems that coordinate concurrent discrete events of an arbitrary physical nature is discussed. To build asynchronous control circuits that coordinate process interaction, the method of direct translation of interact specifications using Petri nets is being developed. Modifications of the known modules and a number of new modules modeling fragments of Petri nets are given. These modules considerably improve the quality of the obtained solutions. The design reefs'' are fixed. The minimization procedures are associated with a change of marking change rules.

4. V. Varshavsky, V. Marakhovsky, and T.A. Chu. Logical timing (global synchronization of asynchronous arrays). In The first Aizu International Symposium, Parallel Algorithm/Architecture Synthesis, pages 130--138, Aizu-Wakamatsu, Japan, 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.

5. V. Varshavsky, V. Marakhovsky, and R. Lashevsky. Asynchronous interaction in massively parallel computing systems. In Proceedings of the IEEE First International Conference on Algorithms and Architectures for Parallel Processing, volume 2, pages 481--492, Australia, Brisbane, April 1995. IEEE, 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.

6. A. Yakovlev, V. Varshavsky, V. Marakhovsky, and A. Semenov. Designing an asynchronous pipeline token ring interface. In Proc. of the 2nd Working Conference on Asynchronous Design Methodologies, pages 32--41, London, May 1995. IEEE, IEEE Comp. Society Press.

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.

7. V.Varshavsky, V. Marakhovsky, and R. Lashevsky. Critical view on the current sensor application for self-timing in vlsi systems. In Proceedings of the ASP-DAC'95/CHDL'95/VLSI'95, pages 743--750, Chiba, Japan, August 1995. IEEE, ACM, 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.

8. V. I. Varshavsky and V. B. Marakhovsky. Asynchronous event control design using simulating circuits. In Joint Symposium on Systems, Artificial Intellegence, Nueral Networks, Discrete Event Systems and Autonomous Decemtralized Systems, pages 249--256, Toyama, Japan, November 1995. The Society of Sensing Instrument Control Engineers (SICE).

An approach to design asynchronous systems that coordinate concurrent discrete events of an arbitrary physical nature is discussed. To build asynchronous control circuits that coordinate process interaction, the method of direct translation of interact specifications using Petri nets is being developed. Modifications of the known modules and a number of new modules modeling fragments of Petri nets are given. These modules considerably improve the quality of the obtained solutions. The design reefs'' are fixed. The minimization procedures are associated with a change of marking change rules.

9. V. Varshavsky, V. Marakhovsky, and T. Chu. Asynchronous timing of arrays with synchronous prototype. In Proc. of the Second Intermational Conference on Massively Parallel Computing Systems, pages 47--54, Ischia, Italy, May 1996. Euromicro, IEEE Press.

The problem of global synchronization for asynchronous cellular automata arrays is considered. Global synchronization of an asynchronous system is treated as a homomorphic mapping of its behavior in logical time onto the behavior of the corresponding synchronous prototype system that functions in physical time. Here we developed the idea of decomposing an asynchronous array to the automata stratum (close to the synchronous prototype array with cells modified to organize timing handshake) and synchronization stratum which functions as a distributed asynchronous clock. We considered various disciplines of prototype timing and the corresponding synchro-stratum implementations.

10. V. Varshavsky, V. Marakhovsky, and M. Tsukisaka. Data-controlled delays in the asynchronous design. In IEEE International Symposium on Circuits and Systems, ISCAS'96, Atlanta, USA, May 1996. IEEE, IEEE Press.

Asynchronous design technique has an approach of using padding delays to produce signals of transient process completion. In order to increase the efficiency of this approach, we suggest to use data-controlled incorporated delays in the cases when the variations of transient process durations are determined by the sets of input signal values. The control over the value of an incorporated delay is illustrated by an example of asynchronous adder design. The results of PSPICE simulation confirm the efficiency of this approach.

11. Zixue CHENG, Tongjun Huang, and Norio Shiratori. A distributed algorithm for implementation of first-order multiparty interactions. In 1996 International Conference on Parallel and Distributed Systems (ICPADS-96), June 1996.

First-order multiparty interactions, a generation of multiparty synchronization, are a powerful communication mechanism that allows a set of processes to enroll into different roles of an interaction and to execute the interaction in a synchronous way, and guarantees conflict interactions to be executed exclusively. It is not a trivial problem to implement first-order multiparty interactions in a network environment. The implementation has to maintain the synchronous and exclusive properties mentioned above, be fair and make progress. Recently, Joung et al. gave a definition of the first-order multiparty interactions and presented a distributed algorithm with message complexity $O(|P|^2)$ as solution to the problem (Joung et al.), where $|P|$ is the number of set of processes which may potentially enroll into some roles of the interaction. So far Joung's algorithm is the only one for first-order multiparty interactions by our knowledge. In Joung's algorithm, a coordinator is devised for each process, and each coordinator tries to capture other processes for establishing a quorum. The Joung's algorithm is not a fully distributed one due to the following two reasons: (1) every coordinator has to know and keep global information about the potential enrollment relation between processes and roles, and (2) the local computation time complexity is unbalanced. In this paper, we propose a new distributed algorithm for implementing first-order multiparty interactions based on a new implementation model, in which a role manager is devised for each role. Our algorithm solves the problem with $O(|R|^2 \cdot |P|)$ messages per interaction as opposed to $|P|^2$ messages required in (Joung et al.), where $|R|$ is the number of roles of the interaction and $|P|$ is the number of processes. Our algorithm is more efficient than that in (Joung et al.) when $|R|^2 < |P|$. Furthermore our algorithm is closer to the fully distributed one than that in (Joung et al.) in the sense that (1) every process (role manager) only knows its adjacent role managers (processes), and (2) the time complexity of local computation in each process and role manager is equal.

12. Zixue Cheng and David S. L. Wei. Efficient distributed ranking and sorting schemes for a coterie. In The 1996 International Symposium on Parallel Architecture, Algorithms and Networks (ISPAN'96), June 1996.

We consider the problems of distributed ranking and sorting on a Coterie, a communication structure which has proven to be a good candidate as underlying interconnection network for distributed processing. Ranking and sorting problems are harder than a consensus one, a vital and well studied problem in distributed processing, in that the later one computes for only one function (e.g. summation), while the former one actually performs $n$ functions, as ranking is to rank the key in each of $n$ sites. The currently best known decentralized consensus protocols on a coterie uses $O(n\sqrt{n})$ messages, and requires two rounds of message exchange. In this paper we show that both ranking and sorting can be done on a coterie with the same message complexity although the problems we investigate are much harder. We first present a two-round ranking algorithm which requires only $O(n\sqrt{n})$ messages. Then using this ranking algorithm, we obtain a sorting algorithm which also uses only $O(n\sqrt{n})$ messages, but requires two more rounds of message exchange. Our schemes are optimal in the sense that the lower bound of messages needed for achieving a consensus is $\Omega(n\sqrt{n})$.

Technical Reports

1. T. Huang, Z. Cheng, M. Osano, and N. Shiratori. Design of a coordinator for the committee coordination problem. Technical Report, 95-6-001, March 24, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

2. Tongjun Huang, Zixue Cheng, and Norio Shiratori. A distributed implementation for first-order multiparty synchronization. Technical Report, 96-6-001, February 28, 18pgs, The University of Aizu, Aizu-Wakamatsu, Japan, 1995.

1. Kshirasagar Naik, British Computer Society, 1996. Reviewed paper for The Computer Journal.

2. Kshirasagar Naik, IEEE communication sociaty, 1995. Reviewed a paper for the IEEE Transactions on Networking.

3. Kshirasagar Naik, IEEE Computer Society and Communication Society, 1995. Member.

4. Kshirasagar Naik, ACM, 1995. Member.

5. Vyacheslav B. Marakhovsky, IEEE, 1995. Member.

6. Vyacheslav B. Marakhovsky, ACM, 1995. Member.

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

www@u-aizu.ac.jp
October 1996