Networked computer with gateway selection

A networked computer system in which a gateway is selected for efficient transmission over a network using a layered protocol. When a transmission over the network fails, information at multiple protocol layers indicates the usability of the gateway through which the failed transmission was made. In a layered protocol with an application or connection layer, a path layer and a link layer, information at the link layer is used to determine whether retransmission through the same gateway should be attempted. Information at the path layer is used to determine whether the gateway is faulty. Information from the application or connection layer is used to determine whether responses are received to transmissions. These determinations are used in setting the status of the gateway, which in turn is used to prioritize gateways when selecting a gateway for future transmissions. The system also temporarily raises the priority associated with a gateway so that it will be used in a transmission, which can reveal that the state of the gateway should be changed.

BACKGROUND

Networks facilitate the exchange of information between applications running on different computers. Computers with applications that share data with other computers are used pervasively in both personal and business settings. As a result, networks are now widely used in both homes and offices to transmit many types of information.

Information sent over a network is traditionally formatted in packets. Each packet contains a header with routing information, which allows network devices to process the packet so that it reaches its intended destination. Each packet is traditionally formatted according to a protocol, which specifies what routing information is included the header and how network devices respond to that information. For example, a protocol may specify that a device receiving a packet generate an acknowledgement message so that the device sending the packet learns that the packet was received.

Multiple layers of routing information are needed to provide sufficient information for all network devices to route information from an application on one computer to an application on another computer. At the highest interconnection layer, a specific application on a computerized device must be specified. At the lowest layer, each computerized device is connected to a local network and has an address on that local network, which must also be specified. A middle layer is also required because networks may be formed from interconnected local networks, and information must be specified to allow information to be routed from one local network to another. These layers may be called, from highest to lowest, a connection or application layer (depending on the protocol), a path layer and a link layer.

A network will frequently operate according to a layered protocol, with each layer being a protocol that specifies processing of a packet, or other interactions, appropriate for one interconnection layer. For example, a widely used layered protocol is the TCP/IP/ARP layered protocol. TCP is a protocol used at the connection layer. IP is a protocol used at a path layer, and ARP is a protocol used at the link layer.

In many computers, a network stack formats information and performs other processing required to comply with a layered protocol. The network stack frequently is part of the computer's operating system and contains a number of software modules, each performing processing appropriate for one protocol layer.

To ensure that information is properly transmitted over a network, the network stack manages the process of transmitting a packet, including compensating for errors. For example, if the network stack attempts to transmit a packet and does not receive an acknowledgement within a timeout period, the network stack may make another attempt to transmit the message. The network stack may make multiple attempts to transmit a packet until successful or until it eventually reports to the application attempting to send information that the transmission failed.

A network stack may also select transmission parameters to increase the likelihood that a packet reaches it destination. For example, in a computer that has multiple “gateways” to a network through which packets could be sent, a network stack may select a gateway for transmission of a packet deemed best for transmission of the packet. The gateway could be selected based on information about whether packets with similar addresses had been previously routed successfully through that gateway.

Information specifying which gateways had been previously used for transmission to specific destination addresses is stored in a routing table. The routing table stores, for prior successful transmissions, the destination address and the gateway used. As each new packet is transmitted, a routing module within the network stack selects an entry in the routing table, which specifies a gateway through which that packet is transmitted.

Selection of an entry in a routing table may be based on multiple criteria. One criteria is the closeness of the match between an address in the routing table and the destination address in that packet to be transmitted. Matching is performed based on the number of identical bits in the prefixes of the addresses being compared. If no address in the routing table matches any prefix bits of the destination address in a packet, the network stack transmits the packet through a “default gateway.”

To avoid attempting to transmit packets through a gateway that could not support communication, the status of the default gateway may be monitored. In the MICROSOFT WINDOWS XP® operating system, the network stack classifies the default gateway as “dead” if 75% of the transmissions over connections that use the default gateway fail. When the default gateway is classified as “dead,” it is not used for further transmissions. If another gateway is classified as “live,” the live gateway is used. However, if there is no “live” gateway, the transmission fails.

SUMMARY OF INVENTION

Gateway selection according to the invention may reduce the time required for each transmission, reduce the circumstances in which a transmission fails or improve network communication by increasing the number of circumstances in which the best available gateway is used for a transmission.

