Method and apparatus for an automatic load balancing and back-up of a multi-users network

[0002] The present invention relates to data processing in a multi-users communication network and more particularly to a Token Ring Automatic Load Balancing/Backup function in a multiple users environment.

[0003] The invention refers to Fe following terminology:

[0004] 802.2 TEST frame: is an 802.2 Data Link Control (DLC) frame which is used for discovering a route toward a remote station.

[0005] XID frame: is an 802.2 DLC frame which is used for exchanging identification before establishing a connection.

[0006] SABME (Set Asynchronous Balanced Mode Extended) Frame: is an 802.2 DLC frame which is used for establishing a connection.

[0007] UA (Unnumbered Acknowledgment) Frame: is an 8022 DLC frame which is used for confirming a connection establishment.

[0008] Routing Information: is an 802.5 MAC Frame field containing the route which is used for a connection (list of ring numbers and bridge numbers).

[0009] Token Ring User: is the host computer that is shared and connected to a plurality of Token Ring stations.

[0010] MAC address: is the station address on the Token Ring.

[0011] Load Balancing function: enables to switch to another route when a route is overloaded.

[0012] Backup function: enables to back up a route which has become inoperative.

[0013] Resolve Procedure: enables to discover the route to the destination station by means of the Test frame.

[0014] SAP: Service Access Point used for identifying a user of the DLC 802.2. All Route Broadcast implement& the broadcast function that is used for copying the Test frame on all the rings.

[0015] The Automatic Load Balancing/Backup function is an improvement of the Token Ring Architecture. It allows an automatic balancing of the traffic between different Token Ring Adapters using the same MAC address, and also automatic backup in case one of the Token Ring adapter becomes unavailable.

[0016] The U.S. Pat. No. 5,493,689 describes a system for configuring an event driven interface including control blocks defining good loop locations in a memory which represent detection of a characteristic pattern. This technique is a combination of a source of control vectors which sends control vectors in a programmable performance vector generator which is coupled to a data communications network to be monitored and controlled. This invention enables real-time load distribution, load balancing, problem determination, routing and customer services, but it is to be implemented in environment that uses an expert system which analyzes the event vectors and provides monitoring information and control signals to the network.

[0017] The U.S. Pat. No. 5,606,693 and 5,668,986 which respectively relate to “A distributed database management over a network” and to “A method and apparatus for handling data storage requests in a distributed data base environment” are dedicated to a distributed database application for logging large volumes of data to a plurality of databases servers. A central configuration management is employed to balance the database load to direct requesting workstations to the appropriate database. Furthermore, this technique is to be implemented using workstations and database servers and configuration controllers connected to a dual network. In such an environment, a central configuration management and a dual network are unavoidable constraints.

[0018] FIG. 1 shows the different elements which are present in the Automatic Load Balancing/Backup Function.

[0019] The Token Ring User (100) activates 2 different Token Ring Data Link Control (DLC) (102 and 112) and 2 Token Ring Adapters (103 and 113), using the same MAC address, provided the Token Ring Adapters are connected to 2 separate rings (104 and 114).

[0020] When a remote Token Ring station (130) is to be connected to the Token Ring User (100), it uses the MAC address as its destination MAC address, and executes a Resolve Procedure to discover the route to the Destination. It first issues an All Route Broadcast Test frame assigned to the MAC address A.

[0021] Since the Test frame is sent in All Route Broadcast Mode, it is copied on Token Ring (104) by the bridge (105) and also on the Token Ring (114) by the bridge (115). As a consequence, both Token Ring adapters (103 and 113) receive a copy of the Test frame, and both respond. The Remote Token Ring Station (130) selects the first response and establishes the connection. This connection may be deselected in case it is overloaded or inoperative. Should the occasion arises, the second connection is established.

[0022] If the link between the Token Ring user (100) and one of the Token Ring DLCs (for example 102) gets overloaded, this Token Ring DLC (102) does not respond to the Resolve procedure and the connection is established via the other Token Ring DLC (112). This insures an automatic load balancing between the 2 Token Ring DLCs (102 and 112).

