Search

Presents the special issue in the journal "Parallel Processing Letters," which contains the best papers from the Centre Interantional de Rencontres Mathématiques workshopin October 2001. "Scheduling Issues in Survivality Applications Using Hybrid Fault Models," by A. W. Krings, W. S. Harrison, A. Azadmanesh and M. McQueen"; "Parallel Tabu Search Approaches for Two-Dimensional Cutting," by J. Blazewicz, A. Moret-Salvador and R. Walkowiak"; "Strategies for Workload Balancing in Cluster-Based Image Databases," by F. Drews, K. Ecker, O. Kao and S. Schomann.

A directory service keeps track of the location and status of mobile objects in a distributed system. This paper describes our experience implementing two distributed directory protocols as part of the Aleph toolkit, a distributed shared object system implemented in Java. One protocol is a conventional home-based protocol, in which a fixed node keeps track of the object's location and status. The other is a novel Arrow protocol, based on a simple path-reversal algorithm. We were surprised to discover that the Arrow protocol outperformed the home protocol, sometimes substantially, across a range of system sizes. This paper describes a series of experiments testing whether the discrepancy is due to an artifact of the Java run-time system (such as differences in thread management or object serialization costs), or whether it is something inherent in the protocols themselves. In the end, we use insights gained from these experimental results to design a new directory protocol that combines advantages of both. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Abstract  This paper emphasizes the importance of defining processes rigorously, completely, clearly, and in detail in order to support the complex projects that are essential to the modern world. The paper argues that such process definitions provide needed structure and context for the development of effective software systems. The centrality of process is argued by enumerating seven key ways in which processes and their definitions are expected to provide important benefits to society. The paper provides an example of a process formalism that makes good progress towards the difficult goal of being simultaneously rigorous, detailed, broad, and clear. Early experience suggests that these four key characteristics of this formalism do indeed seem to help it to support meeting the seven key benefits sought from process definitions. Additional research is suggested in order to gain more insights into needs in the area of process definition formalisms. [ABSTRACT FROM AUTHOR]

Efficient exact schedulability tests are required both for online admission of applications to dynamic systems and as an integral part of design tools for complex distributed real-time systems. This paper addresses performance issues with exact response time analysis (RTA) for fixed priority preemptive systems. Initial values are introduced that improve the efficiency of the standard RTA algorithm 1) when exact response times are required and 2) when only exact schedulability need be determined. This paper also explores modifications to the standard RTA algorithm, including the use of a response time upper bound to determine when exact analysis is needed, incremental computation aimed at faster convergence, and checking tasks in reverse priority order to identify unschedulable tasksets early. The various initial values and algorithm implementations are compared by means of experiments on a PC recording the number of iterations required and execution time measurements on a real-time embedded microprocessor. Recommendations are provided for engineers tasked with the problem of implementing exact schedulability tests as part of online acceptance tests and spare capacity allocation algorithms or as part of offline system design tools. [ABSTRACT FROM AUTHOR]

We introduce Probabilistic Resilient Multicast (PRM): a multicast data recovery scheme that improves data delivery ratios while maintaining low end-to-end latencies. PRM has both a proactive and a reactive components; in this paper we describe how PRM can be used to improve the performance of application-layer multicast protocols especially when there are high packet losses and host failures. Through detailed analysis in this paper, we show that this loss recovery technique has efficient scaling properties—the overheads at each overlay node asymptotically decrease to zero with increasing group sizes. As a detailed case study, we show how PRM can be applied to the NICE application-layer multicast protocol. We present detailed simulations of the PRM-enhanced NICE protocol for 10 000 node Internet-like topologies. Simulations show that PRM achieves a high delivery ratio (>97%) with a low latency bound (600 ms) for environments with high end-to-end network losses (1%–5 %) and high topology change rates (5 changes per second) while incurring very low overheads (<5%). [ABSTRACT FROM AUTHOR]