Gateway selection involves prioritizing gateways based on the success or failure of prior transmissions. As each new transmission is processed, priority information may be used to select a gateway. For example, if a transmission fails, the priority assigned to the gateway used for the failed transmission may be lowered and a new gateway may be selected based on previously computed priorities.

However, not every failed transmission attempt results in selecting a new gateway or reprioritizing the gateway used for a failed attempt. In a networked computer operating according to a layered protocol, information from multiple protocol layers may be used for gateway selection to more accurately determine the status of a gateway. For example, information may be obtained from a link layer, indicating whether network neighbors are reachable through a gateway. Alternatively, information may be obtained through the path layer to determine a quantity of paths that are unreachable through a gateway. Similarly, information may be obtained through the connection or application layer to determine whether responses are received for transmissions sent through a gateway. By using information from other protocol layers, a more accurate assessment of the status of a gateway can be made, which avoids disqualifying a gateway for use based on transmission problems unrelated to the gateway and avoids time spent attempting to transmit through a gateway that will not support a transmission.

Prioritizing gateways improves selection of a gateway, even if all gateways have experienced at least one transmission failure. Further, the priority of a gateway can be periodically raised to test whether a gateway through which a transmission previously failed is usable, which increases the likelihood that the best available gateway will be used for a transmission.

DETAILED DESCRIPTION

Gateway selection according to embodiments of the invention may be implemented by programming a computer operating in a conventional network environment.FIG. 1shows a network in which gateway selection according to an embodiment of the invention may be used. A computer, such as laptop computer112, is connected to the network. Laptop computer112has multiple gateways. A gateway selection process is described below using as an example transmission of packets by laptop112, which may be programmed to perform gateway selection according to an embodiment of the invention.

As shown inFIG. 1, laptop computer112is connected to local area network (LAN)122. Other devices may be connected to LAN122. In the example ofFIG. 1, computers124and126are shown connected to LAN122. The devices connected to LAN122are considered “neighbors” of laptop computer112.

Laptop computer112can communicate with neighbor devices without transmitting packets through a device that connects LAN122to a broader network. In the example ofFIG. 1, router128is shown coupling LAN122to a wide area network, which may be Internet130. The connection through router128allows a device connected to LAN122to communicate with a remote device, such as remote server140, that is also connected to Internet130.

The network ofFIG. 1may operate according a layered protocol as in a conventional network. Accordingly, each device connected to the network may have an address specified at the link layer of the layered protocol. Applications within laptop computer112may establish connections with applications running on remote devices, such as remote server140, in accordance with the protocol of the connection layer. Each connection may be associated with a path in compliance with the protocol of the path layer of the network.

As shown inFIG. 1, laptop computer112may connect to local area network122over wireless link114. Wireless link114connects laptop computer112to LAN122through wireless access point120. In addition, laptop computer112is connected to LAN122through wired link116. In the configuration illustrated, laptop computer112is said to have multiple gateways through which packets may be transmitted. Packets transmitted through one gateway are intended to pass over wireless link114to LAN122. Packets transmitted through a second gateway are intended to pass over wired link116to LAN122. Within LAN122, the packets may be processed according to the rest of the protocol information in the packet so that each packet should ultimately reach its intended destination.

Packets transmitted through either gateway should ultimately reach a device connected to the network. However, problems can arise in network transmission that prevent a packet from reaching its destination. Because packets transmitted through different gateways may encounter different problems, one gateway may be more suitable for sending a transmission than the others. Accordingly, laptop computer112, and other devices with multiple gateways, may be programmed to select an appropriate gateway for each packet based on routing information specified in the path protocol layer.

The system ofFIG. 1may be implemented using conventional hardware devices. Those devices may be programmed using conventional programming techniques to create applications, establish connections, process information according to a layered protocol, build a routing table and to transmit a packet through a selected gateway. However, in the example ofFIG. 1, laptop computer112is additionally programmed to select gateways for transmission of packets according to an embodiment of the invention.

FIG. 2shows a block diagram of a software architecture that may be used in implementing the programming for laptop computer112or other device performing gateway selection according to an embodiment of the invention.FIG. 2shows that computer112is programmed with an application layer210. Application layer210represents one or more applications that laptop computer112performs. Application layer210, for example, may contain a word processing program, an e-mail program, a web browser, or any other desired application program. Each application generates information for transmission to other devices. Information for transmission is passed from application layer210to network stack212.

