Next: Performance Evaluation Laboratory Up: Department of Computer Previous: Distributed Parallel Processing Laboratory

Computer Networks Laboratory


/ V. B. Marakhovsky / Professor
/ Zi Xue Cheng / Associate Professor
/ Akio Koyama / Assistant Professor

Computer Networks Laboratory is working in six directions within Research Projects.

  1. Logical-timing and Decentralized Control in Computing Systems;
  2. Beta-CMOS implementation of artificial neuron;
  3. Network-based Computing and Distributed Computing;
  4. Network Agents;
  5. Network Applications.
  6. A Media Access Protocol for Super High Speed Networks.

1. Logical-timing and Decentralized Control in Computing Systems

One of the main problem of this direction is Global Synchronization of Asynchronous Arrays in Logical Time. It is shown that the duration of current transient process in CMOS circuits depends on the number of concurrently switching gates k, increasing approximately by $ln k$. It makes doubtful the efficiency of using current sensors in circuits with high concurrency. A class of circuits is discussed for which efficient usage of current sensors is suggested.

2. Beta-CMOS implementation of artificial neuron

2.1 The improved version of digital-analog CMOS implementation of an artificial neuron is suggested. It is built on the basis of the circuit consisting of synapses, $\beta$-comparator and output amplifier. It has been shown that higher non-linearity of the $\beta$-comparator in the threshold zone can sharply increase the threshold of the realized functions and noise-stability of the neuron.

2.2 The functional possibilities, parameter stability, and learnability of the artificial $\beta$-CMOS neuron have been considered. The SPICE simulation results confirm that the neuron is learnable to realize threshold functions up to 12 variables.

2.3 One of the problems in designing analog/digital artificial neuron is answering the question about what class of threshold functions can be used for testing the learnable neuron. It was shown that Gorner's threshold functions cover wide range of input weights, have big value of the threshold, and can be recommended for usage as test functions.

2.4 The earlier suggested neuron implementation contains only synapses with excitatory inputs. However, most problems solved by artificial neural networks either require inhibitory inputs. Thus the neuron should have synapses capable to form the weight and type (excitatory or inhibitory) of the input during the learning. Several synapse circuits are suggested with two capacitors for storing positive and negative input weights.

3. Network-based Distributed Computing

3.1 Distributed Resource Allocation among Overlapping Groups
In this research, we presented a new problem which described explicitly the competition for resources among process groups which may share common processes. A solution which allocates resources to groups of processes with deadlock among groups and starvation of a group never happening, was given.

3.2 Distributed Algorithms for Leader Election on Partially Ordered Keys
In this research, we generalize the traditional leader election problem, in the way that finds all the processors with the maximal keys on the basis of a partial order on the keys, and proposed two distributed algorithms for the generalized problem.

4. Network Agents

4.1 Match-making network agents which consider psychological factors of users
Match-making is a service which helps users to find suitalbe friends or partners in network environment. We developed methods for match-making, with some psychological factors of users being considered.

4.2 Learning assistant agents
In this research, we were developing teaching assiatant agents which can catch not only the understanding states of learners but also psychological states of the learners, in order to provide more efficient learning support to learners.

5. Network Applications

The goal of the project is to develop an interactive and personalized tele-education environment over Gigabit network by applying the state-of-the-art technologies in high-speed network, multimedia delivery, and intelligent software agents. Some core parts of the system were implemented and some real time online tele-lecture experiments were performed.

6. A Media Access Protocol for Super High Speed Networks

In this work, we develop a media access protocol for terabit networks such as Wavelength Dvision Multiplexing (WDM) networks. The WDM networks are promising networks which will be used in future Internet. Our goal is to design a protocol with high throughput, low delay, fairness and be used for multimedia communications.


