Guaranteed services in the computer network often require a single reserved path, which easily suffers from single link failures. This paper introduces a backup path computation algorithm, TP, which is intended to compute unreserved backup paths to overcome a single link failure in the network. Simulations are performed to compare TP to other known unreserved backup path computation algorithms. In addition, tests are also done to determine how unreserved backup paths should be used to obtain the best results. The results show that TP backup paths have comparable performance to those of known methods, and that unreserved backup paths as a solution can provide good recovery from a link failure. For the best performance, unreserved backup paths should be paired with strict recovery in light network loads, and they should be paired with relaxed recovery in heavy network loads.

Guaranteed, high-quality service in a computer network often requires a single reserved path. Such a path can easily suffer from single point failures. Thus, to continuously provide the same high-quality service guarantee both before and after a link failure, each flow requires both a reserved primary path and a backup path. One solution category involves eliminating resource reservation on the backup paths, and instead, computes a posteriori good unreserved backup paths to provide strict high quality service in the event of a link failure. This paper provides a solution (AvoidPBO-S) in this category that uses good unreserved backup paths to offer the same strict service guarantee despite a link failure. Initial test results show that there is only a very small likelihood that an unreserved AvoidPBO-S backup path fails to provide the kind of service guarantee as the primary path, and that AvoidPBO-S backup paths perform well compared to other methods.

Guaranteed, high-quality service in the computer network often requires a single reserved path. However, a single path can easily suffer from single point failures. This paper provides a solution to handle flows when their reserved primary paths fail. The solution pairs a reserved primary path with an unreserved backup path. When a failure occurs and a primary path fails, the initial service guarantee is relaxed slightly, and the flow with the failed primary path is re-routed on the least congested alternate path. This approach allows all flows to continue despite a failure in the network. In addition, even though the service quality is relaxed to accommodate flows with failed primary paths, by carefully planning the least congested alternate paths as backups, very high levels of service quality can still be retained after failure.

Providing high quality-of-service using a single reserved path easily suffers from single link failures. This paper provides a scalable solution, TPmax-R, to tolerate single link failures. TPmax-R is based on an existing method, AvoidPBO-R. TPmax-R reduces the communication cost incurred by AvoidPBO-R to a scalable level. Instead of broadcasting routing information of all the flows in the network, TPmax-R source nodes communicate only link-based information to each other. TPmax-R pairs a reserved primary path with a well chosen unreserved backup path. Conflicts that might occur in the event of failure are predicted and backup paths are chosen to avoid these conflicts. By carefully planning the backup paths, the resulting service quality provided to the flows after re-routing is expected to be very close to that before the failure. Initial simulations show that TPmax-R provides competitive service quality after the failure while using less overhead.

VoIP applications have grown rapidly and continue to enjoy exponential growth due to largely reduced cost and wider range of advanced services, as compared to traditional telephone network., however, they face many technical challenges. One of major challenges is the provision of quality of service. Presently, VoIP quality is not as good as achieved in traditional telephone networks due to the data loss and delay in IP networks. In this paper, a perceptual quality-driven scheduling scheme is proposed. Simulation experiments results show that it significantly increases the quality of voice traffic transmission over IP network yielding QoS satisfaction both for VoIP users and service providers

Current network techniques provide quality of service (QoS) from the viewpoint of the network. However, these schemes often do not result in satisfactory performance for application users. The paper proposes two new proactive resource allocation schemes for satisfying the perceived QoS requirements of video users. The schemes are proactive in the sense that they schedule queued packets to exit the router according to information related to future data, rather than just the information for currently arriving data. Unexpected data loss during a future time interval is avoided, thus increasing the number of video users with QoS satisfaction The second scheme modifies the first one by adding a stream-aware packet discard algorithm to correct further any QoS requirement violation from the users' perspective. It is shown that the combined scheme yields a higher QoS-satisfied user ratio but it is computationally more expensive, compared to the first scheme alone.

Shortest path first (SPF) routing protocols, such as OSPF and IS-IS are currently the dominant intra-domain IP routing protocols and are widely used in the ISP backbones. Although the traffic on the Internet is highly dynamic, OSPF and IS-IS are not adaptive to the changing traffic, because the shortest path generated by these protocols are based on the link weights, which are fixed and usually can not be changed during network operation. This paper investigates a way of changing the weights in OSPF/IS-IS adaptively according to the changing traffic load on the links. The feedback effect and the stability issue of adaptive routing are analyzed from a control system point of view. The paper shows why minimal-delay adaptive routing, such as the routings in the early ARPANET, is not stable, and proposes some techniques to make our load-sensitive adaptive routing (LSAR) stable. Finally, the performance of LSAR is evaluated by simulation. The result shows that LSAR can significantly improve the QoS of the network by increasing network throughput and reducing packet drop ratio.

