Analysis and Algorithms for Partial Protection in Mesh Networks

Abstract

This paper develops a mesh network protection scheme that guarantees a quantifiable minimum grade of service upon a failure within a network. The scheme guarantees that a fraction q of each demand remains after any single link failure. A linear program is developed to find the minimum cost capacity allocation to meet both demand and protection requirements. For q <- 1/2, an exact algorithmic solution for the optimal routing and allocation is developed using multiple shortest paths. For q > 1/2, a heuristic algorithm based on disjoint path routing is developed that performs, on average, within 1.4% of optimal, and runs four orders of magnitude faster than the minimum-cost solution achieved via the linear program. Moreover, the partial protection strategies developed Achieve reductions of up to 82% over traditional full protection schemes.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 29, 2011
Accession Number
ADA570528

Entities

People

  • Aradhana Narula-tam
  • Eytan Modiano
  • Greg Kuperman

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Contracts
  • Data Rate
  • Department Of Defense
  • Governments
  • Guarantees
  • Information Operations
  • Linear Programming
  • Mathematical Models
  • Mesh Networks
  • Network Topology
  • Simulations
  • Standards
  • United States
  • United States Government

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.