"Ant algorithms" have been proposed to solve a variety of problems arising in optimization and distributed control. They form a subset of the larger class of "Swarm Intelligence" algorithms. The ce...
详细信息
ISBN:
(纸本)9781424414970;1424414970
"Ant algorithms" have been proposed to solve a variety of problems arising in optimization and distributed control. They form a subset of the larger class of "Swarm Intelligence" algorithms. The central idea is that a 'swarm' of relatively simple agents can interact through simple mechanisms and collectively solve complex problems. Instances that exemplify the above idea abound in nature. The abilities of ant colonies to collectively accomplish complex tasks have served as sources of inspiration for the design of "Ant algorithms". Examples of "Ant algorithms" are "Ant routing" algorithms that have been proposed for communication networks. We analyze in this paper an Ant-Based routing Algorithm for packet-switched wireline networks. The algorithm is an attractive multiple path probabilistic routing scheme, that is fully adaptive and distributed. Using methods from adaptive algorithms and stochastic approximation, we show that the evolution of the link delay estimates can be closely tracked by a deterministic ODE system. A study of the equilibrium points of the ODE then gives us the equilibrium behavior of the routing algorithm, in particular, the equilibrium routing probabilities, and mean delays in the links under equilibrium. We also show that the fixed-point equations that the equilibrium probabilities satisfy are actually the necessary and sufficient conditions of an appropriate optimization problem. Simulations supporting the analytical results are provided.
Efficient on-chip communication is very important for exploiting enormous computing power available on a multi core chip. Network on Chip (NoC) has emerged as a competitive candidate for implementing on-chip communica...
详细信息
ISBN:
(纸本)9780769541716
Efficient on-chip communication is very important for exploiting enormous computing power available on a multi core chip. Network on Chip (NoC) has emerged as a competitive candidate for implementing on-chip communication. routing algorithms significantly affect the performance of a NoC. Most of the existing NoC architectural proposals advocate distributed routing algorithms for building NoC platforms. Although source routing offers many advantages, researchers avoided it due to its apparent disadvantage of larger header size requirement that results in lower bandwidth utilization. In this paper we make a strong case for the use of source routing for NoCs, especially for platforms with small sizes and regular topologies. We present a methodology to compute application specific efficient paths for communication among cores with a high degree of load balancing. The methodology first selects the most appropriate deadlock free routing algorithm, from a set of routing algorithms, based on the application's traffic patterns. Then the selected (possibly adaptive) routing algorithm is used to compute efficient static paths with the goal of link load balancing. We demonstrate through simulation based evaluation that source routing has a potential of achieving higher performance, for example up to 28% lower latency even at medium load, as compared to distributed routing. A simple scheme is proposed for encoding of router ports to reduce the header overhead. A generic simulator was developed for evaluation and performance comparison between source routing and distributed routing. We also designed a router to support source routing for mesh topology NoC platforms.
For the design of mobile ad hoc networks, particularly those consisting of low-cost devices, we propose a new routing algorithm, called ranging-based link availability routing (RBLAR). In order to reduce link breakage...
详细信息
ISBN:
(纸本)9781424463985
For the design of mobile ad hoc networks, particularly those consisting of low-cost devices, we propose a new routing algorithm, called ranging-based link availability routing (RBLAR). In order to reduce link breakages during data services, we propose a new link cost, i.e., the unavailability of a link. In order to reduce the cost and complexity of the implementation, we propose to use only ranging information in the link availability, in stead of complete localization information. Based on the new metrics, the routing is formulated as an optimal routing problem, for which a heuristic algorithm is developed. Simulation results have demonstrated that RBLAR significantly improves link connectivity by reducing link breaks and also network performance including packet delivery ratio and throughput, as compared to the existing routing algorithms.
A heuristic optimization framework is proposed for routing virtually-concatenated 100Gb/s Ethernet over optical transport networks with distributed differential delay compensation. Under short computing times, reduced...
详细信息
ISBN:
(纸本)9781557528841
A heuristic optimization framework is proposed for routing virtually-concatenated 100Gb/s Ethernet over optical transport networks with distributed differential delay compensation. Under short computing times, reduced buffer sizes and limited link capacity requirements are obtained. (C) 2010 Optical Society of America
In this paper, we propose CAFE router which obtains routes of multiple nets with target wire lengths for single layer routing grid with obstacles. CAFE router extends the route of each net from a pin to the other pin ...
详细信息
ISBN:
(纸本)9781424457656
In this paper, we propose CAFE router which obtains routes of multiple nets with target wire lengths for single layer routing grid with obstacles. CAFE router extends the route of each net from a pin to the other pin greedily so that the wire length of the net approaches its target wire length. Experiments show that CAFE router obtains the routes of nets with small length error in short time.
We study the problem of online packet routing in dynamic store-and-forward directed line networks. We present a centralized randomized online algorithm that achieves a throughput that is O(log n)-competitive, where n ...
详细信息
ISBN:
(纸本)9783642141614
We study the problem of online packet routing in dynamic store-and-forward directed line networks. We present a centralized randomized online algorithm that achieves a throughput that is O(log n)-competitive, where n denotes the number of nodes. Our algorithm is applicable to all values of buffer sizes and communication link capacities. In particular, it holds also for unit buffers. This algorithm improves the best previous O(log(2) n)-competitive ratio of [6] and considers links with unit capacities.
Geometric routing by using virtual locations is an elegant way for solving network routing problem. In its simplest form, greedy routing, a message is forwarded to a neighbor that is closer to the destination. One maj...
详细信息
ISBN:
(数字)9783642135620
ISBN:
(纸本)9783642135613
Geometric routing by using virtual locations is an elegant way for solving network routing problem. In its simplest form, greedy routing, a message is forwarded to a neighbor that is closer to the destination. One major drawback of this approach is that the virtual coordinates requires Omega(n log n) bits to represent, which makes this scheme infeasible in sonic applications. In this paper, we introduce a modified version of greedy routing which we call generalized greedy routing algorithm. Instead of relying on decreasing distance for routing decision, our routing algorithms use other criterion to determine routing path, solely based on local information. We present simple generalized greedy routing algorithms based on Schnyder coordinates (consisting of three integers between 0 and 2n), which are derived from Schnyder realizer for plane triangulations and Schnyder wood for 3-connected plane graphs. The algorithms are simple and can be easily implemented in linear time.
Radiation effects on SRAM-based FPGA configuration memory induce unique failure modes that cannot be found in similar ASIC devices and can translate into permanent errors in the circuit mapped into the FPGA. The physi...
详细信息
ISBN:
(纸本)9781424472055
Radiation effects on SRAM-based FPGA configuration memory induce unique failure modes that cannot be found in similar ASIC devices and can translate into permanent errors in the circuit mapped into the FPGA. The physical layout of the mapped circuit has a considerable impact on the overall reliability of the implemented circuit. In this work we present a set of soft error reliability aware placement and routing algorithms, by modifying the original VPR toolset, to improve the reliability of the mapped designs against SEUs occurring in the FPGA SRAM configuration memory. Our proposed approach tries to minimize the number of possible errors in the circuit while optimizing for traditional design constraints, namely, area and delay. Using our approach we were able to reduce the number of total sensitive bits by 58% on average.
In this paper, we seek the improvement of a newly developed Static Channel Width Routeless routing (SCWRR) protocol which uses a self-determined Geographical Forwarding MASNET. Even though our previously obtained resu...
详细信息
This paper presents a column generation heuristic for the general vehicle routing problem (OVRP), a combined load acceptance and rich vehicle routing problem incorporating various real-life complexities. Computational...
详细信息
ISBN:
(纸本)9783642137990
This paper presents a column generation heuristic for the general vehicle routing problem (OVRP), a combined load acceptance and rich vehicle routing problem incorporating various real-life complexities. Computational experiments show that proposed column generation heuristic is competitive with heuristics previously presented for the GVRP.
暂无评论