Finding all hops shortest paths

In this letter, we introduce and investigate a new problem referred to as the All Hops Shortest Paths (AHSP) problem. The AHSP problem involves selecting, for all hop counts, the shortest paths from a given source to any other node in a network. We derive a tight lower bound on the worst-case computational complexities of the optimal comparison-based solutions to AHSP.     

DT-MRI fiber tracking: a shortest paths approach

We derive a new fiber tracking algorithm for DT-MRI that parts with the locally “greedy” paradigm intrinsic to conventional tracking algorithms. We demonstrate the ability to precisely reconstruct a diverse range of fiber trajectories in authentic and computer-generated DT-MRI data, for which well-known conventional tracking algorithms are shown to fail. Our approach is to pose fiber tracking as a problem in computing shortest paths in a weighted digraph. Voxels serve as vertices, and edges are included between neighboring voxels. We assign probabilities (weights) to edges using a Bayesian framework. Higher probabilities are assigned to edges that are aligned with fiber trajectories in their close proximity. We compute optimal paths of maximum probability using computationally scalable shortest path algorithms. The salient features of our approach are: global optimality—unlike conventional tracking algorithms, local errors do not accumulate and one “wrong-turn” does not spell disaster; a target point is specified a priori; precise reconstruction is demonstrated for extremely low signal-to-noise ratio; impartiality to which of two endpoints is used as a seed; and, faster computation times than conventional all-paths tracking. We can use our new tracking algorithm in either a single-path tracking mode (deterministic tracking) or an all-paths tracking mode (probabilistic tracking).      

Computing shortest paths for any number of hops

In this paper, we introduce and investigate a "new" path optimization problem that we denote the all hops optimal path (AHOP) problem. The problem involves identifying, for all hop counts, the optimal, i.e., minimum weight, path(s) between a given source and destination(s). The AHOP problem arises naturally in the context of quality-of-service (QoS) routing in networks, where routes (paths) need to be computed that provide services guarantees, e.g., delay or bandwidth, at the minimum possible "cost" (amount of resources required) to the network. Because service guarantees are typically provided through some form of resource allocation on the path (links) computed for a new request, the hop count, which captures the number of links over which resources are allocated, is a commonly used cost measure. As a result, a standard approach for determining the cheapest path available that meets a desired level of service guarantees is to compute a minimum hop shortest (optimal) path. Furthermore, for efficiency purposes, it is desirable to precompute such optimal minimum hop paths for all possible service requests. Providing this information gives rise to solving the AHOP problem. The paper's contributions are to investigate the computational complexity of solving the AHOP problem for two of the most prevalent cost functions (path weights) in networks, namely, additive and bottleneck weights. In particular, we establish that a solution based on the Bellman-Ford algorithm is optimal for additive weights, but show that this does not hold for bottleneck weights for which a lower complexity solution exists.     

Alternative paths to broadband deployment

Widespread deployment of broadband technology may well be the next wave of the computer and communications revolutions. No one knows what technology, business plan, marketing idea, or combination of such ideas will best serve customers or succeed in the marketplace. As a result, government policy should not favor or disfavor any type of plan to provide these services. The computer industry provides a great model for widespread deployment of advanced technology with the government acting as a referee to ensure competitive service provision. In this way customers will get to decide which services they desire and are worth their support     

Constrained shortest link-disjoint paths selection: a network programming based approach

Given a graph G with each link in the graph associated with two positive weights, cost and delay, we consider the problem of selecting a set of k link-disjoint paths from a node s to another node t such that the total cost of these paths is minimum and that the total delay of these paths is not greater than a specified bound. This problem, to be called the constrained shortest link-disjoint path (CSDP(k)) problem, can be formulated as an integer linear programming (ILP) problem. Relaxing the integrality constraints results in an upper bounded linear programming problem. We first show that the integer relaxations of the CSDP(k) problem and a generalized version of this problem to be called the generalized CSDP (GCSDP (k)) problem (in which each path is required to satisfy a specified bound on its delay) both have the same optimal objective value. In view of this, we focus our work on the relaxed form of the CSDP(k) problem (RELAX-CSDP(k)). We study RELAX-CSDP(k) from the primal perspective using the revised simplex method of linear programming. We discuss different issues such as formulas to identify entering and leaving variables, anti-cycling strategy, computational time complexity etc., related to an efficient implementation of our approach. We show how to extract from an optimal solution to RELAX-CSDP(k) a set of k link-disjoint s-t paths which is an approximate solution to the original CSDP(k) problem. We also derive bounds on the quality of this solution with respect to the optimum. We present simulation results that demonstrate that our algorithm is faster than currently available approaches. Our simulation results also indicate that in most cases the individual delays of the paths produced starting from RELAX-CSDP(k) do not deviate in a significant way from the individual path delay requirements of the GCSDP(k) problem.     

