NDLI: Algorithms for FaultTolerant Routing in CircuitSwitched Networks

Please wait, while we are loading the content...

Algorithms for FaultTolerant Routing in CircuitSwitched Networks

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Chaudhary, Amitabh Kolman, Petr Bagchi, Amitabha Scheideler, Christian
Copyright Year	2007
Abstract	In this paper we consider the k edgedisjoint paths problem kEDP, a generalization of the wellknown edgedisjoint paths problem. Given a graph $G=(V,E)$ and a set of terminal pairs or requests T, the problem is to find a maximum subset of the pairs in T for which it is possible to select paths such that each pair is connected by k edgedisjoint paths and the paths for different pairs are mutually disjoint. To the best of our knowledge, no nontrivial result is known for this problem for $k>1$. To measure the performance of our algorithms we use the recently introduced flow number F of a graph. This parameter is known to fulfill $F=O(\Delta \alpha^{-1} \log n)$, where $\Delta$ is the maximum degree, $\alpha$ is the edge expansion of G, and n is the number of vertices in G. We show that a simple greedy online algorithm achieves a competitive ratio of $O(k^3 F)$ which naturally extends the best known bound of $O(F)$ for $k=1$ to higher k. To achieve this competitive ratio, we introduce a new method of converting a system of k disjoint paths into a system of k lengthbounded disjoint paths. We also show that any deterministic online algorithm has a competitive ratio of $\Omega(k F)$. In addition, we study the k disjoint flows problem kDFP, which is a generalization of the previously studied unsplittable flow problem. The difference between the kDFP and the kEDP is that now we consider a graph with edge capacities and our requests are allowed to have arbitrary demands $d_i$. The aim is to find a subset of requests of maximum total demand for which it is possible to select flow paths such that all the capacity constraints are maintained and each selected request with demand $d_i$ is connected by k disjoint paths, each of flow value $d_i/k$. The kEDP and kDFP problems have important applications in faulttolerant virtual circuit switching, which plays a key role in optical networks.
Starting Page	141
Ending Page	157
Page Count	17
File Format	PDF
ISSN	08954801
DOI	10.1137/S0895480102419743
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	1
Volume Number	21
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2007-02-15
Access Restriction	Subscribed
Subject Keyword	greedy algorithms faulttolerant routing flow number multicommodity flow Graph theory Analysis of algorithms edgedisjoint paths
Content Type	Text
Resource Type	Article
Subject	Mathematics

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

Algorithms for fault-tolerant routing in circuit switched networks

The all-or-nothing multicommodity flow problem

All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs

Approximating Fractional Multicommodity Flow Independent of the Number of Commodities

Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

Distributed network utility maximization in wireless networks with a bounded number of paths

Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size

HAGR: Hole Aware Greedy Routing for Geometric Ad Hoc Networks

Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

Algorithms for FaultTolerant Routing in CircuitSwitched Networks

Similar Documents

Algorithms for fault-tolerant routing in circuit switched networks

The all-or-nothing multicommodity flow problem

All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs

Approximating Fractional Multicommodity Flow Independent of the Number of Commodities

Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

Distributed network utility maximization in wireless networks with a bounded number of paths

Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size

HAGR: Hole Aware Greedy Routing for Geometric Ad Hoc Networks

Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

Algorithms for FaultTolerant Routing in CircuitSwitched Networks