Abstract  Recently, distributed source coding (DSC) has been proposed to implement source compression by exploiting source statistics at the decoder only, which enables low-complexity video coding. However, to date, the video codecs based on DSC have been unable to compress as efficiently as traditional predictive video codecs, such as H.264. So, new techniques have to be investigated to improve the performance of the distributed video coding scheme for practical applications. In this paper, I propose a novel distributed video coding scheme based on part intracoding and soft side information estimation. Firstly, at the encoder side, to improve the compression performance of distributed video coding system, we divide the video data into strongly correlative data encoded by Slepian–Wolf codec and weakly correlative data encoded by Intracoding codec. Secondly, at the decoder side, to improve the accuracy of side information estimation, a soft side information estimation method is proposed, which is more suitable for video coding due to the non-stationary feature of video data. Our experimental results show that the performance of our coding system is better than that of the traditional distributed video coding system while keeping the simple encoding property. Also the concept of soft side information is a new idea in distributed video coding and will significantly influence the side information estimation method. [ABSTRACT FROM AUTHOR]

Emerging network technologies have complex network interfaces that have renewed concerns about network reliability. In this paper, we present an effective low-overhead fault tolerance technique to recover from network interface failures. Failure detection is based on a software watchdog timer that detects network processor hangs and a self-testing scheme that detects interface failures other than processor hangs. The proposed self-testing scheme achieves failure detection by periodically directing the control flow to go through only active software modules in order to detect errors that affect instructions in the local memory of the network interface. Our failure recovery is achieved by restoring the state of the network interface using a small backup copy containing just the right amount of information required for complete recovery. The paper shows how this technique can be made to minimize the performance impact to the host system and be completely transparent to the user. [ABSTRACT FROM AUTHOR]

In this paper, we rigorously investigate the energy minimization problem for wireless packet networks with automatic repeat request (ARQ) capability. We first formulate the problem for the single-hop case under constrained packet delay and reliability and derive the necessary and sufficient condition for the optimal transmission power at each ARQ stage. We formulate a global rule of optimal transmission power control that achieves optimality regardless of the delay and reliability constraints. Then we extend it to encompass the multi-hop case by dividing the overall problem into two subproblems—energy determination for each ARQ stage and energy distribution among the constituent nodes. We show that the optimality condition established for the single-hop case is also applicable to solve the energy determination problem in the multi-hop case, rendering an optimal solution to the energy distribution problem. Numerical examples reveal that a significant amount of energy is saved by adopting the optimal transmission power and the performance gain is strongly correlated with the decreasing property of the frame error rate. [ABSTRACT FROM AUTHOR]

Routing and wavelength assignment (RWA) is a central issue to increase efficiency and reduce cost in Wavelength Division Multiplexing (WDM) optical networks. In this paper, we address the problem of wavelength assignment for realizing parallel FFT on a class of regular optical WDM networks. We propose two methods for sequential mapping and shift-reversal mapping of FFT communication pattern to the optical WDM networks concerned. By sequential mapping, the numbers of wavelengths required to realize parallel FFT with 2 n nodes on WDM linear arrays, rings, 2-D meshes and 2-D tori are 2 n − 1, 2 n − 1, 2max ( k, n − k) − 1 and 2max ( k, n − k) − 1 respectively. By shift-reversal mapping, the numbers of wavelengths required are max (3× 2 n − 3,2), 2 n − 2, max (3× 2max ( k, n − k) − 3,2) and 2max ( k, n − k) − 2. These results show that shift-reversal mapping outperforms sequential mapping. Our results have a clear significance for applications because FFT represents a common computation pattern shared by a large class of scientific and engineering problems and WDM optical networks as a promising technology in networking has an increasing popularity. [ABSTRACT FROM AUTHOR]

