While active researches have been continuously made on the ATM switch architectures and the QoS service guarantees, most of them have been treated independently in the past. In this paper, we first explain the architectural requirement on the ATM switches to implement the mechanism of QoS guarantees in the context of ATM congestion control. Then we discuss how a vital link between two should be built, and remaining problems are pointed out.

When a set of objects is shared among several applications, multiple implementations for the set are required in order to suit each application as much as possible. Furthermore, if a set of objects could have multiple implementations, the following issues arise: (1) how to select the best implementation when processing queries on the set, and (2) how to propagate updates on an implementation of the set to the others. In this paper we propose a mechanism of multiple implementations for a set, and also give a solution for the latter issue. In the proposal a set can be of multiple types, and each of the types corresponds to an implementation already contained within the set. Update propagation can be achieved by a rewriting technique at compilation time. We also present a performance study in which the feasibility and effectiveness of our proposal were examined.

In this paper we newly define a generalized edge-ranking of a graph G as follows: for a positive integer c, a c-edge-ranking of G is a labeling (ranking) of the edges of G with integers such that, for any label i, deletion of all edges with labels >i leaves connected components, each having at most c edges with label i. The problem of finding an optimal c-edge-ranking of G, that is, a c-edge-ranking using the minimum number of ranks, has applications in scheduling the manufacture of complex multi-part products; it is equivalent to finding a c-edge-separator tree of G having the minimum height. We present an algorithm to find an optimal c-edge-ranking of a given tree T for any positive integer c in time O(n2log Δ), where n is the number of vertices in T and Δ is the maximum vertex-degree of T. Our algorithm is faster than the best algorithm known for the case c=1.