[0023] If the link between the Token Ring User (100) and one of the Token Ring DLCs (for example 102) gets inoperative, this latter (102) does no longer respond to the Resolve procedure, and the connection is established with the other DLC (112). This insures an automatic backup between the 2 Token Ring DLCs (102 and 112).

[0024] FIG. 2 shows the Normal Flow of Mono User Load Balancing.

[0025] The Remote Station (130) tries to connect to the Token Ring user (100). It first issues an All Route Broadcast Test frame assigned to the MAC address A and SAP 0. The Test frame is then received by DLC No 1 (102) and DLC No 2 (112).

[0026] When the DLC No 1 (102) receives the Test frame command, it checks whether a Token Ring user (100) is connected to the Token Ring Adapter (103). In such case, the DLC No 1 generates a response to the Test frame. This response contains the Routing Info field of route 1 that connects the Token Ring station (130) to the Token Ring user (100) through the Token Rings (120, 104, 102).

[0027] Conversely, when the DLC No 2 (112) receives the Test frame command, it also checks whether a Token Ring user (100) is connected to the Token Ring Adapter (113). Which is the case in this example. Thus, the Token Ring No 2 (112) responds to the Test frame and includes in its response the Routing Info field of route 2 that connects the Token Ring station (130) to the Token Ring user (100) through the Token Rings (120,114,112).

[0028] In our example, the Test response from DLC No 1 (102) is received first. The Remote Station (130) accepts the first Test frame response it receives, indicating the shortest path, and stores the corresponding route. This route will then be used for the transmission and reception of all frames for this connection between the remote station (130) and the Token Ring user (100).

[0029] In consequence, the Remote Station (130) ignores any additional Test frame response that would be received later on for this connection. The Test frame response from DLC No 2 (112) is ignored since it is received after the one from DLC No 1 (102).

[0030] Once the resolve procedure is completed, i.e. the Test frames are exchanged, the Remote Station (130) sends an XID frame to the DLC No 1 (102). The XID frame which contains the routing information of Route 1, is transmitted to the Token Ring user (100).

[0031] If DLC No 1 (102) receives an XID frame assigned to Token Ring user (100), it checks if this latter is active so as to report it the XID data. If the Token Ring user (100) accepts the connection, DLC No 1 (102) sends back an XID response to the Remote Station (130). This latter sends a SABME command to establish the connection with DLC No 1 (102) which responds with a UA response. The connection for the route 1 is then established and the data traffic can begin on this connection.

[0032] FIG. 3 describes the Normal flow of a single User Backup.

[0033] In this example, the Token Ring user (100) is not available on DLC No 1 (102) but it is still available on DLC No 2 (112).

[0034] The remote station (130) sends a Test frame in the All Route Broadcast mode assigned to MAC Address A. The Test frame is then received by DLC No 1 (102) and DLC No 2 (112).

[0035] When DLC No 1 (102) receives the Test frame, it checks if the Token Ring user (100) is available. Since this latter is not available for DLC No 1, it does not respond to the Test frame.

[0036] On the contrary, when DLC No 2 (112) receives the Test frame, it checks if the application is available for DLC No 2 so as to send back a Test frame response containing the routing information of Route 2.

[0037] The Remote station (130) receives the Test frame response from DLC No 2 (112), and accepts it since it is received first. The routing information of Route 2 is stored and Route 2 will be used for the connection between the remote station (130) and the Token Ring user (100).

[0038] The remote station (130) sends an XID command to DLC No 2 (112), using this route 2. When DLC No 2 receives the XID command, it reports the XID data to the Token Ring user (100) which accepts the connection. DLC No 2 sends an XID response frame back to the Remote Station (130) on this route 2.

[0039] The remote station (130) sends a Set Asynchronous Balanced Mode Extended command (SABME) to Token Ring DLC No 2 (112), which responds with an unnumbered acknowledgment response (UA). The connection is now established between the remote station and the Token Ring DLC No 2. From now on data traffic flows on that connection.

