Fast Local Rerouting for Handling Transient Link Failures

Link failures are part of the day-to-day operation of a network due to many causes such as maintenance, faulty interfaces, and accidental fiber cuts. Commonly deployed link state routing protocols such as OSPF react to link failures through global link state advertisements and routing table recomputations causing significant forwarding discontinuity after a failure. Careful tuning of various parameters to accelerate routing convergence may cause instability when the majority of failures are transient. To enhance failure resiliency without jeopardizing routing stability, we propose a local rerouting based approach called failure insensitive routing. The proposed approach prepares for failures using interface-specific forwarding, and upon a failure, suppresses the link state advertisement and instead triggers local rerouting using a backwarding table. With this approach, when no more than one link failure notification is suppressed, a packet is guaranteed to be forwarded along a loop-free path to its destination if such a path exists. This paper demonstrates the feasibility, reliability, and stability of our approach     

A localized adaptive proportioning approach to QoS routing

In QoS routing, paths for flows are selected based on knowledge of resource availability at network nodes and the QoS requirements of flows. Several QoS routing schemes have been proposed that differ in the way they gather information about the network state and select paths based on this information. We broadly categorize these schemes into best path routing and proportional routing. The best path routing schemes gather global network state information and always select the best path for an incoming I-low,based on this global view. It has been shown that best path routing schemes require frequent exchange of network state, imposing both communication overhead on the network and processing overheads on the core routers. On the other hand, proportional routing schemes proportion incoming flows among a set of candidate paths. We have shown that it is possible to compute near-optimal proportions using only locally collected information. Furthermore, a few good candidate paths can be selected using infrequently exchanged global information and thus with minimal communication overhead. We describe these schemes in detail and demonstrate that proportional routing schemes can achieve higher throughput with lower overhead than best path routing schemes     

On localized control in QoS routing

In this note, we study several issues in the design of localized quality-of-service (QoS) routing schemes that make routing decisions based on locally collected QoS state information (i.e., there is no network-wide information exchange among routers). In particular, we investigate the granularity of local QoS state information and its impact on the design of localized QoS routing schemes from a theoretical perspective. We develop two theoretical models for studying localized proportional routing: one using the link-level information and the other using path-level information. We compare the performance of these localized proportional routing models with that of a global optimal proportional model that has knowledge of the global network QoS state. We demonstrate that using only coarser-grain path-level information it is possible to obtain near-optimal proportions. We then discuss the issues involved in implementation of localized proportional routing and present some practical schemes that are simple and easy to implement     

Adaptive proportional routing: a localized QoS routing approach

Most of the QoS routing schemes proposed so far require periodic exchange of QoS state information among routers, imposing both communication overhead on the network and processing overhead on core routers. Furthermore, stale QoS state information causes the performance of these QoS routing schemes to degrade drastically. In order to circumvent these problems, we focus on localized QoS routing schemes where the edge routers make routing decisions using only local information and thus reducing the overhead at core routers. We first describe virtual capacity based routing (vcr), a theoretical scheme based on the notion of virtual capacity of a route. We then propose proportional sticky routing, an easily realizable approximation of vcr and analyze its performance. We demonstrate through extensive simulations that adaptive proportional routing is indeed a viable alternative to the global QoS routing approach.