Exchange Server 2003 Message Routing

For messages to nonlocal recipients, the routing engine must provide the advanced queuing engine with information about the next hop host on the transfer path of the destination and the next hop type, as discussed in the previous topic. The next hop host is the actual routing address and the next hop type determines how the advanced queuing engine handles the message. To provide this important information, the routing engine must have a complete view of the whole routing topology. This includes all routing groups and their servers, routing group connectors, and connectors to external messaging systems. In Exchange Server 2003, this information is in Active Directory directory service.

Message Routes and Link State Table

Every Exchange 2003 server maintains its own routing table, called the link state table, dynamically in memory, based on Active Directory and link state information, as follows:

• Routing-related Active Directory information   This information is stored in attributes of the organization object, routing group objects, connector objects, and server objects. These objects reside in the configuration directory partition and define the routing topology of the entire Exchange organization.

  Note

  Administrative groups are not part of the routing topology in an Exchange organization.

• **Link state information   **This information specifies whether each connector in the routing topology is available (up) or unavailable (down). Link state information is dynamic and might change when a connector experiences transfer problems or when transfer issues are resolved. For more information about link state changes and the propagation of link state information across an Exchange organization, see Link State Propagation.

Initializing the Link State Table

Upon startup, each Exchange server initializes its link state table with the following information from Active Directory:

• Organization object   The routing topology boundary is the Exchange organization. That is, the link state table does not include any information about external bridgehead servers or messaging connectors in an external messaging system. As far as the routing engine is concerned, the routing topology ends at the connector to the external messaging system. Accordingly, the routing engine reads the GUID that is registered in the objectGUID attribute of the Exchange organization object in Active Directory and stamps the link state table with this GUID to determine the organization to which this routing information belongs.

• Routing group objects   The routing engine enumerates all routing groups that exist in any administrative groups and queries each routing group for all object attributes, including the msExchRoutingGroupMembersBL attribute that contains a list of all routing group member servers. The routing engine puts this information in the link state table. The routing engine also puts the servers together with the GUID of the server's routing group in a server cache in memory. Each entry in the server cache is a server FQDN appended by the server's routing group GUID.

  Another important routing group attribute is the msExchRoutingMasterDN attribute, which points to the distinguished name of the routing group master in the selected routing group. For more information about the tasks and responsibilities of the routing group master, see the discussion later in this section.

• Messaging connector objects   The routing engine enumerates all child objects with an object type of msExchconnector that exist in the Connections container of each routing group. The msExchconnector objects in the Connections container are the routing group connectors and connectors to external messaging systems configured in the routing group. The routing engine reads all attributes from these connector objects to determine address spaces, cost values, restrictions, and more. The routing engine puts the information for each connector in the link state table. This enables messages to destinations outside the local routing group to be routed.

The process continues until the routing engine identifies all directly and indirectly connected routing groups and queries for the configuration details of their messaging connectors. When this process ends, the routing engine has a complete view of all available transfer paths across the Exchange organization. All links are assumed to be up and available for message transfer. Following the initialization of the link state table, the routing engine communicates with the Microsoft Exchange Routing Engine service on the local server to obtain dynamic link state information that reflects the current state of each connector. The Exchange Routing Engine service connects to the routing group master in the local routing group through TCP port 691 to retrieve this information. For more information about link state information, see the section, "Examining the Link State Table," later in this topic.

Routing Engine and Exchange Routing Engine Service

The routing engine in the transport subsystem and the Exchange Routing Engine service have different roles. The Exchange Routing Engine service does not perform any message routing. The Exchange Routing Engine service communicates link state information between servers that are running Exchange 2000 Server and Exchange Server 2003 in the local routing group. The Exchange Routing Engine service is implemented in resvc.dll, which resides in the \Program Files\Exchsrvr\bin\ directory. The service name is RESvc. For more information about the Microsoft Windows services of Exchange Server 2003, see Exchange Server 2003 Services Dependencies.

The Exchange Routing Engine service is an intra-routing group link state communication service, instead of a routing engine. The actual routing engine that the SMTP advanced queuing engine and Exchange MTA use to route messages is implemented in a file that is named reapi.dll. For the Exchange MTA, some additional code is in mtaroute.dll. Therefore, when the Exchange Routing Engine service is stopped, both the advanced queuing engine and Exchange MTA still use the code in reapi.dll to route messages. Only dynamic updates to the link state table are not received any longer.