An efficient multiple shortest augmenting paths algorithm for constructing high performance VLSI subarray

Reconfiguring a high-performance subarray of a VLSI array with faults is to construct a maximum target array with the minimum number of long interconnects, which can reduce communication costs, capacitance and dynamic energy dissipation. An existing work proved that the high performance VLSI subarray can be constructed in polynomial time using network flow algorithm. However, because of the disadvantage of the previous network model and the low-performing of standard network flow algorithms for reconfiguration, the efficiency of these algorithms is poor for constructing the high performance VLSI subarray. In this paper, we present an efficient multiple shortest augmenting paths algorithm for rapidly constructing high performance VLSI array. Firstly, we proposed an efficient data structure to construct the network model of the VLSI array with faults, which can dramatically reduce the size of the model compared with previous algorithm. Secondly, a multiple shortest augmenting path algorithm based on the new data structure is proposed, which can significant reduce the running time. Finally, we conduct solid experiments to highlight the efficiency of the proposed method in terms of the running time compared to the standard network flow algorithms. The experimental results show that on a 64 × 64 host array with 0.1% faults, the size of the network model can be reduced by about 50% and the average improvements in running time is up to 85.10% compared with four standard network flow algorithms.     

F-TPR: fine two-phase IP routing scheme over shortest paths for hose model

This letter proposes an IP-based finely-distributed routing scheme based on two-phase routing (TPR) over shortest paths for the hose model. It is called the fine-TPR (F-TPR) scheme. Compared to the original TPR, F-TPR distributes traffic from a source node to intermediate nodes more finely, where the distribution ratio is determined for each source-destination pair. To determine an optimum set of the distribution ratios, we successfully formulate our problem as a quadratic constraint programming (QCP) formulation that can be solved by using a mathematical programming solver. Numerical results show that F-TPR greatly outperforms TPR and its performance approaches that provided by the sophisticated traffic engineering (TE) scheme of multi-protocol label switching (MPLS-TE).     

An efficient pursuit automata approach for estimating stable all‐pairs shortest paths in stochastic network environments

This paper presents a new solution to the dynamic all‐pairs shortest‐path routing problem using a fast‐converging pursuit automata learning approach. The particular instance of the problem that we have investigated concerns finding the all‐pairs shortest paths in a stochastic graph, where there are continuous probabilistically based updates in edge‐weights. We present the details of the algorithm with an illustrative example. The algorithm can be used to find the all‐pairs shortest paths for the ‘statistical’ average graph, and the solution converges irrespective of whether there are new changes in edge‐weights or not. On the other hand, the existing popular algorithms will fail to exhibit such a behavior and would recalculate the affected all‐pairs shortest paths after each edge‐weight update. There are two important contributions of the proposed algorithm. The first contribution is that not all the edges in a stochastic graph are probed and, even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the final list involving all pairs of nodes in the graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. The second contribution is designing a data structure, the elements of which represent the probability that a particular edge in the graph lies in the shortest path between a pair of nodes in the graph. All the algorithms were tested in environments where edge‐weights change stochastically, and where the graph topologies undergo multiple simultaneous edge‐weight updates. Its superiority in terms of the average number of processed nodes, scanned edges and the time per update operation, when compared with the existing algorithms, was experimentally established. Copyright © 2008 John Wiley & Sons, Ltd.     

Use of n-cubes in the design of logic circuits

A method of visualising n-cubes is presented, which may make n-cubes more convenient in logic design than the more usual Karnaugh maps.     

Mapping a class of neural networks on k-ary n-cubes

In this paper we propose a scheme for mapping two important artificial neural network (ANN) models on the popular k-ary n-cube parallel architectures (KNCs). The scheme is based on generalizing the mapping of a bipartite graph onto the KNC architecture and thus can be adapted to any model whose computations can be represented by a bipartite task graph. Our approach is the first to adjust the granularity of parallelism so as to achieve the best possible performance based on properties of the computational model and the target architecture. We first introduce a methodology for optimal implementation of multi-layer feedforward artificial neural networks (FFANNs) trained with the backpropagation algorithm on KNCs. We prove that our mapping methodology is time-optimal and that it provides for maximum processor utilization regardless of the structure of the FFANN. We show that the same methodology can be utilized for efficient mapping of Radial Basis Function neural networks (RBFs) on KNCs. This revised version was published online in June 2006 with corrections to the Cover Date.     

