Method and apparatus for routing messagers in an electronic messaging system

• US 5,459,717 A
• Filed: 03/25/1994
• Issued: 10/17/1995
• Est. Priority Date: 03/25/1994
• Status: Expired due to Term

• Current Assignee: Sprint International Communications Corp. (Deutsche Telekom AG)
• Original Assignee: Sprint International Communications Corp. (Deutsche Telekom AG)
• Inventors: Roger, Fernando, Mullan, John A.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): BLUM, RUSSELL
• Application Number:
  US08/217,903
• Time in Patent Office: 571 Days
• Field of Search: 370/54, 370/58.2, 370/60, 370/92, 370/110.1, 370/58.1, 370/58.3, 379/93, 379/220, 379/90, 379/94, 340/825.52, 340/825.53
• US Class Current: 370/351
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00

Abstract

A method and apparatus for routing a message embodied in a signal received by an electronic messaging system includes formatting a search key using address codes parsed from a user address specified in the message, where each of the address codes corresponds to a different level of specificity for the user address. An attempt is made to retrieve a record from a database of routing information using the search key. If no record is found, the address code corresponding to the most detailed level of specificity in the user address is stripped from the search key and another attempt is made to retrieve a record. This process continues until a record is successfully retrieved from the database or a predetermined base level of specificity is reached.

Claims

1. A method for routing a message encoded in a signal received by an electronic messaging system, the electronic messaging system including a data store of routing information, the message containing a user address having a plurality of address codes, the method comprising:

(a) setting a search level indicator according to a number of address codes in the user address;

(b) attempting to retrieve routing information associated with the plurality of address codes in the user address;

(c) eliminating one of the plurality of address codes from the user address if no routing information is retrieved;

(d) repeating steps (a) through (c) until routing information is successfully retrieved or the search level indicator equals a predetermined base level; and

(e) in the event routing information is successfully retrieved, routing the message according to said routing information.

2. The method of claim 1 wherein the one of the plurality of address codes eliminated from the user address corresponds to a most specific level of address information contained in the user address.

3. The method of claim 2 wherein the step of attempting to retrieve routing information includes a binary search of the routing information data store.

4. The method of claim 3 wherein the binary search includes pattern matching to determine whether a match for the plurality of address codes exists in the routing information data store.

5. The method of claim 2 further comprising the step of indicating an invalid user address if no routing information is retrieved within the predetermined number of attempts.

6. A method for routing a message encoded in a signal received by an electronic messaging system, the electronic messaging system including a routing information database containing a plurality of routing path records keyed by user addresses, the message containing a user address having a plurality of address codes corresponding to different levels of specificity, the method comprising:

(a) setting a search level indicator to a number of address codes in the user address of the message, the search level indicator corresponding to a current level of specificity;

(b) formatting a search key using a set of address codes parsed from the user address and corresponding to the current level of specificity;

(c) attempting to retrieve a routing path record associated with the search key;

(d) decrementing the search level indicator if no routing path record is retrieved; and

(e) repeating steps (b) through (d) until a routing path record is successfully retrieved or the search level indicator equals a predetermined base level.

7. The method of claim 6 wherein the step of attempting to retrieve a path record comprises a binary search of the plurality of routing path records.

8. The method of claim 7 wherein the binary search includes pattern matching to determine whether a match for the search key exists.

9. The method of claim 6 further comprising the step of routing the message according to information contained in a retrieved routing path record.

10. The method of claim 9 further comprising the step of indicating an invalid user address when the search level indicator equals the predetermined base level.

11. A message transfer device for routing a message encoded in a signal received by an electronic messaging system including a memory and a routing information dataset stored therein, the routing information dataset associating communications paths with user addresses, the message including a user address comprising a plurality of address codes, the message transfer device comprising:

(a) a search key generator adapted to format a search key comprising a set of address codes parsed from the user address of the message;

(b) a database access module capable of retrieving routing information from the routing information dataset; and

(c) a routing module coupled to the search key generator and the database access module, the routing module adapted to coordinate an iterative search of the routing information dataset using a search key comprising a progressively decreasing number of address codes.

