Predicting the execution time of parallel applications in High Performance Computing (HPC) clusters has served different objectives, including helping developers to find relevant areas of code that require fine tuning, designing better job schedulers to increase clusters' utilization, and detecting system bottlenecks. We present a statistical approach to predict parallel application execution times using empirical analyses of the application execution times for small input sizes and the time spent on various phases of execution. We model the execution time of each phase an application by selecting a suitable kernel from a collection of well known benchmark kernels. To predict the application execution time for a larger input, the matching kernels are used to estimate the execution times for the major phases of the application, and a regression approach is then used to estimate the overall execution time. Prior approaches required determination of application's characteristics by extracting instruction traces, instrumenting the application code for time stamps, static code analysis, or creation of accurate simulation models. In contrast, our approach requires a few short executions (each taking less than 50 seconds) of the application to collect runtime profile data that are used to match application phases to kernels using statistical analyses and produce accurate execution time predictions for parallel scientific applications. We evaluate our methodology using three well known parallel scientific applications: SMG2000, SNAP and HPCG. Our prediction errors range from 1% to 15%.

Communication privacy techniques that protect the locations of source sensor nodes and sink nodes have received significant attention recently. Several communication protocols that improve the capture time, which is the time it takes for an adversary to identify the location of the source, have been proposed and their effectiveness is analyzed using simulation models. A simple anonymous communication protocol (ACP) to hide source sensor nodes locations is proposed. ACP renders an adversary with complete understanding of ACP design and operation and with extensive computational and radio monitoring resources perform no better than an adversary who tries to identify sources by randomly checking sensor nodes. ACP achieves this by ensuring that (a) each node transmit a packet in each active period regardless whether it has data to send or not, and (b) dummy packets be indistinguishable from real packets based on the contents. A simple analytical model and extensive simulations are used to show that ACP effectively randomizes sources locations. Energy consumption analysis shows that the increased energy cost owing to transmissions in every active cycle is a small fraction of the overall energy consumption by sensor nodes.

Several intrusion detection techniques (IDTs) proposed for mobile ad hoc networks rely on each node passively monitoring the data forwarding by its next hop. This paper presents quantitative evaluations of false positives and their impact on monitoring-based intrusion detection for ad hoc networks. Experimental results show that, even for a simple three-node configuration, an actual ad hoc network suffers from high false positives; these results are validated by Markov and probabilistic models. However, this false positive problem cannot be observed by simulating the same network using popular ad hoc network simulators, such as ns-2, OPNET or Glomosim. To remedy this, a probabilistic noise generator model is implemented in the Glomosim simulator. With this revised noise model, the simulated network exhibits the aggregate false positive behavior similar to that of the experimental testbed. Simulations of larger (50-node) ad hoc networks indicate that monitoring-based intrusion detection has very high false positives. These false positives can reduce the network performance or increase the overhead. In a simple monitoring-based system where no secondary and more accurate methods are used, the false positives impact the network performance in two ways: reduced throughput in normal networks without attackers and inability to mitigate the effect of attacks in networks with attackers.

Several secure data aggregation (SDA) schemes are proposed in literature to reduce energy consumption for cryptographic operations and minimize their impact on the sensor network lifetime. Comparisons of SDA schemes focus primarily on the number of cryptographic operations used and number of bits transmitted in a given scenario. In reality, however, a sensor node operation is more complex: significant frame level overhead compared to data payload, sporadic communication, unreliable wireless links owing to radio interference from environment and competing transmissions by other sensor nodes, non-negligible energy consumption during sleep or power down mode, and overhead due to clock drift compensation. In this paper, we evaluate two representative SDA schemes in a more realistic setting by taking these other issues into account. We used TOSSIM simulator for our analyses, but validate our implementation of data aggregation techniques and simulation results using an analytical model. Our results show that, it is more crucial to reduce the number of packets transmitted than the overall number of bits transmitted. With low duty cycles and low probability of sensor data generation, even simple concatenation of sensor data, which reduces mostly the number of packets transmitted, is nearly as effective as the more sophisticated SDA schemes; when sensor data are generated more frequently, SDA schemes that do not require intermediate nodes to decrypt sensor data give 10% higher network lifetime.

