Routing Algorithms
[Kvalbein-Hansen-Cicic-Gjessing-Lysne-2008 [ (doi)] .]
Amund Kvalbein, Audun Fosselie Hansen, Tarik Cicic, Stein Gjessing, and Olav Lysne,
“Multiple Routing Configurations for Fast IP Network Recovery”,
IEEE/ACM Transactions on Networking (to appear),
ResiliNets Keywords: multipath, routing
Keywords: availability, computer network reliability, communication system fault tolerance, communication system routing, protection
Abstract: "As the Internet takes an increasingly central role in our communications infrastructure, the slow convergence of routing protocols after a network failure becomes a growing problem. To assure fast recovery from link and node failures in IP networks, we present a new recovery scheme called Multiple Routing Configurations (MRC). Our proposed scheme guarantees recovery in all single failure scenarios, using a single mechanism to handle both link and node failures, and without knowing the root cause of the failure. MRC is strictly connectionless, and assumes only destination based hop-by-hop forwarding. MRC is based on keeping additional routing information in the routers, and allows packet forwarding to continue on an alternative output link immediately after the detection of a failure. It can be implemented with only minor changes to existing solutions. In this paper we present MRC, and analyze its performance with respect to scalability, backup path lengths, and load distribution after a failure. We also show how an estimate of the traffic demands in the network can be used to improve the distribution of the recovered traffic, and thus reduce the chances of congestion when MRC is used."
Notes:
[Motiwala-Elmore-Feamster-Vempala-2008 (doi) .]
Murtaza Motiwala, Megan Elmore, Nick Feamster, and Santosh Vempala,
“Path Splicing”,
Proceedings of the ACM SIGCOMM 2008 conference on data communication,
Seattle, Washington, USA, August 17-22 2008, pp. 27–38
ResiliNets Keywords: multipath, routing
Keywords: Path Splicing, path diversity, multi-path routing
Abstract: “We present path splicing, a new routing primitive that allows network paths to be constructed by combining multiple routing trees ("slices") to each destination over a single network topology. Path splicing allows traffic to switch trees at any hop en route to the destination. End systems can change the path on which traffic is forwarded by changing a small number of additional bits in the packet header. We evaluate path splicing for intradomain routing using slices generated from perturbed link weights and find that splicing achieves reliability that approaches the best possible using a small number of slices, for only a small increase in latency and no adverse effects on traffic in the network. In the case of interdomain routing, where splicing derives multiple trees from edges in alternate backup routes, path splicing achieves near-optimal reliability and can provide significant benefits even when only a fraction of ASes deploy it. We also describe several other applications of path splicing, as well as various possible deployment paths.”
Notes:
[Merindol-Pansiot-Cateloin-2008 (doi) .]
P. Merindol, J.-J. Pansiot, and S. Cateloin,
“Improving Load Balancing with Multipath Routing”,
Proceedings of 17th International Conference on Computer Communications and Networks, 2008. ICCCN’08., pages 1–8, August 2008.,
Seattle, Washington, USA, August 17-22 2008, pp. 27–38
ResiliNets Keywords: multipath, routing, load balancing, path diversity
Keywords: Internet, computer network reliability, resource allocation, routing protocols, Internet service, bandwidth utilization, dynamic routing protocols, load balancing, multipath routing protocols, network reliability, network robustness, path diversity
Abstract: "Internet service providers have to provision network resources to optimize bandwidth utilization. Dynamic routing protocols take traffic variations into account to control the load distribution. Multipath routing protocols attempt to take advantage of the path diversity to bring network robustness and reliability. Indeed, with a specific traffic engineering policy, they enable load balancing across several paths. Our aim is to compute a set of loopfree paths in order to allow routers to share the load on several next hops depending on current load measurement. In this paper, we first describe our original Incoming Interface Multipath Routing technique, DT(p), then we present a scheme for load balancing, DT(p)-TE, based on link monitoring. We evaluate and compare our technique with several existing approaches by a set of simulations, using different scenarios and topologies. The simulations results suggest that the path diversity achieved with our proposition can significantly improve the network response time."
Notes:
[Kvalbein-Hansen-Cicic-Gjessing-Lysne-2006 (doi) .]
Amund Kvalbein, Audun Fosselie Hansen, Tarik Cicic, Stein Gjessing and Olav Lysne,
“Fast IP Network Recovery using Multiple Routing Configurations”,
Proceedings of 25th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2006),
Barcelona, Spain, April 23-29 2006, pp. 1–11
ResiliNets Keywords: list
Keywords: list from paper
Abstract: "As the Internet takes an increasingly central role in our communications infrastructure, the slow convergence of routing protocols after a network failure becomes a growing problem. To assure fast recovery from link and node failures in IP networks, we present a new recovery scheme called Multiple Routing Configurations (MRC). MRC is based on keeping additional routing information in the routers, and allows packet forwarding to continue on an alternative output link immediately after the detection of a failure. Our proposed scheme guarantees recovery in all single failure scenarios, using a single mechanism to handle both link and node failures, and without knowing the root cause of the failure. MRC is strictly connectionless, and assumes only destination based hop-by-hop forwarding. It can be implemented with only minor changes to existing solutions. In this paper we present MRC, and analyze its performance with respect to scalability, backup path lengths, and load distribution after a failure."
Notes: (optional) relevance or importance or importance to ResiliNets
[Sambasivam-Murthy-Royer-2004 [ (doi)] .]
Perumal Sambasivam, Ashwin Murthy, and Elizabeth M. Belding-Royer
“Dynamically Adaptive Multipath Routing based on AODV”,
Proceedings of 3rd Annual Mediterranean Ad Hoc Networking Workshop (MEDHOCNET) 2004,
Bodrum, Turkey, June 2004, S3.2
ResiliNets Keywords: list
Keywords: list from paper
Abstract: “Mobile ad hoc networks are typically characterized by high mobility and frequent link failures that result in low throughput and high end-to-end delay. To reduce the number of route discoveries due to such broken paths, multipath routing can be utilized so that alternate paths are available. Current approaches to multipath routing make use of pre-computed routes determined during route discovery. These solutions, however, suffer during high mobility because the alternate paths are not actively maintained. Hence, precisely when needed, the routes are often broken. To overcome this problem, we present an adaptive multipath solution. In this approach, multiple paths are formed during the route discovery process. All the paths are maintained by means of periodic update packets unicast along each path. These update packets measure the signal strength of each hop along the alternate paths. At any point of time, only the path with the strongest signal strength is used for data transmission. In this paper, we present two variations of our protocol and evaluate both with respect to two previously published multipath routing protocols. Simulation results show that the proposed solutions result in significant performance improvement.”
Notes: (optional) relevance or importance or importance to ResiliNets
[Cetinkaya-Knightly-2004 (doi) .]
C. Cetinkaya and E.W. Knightly
“Opportunistic Traffic Scheduling over Multiple Network Paths”,
Proceedings of the Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies - INFOCOM 2004,
7-11 March 2004, vol. 3 pp. 1928-1937
ResiliNets Keywords: Routing, Resilience, Multipath
Keywords: Internet, routing protocols, scheduling, telecommunication network management, telecommunication traffic, transport protocolsHurst parameter, TCP throughput, high-throughput path, multipath routing, multiple network path, network traffic, opportunistic multipath scheduling, path condition, path quality, path selection, round-robin scheduling, routing protocol, traffic fluctuation, traffic management policy, traffic split
Abstract: “Multipath routing enables a network's traffic to be split among two or more possibly disjoint paths in order to reduce latency, improve throughput, and balance traffic loads. Yet, once the control plane establishes multiple routes, a policy is needed for efficiently splitting traffic among the selected paths. In this paper, we introduce opportunistic multipath scheduling (OMS), a technique for exploiting short term variations in path quality to minimize delay, while simultaneously ensuring that the splitting rules dictated by the routing protocol are satisfied. In particular, OMS uses measured path conditions on time scales of up to several seconds to opportunistically favor low-latency high-throughput paths. Consequently, OMS ensures that over longer time scales relevant for traffic management policies, traffic is split according to the ratios determined by the routing protocol. We develop a model of OMS and derive an asymptotic lower bound on the performance of OMS as a function of path conditions (mean, variance, and Hurst parameter) for self-similar traffic. An example finding from the model is that long-time-scale traffic fluctuations represented by a larger Hurst parameter improve the performance gain of OMS vs. round-robin scheduling, even under paths that are statistically identical. Finally, we use an extensive simulation-based performance study to evaluate the accuracy of the analytical model, explore the impact of OMS on TCP throughput, and study the impact of factors such as delayed measurements.”
Notes:
[Biagioni-Chen-2004 (doi) .]
Edoardo Biagioni, Shu Hui Chen
“A Reliability Layer for Ad-Hoc Wireless Sensor Network Routing”,
Proceedings of the 37th Hawaii International Conference on System Sciences - 2004,
Hawaii, 5-8 Jan. 2004, pp. 1-8
ResiliNets Keywords: Routing, resilience
Keywords: list from paper
Abstract: "We have been studying communication in wireless ad-hoc sensor networks. One of the authors has designed the Multipath On-demand Routing (MOR) protocol [4], which makes use of all possible paths to a given destination. Each node in MOR has, wherever possible, a choice of next hops for a given destination. We have designed and implemented a MOR reliability layer to take advantage of this. The basic strategy is to use a different node on each retransmission, and to keep track of which transmissions are successful. The main benefit is that a packet is likely to be delivered even if a given neighbor is temporarily unavailable, thus improving the delivery ratio or decreasing the number of end-to-end retransmissions. A further benefit is that nonresponsive nodes are removed from the routing table after a number of consecutive failures.
In a sensor network transmission may be unreliable for a number of reasons, but particularly when congestion results in collisions. Without our reliability layer, collisions would cause packet loss and route loss. If the transport protocol is reliable, this results in end-to-end retransmission, which requires additional energy. We simulated transmission in congested conditions in different realistic sensor networks and compared MOR to available protocols. In our tests, the reliability layer helped MOR deliver data faster and using less energy than the other protocols."
Notes:
[Ganesan-Govindan-Shenker-Estrin-2001 (doi) .]
Deepak Ganesan, Ramesh Govindan, Scott Shenker, Deborah Estrin
“Highly-Resilient, Energy-Efficient Multipath Routing in Wireless Sensor Networks”,
Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing,
Long Beach, CA, month 2001, pp. 251-254
ResiliNets Keywords: Resilience
Keywords: Disjoint
Abstract: "Previously proposed sensor network data dissemination schemes require periodic low-rate flooding of data in order to allow recovery from failure. We consider constructing two kinds of multipaths to enable energy efficient recovery from failure of the shortest path between source and sink. Disjoint multipath has been studied in the literature. We propose a novel braided multipath scheme, which results in several partially disjoint multipath schemes. We find that braided multipaths are a viable alternative for energy-efficient recovery from isolated and patterned failures."
Notes: (optional) relevance or importance or importance to ResiliNets
[Ramanathan-Basu-Krishnan-2007 (doi) .]
Ram Ramanathan, Prithwish Basu and Rajesh Krishnan
“Towards a Formalism for Routing in Challenged Networks”,
Proceedings of the second ACM workshop on Challenged networks,
Montreal Quebec, Canada, September 2007, pp. 3–10
ResiliNets Keywords: challenged networks, disruption tolerant networks, formalism
Keywords:
Abstract: "Research on challenged or delay/disruption-tolerant networks has exploded in the past few years with a plethora of algorithms targeted at different versions of the problem. Yet, there have been few formal studies on the fundamental nature of the routing problem in challenged networks. As a step toward closing this gap, we introduce a formal framework relating the problem and solution spaces in challenged networks. We define three fundamental types of challenged networks and several classes of routing mechanisms. We then prove a number of results on the power of each class of routing mechanism in terms of the network types that it can solve. We show that simple variants of MANET protocols can solve two but not all three network types. However, either complete schedule awareness or maximal replication is sufficient to solve even the most general type of challenged network. We extend these results to the bounded-storage and bounded-bandwidth cases. Finally, we briefly discuss a number of avenues in which the core formalism may be extended, including an infinite opportunity model and graph theoretic extensions."
Notes:
