A 2-switch node network is one of the most fundamental structure among communication nets such as telephone networks and local area networks etc. In this letter, we prove that a problem of designing a 2-switch node network satisfying capacity conditions of switch nodes and their link, which we call 2-switch node network problem, is NP-complete.

In this paper, an analysis of a slotted ring type network, the Pierce type ring network, is carried out and characteristics of the ring are derived. The ring type network is one of the fundamental computer network topologies. It is easy to implement and has many merits such as low cost and expansion flexibility. However, possible hogging, or domination of slots by one station, is one of its drawbacks. At first, when we regard vacant slots as usable, we show how system performance is fairly dependent on traffic patterns. We also show quantitatively that when slots are fixed to each station, domination of the ring can be completely prevented, although the performance of the system will be reduced. We propose a method to control the transmission of packets in which we have positively adopted the insertion of shift registers into the transmission line to prevent the deterioration of the performance. With the insertion of shift registers, we show the feasibility of improving the performance of the fixed slot allocation method at the same time as preventing domination of the ring. We will discuss the merits of the shift register insertion method, which is introduced to improve the fixed slot and semi-fixed slot allocation methods. In the slotted ring type system, four types of slot allocation method including a register insertion method are considered for the improvement of the system performance. The merits and demerits of the methods are discussed. We show how system performance depends on the traffic patterns considered. We analyse the characteristics of the ring system under various conditions.

We study an asynchronous transfer mode (ATM) multiplexer with selective cell discarding (SCD), and propose as a new traffic parameter the ratio of high and low priority cell streams when a cell stream multiplexed is classified by the cell loss priority (CLP) field in a cell header. By having loss priority control, it is possible to increase the multiplexing gain. For performance analysis we assume that an on-of T bursty traffic is described with several traffic parameters and the proposed priority ratio, and is approximately modeled by a Markov-modulated deterministic process (MMDP). Assuming that several independent and homogeneous on-off bursty traffics with priority discrimination are multiplexed, we present an analytical procedure for the cell loss probability of each priority level in statistical cell multiplexing with loss priority control, and use the performance results for connection admission control (CAC). Also, we consider the effect of the proposed priority ratio. Although loss priority control increases the statistical multiplexing gain, it is not appropriate for the on-off bursty traffic to change the value of the high-priority ratio in order to obtain a larger multiplexing gain, since the admissible load is determined by the loss probability of low priority traffic for most cases and the values of the ratio in a certain range slightly affect it.

In this paper, we analyze the traffic data management requirements of the customers, describe the functions of the traffic database needed to satisfy their requirements, and propose a highly distributed database system which can efficiently implement these functions. Finally, we report the results of system performance evaluations.

The traceability of data flow diagrams against structure charts is very important for large software development. Specifying if there is a relationship between a data flow diagram and a structure chart is a time consuming task. Existing CASE tools provide a way to maintain traceability. If we can extract the input-output relationship of a system from a structure chart, the corresponding data flow diagram can be automatically generated from the relationship. For example, Benedusi et al. proposed a reverse engineering methodology to reconstruct a data flow diagram from existing code. The methodology develops a hierarchical data flow diagram from dependency relationships between the program variables. The methodology, however, transforms each module in structure charts into a process in data flow diagrams. The reconstructed diagrams may have different processes with the same name. This paper proposes a transformation algorithm that solves these problems. It analyzes the structure charts and extracts the input and ouput relationships, then determines how the set of outputs depends on the set of inputs for the data flow diagram process. After that, it produces a data flow diagram based on the include operation between the sets of output items. The major characteristics of the algorithm are that it is simple, because it only uses the basic operations of sets, it generates data flow diagrams with deterministic steps, and it can generate minimal data flow diagrams. This process will reduce the cost of traceability between data flow diagrams and structure charts.

This paper described discrete time Cellular Neural Networks (DT-CNN) with two types of neuron circuits for image coding from an analog format to a digital format and their VLSI implementations. The image coding methods proposed in this paper have been investigated for a purpose of transmission of a coded image and restoration again without a large loss of an original image information. Each neuron circuti of a network receives one pixel of an input image, and processes it with binary outputs data fed from neighboring neuron circuits. Parallel dynamics quantization methods have been adopted for image coding methods. They are performed in networks to decide an output binary value of each neuron circuit according to output values of neighboring neuron circuits. Delayed binary outputs of neuron circuits in a neighborhood are directly connected to inputs of a current active neuron circuit. Next state of a network is computed form a current state at some neuron circuits in any time interval. Models of two types of neuron circuits and networks are presented and simulated to confirm an ability of proposed methods. Also, physical layout designs of coding chips have been done to show their possibility of VLSI realizations.