12. The message transfer device of claim 11 wherein the iterative search uses a search key corresponding to a progressively less specific set of address codes.

13. The message transfer device of claim 12 wherein the routing module is adapted to transmit the message to an intended recipient according to the retrieved routing information.

14. The message transfer device of claim 13 wherein the database access module is adapted to perform a binary search of the routing information dataset.

15. A message transfer device for routing a message in an electronic messaging system including a memory, the message including a plurality of address codes, the message transfer device comprising:

(a) a search key generator adapted to parse a subset of the plurality of address codes from the message and use the subset of the plurality of address codes to format a search key, the search key generator further adapted to reformat the search key by eliminating one of the subset of the plurality of address codes, wherein the search key generator maintains a search level indicator corresponding to a number of address codes in the search key;

(b) a routing information dataset stored in the memory of the electronic messaging system, the routing information dataset containing a plurality of routing path records associating a communications path with user address information;

(c) a data access module capable of retrieving a routing path record having user address information corresponding to the search key; and

(d) a routing module coupled to the search key generator and the data access module, the routing module capable of transmitting a message along a communications path specified in a retrieved routing path record and adapted to coordinate an iterative operation comprising;

(i) attempting to retrieve a routing path record corresponding to the search key using the data access module,

(ii) indicating whether a routing path record was successfully retrieved by the data access module, and

(iii) reformatting the search key using the search key generator if a routing path record was not successfully retrieved.

16. The message transfer device of claim 15 wherein the routing information dataset comprises a dataset sorted by user address information.

17. The message transfer device of claim 16 wherein the data access module performs a binary search of the plurality of routing path records.

18. The message transfer device of claim 17 wherein the message conforms to X.400 standards.

19. The message transfer device of claim 15 wherein the routing information dataset comprises a direct access dataset keyed by user address information.

20. A message transfer device for routing a message in an electronic messaging system having a memory coupled thereto, the message including an externally meaningful address corresponding to an intended recipient, the message transfer device comprising:

(a) an address translator adapted to convert an externally meaningful address to an internal address reflecting a configuration of the electronic messaging system;

(b) a search key generator adapted to parse a set of address codes from the internal address and use the set of address codes to format an initial search key, the search key generator further adapted to reformat a search key by eliminating one of the set of address codes from the search key;

(c) a routing information dataset stored in the memory coupled to the electronic messaging system, the routing information dataset containing a plurality of routing path records associating a communications path with user address information;

(d) a data access module capable of retrieving a routing path record having user address information corresponding to the set of address codes in the search key; and

(e) a routing module coupled to the search key generator and the data access module, the routing module capable of transmitting a message along a communications path specified in a retrieved routing path record and adapted to coordinate an iterative operation beginning with a search key formatted by the search key generator, the iterative operation comprising;

(i) attempting to retrieve a routing path record corresponding to the search key using the data access module,

(ii) indicating whether a routing path record was successfully retrieved by the data access module, and

(iii) reformatting the search key using the search key generator if a routing path record was not successfully retrieved.

21. The message transfer device of claim 20 wherein the address translator comprises a conversion table stored in a memory of the electronic messaging system and including a plurality of table entries associating internal address codes with external address codes.

22. A method for routing a signal received by a switching device, the switching device including a memory associating routing information with user address information, the signal containing an encoded representation of a user address comprising a plurality of address codes, the method comprising the steps of:

(a) analyzing the received signal to identify the plurality of address codes encoded therein;

(b) formatting a search key using the plurality of address codes;

(c) setting a search level indicator according to the number of address codes in the search key;

(d) attempting to retrieve routing information from the memory associated with the plurality of address codes in the search key;

(e) eliminating one of the plurality of address codes from the search key if no routing information is successfully retrieved;

(f) repeating steps (c) through (e) until routing information is successfully retrieved or the search level indicator equals a predetermined level; and

(g) in the event routing information is successfully retrieved, routing the signal according to the retrieved routing information.

23. The method of claim 22 wherein the step of analyzing the received signal comprises parsing address codes from predetermined positions of the received signal, the predetermined positions corresponding to portions of an electronic messaging address in which each of a plurality of address codes represents a unique degree of specificity.