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&#39;s partial match characteristics, may also be used to efficiently retrieve domain specific configuration data for an SMTP Message Transfer Agent

Description:
This application claims the benefit of U.S. Provisional Application Ser. No. 60/045,852, filed May 7, 1997. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates generally to a hierarchical memory mapping system and more particularly relates to a system that provides hierarchical table lookups for mapping across a multiprotocol messaging environment 
     2. Description of the Background 
     With tie explosive increase of traffic on the Internet, specifications standardizing the transfer of electronic messages are frequently being developed. For example, RFC 1327 specifies a standard mechanism for mapping between X.400 and Simple Mail Transfer Protocol (SMTP). Every mail gateway between X.400 and SMTP must follow this specification. One important aspect of this mapping involves the mapping of addresses. To facilitate the mapping of addresses, RFC 1327 specifies three global tables for maintaining equivalences between X.400 domain names and Internet domain names. The three tables are rfc2or, or2rfc and rfc1148gate. The rfc2or table maps Internet domain names into their equivalent X.400 O/R domains. The or2rfc table maps X.400 O/R domains into their equivalent Internet domain names. The rfc1148gate table maps Internet domain names to their preferred gateway name. The three tables are regularly updated by global naming authorities. Every name, whether it be an originator name, a recipient name or any type of copy name, is looked up in at least one of these tables. 
     The RFC 1327 specification requires that the best matching table entry, if any, be used. The best match is considered to be the longest matching domain name, according to that domain&#39;s hierarchy. Typically, this means that each name is looked up with its full domain name as the key. If that lookup fails, the domain is shortened by one element, a subdomain, and looked up again. This repeats until a matching entry is found, or there are no more subdomains. With thousands of entries in each mapping table, this process of a linear search throughout one or more global tables becomes burdensome, time-consuming and expensive. These costs are compounded by the fact that every address on every e-mail item must undergo these lookups. Furthermore, many addresses never match any table entries, thus amounting to wasted work. 
     SUMMARY OF THE INVENTION 
     It is therefore an object of the present invention to provide a system that efficiently and quickly maps messaging addresses across multiple protocols. 
     It is another object of the invention to provide a system that creates table lookups for mapping across a multiprotocol mail environment. 
     It is another object of the invention to provide a means for applying the RFC 1327 specification in a quick and efficient manner. 
     According to one embodiment of the present invention, these and other objects of the invention are achieved by providing a system that facilitates the mapping of addresses through constructing mapping tables into domain hierarchy trees, and searching the trees using a Trie search. The Trie search makes use of a key&#39;s representation as part of a domain name. Source data, which is preferably changed infrequently, is compiled into a hierarchical tree that is stored in a file. The file contains internal data structures that can be used simultaneously by multiple processes at different virtual addresses. Addresses are stored relative to the base of the map instead of as absolute values. A lookup code finds the longest match, if any, for a given key, in a very efficient manner. 
     Other objects, advantages and embodiments of the invention are set forth in part in the description which follows, and in part will be apparent from this description or may be learned from practice of the invention. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a messaging system over a multiprotocol environment. 
     FIG. 2 is a messaging subsystem of the system illustrated in FIG. 1. 
     FIG. 3 is a shared memory mapped file created by a preferred embodiment of the invention. 
     FIG. 4 is an excerpt of an RFC 1327 rfc2or table. 
     FIGS. 5(a)-5(c) are parts of a lookup tree of the RFC 1327 excerpt of FIG. 4 created according to a preferred embodiment of the invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The preferred embodiment of the present invention and its advantages are best understood by referring to FIGS. 1 through 5(c) of the drawings, like numerals being used for like and corresponding parts of the various drawings. 
     A messaging system over a multiprotocol environment according to a preferred embodiment of the invention is shown in FIG. 1. Clients, senders, receivers, and other communicators 10 communicate with each other via messaging gateways 14. Messaging protocols 12 define how messages are transferred between communicators 10 in different messaging environments. Messaging protocols include X.400, SMTP and other protocols that are developed to meet the expanding facilities for messaging. Each messaging gateway 14 has at least one shared memory mapped file 16 that enables quick and efficient mapping across different protocols. The memory mapped file 16 is shared among different processes in the same gateway. Typically, a gateway uses a plurality of memory mapped files such as described below. 
     FIG. 2, which is a subsystem of the communications network shown in FIG. 1, illustrates communications between X.400 18 and Simple Mail Transfer Protocol (SMTP) 20. The messaging gateway 22 transfers messages between X.400 18 and SMTP 20 through application of an RFC 1327 shared memory mapped file (&#34;RFC 1327 mmap file&#34;). The RFC 1327 mmap file specifies a set of mappings of high level network names between the two protocols 18 and 20. The RFC 1327 mmap file comprises memory mapped files for the three RFC 1327 mapping tables, rfc2or 24, rfc1148gate 26 and or2rfc 28. There is a separate mmap file for each mapping table. A preferred embodiment of the invention provides a domain hierarchy tree for any mapping between messaging protocols. For illustration purposes only, the mapping between X.400 and SMTP will be described in greater detail herein. It is readily understood, however, that the present invention is potentially applicable to any mapping across multiprotocol messaging environments. 
     Each RFC 1327 mapping table 24, 26 and 28 is created as a domain hierarchy tree, such as an M-ary tree, in its own memory mapped file. This allows the mapping to be created once and then efficiently shared amongst multiple processes. 
     Nodes in the domain hierarchy tree represent each subdomain in the mapping table. As defined by the Domain Name System (DNS), domains form a tree with each part of the name forming part of the sequence of ultimately resolving the name. 
     Each shared memory mapped file is preferably organized as illustrated in FIG. 3. CRC-32 30, which is a checksum, helps verify the table data integrity. Other similar means for verifying data integrity may be used. Since the memory mapped files represent internal data structures, a CRC-32 value is computed and stored in each of the memory mapped files for verification during initialization. This helps prevent use of a file that has been accidentally or intentionally corrupted. Preferably this check is made only at startup. 
     Version number 32 is the table format version number. The memory mapped file contains data structures having an implicit format Creation of a version number allows future implementations to change the format of the data structures without regard to backward compatibility. A version number mismatch will cause the map to be rebuilt 
     File size 34 and creation timestamp 36 are used to enhance uniqueness for the CRC. 
     Table offsets 38 construct pointers into the memory mapped file. These include offsets to the Domain table, Domain data and Domain strings. 
     Domain table 40 is the Trie matrix. The Trie preferably is implemented as an M×N matrix, where each column N is a vector length M addressed by subscript k in the range 0≦k≦M-1. M is a prime number and N represents the number of subdomains within the table. Each component (selected by k) of the vector represents a link to list of subdomain tree roots. The link may be NULL. Each of these roots may be a leaf node of the Trie or may actually be the root node of a new subdomain table (e.g., column). 
     Domain data 42 are the list nodes to which Trie vector components link. They form linked lists. Since the M-ary decision represented by each column vector in the table is potentially large, a hash function is used to select k and group the subdomain roots into the lists linked by each vector component In a preferred embodiment, the hash function HashPJW() is used. Alternatively, a similar general purpose hash function applicable for text keys may be used. 
     Domain strings 44 is a heap of string data which holds the key/value data. 
     If the memory mapped files are older than the source files, or if the memory mapped files are found to be corrupt, then the memory mapped files are compiled from the source tables during master initialization. 
     Per RFC 1327, the tree is searched to find the longest matching value for each given search key. The search interface returns the best matching value and the portion of the key used to find this value, so that non-matching elements of the key can be mapped according to the algorithms specified in RFC 1327. This reduces an address lookup to one memory based search. 
     When searching the table for a specific name, the name is broken into its component parts. For example, &#34;spyder.ssw.com&#34; is broken into &#34;com&#34;, &#34;ssw&#34; and &#34;spyder&#34;. The search starts at the root of the tree, column 0 in the array, and a hash function, hash(com) is used to select k. The list of subdomain tree roots linked by node k is linearly searched for the &#34;com&#34; domain. If &#34;com&#34; is potentially the end of a search, a value for the input key will be stored in the record for &#34;com&#34;. Optionally &#34;com&#34; links to a subdomain tree (the one in which &#34;ssw&#34; is found) and the search can continue until a leaf node is found. The search results in an exact match, partial match or no match. 
     This type of search is efficient. Unsuccessful searches go very fast. Moreover, since the search picks up values for the key along the way, the longest match for the key is always retrieved. 
     A cache is implemented as an array of cache entries where recently looked up values are placed into the array using HashPJW(). When doing a lookup, a hash is made on the input key and the selected cache entry is compared to the key. If it is a HIT, the value data may be directly extracted from the Domain Data. Otherwise, a table lookup is required. In order to avoid concurrency problems, the cache is maintained on a per process basis in its own local memory. 
     The linked lists of subdomain tree roots are lexically sorted in ascending order. This allows for reducing the amount of linear searching done on the lists by comparing the search key to the current list comparator. If the comparator is lexically greater than the search key, the linear search may be safely terminated without searching the entire list. 
     There is a separate mapping (and mapped file) for each table. The calling application decides when to search the tables and which table will be used for a search The invention constructs a plurality of mapping tables into lookup trees. For example, consider the excerpt from the &#34;rfc2or&#34; table illustrated in FIG. 4. The data from this table is mapped into a lookup tree 50 illustrated in FIGS. 5(a)-5(c). Although shown separately, FIGS. 5(a)-5(c) comprise one lookup tree. Each node in the lookup tree 50 represents each subdomain in the rfc2or table. The values &#34;it&#34;, &#34;com&#34; and &#34;be&#34; are mapped as roots 52, 54 and 56, respectively, in the lookup table 50. The table entry &#34;it:ADMD$garr.C$it&#34; 58 is mapped into branch 60. Similarly, table entry &#34;astro.it:O$@.PRMD$astro.ADMD$garr.C$it&#34; 62 is mapped into branch 64. Table entry &#34;jrc.it:PRMD$ccrispra.ADMD$garr.C$it&#34; 66 is mapped into branch 68. Table entry &#34;hac.com:O$SCG.PRMD$Hughes.ADMDSMCI.C$us&#34; 70 is mapped into branch 72. Table entry &#34;cdc.com:PRMD$CDC.ADMD$ATTMAIL.C$us&#34; 74 is mapped into branch 76. Table entry &#34;comtech.rrt.be:PRMD$comtech.ADMD$rttC$be&#34; 78 is mapped into branch 80. Table entry &#34;cec.be:PRMD$cec.ADMD$rtt.C$be&#34; 82 is mapped into branch 84. 
     Using the lookup tree 50, the address &#34;spyder.ssw.it&#34; quickly resolves to &#34;ADMD$garr.C$it&#34;. The name &#34;spyder.ssw.it&#34; is broken into its component parts &#34;it&#34;, &#34;ssw&#34; and &#34;spyder&#34;. The search starts at the root of the tree, column 0 in the array, and a hash function, hash(it) is used to select k. The list of subdomain tree roots linked by node k is linearly searched for the &#34;it&#34; domain. If &#34;it&#34; is potentially the end of a search, a value for the input key will be stored in the record for &#34;it&#34;. Optionally &#34;it&#34; links to a subdomain tree (the one in which &#34;ssw&#34; is found) and the search can continue until a leaf node is found. In this case, &#34;it&#34; is linked to subdomain trees &#34;jrc&#34; and &#34;astro&#34;, but not &#34;ssw&#34;. Accordingly, the search for the address corresponding to &#34;spyder.ssw.it&#34; retrieves the address &#34;ADMD$garr.C$it&#34;. 
     Other embodiments and uses of the invention will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. The specification should be considered exemplary only.