Buffer management plays an important role for enhancing quality of service (QoS) for video streaming over IP networks. However, most existing buffer management techniques have been developed according to the network's point of view; consequently, QoS requirements from users' perspectives are not well satisfied. The paper proposes a novel buffer management scheme based on user's expectations. Simulation results show the advantages of the scheme in terms of video quality, service fairness and network efficiency.

Packet loss due to network congestion causes degradation in the quality of networked video transmitted over IP networks. Buffer management and packet scheduling are two key router-based quality of service (QoS) control techniques. Existing buffer management mechanisms mainly focus on preventing network congestion in order to reduce packet loss. However, a low packet loss ratio by itself does not necessarily translate to high video quality, so these methods, by themselves, do not ensure user-expected video quality. We proposed an alternative buffer management approach, called FDDT, which focuses on improving user-expected video quality, rather than just aiming at reducing packet loss (Ito, M.R. and Bai, Y., 8th IEEE Int. Conf. on Commun. Systems, 2002). Most packet scheduling mechanisms are designed to provide delay guarantees. We have shown that packet scheduling is a viable and attractive option to help provide further loss guarantees (Bai and Ito, 10th Int. Conf. on Telecom., 2003). The packet scheduling scheme is called MPAPS. This paper compares the performance of FDDT, MPAPS, and a combination of FDDT and MPAPS based on video quality, service fairness and network efficiency.

Traditional buffer management techniques, which are based on reducing packet loss, fail to ensure user expected video quality. In www3.informatic.uni-wuerzburg.de, we proposed an alternative buffer management approach, called FDDT, which focuses on controlling packet loss distribution. Experiments have shown that FDDT significantly improves both video quality and network efficiency. As an extension of FDDT, in this paper, we address fairness with respect to different video streams and introduce a new buffer management scheme called FDDT+. Performance evaluation of the FDDT+ scheme is presented.

Packet loss due to network congestion causes degradation in the quality of networked video transmitted over IP networks. Previous buffer management methods have been designed to prevent network congestion in order to reduce packet loss. However, a low packet loss ratio by itself does not necessarily translate to high video quality, so these methods do not ensure user-expected video quality; and hence, there is a need for alternative approaches to achieve user-expected video quality. This paper proposes a new buffer management scheme that focuses on achieving user-expected video quality, rather than just aiming at reducing packet loss. The proposed scheme allows the videos that share an output buffer to be guaranteed an appropriate share of the buffer when the buffer faces overflow, yet allows a complete sharing of the buffer space when it is not overflowing. The scheme also provides a mechanism that gives parts of a video lower loss than other parts. Simulation experiments show that the Quality of Service requirements of multiple videos and effective utilization of network resources can both be achieved.

Packet scheduling is typically designed to support the delay requirements of video communication. In this paper, a new innovative use of packet scheduling to provide loss guarantees is proposed. A packet scheduling scheme at a router that assures that intra and interstream loss requests for video transportation are met was developed and evaluated using real video data. The results show that the proposed scheme can significantly improve the quality of each video. It can also provide different classes of videos with different levels of loss guarantees, while maintaining service fairness among all competing videos.

This paper proposed a receiver-driven layered multicast scheme using active networks (RLM-AN). The multicast tree is regarded as a set of virtual links. TCP-friendly congestion control and FEC-based error control are performed on each virtual link. In order to solve the loss path multiplicity problem, the intermediate active nodes also perform error recovery. By introducing congestion control and error mechanisms in active nodes inside the network, we obtain smoother and more TCP-friendly throughputs and quicker response to congestion inside the network and much lower packet loss rate.

This paper presents a new instruction cache scheme: the TAC (Thrashing-Avoidance Cache). A 2-way TAC scheme employs 2-way banks and XOR mapping functions. The main function of the TAC is to place a group of instructions separated by a call instruction into a bank according to the Bank Selection Logic (BSL) and Bank-originated Pseudo-LRU replacement policies (BoPLRU). After the BSL initially selects a bank on an instruction cache miss, the BoPLRU will determine the final bank for updating a cache line as a correction mechanism. These two mechanisms can guarantee that recent groups of instructions exist in each bank safely. We have developed a simulation program, TACSim, by using Shade and Spixtools, provided by SUN Microsystems, on an ultra SPARC/10 processor. Our experimental results show that 2-way TAC schemes reduce conflict misses more effectively than 2-way skewed-associative caches in both C (17% improvement) and C++ (30% improvement) programs on L1 caches.

