(12) United States Patent
`Brendel
`
`US006182139B1
`(10) Patent No.:
`US 6,182,139 B1
`(45) Date of Patent:
`*Jan. 30, 2001
`
`(54) CLIENT-SIDE RESOURCE-BASED
`LOAD-BALANCING WITH
`DELAYED-RESOURCE-BINDING USING TCP
`STATE MIGRATION TO WWW SERVER
`FARM
`
`(75) Inventor: Juergen Brendel, Santa Clara, CA (US)
`(73) Assignee: Resonate Inc., Mountain View, CA
`(US)
`Under 35 U.S.C. 154(b), the term of this
`patent shall be extended for 0 days.
`
`(*) Notice:
`
`This patent is Subject to a terminal dis
`claimer.
`
`(21) Appl. No.: 09/103,336
`(22) Filed:
`Jun. 23, 1998
`Related U.S. Application Data
`(63) Continuation-in-part of application No. 08/691,006, filed on
`Aug. 5, 1996, now Pat. No. 5,774,660.
`(51) Int. Cl." ............................. G06F 13/38; G06F 15/17
`(52) U.S. Cl. ..................
`709/226; 709/105; 709/201
`(58) Field of Search ..................................... 709/226, 229,
`709/238, 239, 245, 250, 302,304, 219,
`203,105,104; 370/237, 390; 714/11, 13,
`5, 6, 7
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,181,200
`5,325,362
`
`1/1993 Harrison .............................. 370/85.1
`6/1994 Aziz .................................... 370/94.1
`(List continued on next page.)
`
`FOREIGN PATENT DOCUMENTS
`648038 * 4/1995 (EP) .............................. HO4L/29/06
`677943 * 10/1995 (EP) .............................. HO4L/29/06
`Primary Examiner Mark H. Rinehart
`Assistant Examiner Bunjob Jaroenchonwanit
`(74) Attorney, Agent, or Firm-Stuart T. Auvinen
`(57)
`ABSTRACT
`A client-side dispatcher resides on a client machine below
`high-level client applications and TCP/IP layers. The client
`Side dispatcher performs TCP State migration to relocate the
`client-server TCP connection to a new server by storing
`packets locally and later altering them before transmission.
`The client-side dispatcher operates in Several modes. In an
`error-recovery mode, when a Server fails, error packets from
`the Server are intercepted by the client-Side dispatcher.
`Stored connection packet's destination addresses are
`changed to an address of a relocated Server. The altered
`packets then establish a connection with the relocated Server.
`Source addresses of packets from the Server are changed to
`that of the original Server that crashed So that the client
`application is not aware of the error. In a delayed URL-based
`dispatch mode, the client-side dispatcher intercepts connec
`tion packets before they are Sent over the network. Reply
`packets are faked by the client-Side dispatcher to appear to
`be from a server and then sent to up to the client TCP/IP
`layers. The client's TCP then sends URL packet identifying
`the resource requested. The client-side dispatcher decodes
`the URL and picks a server and sends the packet to the
`Server. Reply packets from the Server are intercepted, and
`data packets altered to have the Source address of the faked
`server. Multicast of the initial packet to multiple servers is
`used for empirical load-balancing by the client. The first
`Server to respond is chosen while the others are reset. Thus
`the client-side dispatcher picks the fastest of Several Servers.
`20 Claims, 9 Drawing Sheets
`
`
`
`CLIENT-SIDE
`DISPATCHER 20
`
`EXHIBIT 1010
`Guest-Tek v. Nomadix, IPR2018-00376
`
`