LSRP: local stabilization in shortest path routing

We formulate a notion of local stabilization, by which a system self-stabilizes in time proportional to the size of any perturbation that changes the network topology or the state of nodes. The notion implies that the part of the network involved in the stabilization includes at most the nodes whose distance from the perturbed nodes is proportional to the perturbation size. Also, we present LSRP, a protocol for local stabilization in shortest path routing. LSRP achieves local stabilization via two techniques. First, it layers system computation into three diffusing waves each having a different propagation speed, i.e., "stabilization wave" with the lowest speed, "containment wave" with intermediate speed, and "super-containment wave" with the highest speed. The containment wave contains the mistakenly initiated stabilization wave, the super-containment wave contains the mistakenly initiated containment wave, and the super-containment wave self-stabilizes itself locally. Second, LSRP avoids forming loops during stabilization, and it removes all transient loops within small constant time. To the best of our knowledge, LSRP is the first protocol that achieves local stabilization in shortest path routing.     

基于路径分解的关键路径求解方法

提出了一种求解关键路径的新方法,该方法基于路径分解的思想,对AOE网所有的路径进行分解,并利用多头单尾链表结构实现关键路径的求解。通过实例验证了算法的正确性。     

最短路程的运输问题及解法

针对最短路程的运输问题,建立了模型,研究了其解的最优性充分条件,提出了一种简捷、快速的求解方法,并给出了具体的求解步骤,最后用实例表明了解法的可操作性。     

Another adaptive distributed shortest path algorithm

The authors give a distributed algorithm to compute shortest paths in a network with changing topology. The authors analyze its behavior. The proof of correctness is discussed. It does not suffer from the routing table looping behavior associated with the Ford-Bellman distributed shortest path algorithm although it uses truly distributed processing. Its time and message complexities are evaluated. Comparisons with other methods are given     

Asymptotic optimality of shortest path routing algorithms

Many communication networks use adaptive shortest path routing. By this we mean that each network link is periodically assigned a length that depends on its congestion level during the preceding period, and all traffic generated between length updates is routed along a shortest path corresponding to the latest link lengths. We show that in certain situations, typical of networks involving a large number of small users and utilizing virtual circuits, this routing method performs optimally in an asymptotic sense. In other cases, shortest path routing can be far from optimal.     

Light paths in retinal vessel oxymetry

The oxygen utilization and, therefore, the metabolic state, of a distinctive area of the retina may be calculated from the diameter of the supplying artery and vein, the haemoglobin oxygenation, and the velocity of the blood. The first two parameters can be determined by imaging spectrometry at the patients ocular fundus. However, the reflected light emerging from a vessel followed different pathways through the ocular fundus layers and the vessel embedded in the retina. The contribution of the single pathways to the vessel reflection profile is investigated by a Monte Carlo simulation. Considering retinal vessels with diameters of 25-200 microm we found the reflection from a thin vessel to be determined by the single and double transmission of light at 560 nm. The backscattering from the blood column determines the reflectance in the case of a thick vessel. However, both components are in the same order of magnitude. This has to be considered in the calculation of the oxygen saturation of blood in retinal vessels from their reflection spectra.     

机器人避障中最短路径的算法研究及应用

基于机器人在平面区域运动的避障问题,通过单一障碍物路径长度设计算法,利用MATLAB软件进行分别计算,综合比较得出机器人从区域起点到达目标点的避障最短路径。     

Distributed multicast multichannel paths

Supporting multimedia applications in QoS-aware multicast deployment has become an important research dimension in recent years. Future communication networks will face an increase in traffic driven by multimedia applications with stringent requirements in the following important functions: (1) nodes and links used distributing, (2) packets duplication distributing, (3) QoS supporting, (4) multichannel routing. For improving these four functions, in this paper we propose a new polynomial time algorithm, named Nodes Links Distributed-Multicast Multichannel Routing (NLD-MMR), based on the Constraint-Based Routing (CBR) and Linear Programming (LP). The new algorithm by constructing Distributed Multicast Multichannel Paths (DMMCP) can distribute or compact both paths and traffic. Our simulation study shows that the proposed algorithm, as compared to other available algorithms, performs well and constructs a new generation of optimal paths with the best cost and efficiency.