This paper presents analysis of a congestion control scheme in which a multiplexer notifies upstream traffic sources when its buffer level crosses a preset threshold. Upon notification, the traffic streams are reshaped to a form less likely to cause overflow through rate or burstiness restrictions, or a combination of the two. For the analysis, the traffic is modeled by two Markov Modulated Rate Processes (MMRP's), one for above and one for below the threshold, and an iterative fluid approximation technique is used to determine the buffer occupancy distribution. Simulation results verify the accuracy of the approach, and the analysis is used to study the effect of varying the threshold and shaping function.

In this paper, a new traffic shaping mechanism for ATM networks, the RC Shaper, is proposed and studied. The objective of a shaping mechanism is, to smoothen the traffic by reducing the burstiness. Using the analogies between the RC low pass filter and the proposed shaper, performance measures such as burstiness reduction factor and cell mean waiting time of the shaper can be obtained. In this current exploratory stage of study, the shaper is used to shape the well-known Markov Modulated Poisson Process. Behaviour of the shaper is established through examining the burstiness reduction achieved by the device. Another performance measure obtained for the shaper is the cell mean waiting time. Difference in shaping each connection individually and a group of connections collectively is also observed. From our results, it seems better to shape VCs within a virtual path `aggregately' instead of shaping each of these VCs individually. Comparison with fixed-rate shaper is reported and difference in multiplexing shaped and unshaped cell streams is also observed.

A new adaptive rate control with congestion prediction is developed that is highly robust against long propagation delays. It minimizes the network performance degradation caused by the delay based on prediction by extrapolating past data and correction using new notification. The simulation results show that our proposed control maintains high throughput and a smaller buffer even in long propagation delay networks, like ATM-WAN.

We investigate performance of TCP protocol over ATM networks by using a simulation technique. As the ATM layer, we consider (1) rate-based control of the ABR service class and (2) an EPD (Early Packet Discard) technique applied to the UBR service class and (3) and EPD with per-VC accounting for fairness enhancement applied to the UBR service class. In comparison, we adopt a multi-hop network model where the multiple ATM switches are interconnected. In such a network, unfairness among connections is a possible cause of the problem due to differences of the number of hops and/or the round trip times among connections. Simulation results show that the rate-based control method of ABR achieves highest throughput and best fairness in most circumstances. However, the performance of TCP over ABR is degraded once the cell loss takes place due to the inappropriate control parameter setting. To avoid this performance degradation, we investigate the appropriate parameter set suitable to TCP on ABR service. As a result, parameter tuning can improve the performance of TCP over ABR, but limited. We therefore consider TCP over ABR with EPD enhancement where the EPD technique is incorporated into ABR. We last consider the multimedia network environment, where the VBR traffic exists in the network in addition to the ABR/UBR traffic. By this, we investigate an applicability of the above observations to a more generic model. Through simulation experiments, we find that the similar results can be obtained, but it is also shown that parameters of the rate-based congestion control must be chosen carefully by taking into account the existence of VBR traffic. For this, we discuss the method to determine the appropriate control parameters.

A novel approach to the cache coherent Multistage Interconnection Network (MIN) called the MINC (MIN with Cache control mechanism) is proposed. In the MINC, the directory is located only on the shared memory using the Reduced Hierarchical Bit-map Directory schemes (RHBDs). In the RHBD, the bit-map directory is reduced and carried in the packet header for quick multicasting without accessing the directory in each hierarchy. In order to reduce unnecessary packets caused by compacting the bit map in the RHBD, a small cache called the pruning cache is introduced in the switching element. The simulation reveals the pruning cache works most effectively when it is provided in every switching element of the first stage, and it reduces the congestion more than 50% with only 4 entries. The MINC cache control chip with 16 inputs/outputs is implemented on the LPGA (Laser Programmable Gate Array), and works with a 66 MHz clock.

This paper compares three cell transfer quality control schemes, namely HPS, DAS and ORS, which integrate a preventive congestion control and a reactive congestion control in ATM switch. Simulation results showed that ORS achieves the largest network utilization, and HPS provides enough large throughput compared with DAS only when many VBR connections are multiplexed.

A leaky-bucket-with-gate algorithm is proposed to control connection-setup congestion in telecommunication networks providing multimedia services, in place of the call-gapping algorithm used in telephone networks. Multimedia services may use more than one connection simultaneously, while standard telephone services use only one connection at a time. A set of connections used to construct a multimedia service is called a correlated connection group, and the setup requests of such a group form correlated request group. A correlated request group is assumed to be accepted into the network only when all the connection-setup requests for the group are accepted. In this paper, the proposed leaky-bucket-with-gate algorithm, a pure leaky-bucket algorithm, and a call-gapping algorithm are evaluated by simulating traffic with a mix of correlated and uncorrelated connection-setup requests, which models setup requests for video conferencing and telephone services. The simulation results show that the proposed algorithm accepts correlated request groups more efficiently than the pure leaky-bucket and call-gapping algorithms under the simulated traffic conditions, except when the interarrival time in a correlated request group is longer than the acceptance interval. We also present queueing analysis for determining the control parameters in the proposed algorithm. Implementation of this algorithm will facilitate the handling of both setup request traffic for correlated connection groups and for uncorrelated connections in multimedia networks.

In this paper, algorithms for resource allocation in an ATM node that serves heterogeneous traffic sources subject to varying Quality of Service (QoS) requirements are proposed. The node can be either a switch port or a multiplexer. Each connection is first individually treated as logical queue. Quick and efficient algorithms allocating service rate and buffer space to each connection based on traffic characteristics and QoS requirement are developed. In order to improve link and buffer utilization, the aggregate traffic is next replaced by an appropriately parameterized new traffic source that still preserves the key characteristics of the aggregate traffic. The most stringest QoS requirement among all connections is selected to be the QoS target of the new traffic source to assure that QoS of each individual connection is satisfied. Resource allocation for the aggregate traffic is determined based on the traffic parameters and QoS target of the new source. Each individually determined service rate and buffer space can be used in cell transmission scheduling and selective cell discarding. In other words, resource allocation together with two related side problems: cell transmission and cell discarding, are treated in this paper in an integrated and efficient manner. The resource allocation algorithms proposed in this paper can also be used to support Call Admission Control (CAC) in ATM networks.

Narrow-band ISDN services may experience nonstationary traffic conditions. Therefore, switch design should take account of these conditions. We propose new performance measures for switching systems and describe a traffic model, which is a mixture of stationary Poissonian traffic and momentarily focused traffic. On the basis of this model, performance measures are determined so as to satisfy grade of service requirements that are in effect during some short interval after the momentarily focused traffic enters the system. We also propose an overload control scheme that uses these new performance measures. Finally, we show practical and numerical examples for the performance measures and overload control scheme.

This paper proposes a time-dependent gateway earth station (GES) assignment method for a user terminal in non-geostationary orbiting satellite systems. Time-dependent nature of the GES service area is first discussed for an example intermediate circular orbit system. Then, the time-dependent GES assignment method is proposed. Finally, the advantage of the proposed method is shown by several calculation results.

One of the functions that should be provided in ATM LANs is multicast communication. For multicast communication on ATM LANs, the architecture of switch fabric and protocols for signaling have been studied. However, when data communication using a multicast connection such as LAN emulation service is provided, ABR service on a multicast connection (Multicast ABR) is also required. ABR service has been actively discussed in the ATM forum. Unfortunately, the study on flow control mechanism for Multicast ABR is not enough. This paper discusses the suitable flow control mechanism for Multicast ABR and shows its performance.

A subclass of context-free languages, called pure context-free languages, which is generated by context-free grammar with only one type of symbol (i.e., terminals and nonterminals are not distinguished), is introduced and the problem of identifying from positive data a restricted class of monogenic pure context-free languages (mono-PCF languages, in short) is investigated. The class of mono-PCF languages is incomparable to the class of regular languages. In this paper we show that the class of mono-PCF languages is polynomial time identifiable from positive data. That is, there is an algorithm that, given a mono-PCF language L, identifies from positive data, a grammar generating L, called a monogenic pure context-free grammar (mono-PCF grammar, in short) satisfying the property that the time for updating a conjecture is bounded by O(N3), where N is the sum of lengths of all positive data provided. This is in contrast with another result in this paper that the class of PCF languages is not identifiable in the limit from positive data.

This paper addresses the problem of estimating 3-D motion of a rigid object from a sequence of monocular 2-D images. The surface of object is assumed to be modeled with several patches, each of which is expressed by an implicit equation. The proposed method estimates the pose (i.e., the location and orientation) of object that corresponds to each image in the sequence: The sequence of the estimated poses gives the motion of the object. The estimation is done by solving a system of equations, each of which is typically an algebraic equation of low degree, that is derived from the expressions of the surface patches and image contours data: so the method does not require establishing the correspondence between successive two frames in the image sequence or computing optic flow. Allowing several-patch models for objects enables the proposed approach to deal with a great variety of objects. The paper includes a numerical example, where our aproach has been applied to a polyhedral object modeled with several patches.

Several two-dimensional largest common subpatterns (LCP) between pictures are defined and their computing methods are proposed. The time and space complexities of the computing methods are O(IJMN) to obtain the size of LCPs between a picture with IJ pixels and a picture with MN pixels. These LCPs can be used as similarity measures between pictures and can be applied to texture recognition and classification.

Video services such as video-on-demand are expected to be a motivation for deploying multimedia services in residential areas. These services should increase customer demand for video channels as customer demands become more sophisticated and diverse in the future. Therefore, it is important to determine how network configurations (i.e. network transition scenarios) should evolve in response to changes in access network demand. This paper proposes economical deployment of access networks based on transition scenarios. We conclude that transition scenarios offer more economical deployment than single-network configurations. Two transition scenarios, from passive double-star to fiber single-star, and from hybrid fiber-coax to fiber single-star, are evaluated as examples. These transition scenarios are economical even when customer demand changes. The transition starting time affects the present worth of annual charges (PWAC) of access networks more than the transition period does.

String grammars (languages) have been extensively studied from 60's. On the other hand, the transformational grammar, proposed by N. Chomsky, contains the transformation from the set of derivation trees of context-free language to the surface set. And the grammar regarded a tree as an input sentence to some transducer. After that from latter half of 60's, the studies of acceptors, transducers, and so on, whose input is a tree, have been studied extensively. And recently some pushdown tree automata were introduced, and their fundamental properties and some other various properties were investigated [11]-[17]. Furthermore, a top-down pushdown tree transducer (t-PDTT for short), which is an extension of a top-down pushdown automaton (t-PDTA for short), was introduced and its fundamental properties were investigated [19]. In this paper, we define the various subclasses of context-free tree grammar (CFTG for short) by the combination of variables contained in the rules. Furthermore, we consider a monadic case of CFTG which is a special case of CFTG. Based on these definitions, we classify the subclasses of CFTG, and we investigate some inclusion properties of subclasses of CFTL (where CFTL indicates the class of context-free tree languages).

A hierarchical relaxation method is presented for detecting local features in moving images. The relaxation processes are performed on the temporal-spatial pyramid, which is a multi-resolution data structure for the moving images. The accurate and high speed edge detection can be obtained by using infomation in the neighboring frames as well as the processed results in the higher layers of the pyramid.