Browse Prior Art Database

Highly Reliable Networks with Short Disjoint Paths

IP.com Disclosure Number: IPCOM000107280D
Original Publication Date: 1992-Feb-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 2 page(s) / 73K

Publishing Venue

IBM

Related People

Hantler, SL: AUTHOR [+2]

Abstract

Disclosed is a technique for designing highly reliable networks with short disjoint paths between locations. To provide disjoint paths, each location consists of a pair of communication controllers. The pair of controllers also provides load balancing at each location. Controllers and lines may fail and a path is available if none of its controllers or lines has failed. Two locations can communicate with one another if there is at least one path available between a controller in one location and a controller in the other location. To obtain low delay and high reliability, each pair of locations must be connected by a one-hop path and a second path, disjoint from it.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Highly Reliable Networks with Short Disjoint Paths

       Disclosed is a technique for designing highly reliable
networks with short disjoint paths between locations.  To provide
disjoint paths, each location consists of a pair of communication
controllers.  The pair of controllers also provides load balancing at
each location.  Controllers and lines may fail and a path is
available if none of its controllers or lines has failed.  Two
locations can communicate with one another if there is at least one
path available between a controller in one location and a controller
in the other location.  To obtain low delay and high reliability,
each pair of locations must be connected by a one-hop path and a
second path, disjoint from it.  The shortest such disjoint path is
called the alternate path, whose existence is necessary and
sufficient to ensure that no single controller or line failure
disconnects the network.  For reasons of economy we seek a network
with as few lines as possible.

                            (Image Omitted)

      Whenever there are at least two locations we present a network
satisfying these conditions.

      For ease of exposition we adopt standard graph theoretic
notation throughout this article.  The controllers are the nodes, the
lines are the edges, and two nodes are adjacent if there is a line
between the controllers.  We seek a graph in which pairs of nodes are
identified as locations and we say that two locations are adjacent if
they contain a pair of adjacent nodes, one per location.

      To reiterate, we require a graph, G, with the following
properties:
      (1) Every pair of locations is adjacent.
      (2) Every pair of locations has (at least) two disjoint paths
between them.
      (3) No graph satisfyin...