Load balancing between E-mail servers within a local area network

Message traffic is balanced between a plurality of alternative message routes connecting a plurality sites in an electronic messaging system by assigning a cost to each potential message route between the plurality of sites. The cost defines a desired relative frequency of usage for the corresponding message route. A weight is calculated for each potential message route based on its assigned cost of connecting one site to another site. A message route between the one site and the other site is chosen based on the collective calculated weights and a message is transmitted over the chosen message route from one site to the other site.

BACKGROUND 
This invention relates to regulating the flow of information between 
electronic mail ("e-mail") servers within a local area network ("LAN"). 
A typical e-mail system as shown in FIG. 1 includes one or more 
interconnected servers 101 each serving one or more clients 103 (e.g., 
individual workstations). A client in turn may interact with an 
end-user--a human operator that seeks to use the e-mail system to 
communicate with other end-users, for example. The collection of 
interconnected servers 101 and their respective clients 103 constitute a 
single "site" 105 which may communicate with one or more other sites 
within the same LAN. A site is delimited by a unique e-mail address 
space--that is, each server 101 within a single site 105 shares the same 
e-mail address space. 
In a typical application of an e-mail system, an end-user uses an 
associated client 103 connected to a particular server 101 within site 105 
to send an e-mail message, or some other type of information packet, to 
another end-user who may be connected through a client to the same server 
or to a different server. The server on which the message originates is 
the "originating" server and the server that receives the message is the 
"destination" server. The destination server may be within the same site 
(the "local" or "source" site) as the originating server or at a different 
site (a "remote" or "destination" site). 
Each server within a site has a direct communication path 107 to every 
other server within that same site. This allows messages to be delivered 
in a single "hop" between any two servers within the site. A mechanism 
that may be used to transport messages from one server to another, either 
within a single site or across site boundaries, is the remote procedure 
call ("RPC"). An RPC passes the thread of execution from one memory 
address space to another memory address space while maintaining program 
context. Two servers that may communicate directly with each other using 
an RPC are said to have direct RPC connectivity. The RPC protocol is 
discussed in detail in "Microsoft RPC Programming Guide," John Shirley and 
Ward Rosenberry, O'Reilly & Associates, Inc., Sebastopol, Calif., 1995, 
which is incorporated herein by reference. 
A conventional e-mail system such as that shown in FIG. 2 employs a 
"one-to-one" intersite connectivity model in which every server in site 
205 has direct RPC connectivity (via communication paths 107) with every 
server in site 215. The one-to-one connectivity model, while acceptable 
for LANs having only a few sites, does not scale up gracefully and thus is 
not well suited as a general model for intersite communications. As more 
sites are added to the LAN, the number of direct communication paths 
required to maintain one-to-one intersite connectivity increases 
dramatically and quickly becomes unmanageable if the number of sites grows 
to more than just a few. 
In the two site configuration of FIG. 2, for example, eight separate 
communication paths are necessary to maintain one-to-one connectivity 
between site 205 and site 215. If a third site having four servers were 
added to the LAN, the number of communication paths required to maintain 
one-to-one intersite connectivity would increase to 32--a fourfold 
increase through the addition of just one extra site. The amount of 
network and operating system resources that are consumed by the managment 
of these connections would increase proportionately with the total number 
of connections maintained. Moreover, a substantial amount of manual 
administrative overhead is imposed on the system administrator who must 
keep the list of servers in the remote sites up to date with respect to 
the actual servers present in those sites. Consequently, the burden 
imposed on the e-mail system's resources quickly would become unmanageable 
if the number of sites in FIG. 2 was increased beyond just 2 or 3. 
In any multi-site e-mail system, a system administrator is faced with a 
challenge of determining an efficient and cost-effective manner of 
transporting e-mail traffic from one site to another. What is needed is a 
set of tools and techniques that facilitate efficient intersite 
communications in a LAN having an arbitrarily large number of sites. 
SUMMARY 
In one aspect of the invention, message traffic is balanced between a 
plurality of alternative message routes connecting a plurality of sites in 
an electronic messaging system by assigning a cost to each potential 
message route between the plurality of sites. The assigning may be 
performed off-line by a system administrator. The cost defines a desired 
relative frequency of usage for the corresponding message route. A 
probability of choosing a message route having a low cost is higher than a 
probability of choosing a message route having a high cost. A weight is 
calculated for each potential message route based on its assigned cost and 
a message route between the one site and the other site is chosen based on 
the collective calculated weights. A message is transmitted over the 
chosen message route from one site to the other site, for example, using a 
remote procedure call. This action causes the message to move from one 
e-mail address space to another e-mail address space. 
Special cost values may be assigned to one or more of the message routes, 
for example, to cause the associated message route to be excluded as a 
possible message route choice. Alternatively, the special cost may cause 
the associated message route to be consistently chosen. In any event, 
these special cost values are excluded from the weight calculations. 
The weight calculations for a particular message route between two sites 
may include comparing that message route's cost to the combined costs for 
all potential message routes between the two sites. In particular, the 
message route's cost may be subtracted from a sum of the costs for the 
plurality of message routes between the two sites. 
In one embodiment, the choosing of a particular message route involves 
constructing a logical weight table having a number of positions equal to 
a sum of the weights for the plurality of message routes, associating a 
number of positions in the weight table to each message route equal to its 
weight. A random number is then generated and compared with the weight 
table. The message route that has an assigned position in the weight table 
corresponding to the random number is picked as the route to use for the 
communication sequence (i.e., one or more messages). 
As a result, the choosing of a message route is probabilistic such that an 
actual relative frequency of use for each message route converges toward 
the desired relative frequency of use for each message route as a 
cumulative number of transmissions from one site to another site 
increases. 
Once the costs have been assigned, and their respective weights have been 
calculated, the message route for each successive communication sequence 
will be newly chosen using the same costs and weights until they are 
reassigned by the system administrator. 
In another aspect of the invention, a method for load balancing in an 
electronic messaging system includes, in each server in a network which 
can send messages to other servers in the network, assigning a cost to 
each potential transmission route from one server to another server and 
storing a record of the assigned cost for each potential transmission 
route. A copy of these costs may be stored on each server in the network. 
For one server having a message to be sent, the set of potential 
transmission routes from the one server to a server addressed by the 
message is determined. At the sending server, a desired relative frequency 
of use is established for each potential transmission route in the set 
based on its assigned cost relative to the other assigned costs. A 
transmission route is chosen probabilistically from among the set such 
that an actual relative frequency of use for each potential transmission 
route converges toward the desired relative frequency of use for each 
transmission route as a cumulative number of transmissions from the one 
server to the addressed server increases. After it has been chosen, one or 
more messages are sent over the transmission route. The steps of choosing 
a transmission route and sending messages over that route may be repeated 
for each server in the network that has a message to be sent to another 
server in the network. 
In another aspect of the invention, an electronic messaging system includes 
a plurality of sites each of which includes multiple servers that are 
capable of exchanging messages. Each site occupying a unique address 
space. The system includes a plurality of communication paths connecting 
the plurality of sites, each communication path having a preassigned cost 
that represents a desired relative frequency of use for that communication 
path. The number of communication paths between a pair of sites is less 
than the number of servers in one site in the pair multiplied by the 
number of servers in the other site in the pair. Message traffic is 
distributed across the plurality of communication paths based on the 
collective preassigned costs of the plurality of communications paths. 
In the messaging system, each of the plurality of servers has direct 
connectivity to every other server within a same site. At least one of the 
plurality of servers in a particular site is a bridgehead server from 
which the plurality of communication paths for that site emanate 
exclusively. The messaging system may include a target server, which may 
be the same or different server as the bridgehead server, and into which 
the plurality of communication paths lead. 
Advantages of the invention may include one or more of the following: 
By reducing the number of intersite connections, the connectivity models 
described herein simplify an e-mail network without decreasing its 
functionality. Each server continues to have a communication path, either 
direct or indirect, to every other server within the network. At the same 
time, these connectivity models provide the system administrator with 
increased control and flexibility over the flow of e-mail message traffic 
between different sites in the network. The attendant reduction in 
complexity makes the network easier to maintain and thus reduces the load 
on the e-mail system and reduces the practical burdens faced by the system 
administrator. Techniques for managing and simplifying the flow of e-mail 
message traffic are described further in commonly-assigned U.S. Ser. No. 
08/680,232, filed Jul. 11, 1996, entitled "AUTOMATIC UPDATING AND USE OF 
ROUTING INFORMATION," which is incorporated herein by reference. 
Moreover, depending on the particular configuration implemented, the option 
of having redundant intersite communication paths is available to the 
system administrator. This available redundancy may be used to enhance the 
fault tolerance of the e-mail system. 
Because these connectivity models are susceptible to many different 
implementations (e.g., one-to-many, few-to-many, many-to-one, many-to-few, 
etc.), they provide a system administer with a rich set of tools that 
enhances the administrator's control over the network. The administrator 
may use one or more of these connectivity models to realize certain 
system-wide policy objectives, even if the e-mail network is composed of 
several disparate site configurations. 
For example, the administrator may implement load balancing across two or 
more different communications paths based on their relative capabilities. 
Communication paths leading to or from servers that possess greater 
processing power or bandwidth may be used at a proportionately larger 
frequency over paths associated with less powerful servers. Certain 
communication paths may be designated to handle all message traffic under 
normal circumstances, with other servers providing fall back 
communications paths if failure occurs. Other communication paths may be 
designated as unavailable except as a last resort--i.e., only when all of 
the other potentially available communications paths have failed. 
The load balancing may be based on a cost--weighted technique which lets 
the administrator distribute message traffic across multiple 
communications paths simply by preassigning a cost value to each of the 
potentially available paths. In this manner, the administrator may achieve 
a rationalized distribution of message traffic across the e-mail network. 
Other advantages and features will become apparent from the following 
description, including the drawings and claims.

