Mapping table lookup optimization system

• US 6,035,326 A
• Filed: 09/08/1997
• Issued: 03/07/2000
• Est. Priority Date: 05/07/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Miles, Robert S., Fox, Jason P.
• Primary Examiner(s): Asta, Frank J.
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US08/925,180
• Time in Patent Office: 911 Days
• Field of Search: 395/200.6, 395/200.66, 395/200.76, 395/200.36, 395/182.02, 395/182.01, 395/600, 395/557, 395/602, 395/650, 370/466, 370/467, 707/100, 707/101, 707/104, 707/2, 707/3, 707/10, 709/206, 709/227
• US Class Current: 709/206
• CPC Class Codes: H04L 51/066 Format adaptation, e.g. format conversion or compression
• CPC Class Codes: H04L 51/48 Message addressing, e.g. address format or anonymous messages, aliases
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming

Abstract

The present invention is a system and method for creating lookup trees of mapping specifications for multiprotocol messaging environments. Source data, which is preferably updated infrequently, is compiled into a hierarchical tree, which is stored in a file. The file contains internal data structures that can be used simultaneously by multiple processes at different virtual addresses. A lookup code finds the longest match, if any, for a given key, in a very efficient manner. In a preferred embodiment, the present invention efficiently maps names between X.400 and SMTP per the RFC1327 specification. The organization of the keys, along with the present invention'"'"'s partial match characteristics, may also be used to efficiently retrieve domain specific configuration data for an SMTP Message Transfer Agent

Claims

1. A method for mapping addresses in a first messaging format into a second messaging format using table lookup optimization, said method comprising:

constructing a plurality of mapping tables into at least one lookup tree, said

at least one lookup tree comprising at least one lookup tree root and at least one subdomain tree linked to said lookup tree root, said subdomain tree comprising at least one subdomain tree root;

searching said at least one lookup tree, said step of searching comprising;

receiving an address in a first messaging format;

dividing said address into a plurality of component parts;

matching at least one of said component parts with one of said at least one lookup tree;

using a hash function to operate upon said at least one lookup tree to select a lookup tree root;

accessing a per process cache to determine if said lookup tree root matches a selected cache entry;

returning a result in a second messaging format if a match is found;

if a match is not found, proceeding to linearly search said at least one subdomain tree root linked by said lookup tree root; and

returning a best match subdomain root corresponding to said address in a second messaging format.

2. The method of claim 1, wherein said step of linearly searching comprises:

searching said subdomain tree roots for a longest matching value; and

selecting the subdomain tree root having said longest matching value.

3. The method of claim 1,

wherein said step of accessing a per process cache comprises accessing an array of recently looked-up values.

4. The method of claim 3, wherein said recently looked-up values are placed into said array using a hash function.

5. A system for mapping table lookup optimization comprising:

a sender, said sender communicating with a first messaging protocol;

at least one receiver, said receiver communicating with a second messaging protocol; and

at least one messaging gateway in communication with said sender and said at least one receiver, said messaging gateway comprising a shared memory mapped file; and

a per process memory cache;

wherein said shared memory mapped file comprises;

at least one table offset;

a domain table;

a plurality of domain data; and

at least one domain string;

wherein said table offset constructs a plurality of pointers into said domain table, into said plurality of domain data, and into said at least one domain string.

6. The system of claim 5, wherein said shared memory mapped file applies the RFC 1327 protocol.

7. A system for mapping table lookup optimization for use in a messaging system having at least one client operating with a first message protocol and at least one other client operating with a second message protocol said system comprising:

a messaging gateway;

a shared memory mapped file, wherein said shared memory mapped file further comprises mapping tables configured as hierarchical trees;

wherein said hierarchical trees comprise;

at least one domain table,

at least one domain data list, and

at least one domain string;

said hierarchical trees further comprising table offsets, which construct pointers into said shared memory mapped file; and

a per process memory cache.

8. The system of claim 7 wherein said hierarchical trees further comprise a checksum module to verify data integrity.

9. The system of claim 7 wherein said hierarchical trees further comprise a version number indicating the revision number of said hierarchical trees.

10. The system of claim 7 wherein said hierarchical trees further comprise at least one uniqueness indicator which assists in uniquely identifying said hierarchical trees.

11. The system of claim 10 wherein said uniqueness indicator is a representation of said hierarchical tree file size.

12. The system of claim 10 wherein said uniqueness indicator is a timestamp indicating a time.

13. The system of claim 7 wherein said at least one domain table comprises a matrix containing links to a list of subdomain tree roots.

14. The system of claim 7 wherein said at least one domain data list comprises listings of subdomain tree roots.

15. The system of claim 7 wherein said at least one domain string comprises key value data.

16. A system for mapping table lookup optimization for use in a messaging system having at least one client operating with a first message protocol and at least one other client operating with a second message protocol said system comprising:

messaging gateway means;

shared memory mapped file means, wherein said shared memory mapped file means further comprise mapping table means configured as hierarchical tree means;

wherein said hierarchical tree means comprises;

domain table means;

domain data list means, and

domain string means;

said hierarchical tree means further comprising table offset means, which construct pointer means into said shared memory mapped file means; and

a per process memory cache means.

17. The system of claim 16 wherein said hierarchical tree means further comprise a checksum means to verify data integrity.

18. The system of claim 16 wherein said hierarchical tree means further comprise a version number means for indicating the revision number of said hierarchical tree means.

19. The system of claim 16 wherein said hierarchical tree means further comprise at least one means for indicating uniqueness which assists in uniquely identifying said hierarchical tree means.

20. The system of claim 19 wherein said means for indicating uniqueness is a means for representing file size.

21. The system of claim 19 wherein said means for indicating uniqueness is a means for indicating a time.

22. The system of claim 16 wherein said domain table means comprises a matrix containing links to a list of subdomain tree roots.

23. The system of claim 16 wherein said domain data list means comprises listings of subdomain tree roots.

24. The system of claim 16 wherein said domain string means comprises key value data.

25. A computer usable medium having computer readable code embodied therein for enabling a system for mapping table lookup optimization for use in a messaging system having at least one client operating with a first message protocol and at least one other client operating with a second message protocol said system comprising:

a messaging gateway;

computer readable code that identifies a shared memory mapped file, wherein said shared memory mapped file further comprises computer readable code identifying mapping tables configured as computer readable code for hierarchical trees;

wherein said computer readable code for hierarchical trees comprises;

computer readable code for at least one domain table,

computer readable code for at least one domain data list, and

computer readable code for at least one domain data string;

said computer readable code for hierarchical trees further comprising computer readable code for table offsets, which construct computer readable code for pointers into said computer readable code that identifies a shared memory mapped file; and

computer readable code for a per process memory cache.