[0040] Statement of Problem and Solution

[0041] FIG. 4 describes the Multi User configuration which environment is almost the same as in FIG. 1, except that a Token Ring User No 2 (400) has been added.

[0042] Both users No 1 and No 2 (410 and 400) share both Token Ring DLC No 1 and No 2 (402 and 412) which are respectively connected to Token Ring Adapters (403) and (413). A Remote Station (430) is connected to each Token Ring User via 2 different routes. Route 1 is composed of Token Ring (420), Bridge (405) and Token Ring (404). Route 2 is composed of Token Ring (420), Bridge (415) and Token Ring (414). The numeral 431 indicates the path between DCL No 1 (402) is not available.

[0043] FIG. 5 describes the Flow of Multi User Load Balancing/Backup without the implementation of the present invention. Remote station (430) tries to connect to Token Ring User 1 (410) which is not available for Token Ring DLC No 1 (402).

[0044] Remote station (430) sends a Test frame command in the All Route Broadcast mode, assigned to MAC Address A The Test frame is received by both Token Ring DLC No 1 (402) and No 2 (412).

[0045] Token Ring DLC No 1 (402) receives the Test frame command, said Test frame being assigned to SAP 0, which means there is no indication of destination user in Test frame. Since DLC No 1 has at least one Token Ring user (400) available (user No 2), DLC No 1 accepts the Test frame and sends back a Test frame response containing the Routing Information of route 1. The Remote station (430) receives this Test frame response as a first Test response for this connection. It accepts the Test frame response and stores this route 1.

[0046] When DLC No 2 (412) receives the Test frame command, it accepts the Test frame and sends back a Test frame response, containing the Routing Information of route 2.

[0047] The Remote Station (430) receives this second Test frame response. Since it has already received a Test frame response for this connection, the remote station ignores this additional test frame response.

[0048] The remote station (430) sends an XID to be transmitted to Token Ring user 1 (410) by using route 1 obtained from the first received Test frame response. DLC No 1 (402) receives the XID and it checks for which Token Ring user the XID is assigned owing to the SAP in the XID frame. DLC No 1 ignores the XID for Token Ring user 1, because this latter is unavailable.

[0049] The remote station (430) times out and retries sending XID frame for Token Ring user 1 (410) through DLC No 1 (402) which ignores them since Token Ring user 1 is not available on route 1.

[0050] After many failed attempts, the remote station (430) starts again with a new Test frame command. Since route 1 is shorter or has a better response time than route 2, DLC No 1 (402) is always the first to respond to the Test frame. Therefore, route 1 will always be selected and the connection between the remote station (430) and the Token Route user 1 (410) through the DLC No 1 (402) will always fail.

[0051] The problem is that the Test frame command contains a field SAP which is unfilled. Thus, the final destination cannot be determined at this stage and it is not possible to determine for which Token Ring user of the connection is available. On the contrary, XID frame contains the information of the final destination, i.e. which Token Ring user, but at that time, it is too late for DLC No 1. The reason of the problem is that the Token Ring DLC cannot determine from the Test frame the identification of the Token Ring user of the connection.

[0052] Besides, the DLC No 1 (402) is too fast to respond to the Test frame of the remote station (430) without taking into account the fact that Token Ring user No 1 (410) is unavailable through DLC No 1 (402). Whereas Token Ring User No 1 is available through DLC No 2 (412), but this latter does not respond to the Test frame earlier than DLC No 1.

[0053] The limitation of the Load Balancing/Backup function in Multi User environment is due to the fact that the resolve procedure Is directed to all Token Ring DLCs and not to a specific Token Ring DLC which is connected to an available Token Ring user.

[0054] Because of this multi-user environment, the link between one of the 2 Token Ring users and one Token Ring DLC may be overloaded while other links are not. In such case, the Token Ring DLC still responds to the resolve procedure since one of its links is not overloaded, and the automatic backup will fail. But if the Token Ring DLC were to ignore the Resolve Procedure because one of the links is overloaded, traffic to the Token Ring user No 1 and No 2 will be backed-up on me other Token Ring DLC. Such situation will interrupt all the connections if the link between Token Ring DLC 2 and user 2 were to be overloaded or inoperative.