Refereed Journal Papers

  1. Zixue Cheng, Yutaka Wada, Yukiko Inoue, Yao Xue Zhang, and Shoichi Noguchi., Distributed Resource Allocation among Overlapping Groups. Trans. of Information Processing Society of Japan, vol.42, no.2, pp.474--487, 2000.

    In this paper, we present a new model which described explicitly the competition for resources among process groups which may share common processes, and a definition of ``Distributed Allocation of Resources to process Group'' (DARG) under the model. A solution to $DARG$ is also proposed by extending an acyclic graph approach to the dining philosopher problem. Our solution allocates resources to groups of processes with deadlock among groups and starvation of a group never happening. In addition, our algorithm guarantees that more than one group work mutual exclusively, if a common process belongs to these groups.

  2. Zixue Cheng, Kshirasagar Naik, Naka Tajima, Tongjun Huang, and Shoichi Noguchi., An Efficient Distributed Algorithm for Implementation of Multi-Rendezvous based on L-Chain-Coterie. Trans. of Information Processing Society of Japan, vol.42, no.2, pp.462--473, 2000.

    Multi-Rendezvous is a powerful communication mechanism that allows a group of processes to execute an event in a synchronous way. Besides the multi-synchronou s property, Multi-Rendezvous has an exclusive property which requires no more th an one group to execute their events simultaneously, if they share a common proc ess. It is not a trivial task to implement Multi-Rendezvous in a network system. The implementation has to maintain the properties mentioned above, be fair and make progress. Some highly abstract specification languages have employed Mult i-Rendezvous to enhance the specification power of the languages, e.g. LOTOS, a specification language for communication protocols and distributed systems. $Coterie$ is a communication structure which has been used in solutions for many distributed problems such as mutual exclusion, replica control, and distributed consensus. Our previous work has shown that $coterie$ can also be used for solving implementation problem of Multi-Rendezvous, with $O(N^{1.5})$ message passes. In this paper, we propose a communication structure called {\it l}-chain-coterie, as a generalization of $coterie$, and a more efficient distributed algorithm for implementing Multi-Rendezvous based on the structure with $O(N^{1+1/l})$ message passes. Our algorithm is fully distributed and does not use manager processes and auxiliary resources.

  3. Zixue Cheng and Qian-Ping Gu., Distributed Algorithms for Leader Election on Partially Ordered Keys. Trans. of Information Processing Society of Japan, vol.42, no.2, pp.415--423, 2000.

    The leader election problem is a fundamental problem in distributed computing. The classical leader election problem can be considered as finding the processor with the maximum key in a distributed network in which each processor has one key and a total order is defined on the keys. In this paper, we define a generalized leader election problem that finds all the processors with the maximal keys on the basis of a partial order on the keys. We propose two distributed algorithms for the generalized leader election problem. The first algorithm solves the problem on a network by using a spanning tree of the network. The message complexity of the algorithm is $O(mn)$, where $m$ is the number of different keys and $n$ is the number of processors. The time complexity of the algorithm is $O(n)$. The second algorithm solves the problem using a coterie of the $n$ processors. The number of messages exchanged on the coterie is $O(\max\{rn,n^{1.5}\})$, where $r$ is the number of the maximal keys.

  4. Yao Xue Zhang, Zixue Cheng, X. Wang, H. Chen, and Shoichi Noguchi., The Design and Implementation of an QoS Control Mechanism Underlying Perceptual-Time Channel. Trans. of Information Processing Society of Japan, vol.40, no.9, pp.3564--3576, 1999.

    This paper presents a Quality of Services (QoS) control mechanism for distributed multimedia computing, and describes the design and implementation of this mechanism, which is based on the RSVP protocol. The purpose of this QoS control mechanism is to provide end users with customized computations according to the QoS demands for effective utilization of network resources. The mechanism establishes, maintains, and deletes end-to-end sessions for different multimedia streams and provides both guaranteed service and controlled load service to end users in perceptual-time, but not real time.

    We discuss the key components of the QoS control mechanism, such as the architecture of the mechanism, the mathematical definitions of QoS parameters, the implementation formats of the control packets based on the defined QoS parameters and RSVP, and the packet scheduling policy in routers. This paper describes the implementation of a prototyping system for QoS control based on the proposed control mechanism.

  5. Yao Xue Zhang, H. Chen, and Z. Cheng., The Design and Implementation of a Job-Scheduling System in Flexible Production Planning. Chinese Journal of Electronics, vol.8, no.1, pp.5--11, 1999.

    It is one of the most interesting challenges to develop a practical efficient production scheduling system for flexible or low-volume/high variety manufacturing. In this paper, we report the design and implementation of such a job scheduling system which takes into account of the influence of many factors such as machine setup times, cell changes, over-times of operators, and load balancing among machines. the system is based on a set of heuristic rules and algorithms, and also network technology, such as Intranet. Except for some description on these rules and algorithms, this paper also focuses on database construction based on object-oriented method.

  6. L. Barolli, A. Koyama, S. Motegi, S. Yokoyama., Performance Evaluation of a Genetic Algorithm based Routing Method for High-speed Networks. Tran. IEE of Japan, vol.119-C, no.5, pp.624--631, 1999.

    High-speed transmission rates bring forward their specific issues influencing the network design. To cope with high-speed networks the routing algorithms should give a fast decision. The conventional routing algorithms of slow-speed networks are generally inapplicable for high-speed networks. Modern high-speed networks will operate in gigabit speed and are expected to handle traffic patterns of various kinds. Therefore, it is required that the network control traffic methods must be adaptive, flexible, and intelligent for efficient network management. The intelligent routing algorithms based on Genetic Algorithms (GA), Neural Networks (NN), and Fuzzy Theory (FT) can prove to be efficient in high speed networks. In this paper, we propose a new adaptive routing method called ARGA (Adaptive Routing using GA). In the ARGA method, the network is modeled by a tree. The tree is reduced in the part where there are the same communication routes. In the reduced tree model, the tree junctions are represented by individual genes. By using a new gene coding method, the chromosomes have the same length, which results in easy genetic operations and an efficient routing can be achieved. Performance evaluation via simulations show that the ARGA method has a faster routing decision compared with the Genetic Load Balancing Routing (GLBR) method.

  7. A. Koyama, L. Barolli, S. Mirza and S. Yokoyama., An Exact Explicit Indication Scheme for each VC in ATM Networks. Tran. IEE of Japan, vol.119-C, no.6, pp.714--723, 1999.

    The Asynchronous Transfer Mode (ATM) technique has been accepted as a basis for the future B-ISDN networks. With the B-ISDN/ATM goals of supporting diverse services and traffic mixes, and of efficient network resource engineering, the design of the traffic control becomes a difficult task. The ATM Forum has chosen the rate-based scheme as an approach to congestion control for the Available Bit Rate (ABR) services. So far, many rate-based congestion control schemes have been proposed. Some of them use the negative feedback rate control. Therefore, if all notification cells in backward direction experience extreme congestion, the overall network congestion collapse may happen. Others use the positive feedback rate control, but the unfair distribution of available bandwidth among Virtual Connections (VCs) may occur. To resolve the problems of the existing rate-based control scheme, in this paper, we propose a new congestion control scheme called Exact Explicit Rate Indication (EERI) scheme. In the EERI scheme, the network explicitly informs each source the exact rate they should transmit a message. The network determines the rate of each source based on the fair rate setting procedure. The rate determination mechanism doesn't require per-connection queuing or per-accounting in the network, which are considered expensive techniques with the current hardware technology. By using the Benchmark Fairness Configuration (BFC), we show that the proposed scheme can achieve an excellent fairness performance among connections existing in the network. Furthermore, in the EERI scheme there are not oscillations in the rate allocation. In the transient behavior, the EERI scheme offers fast access to available bandwidth, which is a sensible requirement particularly in the LAN and MAN environments.

  8. A. Koyama, L. Barolli and S. Yokoyama., Enhanced Self-Token Protocol for High-Speed Multimedia Communications. Electronics and Communications in Japan, vol.82, no.12, pp.40--48, 1999.

    Local Area Networks (LAN) are considered an approach to supporting multimedia services, such as voice, video, image, and data. To realize a multimedia LAN, the priority control function must be implemented for each traffic characteristic. In this paper, we propose a multimedia protocol, called the Enhanced Self-Token Protocol, for transmitting multimedia services in a LAN environment. This method supports synchronous and asynchronous transmission by using two kind of self-tokens, one for synchronous and the other for asynchronous transmission. Synchronous data have a high priority than asynchronous data. Therefore, the bandwidth and real-time transmission of synchronous data are guaranteed. The remaining bandwidth is allocated to asynchronous data. Performance evaluation via simulations shows that synchronous data can be transmitted within the predetermined interval. A comparison with FDDI shows that the proposed method has better throughput for asynchronous data. Furthermore, the proposed protocol can guarantee the upper limit of the Token Rotation Time (TRT) as in the Timed Token Protocol.

