Performance analysis of multihop lightwave networks with hot potatorouting and distance-age-priorities

Multihop lightwave networks with hot potato routing offer the potential for significantly higher aggregate capacity as compared against minimum distance routing since each interconnecting link can be operated at a rate much higher than the electro-optic constraint forced by store-and-forward buffering. If the links can be operated at a speed sufficiently high as to offset the hot potato misrouting inefficiency, then a net capacity gain will be enjoyed. In this paper, we study such a network in which contention for an outbound link is resolved by assigning to each packet a priority based on its distance to destination and its age (number of misroutes previously suffered). An approximate analysis based on a reasonable set of assumptions is presented, queueing delay, packet loss performance, and network aggregate capacity (saturation throughout) are compared for distance-age prioritization, age-distance prioritization, and no prioritization. Results suggest that the lowest delay, lowest packet loss performance, and highest saturation throughput are offered by distance-age prioritization (priority given first to a packet closest to its destination and second to the oldest of multiple packets of the same distance to destination). The tails of the probability distribution for the number of hops taken by a representative packet are, however, shorter for age-distance routing. The capacity gain with link speed-up and hot potato routing can be quite significant compared to link speed-constrained store and forward buffering, and grows with both link speed-up factor and network size     

Analysis and comparison of hot-potato and single-buffer deflectionrouting in very high bit rate optical mesh networks

The steady state behavior of regular two-connected multihop networks in uniform traffic under a hot-potato and a simple single-buffer deflection routing technique is analyzed for very high bit rate optical applications. Manhattan Street Network and ShuffleNet are compared in terms of throughput, delay, deflection probability, and hop distribution both analytically and by simulation. It is analytically verified that this single-buffer deflection routing technique recovers in both networks more than 60% of the throughput loss of hot-potato with respect to store-and-forward when packets are generated with independent destinations. This gain, however, decreases to below 40% when the average message length exceeds 20 packets     

Packet scheduling algorithms and performance of a bufferedshufflenet with deflection routing