As in a conventional computer, network stack212may be implemented as a portion of the operating system of laptop computer112. Also as in a conventional computer, network stack212may be implemented in multiple layers, each layer corresponding to a protocol layer of a layered protocol used on the network. In the example ofFIG. 12, processing at each of the protocol layers is illustrated to be performed by a separate software module. Accordingly, network stack212includes connection layer214, path layer216and link layer218. Such an implementation is conventional, but it is not a requirement of the invention that processing had each layer be preformed in a separate module.

In the example ofFIG. 2, connection layer214implements processing according to a TCP protocol. However, any suitable connection level protocol may be used. As an application in application layer210needs to send information to a destination application in another device, connection layer214establishes a TCP connection from that application in layer210to the destination application. Any information passed to network stack212identifying that TCP connection will be processed by network stack212to generate packets formatted to pass through the network to the destination application.

Each connection must specify the destination device in which the corresponding application resides. The destination device is specified at the path layer. Accordingly, each connection formed in connection layer214is associated with a path within path layer216. Such processing may also be as in a conventional networked computer. Processing performed at link layer218may also be as in a conventional networked computer.

Once a packet is processed in link layer218, routing module220selects a gateway for transmission of the packet. In the illustration ofFIG. 2in which laptop computer112has two gateways, routing module220selects between gateway230A and230B.

If gateway230A is selected, routing module220directs the packet to driver232A, which controls a network interface card234A. Network interface card234A provides a physical interface through which laptop computer112may connect to a network. In this example, network interface card234A connects to wireless link114. Accordingly, network interface card234A may be a wireless network interface card such as is conventionally used in a laptop computer. However, the specific physical connection made to gateway230A is not important to the invention, and any suitable connection may be used.

Conversely, routing module220may select gateway230B for transmission of a packet. In that circumstance, routing module220passes the packet to driver232B, which controls network interface card234B. In the example ofFIG. 2, gateway230B connects laptop112to LAN122through a wired link. Accordingly, network interface card234B may be a convention network interface card designed to interface to LAN122through a cable.

Routing module220may select between gateways230A and230B, or more generally between any gateways in laptop computer112, using processing intended to maximize the likelihood that the packet will reach the intended destination efficiently. An example of processing to select a gateway is described below in connection withFIG. 5.

One aspect of gateway selection is prioritizing the gateways. Gateway priorities are assigned by gateway prioritization module240. Gateway prioritization module240assigns each gateway a priority representing the likelihood that the gateway is functioning for transmission of packets. An example of the processing performed in gateway prioritization module240is given below in connection withFIG. 4.

In embodiments described herein, priorities of gateways are related to the state of the gateway. In some embodiments, one of three states is assigned to each gateway. Those states are “LIVE,” “DEAD” and “PROBE.” However, additional or different status codes may be used to define a priority for a gateway.

A status code of “LIVE” may indicate the highest priority and could be assigned to gateways either known to be functioning or that have not experienced sufficient failures that a problem with the gateway is indicated. Conversely, a status code of “DEAD” may indicate the lowest priority and could be assigned to gateways that have experienced sufficient failures that a problem with the gateway is indicated. A status code of “PROBE” may indicate an intermediate priority and may be temporarily assigned to gateways previously classified as “DEAD so that these gateways will occasionally be used to attempt a transmission.

Attempting a transmission through a gateway from time-to-time allows the status of a DEAD gateway to be changed if conditions on the gateway change so that the gateway no longer warrants classification as a DEAD gateway. For example, radio frequency interference may make a gateway using a wireless link DEAD at one time, but that interference could be removed so that the gateway is again usable. Similarly, a gateway incorrectly classified as DEAD because many transmissions through that gateway failed for reasons unrelated to a failure in the gateway could be returned to a LIVE status.

FIGS. 3A,3B,3C and3D illustrate data structures used in the processing within network stack212. These figures illustrate conceptually how data is stored in RAM within laptop computer112. Data is graphically depicted as being stored contiguously in memory. However, the precise organization of the information and the type and location of the memory in which it is stored are not critical to the invention. Any suitable way may be used to store the data.