Refereed Proceeding Papers

  1. Varshavsky, V.; Marakhovsky, V., Beta-CMOS implementation of artificial neuron. SPIE's 13th Annual International Symposium on Aerospace/Defense Sensing, Simulation, and Controls. Applications and Science of Computational Intelligence II, pp.210--221, SPIE, Orlando, Florida, April 1999.

    The improved version of digital-analog CMOS implementation of an artificial neuron is discussed. This neuron is learnable to logical threshold functions, being functionally powerful and highly noise-stable. It is built on the basis of a previously suggested circuit consisting of synapses, beta-comparator and output amplifier. Every learnable synapse contains 5 minimum transistors and a capacitor for storing the result of the learning. It has been shown that higher non-linearity of the beta-comparator in the threshold zone can sharply increase the threshold of the realized functions and noise-stability of the neuron. To increase the minimum leap of voltage at the beta-comparator output in the threshold zone which is attainable during the teaching, it is suggested to use an output amplifier with threshold hysteresis. For this aim, the neuron has three output amplifiers with different thresholds. The output of the amplifier with the middle value of threshold is the output of the neuron; the outputs of the other two amplifiers are used during the teaching. The way is suggested of refreshing the voltages (found during the teaching) on the capacitors during the evaluation process. The results of SPICE simulation prove that the neuron is learnable to most complicated threshold functions of 10 and more variables and that it is capable to maintain the learned state for a long time. In the simulation, transistor modes MOSIS BSIM3v3.1 0.8mkm were used.

  2. Varshavsky, V.; Marakhovsky, V., Learning Experiments with CMOS Artificial Neuron., Lecture Notes in Computer Science 1625, Computational Intelligence Theory and Applications, ed. by Bernard Reusch. Proceedings of the 6th Fuzzy Days International Conference on Computational Intelligence, pp.706--707, Springer, Dortmund, Germany, May 1999.

    Learning experiments with digital/analog artificial neuron by SPICE-simulation for limiting values of the parameters (such as the sum of input weights and/or threshold) requires long time that largely depends on the length of the learning (test) sequence. We suggest to use as test functions a class of threshold functions the minimum forms of which can be represented in accordance with Gorner's scheme (Gorner's functions). These functions have shortest teaching sequences and provide the neuron parameters close to the biggest ones for a given number of variables. For Gorner's function of $n$ variables the values of the variable weights and threshold form the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 ...) with the length of a unit learning sequence equal to n+1.

  3. Varshavsky, V.; Marakhovsky, V., Beta-CMOS Artificial Neuron and Implementability Limits. Lecture Notes in Computer Science 1607, Engineering Applications of Bio-Inspired Artificial Neural Networks, Vol.11, pp.117--128, International Work-Conference on Artificial and Natural Neural Networks (IWANN'99). Springer, Spain, June 1999.

    The paper is focused on the functional possibilities (class of representable threshold functions), parameter stability and learnability of the artificial learnable neuron implemented on the base of CMOS beta-driven threshold element. A neuron beta-comparator circuit is suggested with a very high sensitivity to input current change that allows us to sharply increase the threshold value of the functions. The SPICE simulation results confirm that the neuron is learnable to realize threshold functions of 10, 11 and 12 variables with maximum values of threshold 89, 144 and 233 respectively. A number of experiments were conducted to determine the limits in which the working parameters of the neuron can change providing its stable functioning after learning to the functions for each of these threshold values. MOSIS BSIM3v3.1 0.8mkm transistor models were used in the SPICE simulation.

  4. Varshavsky, V.; Marakhovsky, V., The Simple Neuron CMOS Implementation Learnable to Logical Threshold Functions. Proceedings of International Workshop on Soft Computing in Industry'99 (IWSCI'99), pp.463--468, IEEE, Muroran, Hokkaido, Japan, June 1999.

    The problem of hardware implementation of artificial neuron in CMOS technology is discussed. The neuron is constructed on the base of beta-driven threshold element consisting of beta-comparator and output amplifier. The beta-comparator circuit is improved to provide a very high sensitivity to current change that allows to sharply increase the function threshold value. The full circuit of the learnable synapse consists of 5 transistors and capacitor. The neuron contains three amplifiers with different input threshold that improves its learnability. SPICE simulation confirms that the neuron is learnable to realize the most complex threshold functions of 10 and more variables. Some simulation results of teaching process of the neuron to implement the certain threshold function of 10 variables with threshold equal to 89 are given.

  5. Varshavsky, V.; Marakhovsky, V.; Tsukisaka, M.; Kato, A., Current Sensor --- Transient Process Problems. Proceedings of the 8th International Symposium on Integrated Circuits, Devices & Systems (ISIC-99), IEEE, pp.163-166, IEEE, Singapore. September 1999.

    The idea of using a current sensor to produce the signal of transient process completion in asynchronous CMOS circuits has been a subject of both hopes and disappointments for many years. In the paper, the behavior of current in the transition mode is discussed. It is shown that, unlike the voltage transient process, the duration of current transient process depends on the number of concurrently switching gates k, increasing approximately by ln k. Generally, it makes doubtful the efficiency of using current sensors in circuits with high concurrency. A class of circuits with high concurrency (circuits with weak transistors) is discussed for which efficient usage of current sensors is suggested.

  6. Varshavsky, V.; Marakhovsky, V., The Simple Neuron CMOS Implementation Learnable to Logical Threshold FunctionsImolementability Restrictions on the Beta-CMOS Artificial Neuron. Proceedings of the 6th International Conference on Electronics, Circuits and Systems (ICECS'99), pp.401--405, IEEE, Pafos, Cyprus, September 1999.

    The paper is focused on the functional possibilities, parameter stability and learnability of the artificial learnable neuron implemented on the base of CMOS beta-driven threshold element. A neuron beta-comparator circuit is suggested with a very high sensitivity to input current change that allows us to sharply increase the threshold value of the functions. The SPICE simulation results confirm that the neuron is learnable to realize threshold functions of 10, 11 and 12 variables with maximum values of threshold 89, 144 and 233 respectively. A number of experiments were conducted to determine the limits in which the working parameters of the neuron can change providing its stable functioning after learning to the functions for each of these threshold values. MOSIS BSIM3v3.1 0.8mkm transistor models were used in the SPICE simulation.

  7. Varshavsky, V.; Marakhovsky, V., Non-Isotonous Beta-Driven Artificial Neuron. Proceedings of SPIE. Applications and Science of Computational Intelligence III, pp.250--257, SPIE, Orlando, Florida, April 2000.

    In the paper we discuss variants of digital-analog CMOS implementation of artificial neuron taught to logical threshold functions. The implementation is based on earlier suggested beta-driven neuron circuit consisting of synapses with excitatory inputs, beta-comparator and three output amplifiers. Such a circuit can be taught only to threshold functions with positive weights of variables, which belong to the class of isotonous Boolean functions. However, most problems solved by artificial neural networks either require inhibitory inputs. If the input type (excitatory or inhibitory) is known beforehand, the problem of inverting the weight sign is solved trivially by inverting the respective variable. Otherwise, the neuron should have synapses capable of forming the weight and type of the input during the learning, using only increment and decrement signals. A neuron with such synapses can learn an arbitrary threshold function of a certain number of variables. Synapse circuits are suggested with two or one memory element for storing positive and negative input weights. The results of SPICE simulation prove that the problem of teaching non-isotonous threshold functions to a neuron has stable solutions.

  8. H.H. Cheng, Z. Cheng, and Shoichi Noguchi., Individualized Course on Demand Based on Knowledge Base. Proceedings of IPSJ workshop on multimedia communication and distributed processing, IPSJ symposium series, pp.115--120, IPSJ, IPSJ, Dec. 1999.

    Virtual University and distance learning systems worldwide are trying to provide on the Internet online courses that are accessible to anyone, from anywhere, at anytime. In this paper, we propose the course on demand model in our Virtual University Project. the model is based on semantics network and is intended to produce highly interactive and individual-oriented courses on learners' specific demands. In this model, we define two major types of knowledge units, and establish a response channel and response manipulation mechanism to collect learners' data upon which dynamic content selection can be achieved.

  9. L. Barolli, A. Koyama, S. Yokoyama, T. Yamada., An Agent-based Distributed Routing Strategy for High Speed Large Scale Networks. IEEE International Workshop on Intelligent Signal Processing and Communication Systems (ISPACS'99), pp.13--16, IEEE, Dec. 1999.

    The routing algorithms for high speed networks should have a fast decision. To achieve this, they should be distributed for the purposes of reliability and the routing decision should be made at the source or destination in order to avoid computations at intermediate nodes. The conventional centralized routing algorithms are computationally expensive. Also, the database increases with the network size and can be large for a network with many nodes. To cope with high speed large scale networks, traffic methods must be adaptive, flexible, and intelligent for efficient network management. This paper proposes a distributed routing strategy for high speed large scale networks based on cooperative agents. This strategy uses both simple and intelligent agents. The intelligent agents are based on fuzzy theory and genetic algorithms. The network is partitioned into multiple domains and each domain has its own agents. All agents cooperate together to handle admission control and routing of connections. This strategy is able to scale up the network in order to deal with the increasing users demands and number of switches.

  10. L. Barolli, A. Koyama, T. Yamada, S. Yokoyama., A Comparative Analysis of Two Genetic Algorithm Based Routing Methods for High-speed Networks. APGA'2000, pp.332--341, May 1999.

    High-speed transmission rates bring forward their specific issues influencing the design of network hardware and software. The high-speed traffic requires a fast information processing. The conventional routing algorithms of slow-speed networks are generally inapplicable for high-speed networks. Traffic control methods for high-speed networks must be adaptive, flexible, and intelligent for efficient network management. The intelligent routing algorithms based on Genetic Algorithms (GAs), Neural Networks (NNs), and Fuzzy Theory (FT) can prove to be efficient in high-speed networks. In this paper, we propose a novel adaptive routing method called ARGA (Adaptive Routing using GAs). The ARGA method is compared with a Genetic Load Balancing Routing (GLBR) method. Performance evaluation via simulations show that the ARGA method has a faster routing decision compared with GLBR method.

  11. L. Barolli, A. Koyama, T. Yamada, S. Yokoyama., An Intelligent Fuzzy Routing Scheme for Improving ATM Networks Performance Using Violation Tagging Function. accepted, NBIS'2000/DEXA'2000, Sep. 2000.

    In ATM networks, the traffic control design becomes an important challenge, because of the diverse services support and the need for an efficient network resource engineering. To cope with rapidly changing network conditions, the traffic control methods for high speed networks must be adaptive, flexible, and intelligent for efficient network management. Use of intelligent algorithms based on fuzzy logic, neural networks and genetic algorithms can prove to be efficient for traffic control in ATM networks. In this paper, we propose a routing scheme which is based on fuzzy logic. The proposed scheme by routing the tagged cells can improve the network utilization. Performance evaluation via simulations shows that DPFC decision is very close to the ideal one. The DPFC and FRM were able to send to the destination node 31% and 54% of tagged cells, respectively.

Academic Activities

  1. Vyacheslav B. Marakhovsky., Member of ACM.

  2. Vyacheslav B. Marakhovsky., Member of IEEE.



Next: Performance Evaluation Laboratory Up: Department of Computer Previous: Distributed Parallel Processing Laboratory


www@u-aizu.ac.jp
July 2000