Browse Prior Art Database

Overflow/Fault Recovery Using Automatic Network Routing

IP.com Disclosure Number: IPCOM000101786D
Original Publication Date: 1990-Sep-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 8 page(s) / 260K

Publishing Venue

IBM

Related People

Ofek, Y: AUTHOR

Abstract

Communication networks are often designed with the possibility of data loss as a result of an overflow or link failure. This work presents a uniform and general approach for overflow and error recovery in a packet switch network. The packet are sent over network with the routing information in their header. All network's routes are reversible, and therefore, any packet can return to its source using the same routing information. In case of overflow or link failure, the headers of all packets involved are returned to their sources. The returning header paths have the highest priority, and as a result, the information on failure and overflow propagates in about the sum of the link delay (i.e., no queuing delay in the returning path).

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

Overflow/Fault Recovery Using Automatic Network Routing

       Communication networks are often designed with the
possibility of data loss as a result of an overflow or link failure.
This work presents a uniform and general approach for overflow and
error recovery in a packet switch network. The packet are sent over
network with the routing information in their header.  All network's
routes are reversible, and therefore, any packet can return to its
source using the same routing information.  In case of overflow or
link failure, the headers of all packets involved are returned to
their sources.  The returning header paths have the highest priority,
and as a result, the information on failure and overflow propagates
in about the sum of the link delay (i.e., no queuing delay in the
returning path).  So, this protocol provides very fast feedback to
source, with information on the packet ID and where the overflow
occurred or the location of a faulty link.

      This article has the following objectives:
1.   Explicit Overflow - if an overflow has occurred, the packet
sender (the source) should be notified in the shortest possible time,
which is the propagation delay in the network.  The information that
is returned to the source includes the packet identification (ID) and
where the overflow has occurred.
2.   Arbitrary Loss - any packet can be overflowed from the set of
packets in the buffers of output port.  As a result, it will be
possible to implement any arbitrary priority scheme at the output
port.
3.   Error Recovery - in the case of a link failure the headers of
all packets which should be routed through this link, are returned to
their sources, with the packet ID and the faulty link ID.  As a
result, the packet can be rescheduled for transmission via an
alternative path and any further use of this link is suspended.

      There are two major means for achieving these objectives:
1.   Memory Organization - the storage at the output port is not a
queue (FIFO), but a linear set of buffers which can be randomly
accessed.
2.   Reversed ANR - the automatic network routing (ANR) information
is preserved, and the system is configured such that the same ANR can
be used in both direction. The proposed recovery protocol is
completely distributed, and is performed independently by each link
adapter (port).

      The System's Operation In this section we describe some basic
principles of the system's operation, which are helpful in
understanding the recovery protocols.  The system is a
store-and-forward communication network, constructed of a full-duplex
links and link adapters (LAs) or ports.  Each LA has two sides for
serial receiving and transmitting, and is realized as one functional
unit (probably on one card).

      The Switching Requirements Each switching node has two basic
switching requirements. One relates to the total switching capability
from inputs to outputs, and the other relates to the swit...