Methods, systems and computer program products for hashing...

Details Methods, systems and computer program products for hashing... Methods, systems and computer program products for hashing...

1998-12-10

2004-08-31

Nguyen, Hanh (Department: 2662)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395310, C711S202000, C711S208000

Reexamination Certificate

active

06785278

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to network routing in general, and in particular to hashing address values for network communications.
BACKGROUND OF THE INVENTION
In network communications, it is often necessary to determine routing paths or other addressing in light of a destination address in a message to be routed. For example, in the Transmission Control Protocol/Internet Protocol (TCP/IP) the destination address may be an IP address which may be utilized to determine the address of the next jump in the route of the message. The IP address is a 32 bit address which identifies the destination of the message. This 32 bit address may be mapped to labels (numbers with fewer bits than the address) so as to increase the speed with which the next address in the route or other address based determinations may be made. Thus, the 32 bit address may, for example, be hashed to 16 bits which are then associated with routing rules. Such a use of a hash function in IP routing is well known to those of skill in the art. For example, U.S. Pat. No. 5,708,659 entitled Method for Hashing in a Packet Network Switching System describes such a routing system.
One problem of hashing occurs with “collisions” of hash values. Ideally, each address would hash to a unique value such that no two addresses result in the same hash values. However, in practice, address values may hash to the same hash value which may result in ambiguity as to which rules are to be utilized to route a message. Thus, further processing is generally required to determine the rule which is to be applied. Accordingly, hash functions which reduce the number of hash collisions are more desirable for routing applications.
Typically, hash functions are one directional in that the address which generates the hash value may not be determined from the hash value. Thus, in general, if a collision occurs the full address which generated the hash value must be utilized and a search restarted to resolve the ambiguity. Such operations may reduce the efficiency of the hash operations in the event of collision.
Examples of various hash functions are utilized in routing systems are described in U.S. Pat. Nos. 4,215,402, 5,247,620, 5,414,704, 5,530,834, 5,566,170, 5,740,171, and 5,757,795. Similarly, other hash functions in differing contexts are described in IBM Technical Disclosure Bulletin, Vol. 16, No. 3, pp. 694-69 (August 1973) and IBM Technical Disclosure Bulletin Vol., Vol. 24, No. 6, pp. 2724-2726 (November 1981).
While these hash functions may provide acceptable performance in many routing systems, as routing systems become larger and more complex, hash functions which reduce collisions while still maintaining performance advantages of hashing may become more critical to the performance of the routing system. Furthermore, hashing functions which, together with a complementary function, are invertible may be even more beneficial in that the need to restart a search with the original address may be avoided in the event of a hash collision. Thus, further improvements in hashing functions may still be desirable.
SUMMARY OF THE INVENTION
In light of the above discussion, it is an object of the present invention to provide methods, systems and computer program products for hashing address values.
It is a further object of the present invention to provide such methods, systems and computer program products which reduces hash collisions while providing reduced bits.
It is a further object of the present invention to provide an address hashing function which is invertible.
These and other objects are provided, according to the present invention, hashing address values that exhibit banding in a plurality of regions of an address space defined by at least two segments of the address values, by performing at least one of a translation and a rotation of the at least two segments to thereby map the at least two segments from the plurality of regions to one of the plurality of regions. Furthermore, these hash values may be used for selecting an action from a plurality of actions based on the mapped at least two segments. In particular, the hashed values may be used for selecting an action from a plurality of data network routing actions.
In particular embodiments of the present invention, the translation and/or rotation is provided by dividing an address space defined by the at least two segments of the address values into at least four regions. The values of the at least two segments corresponding to a second region of the at least four regions are translated to a first region of the at least four regions. Values for the at least two segments corresponding to a third region and a fourth region of the at least four regions are flipped into the first region to provide hash values. The third region and the fourth region are regions other than the first and the second regions. The translated and/or flipped values of the segments are then utilized as hash values for address values.
In particular the flipping operations may be performed by mirroring the values of the at least two segments about an axis dividing the first region from the third region to provide first, third region, mirrored values of the at least two segments corresponding to the third region. Values of the at least two segments are mirrored about an axis dividing the first region from the fourth region to provide first, fourth region, mirrored values of the at least two segments corresponding to the fourth region. The first, third region, mirrored values are then mirrored so as to rotate the values about an axis midway between the first region and the third region to provide second, third region, mirrored values. The first, fourth region, mirrored values are also mirrored so as to rotate the values about an axis midway between the first region and the fourth region to provide second, fourth region, mirrored values. The second, third region, mirrored values are mirrored so as to rotate the values about an axis diagonal across the first region and the second, fourth region, mirrored values are also mirrored so as to rotate the values about an axis diagonal across the first region.
Furthermore, the bit values from segments other than the at least two segments may be EXCLUSIVE ORed with the hash values.
In a further embodiment of the present invention, a plurality of hash values may be determined for permutations of segments of the address values and EXCLUSIVE ORed together. A cyclic shift of the bits of the plurality of hash values may be performed prior to EXCLUSIVE ORing the hash values together.
In a further embodiment, the values of the bits from other segments EXCLUSIVE ORed with the hash values are stored as the complement of the hash value.
In still another embodiment of the present invention, the translation and rotation may be performed by determining a first set of bits of the hash value based on the inverted bit values of a first segment of the at least two segments and a second set of bits of the hash value based on the inverted bits of a second segment of the at least two segments if either a most significant bit of the first segment or a most significant bit of the second segment is a logical 1 value. Bits of the first segment other than the most significant bit of the first segment may then be utilized as the first set of bits and bits of the second segment other than the most significant bit of the second segment utilized as the second set of bits of the hash value if the most significant bit of the first segment and the most significant bit of the second segment have the same logical value.
In a specific embodiment, a 16 bit hash values is determined by determining a 14 bit hash value (H[
31
] through H[
18
] utilizing the logical operations of:
H[
31
]=((g AND A[
6
]) XOR (f AND (NOT B[
6
]))) XOR C[
6
]
H[
30
]=((g AND A[
5
]) XOR (f AND (NOT B[
5
]))) XOR C[
5
]
H[
29
]=((g AND A[
4
]) XOR (f AND (NOT B[

Affiliated with

Also associated with

Rating

Methods, systems and computer program products for hashing... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods, systems and computer program products for hashing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods, systems and computer program products for hashing... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3336140