Generalized minimum information path routing strategy on scale-free networks

This paper presents a new routing strategy by introducing a tunable parameter into the minimum information path routing strategy we proposed previously. It is found that network transmission capacity can be considerably enhanced by adjusting the parameter with various allocations of node capability for packet delivery. Moreover, the proposed routing strategy provides a traffic load distribution which can better match the allocation of node capability than that of traditional efficient routing strategies, leading to a network with improved transmission performance. This routing strategy, without deviating from the shortest-path routing strategy in the length of paths too much, produces improved performance indexes such as critical generating rate, average length of paths and average search information.

An efficient QoS routing algorithm for multi-constrained path selection

An efficient QoS routing algorithm was proposed for multiple constrained path selection. Making use of efficient pruning policy, the algorithm reduces greatly the size of search space and the computing time. Although the proposed algorithm has exponential time complexity in the worst case, it can get the running results quickly in practical application. When the scale of network increases, the algorithm can efficiently control the size of search space by constraint conditions and prior queue. The results of simulation show that successful request ratio ( r ) of efficient algorithm for multi-constrained optimal path (EAMCOP) is better than that of heuristic algorithm for multi-constrained optimal path (H-MCOP), but average computing time ( t ) of EAMCOP is far less than that of H-MCOP. And it can be seen that the computing time of EAMCOP is only one fourth of that of H-MCOP in Advanced Research Projects Agency Network (ARPANet) topology.

Reliable Braided Multipath Routing with Network Coding for Underwater Sensor Networks

Owing to the long propagation delay and high error rate of acoustic channels, it is very challenging to provide reliable data transfer for underwater sensor networks. Moreover, network coding is proved to be an effective coding technique for throughput and robustness of networks. In this paper, we propose a Reliable Braided Multipath Routing with Network Coding for underwater sensor networks （RBMR-NC）. Disjoint multi-path algorithm is used to build independent actual paths, as called main paths. Some braided paths on each main path are built according to the braided multi-path algorithm, which are called logic paths. When a data packet is transmitted by these nodes, the nodes can employ network coding to encode packets coming from the same group in order to further reduce relativity among these packets, and enhance the probability of successful decoding at the sink node. Braided multi-path can make the main paths to be multiplexed to reduce the probability of long paths. This paper mainly employs successful delivery rate to evaluate RBMR-NC model with theoretical analysis and simulation methods. The results indicate that the proposed RBMR-NC protocol is valuable to enhance network reliability and to reduce system redundancy.

Novel multi-path routing scheme for UWB Ad hoc network

The routing protocols play an important role for ad hoc networks performance.As some problems with DSR,SMR,and AMR protocols were analyzed,a new routing protocol suitable for UWB Ad hoc networks was proposed in this paper.The new routing protocol utilize an act of orientation of UWB and tries to get sufficient route information and decrease the network load caused by route discovery at the same time.Simulation results show that the routing load of the new protocol is lower and throughput is higher than that of DSR.While the node’s mobility increases,these advantages become more obvious.

MRBCH: A Multi-Path Routing Protocol Based on Credible Cluster Heads for Wireless Sensor Networks

Wireless sensor networks are widely used for its flexibility, but they also suffer from problems like limited capacity, large node number and vulnerability to security threats. In this paper, we propose a multi-path routing protocol based on the credible cluster heads. The protocol chooses nodes with more energy remained as cluster heads at the cluster head choosing phase, and then authenticates them by the neighbor cluster heads. Using trust mechanisms it creates the credit value, and based on the credit value the multi-path cluster head routing can finally be found. The credit value is created and exchanged among the cluster heads only. Theoretical analysis combined with simulation results demonstrate that this protocol can save the resource, prolong the lifetime, and ensure the security and performance of the network.

Multi-Path Routing and Resource Allocation in Active Network

An algorithm of traffic distribution called active multi-path routing (AMR)in active network is proposed. AMR adopts multi-path routing and applies nonlinear optimizeapproximate method to distribute network traffic among multiple paths. It is combined to bandwidthresource allocation and the congestion restraint mechanism to avoid congestion happening and worsen.So network performance can be improved greatly. The frame of AMR includes adaptive trafficallocation model, the conception of supply bandwidth and its' allocation model, the principle ofcongestion restraint and its' model, and the implement of AMR based on multi-agents system in activenetwork. Through simulations, AMR has distinct effects on network performance. The results show AMRisa valid traffic regulation algorithm.

Shortest Path Routing Algorithm Based on Chaotic Neural Network

A shortest path routing algorithm based on transient chaotic neural network is proposed in this paper. Gam-pared with previous models adopting Hopfield neural network, this algorithm has a higher ability to overcome the local minimum, and achieves a better performance. By introducing a special post-processing technique for the output matrixes, our algorithm can obtain an optimal solution with a high probability even for the paths that need more hops in large-size networks.

Dynamic Routing and Wavelength Assignment for Multi-Lightpath Demands

