Asynchronous Shared Memory Search Structures

We study the problem of storing an ordered set on an asynchronous shared memory parallel computer. We examine the case where we want to perform successor (least upper bound) queries efficiently on the set members that are stored. We also examine the case where processors insert and delete members of the set. Due to asynchrony, we require processors to perform queries and to maintain the structure independently. Although several such structures have been proposed, the analysis of these structures has been very limited. We here use the recently proposed QRQW PRAM model to provide upper and lower bounds on the performance of such data structures. In the asynchronous QRQW PRAM, the problem of processors concurrently and independently searching a shared data structure is very similar to the problem of routing packets through a network. Using this as a guide, we introduce the Search-Butterfly, a search structure that combines the efficient packet routing properties of the butterfly graph with the efficient search structure properties of the B-Tree. We analyze the behavior of the Search-Butterfly when the following operations are performed: arbitrary searches, random searches, and random searches, insertions, and deletions. We also provide lower bounds that show that the results are within a factor of O(\log n) of optimal where n is the number of keys in the structure. When the searches are random, the results are within a constant factor of optimal. Many of the proofs are derived from closely related results for packet routing. Others are of independent interest, most notably a method of adding queues to any network belonging to a large class of queuing networks with non-Markovian routing in a manner that allows us to bound the delay experienced by packets in the augmented network. Received October 1996, and in final form July 1997.     

Õ(Congestion + Dilation) Hot-Potato Routing on Leveled Networks

We study packet routing problems, in which we are given a set of N packets which will be sent on preselected paths with congestion C and dilation D. For store-and-forward routing, in which nodes have buffers for packets in transit, there are routing algorithms with a performance that matches the lower bound Ω(C+D). Motivated from optical networks, we study hot-potato routing in which the nodes are bufferless. Due to the lack of buffers, in hot-potato routing the packets may be delayed more than in store-and-forward routing. An interesting question is how much is the performance of routing algorithms affected by the absence of buffers. Here, we answer this question for the class of leveled networks, in which the nodes are partitioned into L+1 distinct levels. We present a randomized hot-potato routing algorithm for leveled networks, which routes the packets in O((C + L) ln⁹ (LN)) time with high probability. For routing problems with dilation Ω(L), and where N is a polynonial in L, this bound is within polylogarithmic factors of the lower bound Ω(C+L). Our algorithm demonstrates that for such routing problems the benefit from using buffers is no more than polylogarithmic; thus, hot-potato routing is an efficient way to route packets in leveled networks. In hot-potato routing, due to the lack of buffers, the packets may not be able to remain on their preselected paths during the course of routing (while in store-and-forward routing the packets remain on their preselected paths). However, in our algorithm the actual path that each packet follows contains its original preselected path; thus the lower bound Ω(C+L) is also a lower bound for the new paths. Our algorithm is distributed, that is, routing decisions are taken locally at each node while packets are routed in the network. To our knowledge, this is the first hot-potato algorithm designed and analyzed, in terms of congestion and dilation, for leveled networks.     

Potential Function Analysis of Greedy Hot-Potato Routing

We study the problem of packet routing in synchronous networks. We put forward a notion of greedy hot-potato routing algorithms and devise tech- niques for analyzing such algorithms. A greedy hot-potato routing algorithm is one where: • The processors have no buffer space for storing delayed packets. Therefore, each packet must leave any intermediate processor at the step following its arrival. • Packets always advance toward their destination if they can. Namely, a packet must leave its current intermediate node via a link which takes it closer to its destination, unless all these links are taken by other packets. Moreover, in this case all these other packets must advance toward their destinations. We use potential function analysis to obtain an upper bound of O(n k ^1/2 ) on the running time of a wide class of algorithms in the two-dimensional n × n mesh, for routing problems with a total of k packets. The same techniques can be generalized to obtain an upper bound of O(exp(d) n ^d-1 k ^1/d ) on the running time of a wide class of algorithms in the d -dimensional n ^d mesh, for routing problems with a total of k packets. Received December 1993, and in final form March 1997.     

An optimal time bound for oblivious routing

The problem of routing data packets in a constant-degree network is considered. A routing scheme is calledoblivious if the route taken by each packet is uniquely determined by its source and destination. The time required for the oblivious routing ofn packets onn processors is known to be Θ(√n). It is demonstrated that the presence of extra processors can expedite oblivious routing. More specifically, the time required for the oblivious routing ofn packets onp processors is Θ(n/√p + logn).     

An optimal time bound for oblivious routing

The problem of routing data packets in a constant-degree network is considered. A routing scheme is calledoblivious if the route taken by each packet is uniquely determined by its source and destination. The time required for the oblivious routing ofn packets onn processors is known to be (n). It is demonstrated that the presence of extra processors can expedite oblivious routing. More specifically, the time required for the oblivious routing ofn packets onp processors is (n/p + logn).     