This paper proposes S-MAC, a medium access control (MAC) protocol designed for wireless sensor networks. Wireless sensor networks use battery-operated computing and sensing devices. A network of these devices will collaborate for a common application such as environmental monitoring. We expect sensor networks to be deployed in an ad hoc fashion, with nodes remaining largely inactive for long time, but becoming suddenly active when something is detected. These characteristics of sensor networks and applications motivate a MAC that is different from traditional wireless MACs such as IEEE 802.11 in several ways: energy conservation and self-configuration are primary goals, while per-node fairness and latency are less important. S-MAC uses a few novel techniques to reduce energy consumption and support self-configuration. It enables low-duty-cycle operation in a multihop network. Nodes form virtual clusters based on common sleep schedules to reduce control overhead and enable traffic-adaptive wake-up. S-MAC uses in-channel signaling to avoid overhearing unnecessary traffic. Finally, S-MAC applies message passing to reduce contention latency for applications that require in-network data processing. The paper presents measurement results of S-MAC performance on a sample sensor node, the UC Berkeley Mote, and reveals fundamental tradeoffs on energy, latency and throughput. Results show that S-MAC obtains significant energy savings compared with an 802.11-like MAC without sleeping. [ABSTRACT FROM AUTHOR]

TCP does not perform well in a connection that includes a lossy wireless link. Techniques intended to improve the performance of TCP for such connections can be grouped into three categories: end-to-end, link layer and split-connection approaches. Some simulations and experimental results indicate that split-connection protocols yield better performance than the other two approaches. Although analytical modeling of the end-to-end and link-layer approaches has been presented, no comparable performance analysis for split-connection protocols has been reported previously. In this paper, a stochastic model is developed and used to analyze the performance of a class of split-connection protocols which deploy TCP on the wire-line network and a light-weight transport protocol on the wireless final hop. The final hop is provided by a digital TDMA cellular system. The condition of heavy source traffic to the wireless terminal is considered. The model relates the throughput and some useful auxiliary performance measures to key system parameters such as propagation delays, the base-station buffer size, the ARQ protocol and channel-error process of the wireless link. The usefulness of the analysis is illustrated by its application to the problem of sizing the TCP receiving buffer in a base station. [ABSTRACT FROM AUTHOR]

A graph G with n vertices and maximum degree ΔG cannot be given weak sense of direction using less than ΔG colours. It is known that n colours are always sufficient, and it was conjectured that just ΔG + 1 are really needed, that is, one more colour is sufficient. Nonetheless, it has been shown [3] that for sufficiently large n there are graphs requiring Ω(n log log n/ log n) more colours than ΔG. In this paper, using recent results in asymptotic graph enumeration, we show that (surprisingly) the same bound holds for regular graphs. We also show that Ω(dG√log log dG) colours are necessary, where dG is the degree of G. [ABSTRACT FROM AUTHOR]

Sensor networks (SNs) consist of spatially distributed sensors which monitor an environment, and which are connected to some sinks or backbone system to which the sensor data is being forwarded. In many cases, the sensor nodes themselves can serve as intermediate nodes for data coming from other nodes, on the way to the sinks. Much of the traffic carried by SNs will originate from routine measurements or observations by sensors that monitor a particular situation, such as the temperature and humidity in a room or the infrared observation of the perimeter of a house, so that the volume of routine traffic resulting from such observations may be quite high. When important and unusual events occur, such as a sudden fire breaking out or the arrival of an intruder, it will be necessary to convey this new information very urgently through the network to a designated set of sink nodes where this information can be processed and dealt with. This paper addresses the important challenge by avoiding the routine background traffic from creating delays or bottlenecks that impede the rapid delivery of high priority traffic resulting from the unusual events. Specifically we propose a novel technique, the ‘Randomized Re-Routing Algorithm (RRR)’, which detects the presence of novel events in a distributed manner, and dynamically disperses the background traffic towards secondary paths in the network, while creating a ‘fast track path’ which provides better delay and better quality of service (QoS) for the high priority traffic which is carrying the new information. When the surge of new information has subsided, this is again detected by the nodes and the nodes progressively revert to best QoS or shortest-path routing for all the ongoing traffic. The proposed technique is evaluated using a mathematical model as well as simulations, and is also compared with a standard node by a node priority scheduling technique. [ABSTRACT FROM PUBLISHER]

