| 1. |
- Chiesa, Marco, 1987-, et al.
(author)
-
On the resiliency of randomized routing against multiple edge failures
- 2016
-
In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. - : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. - 9783959770132
-
Conference paper (peer-reviewed)abstract
- We study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph G = (V, E), a unique destination vertex d, and an integer constant c > 0, does there exist a static and destination-based routing scheme such that the correct delivery of packets from any source s to the destination d is guaranteed so long as (1) no more than c edges fail and (2) there exists a physical path from s to d? We embark upon a study of this problem by relating the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions G, to its resiliency. Following the success of randomized routing algorithms in dealing with a variety of problems (e.g., Valiant load balancing in the network design problem), we embark upon a study of randomized routing algorithms for the Static-Routing-Resiliency problem. For any k-connected graph, we show a surprisingly simple randomized algorithm that has expected number of hops O(|V|k) if at most k-1 edges fail, which reduces to O(|V|) if only a fraction t of the links fail (where t < 1 is a constant). Furthermore, our algorithm is deterministic if the routing does not encounter any failed link.
|
|
| 2. |
- Chiesa, Marco, 1987-, et al.
(author)
-
On the Resiliency of Static Forwarding Tables
- 2017
-
In: IEEE/ACM Transactions on Networking. - : Institute of Electrical and Electronics Engineers (IEEE). - 1063-6692 .- 1558-2566. ; 25:2, s. 1133-1146
-
Journal article (peer-reviewed)abstract
- Fast reroute and other forms of immediate failover have long been used to recover from certain classes of failures without invoking the network control plane. While the set of such techniques is growing, the level of resiliency to failures that this approach can provide is not adequately understood. In this paper, we embarked upon a systematic algorithmic study of the resiliency of forwarding tables in a variety of models (i.e., deterministic/probabilistic routing, with packet-headerrewriting, with packet-duplication). Our results show that the resiliency of a routing scheme depends on the "connectivity" k of a network, i.e., the minimum number of link deletions that partition a network. We complement our theoretical result with extensive simulations. We show that resiliency to four simultaneous link failures, with limited path stretch, can be achieved without any packet modification/duplication or randomization. Furthermore, our routing schemes provide resiliency against k - 1 failures, with limited path stretch, by storing log(k) bits in the packet header, with limited packet duplication, or with randomized forwarding technique.
|
|
| 3. |
- Chiesa, Marco, 1987-, et al.
(author)
-
The quest for resilient (static) forwarding tables
- 2016
-
In: INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, IEEE. - : Institute of Electrical and Electronics Engineers (IEEE). - 9781467399531
-
Conference paper (peer-reviewed)abstract
- Fast Reroute (FRR) and other forms of immediate failover have long been used to recover from certain classes of failures without invoking the network control plane. While the set of such techniques is growing, the level of resiliency to failures that this approach can provide is not adequately understood. We embark upon a systematic algorithmic study of the resiliency of immediate failover in a variety of models (with/without packet marking/duplication, etc.). We leverage our findings to devise new schemes for immediate failover and show, both theoretically and experimentally, that these outperform existing approaches.
|
|