[0055] The object of the invention is to suppress this limitation of the Load Balancing/Backup function in a Multi-Users environment, by allowing a remote station to search for an alternate route through another Token Ring DLC to backup as soon as Token Ring user is unavailable through a previously selected Token Ring DLC.

[0056] It is another object of the invention to delay the connection from a remote station to a Token Ring user through a first selected Token Ring DLC for a predetermined delay.

[0057] The implementation of the automatic Load Balancing/Backup function also corresponds to the need in redundancy, backup and load balancing in their single protocol network.

[0058] Furthermore, the network evolution now leads to heterogeneous networks with different protocols, such as SNA (System Network Architecture), APPN (Advanced Peer to Peer Networking) or IP (Internet Protocol). It is therefore required to run these different protocols on the same adapters that are shared by a plurality of networks.

[0059] In addition, according to the present solution, it is possible to use the Token Ring Adapters for different network protocols and to implement the Load Balancing/Backup function.

[0060] According to the parent invention, the DLC memorizes the source MAC address and source SAP of the N remote stations for which an XID connection has been refused because of an unavailable Token Ring user. These MAC addresses and SAPs are stored in a Connection Cache Table. Each Token Ring DLC has its own Connection Cache Table.

[0061] When a Test frame is received, the Token Ring DLC checks in the Connection Cache Table before responding to the Test frame. If the Test frame has been sent from a remote station whose identification is already in the Connection Cache Table, it means this remote station has previously attempted to conned to an unavailable Token Ring User. In such case, the Test frame is ignored and no Test response is sent back to the remote station. This will allow the remote station to have a chance to detect an alternate route with a backup Token Ring DLC if it exists. Otherwise, the connection attempts will be directed to the same Token Ring DLC.

[0062] Each Token Ring DLC manages its own Connection Cache table contents. Each connection cache table entry contains, in addition to the source MAC address and the

[0063] Source SAP, a counter indicating the number of unsuccessful attempted Test frames received from that remote station. When a Test frame is received and the source MAC address/Source SAP of that Test frame is found in the station cache table, the Test frame is ignored but the counter is incremented for that entry. If the counter reaches a predetermined value N, then the entry corresponding to the remote station is removed from the connection cache table. This means that the next time a Test frame is received from this remote station, it will be accepted and a response will be sent from the Token Ring DLC. It will give a new opportunity to the remote station to try to establish a connection to the Token Ring user in case this latter would become available again.

[0064] Thus, the method of load balancing and backing up a connection in communication network according to the present invention comprises the steps as are set in claim 1.

[0065] The apparatus in which the method of the present invention is implemented comprises the features that are set in claim 7.

[0066] FIG. 1 describes the Automatic Load Balancing and Duplicate TIC address in a single user environment in the prior art.

[0067] FIG. 2 scribes the Normal Flow of a single User Load Balancing in the prior art.

[0068] FIG. 3 describes the Normal flow of a single User Backup in the prior art.

[0069] FIG. 4 describes the Multi User configuration and problems associated with it.

[0070] FIG. 5 describes the Flow of Multi User Load Backup.

[0071] FIG. 6 describes the Flow of Multi-User Load Backup according to the present invention.

[0072] FIG. 7 describes the XID processing in a Token Ring DLC according to the present invention.

[0073] FIG. 8 describes the Test frame processing according to the present invention.

[0074] FIG. 9 describes the Connection Cache Table format according to the present invention.

[0075] This solution is applicable in the environment of Token Ring networks running multiple protocols, but could be extended to other 802.2 DLC such as bridged Frame Relay or ATM LAN Emulation etc