Information systems (IS) research has been long concerned with improving task-related performance. The concept of fit is often used to explain how system design can improve performance and overall value. So far, the literature has focused mainly on performance evaluation criteria that are based on measures of task efficiency, accuracy, or productivity. However, nowadays, productivity gain is no longer the single evaluation criterion. In many instances, computer systems are expected to enhance our creativity, reveal opportunities and open new vistas of uncharted frontiers. To address this void, we introduce the concept of generativity in the context of IS design and develop two corresponding design considerations –‘generative capacity’ that refers to one's ability to produce something ingenious or at least new in a particular context, and ‘generative fit’ that refers to the extent to which an IT artefact is conducive to evoking and enhancing that generative capacity. We offer an extended view of the concept of fit and realign the prevailing approaches to human–computer interaction design with current leading-edge applications and users' expectations. Our findings guide systems designers who aim to enhance creative work, unstructured syntheses, serendipitous discoveries, and any other form of computer-aided tasks that involve unexplored outcomes or aim to enhance our ability to go boldly where no one has gone before. In this paper, we explore the underpinnings of ‘generative capacity’ and argue that it should be included in the evaluation of task-related performance. Then, we briefly explore the role of fit in IS research, position ‘generative fit’ in that context, explain its role and impact on performance, and provide key design considerations that enhance generative fit. Finally, we demonstrate our thesis with an illustrative vignette of good generative fit, and conclude with ideas for further research. [ABSTRACT FROM AUTHOR]

Many approximation algorithms have been presented in the last decades for NP-hard search problems. The focus of this paper is on cryptographic applications, where it is desirable to design algorithms which do not leak unnecessary information. Specifically, we are interested in private approximation algorithms--efficient approximation algorithms whose output does not leak information not implied by the optimal solutions to the search problems. Privacy requirements add constraints on the approximation algorithms; in particular, known approximation algorithms usually leak a lot of information. For functions, Feigenbaum et al. [ACM Trans. Algorithms, 2 (2006), pp. 435-472] presented a natural requirement that a private algorithm should not leak information not implied by the original function. Generalizing this requirement to relations is not straightforward as an input may have many different outputs. We present a new definition that captures a minimal privacy requirement from such algorithms; applied to an input instance, it should not leak any information that is not implied by its collection of exact solutions. We argue that our privacy requirement is natural and quite minimal. We show that, even under this minimal definition of privacy, for well-studied problems such as vertex cover and max exact 3SAT, private approximation algorithms are unlikely to exist even for poor approximation ratios. Similarly to Halevi et al. [in Proceedings of the 33rd ACM Symposium on Theory of Computing, ACM, New York, 2001, pp. 550-559], we define a relaxed notion of approximation algorithms that leak (a little) information, and demonstrate the applicability of this notion by showing near optimal approximation algorithms for max exact 3SAT that leak a little information. [ABSTRACT FROM AUTHOR]

With the availability of affordable sensors and sensor networks, sensor-based human-activity recognition has attracted much attention in artificial intelligence and ubiquitous computing. In this paper, we present a novel two-phase approach for detecting abnormal activities based on wireless sensors attached to a human body. Detecting abnormal activities is a particularly important task in security monitoring and healthcare applications of sensor networks, among many others. Traditional approaches to this problem suffer from a high false positive rate, particularly, when the collected sensor data are biased toward normal data while the abnormal events are rare. Therefore, there is a lack of training data for many traditional data mining methods to be applied. To solve this problem, our approach first employs a one-class support vector machine (SVM) that is trained on commonly available normal activities, which filters out the activities that have a very high probability of being normal. We then derive abnormal activity models from a general normal model via a kernel nonlinear regression (KNLR) to reduce the false positive rate in an unsupervised manner. We show that our approach provides a good tradeoff between the abnormality detection rate and false alarm rate and allows abnormal activity models to be automatically derived without the need to explicitly label the abnormal training data, which are scarce. We demonstrate the effectiveness of our approach using real data collected from a sensor network that is deployed in a realistic setting. [ABSTRACT FROM AUTHOR]