FIG. 3Ashows a connection data structure310used for processing within connection layer214. As described above, applications within application layer210form connections with applications in the application layers of other devices. Each connection uniquely identifies a source and destination application. Connection data structure310illustrates the types of information that may be stored about connections.

In the example ofFIG. 3A, connection data structure310includes multiple records3121,3122. . .312N. Each record stores information about one connection. Record312Nstores data about connection N and illustrates the types of data that is stored for each connection. Record312Ncontains multiple fields, of which fields314N,316Nand318Nare shown. Field314Nis an identifier for the connection described by the rest of the data in row312N. In this example, connections are numbered sequentially from1through N, but any suitable representation may be used. The connection identifier in field314Nmay be used by connection layer214to identify the connection over which information provided by application layer210is to be transmitted.

Field316Nprovides information about the source and destination applications for information transmitted using connection N. Each source and destination may be identified by port number or any other suitable identifier. Additionally, record312Nincludes field318N, which identifies a path used for transmission of information over connection N. In the illustrated embodiment, each path is described by information stored in path data structure320(FIG. 3B). Accordingly, information stored in field318Nmay identify a record within path data structure320(FIG. 3B).

Connection data structure310does not contain information specifically used in gateway selection or gateway prioritization. Accordingly, network stack212may generate and process information describing a connection in a conventional manner.

FIG. 3Bshows path data structure320according to an embodiment of the invention. Path data structure320includes records3221,3222. . .322M. Each of the records holds information about one path that may be used for communication between laptop computer112and another device.

Each of the records3221,3222. . .322Mstores the same type of information. Record322Mstores information about path M and illustrates the type of information that is stored for each path. Record322Mcontains multiple fields, of which fields324M,326Mand328Mare shown.

Field324Mcontains an identifier for the path described in record322M. Field324Mmay store information in any suitable form to identify the path described by the remainder of record322M. In this example, paths are numbered sequentially from1through M, but any suitable representation may be used. The identifier stored in field324Mmay be the same identifier stored within field318N(FIG. 3A) to associate a specific path with a connection.

Field326Mstores information describing a specific path. Because a path is an association between a source and destination computer, field326Mincludes an address for the source and destination computer in path M. Other information about path M required for processing in accordance with the specific path protocol used by a network to which computer112is connected may also be stored within field326M. Though field326Mis shown as a unitary field, it may contain one or more subfields to store the required information.

Record322Malso includes a field328M, which stores information about gateways through which packets addressed for path M have been transmitted. Field328Mmay also contain one or more subfields, each providing information on a different gateway. The information stored in field328M, for example, may indicate whether a transmission on path M through the gateway succeeded or failed. Information on gateway status associated with each path may be used in gateway selection or prioritization as described in greater detail below.

FIG. 3Cillustrates routing table340. Routing table340is a data structure used as part of gateway selection within routing module270(FIG. 2). Routing table340may be a routing table as is conventionally built and used in networked computer system. Routing table340associates a specific destination address with a gateway through which transmissions addressed to a specific destination address may be sent. As in a conventional system, routing table340may be built by caching destination and gateway information following each successful transmission.

As shown inFIG. 3C, routing table340includes records3421,3422. . .342x. Each record provides an association between a destination address and a gateway. Taking record342xas illustrative, each record includes a field344xand a field346x. Field344xstores a destination address and field346xidentifies a gateway through which a packet addressed to that address was successfully transmitted.

FIG. 3Dillustrates gateway data structure360. Gateway data structure360stores information concerning the gateways in laptop computer112. In the example ofFIG. 3D, each gateway is described by a record in gateway data structure360. In the illustration ofFIG. 3D, records3621,3622. . .362yare shown. Record362ystores data about gateway Y and illustrates the types of data that is stored for each gateway. Record362ycontains multiple fields, of which fields364y,366y,368y,370yand372yare shown. Field364ystores an identifier for the gateway identified by the data in record362y. In this example, the gateways are numbered sequentially from1to Y. These identifiers provide a mechanism for a gateway to be identified in field346xof routing table340(FIG. 3C), but any suitable manner may be used to identify a gateway.

