Browse Prior Art Database

Dynamic Addressing Scheme Applied to Routing Functions

IP.com Disclosure Number: IPCOM000113894D
Original Publication Date: 1994-Oct-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 94K

Publishing Venue

IBM

Related People

Creteny, A: AUTHOR [+5]

Abstract

This paper discloses the implementation of an addressing scheme used in a communication node for routing data packets. A frame-relay frame handler is taken as an example to explain the rationale and to illustrate the solution.

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

Dynamic Addressing Scheme Applied to Routing Functions

      This paper discloses the implementation of an addressing scheme
used in a communication node for routing data packets.  A frame-relay
frame handler is taken as an example to explain the rationale and to
illustrate the solution.

      Need for an efficient addressing scheme - The throughput of a
communication node such as a bridge or a router is directly dependent
on the time needed to find out where an incoming data packet is to be
sent.  Generally a fixed length field is to be extracted from the
incoming data unit.  This field is then matched with an entry in a
table where routing information has been stored by some
initialization process.

      The technique for retrieving routing information results from a
tradeoff between hardware cost and efficiency.  For example, hardware
devices such as Contents Addressable Memories (CAM) provide the best
performance at the expense of cost and complexity.  On the other end,
a table search implemented in software results in a much lower cost
but requires careful organization to be efficient.

      Frame-relay example - To illustrate the proposed solution, we
consider a frame-relay Frame Handler equipped with 128 communication
interfaces (hereafter referred to as lines).  On every line a Virtual
Circuit (VC) is identified by its local 10-bit Data Link Channel
Identifier (DLCI).  Thus every frame entering the frame handler
equipment can be linked to its destination VC by the means of a 17
bit identifier - 7-bit line number + 10-bit DLCI.

      A direct table lookup would be very fast but would waste
memory.  It would require an array of about 128000 entries even if
few VCs are active.

      The proposed solution involves two table lookup operations.  It
is based on the fact that DLCI values are not assigned randomly.
Some values are defined for all lines (e.g., DLCI 0 is used for
signalling and maintenance), some are never used (e.g., DLCI x
through y are defined as "reserved" by standards).  Moreover, in the
case of permanent VCs, DLCI assignment can be chosen by the network
administrator in order to optimize the use of equipment resources.

      Data structures - DLCI table:  This 1024-entry table is indexed
by a 10-bit DLCI number.  Every entry contains two fields: an index
and a 2-bit index modifier.  The Table explains the usage of the
index and index modifier fields.

      Routing Information Table (RIT):  Every row of this array
contains all information pertaining to a given VC such as VC status,
destination node, ...  Its detailed contents are beyo...