Abstract Route falsification attacks are easy to launch in mobile ad hoc networks with on demand routing protocols that employ network‐wide flooding of control packets for route discoveries. To mitigate such attacks, we propose ap‐hop crosscheck mechanism, which requires nodesp,p ≥ 2, hops apart to authenticate and verify route reply packets using pairwise shared keys. This mechanism can detect route falsification by non‐colluding malicious nodes on‐the‐fly; furthermore, it can identify a group of at mostp+1 nodes that contain the malicious nodes that caused the route falsification. Unlike intrusion detection techniques, which require extensive monitoring and sampling, the proposed crosscheck mechanism is light‐weight and fast and hence can be used to augment the existing secure routing protocols and improve intrusion detection capability. We implement a two‐hopcrosscheck for an on demand ad hoc network routing protocol. Using simulations, we show that the two‐hopcrosscheck mitigates attacks by multiple malicious nodes with negligible impact on performance. Copyright © 2008 John Wiley & Sons, Ltd.

Abstract Colluding malicious insider nodes with no special hardware capability can use packet encapsulation and tunneling to create bogus shortcuts (in‐band wormholes) in routing paths and influence data traffic to flow through them. This is a particularly hard attack using which even a handful of malicious nodes can conduct data traffic analysis of packets or disrupt connections by dropping packets when needed. Simulation analysis shows that a disproportionately large amount of traffic goes through routes with wormholes even when a secure routing protocol (SRP) such as Ariadne is used. To mitigate such attacks and augment existing on demand SRPs, distributed packet filtering techniques based on statistical profiling of control packet propagation speeds are proposed. These techniques do not require network‐wide synchronized clocks or new packet transmissions and need only simple computations by the sources or the destinations of the connections. The proposed packet filters together with Ariadne are implemented in the Glomosim simulator and their effectiveness is evaluated. The simulation results indicate that the proposed packet filters can reduce the in‐band wormhole creation and their usage by a factor of 2‐‐10. Also, the false alarm rates of the proposed techniques are very low and have little impact on normal network throughput, making them practical for mobilead hocnetworks. Copyright © 2008 John Wiley & Sons, Ltd.

Several intrusion detection techniques proposed for mobile ad hoc networks rely on each node passively monitoring the data forwarding by its next hop. This paper presents quantitative evaluations of false positives and their impact on monitoring based intrusion detection for ad hoc networks. Experimental results show that even for a simple 3-node configuration, an actual ad hoc network suffers from high false positives; these results are validated by a Markov model. However, this false positive problem cannot be observed by simulating the same network using popular ad hoc network simulators such as ns- 2, OPNET or Glomosim with default noise models. To remedy this, a probabilistic noise generator model is incorporated in the Glomosim simulator. With this revised noise model, the simulated network exhibits the aggregate false positive behavior similar to that of the experimental testbed. Simulations of larger (50- node) ad hoc networks indicate that a monitoring based intrusion detection has very high false positives which impact its ability to mitigate the attacks.

Wormhole attacks, in which colluding attackers with out-of-band communication links record packets (or bits) at one location and replay at another, cause far away nodes to consider themselves as neighbors to one another. Such attacks can ruin the routing and communication capabilities of mobile ad hoc networks. This paper presents NEVO, in which nodes passively monitor (overhear) the forwarding of broadcast type packets by their neighbors and use the send and overhear times of transmissions of these packets, to mitigate these wormhole attacks. NEVO does not require synchronized clocks, special hardware support, or any special capability. NEVO can detect almost all instances of wormhole attacks and is virtually independent of the routing protocol used. NEVO is simple to implement - requires mostly network layer software changes, has low overhead, and is very robust. NEVO is implemented in the Glomosim simulator and its performance is evaluated. Simulation results show that NEVO effectively mitigates wormhole attacks (no data packets were sent through the wormholes in the simulated networks) and has low impact in normal with low to moderate traffic loads.

Colluding malicious insider nodes with no special hardware capability can use packet encapsulation and tunnelling to create bogus short-cuts (in-band wormholes) in routing paths and influence data traffic to flow through them. This is a particularly hard attack using which even a handful of malicious nodes can conduct traffic analysis of packets or disrupt connections by dropping packets when needed. Using simulations we show that a disproportionately large amount of traffic goes through routes with wormholes even when a secure routing protocol such as Ariadne is used. To mitigate this, we propose distributed techniques based on the propagation speeds of requests and statistical profiling; they do not require network-wide synchronized clocks, do not impose any additional control packet overhead, and need only simple computations by the sources or destinations of connections. We implemented our techniques in Ariadne and evaluated their effectiveness using the Glomosim simulator. Our results indicate that in-band wormhole creation and usage can be reduced by a factor of 2-10. Also, the false alarm rates of the proposed techniques are very low and have little impact on normal network operation, making them practical for MANETs.