Field366yidentifies a state assigned to gateway Y. In some embodiments, the state can be “LIVE,” “DEAD” or “PROBE,” and field366ymay store a value indicating one of these states. The value in field366ymay be assigned by gateway prioritization module240(FIG. 2), though each gateway may be initialized to indicate that it is in a LIVE state. As described in more detail below, the states of the gateways may be used to prioritize the gateways when selecting a gateway for transmission of a packet.

Gateway data structure360may also contain other information used in selecting a gateway for transmission of a packet. Field368ystores a performance metric for gateway Y. The information stored in field368ymay be obtained as in a conventional networked computer. For example, a network interface card may measure one or more parameters of transmissions, which may serve as a metric for a gateway. Examples of metrics that may be suitable are data rate, measured noise, percentage of dropped packets and received signal strength.

Field370ystores a further performance parameter associated with gateway Y. In this example, field370ystores a Boolean value indicating whether a neighbor of computer112can be reached through gateway Y. Neighbor reachability may be determined by transmitting a “neighbor reachability probe” using information available at the link layer of the layered protocol. For example, the address resolution protocol (ARP) specifies a format of transmissions on a network that allow one computer to determine whether there are links joining that computer to a neighbor. The value in field370ymay be set using processing as in a conventional networked system.

Field372ystores a time value. The value in field372ymay also be used within gateway prioritization module240(FIG. 2) as part of the gateway selection process. As described in more detail below, once a gateway is assigned a DEAD state because communications through that gateway failed, gateway prioritization module240may from time to time set the state of that gateway to PROBE. Setting the state to PROBE alters the priority of the gateway, increasing the likelihood that the gateway will be selected by routing module270(FIG. 2). As a result, a gateway with a PROBE state may be used for an attempted transmission.

The value in field372ymay be used by gateway prioritization module240to determine an appropriate time to alter that state associated with gateway Y. Any suitable format may be used to store information in field372y. For example, the value stored in field372ymay identify a time at which the state of gateway Y should be set to PROBE. Alternatively, the value in field372ymay identify a time at which the priority of gateway Y was most recently set to DEAD. These time values may be specified in offsets of a system clock of computer112or any other suitable format.

Different or additional information may be stored in gateway data structure360. For example, information identifying the paths or the number of paths used by a gateway may be stored.

Turning now toFIG. 4, processing performed as part of transmission of a packet is illustrated. The processing ofFIG. 4is described in connection with components of network stack212(FIG. 2) and data structures as shown inFIGS. 3A. . .3D. However, the process may be implemented with any suitable hardware or software.

The process ofFIG. 4starts following a first attempt at transmission of the packet. At decision block410, the process branches depending on whether the transmission attempt succeeded. If the transmission succeeded, no changes to either the selected gateway or prioritization of the gateway used for the transmission are required. Accordingly, the process branches to block411.

At block411, a record in path database320(FIG. 3B) may be updated. If necessary, the record corresponding to the path over which the packet was successfully sent is updated to indicate the gateway used for the transmission.

In some circumstances, processing at block411may also alter that state assigned to the gateway through which a transmission succeeded. If a gateway is in a PROBE state, the gateway was previously classified as DEAD, but a transmission is being made through that gateway as a way to test whether a defect still exists with the gateway. A successful transmission through the gateway may be taken as an indication that the gateway is LIVE, and processing at block411may change the state of the gateway accordingly.

In other embodiments, different or additional processing may be performed at block411to indicate whether a gateway in a PROBE state should be indicated as LIVE. For example, the status of a gateway may be changed to LIVE only if multiple transmissions succeed through that gateway. However, regardless of the specific processing performed at block411, processing thereafter proceeds to termination point412, where processing of the packet within network stack212concludes.

Conversely, if the transmission attempt failed, processing proceeds from decision block410to decision block420. At decision block420, the process branches depending on whether the failed transmission attempt was the first transmission attempt for the packet. On the first failed transmission attempt, the process branches to block422.

At block422information from the link layer of the protocol is used to select a gateway for a subsequent transmission attempt. In this example, information from the link layer is obtained by probing for network neighbors. For a computer connected to a network using the address resolution protocol (ARP) at the link layer, probing for network neighbors may be performed according to that protocol. However, any suitable method of obtaining information from the link layer concerning connections through the gateway may be employed.

