Routing in Networks.

Abstract

This report is concerned with routing protocols in networks. The major result is a low bound for any oblivious routing strategy where the route of a packet depends only on the source and destination of the packet. We show that for any oblivious routing protocol for a network of n processors in which the maximum number of processors directly connected to any processor is d, there exists a permutation that requires time (sq. root of n) d (to the 3/2). For specific networks such as an n-cube we give an oblivious routing algorithm whose performance is close to this lower bound. (Author)

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1981
Accession Number
ADA107841

Entities

People

  • Allan Borodin
  • John E. Hopcroft

Organizations

  • Cornell University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Communication Systems
  • Communications Protocols
  • Computer Communications
  • Mathematics
  • Permutations
  • Routing Protocols

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.
  • Neural Network Machine Learning.