The architecture of a hierarchical video-on-demand (VOD) system consists of continuous media servers (CMS) which basically stand as a cache between the archive servers (AS) and the clients. The adaptive viewers' bias-based (AVBB) cache management algorithm is higher-performing than any existing ones because it considers and adapts to the video characteristics which viewers generally have a bias towards at different times and places. However, in AVBB, a cached item is an entire video. In this paper, we briefly look at both the AVBB and integrated bandwidth and space-constrained (IBSC) caching algorithms. We then incorporate the interval caching concept from IBSC into AVBB by reformulating the AVBB cache management algorithm not in terms of the videos themselves but in terms of video intervals. We then compare the performance of this modified algorithm with that of existing algorithms.

The architecture of the Berkeley distributed hierarchical video-on-demand (VOD) system consists of continuous media servers (CMS) basically standing as a cache between the archive servers (AS) and the clients. Many replacement policies used in cache management, we notice, is restricted in that they consider only one (or few) parameters to decide which video to kick out of the cache, like the frequency of requests, or the size of objects. We look at a new cache management algorithm which is higher-performing since it considers, besides the time of requests and the past request history of a video, the video characteristics which viewers, generally, have a bias for. However, the viewer's bias and the objects' characteristics vary with time and location. We enhanced the cache management technique by making it adaptive to the different characteristics viewers and videos have at different times and places.

Synchronization constitutes an important research field in multimedia communication. The synchronization problem has been addressed in the literature in two distinct levels: specification and design. On the specification level, several formal models have been proposed, which are mostly variations of the Petri net model. Although some models are deemed to be better than others in some aspects, there has not been a comprehensive comparison of these specification models. This paper provides a critical review of the existing Petri net specification approaches for specifying synchronization constraints, including object composition, extended object composition, dynamic timed and time stream Petri net models, and applies them to the specification of an interesting, relatively straightforward synchronization example for a qualitative and quantitative evaluation of their strengths and weaknesses.

This paper presents highly parallel VLSI structures for linear convolution. Our methodology implements Toom's algorithm and is based on mapping a modified version of the tensor product factorization proposed by Granata et al. (1991). The resulting networks have very simple structure, highly regular topology, and use simple bit-serial devices. Additionally, the proposed networks have very small depth and contain only a single stage of multipliers, while all other stages contain adders only.

Petri nets have proven themselves to be an excellent modeling and analysis tool for discrete event or asynchronous systems. On the other hand, linear system analysis uses differential and difference equations to represent time dependent or synchronous systems. A new extension of Petri nets, called Global Petri Net (GPN) provides a means for combining these two powerful tools. Here, we define this tool and show how it can be used to model and simulate hybrid systems consisting of both time and event driven parts. An example of a distributed control system is used to illustrate the GPN modeling and simulation capabilities.

This paper presents a methodology for designing folded VLSI networks for implementing tensor-product forms. Using tensor-products leads to very efficient expressions for a large number of computations in digital signal processing and matrix arithmetic. The resulting networks can trade-off total time delay with I/O bandwidth and chip area. The main goal is to parametrize the VLSI architecture so that it can be implemented under various packaging constraints including the available number of I/O pins, available chip-area, and certain restrictions on maximum wire length. Our methods result in folded VLSI networks with optimal AT/sup 2/ trade-off for digital filtering and multidimensional transforms, where A is the total area of the VLSI circuit (or chip) and T is its total time delay.>

Several compile time transformations of loops with simple dependencies have been developed in order to expose possible parallelism in these loops. However, once an irregular data dependence is detected, no attempt is usually made to extract any parallel thread from the loop. In this paper, we present the parallel region execution, a new compile time approach for improving the execution of loops with complex dependencies. It consists of dividing the iteration space of the loop into parallel regions and serial regions, where all the iterations in the parallel regions can be fully executed in parallel. Our parallel region execution technique has been tested on the MasPar machine for various examples and generally resulted in a large speedup.

Traditional dependence analysis techniques usually attempt to recognize the existence of dependencies between iterations of a loop and, in some cases, characterize these dependencies by finding direction vectors or distance vectors. A more general form of data dependence called hyperplane dependence is introduced. It is a dependence whose source and destination are subspaces of the iteration space. This dependence form can be useful mainly for expressing dependencies across loop-nests, and consequently better understand the interaction between the loops. In order to be able to express across loop dependencies and analyze all loops in the code simultaneously, a global iteration space for all loops in the code is formed. Hyperplane dependence analysis is used to improve automatic generation of communication statements across loops and index alignment for n-dimensional grid target machines.>

Partitioning the iteration space can significantly affect the execution time of a loop. The authors propose an improvement over previous partitioning methods for single loops with uniform data dependencies. For distributed memory systems, partitioning each loop separately does not guarantee an efficient execution of the code because of across loop data dependence. As a result, a global iteration space is formed so that all loops in a program are considered when partitioning the global space. In addition, a new and general form of data dependence called hyperplane dependence is introduced and used in the partitioning. It is a dependence whose source and destination are subspaces (of any dimension) of the global iteration space.