This paper proposes two algorithms for defining a routing domain in multiclass-of-service networks. One an off-line-based method, whose objective is to optimize dynamic routing performance by using precise knowledge on the traffic levels. The algorithm of the proposed method takes into account the random nature of the traffic flow, which is not considered in the network flow approach. The proposed method inherits the conceptual simplicity of the network flow approach and remains applicable to large and complex networks. In simulation experiments, the proposed off-line-based method performs better than the method based on the network flow approach, but has a similar the computation time requirement. The other method proposed here is an on-line-based method for application to B-ISDNs, where precise traffic data is not expected to be available. In this method, the routing domain is defined adaptively according to the network performance (call-blocking probability) measured in real-time. In simulation experiments, the performance of this method is comparable to that of the off-line-based method--especially when highly efficient dynamic routing is used. This paper also derives and describes methods for approximating the implied costs for multiclass-of-service networks. The approximations are very useful not only for off-line-based routing domain definition (RDD) methods but also for other kinds of network controls or optimal network dimensioning based on the concept of revenue optimization.

Efficiency of network resource can be improved by statistical multiplexing in ATM networks. If cell traffic characteristics of each connection could be obtained beforehand, we could admit maximum connections while satisfying the QoS (Quality of Service) objective. Since such traffic characteristics as an average rate and a mean burst length are difficult to anticipate, only peak rate will be used for CAC (connection admission control). The peak rate assignment strategy will, however, lead to inefficient network utilization for bursty traffic. This paper proposes an adaptive admission control using real-time traffic measurements to overcome the above problem. This scheme is based on two-state cell stream model composed of overload and underload states. The two-state model simplifies the measuring algorithm, which is suited for online processing. Performance of this scheme is investigated through simulation study for multiplexing of on-off sources with a wide spectrum of traffic characteristics. Since the proposed control scheme exploits measurements of cell streams, it achieves nearly optimum bandwidth efficiency.

This paper discusses two approaches to statistical multiplexing: rate envelope multiplexing, allowing resource sharing with small delays for low peak rate connections, and rate sharing, based on the use of large multiplexer buffers to ensure high link utilization for high speed data traffic. We argue that the weighted fair queueing scheduling algorithm provides an efficient means for combining both kinds of multiplexing in the B-ISDN. A feasible implementation known as Virtual Spacing is outlined. We illustrate the flexibility of the proposed scheme by showing how different service categories could be provided.

Calls using different media which require different transfer quality will arrive at ATM networks. Therefore it is important to develop a method for allocating network resources efficiently to individual calls by judging admission of calls. Various call admission control schemes have been already proposed, and these schemes assume that users specify values of traffic descriptors when they originate calls. However, it is sometimes difficult for users to specify these values accurately. This paper proposes a new ATM call admission control scheme based on cell transfer state monitoring which does not require that users specify values of traffic descriptors in detail when they originate calls. In this proposed scheme, the acceptance or rejection of calls is judged by comparing the monitored cell transfer state value with a threshold prepared in advance. This threshold must be adjusted according to changes in the characteristics of traffic applied to ATM networks. This is one of the most serious problems in the control scheme based on the monitoring of cell transfer state. Herein, this paper proposes neural network application to the control scheme in order to resolve this problem and improve performance. In principle, the threshold can be adjusted automatically by the self-learning function of the neural network, and the control can be maintained appropriately even if the characteristics of traffic applied to ATM networks change drastically. In this paper, the effectiveness of the application of a neural network is clarified by showing the configuration of this proposed control scheme with the neural network, a method for deciding various parameter values needed to implement this control scheme, and finally the results of a performance evaluation of the control scheme. Inputs required by the neural network are also discussed.

We propose a new concept of network dimensioning, which is based not only on the grade of service but also on profit. In traditional network dimensioning methodology, the number of circuits on links is designed under a cost-minimization concept with grade of service constraints. Recently, telecommunication markets have become very large and competitive; therefore, we believe that a profit viewpoint is now essential. However, it is difficult to calculate profit in almost all the dimensioning methods currently used, because they mainly employ peak-hour traffic data, while profit depends on all the hourly traffic data which contain both peak and off-peak data. In this paper, we propose using all the hourly traffic data in network dimensioning. From these data and telephone charges for each hour, revenues will be estimated. On the other hand, facility costs will be estimated from the number of circuits. Finally, we can estimate profit from the difference between revenues and facility costs. Focusing on both quality and profits in network dimensioning leads to more advanced quality management and quality control in telecommunications networks than with traditional methodology. This paper outlines a dimensioning method based on profit, and describes its properties, some applications of it, and summarizes further studies.