`

`US 6,182,139 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`2/1998 Largarde et al. .................... 395/610
`5,721,908
`5,751,971 * 5/1998 Dobbins et al.
`... 709/238
`5,774,660 * 6/1998 Brendel et al. .
`709/201
`12/1995 Li et al. ................................. 370/16
`5,473,599
`56.6 : A: s et t
`39. 5,774,668
`6/1998 Choquier et al.
`709/223
`2 - - -2
`f
`an et al. .........................
`f
`5,826,032
`10/1998 Finn et al. ........................... 709/236
`5,621,734
`4/1997 Mann et al. ...
`370/94.1
`5,862,335 * 1/1999 Welch, Jr. et al. .
`709/224
`5,636,371 * 6/1997 Yu et al. .....
`... 395/500
`5,862,362 * 1/1999 Somasegar et al.
`... 395/500
`5,673,322
`9/1997 Pepe et al. ..
`... 380/49
`5,892,924 * 4/1999 Lyon et al.......
`... 709/245
`5,701,451
`12/1997 Rogers et al. .
`... 395/600
`5,894.554 * 4/1999 Lowery et al. .
`... 709/203
`5,926,482 * 7/1999 Christie et all
`370/469
`5,706,507
`1/1998 Schloss ..........
`... 395/615
`2 - 1 - 2
`IISLle el all. . . . . . . . . . . . . . . . . . . . . . .
`5,710,918
`1/1998 Lagarde et al.
`... 395/610
`5,715,453
`2/1998 Stewart ................................ 395/615
`5,717.860
`2/1998 Graber et al. ................... 395/200.16
`
`
`
`* cited by examiner
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 1 of 9
`
`US 6,182,139 B1
`
`CLENT
`"BROWSER"
`
`70
`
`
`
`SERVER
`
`56
`
`51
`
`52
`
`55
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 2 of 9
`
`US 6,182,139 B1
`
`CLIENT
`"BROWSER"
`
`
`
`10
`
`
`
`
`
`
`
`NO RESPONSE
`TIMEOUT
`
`T1/T3
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 3 of 9
`
`US 6,182,139 B1
`
`CLIENT
`
`10
`
`SERVER
`
`IP 18
`
`
`
`CLIENT-SIDE
`DISPATCHER 20
`
`
`
`DYNLINK 22
`
`3 O
`
`FIG.3
`
`CLIENT-SIDE DISPATCHER
`
`
`
`SESSION
`TABLE 32
`
`
`
`TCP 38
`STATE
`MACHINE
`
`
`
`LOCAL 40
`PACKET
`STORAGE
`
`
`
`FIG.4
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 4 of 9
`
`
`\dO0TSYOL:dlONSdiLS3dYAHOLVdSId}SONVHOWOOL
`SAONVHOSAIS-LNANMO}
`
`
`
`
`eeeDKSOASZ.tOt~™”W
`
`Nid(O)MOV+NAS(ONAS
`
`
`
`
`
`
`erereteeseeees: (o)HSNd:Tz:dol2:tddWLNAITO}TOSMIGSYSOSNS
`
`WoW
`
`
`
`
`
`(O)HSNd(O)NAS(O)NAS
`
`oe
`
`NisNid+NAS
`
`YAS90734YYAS90714uYAS0073yYASSIYOgretecsesescees;: o%
`(0)MOVsy:Td}
`
`
`
`
`
`US 6,182,139 B1
`
`>.
`
`Gols
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 5 of 9
`
`US 6,182,139 B1
`
`o€
`
` S0NaNDSDROOLOIssaMSHOLVdSIC}3SONVHO
`4acusSONVHDACIS-LNAI9}(0)NAS
`
`
`
`
`YASOOTSY=NAS.ywouda|og(ONO2¢C44q}dH(O)4OVvivaDOTSYASSIOBASSIOgeveseseseessees
`dH+NASLeceeeenewsees:+NAS
`(o)uSn¢(O)NAS{ SHSaWNNYASYAS0¢(O)NAS(O)HSNd
`
`
`
`\
`dH+NAS
`
`Viva(O)MOV
`
`iddWLNAIO}LOSHIGAYMOMSVIVGTeens°
`
`(O)HSNdtT; di/dOL8}
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jan. 30, 2001
`Jan. 30, 2001
`
`Sheet 6 of 9
`Sheet 6 of 9
`
`
`
`US 6,182,139 B1
`US 6,182,139 B1
`
`o¢€
`
`
`
`gresceetseeecees;>te:(viva)(o)OWa;1d}(o)HSNd(Via)
`(OHSNd+NAS
`
`+MOV+Y4OV(0)NAS
`
`sqis-inanobecceceseesNGONWHOLYSONVHOoccccccccssscssecsesessecesssseseseseessecteeceneses
`
`
`YSHOLVdsia:d|1S3ddlONSBTUNGvVaYAWV4NSD
`
`
`YASYASD07SY0¢:90144OLOMWOOLOLNOISSVSlyddol
`SAS90734YASD0TSHYASDOT3Y
`
`(LWHSNd(O)HSNd
`
`
`
`(LHSNd(O)HSNd*NASiz: di/dOl8}
`YAS
`
`
`(O)HSNd(O)MOV
`
`(viva)(O)NAS
`
`
`+OVNoceceeseccsceee
`
`tddWLNAITO}HOLVdSIGGSSVE-THNINSIIDPPBEESSESS°
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 7 of 9
`
`US 6,182,139 B1
`
`(viva)
`
`
`
`+HOV(0)MOV+NAS
`
`
`
`(O)HSNd(O)NAS
`
`:SIOOL
`
`dlONSYSHOLVdSid
`
`(O)HSNd
`
`isumocecccccccsscccccccesarsgeenssceasssenssscenassceassccenssecenssseassecnsasesserscensstenssceeeennnnane
`
`
`
`
`
`ZSOAS
`
`auASTe
`
`(VLVQ):(O)HSNd¢CC4q}+OVLewcececneccces-
`.
`
`YYAS
`
`O0)NAS
`
`
`
`
`
`
`
`
`TSVOLLINiddvINAIT9|(O)HSNdpurennestsrereees:: di/dOl8:
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 8 of 9
`
`US 6,182,139 B1
`
`
`
`
`
`
`
`
`L?JOdTITO
`d?TITO
`
`69
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 9 of 9
`
`US 6,182,139 B1
`
`
`
`SDNSOLTO
`SOWONI
`
`El LVLS
`d'O L
`
`E||W.LS
`
`d'OL
`
`

