NDLI: Tree based MPLS routing

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

Optimal sharing of bags of tasks in heterogeneous clusters

A practical algorithm for constructing oblivious routing schemes

Optimal fault-tolerant linear arrays

I/O-efficient topological sorting of planar DAGs

A proportionate fair scheduling rule with good worst-case performance

Performance comparison of MPI and three openMP programming styles on shared memory multiprocessors

Designing overlay multicast networks for streaming

Compact routing with name independence

Analysis of link reversal routing algorithms for mobile ad hoc networks

High throughput, parallelized 128-bit AES encryption in a resource-limited FPGA

The load rebalancing problem

Polynomial time algorithms for network information flow

Toward a decidable notion of sequential consistency

Information gathering in adversarial systems: lines and cycles

Minimizing total flow time and total completion time with immediate dispatching

A polynomial-time tree decomposition to minimize congestion

The effect of communication costs in solid-state quantum computing architectures

MST construction in O(log log n) communication rounds

Integrated prefetching and caching in single and parallel disk systems

Quantifying instruction criticality for shared memory multiprocessors

Combining online algorithms for rejection and acceptance

Tree based MPLS routing

On local algorithms for topology control and routing in ad hoc networks

MAPO: using a committee of algorithm-experts for parallel optimization of costly functions

Load balancing of unit size tokens and expansion properties of graphs

Improved approximation algorithms for the freeze-tag problem

Nonblocking k-compare-single-swap

A near optimal scheduler for switch-memory-switch routers

Online deadline scheduling: multiple machines and randomization

Online oblivious routing

VLSI layout of trees into grids of minimum width

Asynchronous parallel disk sorting

Off-line and on-line guaranteed start-up delay for media-on-demand with stream merging

Throughput-centric routing algorithm design

Worst case mobility in ad hoc networks

Buffer overflows of merging streams

Cycle stealing under immediate dispatch task assignment

Can we elect if we cannot compare?

Scheduling policies for CIOQ switches

Novel architectures for P2P applications: the continuous-discrete approach

TCP is competitive against a limited adversary

Short length menger's theorem and reliable optical routing

Randomized permutations in a coarse grained parallel environment

Relaxing the problem-size bound for out-of-core columnsort

Bicriteria approximation algorithms for scheduling problems with communications

The complexity of verifying memory coherence

Efficient galois field arithmetic on SIMD architectures

Tree based MPLS routing

Content Provider	ACM Digital Library
Author	Thorup, Mikkel Gupta, Anupam Kumar, Amit
Abstract	MPLS (MultiProtocol Label Switching) is a new technology proposed by the IETF [4,10] for network routing, and is being increasingly deployed by the largest Internet service providers. The MPLS technology differs from conventional network protocols in a crucial way: instead of reading the entire packet header at all switching points, the analysis of the packet header is done just once, when the packet header is assigned a stack of labels, and thenceforth, each switching point or router just gets to look at the label at the top of the stack (and the ingress edge), and based only on this information, it has to make a decision about the next-hop node [17,16]. In another departure from conventional routing and in particular from IP source routing, where the entire packet route is explicitly put in the header and popped off along the route, the router can not only pop the top label, it can push other labels on top of the stack.The two parameters of interest in designing MPLS routing protocols are the number of labels used, and the depth of the stack used for routing. Clearly, both cannot be simultaneously minimized, and there is often an interesting trade-off between label size and stack depth: it is obvious that if k labels are used, one must have a stack depth of $log_{k}$ n.In fact, it was not known whether this bound could be achieved even for trees; the best stack depth previously achieved with a constant number of labels was $O(log^{2}$ n). In this paper, we show that one can indeed get asymptotically optimal upper bounds and route on trees using k labels and a maximum stack depth of $O(log_{k}$ n), and that this trade-off can be achieved using a simpler and more intuitive protocol than the one given in [9]. These tree-routing ideas are then shown to give better routing protocols for planar graphs as well. In particular, we show how to route along near-shortest paths (of length at most (1 + ε) times the shortest-path) with $O(log^{2}$ n/ε) labels and logarithmic stack depth. We also apply them to graphs with smaller separators, including most large ISP networks.
Starting Page	193
Ending Page	199
Page Count	7
File Format	PDF
ISBN	1581136617
DOI	10.1145/777412.777443
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-06-07
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Networks Mpls routing Routing algorithms
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

QoS sensitive routing in DiffServ MPLS-TP networks

Traveling with a Pez Dispenser (or, Routing Issues in MPLS)

Online constraint-based routing as support for MPLS Traffic Engineering

Designing an Efficient MPLS-Based Switch for FAT Tree Network-on-Chip Systems

Multicast routing simulator over mpls networks (2002).

QoS-based MPLS multicast tree selection algorithms

Evaluation of MPLS P2MP distribution tree algorithms

Evaluation of MPLS P2MP Distribution Tree Algorithms

Multi-path constraint-based routing algorithms for MPLS traffic engineering

Tree based MPLS routing

Similar Documents

QoS sensitive routing in DiffServ MPLS-TP networks

Traveling with a Pez Dispenser (or, Routing Issues in MPLS)

Online constraint-based routing as support for MPLS Traffic Engineering

Designing an Efficient MPLS-Based Switch for FAT Tree Network-on-Chip Systems

Multicast routing simulator over mpls networks (2002).

QoS-based MPLS multicast tree selection algorithms

Evaluation of MPLS P2MP distribution tree algorithms

Evaluation of MPLS P2MP Distribution Tree Algorithms

Multi-path constraint-based routing algorithms for MPLS traffic engineering

Tree based MPLS routing