In this paper, we propose a new framework for global traffic control in ATM networks which aims to maximize resource utilization and to guarantee the reliable congestion control. To do this, we first propose Global Traffic Control (GTC) mechanism which is based on harmonious cooperation of each traffic control function. GTC measures real bandwidth utilization to compensate inaccuracy of the declared mean cell rate and it also monitors cell losses to manage input traffic load when a network approaches congestion state. We also propose new adaptive connection admission control (CAC) algorithms which calculate cell loss performance of related function blocks in a switch node using only a declared peak cell rate and an estimated mean cell rate. We measure only the mean cell rate of the aggregate cell stream in a link to estimate the mean cell rate of each virtual channel connection. We adopt a peak cell rate spacer at the User Network Interface (UNI) to compensate a cell delay variation (CDV). We will also present an approximation technique to estimate a queue length distribution of a general queue. As this technique requires negligible calculation time, it can meet the stringent requirement on the connection set-up time.

A uniquely-structured Usage Parameter Control (UPC) method named Virtual-shaping is proposed which considers cell arrival time jitter between user and UPC point. The method uses a modified Dangerous Bridge UPC circuit (Sliding window type) and virtually (logically) shapes cell traffic using cell arrival time compensation to offset cell delay variation (CDV). In addition, the proposed method is based on a cell-buffer-less structure and can be realized with reasonable hardware. The method yields precise and accurate monitoring. Computer simulations show that the method offers higher network utilization than the conventional Leaky Bucket based UPC method. The proposed method will make it possible to create more effective B-ISDNs, and more cost-effective broadband VBR services.

Over the last decade, the Internet has been extremely successful by distinguishing between overlaying applications and underlying networking technologies. This approach allows rapid and independent improvement in both networking and application technologies. The internetworking layer that divides applications and the network enables the Internet to function as a general and evolving infrastructures for data communications. The current Internet architecture offers only best-effort data delivery. However, recent emerging computer and networking technologies, demand the Internet guaranteed performance. In particular, audio and video applications have more rigid delay requirement than those applications which the current Internet supports. To offer guaranteed services in addition to best-effort services, both a new service model and a new architecture are necessary in the Internet architecture. The paper surveys researches and experiments conducted in the Internet community to accommodate a wide variety of qualities of services.

The Manchester Dataflow Machine (MDFM) works with tasks of size equal to one single instruction. This fine granularity aims at exploring all parallelism at the instruction level. However, this project decision increases the instruction communication cost, which ends up to jam the interconnection network and reduces the system performance. One way to skirt this problem is to adopt variable size tasks instead of working with such small task size. In this paper, in order to study whether or not the usage of such variable size tasks in the MDFM architecture contributes to the improvement of the performance, some simulations by toy programs take place. In the simulation, variable size tasks are realized by packing the sequential instruction stretches into one task. To manage this packing, the Sequential Block (SB) technique is developed. The simulation of those packed and unpacked programs give an outline of advantages and disadvantages of working with variable size tasks, and how the SB technique should be implemented in the system.

In improving channel utilization in microcellular systems, adaptive channel allocation using distributed control has been reported to be effective. We describe an analytical approximation algorithm for channel dimensioning of distributed adaptive channel allocation. We compare our analytical results with simulation results and show the characteristics of permissible load as a function of the number of base station channels based on our method. Finally we illustrate traffic design and administration based on our algorithm.

We model a road network as a directed graph G(V,E) with a source s and a sink t, where each edge e has a positive length l(e) and each vertex v has a distribution function αv with respect to the traffic entering and leaving v. This paper proposes a polynomial time algorithm for evaluating the importance of each edge e E whicn is defined to be the traffic f(e) passing through e in order to assign the required traffic Fst(0) from s to t along only shortest s-t paths in accordance with the distribution function αv at each vertex v.

We propose a method for configuring LSI manufacturing lines so that they can not only be used to manufacture low-cost LSIs in bulk quantities but also can be used to manufacture small lots with ultra-short TAT. This is achieved by adding a relatively small amount of single-wafer processing equipment to a existing conventional processing line, and therefore involves minimum investment.

This paper presents an alternative traffic model for an ATM multiplexer providing video, voice, image, and data services. The traffic model classifies the input traffic into two types: real-time and non-real-time. The input process for realtime traffic is periodic and correlated, while that for non-realtime traffic is batch Poisson and independent. This multiplexer is assumed to be a priority queueing system with synchronous servers operating on time-frame basis and with separate finite buffers for each type of traffic. State probabilities and performance measures are successfully obtained using a Markov analysis technique and an application of the residue theorem in complex variable. The results can be applied in the design of an ATM multiplexer.

This letter proposes a VP-shaper for ATM networks that controls the VC-level cell clumping. The new shaper is compared with a conventional shaper and is found to significantly increase CAC (Call Admission Control) efficiency and achieve high VP utilization gain. Hardware implementation based on a shared buffer and chained lists is presented and its feasibility is shown.