Browse Prior Art Database

Mechanism to Efficiently Determine that Certain Information does not Belong to a Given Set of Values

IP.com Disclosure Number: IPCOM000118364D
Original Publication Date: 1997-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 2 page(s) / 69K

Publishing Venue

IBM

Related People

Mauduit, D: AUTHOR [+4]

Abstract

Consider the following example application: a network is accessed by stations (such as LAN routers, identified by MAC addresses) through access facilities, generically called Network Ports. Suppose that the Network Port which attaches station S1 knows the route in the network to reach only a small set of stations (e.g., S2 and S3). If a message provided by station S1 contains a destination address which corresponds neither to S2 nor S3, the Network Port sends it to a Server on a predetermined route. That Server would, in turn, resolve the address search and then forward the message to the appropriate destination. So, it is important for the Network Port to efficiently determine that an input address does not belong to its address table in order to send the corresponding message to the Server.

This text was extracted from an ASCII text file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Mechanism to Efficiently Determine that Certain Information does
not Belong to a Given Set of Values

      Consider the following example application:  a network is
accessed by stations (such as LAN routers, identified by MAC
addresses) through access facilities, generically called Network
Ports.  Suppose that the

Network

Port

which attaches station S1 knows
the route in the network to reach only a small set of stations (e.g.,
S2 and S3).  If a message provided by station S1 contains a
destination address which corresponds neither to S2 nor S3, the

Network

Port

sends  it to a Server on a predetermined route.  That
Server would, in turn, resolve the address search and then forward
the message to the appropriate destination.  So, it is important for
the

Network

Port

to efficiently determine that an input address does
not belong to its address table in order to send the corresponding
message to the Server.  It is assumed that, out of N=2 sup n possible
addresses (e.g., n=48), only S=2 sup s (e.g., s=5) are present in the

Network

Port

  table.

      The conventional solutions, such as Contents Addressable
Memories (CAMs) or software table search algorithms, look for a table
match but do not favor the 'no-match' case.

      The solution described hereafter involves a Selected Address
Table (SAT), containing S 'known' addresses, a Key function which
provides a k-bit value calculated on the input address (e.g., k=8),
and a Key Match Table (KMT) consisting in K=2 sup k words of S bits,
the contents of which are explained hereafter.

      The KMT table is prepared in the followi...