`

`1
`CLIENTSIDE RESOURCE-BASED
`LOAD-BALANCING WITH
`DELAYED-RESOURCE-BINDING USING TCP
`STATE MIGRATION TO WWW SERVER
`FARM
`
`RELATED APPLICATION
`This application is a continuation-in-part of the
`co-pending parent application for “A World-Wide-Web
`Server with Delayed Resource-Binding for Resource-Based
`Load Balancing on a Distributed-Resource Multi-Node
`Network”, U.S. Ser. No. 08/691,006, filed Aug. 5, 1996, now
`U.S. Pat. No. 5,774,660.
`FIELD OF THE INVENTION
`This invention relates to network Servers, and more par
`ticularly to URL-based Server-assignment on the client-Side.
`BACKGROUND OF THE INVENTION
`Many Internet users can testify to the utter frustration
`when a “SERVER NOT RESPONDING” error message is
`displayed on their browser while trying to connect to a web
`Site. Users often blame the company that administers the
`unavailable web site, despite large investments in replicated
`Servers. Internet technologies are increasingly used for
`mission-critical Intranet applications that require high levels
`of reliability. An intelligently-designed web-site architecture
`with better fault-tolerance is needed.
`The parent application described a server farm that uses a
`single, virtual IP address for all server machines. The client
`first connects to a load-balancer at the Server farm that
`receives all incoming packets to the Virtual IP address. The
`load-balancer makes the initial connection with the client,
`Saving the packets used to make the connection. Once the
`connection is made and acknowledged, the client Sends the
`data request in a packet that contains a Universal Resource
`Locator, or URL.
`The load-balancer extracts the URL from the packet. The
`URL specifies a file or service at the web-server farm. The
`load-balancer then Selects only those Servers that have the
`resource requested in the URL. Load-balancing is then
`performed among these Servers.
`Since load-balancing waits until the URL is received,
`load-balancing depends on the resource requested, not
`merely on the load of each server. The server farm can be
`heterogeneous-the entire content of the web site does not
`have to be mirrored to each server's hard disk. Some files
`and resources may be located on a single node or a few
`nodes. Other web sites resources may include dedicated
`Servers with Specific resources Such as databases or built-in
`application-programming interfaces (API's) to interface
`with user-defined programs, or Software licenses to run
`particular programs on particular Servers. Other Servers may
`support the SMTP or POP3 post-office-protocols for e-mail,
`the NNTP protocol for newsgroups, etc. These specialized
`resources can reside on just a few of the Servers.
`TCP State Migration
`The connection is transferred from the load-balancer to
`the assigned Server once the URL is extracted. In this
`process, called TCP State migration, the Stored packets from
`the client are replayed by the load-balancer to the assigned
`Server. The acknowledgement packets from the assigned
`Server are captured by the load-balancer and deleted So that
`the client is unaware that the connection has been transferred
`from the load-balancer to the assigned Server. Future packets
`from the client are first routed to the load-balancer, and then
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,182,139 B1
`
`2
`passed through to the assigned Server. The assigned Server
`uses the virtual IP address instead of its own IP address as
`the Source address for packets returned to the client.
`TCP state migration is described in much more detail in
`the parent, U.S. Pat. No. 5,774,660, hereby incorporated by
`reference.
`Fault-Tolerant Web Site-FIG. 1
`The parent application described a fault-tolerant web farm
`using a back-up load balancer. FIG. 1 is a diagram of a
`fault-tolerant web site with a back-up load balancer and dual
`Internet connections. Browser client 10 Sends requests
`through Internet 66 with a virtual IP address for the whole
`web site. Incoming packets with the virtual IP address are
`routed to load balancer 70 over local LAN 144. Local LAN
`144 may contain routers, Switches, and hubs (not shown)
`when Servers are located on Separate network nodes. Most
`large Server farms have very complex interconnections
`within the local LAN network. Local LAN 144 connects to
`Internet 66 through Internet connection 142 which directly
`connects to Internet connection router 140, and through
`Internet connection 148, which is connected to Internet
`connection router 146.
`Connections 142, 148 provide connection to Internet 66.
`A primary load balancer 70 is used to direct and load balance
`connections across servers 51, 52, 55, 56. A backup load
`balancer 70' is also provided to take over operation should
`primary load balancer 70 fail. These load balancers are
`located on Separate Servers to lessen the chance that both fail
`at the same time. Backup load balancer 70' closely monitors
`primary load balancer 70 to detect a failure.
`It is Somewhat undesirable to have a back-up load bal
`ancer. If the primary and back-up load-balancers crash or
`otherwise becomes unavailable, client packets are no longer
`forwarded to their Servers, causing the clients to hang. A
`technique to avoid this client hang caused by a load-balancer
`crash is desired.
`Incoming Packets Through Load-Balancer
`FIG. 1 shows that incoming packets from client 10 are all
`routed through load-balancer 70, since a virtual IP address is
`used as the destination address. Load-balancer 70 changes
`the address of these incoming packets to direct them to the
`assigned server, such as server 52. Server 52 then sends the
`data back to client 10, using the virtual IP address as the
`SOCC.
`Although Server 52 sends outgoing packets directly to
`client 10, the incoming packets Still all go through load
`balancer 70. This still creates Somewhat of a network
`bottleneck, although certainly not as Severe as the prior art
`Since only the Smaller incoming packets are routed through
`load-balancer 70. It is desirable to remove this bottleneck.
`FIG. 2 shows a client attempting to connect to a failed
`Server. Similar reference numbers are used as described for
`FIG. 1. Client 10 attempts to open a connection to load
`balancer 70, which is migrated over to server 52. Packets
`from client 10 are not responded to by server 52 since server
`52 has crashed. Client 10 receives no reply from server 52,
`So client 10 eventually displays an error message to the user
`such as “Server Not Responding”. Otherwise, the client
`times out while waiting for a response, and displays the error
`message “Server Down or Unreachable', or “Connection
`Timed Out’.
`Another common error is that the client uses a Stale
`reference-a URL to a web page that no longer exists or has
`been relocated. It is desirable to have URL automatically
`translated to the relocated web page to avoid this error.
`
`

`