The results of probing for network neighbors at block422may be recorded in gateway data structure360in connection with the gateway used for the failed transmission attempt. Specifically, information obtained at block422on a gateway Y may be used to update field370y. Additionally, the results of probing at block422may be used to control branching as processing proceeds to decision block424.

At decision block424, the process branches depending on whether a network neighbor was identified as a result of probing at block422. If a neighbor is reachable through the gateway, a failed transmission attempt is unlikely to have been caused by a faulty gateway. Accordingly, processing branches from decision block422to block426where a further attempt is made to transmit the packet through the same gateway.

Conversely, if probing at the link layer was unable to reach a neighbor, retransmission through the same gateway is unlikely to be successful. Accordingly, in this circumstance, the process branches from decision block424to decision block440.

At decision block440a check is made whether there is an alternative gateway available. As described above, routing module270selects the best available gateway based on multiple criteria that are explained in greater detail in conjunction withFIG. 5, below. The first transmission attempt is made with the gateway best meeting the criteria applied by routing module270. When processing reaches decision block440, the gateway ranked second highest based on the criteria applied by routing module270is identified. If a next best gateway exists, processing branches to block442.

At block442, the data structures used by network stack212are updated to indicate that an attempted transmission through a gateway was unsuccessful. In this example, path data structure320is updated and gateway data structure360may be updated. The record in path data structure320associated with the path through which the transmission was attempted is updated. That record is updated to indicate the gateway through which failed transmission attempt was made. For example, if the attempted transmission was on path M using gateway Y, record322Mmay be updated. Within record322M, field328Mmay be updated to indicate an attempted transmission through gateway Y failed.

At block442, information in gateway data structure360may also be updated, if appropriate. Because a transmission could fail for many reasons unrelated to a problem with a gateway, a gateway is not deemed DEAD if a single transmission fails through that gateway. In the described embodiment, processing at block442determines whether a sufficient number of transmission attempts through the gateway have failed to warrant a conclusion that the gateway is defective with sufficient confidence to lower its priority.

In some embodiments, a faulty gateway is deemed DEAD based on the percentage of paths using that gateway over which transmissions have failed. Processing at block442, for example, may access path data structure320(FIG. 3B). Gateway status fields in each of the records3221,3222, . . .322Mmay be accessed. The information stored in these fields provides a quantitative measure of the number of paths using the same gateway as the failed transmission attempt. If this measure is large enough, the gateway is deemed DEAD. If the percentage exceeds a threshold, the gateway may be deemed defective and gateway data structure360(FIG. 3D) may be updated. Specifically, if gateway Y is deemed defective, the value in field366ymay be set to a value of DEAD, giving gateway Y a low priority in subsequent processing to select a gateway.

In one embodiment, the percentage of paths using the same gateway as the failed transmission attempt is used as the quantitative measure. The precise value used for the threshold is not crucial to the invention. In some embodiments, the threshold will be a percentage between 50 and 100 percent. In some embodiments, the percentage will be approximately 75 percent.

A gateway used for a failed transmission attempt may also be have its state changed if it was in the PROBE state. This circumstance indicates that the gateway was previously marked as DEAD and was given a status of PROBE to increase the likelihood that it would be selected for transmission as a way to test whether the gateway was still exhibiting transmission problems. In this circumstance, a single transmission failure through the gateway may be taken as an indication that further transmission attempts through the gateway would be inefficient and the gateway is properly marked as DEAD. Accordingly, processing at block444may also change from PROBE to DEAD the status of a gateway through which a transmission failed. However, in other embodiments, different or additional criteria may be used to change the state of a gateway from PROBE to DEAD. These different or additional criteria may be applied at block442.

Once path data structure320and, if appropriate, the gateway data structure360have been updated to block442, processing proceeds to block444. At block444, the gateway associated with the packet being transmitted is changed. Any suitable manner may be used to change the gateway associated with a packet being transmitted. For example, routing module220(FIG. 2) may store information indicating that subsequent attempts to transmit the packet are to be directed to the newly selected gateway. Regardless of the specific mechanism used to change the gateway at block444, processing again loops back to block426. At block426a further attempt is made to retransmit the packet.