Examining the Link State Table

The link state table is a small, in-memory database that is not stored on disk. To examine the entries that the routing engine uses to make routing decisions, you can use the Exchange Server 2003 WinRoute tool (Winroute.exe), which is available for download from the Downloads for Exchange Server 2003 Web site.

The WinRoute tool connects to the link state port, TCP port 691, on the selected Exchange server and extracts the link state table. The information in this table is a series of GUIDs and ASCII text that represent routing groups, routing group members, and connectors in the routing groups. The link state table also includes information about the configuration of each connector. The information fields in the link state table are separated by parentheses as follows:

'General Info' ('Routing Group' 'Routing Group Master' 'Version Info' 'Routing Group Addresses' (Routing Group Members) (Connectors in Routing Group (Connector configuration))).

The following is a shortened example of a link state table (all except one routing group removed):

d38082e7c9ecd74dbff32bada8932642 d037d6eaf2fa7cd10934aca433390623 (489416bfa3a4ff459b8f4403f20cad0d 1650c1fe32aef740be236e1089e0da6a 8 0 2 c2da71f9b39ec748aaf44119a2bdcb36 {26}*.489416BF-A3A4-FF45-9B8F-4403F20CAD0D {4c}c=DE;a= ;p=TailspinToys;o=Exchange;cn=489416BF-A3A4-FF45-9B8F-4403F20CAD0D;* {55}/o=TailspinToys/ou=First administrative Group/*/489416BF-A3A4-FF45-9B8F-4403F20CAD0D ( 1650c1fe32aef740be236e1089e0da6a YES 1 1b20 {10}0701000000000101 ) ( aa582d35e9621c4ca8ae57aa33d953a1 ( CONFIG {4}SMTP {} {23}_aa582d35e9621c4ca8ae57aa33d953a1_D {63}/o=TailspinToys/ou=First administrative Group/cn=Configuration/cn=Connections/cn=RGC RG A <-> RG B 0 0 0 0 ffffffff ffffffff 0 1 0 () 0 () 0 () 0 () ARROWS ( {2}RG {20}83bd0e29fad06d4eb8b00faab3265cd5 1 {4}X400 {23}c=DE;a= ;p=TailspinToys;o=Exchange; 1 ) BH () TARGBH ( 766a192b43bfc3459ee85608d65a98a9 CONN_AVAIL {19}server01.TailspinToys.com ) STATE UP)))

(... next routing group... (... next routing members...) (... connectors in routing group (... connector configuration..)))

The following table maps this information to the various information fields in the link state table.

Information in the link state table

Exchange Routing Path Selection

In an organization with multiple routing groups, various routes might lead to the same destination. Typically, the most efficient (that is, the shortest or cheapest) route is used for message transfer, and additional routes stand by, in case the best route is temporarily unavailable. For example, in the topology shown in the following figure, multiple transfer routes exist between all routing groups.

A routing topology with five routing groups

The routing engine uses the following information to determine the best route:

• Address space   When configuring routing group connectors, you associate possible destinations with messaging connectors by using the Connected Routing Groups tab in the connector properties. However, the routing group connector does not provide this tab. Because this connector is used only to connect to routing groups, the routing engine can determine the routing group address spaces from the connector configuration.

  Routing group GUIDs and RG address spaces

  

  Address spaces can be added to a connector through the Address Space tab. As mentioned in the "Information in the link state table" table, address spaces consist of an address type, such as RG, SMTP, X400, MSMAIL, or CCMAIL, an address , and a cost value. The cost value that you assign to an address space is an important routing criterion. The routing engine uses the Dijkstra shortest-path algorithm to make routing decisions. This algorithm is based on cost values.

• Connector scope   Connectors to external messaging systems might be restricted to the connector's routing group, in which case only users in the local routing group of the connector are permitted to use this connector. By default, all connectors have a scope of Entire Organization.

  Note

  Routing group connectors are always available across the whole organization.

• Restrictions   The routing engine determines the message size, priority, and message type (that is, system or non-system message). The routing engine compares these properties with available connector restriction information. It then excludes those connectors that cannot transfer the message due to effective connector restrictions from the list of potential connectors.

• Status   Only available connectors are included in the route selection process. The status field of each connector indicates whether the connector is available (STATE UP) or unavailable (STATE DOWN).

Routing Path Selection Process

To select the best route to the destination, the routing engine calculates the shortest transfer route from the source routing group to the destination routing group across the Exchange organization, using the Dijkstra shortest-route algorithm. The routing engine then determines the next hop on the shortest route that the advanced queuing engine should use for message transfer.

The routing path selection is a two-step process:

1. The advanced queuing engine calls the GetMessageType method on the IMessageRouter interface of the routing engine. In the GetMessageType method, the advanced queuing engine passes the message to the routing engine in the form of a MailMsg object.

   In this step, the routing engine performs the following processes:

   1. It checks message-trace information to detect loops. If a message loop is detected, the message is dropped with an NDR to the sender.

   2. It reads or recalculates (if necessary) the current organization topology (that is, it determines the list of shortest routes to all destinations in the routing topology, starting from the local routing group).

   3. It checks and possibly refreshes restriction information about connectors in the link state table.

   4. It determines all connectors to the message destination in the organization topology, and then analyzes message characteristics and connector restrictions to exclude all those connectors that must not be used to transfer the message.

   5. It computes a filter value for the message, which uniquely defines the message type. The message type identifies the actual path that messages with similar characteristics can use. The message type is cached. Therefore, the routing engine does not recalculate the filter value for subsequent messages with similar characteristics.

      Note

      The advanced queuing engine maintains a separate message queue for each message type.

   6. It creates associated message types. An associated message type is similar to the actual message type, but is calculated with relaxed restrictions. Associated message types enable the SMTP transport subsystem to return extended error codes if a transfer path is not available for the actual message type because of connector restrictions.

   7. It returns the index of the cached message type to the advanced queuing engine.

2. The routing engine determines the next hop on the shortest route. To complete this step, the advanced queuing engine calls the GetMessageType method on the IMessageRouter interface. The most important information that the advanced queuing engine passes to the routing engine at this point is the destination address and the message type ID. For recipients in the Exchange organization, the destination address is the FQDN of the recipients' home server. The routing engine determines the destination routing group from the server cache, checks the available route for the message type, and returns the next hop on the route to the destination routing group to the advanced queuing engine. The advanced queuing engine can then transfer the message to the next hop on the way to the destination.

Dijkstra's Shortest-Path Algorithm

To make correct routing decisions, the routing engine must know the shortest routes to all possible destinations in the routing topology. The routing engine must find the shortest routes from all available transfer routes to all destinations in a complex routing topology. This problem is known as the single-source shortest paths problem.

The following figure shows that even in a relatively straightforward routing topology, many routes can exist from one routing group to any other routing group. The figure shows the routing group connectors from Figure 5.4 in simplified form, with their default cost values of 1.

Routing group connectors with default cost values

In 1959, Professor Edsger Dijkstra solved the single-source shortest paths problem by developing an algorithm that locates, in a single calculation, the shortest paths from a given source to all points in a topology.

The routing engine uses the Dijkstra algorithm, as follows:

1. It is assumed that the routing topology representing all the paths from one routing group to all other routing groups is a spanning tree. This determines that the topology must include all routing groups and routing group connectors, and that there are no loops between routing groups. Therefore, paths in the routing topology that allow a message to return to the source routing group are illegal transfer paths and are not included in the calculation.

2. Based on Dijkstra's algorithm, the routing engine maintains two sets of routing groups. The first set includes all groups for which the shortest path from the source routing group has already been determined. The second set includes all remaining routing groups. At first, the set of routing groups for which the shortest paths from the source routing group have already been determined is empty. As long as there are routing groups remaining that have not been processed, the routing engine performs Steps 3 through 6, as follows.

3. The routing engine sorts the remaining routing groups according to the current best estimate of their distance (that is, the sum of cost values) from the source routing group.

4. It then adds the closest routing group to the set of routing groups for which the shortest paths have been determined.

5. The routing engine then updates the costs of all the routing groups connected to that routing group (if this improves the best estimate of the shortest path for each of the remaining routing groups) by including the cost value of the connector between those routing groups in the distance value.

6. It updates the predecessor for all updated routing groups. The list of predecessors eventually defines the shortest path from each routing group to the destination routing group.

The following steps illustrate how the routing engine finds the shortest paths from routing group A to all other routing groups in the routing topology:

1. The calculation begins at routing group A because in this example the source is routing group A. The distance value of routing group A to itself is zero. The distance value of all other routing groups has not been determined.

2. Routing group A is added to the set of routing groups for which the shortest paths from the source routing group have been determined. Then, the distance value of all routing groups adjacent to routing group A is updated with the cost values of their connectors. The predecessor (indicated by the source of the black arrows) for all these routing groups is then updated. The predecessor is routing group A.

3. The routing engine sorts the remaining routing groups according to the current best estimate of their distance from the source routing group. It adds the closest routing group to the set of routing groups for which the shortest paths have been determined. Because routing groups B and C have the same distance value, the routing engine selects one routing group at random. This example assumes that the routing engine selects routing group B.

4. The routing engine calculates the distance value of all remaining routing groups adjacent to routing group B, by combining the cost value of the connector between routing group B and the adjacent routing group with the distance value of routing group B. It updates the distance value of an adjacent routing group only if the calculated distance value is smaller than the value that is already assigned to the routing group, and only then updates the predecessor (indicated by black arrows).

   The neighbors of routing group B are routing groups C, D, and E. The current distance value of routing groups C and D is not defined. Therefore, their distance value is updated with the cost values of their connectors, plus the distance value of routing group B (1+1). Then the predecessor (indicated by the source of the black arrows) for all these routing groups is updated. The predecessor is routing group B.

   Routing group C is not updated, because the sum of the distance value of routing group C and the connector cost (1+1) is larger than the current distance value of routing group C.

5. The routing engine sorts the remaining routing groups according to the current best estimate of their distance from the source routing group and adds the closest routing group to the set of routing groups for which the shortest paths have been determined. The algorithm now picks routing group C, because this routing group has the smallest distance value.

6. The routing engine calculates the distance value of all remaining routing groups adjacent to routing group C, by combining the cost value of the connector between routing group C and the adjacent routing groups with the distance value of routing group C. It updates the distance value of an adjacent routing group only if the calculated distance value is smaller than the value that is already assigned to the routing group, and only then updates the predecessor (indicated by black arrows).

   The remaining routing groups that are neighbors of routing group C are routing groups D and E (routing groups A and B were already processed).

   The current distance value of routing groups D and E is 2. This value is smaller than the sum of the connector cost and distance value of routing group C (1+2). Therefore, the distance value and predecessor list of routing groups D and E are not updated.

7. The routing engine sorts the remaining routing groups (routing groups D and E) according to the current best estimate of their distance from the source routing group and adds the closest routing group to the set of routing groups for which the shortest paths have been determined.

   Because routing groups D and E have the same distance value, the routing engine selects one routing group at random. This example assumes that the routing engine chooses routing group D.

   The only remaining neighbor is routing group E, which has a current distance value of 2. This value is smaller than the sum of the connector cost and distance value of routing group D (1+2). Therefore, the distance value and predecessor list of routing group E are not updated.

   The last routing group that has not been added to the list of routing groups for which the shortest paths have been determined is routing group E. There are no remaining adjacent routing groups. Therefore, the calculation of the shortest path is complete. The shortest paths from routing group A to any other routing group in the topology have been determined.

Message Transfer Load Balancing

If multiple paths with the same cost value exist, the routing engine selects a transfer path at random, as outlined in the previous steps. However, the routing engine does not perform load balancing. As explained earlier, the routing engine caches the message type information that refers to the shortest path a message can take to its destination. Therefore, all messages of the same type travel the same path, even if another path with the same cost value exists (for example, "routing group A > routing group B > routing group E" and "routing group A > routing group C > routing group E").

Load Balancing between Routing Groups

True load-balancing between routing groups can be achieved only by using one Routing Group Connector with multiple bridgehead servers.

The following table lists the load-balancing configurations that you can use between routing groups.

Possible configurations between routing groups

Load Balancing between Connectors and External Systems

Depending on the scenario, there are a few ways to achieve load balancing across SMTP connectors.

• If you want to load-balance outbound requests across multiple servers in the sending organization, configure multiple source bridgeheads.

• If you want to load-balance traffic across multiple destination servers, either have the destination administrator configure DNS correctly (using a suitable configuration of MX and A records), or specify multiple smart host addresses on the connector.

Or, if you want to ensure failover resiliency, create multiple SMTP connectors scoped with the same address space, different costs, and different source bridgeheads. If the bridgehead server on the preferred connector with the lowest cost is unavailable, the connector is considered unavailable and routing automatically chooses the second connector. If you use two connectors with the same cost, Exchange servers randomly select which bridgehead server and connector to use. Then, if this bridgehead server becomes unavailable, they will fail over to the second connector. However, when the first bridgehead server becomes available, the servers will not fail back to this server because the route has the same cost as the server that they are already using.

The connector configuration in the following figure, for example, is not load-balanced for failover configuration because the address spaces do not match. Messages sent to external users in a .NET domain always travel over the SMTP connector with the .NET address space. This is because the routing engine chooses the most detailed address before evaluating costs.

A connector configuration that does not provide load balancing or fault tolerance

Message Rerouting Based on Link State Information

If a connector cannot transfer messages, the advanced queuing engine notifies the routing engine of a link failure. This might cause the routing engine to mark the connector as down, in which case all queued messages are rerouted.

The routing engine considers a connector as down if one of the following conditions is true:

• The routing engine cannot establish a connection to at least one of the connector's source bridgehead servers, and there is no TCP/IP connection to port 691 between the routing group master and the source bridgehead servers. Unavailable source bridgehead servers are marked as VS_NOT_STARTED in the link state table.

• None of the source bridgehead servers can transfer the message to a destination bridgehead server successfully. Source bridgehead servers that cannot transfer messages to the destination are marked as CONN_NOT_AVAIL.

Message Rerouting

To guarantee efficient message transfer, the routing engine informs the advanced queuing engine and Exchange MTA immediately of any link state changes. To avoid sending messages along broken paths, all queued messages must be routed again. This process is named rerouting. In rerouting, the advanced queuing engine discards all cached next hop information, because this information is no longer valid. Each message that is currently waiting to be transferred is passed to the routing engine again, to recalculate the next hop. This can be a resource-intensive task.

The following figure shows a rerouting example in which the bridgehead server in routing group E is down. No messages can reach this routing group currently. When the routing engine recalculates the shortest paths for messages to recipients in routing group E, it discovers that no path is available. Connectors marked as down are excluded from the routing process. Therefore, routing group E is currently isolated.

Broken routing group connectors

Because no valid path exists, the routing engine cannot determine a valid next hop for messages that are waiting to be transferred to routing group E. The routing engine informs the advanced queuing engine, in the next hop type information, that the next hop is currently unreachable. The advanced queuing engine must retain the message until at least one transfer path becomes available, or until the message expires and is returned to the sender with an NDR.

Rerouting and Address Spaces

As with load-balancing, Exchange Server 2003 reroutes messages only over connectors that have the same address space. For example, you can create two separate connectors on different bridgehead servers, each with the same address space but different costs. If the preferred connector becomes unavailable, the routing engine automatically selects the second connector, until the primary connector becomes available again.

If there are restrictions on the connector with the .NET address space, and the restrictions prevent certain messages from crossing this connector, for example because the sender is denied message transfer over this connector, the routing engine returns the message to the sender with an NDR. The routing engine does not fall back to the second connector for those messages. The most detailed address space determines which connectors can be used to transfer a message. Connectors with less detailed address space are excluded from the route calculation.

Connector Recovery

The routing engine determines that a connector is available again in one of the following ways:

• VS_NOT_STARTED   The routing group master establishes a connection to TCP port 691 on the source bridgehead server. The source bridgehead server is marked as CONN_AVAIL, and because at least one source bridgehead server is available for the connector, the connector state switches to STATE UP.

• CONN_NOT_AVAIL   For unavailable connectors, the source bridgehead servers continue to retry connection at 60-second intervals, even if no messages are waiting for transfer. When a connection is established, the advanced queuing engine or the Exchange MTA reports to the routing engine an outbound connection success from the source bridgehead server. The routing engine then switches the source bridgehead server to CONN_AVAIL and the connector to STATE UP.

Rerouting and Activation Schedules

All connector types let you configure a schedule for the connector so that you can transfer e-mail messages at specific times. Connectors can be configured to be always active, to become active only at specified times, or to be never active, in which case the connector does not transfer messages until the connector schedule is changed again. You can also configure a connector as remote initiated, which means that the connector does not initiate a connection itself. Instead, it waits for a remote server to connect and trigger the message transfer.

The connector schedule affects the message transfer only. It does not affect message routing. The routing engine considers connectors with any schedule type as available if they are STATE UP. Therefore, messages might even be routed to connectors for which the activation schedule is set to never. Link state changes and rerouting do not occur for these connectors. Messages wait in the connector's queue until the activation schedule is changed. The same is true for remote initiated connectors. Messages are not rerouted while they are waiting for their retrieval.