A parallel implementation of Strassen’s matrix multiplication algorithm for wormhole-routed all-port 2D torus networks

A new parallel implementation of Strassen’s matrix multiplication algorithm is proposed for massively parallel supercomputers with 2D, all-port torus interconnection networks. The proposed algorithm employs a special conflict-free routing pattern for better scalability and is able to yield a performance rate very close to the theoretical bound for many practical network and matrix sizes. It effectively scales up to very large networks typically containing hundreds-of-thousands processors where petaflop or exaflop processing rates are sought.     

Networks on which hot-potato routing does not livelock

Summary. Hot-potato routing is a form of synchronous routing which makes no use of buffers at intermediate nodes. Packets must move at every time step, until they reach their destination. If contention prevents a packet from taking its preferred outgoing edge, it is deflected on a different edge. Two simple design principles for hot potato routing algorithms are minimum advance, that advances at least one packet towards its destination from every nonempty node (and possibly deflects all other packets), and maximum advance, that advances the maximum possible number of packets. Livelock is a situation in which packets keep moving indefinitely in the network without any packet ever reaching its destination. It is known that even maximum advance algorithms might livelock on some networks. We show that minimum advance algorithms never livelock on tree networks, and that maximum advance algorithms never livelock on triangulated networks. Received: March 1999 / Accepted: August 1999     

Multi-log2N交换网络的性能分析模型及控制算法

高速多平面交换网络解决了其内部冲突问题,但需要相应的路由控制算法的辅助,否则,内部冲突不能彻底解决.这是因为包在输入级路由平面的选择不够恰当,容易导致路由冲突的产生.因此,根据冲突链路集的思想,给出一种Multi-log₂N交换网络的控制算法.该算法控制分组在路由平面间的选择,不仅能够适用于RNB和SNB,还能实现单播和多播的控制,保障Multi-log₂N完全实现无阻塞.另一方面,Multi-log₂N消除了内部的链路冲突,提高了交换速率,但对其交换性能缺乏系统的理论分析.给出一种基于嵌入式马尔可夫链的分析模型,对Multi-log₂N网络中队列的使用及分组在队列中的平均等待时间、平均队长等相关性能指标进行了系统的分析,为基于Multi-log₂N的光交换节点的设计提供了良好的理论依据.     

Packet synchronization for synchronous optical deflection-routedinterconnection networks

Deflection routing resolves output port contention in packet switched multiprocessor interconnection networks by granting the preferred port to the highest priority packet and directing contending packets out other ports. When combined with optical links and switches, deflection routing yields simple bufferless nodes, high bit rates, scalable throughput, and low latency. We discuss the problem of packet synchronization in synchronous optical deflection networks with nodes distributed across boards, racks, and cabinets. Synchronous operation is feasible due to very predictable optical propagation delays. A routing control processor at each node examines arriving packets and assigns them to output ports. Packets arriving on different input ports must be bit wise aligned; there are no elastic buffers to correct for mismatched arrivals. “Time of flight” packet synchronization is done by balancing link delays during network design. Using a directed graph network model, we formulate a constrained minimization problem for minimizing link delays subject to synchronization and packaging constraints. We demonstrate our method on a ShuffleNet graph, and show modifications to handle multiple packet sizes and latency critical paths     

Minimal Adaptive Routing on the Mesh with Bounded Queue Size

An adaptive routing algorithm is one in which the path a packet takes from its source to its destination may depend on other packets it encounters. Such algorithms potentially avoid network bottlenecks by routing packets around “hot spots.” Minimal adaptive routing algorithms have the additional advantage that the path each packet takes is a shortest one. For a large class of minimal adaptive routing algorithms, we present an Ω(n²/k²) bound on the worst case time to route a static permutation of packets on ann×nmesh or torus with nodes that can hold up tok≥ 1 packets each. This is the first nontrivial lower bound on adaptive routing algorithms. The argument extends to more general routing problems, such as theh–hrouting problem. It also extends to a large class of dimension order routing algorithms, yielding an Ω(n²/k) time bound. To complement these lower bounds, we present two upper bounds. One is anO(n²/k+n) time dimension order routing algorithm that matches the lower bound. The other is the first instance of a minimal adaptive routing algorithm that achievesO(n) time with constant sized queues per node. We point out why the latter algorithm is outside the model of our lower bounds.     

Optimal opportunistic routing and network coding for bidirectional wireless flows

There is growing interest in recent years in routing methods for wireless networks that leverage the broadcast nature of the wireless medium and the ability of nodes to overhear their neighbors’ transmissions. Such methods include opportunistic routing (OR), which generally choose the next hop on a routing path only after the outcome of the previous transmission is known; and wireless network coding (NC), which linearly combines packets from different flows coexisting in the network. In this paper, we study the potential benefits of forwarding schemes that combine elements from both the OR and NC approaches, when traffic on a bidirectional unicast connection between two nodes is relayed by multiple common neighbors. We present a theoretically optimal scheme that provides a lower bound on the expected number of transmissions required to communicate a packet in both directions as a function of link error probabilities, and demonstrate that this bound can be up to 20% lower than with either OR or NC employed alone even in a small network. Using simulation, we further explore the control overhead in a direct implementation of the scheme with a simple coordination mechanism and show that the optimal bound can be closely approached for a wide range of link error rates.     

基于最近社交圈的社交时延容忍网络路由策略

无稳定拓扑使时延容忍网络(delay tolerant networks,DTN)路由协议主要通过增加冗余数据包副本提高路由性能.社交网络是DTN的一种典型应用场景,但由于其网络规模相对较大,当网络负载高时,通常的DTN路由不能有效控制数据包副本的数量,从而产生大量丢包导致性能下降.借鉴MANET网络中利用分簇结构控制网络冗余路由数据包的思想,通过分析社交网络中节点的移动模型,定义了在社交关系的约束下,聚合移动规律相近的节点构成最近社交圈的节点簇组成策略.提出了一种基于该分簇结构的分为簇外喷射、簇间转发和簇内传染3个阶段的社交时延网络路由协议.实验证明,这种基于最近社交圈分簇结构的路由能有效地控制冗余数据包副本的产生,并在高网络负载的情况下仍然能够达到较好的性能.     

Overhead reduction in a distributed path management system

CEAS (cross entropy ant system) is a distributed, robust and adaptive swarm intelligence system for path management in communication networks. This paper focuses on strategies for handling the overhead in terms of processing cycles, memory storage, and number of management packets (ants) generated by CEAS when the state of the network changes.Pheromone sharing is introduced such that virtual connections with common sub-paths are sharing information and cooperate in the path finding when the paths have the same destination and the same objective function. The sharing of information reduces the required memory in each node significantly on the expense of an increase in the size of the management packets. However, the packets are still rather small. The cooperation also leads to an improvement in convergence rates which again results in reduced transmission overhead.A rate adjustment scheme is also proposed. The scheme is self-tuned and detects state changes implicitly and sets packet rates accordingly by monitoring parameter values in the management system. Rate adaptation can be done both in the network nodes and at the end-points of a virtual path. Compared to a fixed rate strategy the self-tuned strategies show a significant reduction in the number of packets generated, while maintaining the same data packet delay and service availability level. The self-tuned rate adjustment in the network nodes provides fast restoration with short path detection times, which ensures high service availability. The self-tuned ant rate in the end-points avoids flooding the network with management packets when these are not required.The performance and overhead of CEAS are compared to those of the link state routing currently in use in today’s networks. The results show that CEAS outperforms link state routing both with respect to performance and overhead when the network experiences transient link failures, while the opposite is the case with long lived failures.     

Speeding up high-speed protocol processors

Many network technologies aim to exploit the bandwidth of high-speed links, which now achieve data transfer rates up to several terabits per second. As packet interarrival times shrink to a few tens of nanoseconds, network systems must address a transmission-processing gap by providing extremely fast data paths as well as high-performance subsystems to implement such functions as protocol processing, memory management, and scheduling. Today, network processors are an important class of embedded processors, used all across the network systems space-from personal to local and wide area networks. Network processor architectures focus on exploiting parallelism to achieve high performance. They usually employ conventional architectural concepts to accelerate the processing required to switch packets between different protocol stacks. The architectures support the mechanisms that network protocols implement in a specific stack by providing efficient data paths and by executing many intelligent network or more homogeneous links - for example, a set of Ethernet links. Although network processors can also handle packets concurrently from different protocol stacks, we describe only single-stack processing here. However, the arguments and results extend to a multistack environment.     

Packet routing on grids of processors

The problem of routing packets onn ₁×...×n _r mesh-connected arrays or grids of processors is studied. The focus of this paper is on permutation routing where each processor contains exactly one packet initially and finally. A slight modification of permutation routing called balanced routing is also discussed. For two-dimensional grids a determinisitc routing algorithm is given forn×n meshes where each processor has a buffer of size f(n) < n. It needs 2n + O(n/f(n)) steps on grids without wrap-arounds. Hence, it is asymptoticaliy nearly optimal, and as good as randomized algorithms routing data only with high probability. Furthermore, it is demonstrated that onr-dimensional cubes of processors permutation routing can be performed asymptotically by (2r–2)n steps, which is faster than the running times of so-far known randomized algorithms and of deterministic algorithms.Partially supported by Siemens AG, München.     

Spray and forward:Efficient routing based on the Markov location prediction model for DTNs