Network simulators such as NS-2, Glomosim, and OPNET are extensively used to validate and evaluate the performance of network protocols for mobile ad hoc networks (MANETs). For accurate simulations, realistic signal propagation and noise models should be used to simulate the radio channels in MANETs. A significant amount of emphasis is put on the correctness of signal propagation, while the ambient noise (due to external sources) is modeled as a constant noise. Based on the noise levels measured in a wireless ad hoc network testbed, we present two analytical models to describe the noise levels in a real network: a generalized extreme value (GEV) random process model and a Markov chain model. We incorporate GEV noise model in the Glomosim network simulator and show that it impacts the network performance significantly.

Route falsification attacks are easy to launch in mobile ad hoc networks with on demand routing protocols that employ network-wide flooding of control packets for route discoveries. To mitigate this attack, we propose a p-hop crosscheck mechanism that requires nodes p, p ≥ 2, hops apart to authenticate and verify route reply packets using pair-wise shared keys. The crosscheck can detect route falsification by non-colluding malicious nodes on-the-fly; furthermore, it can identify a group of at most p+1 nodes that contain the malicious nodes that caused the route falsification. Unlike intrusion detection techniques, which require extensive monitoring and sampling, the proposed crosscheck mechanism is light-weight and fast. Therefore, the proposed crosscheck mechanism can be used to augment the existing secure routing protocols and improve intrusion detection capability. We implemented 2-hop crosscheck for AODV in the Glomosim simulator. Using simulations, we show that 2-hop crosscheck mitigates attacks by multiple malicious nodes with negligible performance impact.

We focus on the data models for storing the data generated by radio frequency identification (RFID) transactions and architectures for processing such data. We consider the supply chain comprised of the manufacturer, distributor, retailer, and the consumer. We discuss details of the data generated by RFID transactions and data models to store such data. Different organizations in the supply chain may use this data for different applications such as automatic product ordering, shelf replenishment, and product recall. We present models to anticipate the data requirements generated by RFID transactions and indicate how existing enterprise applications can be adapted to handle RFID data. The results presented in this paper will help a practitioner to 1) design and develop databases and applications for handling RFID data and 2) significantly reduce the storage requirements of RFID data. Using the data architectures, we discuss two supply chain applications-product recall and shelf replenishment-in detail. We present analytical models for the cost and time required for shelf replenishment in a retail store.

We present a novel divide and conquer method for parallelizing a large scale multivariate linear optimization problem, which is commonly solved using a sequential algorithm with the entire parameter space as the input. The optimization solves a large parameter estimation problem where the result is sparse in the parameters. By partitioning the parameters and the associated computations, our technique overcomes memory constraints when used in the context of a single workstation and achieves high processor utilization when large workstation, clusters are used. We implemented this technique in a widely used software package for the analysis of a biophysics problem, which is representative for a large class of problems in the physical sciences. We evaluate the performance of the proposed method on a 512-processor cluster and offer an analytical model for predicting the performance of the algorithm.

The on demand routing protocols for mobile ad hoc networks use network-wide broadcasts of control packets to learn routes. This feature can be exploited by malicious nodes to launch highly leveraged denial of service attacks in ad hoc networks. We use an adaptive statistical packet dropping mechanism to mitigate such attacks and their impact on throughput. The proposed mechanism does not use any additional network bandwidth. Using experiments on a wireless testbed, we evaluate the effectiveness of the statistical technique for UDP and TCP traffic

Ad hoc networks based on IEEE 802.11 (Wi-Fi) wireless links are viable for small regions with a few tens of mobile nodes, but such networks suffer from frequently broken routes and low network utilization. We investigate the benefits of adding a few infrastructure nodes to an otherwise ad hoc network to improve its performance. These infrastructure nodes are interconnected among themselves with point-to-point (p2p) links in addition to Wi-Fi capability. To evaluate the benefit of ad hoc networks with mixed broadcast wireless and point to point links, we modify an existing ad hoc routing protocol to automatically discover routes emphasizing p2p links and simulated several ad hoc and mixed networks using the Glomosim simulator. Our results show that adding a small number of point-to-point links makes a significant difference in performance with 2-3 times higher throughput and up to 2-3 times lower packet delays.