To meet the increased communication processing requirements of high-speed networks, a multiprocessing network interface is considered for processing multiple layers of a communication protocol stack. In particular, the processing of the open systems interconnection (OSI) layers 2 to 6 on the network interface are considered. OSI processing is computationally expensive because of the inclusion of the transfer syntax conversion at the presentation layer. The approach taken is to process different packets in parallel. The results obtained from simulations indicate that the approach has promise for OSI processing at higher rates.>

An extension to the convergence theorem for single neurons learning under the AR-Palgorithm is proved. The extension shows that if the conditions of the single-neuron theorem are satisfied and if the environment satisfies one of two sufficient conditions, the weights in an arbitrarily large one-layer network will converge with probability one to values with which the network correctly classifies the training input set. One condition requires that for all output vectors, the probability of reinforcement being one (success) has one of two values: the output vectors having at leastlkcorrect elements have the higher probability, whereas the output vectors having less thanlkcorrect elements have the lower probability. The alternative condition requires that the reinforcement have a higher probability of being one for output vectors having a higher number of correct elements. The extension and its proof are significant because they further the understanding of the factors affecting the convergence of multilayer networks under reinforcement learning

In this paper, we present a re-circulating systolic sorting array and two sorting algorithms. The correctness of these algorithms is proved and general operational constraints are examined. These algorithms are amenable to VLSI implementation owing to the following attributes: (1) the simple control patterns of the algorithms, (2) the regular, repetitive and near-neigbour type of interconnection among the comparators, and (3) the systolic data movement. The sorting array is also well-suited for fabrication on shift-register type of storage and logic devices–such as magnetic bubble memories (MBMs) and charge-coupled devices (CCDs)–because of its closed-loop structure. The number of comparators and sorting time are both in O(N) where N is the number of items to be sorted. A hardware termination methods is incorporated into the control unit of the sorter, so that the sorting process can be terminated within a bounded time after the input list is in the desired order.

An investigation into the feasibility of applying pattern recognition concepts to the classification of metallic objects by their electromagnetic induction responses was performed. The effect on the response of a limited set of steel spheroids due to various factors such as object shape, size, and orientation was examined and a pattern recognition scheme based on these results was proposed. Implementation of the scheme involved the development of a novel extension to the nearest mean vector type of classifier in which the concept of the class mean as a point in feature space was generalized to be a curve. The resultant pattern recognition scheme was tested on a representative test set which included 815 responses, corresponding to 104 variations in object and orientation. A success rate of greater than 96 percent was achieved. It is noted that the classifier extension developed provides a viable approach to classification of responses that very continuously with respect to a single parameter.

This paper describes a novel loop-structured switching network (LSSN) intended for highly parallel processing architectures. With L loops, it can connect up to N = L* log2 L pairs of transmitting and receiving devices using only N/2 two-by-two switching elements; thus, it is very cost-effective in terms of its component count. Its topology resembles that of the indirect binary n-cube network, but a much higher device-to-switch ratio is achieved because all the links between the switches could be used as both transmitting and receiving stations. It has the advantage of incremental extensibility, and-it could avoid store-and-forward deadlocks (SFD) which prevail in other recirculating packet-switched networks. Our simulation studies show that the average throughput rate and delay of LSSN are close to that of other designs despite its relatively low component count.

A metaprogramming system is a programming facility (subprogramming system or language) whose basic data objects include the programs and program fragments of some particular programming language, known as the target language of the system.Such systems are designed to facilitate the writing of metaprograms, that is, programs about programs.Metaprograms take as input programs and fragments in the target language, perform various operations on them, and possibly generate modified target-language programs as output.A grammar-based approach to the specification of the syntactic-manipulation component of a metaprogramming system is described.The method derives the specifications for a set of programmanipulating subprograms from an augmented BNF grammar for the target language.The method is applicable to any programming language and is illustrated in its particular application to Pascal.

Utilization of a uniprocessor system in a multiprogramming environment can be optimized by maximizing the overlap of processor and input-output operations. A computational process can be modeled by a directed graph each node of which represents a task comprising processor and input-output segments. Any optimal schedulng algorithm for the model cannot be polynomially bounded, but the optimal criteria can be used to develop a hierarchy of dispatching heuristics based upon selecting an optimal partial task schedule. These heuristics are analyzed and evaluated by a simulation study and are shown to be more effective than those previously proposed. The dispatching heuristics developed have a wide range of potential applications to systems requiring dynamic task scheduling.

Two general classes of machines for performing code translation and serialization are considered;namely Translate-Table and State machines. The Translate-Table machine is a conventional two-stage machine comprising a translation stage folowed by a serialization stage. Two kinds of State machines are examined: 1) counter-driven and 2) microprogrammed.

No abstract available.