`3
`It is desired to reduce the frequency of “SERVER NOT
`RESPONDING” and “SERVER TIMED OUT” messages
`that Internet users often receive. A more efficient and fault
`tolerant web-site architecture that avoids the data bottleneck
`and Single point of failure at the load-balancer at the web site
`is desired. It is desired for the client to perform load
`balancing or Server assignment and for the TCP connection
`to be migrated from the client to the assigned Server.
`Client-side Server-assignment is desirable.
`WAN load balancing is also desirable. To minimize client
`latency the client should be served by the best responding
`Server. Responding is a function of both Server load and
`network latency. Minimizing latency is desirable since
`minimal-latency paths tend to go around Internet
`bottlenecks, because Server routes though bottlenecks are
`slower. This improves the overall performance of the Inter
`net and/or company WAN links.
`SUMMARY OF THE INVENTION
`A client-side dispatcher migrates a connection for a
`high-level client application from an original Server to a
`relocated Server. The client-side dispatcher has a Session
`table for Storing an original Server address of the original
`Server and a relocated Server address of the relocated Server.
`An input receives first packets from the high-level client
`application. The first packets have the original Server
`address as a destination address. An output outputs to a
`network Second packets. The Second packets have the relo
`cated Server address as the destination address.
`A local packet Storage is for Storing the first packets. An
`address translator converts the destination address of the first
`packets from the original Server address to the relocated
`Server address to generate the Second packets. A packet
`replayer sends the Second packets to the output.
`A first State machine tracks a Sequence of the first packets
`from the high-level client application. A Second State
`machine tracks a Sequence of the Second packets to the
`network. A checksum generator re-generates a checksum for
`the Second packets containing the relocated Server address.
`A sequence-number generator adjusts a Sequence number
`of incoming packets from the relocated Server to match
`Sequence numbers from the original Server. It also adjusts an
`acknowledgement Sequence number of outgoing packets to
`the relocated Server to match Sequence numbers for the
`relocated Server. Thus packets to the original Server are
`altered for transmission to the relocated Server.
`In further aspects the input is connected to an Internet
`Protocol IP layer. The IP layer is connected to a transfer
`control-protocol TCP layer that is connected to the high
`level client application. The output is connected to a data
`link layer that is connected to the network.
`In Still further aspects the Session table has a plurality of
`entries. Each entry is Selected by a first indeX and by a
`Second index. The first indeX has the original Server address
`while the second index has the relocated server address. The
`first indeX is extracted from outgoing first packets while the
`Second indeX is extracted from incoming packets from the
`relocated Server.
`In further aspects the Sequence numbers of incoming
`packets from the relocated Server are adjusted by Subtracting
`a delta Value while the acknowledgement Sequence numbers
`for Outgoing packets to the relocated Server are adjusted by
`adding the delta Value. The delta Value is generated by
`Subtracting a Sequence number from a first packet received
`from the relocated Server from a Sequence number from a
`first packet received from the original Server.
`
`4
`In other aspects an error detector detects an error from the
`original Server. The error detector Sends a reset packet to the
`original Server to close a connection. The error detector
`activates the address translator to translate the first packets
`Stored in the local packet Storage into the Second packets.
`The packet replayer Sends the Second packets to the relo
`cated Server to make a new connection with the relocated
`Server instead of with the original Server. Thus the connec
`tion is migrated from the original Server to the relocated
`Server when an error occurs. The error detector detects the
`error when the original Server does not respond or when
`incoming data indicates an error.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a diagram of a fault-tolerant web site with a
`back-up load balancer and dual Internet connections.
`FIG. 2 shows a client stranded on a failed server.
`FIG.3 shows a client-side dispatcher in the client machine
`that assigns a Server to the client.
`FIG. 4 is a diagram of a client-side dispatcher module.
`FIG. 5 shows an initial error packet intercepted by the
`client-side dispatcher and the connection migrated to a
`relocated Server.
`FIG. 6 illustrates client-side TCP state migration to a
`relocated Server when a connection was made to an original
`server that later fails.
`FIG. 7 highlights delayed URL-based dispatch from the
`client-side dispatcher to a server.
`FIG. 8 highlights multicast from the client-side dispatcher
`to multiple Servers to find the fastest-responding Server to
`handle the request.
`FIG. 9 shows an index into the session table for outgoing
`packets and another indeX into the Session table for incom
`ing packets.
`FIG. 10 shows the contents of the session table in the
`client-side dispatcher.
`DETAILED DESCRIPTION
`The present invention relates to an improvement in Inter
`net request dispatching from clients to Servers. The follow
`ing description is presented to enable one of ordinary skill in
`the art to make and use the invention as provided in the
`context of a particular application and its requirements.
`Various modifications to the preferred embodiment will be
`apparent to those with skill in the art, and the general
`principles defined herein may be applied to other embodi
`ments. Therefore, the present invention is not intended to be
`limited to the particular embodiments shown and described,
`but is to be accorded the widest Scope consistent with the
`principles and novel features herein disclosed.
`The inventor has realized that the TCP state migration
`method described in the parent application can be used not
`just within the web-site farm, but can extend back to the
`client. The connection is transferred or “hops', not just
`within the server farm, but across the Internet from server to
`server, controlled by the client. While the parent describes
`TCP migration of the connection from the load balancer to
`the assigned Server, the inventor has realized that the client
`can also perform TCP migration.
`Client-Side Load Balancer Intercepts Connection Packets
`The functions of the load balancer can be moved below
`the client's network Stack. Then the connection can be
`initially made within the client machine, with all
`connection-establishment packets intercepted without being
`
`US 6,182,139 B1
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`US 6,182,139 B1
`
`S
`Sent out over the network. A load-balancer module in the
`client machine fakes a connection with the standard TCP/IP
`Stack that is used by the higher-level client application
`(browser). Once the browser's stack makes the faked
`connection, the browser sends out the URL with the
`requested resource. The client load-balancer can then extract
`the URL and make a server assignment. The client load
`balancer then replays the connection-establishment packets
`to the assigned Server by transmitting them over the Internet.
`The client-side load balancer resides in the client
`machine's network Stack-invisible to the client applica
`tions. It appears to the client application that a connection is
`made with a remote server. Once the URL is sent from the
`client application, the client-side load-balancer assigns a
`remote Server and migrates the connection over the Internet
`to the remote Server. The client application or browser is not
`aware that the connection was migrated from the local
`machine to a remote node. Thus client-side load balancing is
`transparent to high-level user applications.
`The client-side load balancer can operate in other modes.
`For example, a normal connection with a remote Server can
`be made. If a Server-error message is received, the client
`Side load-balancer intercepts the error messages, hiding
`them from the client user application. A new connection to
`a replacement Server is made by the client-Side load
`balancer by replaying the connection packets. Once the new
`connection is made, the client can continue to make
`requests, unaware that the connection has been transferred to
`another server. Thus server errors are hidden from the user.
`Of course, the client-Side load balancer cannot perform
`traditional load balancing without knowledge of the loads of
`each Server at the Server farm, or knowledge of requests
`from other clients. Thus the inventor prefers the term
`“client-side dispatcher' Since client requests are dispatched
`to various Servers.
`Load-Balancing By MultiCast of Connection Packets
`A simple type of load-balancing is possible from the client
`Side. Rather than just make one connection with one server,
`the client-side dispatcher sends out many connection packets
`to different servers. The server that responds first is likely to
`be the least loaded, or the closest server to the client on the
`network. The connection is acknowledged with this first
`responding Server while connections to the slower Servers
`are cancelled by Sending them reset packets.
`While the load-balancing capabilities of the client-side
`dispatcher are perhaps less powerful than for the Server-side
`load balancer, error handling is better performed on the
`client Side. Thus the client-side dispatcher has error
`handling capabilities that are Superior to those of the Server
`farm's load balancer. The usefulness of the client-side
`dispatcher thus extends beyond traditional load-balancing.
`Client-Side Dispatcher In Client's Network Stack-FIG.
`
`3
`
`6
`the addresses and an IP checksum is generated and
`prepended. The TCP packet with the user-application data is
`contained within the IP packet.
`Several operating systems (Windows NT, Solaris, AIX,
`HPUX, and others) allow for third-party software modules
`to be placed within the network Stack. The exact location
`within the Stack can vary, but the modules can intercept and
`alter network packets without being visible to high-level
`user applications 14. In FIG. 3, client-side dispatcher 20 is
`such a third-party software module that is placed below IP
`layer 18. Client-side dispatcher 20 intercepts IP packets
`from IP layer 18 before they are sent to data-link layer
`(DLL) 22. DLL 22 contains the low-level network-card
`Software drivers, Such as an Ethernet driver. DLL 22 writes
`and reads registers on a network card to Send packets over
`the physical media of network 30.
`ASSigned Server 52 also connects to network 30 using
`data-link layer DLL 23. Packets are passed up the server's
`network stack to IP layer 28 and TCP layer 27 before the
`data is sent to Server application 24. Server application 24
`responds to the high-level request from high-level client
`application 14 by fetching the desired data and transmitting
`it back over network 30 to client 10.
`In this mode, client-side dispatcher 20 intercepts IP pack
`ets and changes the virtual IP address of the server farm to
`the physical IP address of assigned server 52. Since the
`physical IP address is used for outgoing packets, these
`packets are Sent directly to assigned Server 52. These packets
`are not sent first to the server-side load balancer (70 of FIG.
`1). Thus load-balancing functions are shifted to the client
`machine using client-side dispatcher 20.
`Client-Side Dispatcher-FIG. 4
`FIG. 4 is a diagram of a client-side dispatcher module.
`Client-side dispatcher 20 fits in the client machine’s network
`stack as shown for FIG. 3. Session table 32 contains entries
`for TCP Sessions with remote clients, including Sessions
`migrated to a another Server, and Sessions that have not yet
`been migrated to the remote server. Session table 20 is
`described in more detail in FIGS. 9-10.
`Address translation table 32 contains IP addresses and
`TCP ports of relocated servers that are linked to IP addresses
`and ports of requested Servers. Relocated Servers are the
`client's TCP connection endpoints that have been moved to
`a new Server proceSS or machine.
`Address translation table 34 converts the IP address and
`port of a requested server to an IP address and TCP port of
`a relocated Server. This translation is then Stored in Session
`table 32 for currently-active Sessions. Address translation
`table 34 contains translations for active Sessions, and trans
`lations for other addresses not currently active in a Session.
`TCP state machine 38 keeps track of the TCP state as
`Synchronization SYN, acknowledgement ACK, data, and
`reset RST packets are exchanged. Since multiple client
`applications can open multiple Sessions with different
`Servers, TCP States for each active Session are Stored in
`session table 32.
`Rather than Simply pass each packet through, client-side
`dispatcher 20 may store packets in local packet Storage 40.
`Both incoming and outgoing packets may be Stored. Packet
`replayer 42 re-transmits packets from Storage 40 to relocated
`Servers as connections are transferred. Incoming error pack
`ets may be intercepted by client-side dispatcher 20 and
`Stored in Storage 40 rather than Sent up to the client appli
`cation while the connection is being migrated from a failed
`Server. Outgoing packets for establishing a connection can
`be stored rather than sent out over the network until the first
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`FIG.3 shows a client-side dispatcher in the client machine
`that assigns a Server to the client. Client 10 includes one or
`more high-level user applications 14. High-level user appli
`cations 14 send information over network 30 by sending
`information down a network stack. TCP layer 16 receives
`network requests from high-level user applications 14 and
`forms TCP packets. TCP headers, containing Sequence and
`acknowledgement numbers, ports for the Source (client
`application) and destination (server application) and a TCP
`checksum are generated and prepended to the packet.
`IP layer 18 receives the TCP packets from TCP layer 16
`and generates Internet Protocol (IP) addresses for the client
`machine and the Server machine. An IP header, containing
`
`60
`
`65
`
`