DETAILED DESCRIPTION 
FIG. 3 illustrates an alternative configuration, the "many-to-one" 
intersite connectivity model, that may be used in place of the 
conventional one-to-one connectivity model. In contrast to the complexity 
of the one-to-one model, the simplified many-to-one model allows an 
arbitrarily large number of sites to be added to a LAN without unduly 
increasing the number of intersite communication paths that are necessary 
to maintain full communications capability between the sites. 
In the many-to-one intersite connectivity model, only one server in the 
destination site has a direct communication path from servers in the 
source site. All other destination servers must receive their respective 
email traffic through an intermediate (or "target" ) server designated for 
that purpose. As a result, the number of direct intersite communication 
paths is reduced considerably which in turn decreases the complexity of 
the overall system, minimizes the load on the e-mail system and simplifies 
the system administrator's job. 
As shown in FIG. 3, each of Server A (201) and Server B (203) in source 
site 205 has a direct communication path 217, 219 only to a single server 
in the destination site 215--namely, Server 2 (209). Because Server 2 has 
by design a direct intrasite communication path 107 to each of the other 
Servers 1, 3 and 4 (207, 211 and 213, respectively) within destination 
site 215, incoming messages from source site 205 will be received first by 
Server 2 and then distributed to Servers 1, 3 and/or 4 as appropriate. 
Because in the many-to-one configuration all e-mail message traffic flowing 
between servers in source site 205 and servers in destination site 215 is 
routed through a single target server (e.g., Server 2 in FIG. 3), it may 
become overloaded and unable to execute its other tasks in a timely manner 
when message traffic becomes heavy. In that case, another alternative 
configuration, the "many-to-few" intersite connectivity model, provides a 
solution to the potential overloading problem. 
Under the many-to-few approach, each server in a source site has direct RPC 
connectivity to more than one server, but fewer than all of the servers, 
in the destination site. In the example shown in FIG. 4, each of Server A 
(201) and Server B (203) in source site 205 has a direct communication 
path to two servers in destination site 215--namely, communication paths 
217 and 223 to Server 2 (209) and communication paths 219 and 221 to 
Server 1 (207). 
This configuration provides at least three advantages. First, in the same 
manner as the many-to-one connectivity model, the many-to-few 
configuration reduces the number of intersite communication paths that are 
maintained in comparison with the one-to-one connectivity model. 
Second, the redundancy created by having alternative routes for message 
traffic enhances the fault tolerance of the e-mail system by ensuring that 
source site 205 and destination site 215 will be able to communicate when 
one of the communication paths fails. 
A third advantage imparted by the many-to-few model is that the 
availability of alternative routes for message traffic allows the system 
administrator to distribute e-mail message traffic among two or more 
target servers; so that no one server becomes overloaded. This 
distribution of message traffic among two or more communications paths is 
referred to as "load balancing." 
Load balancing may be achieved through the use of a "cost-weighted" 
algorithm. In this technique, it is assumed that the system administrator 
has assigned a "cost" (a numeric value, for example, between the arbitrary 
limits of 0 and 100) to each of the potential communications paths leading 
to a remote site. An assigned cost value has significance only relative to 
the other cost values assigned to the communications paths leading into 
the same remote site. For example, a lower assigned cost means that the 
associated communication path is preferable over another communication 
path that has a higher assigned cost and which leads into the same remote 
site. 
The particular costs that are assigned to the potential communication paths 
depend on the policy objectives that the system administrator seeks to 
implement. For example, if one particular target server in a remote site 
is dedicated to the task of doing nothing but receiving and processing 
incoming message traffic, the system administrator will likely assign a 
low cost (relative to the costs assigned to the other target servers in 
that site) to the communication paths into that remote server so that the 
bulk of e-mail traffic entering the site will be routed through the 
dedicated server. On the other hand, if another target server in the 
remote site, in addition to receiving and processing e-mail traffic, 
performs other important functions that ordinarily should not be 
interrupted, or it has limited bandwidth or processing power, the system 
administrator likely will assign a high relative cost to the communication 
paths leading into that server so that it receives e-mail message traffic 
on an infrequent basis, for example, only 5% of the time or less. 
The assigned cost for a communication path is direction specific and may 
differ depending on which direction the message traffic is flowing. In 
FIG. 4, for example, the cost assigned to the communication path 221 
between Server A and Server 2 might differ if the message was being sent 
from Server 2 to Server A instead of being sent from Server A to Server 2. 
In fact, the system administrator may configure the system, through 
techniques described below, such that Server 2 is not allowed to send 
messages to Server A, but rather only receive them. These capabilities 
further enhance the flexibility and control with which a system 
administrator may manage a multiple site e-mail system. 
The cost-weighted algorithm also allows "special" cost values to be 
assigned to communications paths that are to be treated differently from 
the other communications paths. A system administrator may assign a cost 
value of 100 to a communication path that should be used only as a last 
resort--i.e., only when all other potential communications paths have 
"failed," which typically is some sort of permanent or semi-permanent 
problem that prevents the communication path from functioning properly. 
A special cost value of 0 may be assigned to a communication path that, 
under ordinary circumstances, should be used for all messages entering the 
site. Other communications paths are considered for use only when the zero 
cost communication path has failed. 
Although the embodiment described above uses cost values in the range of 0 
to 100 inclusive, any other range of values may be implemented as desired. 
Moreover-, additional or different special cost values other than 0 and 
100 may be implemented as appropriate to suit the needs of the system 
administrator for a particular e-mail system. 
A hypothetical example of a cost-weighted technique is described with 
reference to the flowchart of FIG. 5. This example is based on the two 
site LAN configuration shown in FIG. 6 but the underlying technique is 
applicable to any arbitrary number of sites. In FIG. 6, the source site 
605 is illustrated as having only a single server, Server A, but it could 
have any number of servers, each of which would be treated in the same 
manner as Server A when it sends a message to the destination site 615. 
The destination site 615 in FIG. 6 has six servers, five of which (Servers 
1-5) are designated as target servers. The intrasite communications paths 
between Servers 1-5 in the destination site 615 are omitted for the sake 
of simplicity but it is assumed that each of the six servers in 
destination site 615 has direct RPC connectivity to the other five servers 
in that site. 
In step 501 of FIG. 5, the system administrator assigns a relative cost 
value to each of the different communications paths leading into the 
destination site, for example, as follows: 
path 617 into Server 1: cost(1)=5 
path 619 into Server 2: cost(2)=50 
path 621 into Server 3: cost(3)=50 
path 623 into Server 4: cost(4)=75 
path 625 into Server 5: cost(5)=100 
This step is typically performed off-line--i.e., before the e-mail 
application has been launched, but it could also be performed in a dynamic 
manner--i.e., while the e-mail application was running. The cost values 
conceivably could be automatically altered by a software process to adapt 
to changing network conditions. In any event, these cost values are stored 
and may be read by software processes executing on the servers in the 
source site. 
Once the cost values have been assigned, a corresponding 
"probability-of-usage," P, may be calculated for each of the potential 
communications paths using equation (i) below, where n is the number of 
the communication path under consideration and N is the total number of 
potential communication paths. 
##EQU1## 
Communication paths having special assigned cost values (e.g., 0 or 100) 
are not included in the probability-of-usage calculations. 
These probabilities-of-usage may also be thought of as statistical 
weighting factors in that a higher probability-of-usage means that a 
communication path has a greater "weight" (a numeric value whose magnitude 
influences the outcome of a computation) and thus is more likely to be 
chosen. Relative to the other communication paths, the weight associated 
with a specific communication path is roughly inversely proportional to 
the cost assigned to that path by the system administrator. 
For the cost values assigned to Servers 1-5 in FIG. 6, the 
probabilities-of-usage for the four servers are calculated as follows: 
##EQU2## 
At step 505, it is determined whether Server A has a request pending to 
send one or more messages to a server in destination site 615. Assume, for 
example, that an end-user located on Server A at source site 605 has 
initiated the transfer of a message to an end-user located at Server 6 in 
destination site 615. In that case, a communication path to be used for 
transmitting the message is chosen in step 507 according to the 
probabilities of usage calculated in step 503. Based on the particular 
values used in this example, a 43.2% chance exists that path 617 into 
Server 1 will be chosen; a 22.7% chance exits that path 619 into Server 2 
will be chosen; a 22.7% chance that path 621 into Server 3 will be chosen; 
and a 11.4% chance exists that path 623 into Server 4 will be chosen. 
Because the cost value assigned to communication path 625 into Server is a 
special cost value, by definition a 0% chance exists that path 625 will be 
chosen to receive incoming message traffic under normal circumstances. 
However, if all of the four other communication paths 617, 619, 623 and 
625 have been tried and failed, path 625 will be chosen as the 
communication path of last resort. 
Assume that in step 507, the path having the highest 
probability-of-usage--path 617 into Server 1--was chosen as the intersite 
communication path to be used to transport the message from Server A in 
source site 605 to Server 6 in destination site 615. At step 509, server A 
establishes a connection with Server 1 via path 617 using the RPC protocol 
and the message is sent to Server 1 in step 511. Upon receipt, Server 1 
forwards the message to its ultimate recipient at Server 6, thereby 
completing the delivery of the message. 
If it is determined at step 513 that more messages are pending transfer 
from Server A in site 605 to any server in site 615, control returns to 
step 511 for the next message to be sent. This loop continues until all 
pending messages in Server A that were to be sent to site 615 are 
transferred. 
Once all of the messages have been sent, the connection to Server 1 via 
communication path 617 is dropped in step 515 and control is returned to 
step 505 to wait for the next intersite message transmission sequence to 
be initiated. 
A single message transmission sequence may result in one or more individual 
messages being sent over a communication path, each individual message 
being sent one after another until no more remain. For each separate 
message transmission sequence, a new communication path is chosen in step 
507 using the same probabilities-of-usage until the system administrator 
changes the cost values, at which point new probabilities-of-usage would 
be calculated as used in selecting a communication path. Accordingly, each 
iteration of path selection in step 507 will be independent of all past 
path selections. The number of individual messages in a message 
transmission sequence, as well as the size (e.g., number of bytes) of the 
messages being transmitted have no effect on which communication path is 
chosen. Rather, the probabilities-of-usage determine the likelihood that a 
certain communication path will be acquired and used for each new message 
transmission sequence, regardless of how many messages or bytes are 
ultimately transferred during the sequence. 
The concepts underlying the many-to-one and many-to-few connectivity 
models, as well as the load balancing techniques described above, may be 
applied internally within the source site by using one or more 
"bridgehead" servers through which all outgoing message traffic to a 
remote site is channeled. When a server has been designated as a 
bridgehead, it means that it is allowed to send messages off site. Other 
servers in the site that are not bridgehead servers must route any 
messages bound for a remote site through a bridgehead server, which then 
sends the message to the destination site. The use of a bridgehead server 
for outbound message traffic reduces the number of direct intersite 
communications paths and thus simplifies the network. 
FIG. 7 shows an example of a two site configuration in which source site 
605 uses Server A as its bridgehead server. All communications paths (two 
in the example illustrated, path 701 and path 703) out of site 605 
originate at Server A. If an end-user connected to Server B in site 605 
wants to send a message to another end-user connected to a server in 
destination site 615--Server 3, for example--Server B first must send the 
message to Server A which then forwards it, for example, to Server 2 in 
site 615, which in turn forwards the message to its ultimate recipient at 
Server 3. The configuration of FIG. 7 is referred to as a "one-to-many" 
connectivity model. 
Alternatively, multiple bridgehead servers may be used in the source site 
to realize a "few-to-many" intersite connectivity model as shown in FIG. 
8. In this model, servers in the source site 605 have two independent 
gateways through which message traffic may travel to the destination site 
615--namely, either through Server A (via communication paths 817 or 819) 
or through Server B (via communication paths 821 or 823). 
This configuration provides several advantages: it reduces the required 
number of communication paths relative to the one-to-one connectivity 
model; it provides fault tolerance through the presence of redundant 
communication paths; and it allows outbound message traffic from source 
site 605 to be load balanced between multiple bridgehead servers. 
Whichever configuration a system administrator decides to 
implement--one-to-one, many-to-one, many-to-few, one-to-many, few-to-many, 
or something else--has its attendant advantages and disadvantages. For 
example, the one-to-one intersite connectivity model provides direct 
access between any two servers in the LAN without regard to the particular 
site in which each may be respectively located. The fact that any other 
server in the e-mail system is just one hop away means that messages will 
be delivered faster and that less computation time will be used in making 
routing and delivery decisions. At the same time, the large number of 
communications paths that a one-to-one model requires makes it impractical 
for a LAN that has more than just a few sites. 
Under the many-to-one, many-to-few, one-to-many, and few-to-many 
connectivity models, the delivery latency for email messages may be 
increased because two or more hops may be required to deliver a message 
rather than just one (e.g, in FIG. 4, a message from Server A in source 
site 205 to Server 4 in destination site 215 would undergo a first hop 
between Server A and Server 2 and a second hop between Server 2 and Server 
4). In addition, these alternative configurations may require that 
additional overhead information be appended to each message so that the 
target server and/or the bridgehead server will be able to route messages 
to the proper destination servers. 
A summary of relative advantages and disadvantages for the various 
configurations is set forth in Table I below. 
TABLE I 
______________________________________ 
Connection Type 
Advantages Disadvantages 
______________________________________ 
one-to-one loads on the system 
no built-in fault 
and network are fairly 
tolerance or 
predictable as the 
redundancy. 
possible number of 
connections is known; 
easy to track a 
message or find a 
fault in the system as 
the messages can flow 
across one and only 
one possible route. 
many-to-one 
each bridgehead server 
no fault tolerance 
can make a direct 
as a single failure 
connection to the 
at the destination 
target server and 
site can impede all 
thus reduce routing 
message traffic; no 
"hops"; fairly easy to 
redundancy or load 
track messages because 
balancing available 
each message must flow 
at the destination 
into a single site. 
destination; some 
redundancy and load 
balancing available at 
the source site. 
many-to-few 
allows for fault 
can necessitate 
tolerance and additional hops for 
redundancy in the 
a message to get 
communications paths; 
from the 
provides load originator's system 
balancing across a 
to the ultimate 
controlled list of 
destination server; 
servers in both the 
requires some degree 
source and destination 
of knowledge on the 
sites. part of the system 
administrator to 
understand the 
network topology and 
system loads so that 
proper choices can 
be made. 
few-to-many 
same as many-to-few 
same as many-to-few 
many-to-many 
a message typically is 
can consume a large 
only one hop away from 
amount of system 
the proper destination 
level resources 
server; little managing connections 
administrative as any server in the 
overhead is required 
topology may make a 
as all systems are 
connection to the 
always utilized; 
particular 
provides for full 
destination server 
fault tolerance and 
at any time. 
redundancy. 
______________________________________ 
Despite these potential tradeoffs, the connectivity models described above 
provide a system administrator with increased control and flexibility in 
regulating intersite message traffic. Depending on the particular policy 
objectives that the system administrator seeks to achieve, the use of one 
or more of these intersite connectivity models may provide considerable 
advantages over a one-to-one connectivity model. The factors that would go 
into a system administrator's decision of which connectivity model to use 
are many and varied and would depend on things such as the bandwidth and 
processing power available at each server, relative task urgency and 
importance, fault tolerance and the like. 
The foregoing is a high level description of the concepts underlying the 
present invention. The specific details for implementing an embodiment 
will now be described. 
As an initial matter, it should be noted that the intersite communications 
paths shown in FIGS. 2-4 and 6-8 represent logical, as opposed to 
physical, connections. Sites in a LAN are physically connected together by 
various connectivity components such as dedicated cable connections, 
modem-telephone line connections and/or wireless connections. A single 
physical connection is able to support multiple logical communications 
paths depending on factors such the bandwidth required for the various 
communication paths. 
The ability to communicate across multiple sites in an integrated and 
cohesive manner may be achieved through the use of a "directory 
service"--a repository of information distributed across the LAN that 
defines which remote sites are reachable from any particular site and how 
those remote sites may be reached. The directory service includes a 
database that stores information concerning the attributes of the 
individual servers and end-users; of the e-mail system, including 
permissions and the like. 
In one embodiment, each server maintains its own copy of the directory 
service database so that all servers within a single site will have access 
to the same information concerning remote sites. Each server also has its 
own directory service process by which other applications make requests to 
read and write information. Other embodiments are possible in which fewer 
instances of the directory service exist than the number of servers in the 
site. The only requirement is that each server have connectivity to an 
instance of the directory service in order that information can be read or 
written as appropriate. In addition, the use of a directory service is not 
necessary, but rather any other mechanism for storing and retrieving 
routing information may be used in its place. 
One important component of the directory service is the site connector--a 
software object (defined as a discrete entity, comprising data and 
processes that act on that data, for performing a specific task) that 
facilitates intersite communications by configuring and managing RPC 
connections across different sites within the e-mail system. Each instance 
of the site connector object identifies one and only one remote site, and 
describes the connectivity between the local site and the designated 
remote site. A separate site connector object is provided for each remote 
site to which a potential connection exists. 
FIG. 9 is a simplified representation of the site connector object 903 
stored within the directory service 901. The site connector object 
includes its common name 905 within the directory service so that the site 
connector object may be located by other objects; a list of site addresses 
907 of remote sites that are reachable from the source site for use in 
building a table of routing information; and the site address 909 of the 
source site. 
A primary component of the site connector object 903 is the target server 
list 911, which is a table of the message transfer agents ("MTAs") (913, 
915, 917) in the destination site that are potentially available to 
establish a communication path from the source site. An MTA is a program 
that executes on a server (each server has its own dedicated MTA) and 
which, when invoked, performs the handshaking functions with an MTA on 
another server, either within the same site or in a remote site, to 
establish a connection and exchange data with the other server. MTAs and 
their use are known in the art. The target server list potentially may 
identify any number of remote MTAs in the destination site, but only those 
MTAs listed are available to form a communication path between two 
servers. In FIG. 9, the remote MTAs are listed as MTA1, MTA2, . . . , 
MTAn, where n is a positive integer. 
If cost-weighted load balancing as described above is implemented, the 
target server list 911 also includes the cost (919, 921, 923) assigned to 
each remote MTA listed. If the source site has a bridgehead server, a 
bridgehead server list 925 identifying the MTAs (MTA1 through MTAk where k 
is a positive integer) for the bridgehead server(s) in the source site 
also is included in the site connector object. The bridgehead server list 
also may include an associated cost value 927, 929 for each bridgehead 
server listed, which values may be used to perform intrasite load 
balancing when more than one bridgehead server is being used. 
When a server in the source site (the "originating" server) wants to send a 
message to a server at the destination site, the MTA for the originating 
server reads the bridgehead server list 921 in the site connector object 
to see if a bridgehead server is implemented for the source site. If so, 
the message is forwarded to the bridgehead server so that its MTA will 
handle the transfer of the message to the destination site. All servers 
within a site may read the site connector object but only the bridgehead 
servers may invoke it to establish a connection to a remote site. 
If more than one bridgehead server is listed in the bridgehead server list 
921, load balancing across the bridgehead servers may be implemented. In 
one embodiment, this is accomplished by having the system administrator 
pre-assign a cost to each of the potentially available bridgehead servers. 
These assigned costs are not weighted; but rather the lowest cost 
bridgehead server is always chosen, absent failure. If two or more 
bridgehead servers have same assigned cost, one is randomly chosen from 
among the group of potential candidates. 
If no bridgehead server is being used (or if bridgehead servers are being 
used and the originating server is a bridgehead server), the MTA for the 
originating server next reads the target server list 911 for the desired 
destination site to determine which MTAs at the destination site have been 
designated as potentially available for an RPC connection. The MTA for the 
originating server then chooses one of the MTAs listed in the target 
server list and uses it to establish a communication path between the 
originating server and the destination site server associated with the 
selected MTA. 
For example, in the two site e-mail system of FIG. 4, in which Server 1 and 
Server 2 are the only servers in destination site 215 that are available 
to receive messages from servers in source site 205, a site connector 
object in the originating server in source site 205 would have a target 
server list with an entry for MTA1 (the MTA executing on Server 1 in 
destination site 215) and an entry for MTA2 (the MTA executing on Server 2 
in destination site 215). If load balancing was being used, the target 
server list 911 also would include the relative costs that were previously 
assigned by the system administrator (i.e., cost(1) 919 for MTA1 and 
cost(2) 921 for MTA2). 
FIG. 10 is a flowchart of the load balancing algorithm that is implemented 
in an embodiment, as explained with reference to FIG. 6. This In step 951, 
the system administrator assigns a relative cost value to each of the 
potentially available MTAs in the remote site, in the manner as discussed 
above in connection with step 501 of FIG. 5. Assume that MTA1 is the MTA 
for Server 1 in destination site 615; MTA2 is the MTA for Server 2; MTA3 
is the MTA for Server 3; MTA4 is the MTA for Server 4; and MTA5 is the MTA 
for Server 5. The same cost values as above are assigned by the 
administrator in this example: 
cost(1) of MTA1=5; 
cost(2) of MTA2=50; 
cost(3) of MTA3=50; 
cost(4) of MTA4=75; and 
cost(5) of MTA5=100. 
At step 953, the total cost, TC, is calculated by summing the cost of the 
individual MTAs, excluding any MTAs that have special cost values. In the 
example, the cost value for MTA5 is excluded from the following 
calculations because its cost value (100) indicates that it should be 
treated as a special case--e.g., not used unless all other MTAs have 
failed. 
Such failure could result, for example, if the destination server to be 
reached is not powered up, if the MTA on the destination server is not 
running, or, potentially, if the destination server is too busy to accept 
another incoming connection request. Failure also may be caused by network 
outages that prevent the network RPC connection from being completed. 
In any event, a "time-out" limit is imposed whenever an source MTA ia 
attempting to form a connection with a remote MTA. If an attempted 
connection fails, an MTA re-try timer is started which must count down to 
zero, for example, from 60 seconds, before the MTA attempts to establish 
the failed connection again. During the time that the re-try timer is 
counting down, the MTA will attempt to make a connection to another server 
on the target server list and will not attempt to make a connection with 
the failed destination server unless it is the only possible route to the 
destination site address space (e.g., it is the only remote MTA listed in 
the target server list). 
The site connector has its own associated re-try timer (i.e., other than 
the individual timers maintained by the MTAs) which becomes active when 
all of the destination servers in the target server list have been tried 
and failed (e.g., a physical network problem has occurred). When that 
happens, the particular site connector under consideration will not be 
used until its re-try timer has counted down to zero, for example, from 60 
seconds. If, however, the failed site connector is the only connector 
covering the destination site address space, a connection using the failed 
site connector will be attempted without regard to the status of its 
re-try timer. 
Excluding the special cost value for MTA5, the total cost is calculated as 
follows: 
##EQU3## 
At step 955, the individual weight, W(n), of each MTA is calculated by 
deducting its cost from the total cost. FIG. 11 is a graph showing the 
relationship between assigned cost (X-axis) and calculated weight (Y-axis) 
for the particular values used in this example. As shown in FIG. 11, an 
MTA's weight decreases linearly with its cost. The general equation for 
calculating the weight of MTAn, where n is a positive integer is as 
follows: 
EQU W(n)=TC-cost(n) 
Using the specific values for this example, the weights for MTA1 through 
MTA4 are: 
EQU W(1)=180-5=175 
EQU W(2)=180-50=130 
EQU W(3)=180-50=130 
EQU W(4)=180-75=105 
At step 957, the total weight, TW, is calculated by summing the weights of 
the individual MTAs: 
##EQU4## 
At step 959, a logical weight table effectively is created as shown in FIG. 
12. The weight table has a number of logical positions (540 in this 
example) equal to the sum of the weights of the MTAs. Each MTA is 
allocated a number of positions in the weight table according to its 
individual weight. An identifier for MTA1 is associated with the first 175 
positions in the weight table (1-175) corresponding to its weight of 175. 
Similarly, based on their respective weights, an identifier for MTA2 is 
associated with the next 130 positions (176-305), an identifier for MTA3 
is associated with the next 130 positions (306-435), and an identifier for 
MTA4 is associated with the last 105 positions in the table (436-540). 
At step 961, it is determined whether Server A in source site 605 has any 
message traffic bound for destination site 615. If not, the following 
steps are not performed. Assume, however, that an end-user located on 
Server A at source site 605 has initiated the transfer of a message to an 
end-user located at Server 6 in destination site 615. In that case, at 
step 963, a random number is generated and normalized to fall within the 
range of 1 to TW, inclusive, using techniques that are well known in the 
art. For example, if a random 10 bit number were generated, the process 
could simply divide by the appropriate scale factor and round off. 
At step 965, the random number resulting from step 961 is compared to the 
weight table. Assume that the random number is 317, for example, which 
falls into the range of the weight table that corresponds to MTA3 (306 to 
435). Accordingly, at step 967, the MTA executing in Server A contacts 
MTA3, which is the MTA for Server 3 in destination site 615, and forms a 
logical communication path 621. 
Control loops between steps 969 and 971 to sequentially transmit all 
pending messages from Server A bound for any server in destination site 
615. 
After all of the messages have been sent, the connection to MTA3 is 
dropped, thus ending the message transmission sequence. At this point, 
control returns to step 961 to await initiation of the next intersite 
message transmission sequence. 
The techniques described above are not limited to email systems but rather 
find applicability in any network that transmits information between 
different nodes, or locations. 
Moreover, the techniques described above may be implemented in hardware or 
software, or a combination of the two. Preferably, the techniques are 
implemented in computer programs executing on programmable computers that 
each include a processor, a storage medium readable by the processor 
(including volatile and non-volatile memory and/or storage elements), at 
least one input device, and at least one output device. Program code is 
applied to data entered using the input device to perform the functions 
described above and to generate output information. The output information 
is applied to one or more output devices. 
Each program is preferably implemented in a high level procedural or object 
oriented programming language to communicate with a computer system. 
However, the programs can be implemented in assembly or machine language, 
if desired. In any case, the language may be a compiled or interpreted 
language. 
Each such computer program is preferably stored on a storage medium or 
device (e.g., ROM, hard disk or magnetic diskette) that is readable by a 
general or special purpose programmable computer for configuring and 
operating the computer when the storage medium or device is read by the 
computer to perform the procedures described in this document. The system 
may also be considered to be implemented as a computer-readable storage 
medium, configured with a computer program, where the storage medium so 
configured causes a computer to operate in a specific and predefined 
manner. 
Other embodiments are within the scope of the following claims.