NDLI: Resilient routing of variable traffic with performance guarantees

Content Provider	IEEE Xplore Digital Library
Author	Kodialam, M. Lakshman, T.V. Orlin, J.B. Sengupta, S.
Copyright Year	2009
Description	Author affiliation: Bell Laboratories, Alcatel-Lucent, Murray Hill, NJ, USA (Kodialam, M.; Lakshman, T.V.) \|\| Microsoft Research, Redmond, WA, USA (Sengupta, S.) \|\| Massachusetts Institute of Technology, Cambridge, USA (Orlin, J.B.)
Abstract	Two-phase routing, where traffic is first distributed to intermediate nodes before being routed to the final destination, has been recently proposed [11], [12], [20] for handling widely fluctuating traffic without the need to adapt network routing to changing traffic. Pre-configuring the network in a traffic independent manner using two-phase routing simplifies network operation considerably. In this paper, we extend this routing scheme by providing resiliency against link failures through shared backup path restoration. We view this as important progress towards adding carrier-class reliability to the robustness of the scheme so as to facilitate its future deployment in Internet Service Provider (ISP) networks. In shared backup path restoration, each connection consists of a link-disjoint primary and backup path pair - two backup paths can share bandwidth on their common links if their primary paths are link disjoint. We show that the optimization problem for maximum throughput two-phase routing with shared backup path restoration is NP-hard. Assuming an approximation oracle for a certain disjoint paths problem (called SBPR-DISJOINT-PATHS, which is also NP-hard) involving the dual variables of a path indexed linear programming formulation for the problem, we design a combinatorial algorithm with provable guarantees. We also provide heuristics for finding approximating solutions to the SBPR-DISJOINT-PATHS problem. We evaluate the throughput performance and number of intermediate nodes in two-phase routing for the above and other restoration mechanisms for two-phase routing on actual ISP topologies collected for the Rocketfuel project [18].
Starting Page	213
Ending Page	222
File Size	210045
Page Count	10
File Format	PDF
ISBN	9781424446353
ISSN	10921648
DOI	10.1109/ICNP.2009.5339683
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-10-13
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Routing Telecommunication traffic Throughput Robustness Web and internet services Bandwidth Linear programming Algorithm design and analysis Approximation algorithms Topology
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Throughput Guaranteed Restorable Routing Without Traffic Prediction

Locally Restorable Routing of Highly Variable Traffic

A dynamic bandwidth guaranteed routing using heuristic search for clustered topology

On Configuring BGP Route Reflectors

QoS routing algorithm based on multiclasses traffic load

Topology design for service overlay networks with bandwidth guarantees

Guaranteed Performance Routing of Unpredictable Traffic With Fast Path Restoration

Design and performance of a distributed dynamic clustering algorithm for ad-hoc networks

On egress router selection for inter-domain traffic with bandwidth guarantees

Resilient routing of variable traffic with performance guarantees

Similar Documents

Throughput Guaranteed Restorable Routing Without Traffic Prediction

Locally Restorable Routing of Highly Variable Traffic

A dynamic bandwidth guaranteed routing using heuristic search for clustered topology

On Configuring BGP Route Reflectors

QoS routing algorithm based on multiclasses traffic load

Topology design for service overlay networks with bandwidth guarantees

Guaranteed Performance Routing of Unpredictable Traffic With Fast Path Restoration

Design and performance of a distributed dynamic clustering algorithm for ad-hoc networks

On egress router selection for inter-domain traffic with bandwidth guarantees

Resilient routing of variable traffic with performance guarantees