In a multihop network, packets go through a number of hops before they are absorbed at their destinations. In routing to its destination using minimum path, a packet at a node may have a preferential output link (the so-called “care” packet) or may not (the so-called “don't care” packet). Since each node in an optical multihop network may have limited buffer, when such buffer runs out, contention among packets for the same output link can be resolved by deflection. In this paper, we study packet scheduling algorithms and their performance in a buffered regular network with deflection routing. Using shufflenet as an example, we show that high performance (in terms of throughput and delay) can he achieved if “care” packets can be scheduled with higher priority than “don't care” packets. We then analyze the performance of a shufflenet with this priority scheduling given the buffer size per node. Traditionally, the deflection probability of a packet at a node is solved from a transcendental equation by numerical methods which quickly becomes very cumbersome when the buffer size is greater than one packet per node. By exploiting the special topological properties of the shufflenet, we are able to simplify the analysis greatly and obtain a simple closed-form approximation of the deflection probability. The expression allows us to extract analytically the performance trend of the shufflenet with respect to its buffer and network sizes. We show that a shufflenet indeed performs very well with only one buffer, and can achieve performance close to the store-and-forward case using a buffer size as small as four packets per node     

Routing for multimedia traffic in wireless frequency-hopcommunication networks

A new method is described for routing multimedia traffic in a frequency-hop (FH) store-and-forward packet radio network. The method is illustrated for traffic of two types, each type having its own throughput, delay, and error-rate requirements. A typical application is the routing of voice and data packets in a distributed multiple-hop network. In such an application, voice packets cannot tolerate much delay, but they are allowed to contain a small number of frame erasures while data packets must be delivered error-free even if a moderate delay is required to do so. The fully distributed routing protocol presented in the paper takes into account the type of service required for each type of traffic, and it adapts to the interference as seen by the FH radio receivers in the network. Our approach to multimedia routing is based on least-resistance routing with different link and path resistance metrics for different message types. Each of the resistance metrics for a link reflects the ability of the link to provide the service required by the one of the message types. This includes, but is not limited to, a measure of the likelihood of successful reception by the FH radio receiver for that link. The route selection for a particular type of packet depends on the resistances of the links along the routes from that packet's source to its destination. In general, different routes may be selected for different types of packets. The primary conclusion of this paper is that the quality of service increases for each of the two types of multimedia traffic if the routing protocol accounts for the type of message that is being relayed     

Multi‐topology routing based egress selection approach to achieve hybrid intra‐AS and inter‐AS traffic engineering

Hot‐potato routing is a border gateway protocol policy that selects the ‘closest’ egress router in terms of interior gateway protocol cost. This policy imposes inherent interactions between intra‐AS (Autonomous System) and inter‐AS traffic engineering. In light of this observation, we present a hybrid intra‐AS and inter‐AS traffic engineering scheme named egress selection based upon hot potato routing. This scheme involves link weight optimization, which can not only minimize the time that IP (Internet Protocol) packets travel across the network by assigning specified egress router but also balance the load among the internal links of the transit network. Egress selection based upon hot potato routing also incorporates multi‐topology routing technique to address the problem that one set of link weights might not guarantee specified egress routers. Accordingly, we formulate the link weights optimization problem using multi‐topology routing as a mixed integer linear programming model. And we present a new heuristic algorithm to make the problem tractable. Numerical results show that only a few topologies are needed to guarantee specified egress router, and maximum link utilization is also reduced. Copyright © 2014 John Wiley & Sons, Ltd.     

Link State Routing Based on Compressed Sensing

In table routing protocols such as link state routing, every node in the network periodically broadcasts its link state and the state of its neighbors. These routing updates result in the transmission of a large number of packets. Some of these packets contain correlated or even redundant data which could be compressed if there is central management in the network. However, in autonomous networks, each node acts as a router, in which case central coordination is not possible. In this paper, compressed sensing is used to reduce routing traffic overhead. This can be done at nodes which have greater processing capabilities and no power consumption limitations such as backbone nodes in wireless mesh networks. A method is proposed to select a subset of nodes and thus a subset of links to probe their state. The sensed states are encoded to generate a low dimension sampled vector. This compressed link state vector is broadcast to the entire network. Nodes can then reconstruct link states from this vector using side information. Performance results are presented which demonstrate accurate anomaly detection while adapting to topology changes. Further, it is shown that a proper choice of weighting coefficients in the sampling process can improve detection performance.     

Improved multicast routing in MANETs using link stability and route stability

The growing popularity of multimedia applications and services needs to support several quality of service metrics such as high throughput, low energy, and jitter, which is a challenging task in mobile ad hoc networks. Because of limited bandwidth, energy constraints, dynamic topology, transmission errors, and fluctuating link stability, the links between adjacent nodes are often not reliable and may break because of node mobility. Link breakage initiates the process of rerouting either at the sender node (the node at which the link breaks) or at the source node. In either case, it leads to packet loss, delivery delays, and increased control overheads. Hence, to attain a minimum quality of service, routing protocols must address the dynamic network topology. Uncertain and varying movement of nodes necessitates stability of the links between such nodes. The objective of this paper is to propose 2 protocols, the first based on link stability and the other based on route stability. Link stability identifies a stable link from the available links to the next hop and determines a stable end‐to‐end route. The probability of successful transmission of periodic packets is used as a link stability metric to assess the stable path. Acknowledgment ‐free packets are used to check connectivity in the network. Increased probability of successful transmission implies that the selected link is sustained for longer duration and can deliver packets more reliably or, as a consequence, results in a stable link to deliver a better data rate. With a stable link, there is a reduced possibility of retransmissions, reduced end‐to‐end delay, reduced control overheads, and enhanced data delivery ratio. Selection of the most stable route for data transmission improves the performance. Experimental results from simulations performed on EXata/Cyber v2.0 simulator reveal that our proposed protocols are an improvement over the existing protocols in terms of packet delivery ratio, average end‐to‐end delay, and average route lifetime, even without route optimization with the minor increase in control packets. A case study of the application of proposed protocols is also presented.     

IP layer restoration and network planning based on virtual protection cycles

We describe a novel restoration strategy called virtual protection cycles (p-cycles, patents pending) for extremely fast restoration in IP networks. Originally conceived for use in WDM and Sonet transport networks, we outline the adaption of the p-cycle concept to an IP environment. In an IP router-based network, p-cycles are implemented with virtual circuits techniques (such as an MPLS label switched path, or other means) to form closed logical loops that protect a number of IP links, or a node. In the event of failure, packets which would normally have been lost are encapsulated with a p-cycle IP address and reenter the routing table, which diverts them onto a protection cycle. They travel by normal forwarding or label switching along the p-cycle until they reach a node where the continuing route cost to the original destination is lower than that at the p-cycle entry node. Diverted packets are deencapsulated (dropped from the p-cycle) at that node and follow a normal (existing) route from there to their destination. Conventional routing protocols such as OSPF remain in place and operate as they do today, to develop a longer term global update to routing tables. Diversionary flows on the p-cycle inherently cease when the global routing update takes effect in response to the failed link or node. The p-cycle thus provides an immediate real-time detour, preventing packet loss, until conventional global routing reconvergence occurs. The aim of the paper is to explain the basic p-cycle concept and its adaptation to both link and node restoration in the IP transport layer, and to outline certain initial results on the problem of optimized design of p-cycle based IP networks.     

A performance model of deflection routing in multibuffer networkswith nonuniform traffic

Deflection routing can be used in networks whose stations have the same number of input and output links. Fixed length packets arrive synchronously on the station's input links at the beginning of time slots, and each packet is routed via the output link that offers the shortest path to its destination. Since the number of packet buffers at each output link is finite, the simultaneous contention of two packets for the last buffer of a common output link must be resolved by “deflecting” one of the packets to another output link. Thus, the deflection of a packet could result in the packet following a route that is not a shortest path. The potentially unbounded number of routes that a given packet can take makes analyzing the performance of such networks difficult. In particular, there are no analytical models that can analyze multibuffer deflection-routing networks with nonuniform traffic. Using independence assumptions, the authors develop a performance model of deflection routing that allows to estimate accurately and efficiently the mean transport time and throughput in a network that has any given two-connected topology, multiple buffers at each output port, and an arbitrary traffic matrix     

Multi‐cost routing for energy and capacity constrained wireless mesh networks

We propose a class of novel energy‐efficient multi‐cost routing algorithms for wireless mesh networks, and evaluate their performance. In multi‐cost routing, a vector of cost parameters is assigned to each network link, from which the cost vectors of candidate paths are calculated using appropriate operators. In the end these parameters are combined in various optimization functions, corresponding to different routing algorithms, for selecting the optimal path. We evaluate the performance of the proposed energy‐aware multi‐cost routing algorithms under two models. In the network evacuation model, the network starts with a number of packets that have to be transmitted and an amount of energy per node, and the objective is to serve the packets in the smallest number of steps, or serve as many packets as possible before the energy is depleted. In the dynamic one‐to‐one communication model, new data packets are generated continuously and nodes are capable of recharging their energy periodically, over an infinite time horizon, and we are interested in the maximum achievable steady‐state throughput, the packet delay, and the energy consumption. Our results show that energy‐aware multi‐cost routing increases the lifetime of the network and achieves better overall network performance than other approaches. Copyright © 2011 John Wiley & Sons, Ltd.     

Network Coding in Multicast Routing for Wireless Link Breakage Problem

Link breakage is one of the critical problems that limit the performance of multicast routing in wireless networks. To ease the problem, we apply network coding to the routing operation. In our proposal, data packets are encoded by a random coding scheme. By performing a re-encoding process, the coding scheme is able to keep conveying the data in the network even though link breakage occurs (without the need of waiting for retransmission). To route encoded packets in the network, a disjoint-path tree is used, which is the routing structure constructed by combining a number of multicast trees without the overlapping links among them. Simulation results show that our proposal can effectively ease the impact of link breakage, achieving better packet delivery ratio and higher multicast capacity under different scenarios.     

Slot Routing as a Solution for Optically Transparent Scalable WDM Wide Area Networks*

All-optical Wavelength Division Multiplexing (WDM) backbones are believed to be a fundamental component in future high speed networks. Currently, the most pursued approach for Wide Area Networks (WANs) is wavelength routing, in which communication circuits are established between node pairs by means of lightpaths (paths of light) spanning one or more fiber-optic links. This approach has, however, two drawbacks. Since the number of wavelengths and links in a network is finite, not all node pairs can be connected via a dedicated lightpath directly. Consequently, some node pairs will communicate using a concatenation of lightpaths, which requires electronic switching of in transit information, loosing the advantages of optical transparency. Secondly, typically some form of (electronic) traffic grooming will be necessary to make efficient use of the fixed lightpath capacity. This paper proposes to design all-optical WANs using a novel approach, called photonic slot routing. With photonic slot routing, entire slots, each carrying multiple packets on distinct wavelengths, are switched transparently and individually, using available fast and wavelength non-sensitive devices. The advantage of using photonic slot routing is threefold. All node pairs in the network communicate all-optically. Traffic aggregation necessary to efficiently use the capacity of the wavelength channels is optically achieved. The solution is practical as it is based on proven optical technologies. In addition, through the use of wavelength non-sensitive devices the proposed WAN design yields intrinsic scalability in the number of wavelengths.     

AODV_RR: A Maximum Transmission Range Based Ad Hoc on-Demand Distance Vector Routing in MANET

Nodes in a mobile ad hoc network are battery constrained devices and energy efficiency becomes an important consideration. In a multi-hop mobile ad hoc network the most common method to achieve energy efficiency is the transmission power control scheme in which a node transmits the data packets to its nearest neighbor which is at minimum required power level. However this scheme minimizes only the transmission power within the node’s neighborhood and energy efficiency at the link level is possible. With this scheme it is not possible to minimize the overall energy consumption of the network and the communication overhead of the network is not minimized. An analysis has been performed and our results have proved that instead of using low transmission power, the routing strategy needs to be controlled and only certain nodes are to be allowed to receive and process this routing request based on the received signal strength, then the overall energy consumption of the network can be minimized and the communication overhead is also minimized. The modified routing strategy is applied to the basic ad hoc on-demand distance vector (AODV) routing protocol and a maximum transmission range based ad hoc on-demand distance vector routing protocol named AODV range routing (AODV_RR) is proposed and studied under different network sizes. Measurable difference in performance is realized and the proposed AODV_RR perform better than normal AODV with respect to all the selected metrics.     

Integrated dynamic distributed routing and admission control in ATM networks

A node-by-node admission control and routing scheme for ATM networks is devised. The scheme is based on the subdivision of traffic into a number of classes, characterized by different performance requirements. At each network node, for all outgoing links, link capacity partitions are periodically assigned to the traffic classes, as the result of an optimization problem over a fixed time interval. Local access control rules compute the maximum number of connections of each class that a link can accept within the assigned capacity. Incoming call connection requests are forwarded in a hop-by-hop fashion. Each node traversed, first checks the presence of resources needed to accept a new connection and guarantee all quality of service (QoS) requirements. This is done by using the local access control rule. Then, it chooses the next node along the path on the basis of a distributed routing strategy. This minimizes a cost function accounting for local instantaneous information, as well as for aggregate information that is passed periodically among adjacent nodes. Two routing strategies are introduced. In the first scheme, a new call is rejected if, at a certain node along the path, there are not enough resources to guarantee QoS requirements, and no recovery mechanism is implemented. In the second scheme, an alternative path is looked for after the first failure. Simulation results are presented which show a comparison between the two proposed routing strategies. Comparison is also made between the proposed scheme and the other approaches. © 1997 John Wiley & Sons, Ltd.     

Iterative approach to optimizing convergence routing priorities

This paper shows how to optimize the routing decisions in a nondeterministic routing algorithm called convergence routing in which routes may change depending on the traffic conditions. The routing algorithm guarantees a loss-free delivery of data packets from bursty sources, and a deterministic bound on the route length in arbitrary topology networks. The routing decisions are based on assigning routing priorities to the links such that a packet is forwarded to the highest priority link which is not blocked. Routing priorities are assigned using a local-greedy metric which minimizes the distance (number of hops) to the destination. This work shows that routing decisions using a local-greedy metric are not optimal, and the performance of the algorithm can be improved substantially by using new measures. Thus, various look-ahead metrics which take into account the potential gain on the other switching nodes toward the destination of a packet are suggested. The contributions of this work are: (1) a new analytical model to capture the behavior of a switching node; (2) an iterative optimization technique to set routing priorities according to various look-ahead measures; and (3) heuristics to ensure the stability of the routing priorities. The optimization objective is to maximize the throughput by minimizing the maximum total flow carried on a link in the network under static traffic model. The performance is studied computationally on various networks and traffic matrices. It is shown that up to a 50% performance increase can be obtained by optimizing the routing priorities     

基于共享路径和网络编码的光组播容量优化

为了降低光组播路由 的光域网络编码代价和提高达到理论最大光组播容量的 概率,提出一种基于共享链路和网络编 码的优化光组播容量方法。首先设计一种从多条源－ 宿最短路径中选择能达到最大光组播容量的最短路径簇,然后在 最短路径簇中计算路径的共享度,选择共享度高的组播路径传输网络编码信息,构造网络编 码次数最少的光组播编码子图, 解决传统的网络编码组 播路由和最大共享度链路组播路由中存在的网络编码次数过多和达到最大光组播容量概率过 低的问 题。仿真结果表明:本文提出的方法具有最低的网络编码代价,能以最大的概率达到光组播 理论最大容量。     

Detecting and avoiding wormhole attacks in wireless ad hoc networks [security in mobile ad hoc]

A particularly severe attack on routing protocols in ad hoc networks is the so-called worm- hole attack in which two or more colluding attackers record packets at one location, and tunnel them to another location for replay at that remote location. When this attack targets specifically routing control packets, the nodes that are close to the attackers are shielded from any alternative routes with more than one or two hops to the remote location. All routes are thus directed to the wormhole established by the attackers. In the optimized link state routing protocol, if a wormhole attack is launched during the propagation of link state packets, the wrong link information percolates throughout the network, leading to routing disruption. In this article we devise an efficient method to detect and avoid wormhole attacks in the OLSR protocOLSR protocolol. This method first attempts to pinpoint links that may potentially be part of a wormhole tunnel. Then a proper wormhole detection mechanism is applied to suspicious links by means of an exchange of encrypted probing packets between the two supposed neighbors (endpoints of the wormhole). The proposed solution exhibits several advantages, among which are its nonreliance on any time synchronization or location information, and its high detection rate under various scenarios.     

Opportunistic media access control and routing for delay-tolerant mobile ad hoc networks

In delay-tolerant mobile ad hoc networks, motion of network nodes, network sparsity and sporadic density can cause a lack of guaranteed connectivity. These networks experience significant link delay and their routing protocols must take a store-and-forward approach. In this paper, an opportunistic routing protocol is proposed, along with its compatible media access control, for non-real-time services in delay-tolerant networks. The scheme is mobility-aware such that each network node needs to know its own position and velocity. The media access control employs a four-fold handshake procedure to probe the wireless channel and cooperatively prioritize candidate nodes for packet replication. It exploits the broadcast characteristic of the wireless medium to utilize long-range but unreliable links. The routing process seizes opportunities of node contacts for data delivery. It takes a multiple-copy approach that is adaptive with node movements. Numerical results in mobile ad hoc networks and vehicular ad hoc networks show superior performance of the proposed protocol compared with other routing protocols. The mobility-aware media access control and routing scheme exhibits relatively small packet delivery delay and requires a modest amount of total packet replications/transmissions.     

一种基于迁移可测度的移动自组织网路由模型

 本文利用链路状态有效估测端到端路径的可达性。路由模型给出最近时间内,任意两点分组传输的迁移可测度;节点根据其邻节点的迁移可测度制定组合策略,计算组合迁移可测度,选取最优中继组合完成分组传输。仿真实验表明,该路由模型既可有效控制分组副本数目,又可获得较高的分组到达率。     

Capacity of interconnected ring communication systems with unique loop-free routing (Corresp.)

{em Capacity} is defined for a given distribution of offered traffic as the maximum rate with which packets can be sent with finite delay through the network by appropriate routing. It is shown how capacity depends on the traffic characteristics and on the topology of ring communication systems interconnected so as to provide unique loop-free routing. First, the traffic conditions are given under which the capacity of a {em single ring} attains its maximum and its minimum. For the case of {em uniform traffic} it is shown that the capacity is equal to twice the minimum capacity. Then it is shown that, for uniform traffic, the capacity relative to a single ring communication system can be increased by as much as33.3or80percent when the stations are split up into two or three separate rings, respectively, interconnected to give unique loop-free routing. Exact formulas are given for the capacity of systems with an arbitrary number of stations split up into an arbitrary number of separate rings interconnected to give unique loop-free routing. Finally, it is shown that connecting {em local rings} through a star network with a central switching node is particularly useful when stations can be segregated into local groups of stations which often communicate with stations from the same local group but only rarely with stations from the other groups. Exact formulas are given to calculate the capacity of such interconnected ring communication systems.