We consider the routing and the wavelength assignment (RWA) of scheduled and random lightpath demands in a wavelength switching mesh network without wavelength conversion functionality. Scheduled lightpath demands (SL...
详细信息
ISBN:
(纸本)0387231773
We consider the routing and the wavelength assignment (RWA) of scheduled and random lightpath demands in a wavelength switching mesh network without wavelength conversion functionality. Scheduled lightpath demands (SLDs) are connection demands for which the set-up and tear-down times are known in advance as opposed to random lightpath demands (RLDs) which are dynamically established and released according to a random pattern of requests. Two routing strategies are proposed which process the SLDs and the RLDs separately. The first routing strategy allows to bifurcate the traffic on several routes connecting the source to the destination of a demand whereas the second strategy forces atomic routing. The routing strategies are compared through rejection ratio.
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.
There is much demand for reducing energy consumption with regards to network communications. For this purpose, this paper proposes an energy-saving routing algorithm that uses a Steiner tree created using a branch-bas...
详细信息
ISBN:
(纸本)9783901882517;9781467352291
There is much demand for reducing energy consumption with regards to network communications. For this purpose, this paper proposes an energy-saving routing algorithm that uses a Steiner tree created using a branch-based multi-cast Steiner tree algorithm. The proposed algorithm creates a Steiner tree among edge nodes in a network and creates point to point paths between two different edge nodes by following the created Steiner tree. Since only the links and nodes on the Steiner tree are used, the numbers of used links and nodes are dramatically reduced compared with other routing algorithms. The proposed algorithm creates bypass routes between nodes on the Steiner tree to reduce traffic congestion between nodes. Many energy-saving routing algorithms have been proposed recently, but most are nondeterministic polynomial time (NP)-complete or NP-hard;thus, it is difficult to apply them to real-time routing operations. This paper compares the proposed routing algorithm with a polynomial time routing algorithm, which has already been proposed for energy saving, and the conventional open shortest path first (OSPF)-based routing algorithm to clarify the applicability of the proposed algorithm.
The family of Theta(k)-graphs is an important class of sparse geometric spanners with a small spanning ratio. Although they are a well-studied class of geometric graphs, no bound is known on the spanning and routing r...
详细信息
ISBN:
(纸本)9783030835088;9783030835071
The family of Theta(k)-graphs is an important class of sparse geometric spanners with a small spanning ratio. Although they are a well-studied class of geometric graphs, no bound is known on the spanning and routing ratios of the directed Theta(6)-graph. We show that the directed Theta(6)-graph of a point set P, denoted (Theta) over right arrow (6)(P), is a 7-spanner and there exist point sets where the spanning ratio is at least 4 - epsilon, for any epsilon > 0. It is known that the standard greedy Theta-routing algorithm may have an unbounded routing ratio on (Theta) over right arrow (6)(P). We design a simple, online, local, memoryless routing algorithm on (Theta) over right arrow (6)(P) whose routing ratio is at most 14 and show that no algorithm can have a routing ratio better than 6 - epsilon.
This study investigates the performance of an innovative routing protocol inspired by the Unsplittable Multi-Commodity Flow (UMCF) problem. LEO routing schemes are often based on Shortest Path (SP) algorithms, the Flo...
详细信息
ISBN:
(数字)9781665473774
ISBN:
(纸本)9781665473774
This study investigates the performance of an innovative routing protocol inspired by the Unsplittable Multi-Commodity Flow (UMCF) problem. LEO routing schemes are often based on Shortest Path (SP) algorithms, the Floyd-Warshall algorithm is usually chosen to compute these network paths within the constellation and their end-to-end latency. Instead of considering latency as a criterion, we seek to optimize the overall amount of IP traffic crossing the constellation. This criterion can be optimized by considering the Unsplittable Multi Commodity Flow problem associated with the system. To solve this problem, we use a heuristic algorithm based on randomized rounding that was shown to return solutions of good quality of the Unsplittable Multi Commodity Flow problem in the optimization literature. Using network simulation over Telesat constellation, we show this proposal significantly reduces the overall congestion level compared to the standard SP routing schemes.
Rumor routing is a classic routing algorithm based on the movement of the software agents among the network. In directional rumor routing, we try to propagate agents in straight lines instead of randomly wandering aro...
详细信息
ISBN:
(纸本)9781424418404
Rumor routing is a classic routing algorithm based on the movement of the software agents among the network. In directional rumor routing, we try to propagate agents in straight lines instead of randomly wandering around the source point leading to definitely better performance. In this paper we try to augment the traditional directional rumor routing by introducing a second layer geographical routing. Moreover, a method is proposed to reduce the cost of localization equipments by using cheaper equipments like AoA antennas. Finally, the new protocol is evaluated by simulation.
The work contains a first attempt to treat the problem of routing in networks with energy harvesting units. We propose HDR - a Hysteresis Based routing Algorithm and analyse it in a simple diamond network. The results...
详细信息
ISBN:
(纸本)9781467373067
The work contains a first attempt to treat the problem of routing in networks with energy harvesting units. We propose HDR - a Hysteresis Based routing Algorithm and analyse it in a simple diamond network. The results are used to give insight into its application in general topology networks.
Many trust-aware routing algorithms have been proposed in order to reliably deliver data packets from sensor nodes to the base station in wireless sensor networks (WSNs) where there exist inside attackers. In these ap...
详细信息
ISBN:
(纸本)9781479924912
Many trust-aware routing algorithms have been proposed in order to reliably deliver data packets from sensor nodes to the base station in wireless sensor networks (WSNs) where there exist inside attackers. In these approaches, a trust mechanism is adopted for each node to measure its neighbors' trustworthiness so the node can send data packets only to the trustworthy neighbors. A false alarm occurs when a good node is considered as untrustworthy. We propose a False Alarm DEtection and Recovery (FADER) technique which enables us to identify and reuse these false alarmed nodes. By doing so, we can improve the performance of the trust-aware routing protocol in terms of many metrics such as the network lifetime, the packet delivery rate, and many routing performance measures. We have conducted extensive OPNET simulations and the results confirm these claimed advantages of our proposed FADER approach over a representative trust-aware routing algorithm. The results show that FADER is able to recover 60-70% of the false alarms without recovering any of the attackers.
Congestion occurs frequently in Networks-on-Chip when the packets demands exceed the capacity of network resources. Congestion-aware routing algorithms can greatly improve the network performance by balancing the traf...
详细信息
ISBN:
(纸本)9783981080186
Congestion occurs frequently in Networks-on-Chip when the packets demands exceed the capacity of network resources. Congestion-aware routing algorithms can greatly improve the network performance by balancing the traffic load in adaptive routing. Commonly, these algorithms either rely on purely local congestion information or take into account the congestion conditions of several nodes even though their statuses might be out-dated for the source node, because of dynamically changing congestion conditions. In this paper, we propose a method to utilize both local and non-local network information to determine the optimal path to forward a packet. The non-local information is gathered from the nodes that not only are more likely to be chosen as intermediate nodes in the routing path but also provide up-to-date information to a given node. Moreover, to collect and deliver the non-local information, a distributed propagation system is presented.
GEM is an ingenious routing algorithm for wireless sensor networks that is based on the idea of graph embedding. However, it cannot survive edge failures well because reliability was not taken into consideration serio...
详细信息
ISBN:
(纸本)9781424433681
GEM is an ingenious routing algorithm for wireless sensor networks that is based on the idea of graph embedding. However, it cannot survive edge failures well because reliability was not taken into consideration seriously when it was designed. In this paper, we propose UD-GEM, a GEM-based multi-path routing algorithm that improves the reliability performance of GEM significantly. Specifically, in the case that 2% of all edges in the network fail to transfer packets and there are 900 sensor nodes in the experimental network, GEM leads to a path error rate of 12% while UD-GEM only results in a path error rate of 1%.
暂无评论