Browse Prior Art Database

Memory Organization Scheme for the Implementation of Routing Tables in High Performance IP Routers

IP.com Disclosure Number: IPCOM000103855D
Original Publication Date: 1993-Feb-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 4 page(s) / 164K

Publishing Venue

IBM

Related People

Abler, JM: AUTHOR [+4]

Abstract

In IP Routers, the identification of the next hop, its IP address and the corresponding output port is done by table lookup. The nature of this procedure is very complex and time consuming because it involves searching a match among entries having different masks. Proposed is a memory organization scheme using Content Addressable Memories and a Static RAM to find a match in a fixed number of memory cycles.

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

Memory Organization Scheme for the Implementation of Routing Tables in High Performance IP Routers

      In IP Routers, the identification of the next hop, its IP
address and the corresponding output port is done by table lookup.
The nature of this procedure is very complex and time consuming
because it involves searching a match among entries having different
masks.  Proposed is a memory organization scheme using Content
Addressable Memories and a Static RAM to find a match in a fixed
number of memory cycles.

      In a network using the Internet Protocol (IP), every node has a
unique 32-bit address, called the IP address.  An IP address is
composed of three fields: the type, the network identifier (NetId),
and the host identifier (HostId).  The type field specifies the
address class, which defines the respective length of each of the
fields as described below.  The network identifier is given to a
requesting organization by a central administration authority.  Large
networks belonging to large organizations are given a short network
identifier (7 bits) and a long host identifier (24 bits).  This
allows such organizations to install (and give unique host
identifiers) to 16 million nodes.  Most organizations, however, are
given a longer network identifier (14 bits) leaving 16 bits for
internal host identifiers.  This allows for 64K nodes.  Smaller
organizations are given 21 bit network identifiers and 8 bits for
local nodes.

      Usually, IP networks are partitioned into several smaller
subnetworks in a hierarchical way.  This is done by network
administrators who define their own fields within the HostId field.
This helps facilitate the network administration by allocating IP
address spaces to the local administrators without risking any
address duplication.  It also allows the use of location-sensitive
addressing (in a way similar to the phone numbering scheme), which
simplifies management and routing.

      Subnetworks (and networks) are interconnected by Routers.
Typically, a router may have several ports, each of which is
connected to a different subnetwork.  All the subnetworks forming the
networks that constitute the Internet (the global IP network) are
connected by these routers, forming a large mesh.  It is possible to
send an IP packet (called datagram) from any source node to any
destination node on the Internet.  Such a datagram carries, in
specific fields, the IP addresses of both the source and destination
nodes.  The source examines the destination address to determine its
direct accessibility on the same subnetwork (in this case both
addresses contain the IP SubnetId of the same physical subnetwork).
This is done by a masked comparison, where the mask is defined by the
local network administrator.  If the destination does not reside on
the same physical subnetwork as the source, the datagram has to be
sent to a Next Hop Router (NHR) that will gradually forward the
datagram one step further...