Electrical computers and digital processing systems: multicomput – Computer-to-computer data addressing
Reexamination Certificate
1999-12-15
2003-04-22
Coulter, Kenneth R. (Department: 2142)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data addressing
C709S206000
Reexamination Certificate
active
06553425
ABSTRACT:
BACKGROUND OF THE INVENTION
1. The Field of the Invention
The present invention relates to electronic communications. Specifically, the present invention relates to methods, computer program products and systems for breadth-first, asynchronous expansion of distribution lists with throttling control.
2. The Prior State of the Art
E-mail systems typically use a directory service (sometimes hereinafter referred to as the “DS”) or database to look up the locations of mailboxes of intended recipients specified in an e-mail message. Typically, two types of records are recognized—mailboxes and distribution lists. A mailbox record directly specifies the location, in terms of an exact storage location on a specified server, of the mailbox itself. Sending e-mail to a mailbox recipient has the effect of delivering the mail to the specified storage location.
On the other hand, a distribution list (sometimes referred to hereinafter as a “DL”) is an e-mail recipient that is actually a list of mailbox recipients and/or other distribution lists. A distribution list is a data record kept in a directory service or a database, wherein the data record has an attribute that represents the members of the distribution list. The members are represented as pointers to other records in the directory service or database. The pointers can be to mailbox records or other distribution lists. Sending e-mail to a distribution list has the effect of sending e-mail to all members of that list.
To identify all of the mailbox recipients contained in a particular distribution list, requires expansion of the distribution list. And since distribution lists can also contain other distribution lists as members, any method used to expand a distribution list must also be capable of handling the situation of a circular reference. As shown in
FIG. 1
, distribution lists can be graphically represented as a tree, wherein the individual members of the distribution list are related to one another in a hierarchical fashion.
Most e-mail systems found in the prior art use a “depth-first” method of expanding distribution lists. In simple terms, this means the system resolves each branch of a distribution list tree until it reaches a leaf node before proceeding on to a different branch of the distribution list tree. The current algorithm for expanding DLs in a depth-first manner is:
Procedure Expand(Record record, Stack parents)
Begin
DirectoryService.Lookup (record);
If (record.type==mailbox)
Save(record.storage Location);
return;
End If
parents.push(record);
For each records.member
If (not parents.find(record.member[I]))
Expand(record.member, parents)
Else
//circular loop—do nothing
return;
End For
End Procedure
The foregoing algorithm has the characteristic that the directory service lookup operation (“DirectoryService.Lookup”) happens once for each member of a distribution list, and the next lookup operation will not occur until the current lookup operation has finished and returned the data record. In the event that the directory service is located on a different server than the server of the e-mail system, the lookup operation may have a high latency. If this latency were x seconds per lookup, the algorithm set forth above would require n*x seconds to complete the expansion of the entire distribution List, where n is the number of members. However, depth-first has the advantage of being relatively efficient in terms of the amount of system resources necessary to complete an expansion process. As a general rule, the amount of system resources needed to complete a depth-first expansion is proportional to log
n
, where n is the number of members in the distribution list.
Another possible method of expanding a distribution list is “breadth-first” expansion. In simple terms, breadth-first expansion means that each level of a distribution list tree is completely resolved before proceeding to the next level of the distribution list tree. This method has some advantages over depth-first expansion in that it allows multiple records to be batched together and sent as a single lookup operation, thereby reducing the number of separate lookup operations and, therefore, reducing the total time required to complete the expansion operation. Unfortunately, doing this in a simplistic fashion will cause a large amount of resources (in terms of the stack objects required to keep track of parents for each DL that is being expanded) to be allocated. As a general rule, the system resources needed to complete a breadth-first expansion can be as great as n
2
, the square of the number of members in the distribution list.
Therefore, what is needed is an efficient method of expanding distribution lists that can be optimized in terms of speed and the amount of resources needed to complete the operation.
SUMMARY AND OBJECTS OF THE INVENTION
The present invention is a technique for doing an asynchronous, breadth-first expansion of e-mail distribution lists, while being able to control the amount of resources needed to complete the expansion operation. The breadth first DL expansion technique described here correctly handles circular references while expanding Distribution Lists asynchronously, in a breadth-first fashion, and without requiring large amount of resources.
The method for breadth first expansion of a DL consists mainly of a priority queue. The method begins by examining a piece of e-mail for all intended recipients. A lookup request is inserted into the priority queue for each recipient specified in the e-mail message. The priority of these requests is set to the lowest priority (i.e., lowest numerical value) possible for the queue. None, some, or all of these recipients can be DLs.
A connection manager module manages connections to a directory service and is responsible for sending lookup requests and processing the responses. The connection manager pulls requests from the priority queue in priority order (i.e., requests with the largest numerical value are pulled first). It then combines a predetermined number of individual requests into one large request and sends it off to the directory service. It continues to pull requests from the priority queue until the maximum number of pending requests is hit, at which point it stops. This provides a throttling control on the process.
When the DS returns the results of the search request, the combined response is split apart by the connection manager. If the result indicates that a lookup request resulted in finding a final recipient (i.e., a mailbox recipient), then information about that recipient is recorded in the e-mail message itself. If the result indicates that the request was for a distribution list or a user with a forwarding address, then a new lookup for each of the members of the distribution list or the forwarding address is inserted into the priority queue. The priority of this subsequent request is incremented to be higher than its previous priority. Also, a stack is allocated, and the original request is inserted as a parent, and is associated with the new lookup request.
When a result is returned by the DS and a stack is associated with its request, the stack is checked to see if the result is already present in the stack. If so, then this indicates a circular DL or forwarding address loop, and this loop detection is recorded in the e-mail recipient.
The combination of throttling mechanism and priority queue provides the mechanism to control how many lookup requests are performed in parallel and the maximum amount of memory resources required to complete the DL expansion.
It is, therefore, a primary object of the invention to provide improved methods, computer program products and systems for expanding distribution lists. Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly poi
Shah Milan M.
Stamerjohn Jeffrey C.
Coulter Kenneth R.
Nguyen Hai V.
Workman & Nydegger & Seeley
LandOfFree
System and method for breadth first asynchronous expansion... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for breadth first asynchronous expansion..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for breadth first asynchronous expansion... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3046843