United States Patent (19)
`Choquier et al.
`
`USOO5951694A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,951,694
`Sep. 14, 1999
`
`54 METHOD OF REDIRECTING ACLIENT
`SERVICE SESSION TO ASECOND
`APPLICATION SERVER WITHOUT
`INTERRUPTING THE SESSION BY
`FORWARDING SERVICE-SPECIFIC
`INFORMATION TO THE SECOND SERVER
`75 Inventors: Philippe Choquier, Paris, France;
`Jean-Francios Peyroux, Bellevue;
`O
`O
`William J. Griffin, Bothell, both of
`Wash.
`
`73 Assignee: Microsoft Corporation, Redmond
`s
`s
`Wash.
`
`21 Appl. No.: 08/794,350
`22 Filed:
`Feb. 3, 1997
`
`Related U.S. Application Data
`
`62 Rys of application No. 08/472.807, Jun. 7, 1995, Pat.
`o. 5,774,668.
`51) Int. Cl. ............................. G06F 11/00; G06F 15/16
`52 U.S. Cl. ................................... 714/15: 714/4; 714/10;
`709/203
`58 Field of Search ......................... 395/182.02, 200.49,
`395/200.75, 182.08, 182.13, 200.33; 707/201;
`714/4, 10, 15; 709/203, 219, 245
`
`56
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,184,200 1/1980 Wagner ................................... 364/200
`4,280,176
`7/1981 Tan ................
`... 364/200
`4,432,057 2/1984 Daniell et al.
`... 364/300
`4,493,024
`1/1985 Baxter ...........
`... 364/200
`
`5,140,689 8/1992 Kobayashi .............................. 395/575
`5,151,989 9/1992 Johnson et al. ......................... 395/600
`(List continued on next page.)
`
`OTHER PUBLICATIONS
`So... Just What is this First Class Thing Anyway? (visited
`Oct. 10, 1995) <http://orion.edmonds.wednet.edu/ESD/FC/
`AboutEC.html>.
`66
`Colton, Malcolm, “Replicated Data in a Distributed Envi
`ss
`roment," IEEE (1993).
`Coulourius et al., “Distributed Transaction,” Chapter 14 of
`Distributed Systems Concepts and Design 2nd Ed., 409–421
`(1994).
`
`(List continued on next page.)
`Primary Examiner Thomas C. Lee
`Assistant Examiner Albert Wang
`Attorney, Agent, or Firm Leydig, Voit & Mayer, Ltd.
`57
`ABSTRACT
`
`An on-line Services network includes application Servers and
`Gateway microcomputers that are interconnected by a LAN.
`The Gateway microcomputers receive Service requests
`which are transmitted over a WAN from client microcom
`puterS operated by end users. Upon receiving a request to
`open a Service, the Gateway microcomputers acceSS a
`periodically-updated Service map to locate the replicated
`application Servers that are currently running the corre
`sponding Service application, and then apply a load balanc
`ing method (using server load data contained within the
`Service map) to select an application server that has a
`relatively low processing load. A communications protocol
`between the client and Gateway microcomputerS enables
`users to acceSS multiple Services simultaneously. A hot
`redirection technique allows a user Service Session to be
`transferred from one application Server to another
`
`E. t1. Sea - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 364/200
`2 : - - 2
`aW C a
`
`1/1989 Agrawal et al. ........................
`4,800,488
`364/200
`4,858,117 8/1989 DiChiara
`4,895,136 2/1990 Beard et al...
`... 340,706
`4.914,571
`4/1990 Baratz et al. .
`... 364,200
`5,079,765
`1/1992 Nakamura .....
`370/85.13
`5,113,499 5/1992 Ankney ................................... 395/325
`
`(replicated) application server without termination of the
`
`service session. Various mechanisms are provided for effi
`ciently reallocating application Servers to different on-line
`Services, and for allowing additional Servers to be efficiently
`added to the network.
`21 Claims, 14 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`'Host DATA TT El
`CENTER
`ARBITER
`
`-104
`
`OO N
`
`GATEWAY
`
`GATEWAY
`
`SERVICE
`
`AP (SE)
`
`GATEWAY
`
`i
`
`
`
`32
`
`EXERNAL
`SERVICE
`POWDER
`
`SERVER
`
`~ic
`
`LOCA
`MAP -134
`
`SERVICEMAP
`DISPATCHER
`GLOBAL.
`REGISTRY
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 1 of 31
`
`