In wavelength division multiplexing (WDM) networks without wavelengthconversion functionality, we convert the dynamic routing and wavelength assignment problem formulti-lightpath demands to the edge-disjoint paths problem, and propose a new algorithm. Thecomputer simulations show that the proposed algorithm has better blocking probability performancethan a sequential algorithm, which first separates a multi-lightpath demand into mutilplesingle-lightpath demands, then uses the fixed-alternate routing-first fit wavelength assignment(AR-FF) algorithm for each single-lightpath demand.

MSDM: Maximally Spatial Disjoint Multipath Routing Protocol for MANET

Mobile Ad-hoc Network (MANET) consists of mobile nodes that are connected via very dynamic multi-hop channels. Routing in MANET is a challenging task that has received great attention from researchers. In this paper we present Maximally Spatial Disjoint Multipath routing protocol (MSDM) which is a modification of AOMDV protocol. MSDM finds paths which are spatially separated and maximally disjointed. We think that sending various packets over spatially disjointed paths reduces the probability of collision occurrence and allows concurrent transmission over the set of different selected paths. Performance comparison of MSDM and AOMDV using GloMoSim simulator shows that MSDM is able to achieve a considerable improvement regarding some performance metrics such as delay, routing packets overhead, and network throughput.

SOPA:Source Routing Based Packet-Level Multi-Path Routing in Data Center Networks

Many ＂rich - connected＂ topologies with multiple parallel paths between smwers have been proposed for data center networks recently to provide high bisection bandwidth, but it re mains challenging to fully utilize the high network capacity by appropriate multi- path routing algorithms. As flow-level path splitting may lead to trafl＇ic imbalance between paths due to flow- size difference, packet-level path splitting attracts more attention lately, which spreads packets from flows into multiple available paths and significantly improves link utilizations. However, it may cause packet reordering, confusing the TCP congestion control algorithm and lowering the throughput of flows. In this paper, we design a novel packetlevel multi-path routing scheme called SOPA, which leverag- es OpenFlow to perform packet-level path splitting in a round- robin fashion, and hence significantly mitigates the packet reordering problem and improves the network throughput. Moreover, SOPA leverages the topological feature of data center networks to encode a very small number of switches along the path into the packet header, resulting in very light overhead. Compared with random packet spraying （RPS）, Hedera and equal-cost multi-path routing （ECMP）, our simulations demonstrate that SOPA achieves 29.87%, 50.41% and 77.74% higher network throughput respectively under permutation workload, and reduces average data transfer completion time by 53.65%, 343.31% and 348.25% respectively under production workload.

An Investigation on the Effect of Migration Strategy on Parallel GA-Based Shortest Path Routing Algorithm

Genetic algorithm (GA) is one of the alternative approaches for solving the shortest path routing problem. In previous work, we have developed a coarse-grained parallel GA-based shortest path routing algorithm. With parallel GA, there is a GA operator called migration, where a chromosome is taken from one sub-population to replace a chromosome in another sub-population. Which chromosome to be taken and replaced is subjected to the migration strategy used. There are four different migration strategies that can be employed: best replace worst, best replace random, random replace worst, and random replace random. In this paper, we are going to evaluate the effect of different migration strategies on the parallel GA-based routing algorithm that has been developed in the previous work. Theoretically, the migration strategy best replace worst should perform better than the other strategies. However, result from simulation shows that even though the migration strategy best replace worst performs better most of the time, there are situations when one of the other strategies can perform just as well, or sometimes better.

PERFORMANCE ANALYSIS OF MINIMAL PATH FAULT TOLERANT ROUTING IN NOC

Occurrence of faults in Network on Chip(NoC) is inevitable as the feature size is con-tinuously decreasing and processing elements are increasing in numbers.Faults can be revocable if it is transient.Transient fault may occur inside router,or in the core or in communication wires.Examples of transient faults are overflow of buffers in router,clock skew,cross talk,etc..Revocation of transient faults can be done by retransmission of faulty packets using oblivious or adaptive routing algorithms.Irrevocable faults causes non-functionality of segment and mainly occurs during fabrication process.NoC reliability increases with the efficient routing algorithms,which can handle the maximum faults without deadlock in network.As transient faults are temporary and can be easily revoked using re-transmission of packet,permanent faults require efficient routing to route the packet by bypassing the nonfunctional segments.Thus,our focus is on the analysis of adaptive minimal path fault tolerant routing to handle the permanent faults.Comparative analysis between partial adaptive fault tolerance routing West-First,North-Last,Negative-First,Odd Even,and Minimal path Fault Tolerant routing(MinFT) algorithms with the nodes and links failure is performed using NoC Interconnect RoutinG and Application Modeling simulator(NIRGAM) for the 2D Mesh topology.Result suggests that MinFT ensures data transmission under worst conditions as compared to other adaptive routing algorithms.

An Adaptive Routing Algorithm for Integrated Information Networks