[0076] Referring again to FIG. 4, the Token Ring user No 2 (400) and Token Ring user No 1 (410) are connected by Network Interface Card (NIC) 401 and NIC 411, respectively. The NICs are substantially identical. Therefore, the description of one is intended to cover the description of all. A functional representation of the NICs is shown in FIG. 4. The NIC is based on the IEEE-802 Committee implementation of the Open Systems Interconnection (OSI) module adopted by the International Standard Organization (ISO). The NIC includes the adaptor (403,413) which occupy the physical layer of the OSI model. The adapter includes all the necessary hardware and software to perform the functions described in the standards which are incorporated herein by reference. The hardware is well known in the art and further description is not warranted. Suffice it to say that the adapter may implement the Token Ring (802.5), ethernet (802.3), etc. In addition, the hardware may include connectors, conductive couplings, etc. the adapter includes a physical layer and devices for coupling to the network and to the Medium Access Control (MAC) layer functions coacting operatively with a Medium Access Controller to practice a desired network protocol. The Data Link Control (DLC) layer adjoins the adapter (physical layer). The (DLC) layer includes the Medium Access Control (MAC) layer and Logical Link Control (LLC) layer. The respective layers include the functions which are necessary to transport or route frames. The DLC further includes a memory storing information identifying remote stations and frequency with which a remote station is unable to connect with a selected resource in the network. A more detailed description of the respective layers and related hardware is set forth in the article entitled “LAN IC's Let You Build Networks for PC's” by Danny Corrnier, EDN, Dec. 11, 1986, (Page 136) and the IEEE related standards all of which are incorporated herein by reference.

[0077] FIG. 6 describes the Flow of a Multi User Load Backup according to the present invention. This scenario differs from the previous one in that Token Ring DLC No 1 (402) keeps track of the connection failure in a Connection Cache Table.

[0078] When Token Ring DLC No 1 (402) receives an XID frame for Token Ring user 1 (410) which is not available for the Token Ring DLC No 1. This latter ignores the XID frame, but it stores the parameters of remote station in the Connection Cache Table. The parameters are the Remote MAC address and Remote SAP. Therefore, the next time a Test frame is received from this remote station, Token Ring DLC No 1 (402) finds its parameters in the Connection Cache Table and ignores the Test frame command.

[0079] Token Ring DLC No 2 (412) receives the Test frame command and sends a Test frame response containing the routing information of route 2 which connects the remote station to the Token Ring user 1 (410) through the Token Rings (420,414) and the Token Ring DLC No 2 (412). Since the remote station receives this Test frame response first, it stores this route 2. Furthermore, it sends an XID frame to Token Ring user 1 (410) by using this route 2.

[0080] Token Ring DLC No 2 (412) receives the XID frame assigned to Token Ring user 1 (401). It reports the XID frame to this latter. If Token Ring User 1 (410) accepts the connection, Token Ring DLC No 2 (412) sends back an XID response to me remote station (430).

[0081] Afterwards, the remote station (430) sends a SABME to DLC No 2 (412) in response of which this latter responds with a UA response. The connection is now established between the remote station (430) and DLC No 2 (412). From now on, data traffic can flow on this connection.

[0082] FIG. 7 describes the XID frame processing in a DLC whose Test response has been received first by the remote station. When an XID frame is received for an unavailable Token Ring user, DLC ignores the connection, but meanwhile, it adds a new entry in the Connection Cache Table and stores the station parameters.

[0083] The algorithm for the XID frame processing is as follows:

[0084] At step (700), an XID frame transmitted from a remote station is received by a Token Ring DLC. This latter checks in the destination SAP of the XID frame to determine if the Token Ring user associated to this SAP is available at step (701).

[0085] If the Token Ring user is available, then the connection is established at step (702). Otherwise at stop (703), the connection cannot be established and the DLC searches for the remote station in the Connection Cache Table. At step (704), the DLC tests if the entry is found in the Connection Cache Table.

[0086] If the remote station is already stored in the Connection Cache Table, DLC just ignores the XID frame at step (705). Otherwise, at step (706) since the remote station for which the connection is being refused is not found in the Connection Cache Table, the DLC creates a new entry in the Connection Cache Table and stores the remote station parameters. Note that this last entry overwrites the oldest entry in the Cache Table. In addition, the count parameter is set to 1, indicating that one connection has been refused for that remote station.