Following an attempt to retransmit the packet, the process branches back to decision block410. If the retransmission attempt is successful, the process branches from decision block410to block411and then to termination point412, as described above. Conversely, if the second attempt is unsuccessful, the process again passes to decision block420. Following the second attempt to transmit a packet, the process branches from decision block420to decision block430.

At decision block430a check is made whether the number of transmission attempts for a packet has exceeded one-half of the maximum times that a transmission will be attempted before a transmission failure is declared. The maximum number of transmission attempts for a packet is a parameter that may be set as part of configuring a computer or in any other suitable manner. The exact value of that parameter and the manner in which it is set are not critical to the invention.

If the transmission has not been attempted one-half of the maximum number of attempts, the process branches again to block426where a further transmission attempt is made through the same gateway. The process will continue to loop back through decision block430and block426until either the transmission is successful, in which case the processing will reach termination point412, or one-half of the maximum number of transmission attempts will be exceeded.

When processing loops back to decision block430after one-half the maximum number of transmission attempts has been exceeded, processing branches from decision block430to decision block432. At decision block432a check is made whether the specified maximum number of transmission attempts has been exceeded. If the maximum number of attempts has not been exceeded, further attempts at transmission are made. However, further attempts are made with a different gateway, if one is available. Accordingly, processing branches to decision block440, where further transmission attempts are made as described above.

As with the prior transmission attempts, if the attempt succeeds, the process branches to block411and termination point412. However, if no transmission attempt is successful, the maximum number of transmission attempts will eventually be exceeded. At this point, processing will branch from decision block432to block450.

At block450, path data structure320and, if appropriate, gateway data structure360will be updated. Processing performed at block450may be the same as that described above in connection with block442. Thereafter, processing proceeds to termination point452where it was ultimately deemed that the overall transmission failed.

The processing pictured inFIG. 4serves as one example of how gateways may be efficiently assigned to one of multiple states. Though a packet is transmitted over a connection, which is at one layer of a layered protocol, information at both the path and link layers of the layered protocol is used to determine whether a gateway is selected for a specific packet sent over a connection.

Information at the link layer limits the number of unsuccessful attempts that will be made using a gateway through which successful transmission is unlikely. In the specific example, probing at the link layer is used to control the number of transmission attempts are made through a gateway before a new gateway is tried. Reducing the number of transmission attempts can decrease the overall time required to transmit a packet and may also decrease the likelihood that that the transmission will timeout and fail without transmitting the packet. Either or both of these results can increase the experience of a user of laptop computer112. Both of these results is particularly important for users of computers that may have three or more gateways.

Information at the path layer is used to reduce the likelihood that an operational gateway is deemed dead incorrectly. Declaring a path as dead, if it is fact operational, means that subsequent transmissions may not use the most efficient gateway. Using information at the path layer is more accurate than simply using information from the connection layer as in the prior art. Because multiple connections may be carried over a single path, a failure in that path can create a large number of failed connections. If only information from the connection layer is used to assess whether a gateway is dead, a gateway may be classified as dead incorrectly if it is used for a faulty path shared by multiple connections. Using information from the path layer avoids this problem and leads to more accurate classification of gateways.

Further, status information on a gateway, even if the gateway is deemed dead, is not used to preclude all use of a gateway. Rather, the status information is used to establish the priority of a gateway. Setting status in this fashion can increase the efficiency of gateway selection by allowing a gateway that once experienced a problem to be properly classified if the conditions blocking communication through that gateway are altered. Using status to prioritize gateway selection may also allow a gateway that is substandard to be used if it is the best available gateway. In this way, transmissions may continue, though degraded, in situations in which prior art processes may have indicated a communication failure.

Turning toFIG. 5, an example is provided of processing that uses status information to prioritize gateways. The process ofFIG. 5applies a series of criteria sequentially until a single gateway is identified. The processing inFIG. 5provides one example of criteria that may be used and of the order in which the criteria may be applied.

The processing ofFIG. 5begins at block510. At block510the subset of gateways with reachable neighbors is selected. Block510may select gateways with reachable neighbors by querying gateway data structure360. As illustrated inFIG. 3D, each gateway has a record in gateway data structure360with a field, such as field3704, that stores an indication of whether neighbors have been detected through that gateway.