`

`US 6,182,139 B1
`
`15
`
`25
`
`7
`data-request packet is received, So the client-side dispatcher
`20 can decode the URL request before deciding which server
`to assign the request to.
`Initial-Effor/Timeout Redirect-FIG. 5
`FIG. 5 shows an initial error packet intercepted by the
`client-side dispatcher and the connection migrated to a
`relocated Server. The client-side dispatcher can operate in
`Several modes. An error-recovery mode is described first.
`The error-recover mode allows packets to flow through
`freely from the high-level client application and TCP/IP
`layers 21 to the data-link layer DLL 22 and out over network
`30 to a server. However, when an error packet is received
`from a server, client-side dispatcher 20 prevents the error
`packet from reaching the client application. Instead, a new
`connection to another Server is opened using TCP State
`migration. The relocated Server then responds to the client
`requests. Packets are altered by client-side dispatcher 20 to
`look like packets from the original Server So that the high
`level client application is not aware of the error or that the
`Server connection has been relocated to another Server.
`When the high-level client application desires to open a
`new connection with a remote server, it causes the TCP layer
`to generate a SYN packet that is sent down the TCP/IP stack
`to network 30. Before reaching DLL 22, the SYN packet is
`intercepted by client-side dispatcher 20. A Session entry in
`the Session table is created for the new connection, but the
`packet is not altered and is passed down to DLL 22.
`The remote server is the original server identified by the
`destination IP address and TCP port from client application
`and TCP/IP layers 21. When this original server operates
`normally, it responds with a SYN+ACK packet to the client.
`When client-side dispatcher 20 sees the SYN+ACK packet,
`it may delete the Session entry and allow the Session to
`proceed normally without altering any packets.
`However, when the Server proceSS is not running, the
`Server machine may respond with an error packet Such as a
`reset RST packet. This RST packet is intercepted by client
`side dispatcher 20 after being passed up by DLL 22. Rather
`than Send this RST packet up to client application and
`TCP/IP layers 21, client-side dispatcher 20 intercepts the
`RST packet and performs TCP state migration to another
`Server. A timeout could also occur rather than a RST packet
`being received. The timeout could then initiate State migra
`tion rather than the RST packet.
`The SYN packet is retrieved from the local packet storage
`in client-side dispatcher 20, and the destination address is
`translated from the original server's address to an IP address
`of another Server, the relocated Server. The address is trans
`lated by looking up the original server's IP address and TCP
`50
`port in the address translation table to find the IP address and
`TCP port of the relocated connection to the server process.
`The TCP and IP checksums are recalculated before the
`altered SYN packet is sent out over network 30 to the
`relocated Server.
`If the relocated Server is also down, and either times out
`or replies with a RST packet, the relocation process can be
`repeated. However, when the relocated Server responds with
`a SYN+ACK packet, the connection can be migrated. The
`Source address of the relocated Server is changed to the
`original Server's address by client-side dispatcher 20, and
`the checksums recalculated. The altered SYN+ACK packet
`is passed up to the client TCP stack. The client applications
`TCP stack then sends its request in a TCP data packet. The
`request packet is intercepted by the client-side dispatcher,
`and it destination address changed from the original Server
`to the relocated Server. Checksums are recalculated and the
`
`8
`altered request packet is sent over network 30 to the relo
`cated Server. The relocated Server responds with one or more
`data packets that are intercepted by the client-Side dis
`patcher. The Source addresses of these data packets are
`changed to the original Server's address before being passed
`up to the client application.
`When the client has received all the desired data, it closes
`the connecti