[0087] The index of the Connection Cache Table is incremented, and if it reaches the bottom of the table, it wraps to the top of the table.

[0088] And finally at step (707), the DLC ignores the XID frame.

[0089] FIG. 8 describes the Test frame processing according to the present invention.

[0090] When a Test frame is received in an all broadcast mode, all Token Ring DLCs scan the Connection Cache Table to determine if a connection has previously been refused for the same remote station. Should the occasion arise in one of the Token Ring DLCs, it ignores the Test fame so as to give the opportunity for the remote station to obtain a backup connection to the Token Ring user.

[0091] The algorithm for the TEST frame processing is as follows:

[0092] At step (800), each DLC receives a Test frame sent from a Remote Station. Then, each DLC scans in the Connection Cache Table to determine if a connection has previously been refused for ma same remote station at step (801). It checks in the Connection Cache Table at step (802) if an entry of the remote station already exists.

[0093] At step (803), if the remote station is not found in the Connection Cache Table, the DLC processes the Test frame command and sends a Test frame response back to the Remote Station. Otherwise, at step (804), the DLC increments its own counter in the Cache table, indicating that an additional connection is being refused for that remote station.

[0094] Then, at step (805), the DLC checks if the counter has reached maximum value (N). If the maximum value (N) has not been reached, then the DLC ignores Fe Test frame at step (806). Otherwise, at step (807), the DLC deletes the corresponding entry in the Connection Cache Table. This means that the next Test frame received from that remote station will be processed and responded by this DLC.

[0095] And finally at step (808), DLC ignores the Test frame and does not respond.

[0096] FIG. 9 describes the content of the Connection Cache Table. The Connection Cache Table (900) contains the Remote Station MAC address and the Remote Station SAP. These parameters allows the DLC to identify the Remote Station. It also contains a connection Counter (count) indicating the number of unsuccessful connections of the remote station.

[0097] When a connection is refused for a remote station, a new entry (901) dedicated to this remote station is created in the Connection Cache Table. This new entry overwrite the oldest entry. Only a predetermined number M of the last unsuccessful connections are stored in the Connection Cache Table.

[0098] When a new entry is created, the Counter is set to 1. Then the index (903) is incremented and points toward the next entry (902). The Connection Cache Table wraps automatically when the bottom of the table is reached.

[0099] The connection cache table has a limited size (M entries). The number of entries must be sufficient to contain all the possible connections between the remote stations and a Token Ring user during a certain time. The best rational is to have M equal to the maximum number of connections between all the different remote stations and a user.

[0100] However, this table should not be too large because it has to be scanned whenever a Test frame is received, and a large table could impact on the performances. The connection cache Table has an index, pointing to the oldest entry in this table, once all the entries have been filled. Since this table has M entries, the index points back to the first position at the M+1 input. When a new connection is refused and the Source MAC address/Source SAP is not yet in the cache table, these new parameters are added in the connection cache table at the entry pointed by the index, and overwriting the oldest entry. The index is then incremented and wraps when the end of the table is reached. In this way, a new connection can be attempted to the destination user on the next Test frame received from said remote station.

[0101] In this document, in order to simplify the comprehension of the invention, a configuration of two Token Ring DLCs (routes) and two Token Ring users is described. But this invention is applicable in a more complex configuration with I Token Ring Remote Stations (130,430) connected to K Token Ring DLCs (402,412) with their associated Token Ring Adapters (403,413) through J Token Rings (404,414,420) and L Token Ring users (400,410). This kind of configuration will not influence on the different processes of the present invention.

[0102] Furthermore, it should be kept in mind that though the description is based on the environment of Token Ring networks running multiple protocols, it could be extended to other 802.2 DLCs such as bridged Frame Relay or ATM LAN Emulation.

[0103] While the invention has been described in terms of preferred embodiments, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims.