Near-optimal message routing and broadcasting in faulty hypercubes

A distributed routing algorithm for faulty hypercubes is described. This algorithm uses a directed depth-first approach to find a path between the sender and receiver of a message whenever at least one non-faulty path exists. We show that, when an arbitrary number of elements of the hypercube can be faulty, the algorithm always routes messages using fewer than 2N hops, whereN is the number of nodes in the hypercube. This performance is shown to be within a factor of two of the optimal worst-case routing efficiency. Through foult simulations, we show that, even when up to half of the elements in the cube are faulty, complete the analysis, we prove that our algorithm is deadlock-free. Finally, we present two extensions of the algorithm. The first uses local storage to reduce the overhead of the algorithm while the second allows reliable broadcasting in the presence of an arbitrary number of faults.Supported in part by the National Science Foundation under Grant CCR-9010547.Supported in part by the National Science Foundation Instrumentation Grant CDA-8820627.     

An efficient construction of one-to-many node-disjoint paths in folded hypercubes

A folded hypercube is basically a hypercube with additional links augmented, where the additional links connect all pairs of nodes with longest distance in the hypercube. In an n$n$-dimensional folded hypercube, it has been shown that n+1$n+1$ node-disjoint paths from one source node to other n+1$n+1$ (mutually) distinct destination nodes, respectively, can be constructed in O(n⁴)$O\left(n^4\right)$ time so that their maximal length is not greater than ⌈n/2⌉+1$\lceil n/2\rceil +1$, where n+1$n+1$ is the connectivity and ⌈n/2⌉$\lceil n/2\rceil$ is the diameter. Besides, their maximal length is minimized in the worst case. In this paper, we further show that by minimizing the computations of minimal routing functions, these node-disjoint paths can be constructed in O(n³)$O\left(n^3\right)$ time, which is more efficient, and is hard to be reduced because it must take O(n³)$O\left(n^3\right)$ time to compute a minimal routing function by solving a corresponding maximum weighted bipartite matching problem with the best known algorithm.     

MANETs中分段式的节点不相交多路径QoS路由

随着多媒体应用日益普及,在移动自组网中提供QoS成为了一个重要的研究领域。提出一种移动自组网中分段式的节点不相交的多路径QoS路由协议。该协议将一条路径划分为多段,在每个段中建立满足多QoS约束的多条节点不相交路径,并在每个段中独立地进行路由维护。模拟研究表明该路由协议具有开销小和路径成功率高的特点。     

大规模定量传输的时间扩展网络K最短路径算法

大规模的军用物资调度,需要传输的物资远远超出保障网络实际传输能力的情况下,现有的Dijkstra算法、Floyd算法以及传统的网络K-最短路径算法,难以求解这类网络调度优化问题。在蚁群算法的基础上,设计了一种基于时间扩展的网络K-最短路径算法,满足网络传输一致性假设的前提下,求解大规模定量传输问题。最后给出面向任务的物流保障网络调度的应用实例,获得满意的网络调度优化方案。     

A Fault-Tolerant and Heuristic Routing Algorithm for Faulty Hypercubes

A fault-tolerant and heuristic routing algorithm for faulty hypercube systems is described.To improve the efficiency,the algorithm adopts a heuristic backtracking strategy and each node has an array to record its all neighbors‘ faulty link information to avoid unnecessary searching for the known faulty links.Furthermore,the faulty link information is dynamically accumulated and the technique of heuristically searching for optimal link is used.The algorithm routes messages through the minimum feasible path between the sender and receiver if at least one such path exists,and takes the optimal path with higher probability when faulty links exist in the faulty hypercube.     

Disjoint paths in hypercubes with prescribed origins and lengths

Given (i) any k vertices u ₁, u ₂, …, u _k (1≤k<n) in the n-cube Q _n , where (u ₁, u ₂), (u ₃, u ₄), …, (u _2m?1, u _2m ) (m≤? k\2 ?) are edges of the same dimension, (ii) any k positive integers a ₁, a ₂, …, a _k such that a ₁, a ₂, …, a _2m are odd and a _2m+1, …, a _k are even, with a ₁+a ₂+···+a _k =2 ⁿ , and (iii) k subsets W ₁, W ₂, …, W _k of V(Q _n ) with |W _i |≤n?k and if a _i =1, then u _i ¬∈W _i , for 1≤i≤k, we show that there exist k vertex-disjoint paths P ₍₁₎, P ₍₂₎, …, P _(k) in Q _n where P _(i) contains a _i vertices, its origin is u _i , and its terminus is in V(Q _n )/ W _i , for 1≤i≤k. We also prove a similar result which extends two well-known results of Havel, [I. Havel On hamilton circuits and spanning trees of hypercubes, ?asopis pro P?stování Matematiky, 109 (1984), pp. 135–152.] and Nebeský, [L. Nebeský Embedding m-quasistars into n-cubes, Czech. Math. J. 38 (1988), pp. 705–712].     

基于事件与能量感知的WMSNs节点不相交多路径算法

在无线传感器网络中建立从源节点到目标节点的多条不相交路径,提出了一种基于事件与能量感知的节点不相交多路径算法（ EEDMA）。建立了基于事件与能量感知的多路径模型,基于对事件类型和各路径中节点剩余能量的感知,为不同的事件类型的数据选择合适的路径进行传输。通过仿真结果验证：这种算法为实现异常事件提供了可靠、快速的传输路径,并且为平衡整个网络的能量消耗有重要意义。     

Fault-tolerant wormhole routing for hypercube networks

We present an adaptive fault-tolerant wormhole routing algorithm for hypercubes by using 3 virtual networks. The routing algorithm can tolerate at least n−1 faulty nodes and can route a message via a path of length no more than the shortest path plus four. Previous algorithms which achieve the same fault tolerant ability need 5 virtual networks. Simulation results are also given in this paper.     

A shortest path routing algorithm using Hopfield neural network with an improved energy function

A shortest path routing algorithm using the Hopfield neural network with a modified Lyapunov function is proposed. The modified version of the Lyapunov energy function for an optimal routing problem is proposed for determining routing order for a source and multiple destinations. The proposed energy function mainly prevents the solution path from having loops and partitions. Experiments are performed on 3000 networks of up to 50 nodes with randomly selected link costs. The performance of the proposed algorithm is compared with several conventional algorithms including Ali and Kamoun's, Park and Choi's, and Ahn and Ramakrishna's algorithms in terms of the route optimality and convergence rate. The results show that the proposed algorithm outperforms conventional methods in all cases of experiments. The proposed algorithm particularly shows significant improvements on the route optimality and convergence rate over conventional algorithms when the size of the network approaches 50 nodes.     

Many-to-many disjoint paths in faulty hypercubes

This paper considers the problem of many-to-many disjoint paths in the hypercube Q_n with f_v faulty vertices and f_e faulty edges, and obtains the following result. For any integer k with 1?k?n-1, any two sets S and T of k fault-free vertices in different parts, if f_v+f_e?n-k-1, then there exist k disjoint fault-free (S,T)-paths in Q_n which contains at least 2ⁿ-2f_v vertices. This result is optimal in the worst case.     

Dynamic shortest path problems: Hybrid routing policies considering network disruptions

Traffic network disruptions lead to significant increases in transportation costs. We consider networks in which a number of links are vulnerable to these disruptions leading to a significantly higher travel time on these links. For these vulnerable links, we consider known link disruption probabilities and knowledge of transition probabilities for recovering from or getting into a disruption. We develop a framework based on dynamic programming in which we formulate and evaluate different known online and offline routing policies. Next to this, we develop computation-time-efficient hybrid routing policies. To test the efficiency of the different routing policies, we develop a test bed of networks based on a number of characteristics and analyze the results in terms of routes, cost performance and calculation times. Our results show that a significant part of the cost reduction can be obtained by considering only a limited part of the network in detail. The performance of our proposed hybrid policy is only slightly worse than the optimal policy.     

基于累积竞争神经网络的多约束路由算法

针对无约束最优路径问题，提出累积竞争神经网络模型及其搜索算法，该算法具有高度并行性、能获得最优解、结构简单等特点．以QoS路由选择为例，将算法推广到多约束路由问题．实验结果表明，对于大多数多约束QoS问题，在与相应最短路径上节点数目相当的迭代次数内，该算法能找到问题的满意解甚至最优解．     

All-pairs shortest paths and the essential subgraph