Ad hoc networks based on IEEE 802.11 (Wi-Fi) wireless links are viable for small regions with a few tens of mobile nodes, but such networks suffer from frequently broken routes and low network utilization. In this paper, we investigate the use of wireless networks large enough to span a campus or a town. To make these networks reliable, we propose mixed networks which are mostly ad hoc networks with a few infrastructure nodes, i-nodes. These i-nodes are interconnected with point-to-point, p2p, links in addition to Wi-Fi capability. We modify an existing ad hoc routing protocol to incorporate the relatively stable p2p links with the broadcast type Wi-Fi channels in finding routes. We have simulated several ad hoc and mixed networks using the Glomosim simulator. Our results show that adding a small number of i-nodes with p2p links can improve the performance dramatically with throughput increasing by a factor of 3 or more. Our results also indicate that using too many i-nodes beyond a certain limit does not improve the performance and that reducing radio transmission power can significantly reduce radio interference and improve throughput significantly.

We investigate the impact of hacker attacks by malicious nodes on the overall network performance. These malicious nodes mimic normal nodes in all aspects, except that they do route discoveries much more frequently than other nodes. We show, using simulations, that the basic route discovery mechanism used in many ad hoc network protocols can be exploited by as few as one malicious or compromised node to bring down throughput dramatically. We propose an adaptive statistical packet dropping mechanism to mitigate such situations and reduce the loss of throughput. The proposed mechanism works even when the identity of the malicious node is unknown and does not use any additional network bandwidth. It is simple to implement and maintains or improves network throughput when there are no malicious nodes, but the network is congested with excess traffic.

The IEEE 802.11 Medium Access Control (MAC) layer plays a crucial role on the overall throughput obtained in a mobile ad hoc network. We show that the virtual carrier sense mechanism as designed and used in 802.11 could have crippling effect on distant but competing transmissions. We propose a modification to mitigate this situation and show using simulations that the proposed modification provides as much as 50% higher User Datagram Protocol (UDP) throughput for static wireless networks and 10-25% higher throughput for mobile ad hoc networks.

We present a new routing algorithm called adaptive distance vector (ADV) for mobile, ad hoc networks (MANETs). ADV is a distance vector routing algorithm that exhibits some on-demand characteristics by varying the frequency and the size of the routing updates in response to the network load and mobility conditions. Using simulations we show that ADV outperforms AODV and DSR especially in high mobility cases by giving significantly higher (50% or more) peak throughputs and lower packet delays. Furthermore, ADV uses fewer routing and control overhead packets than that of AODV and DSR, especially at moderate to high loads. Our results indicate the benefits of combining both proactive and on-demand routing techniques in designing suitable routing protocols for MANETs.

We examine the performance of the TCP protocol for bulk-data transfers in mobile ad hoc networks (MANETs). We vary the number of TCP connections and compare the performances of three recently proposed on-demand (AODV and DSR) and adaptive proactive (ADV) routing algorithms. It has been shown in the literature that the congestion control mechanism of TCP reacts adversely to packet losses due to temporarily broken routes in wireless networks. So, we prospose a simple heuristic, called fixed RTO, to distinguish between route loss and network congestion and thereby improve the performance of the routing algorithms. Using the ns-2 simulator, we evaluate the performances of the three routing algorithms with the standard TCP Reno protocol and Reno with fixed RTO. Our results indicate that the proactive ADV algorithm performs well under a variety of conditions and that the fixed RTO technique improves the performances of the two on-demand algorithms significantly

The ad hoc on-demand distance vector (AODV) is an on-demand routing protocol designed specifically for mobile, ad hoc networks. But the packet latencies with AODV can be very high, >100 ms on average, especially when the network load is low and node mobility is high. To mitigate this effect, we have enhanced AODV with a proactive technique, which lets receiver nodes broadcast periodic 'beacons' throughout the network to keep routing entries in other nodes current. Using simulations we show that beacons reduce the packet latencies by a factor of 2-3. The routing packets transmitted are also reduced as the beacons obviate the need for some route discovery processes.