The classical problem of diagnosability is discussed widely and the diagnosability of many well-known networks have been explored. In this paper, we consider the diagnosability of a family of networks, called the Matching Composition Network (MCN); two components are connected by a perfect matching. The diagnosability of MCN under the comparison model is shown to be one larger than that of the component, provided some connectivity constraints are satisfied. Applying our result, the diagnosability of the Hypercube Qn, the Crossed cube CQn the Twisted cube TQn and the Möbius cube MQn, can all be-proven to be n, for n ≥4. In particular, we show that the diagnosability of the four- dimensional Hypercube Q4 is 4, which is not previously known. [ABSTRACT FROM AUTHOR]

This paper studies the problem of electing a small number of representatives (council) out of a (possible large) group of anonymous candidates. The problem arises in scenarios such as multicast where, to avoid feedback implosion, a small subset of the receivers is chosen to provide feedback on network conditions. We present several algorithms for this problem and analyze the expected number of messages and rounds required for their convergence. In particular, we present an algorithm that almost always converges in one round using a small number of messages (for typical council size) when the number of hosts is known. In the case where the number of hosts is unknown (and too large to be polled), our algorithms converge in a small number of rounds that improves previous results by Bolot et al. (1994). [ABSTRACT FROM AUTHOR]

We discuss nearest neighbor load balancing schemes on processor networks which are represented by a cartesian product of graphs and present a new optimal diffusion scheme for general graphs. In the first part of the paper, we introduce the Alternating-Direction load balancing scheme, which reduces the number of load balance iterations by a factor of 2 for cartesian products of graphs. The resulting flow is theoretically analyzed and can be very high for certain cases. Therefore, we further present the Mixed-Direction scheme which needs the same number of iterations but computes in most cases a much smaller flow. In the second part of the paper, we present a simple optimal diffusion scheme for general graphs, calculating a balancing flow which is minimal in the l2 norm. It is based on the spectra of the graph representing the network and needs only m — 1 iterations to balance the load with m being the number of distinct eigenvalues. Known optimal diffusion schemes have the same performance, however the optimal scheme presented in this paper can be implemented in a very simple manner. The number of iterations of optimal diffusion schemes is independent of the load scenario and, thus, they are practical for networks which represent graphs with known spectra. Finally, our experiments exhibit that the new optimal scheme can successfully be combined with the Alternating-Direction and Mixed-Direction schemes for efficient load balancing on product graphs. [ABSTRACT FROM AUTHOR]

Users previously had to use transcoding methods in which a coded audio stream was decoded and the decoded audio then reencoded at the desired bit rate. Data processing of coded audio therefore usually involves complex and time-consuming tasks. In this paper, we describe three algorithms for bit rate scaling on coded MPEG data domains. One is a bandwidth limitation method to cut higher frequency components until the target data rate is satisfied. A second method uses a requantization process where a quantization step in each subband is modified, and a third method also utilizes a requantization process with a psychoacoustic model from bit allocation information obtained in the bitstream in order to improve bit rate scaling efficiency. The simulation results show that the requantization process provides very high conversion efficiency and that sound quality nearly equal to that of direct coding can be obtained by utilizing the psychoacoustic model. It was also shown that very fast scaling (factor of six) can be achieved compared with the conventional baseband transcoding method. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(10): 47–56, 2001 [ABSTRACT FROM AUTHOR]

Data sharing is an essential process for collaborative works particularly in the banking, finance and healthcare industries. These industries require many collaborative works with their internal and external parties such as branches, clients, and service providers. When data are shared among collaborators, security and privacy concerns becoming crucial issues and cannot be avoided. Privacy is an important issue that is frequently discussed during the development of collaborative systems. It is closely related with the security issues because each of them can affect the other. The tradeoff between privacy and security is an interesting topic that we are going to address in this paper. In view of the practical problems in the existing approaches, we propose a collaborative framework which can be used to facilitate concurrent operations, single point failure problem, and overcome constraints for two-party computation. Two secure computation protocols will be discussed to demonstrate our collaborative framework. [ABSTRACT FROM AUTHOR]

