Congestion-Oriented Shortest Multipath Routing

Abstract

The authors present a framework for the modeling of multipath routing in connectionless networks that dynamically adapt to network congestion. The basic routing protocol uses a short-term metric based on hop-by-hop credits to reduce congestion over a given link, and a long-term metric based on end-to-end path delay to reduce delays from a source to a given destination. A worst-case bound on the end-to-end path delay is derived under three architectural assumptions: each router adopts weighted fair queueing (or packetized generalized processor sharing) service discipline on a per destination basis, a permit-bucket filter is used at each router to regulate traffic flow on a per destination basis, and all paths are loop free. The shortest multipath routing protocol regulates the parameters of the destination-oriented permit buckets and guarantees that all portions of a multipath are loop free.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1996
Accession Number
ADA457722

Entities

People

  • J.J. Garcia-Luna-Aceves
  • Shree Murthy

Organizations

  • University of California, Santa Cruz

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Bandwidth
  • Computations
  • Computer Networks
  • Computing System Architectures
  • Congestion
  • Demographic Cohorts
  • Engineering
  • Flow
  • Guarantees
  • Internet Routing
  • Network Architecture
  • Networks
  • Routing Protocols
  • Scheduling (Production)
  • Steady State
  • Time Intervals

Fields of Study

  • Computer science

Readers

  • Computer Networking