Multistage network based input-buffered ATM switches, which have been studied extensively, are cheaper compared to crossbar designs but suffer from elaborate cell selection methods or expensive network setup. In this paper, a fast cell selection method is proposed to avoid slow cell selection and costly network setup for these designs. In particular, we propose network hardware specific selection techniques for cell selection in input buffered Banyan network with an internal speed twice that of the external links. Our simulation results show that cell selection by looking at up to 10 cells in each input queue for switch sizes up to N=64 yields 95% or higher switch utilization.

The current fault-tolerant routing methods require extensive changes to practical routers such as the Cray T3D's dimension-order router to handle faults. In this paper, we propose methods to handle faults in multicomputers with dimension-order routers with simple changes to router structure and logic. Our techniques can be applied to current implementations in which the router is partitioned into multiple modules and no centralized crossbar is used. We consider arbitrarily located faulty blocks and assume only local knowledge of faults. We apply our techniques for torus networks and show that, with as few as four virtual channels per physical channel, deadlock- and livelock-free routing can be provided even with multiple faults and multimodule implementation of routers. Our simulations of the proposed technique for 2D tori and mesh indicate that the performance degradation is similar to that seen in the case of cross-bar based designs previously proposed.

We show that deadlocks due to dependencies on consumption channels are a fundamental problem in wormhole multicast routing. This type of resource deadlocks has not been addressed in many previously proposed wormhole multicast algorithms. We also show that deadlocks on consumption channels can be avoided by using multiple classes of consumption channels and restricting the use of consumption channels by multicast messages. We provide upper bounds for the number of consumption channels required to avoid deadlocks. In addition, we present a new multicast routing algorithm, column-path, which is based on the well-known dimension-order routing used in many multicomputers and multiprocessors. Therefore, this algorithm could be implemented in existing multicomputers with simple changes to the hardware. Using simulations, we compare the performance of the proposed column-path algorithm with the previously proposed Hamiltonian-path-based multipath and an e-cube-based multicast routing algorithms. Our results show that for multicast traffic, the column-path routing offers higher throughputs, while the multipath algorithm offers lower message latencies. Another result of our study is that the commonly implemented simplistic scheme of sending one copy of a multicast message to each of its destinations exhibits good performance provided the number of destinations is small.

Recent multiprocessors such as the Cray T3D support interprocessor communication using partitioned dimension-order routers (PDRs). In a PDR implementation, the routing logic and switching hardware is partitioned into multiple modules, with each module suitable for implementation as a chip. This paper proposes a method to incorporate adaptivity into such routers with simple changes to the router structure and logic. We show that with as few as two virtual channels per physical channel, adaptivity can be provided to handle nonuniform traffic in multidimensional meshes.

A technique to enhance multicomputer routers for fault-tolerant routing with modest increase in routing complexity and resource requirements is described. This method handles solid faults in meshes, which includes all convex faults and many practical nonconvex faults, for example, faults in the shape of L or T. As examples of the proposed method, adaptive and nonadaptive fault-tolerant routing algorithms using four virtual channels per physical channel are described.

The current multiprocessors such as Cray T3D support interprocessor communication using partitioned dimension-order routers (PDRs). In a PDR implementation, the routing logic and switching hardware is partitioned into multiple modules, with each module suitable for implementation as a chip. This paper proposes a method to incorporate fault-tolerance into such routers with simple changes to the router structure and logic. The previously known fault-tolerant routing methods assume centralized crossbar based routers and are not applicable to multiprocessors with PDRs. The proposed technique works for convex fault model, using only local knowledge of faults. Using the proposed techniques and as few as four virtual channels per physical channel, torus networks with PDRs can handle faults without compromising deadlock- and livelock-freedom. Simulations for 2-dimensional torus and mesh networks show that the resulting fault-tolerant PDRs have performances similar to those of the crossbar based routers.

This paper presents a framework to design fully-adaptive, deadlock-free wormhole algorithms for a variety of network topologies. The main theoretical contributions are: (a) design of new wormhole algorithms using store-and-forward algorithms, (b) a sufficient condition for deadlock free routing by the wormhole algorithms so designed, and (c) a sufficient condition for deadlock free routing by these wormhole algorithms with centralized flit buffers shared among multiple channels. To illustrate the theory, several wormhole algorithms based on store-and-forward hop schemes are designed. The hop-based wormhole algorithms can be applied to a variety of networks including torus, mesh, de Brujin, and a class of Cayley networks, with the best known bounds on virtual channels for minimal routing on the last two classes of networks. An analysis of the resource requirements and performances of a proposed algorithm, called negative-hop algorithm, with some of the previously proposed algorithms for torus and mesh networks is presented.