Once the processing at block510is completed, processing proceeds to decision block512. At Decision block512, the process branches based on whether at least one gateway is selected. If no gateways are selected, the process branches to block514. At block514all of the gateways are selected. Selecting all gateways at block514is equivalent to ignoring the selection criteria of neighbor reachability when no gateways have a reachable neighbor. Alternatively, if no gateways have reachable neighbors, no gateway may be selected and the transmission may simply fail.

Following block514, processing proceeds to decision block516. If processing at block510selected one or more gateways with a reachable neighbor, processing will proceed from decision block512to decision block516. Accordingly, regardless of the number of gateways selected at block510, processing will reach decision block516. When processing reaches decision block516, a subset of the gateways, which may includes from one to all of the gateways, has been selected.

At decision block516a check is made based on the number of gateways in the subset. If a single gateway has been selected, no further processing is required and processing branches from decision block516to termination point550. Alternatively, if multiple gateways have been selected, processing branches from decision block516to block518.

Block518is the beginning of processing in which criteria are sequentially applied to select a gateway.FIG. 5shows just one example of the types and orders in which the criteria may be applied. For example, in some embodiments, processing at block524occurs before processing at blocks518and520.

However, for the illustrated embodiment, process proceeds to block518where any gateways previously allocated a low priority are processed to determine if any such gateways should be temporarily assigned a high priority so that the gateway may be probed. In this embodiment, a gateway previously marked DEAD is from time-to-time set to a status of PROBE. As described above, gateway data structure360includes a state field, such as field366y, and a time field, such as field372y. Processing at block518may examine gateway data structure360to identify gateways having a DEAD state for which the value specified in the timer field has been reached. At block518each of those gateways may be given a temporary high priority, such as by marking them to be in a PROBE state.

Processing then proceeds to block520. At block520a further selection is made from the subset of gateways previously identified. Only those gateways marked with the highest priority are selected. For purposes of processing at block520, gateways with a status of LIVE and PROBE may be considered to have the same priority. In the described embodiment, all gateways with those status values are selected, if any. If no gateways have either of those status values, all gateways in the subset with a status of DEAD may be selected. In embodiments in which other status values are used, selection at block520may reflect the relative priorities associated with those status values.

Processing then proceeds to decision block522. If application of selection criteria at block520results in a single gateway being identified, processing branches to termination point550with the identified gateway being used for the transmission.

If the selection criteria did not result in selection of a single gateway, processing proceeds to block524. At block524, the gateway with the longest prefix matching the prefix of the destination address for the packet being transmitted is selected. Processing at block524may be performed as in a conventional network stack.

Thereafter, processing proceeds to decision block526. If processing at block524results in selection of a single gateway, processing branches to termination point550. Conversely, if multiple gateways have the same longest prefix length, processing continues to block528where further selection criteria are applied. At block528, the gateway from the identified subset having the highest metric is selected. Processing at block528may be performed as in a conventional network stack.

If selection of a gateway based on a metric results in the selection of a single gateway, processing branches from decision block530to termination point550. However, if multiple gateways in the subset of gateways selected have the same highest metric, processing proceeds to block532.

At block532, a further criteria is applied to select a single gateway. In this example, a single gateway is randomly selected from the identified subset of gateways. However, any suitable process may be used to select a single gateway. Thereafter, processing proceeds to termination point550. When processing reaches termination point550, regardless of path through the flowchart ofFIG. 5, a single gateway has been selected for use in the next transmission. The process ofFIG. 5may be used both to select a gateway for an initial attempt to transmit a packet and at any time that processing reaches block444(FIG. 4) and a new gateway is selected. Though, when the process is used at block444, any gateways through which transmission of the same packet was already attempted are excluded from the subset of gateways selected.

For example, the invention was illustrated by a computer programmed to operate according to a TCP/IP/ARP layered protocol. The invention is not limited for use with this protocol. Many computers are programmed to alternatively or additionally communicate according to the UDP/IP/ARP layered protocol.

UDP is an example of a protocol that is not connection oriented. For such protocols, the application typically knows whether a response is to be expected for any transmission, and the absence of a response may be a sign that the selected gateway has failed. Such applications can provide feedback to the networking stack to cause an alternate gateway to be selected, much in the same way that the TCP connection layer provides feedback in the invention. Accordingly, though processing is shown within a network stack, some or all of the processing could be performed in an application layer or in other operating system components.