`

`5,951,694
`Page 2
`
`
`
`U.S. PATENT DOCUMENTS
`
`5,650,994 7/1997 Daley ...................................... 370/259
`5,666,519 9/1997 Hayden ................................... 395/500
`5,675,723 10/1997 Ekrot et al. ..
`395/182.02
`5,187,790 2/1993 Fast et al. ............................... 395/725
`5,675,796 10/1997 Hodges et al........................... 395/670
`5,247,676 9/1993 Ozur et al. .
`395/650
`5,696,895 12/1997 Hemphill ...
`... 395/182.02
`5,257,369 10/1993 Skeen et al. ...
`395/680
`5,774,668 6/1998 Choquier et al. .................. 395/200.53
`5,265,250 11/1993 Andrade et al. ........................ 395/650
`5,291,597 3/1994 Shorter et al..
`OTHER PUBLICATIONS
`5,307,490 4/1994 Davidson et al. ...................... 395/650
`Cox, John, “Sybase Server to Add Complexity User for
`5,321,841
`6/1994 East ............
`395/725
`---4----- ?
`5,329,619 7/1994 Page et al..
`Challenge with Data Replication.” Communication No. 483
`5,341,477 8/1994 Pitkin et al..
`(1993).
`5,347,632 9/1994 Filepp et al..
`Custer, Helen, “The Object Manager and Object Security,”
`5,355,497 10/1994 Cohen-Levy ............................ 395/700
`Inside Windows NT, Chapter 3, 40–43, 49-81 (1993).
`5,367,621 11/1994 Cohen et al. ..
`... 395/154
`Eckerson, Wayne, “Users Give Green Light for Replica
`5,371,852 12/1994 Attanasio .......
`395/200.75
`tion,” Network World (Jul. 19, 1993).
`5,388.255 2/1995 Pytlik et al.
`... 395/600
`Edelstein, Herb, “The Challenge of Replication, " DBMS
`5,396,626 3/1995 Nguyen ................................... 395/700
`vol. 8, No. 4, 68 (Apr. 1995).
`5,423,003 6/1995 Berteau.
`Edelstein, Herb, “Microsoft and Sybase are Adding their
`5,434,994 7/1995 Shaheen et al. ........................ 395/600
`ss
`5,444,848 8/1995 Johnson, Jr. et al..
`Unique Touches to SQI Servers, "Information Week, No.
`5,455,932 10/1995 Major et al. ............................ 7
`528, 62 (1995).
`5,463,625 10/1995 Yasirebi.
`Edelstein, Herb, “Replicating Data, " DBMS vol. 6, 59 (Jun.
`5,473,599 12/1995 Li et al. .................................. 370/219
`1993).
`5,475,819 12/1995 Miller et al..
`Gouhle, Michael, “RDBMS Server Choice Gets Tougher, ”
`5,481,720
`1/1996 Loucks et al. .......................... 395/700
`Network World, 52 (May 23, 1994).
`5,483,652
`1/1996 Sudama et al. ......................... 395/600
`Heylighen, Francis, “World-Wide Web: A Distributed
`5,490.270 2/1996 Devarakonda et al. ................ 707/201
`Hypermedia Paradigm for Global Networking, ' Proceed
`5,491,800 2/1996 Goldsmith et al..
`SE 3: E. in - - - - - - - - - - - - - - - - - - - - - r 3: ings of The SHARE Europe Spring Conference, 355-368
`5,497,463 3/1996 Stein et al......
`Sos/2000
`(1994).
`5,499.342 3/1996 Kurihara et al.
`... 395/200.12
`International Telecommunication Union, CCITTBlue Book
`5,500,929 3/1996 Dickinson ............................... 395/160
`Volume VIII Data Communication Networks Directory, 3-18
`5,513,314 4/1996 Kandasamy et al. .............. 395/182.04
`(1989).
`5,515,508 5/1996 Pettus et al..
`King, Adrian “The User Interface and the Shell, ” Inside
`5,526,491 6/1996 Wei .................................... 395/200.09
`Windows 95, Chapter 5 (1994).
`5,530,852 6/1996 Meske et al. - - - - - - - - - - - - - - - - - - - - - - - - - - - 395/600
`Pallatlo, John, “Sybase Lays Out Blue Print for Client/
`
`395/200.49
`5,544.313 8/1996 Shachanai et al.
`5,544,327 8/1996 Dan et al. ............................... 395/250
`5,548,724 8/1996 Akizawa et al..
`5,548,726 8/1996 Pettus.
`5,553,239 9/1996 Heath et al..
`5,553,242 9/1996 Russell et al. ..................... 395/200.12
`5,559,969 9/1996 Jennings.
`5,564.043 10/1996 Siefert ..................................... 395/600
`5,572,643 11/1996 Judson ...
`395/793
`5,581,753 12/1996 Terry et al.
`.
`r: 395/617
`5,592,611
`1/1997 Midgely et al.
`395/182.02
`5,596,579
`1/1997 Yasirebi ................................... 395/678
`5,596,744 1/1997 Dao ......................................... 3'
`5,608,865
`3/1997 Midgely et al. ........................ 395/18O
`5,608,903 3/1997 Prasad et al. ..
`395/610
`5,617,568 4/1997 Ault et al.l.....
`395/612
`5,617,570 4/1997 Russell et al. .
`395/684
`5,619,632 4/1997 Lamping et al. ....................... 395/141
`
`Server Networks, " PC Week, vol. 9, No. 461, 6 (1992).
`PR Newswire Association, Inc., “America On-Line Publicly
`ss
`Previews World Wide Web Browser, ” Financial News
`Section (May 9, 1995).
`Quereshi, “The Effect of Workload on the Performance and
`Availability of Voting Algorithms," IEEE (1995).
`Rexford, Jennifer, “Window Consistent Replication for
`Real-Time Applications, IEEE (1994).
`Richman, Dan, “Sybase to Enchance RDBMS,” Open Sys
`tem. Today, No. 111 (1992).
`Silberschatz, et al., Operating System Concepts, 4" Ed.,
`36.380.431.457 (1994)
`s
`66
`Terry, Douglas, “Session Guarantees for Weekly Consistent
`Replicated Data," IEEE (1994).
`Wang, Yongdong, Data Replication in a Distributed Heter
`ogenous Database Environment, IEEE (1994) abstract.
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 2 of 31
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 1 of 14
`
`5,951,694
`
`TWNHEIXE
`HECHAOHd
`BO?AHES
`
`FOI • ^ |
`
`
`
`
`
`
`
`
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 3 of 31
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 2 of 14
`
`5,951,694
`
`47/22/
`
`
`
`
`
`| | | | | | | | | | | | | |
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 4 of 31
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 3 of 14
`
`5,951,694
`
`
`
`| dno80 30 A&ES S88_
`
`
`
`
`
`(2624°- ~~
`
`*
`
`NVT
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 5 of 31
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 4 of 14
`
`5,951,694
`
`LOCAL MAP
`(SERVER 1)
`CPULOAD
`CPU INDEX
`SERVICE 1 DESCRIPTION
`- SEVICE NAME
`- STATE
`- CLENT COUNT
`- VERSION
`
`SERVICE n DESCRIPTION
`- SEVICE NAME
`- STATE
`- CLIENT COUNT
`- VERSION
`
`LOCAL MAP
`(SERVER2)
`CPULOAD
`CPU INDEX
`SERVICE DESCRIPTION
`- SEWICE NAME
`- STATE
`- CLENT COUNT
`- VERSION
`
`SERVICE in DESCRIPTION
`- SEWICE NAME
`- STATE
`- CLENT COUNT
`- VERSION
`
`LOCALMAP
`(SERVERn)
`CPULOAD
`CPUNDEX
`SERVICE 1 DESCRIPTION
`- SEWICE NAME
`- STATE
`- CLIENT COUNT
`- VERSION
`
`SERVICE n DESCRIPTION
`- SEVICE NAME
`- STATE
`- CLIENT COUNT
`- VERSION
`
`
`
`
`
`140
`
`400
`
`400
`
`f36
`
`140
`
`
`
`SERVICE MAP
`
`400
`
`400
`
`40
`
`400
`
`400
`
`LOCAL MAP
`FOR SERVER 1
`
`LOCAL MAP
`FOR SERVER 2
`
`LOCAL MAP
`FOR SERVER n
`
`A7C 4.
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 6 of 31
`
`