Typical delay tolerant networks(DTNs)often suffer from long and variable delays,frequent connectivity disruptions,and high bit error rates.In DTNs,the design of an efficient routing algorithm is one of the key issues.The existing methods improve the accessibility probability of the data transmission by transmitting many copies of the packet to the network,but they may cause a high network overhead.To address the tradeoff between a successful delivery ratio and the network overhead,we propose a DTN routing algorithm based on the Markov location prediction model,called the spray and forward routing algorithm(SFR).Based on historical information of the nodes,the algorithm uses the second-order Markov forecasting mechanism to predict the location of the destination node,and then forwards the data by greedy routing,which reduces the copies of packets by spraying the packets in a particular direction.In contrast to a fixed mode where a successful-delivery ratio and routing overhead are contradictory,a hybrid strategy with multi-copy forwarding is able to reduce the copies of the packets efficiently and at the same time maintain an acceptable successful-delivery ratio.The simulation results show that the proposed SFR is efficient enough to provide better network performance than the spray and wait routing algorithm,in scenarios with sparse node density and fast mobility of the nodes.     

Work-efficient routing algorithms for rearrangeable symmetricalnetworks

The work performed by a parallel algorithm is the product of its running time and the number of processors it requires. This paper presents work-efficient (or cost-optimal) routing algorithms to determine the switch settings for realizing permutations on rearrangeable symmetrical networks such as Benes and the reduced Ω _NΩ_N^-1. These networks have 2n-1 stages with N=2ⁿ inputs/outputs, each stage consisting of N/2 crossbar switches of size (2×2). Previously known parallel routing algorithms for a rearrangeable network with N inputs determine the states of all switches recursively in O(n) iterations using N processors. Each iteration determines the switch settings of at most two stages of the network and requires at least O(n) time on a computer of N processors, regardless of the type of its interconnection network. Hence, the work of any previously known parallel routing algorithm equals at least O(Nn²) for setting up all the switches of a rearrangeable network. The new routing algorithms run on a computer of p processors, 1⩽p⩽N/n, and perform work O(Nn). Moreover, because the range of p is large, the new routing algorithms do not have to be changed in case some processors become faulty     

基于OPNET的低轨卫星网络仿真平台

为研究适用于低轨卫星网络的协议与算法,在OPNET中搭建仿真平台,包括卫星网络拓扑的设计、节点模型、进程模型以及链路模型的建立。该平台能模拟低轨卫星网络路由表的建立和数据包选路等过程。依据卫星网络运动的规律性,采用拓扑快照方式的静态路由策略,对低轨卫星网络进行路由仿真,验证了平台的有效性。     

Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links

Summary.  We consider agreement and leader election on asynchronous complete networks when the processors are reliable, but some of the channels are subject to failure. Fischer, Lynch, and Paterson have already shown that no deterministic algorithm can solve the agreement problem on asynchronous networks if any processor fails during the execution of the algorithm. Therefore, we consider only channel failures. The type of channel failure we consider in this paper is Byzantine failure, that is, channels fail by altering messages, sending false information, forging messages, losing messages at will, and so on. There are no restrictions on the behavior of a faulty channel. Therefore, a faulty channel may act as an adversary who forges messages on purpose to prevent the successful completion of the algorithm. Because we assume an asynchronous network, the channel delays are arbitrary. Thus, the faulty channels may not be detectable unless, for example, the faulty channels cause garbage to be sent. We present the first known agreement and leader election algorithm for asynchronous complete networks in which the processors are reliable but some channels may be Byzantine faulty. The algorithm can tolerate up to [n−22] faulty channels, where n is the number of processors in the network. We show that the bound on the number of faulty channels is optimal. When the processors terminate their corresponding algorithms, all the processors in the network will have the same correct vector, where the vector contains the private values of all the processors. Received: May 1994/Accepted: July 1995     

Permutation routing in double-loop networks: design and empirical evaluation

A double-loop network is an undirected graph whose nodes are integers 0,1,…,n−1 and each node u is adjacent to four nodes u±h₁(mod>n), u±h₂(mod>n), where 0<h₁<h₂<n/2. There are initially n packets, one at each of the n nodes. The packet at node u is destined to node π(u), where the mapping uπ(u) is a permutation. The aim is to minimize the number of routing steps to route all the packets to their destinations. If ℓ is the tight lower bound for this number, then the best known permutation routing algorithm takes, on average, 1.98ℓ routing steps (and 2ℓ routing steps in the worst-case).Because the worst-case complexity cannot be improved, we design four new static permutation routing algorithms with gradually improved average-case performances, which are 1.37ℓ, 1.35ℓ, 1.18ℓ, and 1.12ℓ. Thus, the best of these algorithms exceeds the optimal routing by at most 12% on average.To support our algorithm design we develop a program which simulates permutation routing in a network according to the given topology, routing model as well as communication pattern and measure several quality criteria. We have tested our algorithms on a large number of double-loop networks and permutations (randomly generated and standard).