The essential subgraph H of a weighted graph or digraphG contains an edge (v, w) if that edge is uniquely the least-cost path between its vertices. Let s denote the number of edges ofH. This paper presents an algorithm for solving all-pairs shortest paths onG that requires O(ns+n² logn) worst-case running time. In general the time is equivalent to that of solvingn single-source problems using only edges inH. For general models of random graphs and digraphsG, s=0(n logn) almost surely. The subgraphH is optimal in the sense that it is the smallest subgraph sufficient for solving shortest-path problems inG. Lower bounds on the largest-cost edge ofH and on the diameter ofH andG are obtained for general randomly weighted graphs. Experimental results produce some new conjectures about essential subgraphs and distances in graphs with uniform edge costs.Much of this research was carried out while the author was a Visiting Fellow at the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS).     

Improved algorithms for the k simple shortest paths and the replacement paths problems

Given a directed, non-negatively weighted graph G=(V,E) and s,t∈V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want the shortest path from s to t that avoids e, for every edge e in the original shortest path from s to t. The best known algorithm for the k simple shortest paths problem has a running of O(k(mn+n²logn)). For the replacement paths problem the best known result is the trivial one running in time O(mn+n²logn).In this paper we present two simple algorithms for the replacement paths problem and the k simple shortest paths problem in weighted directed graphs (using a solution of the All Pairs Shortest Paths problem). The running time of our algorithm for the replacement paths problem is O(mn+n²loglogn). For the k simple shortest paths we will perform O(k) iterations of the second simple shortest path (each in O(mn+n²loglogn) running time) using a useful property of Roditty and Zwick [L. Roditty, U. Zwick, Replacement paths and k simple shortest paths in unweighted directed graphs, in: Proc. of International Conference on Automata, Languages and Programming (ICALP), 2005, pp. 249-260]. These running times immediately improve the best known results for both problems over sparse graphs.Moreover, we prove that both the replacement paths and the k simple shortest paths (for constant k) problems are not harder than APSP (All Pairs Shortest Paths) in weighted directed graphs.     

An adaptive amoeba algorithm for constrained shortest paths

The constrained shortest path problem (CSP) is one of the basic network optimization problems, which plays an important part in real applications. In this paper, an adaptive amoeba algorithm is combined with the Lagrangian relaxation algorithm to solve the CSP problem. The proposed method is divided into two steps: (1) the adaptive amoeba algorithm is modified to solve the shortest path problem (SPP) in a directed network; (2) the modified adaptive amoeba algorithm is combined with the Lagrangian relaxation method to solve the CSP problem. In addition, the evolving processes of the adaptive amoeba model have been detailed in the paper. Two examples are used to illustrate the efficiency of the proposed method. The results show that the proposed method can deal with the CSP problem effectively.     

交换超立方体网络容错路由研究

为了研究交换超立方体网络容错路由问题,引入了相邻结点集合类的概念,提出了相邻结点集的求解公式。对于满足任意子连通性条件的交换超立方体网络,给出了基于相邻结点集合类的自适应容错路由算法及算法的步长上界。仿真实验结果表明算法是有效的。     

Fault-tolerant routing based on approximate directed routable probabilities for hypercubes

Recently, parallel processing systems have been studied very actively, and many topologies have been proposed. A hypercube is one of the most popular topologies for interconnection networks. In this paper, we propose two new fault-tolerant routing algorithms for hypercubes based on approximate directed routable probabilities. Probabilities represent the ability of routing toward any node located at a specific distance and are calculated by considering from which direction the message has been received. Each node chooses one of its neighbor nodes to forward the message by comparing the approximate directed routable probabilities. We also conducted a computer experiment to verify the effectiveness of our algorithms.     

一种新的交叉立方体最短路径路由算法

Efe提出的交叉立方体(crossed cube)是超立方体(hypercube)的一种变型.交叉立方体的某些性质优于超立方体,比如其直径几乎是超立方体的一半.Efe提出了时间复杂度为O(n2)的交叉立方体最短路径路由算法.Chang等人扩展了Efe的算法,时间复杂度为O(n),它在路由的每一步有更多条边作为最短路径可供寻路选择.但这些边并没有包含全部可进行最短路径路由的边.文中给出了结点各边可进行最短路径路由的充要条件,并在此基础上提出了一种时间复杂度为O(n2)的交叉立方体最短路径路由算法,它在路由的每一步都将所有的最短路径边作为候选边.理论分析和实例表明它可输出任意一条最短路径.