The integrated information network is a large capacity information network that integrates various communication platforms on the ground, at sea, in the air and in the deep air through the inter-satellite and satellite-ground links to acquire information accurately, process it quickly, and transmit it efficiently. The satellite communication, as an important part of integrated information networks, is one of main approaches to acquire, process and distribute communication information and resources. In this paper, based on current researches of the satellite communication network, we put forward a 3-layer satellite communication network model based on the Software Defined Network (SDN). Meanwhile, to improve current routing policies of the Low Earth Orbit (LEO) satellite communication network, we put forward an Adaptive Routing Algorithm (ARA) to sustain the shortest satellite communication link. Experiment results show that the proposed method can effectively reduce link distance and communication delay, and realize adaptive path planning.

Traffic Dataset and Dynamic Routing Algorithm in Traffic Simulation

The purpose of this research is to create a simulated environment for teaching algorithms,big data processing,and machine learning.The environment is similar to Google Maps,with the capacity of finding the fastest path between two points in dynamic traffic situations.However,the system is significantly simplified for educational purposes.Students can choose different traffic patterns and program a car to navigate through the traffic dynamically based on the changing traffic.The environments used in the project are Visual IoT/Robotics Programming Language Environment(VIPLE)and a traffic simulator developed in the Unity game engine.This paper focuses on creating realistic traffic data for the traffic simulator and implementing dynamic routing algorithms in VIPLE.The traffic data are generated from the recorded real traffic data published on the Arizona Maricopa County website.Based on the generated traffic data,VIPLE programs are developed to implement the traffic simulation with support for dynamic changing data.

Escape probability based routing for ad hoc networks

Routes in an ad hoc network may fail frequently because of node mobility. Stability therefore can be an important element in the design of routing protocols. The node escape probability is introduced to estimate the lifetime and stability of link between neighboring nodes and the escape probability based routing （EPBR） scheme to discover stable routes is proposed. Simulation results show that the EPBR can discover stable routes to reduce the number of route rediscovery, and is applicable for the situation that has highly dynamic network topology with broad area of communication.

ON THE FAULT-TOLERANT ROUTING IN DISTRIBUTED LOOP NETWORKS

Based on their "Theorem 2", an O(δ)-time algorithm of searching for the shortest path between each pair of nodes in a double loop network was proposed by K.Mukhopadyaya, et al.(1995). While, unfortunately, it will be proved that both "Theorem 2" and its proof are in error. A new and more faster O(△)-time, △≤δ, algorithm will be presented in this paper.

Backtracking Routing Mechanism for Improving Link Failure Recovery

Failure-insensitive routing is a good mechanism to avoid packet dropping and disconnection of forwarding when some links fail, but multiple failure links may bring routing loop for the mechanism. Backtracking routing algorithm based on inverse shortest path tree rooted at destination is presented. The feasible restoration routing is obtained through searching from the start of the failure link and tracing back to the leaves of the shortest path tree with the destination as the root. The packets are forwarded from the mounted point with smaller sequence to the mount point with bigger sequence to decrease the possible of loop in case of multi-failures. The simulations and analysis indicate that backtracking routing algorithm improves the network survivability especially for large network, at the cost of the computation complexity in the same order as failure insensitive routing.

Study on QOS Routing in Network Centric Warfare

The concept of network centric warfare （NCW） and the distributed equal-node network architecture in NCW are introduced in this paper. The data flow requirement model in NCW is presented. Based on synthetic analysis of network resource, the QOS （Quality of Service） parameters and their characters, the high requirement of real-time synchronization in NCW, the single QOS routing constraint, and the network latency between the detector and weapon control station, are presented. To take an example for 3-node brigade （regiment） level NCW demonstration platform, the algorithm of end-to-end network latency and path information in NCW are presented. The algorithm program based on Server/Client architecture is developed. The optimal path is the link whose latency between the detector and weapon control station is the smallest. This paper solves the key issue and satisfies the needs on network latency in NCW. The study results can be widely applied in the decision of the optimal path which is based on multiple service provision points.

Efficient Routing Protection Algorithm Based on Optimized Network Topology

Network failures are unavoidable and occur frequently.When the network fails,intra-domain routing protocols deploying on the Internet need to undergo a long convergence process.During this period,a large number of messages are discarded,which results in a decline in the user experience and severely affects the quality of service of Internet Service Providers(ISP).Therefore,improving the availability of intra-domain routing is a trending research question to be solved.Industry usually employs routing protection algorithms to improve intra-domain routing availability.However,existing routing protection schemes compute as many backup paths as possible to reduce message loss due to network failures,which increases the cost of the network and impedes the methods deployed in practice.To address the issues,this study proposes an efficient routing protection algorithm based on optimized network topology(ERPBONT).ERPBONT adopts the optimized network topology to calculate a backup path with the minimum path coincidence degree with the shortest path for all source purposes.Firstly,the backup path with the minimum path coincidence with the shortest path is described as an integer programming problem.Then the simulated annealing algorithm ERPBONT is used to find the optimal solution.Finally,the algorithm is tested on the simulated topology and the real topology.The experimental results show that ERPBONT effectively reduces the path coincidence between the shortest path and the backup path,and significantly improves the routing availability.