Abstract: Effective address calculations for load and store instructions need to compete for ALU with other instructions and hence extra latencies might be incurred to data cache accesses. Fast address generation is an approach proposed to reduce cache access latencies. This paper presents a fast address generator that can eliminate most of the effective address computations by storing computed effective addresses of previous load/store instructions in a dummy register file. Experimental results show that this fast address generator can reduce effective address computations of load and store instructions by about 74% on average for SPECint2000 benchmarks and cut the execution times by 8.5%. Furthermore, when multiple dummy register files are deployed, this fast address generator eliminates over 90% of effective address computations of load and store instructions and improves the average execution times by 9.3%. [Copyright &y& Elsevier]

Copyright of Computer Science (1407-7493) is the property of RTU Publishing House and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Abstract  As outsourcing data centers emerge to host applications and services from many different organizations, it is critical for data center owners to isolate different applications while dynamically and optimally allocate sharable resources among them. To address this issue, we propose a virtual-appliance-based autonomic resource provisioning framework for large virtualized data centers. We present the architecture of the data center with enriched autonomic features. We define a non-linear constrained optimization model for dynamic resource provisioning and present a novel analytic solution. Key factors, including virtualization overhead and reconfiguration delay, are incorporated into the model. Experimental results based on a prototype demonstrate that the system-level performance has been greatly improved by taking advantage of fine-grained server consolidation, and the whole system exhibits flexible adaptation in failure scenarios. Experiments with the impact of switching delay also show the efficiency of the framework due to significantly reduced provisioning time. [ABSTRACT FROM AUTHOR]

As distributed configurations of high-powered workstations connected by networks become prevalent, tools for writing distributed programs take on increasing importance. This paper describes our experience implementing CES, a distributed Collaborative Editing System. CES was written in Argus, a language that was designed to support the construction of reliable distributed programs,and exhibits a number of requirements typical of distributed applications. Our experience illustrates numerous areas in which the support provided by Argus for meeting those requirements was quite helpful, but also identifies several areas in which the support provided by Argus was inadequate. Some of the problems arise because of the distinction in Argus (and in other systems) between locally and remotely accessible data and the mechanisms provided for implementing each. Others arise because of limitations of the mechanisms for building user-defined data types. We discuss the problems we encountered, including their implications for other systems. We also suggest solutions to the problems, or in some cases further research directed at finding solutions. [ABSTRACT FROM AUTHOR]

One of the factors which affect the convergence velocity in the learning by a parallel distributed processing network is the input/output characteristic of its elements. This paper proposes anew a learning distance product element to substitute for the conventional learning threshold elements, and performs the computer simulation of a three-layered network with two inputs and one output using the learning distance product elements. As a result, it is confirmed that on average, learning is accelerated compared to the use of the learning threshold elements. [ABSTRACT FROM AUTHOR]

The widespread location-aware applications produce a vast amount of spatio-textual data that contains both spatial and textual attributes. To make use of this enriched information for users to describe their preferences for travel routes, we propose a Bounded-Cost Informative Route (BCIR) query to retrieve the routes that are the most textually relevant to the user-specified query keywords subject to a travel cost constraint. BCIR query is particularly helpful for tourists and city explorers to plan their travel routes. We will show that BCIR query is an NP-hard problem. To answer BCIR query efficiently, we propose an exact solution with effective pruning techniques and two approximate solutions with performance guarantees. Extensive experiments over real data sets demonstrate that the proposed solutions achieve the expected performance. [ABSTRACT FROM PUBLISHER]

The Dutch Advanced School for Computing and Imaging has built five generations of a 200-node distributed system over nearly two decades while remaining aligned with the shifting computer science research agenda. The system has supported years of award-winning research, underlining the benefits of investing in a smaller-scale, tailored design. [ABSTRACT FROM PUBLISHER]