We present simple methods to enhance the current minimal wormhole routing algorithms developed for high radix, low dimensional mesh networks for fault tolerant routing. We consider arbitrarily located faulty blocks and assume only local knowledge of faults. Messages are routed minimally when not blocked by faults and this constraint is relaxed to route around faults. The key concept we use is a fault ring consisting of fault free nodes and links can be formed around each fault region. Our fault tolerant techniques use these fault rings to route messages around fault regions. We show that, using just one extra virtual channel per physical channel, the well known e cube algorithm can be used to provide deadlock free routing in networks with nonoverlapping fault rings; there is no restriction on the number of faults. For the more complex faults with overlapping fault rings, four virtual channels are used. We also prove that at most four additional virtual channels are sufficient to make fully adaptive algorithms tolerant to multiple faulty blocks in n dimensional meshes. All these algorithms are deadlock and livelock free. Further, we present simulation results for the e cube and a fully adaptive algorithm fortified with our fault tolerant routing techniques and show that good performance may be obtained with as many as 10% links faulty.>

We present a method to enhance wormhole routing algorithms for deadlock-free fault-tolerant routing in tori. We consider arbitrarily-located faulty blocks and assume only local knowledge of faults. Messages are routed via shortest paths when there are no faults, and this constraint is only slightly relaxed to facilitate routing in the presence of faults. The key concept we use is that, for each fault region, a fault ring consisting of fault free nodes and physical channels can be formed around it. These fault rings can be used to route messages around fault regions. We prove that at most four additional virtual channels are sufficient to make any fully-adaptive algorithm tolerant to multiple faulty blocks in torus networks. As an example of this technique, we present simulation results for a fully-adaptive algorithm and show that good performance can be obtained with as many as 10% links faulty.

We present simple techniques to enhance the e-cube algorithm for fault-tolerant routing in mesh networks. These techniques are based on the concept of fault rings, which are formed using fault free nodes and links around each fault region. We use fault rings to enhance the e-cube to route messages in the presence of rectangular block faults. We show that if fault rings do not overlap with one another-the sets of links in fault rings are pairwise disjoint, then two virtual channels per physical channel are sufficient to make the e-cube tolerant to any number of faulty blocks. For more complex cases such as overlapping fault rings and faults on network boundaries, three or four virtual channels are used. In all cases, the routing guarantees livelock and deadlock free delivery of each and every message injected into the network. Our simulation results for isolated faults indicate that the proposed method provides acceptable performance with as many as 10 percent faulty links.>

Improvement of message latency and network utilization in torus interconnection networks by increasing adaptivity in wormhole routing algorithms is studied. A recently proposed partially adaptive algorithm and four new fully-adaptive routing algorithms are compared with the well-known e-cube algorithm for uniform, hotspot, and local traffic patterns. Our simulations indicate that the partially adaptive north-last algorithm, which causes unbalanced traffic in the network, performs worse than the nonadaptive e-cube routing algorithm for all three traffic patterns. Another result of our study is that the performance does not necessarily improve with full-adaptivity. In particular, a commonly discussed fully-adaptive routing algorithm, which uses 2n virtual channels per physical channel of a k-ary n-cube, performs worse than e-cube for uniform and hotspot traffic patterns. The other three fully-adaptive algorithms, which give priority to messages based on distances traveled, perform much better than the e-cube and partially-adaptive algorithms for all three traffic patterns. One of the conclusions of this study is that adaptivity, full or partial, is not necessarily a benefit in wormhole routing.

The authors present self-routing algorithms for realizing the class of linear permutations in various multistage networks such as Benes and 2n-stage shuffle-exchange. Linear permutations are useful in providing fast access of data arrays. In the first half of the network, switches are set by comparing the destination tags at their inputs, and, in the second half, switches are set using the Omega self-routing algorithm. It is shown that the comparison operations can be implemented in bit-serial networks without loss of time. In contrast, with the well-known Benes network self-routing algorithm of D. Nassimi and S. Sahni (1981), switches are set by giving priority to the destination tag at the upper input to them. The algorithms presented are useful in providing fast access of various data patterns using interconnection networks cheaper than crossbars.>