`

`|an
`
`-QuyVvOIddo
` YSAV)TMYOMLIN)JOHN
`
`
`(TId'LVHO“5a)
`
` GYyvVOSc’x-;YSAVTYAAV].MYOMLAIN
`tL|gon_|YOLOAYIGAYgYOLYOOT
`
`dvWaoiyas)(dvWNOISSaS
`MYOMLAN
`
`dVWW001
`
`JOINS
`
`SNOILVOMddV
`
`02S
`
`OLS
`
`WLS
`
`OPES
`
`POLS
`
`OFL
`
`YSANSS
`
`GEL
`
`IL
`
`AVMILYVD
`
`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 5 of 14
`
`5,951,694
`
`OFL
`
`GOOS
`
`GCOS
`
`GOLG
`
`WES
`
`GOLS
`
`CCL
`
`VSOLS
`
`SOL
`
`GOL
`
`BLE
`
`Nya
`
`Ovd
`
`LG
`
`COG
`
`COL
`
`INS
`
`SNOILVONMdd¥LNSMS
`906|D902L2206
`
`2008
`
`HG
`
`OG
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1007
`Page 7 of 31
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 7 of 31
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 6 of 14
`
`5,951,694
`
`OZZXJEA>JIES
`
`
`
`
`
`
`
`.
`
`(Ny:
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 8 of 31
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 7 of 14
`
`5,951,694
`
`LOAD BALANCNG
`BY GATEWAY
`
`RECEIVE RECUEST TO
`OPEN NEW SERVICE
`
`ACCESS SERVICE MAP
`TO DENTIFY SERVERS
`WITHN SERVICE GROUP
`
`
`
`MULTIPLE
`NO (1SERVERS IN SERVIC
`GROUP
`2
`
`YES
`
`
`
`a76
`
`6(77
`
`4622
`
`6O4
`
`
`
`
`
`
`
`a 72
`
`
`
`DOES SERVICE N YES
`REQUIRE CUSTOM
`OCATOB
`A.
`
`
`
`a 7%
`
`SPECIAL PROCESSING
`(e.g., USE CONF LOC
`SERVICE TO LOCATE
`SERVER HANDLNG
`CHAT CONFERENCE, OR
`USE USERNAME TO
`DENTFY MAL
`SERVER)
`
`READ SERVICE MAP
`TO OBTAN CPU LOAD
`AND CPU INDEX FOR
`EACH SERVER WITHN
`SERVICE GROUP
`
`SELECT LOAD BALANCNG
`ALGORTHM FOR
`REQUESTED SERVICE
`
`
`
`674
`
`a 7.5
`
`APPLY LOAD BALANCNG
`ALGORTHM TO SELECT
`SERVER WITH 'GREATEST"
`AVAILABLE CPU PROCESSING
`POWER
`(FIGS. 7 AND 8)
`
`
`
`
`
`
`
`
`
`ROUTE 'OPEN' REQUEST TO SERVER,
`OR RETURN ERROR CODE F NO
`SERVER IS AWALABLE
`
`- 62O
`A7C 6
`
`
`
`
`
`
`
`
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 9 of 31
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 8 of 14
`
`5,951,694
`
`
`
`
`
`LOAD BALANCNG
`(SELECT SERVER WITH HIGHEST
`AVAILABLE PROCESSING POWER)
`
`A = UD OF FIRST
`SERVER IN SERVICE GROUP
`
`FREE CPU,
`
`= 100 - CPU LOAD
`
`722
`
`724
`
`776
`AVAILABLE CPU = FREE CPU X CPU INDEX,
`
`
`
`
`
`777
`
`
`
`SERVER IN
`SERVICE GROUP
`2
`
`
`
`NO
`
`MODIFY A
`TO POINT TO
`NEXT SERVER
`IN SERVICE GROUP
`
`772
`
`SELECT SERVER
`WITH GREATEST
`AVAILABLE CPU,
`
`RETURN
`
`A 7,
`
`1
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 10 of 31
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 9 of 14
`
`5,951,694
`
`LOAD 3ALANCENG
`WITH RANDOMIZATION
`
`-502
`A = UD OF FIRST
`SERVER IN SERVICE GROUP
`
`FREE CPU = 100 - CPU LOAD
`
`AVAILABLE CPU = FREE CPU X CPU INDEX
`
`
`
`ASSIGN RANGE OF CONSECUTIVE INTEGERS
`(STARTING WITH 1) TO SERVER A,
`WITH RANGE PROPORTIONAL TO
`AVAILABLE CPU
`
`
`
`
`
`
`
`LAST
`SERVER IN
`SERVICE GROUP
`2
`
`
`
`YES
`
`
`
`MODIFY
`TO POINT TO
`NEXT SERVER IN
`SERVICE GROUP
`
`
`
`772
`
`GENERATE RANDOM INTEGER R
`BETWEEN 1 AND M, WHERE
`M = HGHEST ASSIGNED
`NTEGER
`
`
`
`-se
`PASS REO UEST TO SERVER
`THAT HAS R UNIQUELY
`ASSIGNED TO T
`
`A7C 5
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 11 of 31
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 10 of 14
`
`5,951,694
`
`
`
`727
`
`SERVICE
`RECQUESTS
`
`922
`SERVICE1'DLL
`th read>906
`thredd
`
`97.62
`
`thread -902
`SERVICE2.DLL
`thredd
`965
`thredd
`
`thread
`
`
`
`
`
`
`
`
`
`
`
`A7G 9
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 12 of 31
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 11 of 14
`
`5,951,694
`
`
`
`7OOO
`
`7677O
`
`
`
`
`
`MPC
`
`MESSAGE LAYER
`
`PACKET LAYER
`
`X25
`
`A/C 7O
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 13 of 31
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 12 of 14
`
`5,951,694
`
`BYTE #1: PACKET SEQUENCE NUMBER (O-127)
`
`BYTE #2: ACKNOWLEDGEMENT NUMBER (O-127)
`
`
`
`VARABLE-LENGTH
`MESSAGE SEGMENTS
`(FIG, 11B)
`
`CRC-32 (4-BYTES)
`
`PACKET DELMTER
`
`A7G 774
`
`Z777
`
`SEGMENT HEADER
`
`SEGMENT LENGTH (1 BYTE-PRESENT ONLY
`F SPECIFIED IN SEGMENT HEADER)
`
`
`
`
`
`77O2
`
`77O-Z
`
`77Oa
`
`7722
`
`7772
`
`7774.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SEGMENT BODY
`
`7776
`
`A7G 77A,
`
`7772
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 14 of 31
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 13 of 14
`
`5,951,694
`
`(H
`
`OAdIAOL
`
`AAYASSANVD
`
`
`H444NdSOVSSSW
`
`(08=ALINOIHd)
`
`INSW93S
`INAW9SS
`
`(SALA09)
`(SALASOb)
`
`IVA
`
`
`
`(
`
`S3LAG09)
`(SALAOF)
`
`INAWDAS
`INSW93S
`
`
`
`TOYLNOOLNSWDSS-AY
`
`
`
`TOHLNODLayMovd-1
`
`
`
`SSWVSOACIA
`
`
`
`Y344NgFOVSSAW
`
`PETITIONERS - AMERICAN/SOUTHWEST,Exhibit 1007
`Page 15 of 31
`
`
`
`YH344N8JOVSSAWTVW
`
`
`
`
`
`Y3s4NgJDVSSAWLWHO
`
`TVWOL
`
`YAAYRS
`
`LVHOOL
`
`YAAYAS
`
`
`
`
`
`H444NdJDVSSIWTVW
`
`(Ov=ALINOIHd)
`
`
`
`
`
`H344NdJDVSSSWLVHO
`
`(09=ALIUOIHd)
`
`
`
`SSNV9DOAGIA
`
`cOl
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 15 of 31
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 14 of 14
`
`5,951,694
`
`TEST SERVICE GROUP LOAD
`FOR SERVICE
`
`DENTIFY SERVERS IN
`SERVICE GROUP C.
`
`CALCULATE SERVICE GROUP LOAD
`SVGRP LOAD BY TAKING AVERAGE
`OF CPU LOAD VALUES OF ALL
`SERVERS WITH IN SERVICE GROUPA
`
`
`
`7322
`
`73672
`
`
`
`CALCULATE AVERAGE SERVICE GROUP
`LOAD AVG-SRVGRP- LOAD
`BY TAKING AVERAGE OF SRVGRP-LOAD
`OVER THE LAST N SERVICE MAPS
`
`
`
`
`
`73Oas
`
`AVG SRVGRP LOAD < MIN-LOAD
`
`AVG SRVGRP LOAD > MAX- LOAD
`
`
`
`
`
`
`
`
`
`ADD NEW SERVER
`TO SERVICE GROUP
`FROM POOL
`
`
`
`TAKE ONE SERVER
`FROM SERVICE GROUP
`AND ADD TO POOL
`
`RETURN
`
`A7C 75
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 16 of 31
`
`

`

`1
`METHOD OF REDIRECTING ACLENT
`SERVICE SESSION TO ASECOND
`APPLICATION SERVER WITHOUT
`INTERRUPTING THE SESSION BY
`FORWARDING SERVICE-SPECIFIC
`INFORMATION TO THE SECOND SERVER
`
`This application is a divisional of U.S. patent application
`Ser. No. 08/472,807, filed Jun. 7, 1995, now U.S. Pat. No.
`5,774,668.
`
`FIELD OF THE INVENTION
`The present invention relates to computer networks.
`More particularly, the present invention relates to large
`Scale computer networks for providing information-related
`Services and communications Services to end users.
`
`15
`
`BACKGROUND
`Various on-line Services networks are currently in
`existence, including CompuServe, Prodigy, and America
`On-Line. End users typically access these networks using a
`microcomputer equipped with a modem. During a logon
`Session, a user can use a variety of information-related
`Services and communications Services, including news
`Services, weather Services, bulletin board Services, email,
`and the like.
`Existing architectures for on-line Services networks Suffer
`from a number of limitations. For example, existing on-line
`Services networks do not provide an adequate means for
`allocating processing resources to user Service requests, and
`thus do not make efficient use of available processing
`resources. Additionally, many existing on-line Services net
`Works do not provide a means for updating Service appli
`cations without temporarily taking Services off-line. Further,
`existing on-line Services networks are not capable of allow
`ing a user to acceSS multiple Services at a time.
`It is an object of the invention to provide an on-line
`Services network architecture which overcomes these and
`other limitations of the prior art.
`
`SUMMARY OF THE PREFERRED
`EMBODIMENTS
`In accordance with the present invention a client-server
`architecture for an on-line Services network is provided in
`which on-line Services are distributed and replicated on
`groups of application Servers. The on-line Services are
`implemented as client-Server applications, with Server por
`tions (or "server applications') running on the application
`Servers, and with client portions (or "client applications”)
`running on client microcomputers of end users. The archi
`tecture features a high degree of Scalability, allowing the
`capacity of the network to be scaled (without degradation of
`on-line Services) as the number of end users increases over
`time. The architecture also features various mechanisms for
`dynamically balancing the processing load among the appli
`cation Servers of the System. The architecture also features
`various mechanisms for dynamically allocating processing
`resources (Such as application servers) to specific on-line
`Services, So that fluctuations in usage levels of Specific
`on-line Services can be efficiently accommodated. The archi
`tecture additionally features a transport mechanism that
`allows end users to Simultaneously acceSS multiple on-line
`Services. The architecture further permits Service applica
`tions to be updated without temporarily taking the Services
`off-line.
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,951,694
`
`2
`In a preferred embodiment, the application Servers of the
`System are interconnected by a local area network, and are
`arranged into Service groups, with each Service group cor
`responding to a particular Service. Each application Server of
`a Service group is preferably a "replicated” version of the
`other application Servers within the Service group, meaning
`that each runs the same Server application (or Server
`applications) as the others to implement a common Service.
`For example, application Servers within a bulletin board
`system (“EBBS”) service group all run a BBS server appli
`cation. Depending upon the particular Service, each appli
`cation Server of the Service group may locally Store a
`replicated copy of the Service's content. For example, all
`application servers within the BBS service group preferably
`Store identical copies of all BBS messages. A Service group
`may have as few as one application Server. Further, a given
`Server can handle multiple Services, and can thus be Simul
`taneously allocated to multiple Service groups.
`Users of a Service are assigned to individual application
`Servers on a per-Service Session basis. For example, when an
`end user initially opens the BBS service, the user's BES
`Service Session will be assigned to one of the replicated
`application Servers of the BBS Service group, and that
`application Server will normally Service the end user until
`the BBS service session is terminated.
`Multiple Gateway microcomputers are also connected to
`the local area network. Each Gateway microcomputer is
`connected to a wide area network for communicating with
`client microcomputers of end users. The wide area network
`preferably uses CCITT X.25, and may additionally or alter
`natively use other standards such as TCP/IP, Frame Relay, or
`Asynchronous Transfer Mode (ATM). The Gateway micro
`computerS serve as intermediaries between the client micro
`computers and the application Servers. When a user initially
`logs onto the network, a connection is established between
`the client microcomputer and a Gateway microcomputer,
`and the connection is maintained throughout the logon
`Session. During the logon Session, the user typically opens
`and closes multiple Services, and thus communicates with
`multiple application Servers. The Gateway microcomputer
`assigned to the logon Session maintains the various client
`Server message streams by routing Service requests (from the
`client microcomputer) to the appropriate application servers,
`and by returning application Server responses to the client
`microcomputer. In the preferred embodiment, each Gateway
`microcomputer can handle approximately 1000 Simulta
`neous logon Sessions.
`In accordance with a dynamic load balancing feature of
`the invention, when a user Sends a request to open a Service,
`the Gateway microcomputer that receives the request ini
`tially identifies the application Servers that are within the
`relevant Service group. The Gateway microcomputer then
`determines the current load of each application Server in the
`Service group, and applies a load balancing method to Select
`an application Server that is relatively lightly loaded. The
`Service request is then passed to the Selected application
`Server for processing.
`In the preferred embodiment, the Gateway microcomput
`erS identify the application Servers in the Service groupS and
`determine the loads of the application Servers by accessing
`a locally-Stored Service map. The Service map contains
`information about every application Server of the System.
`For example, for each application Server, the Service map
`indicates the names of the Server applications running on the
`application Server, the current processing load of the appli
`cation server, and the overall processing power (in the form
`of a static CPU INDEX benchmark) of the application
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 17 of 31
`
`

`

`3
`server. The service map is updated on the order of every 30
`Seconds to reflect changes in application Server loads, and to
`reflect various changes in the System configuration.
`Load balancing is preferably performed according to the
`Specific dynamics of the individual Services. One load
`balancing method uses the load and CPU INDEX values
`contained in the service map to calculate the available CPU
`processing power for each application Server in the relevant
`Service-group, and then passes the Service request to the
`application Server having the greatest available CPU pro
`cessing power. Another load balancing method Selects appli
`cation servers such that the probability of selection of a
`given application Server is proportional to that application
`servers available CPU processing power.
`In accordance with another feature of the invention, a
`transport protocol that handles client-Gateway communica
`tions over the local area network multiplexes client-Server
`message Streams to permit end users to access multiple
`Services simultaneously. Using this feature, a user can, for
`example, access one Service while downloading a large file
`from another service. Multiplexing is preferably performed
`by combining variable-length Segments of different message
`Streams within wide area network packets, wherein each
`message Stream corresponds to a different Service. To
`accommodate for differing throughput requirements of dif
`ferent Services, lengths of the variable-length Segments are
`varied on a Service-by-Service basis according to predeter
`mined (or user specified) priority levels. Different amounts
`of wide area network bandwidth are thereby allocated to
`different services.
`In accordance with another feature of the invention,
`application Servers may be dynamically allocated to Services
`(or equivalently, to Service groups) to accommodate for
`fluctuations in usage levels of different Services. To allocate
`an application Server to a particular Service, the Server
`application (or applications) that implement the Service are
`dynamically loaded (i.e., loaded without stopping the under
`lying process) on the application server. Likewise, to remove
`an application Server from a Service group, the relevant
`Server applications are dynamically unloaded. In the pre
`ferred embodiment, dynamic link libraries for every server
`application reside on the hard disks of every application
`Server, So that any Service can be activated on any applica
`tion Server at Virtually any time. Allocation of application
`Servers to Service groups can be performed Semi
`automatically by a System operator who monitorS Service
`loads from a System console, or automatically using a load
`monitoring program that compares Service loads to prede
`termined thresholds.
`In accordance with yet another feature of the invention, a
`user Service Session can be transferred from one application
`Server to another application server (which runs the same
`Service application), without termination or interruption of
`the Service Session. Application Servers can thus be taken off
`line (for maintenance, or for reallocation to another Service
`group, for example) without interfering with the end user's
`immediate use of the on-line Service.
`
`1O
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`These and other features of the invention will now be
`described with reference to the drawings of certain preferred
`embodiments, which are intended to illustrate and not to
`limit the invention, and in which:
`FIG. 1 is a high level diagram illustrating the architecture
`of an on-line Services network in accordance with one
`embodiment of the invention;
`
`60
`
`65
`
`5,951,694
`
`4
`FIG. 2 illustrates a client microcomputer concurrently
`communicating with two different application Servers in
`accordance with a multiplexing feature of the present inven
`tion;
`FIG. 3 illustrates, in example form, how different appli
`cation Servers can be assigned to different Service groups;
`FIG. 4 illustrates how a Service map may be generated
`from Server-specific local maps,
`FIG. 5A illustrates the primary software and hardware
`communications components used when a user connects to
`the network by modem;
`FIG. 5B illustrates the primary software and hardware
`communications components used when a user connects to
`the network using TCP/IP;
`FIG. 6 is a flow chart illustrating the steps taken by a
`Gateway microcomputer upon receiving a request from a
`user to open a Service;
`FIG. 7 is a flow chart illustrating a load balancing
`technique used to Select an application Server to handle a
`request to open a Service;
`FIG. 8 is a flow chart illustrating a variation of the load
`balancing technique of FIG. 7;
`FIG. 9 illustrates a preferred software implementation of
`Services on an application Server;
`FIG. 10 illustrates the two component layers of a protocol
`layer that is used for communications between client and
`Gateway microcomputers,
`FIGS. 11A and 11B illustrate a preferred packet format
`used for data communications between client microcomput
`erS and Gateway microcomputers over a wide area network;
`FIG. 12 illustrates a multiplexing technique for combin
`ing multiple client-server message Streams within packets
`transmitted over the wide area network, and
`FIG. 13 is a flow chart illustrating a technique for moni
`toring Service group loads.
`Reference numbers in the drawings have three or more
`digits. The two least significant digits are reference numbers
`within the drawing, and the more significant digits are the
`figure number. For example, reference number 306 refers to
`an item first shown in FIG. 3.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`Described herein is a distributed, client-server architec
`ture which employs replicated application Servers to provide
`Services to end users. Although the architecture is described
`in the context of an on-line Services network, it will be
`recognized that various aspects and features of the architec
`ture are applicable to other types of distributed Systems.
`For convenience, the description is broken up into the
`following ten sections: ARCHITECTURAL OVERVIEW;
`SERVICE GROUPS; SERVICE MAP; COMMUNICA
`TIONS COMPONENTS; DYNAMIC LOAD BALANC
`ING BY ROUTING OF SERVICE REQUESTS; SOFT.
`WARE IMPLEMENTATION OF SERVICES ON
`SERVERS; CLIENT-GATEWAY COMMUNICATIONS:
`ARBITER, DYNAMICALLOCATION OF SERVERS TO
`SERVICE GROUPS; and SCALABILITY.
`1. Architectural Overview
`FIG. 1 is a high level diagram illustrating the basic
`components of an on-line services network 100 in accor
`dance with one embodiment of the invention. Multiple client
`microcomputers 102 are connected to a host data center 104
`by a wide area network (WAN) 106. The wide area network
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1007
`Page 18 of 31
`
`

`

`5,951,694
`
`15
`
`25
`
`35
`
`40
`
`S
`106 includes WAN lines 108 which are provided by one or
`more telecommunications providers, and which allow end
`users (i.e., users the microcomputers 102) over a wide
`geographic area to access the host data center 104 via
`modem. The WAN lines 108 preferably include both X.25
`lines and ISDN (Integrated Service Digital Network) lines.
`The X.25 lines 108 comply with the X.25 specification of
`the Comité Consultatif Internaionale de Télégraphie et Télé
`phonie (CCITT)—an international standards organization in
`Geneva, Switzerland that recommends communications
`standards. The X.25 standard documents the interface
`required to connect a computer to a packet-Switched net
`work. In addition to or in place of X.25, the wide area
`network 106 may use other types of communications
`Standards, Such as Frame Relay, or the Transport Control
`Protocol/Internet Protocol (“TCP/IP”—a suite of protocols
`developed for use on the Internet).
`The host data center 104 comprises a plurality of appli
`cation servers (APP servers) 120 connected to a high speed
`local area network (LAN) 122 (which may include multiple
`LANs, as described below). Each application server 120 has
`a unique server ID. Also connected to the LAN 122 are
`multiple Gateway microcomputers 126 (hereinafter
`“Gateways”), which link incoming calls from end users to
`the application servers 120. In the preferred embodiment,
`the application servers 120 and the Gateways 126 are
`Pentiumclass (or better) microcomputers which are Scalable
`to at least four central processing units (CPUs), and which
`run the Microsoft Windows NT operating system available
`from Microsoft Corporation. The application servers 120
`will typically have at least 128 MB of random-access
`memory (RAM) and at least 4 GB of disk space. Processing
`power may vary from application Server to application
`Server. For example, one application Server may have four
`120 MHz microprocessors, while another application server
`may have one 90 MHz microprocessor. Each Gateway 126
`will typically have at least 64 MB of RAM and at least 2 GB
`of disk Space, and will be capable of Supporting approxi
`mately 1000 Simultaneous user connections.
`It is envisioned that the host data center 104 may advan
`tageously have on the order of one hundred Gateways 126,
`and between Several hundred to Several thousand application
`servers 120. A host data center of this type will be able to
`handle tens of thousands of Simultaneous user logon SeS
`Sions. Advantageously, the processing capacity of the host
`data center 104 can easily be increased (to Support increases
`in the number of Subscribers, for example) by connecting
`additional Gateways 126 and application servers 120 to the
`LAN 122, adding additional LANs when necessary. Further,
`additional host data centers 104 can be provided at different
`geographical locations to accommodate a wide geographic
`distribution of Subscribers. The multiple host data centers
`104 would preferably be interconnected by leased lines
`and/or by a data network (Such as the Internet), and would
`preferably use TCP/IP to communicate.
`The local area networ