We put forward a new type of computationally sound proof system called universal arguments. Universal arguments are related but different from both CS proofs (as defined by Micali [SIAM J. Comput., 37 (2000), pp. 1253-1298]) and arguments (as defined by Brassard, Chaum, and Crépeau [J. Comput. System Sci., 37 (1988), pp. 156-189]. In particular, we adopt the instance-based prover-efficiency paradigm of CS proofs but follow the computational-soundness condition of argument systems (i.e., we consider only cheating strategies that are implementable by polynomial-size circuits). We show that universal arguments can be constructed based on standard intractability assumptions that refer to polynomial-size circuits (rather than based on assumptions that refer to subexponential-size circuits as used in the construction of CS proofs). Furthermore, these protocols have a constant number of rounds and are of the public-coin type. As an application of these universal arguments, we weaken the intractability assumptions used in the non-black-box zero-knowledge arguments of Barak [in Proceedings of the 42nd IEEE Symposiun on Foundations of Computer Science, 2001]. Specifically, we only utilize intractability assumptions that refer to polynomial-size circuits (rather than assumptions that refer to circuits of some "nice" superpolynomial size). [ABSTRACT FROM AUTHOR]

Reducing the design complexity of switches is essential for cost reduction and power saving in on-chip networks. In wormhole-switched networks, packets are split into flits which are then admitted into and delivered in the network. When reaching destinations, flits are ejected from the network. Since flit admission, flit delivery and flit ejection interfere with each other directly and indirectly, techniques for admitting and ejecting flits exert a significant impact on network performance and switch cost. Different flit-admission and flit-ejection micro-architectures are investigated. In particular, for flit admission, a novel coupling scheme which binds a flit-admission queue with a physical channel (PC) is presented. This scheme simplifies the switch crossbar from 2p×p to (p+1)×p, where p is the number of PCs per switch. For flit ejection, a p-sink model that uses only p flit sinks to eject flits is proposed. In contrast to an ideal ejection model which requires p · v flit sinks (v is the number of virtual channels per PC), the buffering cost of flit sinks becomes independent of v. The proposed flit-admission and flit-ejection schemes are evaluated with both uniform and locality traffic in a 2D 4×4 mesh network. The results show that both schemes do not degrade network performance in terms of average packet latency and throughput if the flit injection rate is slower than 0.57 flit/cycle/node. [ABSTRACT FROM AUTHOR]

Building on the success of unicast IP, IP Multicast adopted a simple, open, best-effort delivery model with many-to-many semantics. Despite several years of effort, a general, scalable and reliable end-to-end transport protocol analogous to TCP has proven elusive. Proposed solutions are either inflexible, or incur high control overhead. We present Lightweight Multicast Services (LMS), which enhance the IP Multicast model with simple forwarding services to facilitate scalable and efficient (compared to pure end-to-end) solutions to problems such as reliable multicast. In LMS, routers tag and steer control packets to preselected endpoints and perform fine-grain multicast to guide responses to a subset of the group without transport-level processing. LMS divides error control into transport and forwarding components, which allows the former to remain at the end-points while the latter is pushed to the routers, where it can be implemented very efficiently. The division is clean, resulting in significant gains in performance and scalability, while reducing application complexity. LMS reaches beyond reliable multicast to applications such as scalable collect, any-cast, and in general, any application that can benefit from a hierarchy congruent with the underlying topology. [ABSTRACT FROM AUTHOR]

Parallelization of the algebraic fictitious domain method is considered for solving Neumann boundary value problems with variable coefficients. The resulting method is applied to the parallel solution of the subsonic full potential flow problem which is linearized by the Newton method. Good scalability of the method is demonstrated on a Cray T3E distributed memory parallel computer using MPI in communication. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

As our networks, hosts, and services become complex, and indeed, as the number of networks, hosts, and services grow and shrink on demand through the magic of virtualization, uncovering software defects by analyzing packet traces are becoming even more important. A by-product of Big Data appears to be Big Traces as well. [ABSTRACT FROM PUBLISHER]