Ulllted States Patent [19]
`Choquier et al.
`
`USOO5774668A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,774,668
`Jun. 30, 1998
`
`[54] SYSTEM FOR ()N-LINE SERVICE IN WHICH
`
`5,444,848
`
`8/1995 Johnson, Jr. et al. ........... .. 395/200.15
`
`GATEWAY COMPUTER USES SERVICE MAP
`
`5,463,625 10/1995 Yasrebi . . . . . . . . . . . . . . . .
`
`. . . . .. 370/85
`
`WHICH INCLUDES LOADING CONDITION
`ggglglglggNBgglgylggsggg 53A,,
`BALA CI G
`N N
`
`,
`
`,
`
`5,544,327
`5,548,724
`
`1234111? e_tt€1-t-~i~ 0 smI e a.
`
`e.
`.... ..
`8/1996 Dan et al. .... ..
`8/1996 Akizawa et a1. ..
`
`n
`395/200 64
`.. 395/20003
`
`__
`
`_
`
`_
`
`[75] IHVPIHOYSI PhlllPPe choquler, Pans, France;
`Jean-Franclos Peyroux, Bellevue;
`William
`Gl‘i?ill, Bothell, bOth Of
`Wash'
`[73] Assignee: Microsoft Corporation, Redmond,
`Wash
`
`[21] Appl. No.: 472,807
`
`[22] Filedi
`
`JllIl- 7, 1995
`
`"""""""""""""""""
`
`6
`
`' 3'95/2'
`
`01;
`395/200‘57f 395/200'48f
`'39’5 200 79' 39’5 675 36'4 2’38_ 364 2'81f
`/
`'
`’
`/
`’
`/
`’
`/
`’
`370/480
`_
`[58] Fleld 0f Search ................................... .. 395/187, 200,
`395/650> 307> 20053> 20033> 20031 20057>
`200'48> 200'79> 675; 370/85> 480; 364/238>
`281
`
`[56]
`
`477997156
`
`5’291’597
`573297619
`5,341,477
`5,347,632
`5,423,003
`
`_
`References Clted
`U_S_ PATENT DOCUMENTS
`_
`1/1989 Shavlt et al'
`glikamutml """ "
`3/1994 shzilereeiia'l
`7/1994 Page et a1. .1-.. ..................... .: 395/200
`8/1994 Pitkin etal. .......................... .. 395/200
`9/1994
`395/200.09
`6/1995 Berteau ................................. .. 395/200
`
`5,548,726
`
`8/1996 Pettus .............. ..
`
`.. 395/20009
`
`5,553,239
`.. 395/187.01
`9/1996 Heath et al.
`5,559,969
`395/307
`9/1996 Jennings
`5,650,994
`7/1997 Daley .................................... .. 370/259
`Primary Examiner—Thomas C. Lee
`_
`Assistant Examiner
`S‘ K1m_
`Attorney, Agent, or Fzrm—Leyd1g, Volt & Mayer, Ltd.
`[57]
`ABSTRACT
`_
`_
`_
`_
`_
`An 1
`t
`k 1 d
`1
`t
`d
`on- me services ne wor mc u es app 1ca 1on servers an
`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
`Spending 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
`(replicated) application server without termination of the
`service session. Various mechanisms are provided for ef?
`ciently reallocating application servers to different on-line
`Services> and for allowing additional Servers to be e?icien?y
`added to the network
`
`59 Claims, 14 Drawing Sheets
`
`I ,404
`
`"
`
`‘ OSTDATA
`I CENTER
`
`128
`
`APP
`sERvER
`
`@fmo
`
`APP
`sERvER
`
`LOCAL
`MAP
`
`APP
`sERvER
`
`AHBITER
`
`122
`
`GATEWAY
`
`72o #4 _
`@
`@
`
`126
`
`GATEWAY
`
`GATEWAY
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 1
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 1 0f 14
`
`5,774,668
`
`.209
`
`/ NNN
`
`Q2
`
`20.530
`
`m2
`
`m2 \ H
`
`225%
`
`QNHK m2
`
`
`
`
`
`><>>E<w TIA’
`
`_ _ _ _ _ _ _
`
`1/25
`
`mow
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 2
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 2 0f 14
`
`5,774,668
`
`25
`
`E?mm
`
`33.218
`
`55$;
`
`SSEIEQSV
`
`E>~mm
`
`A
`
`7
`
`
`
`hing .mw‘x
`
`n62
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 3
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 3 of 14
`
`5,774,668
`
`
`
`GEL
`
`SOEL
`
`20E¢
`
`NOILOVSNVYL
`907real
`iNSANaS||!YSANIS||YSANIS
`saa!Sas/IIVAN]|TVA!|
`
`
`IVAN
`
`YSANAS
`
`GOZL
`
`NV]
`
`CEL
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 4
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 4
`
`
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 4 0f 14
`
`5,774,668
`
`140
`LOCAL MAP
`(SERVER 1) /
`CPU LOAD
`CPU INDEX
`/- 400
`SERVICE 1 DESCRIPTION /
`- SEVICE NAME
`- STATE
`- CLIENT COUNT
`- VERSION
`
`,- 400
`
`SERVICE n DESCRIPTION
`- SEVICE NAME
`- STATE
`- CLIENT COUNT
`- VERSION
`
`140
`LOCAL MAP
`(SERVER 2) /
`
`136
`
`SERVICE MAP
`
`CPU LOAD
`CPU INDEX
`SERVICE 1 DESCRIPTION
`- SEVICE NAME
`- STATE
`- CLIENT COUNT
`- VERSION
`
`-
`SERVICE n DESCRIPTION
`-SEV|CE NAME
`- STATE
`- CLIENT COUNT
`_
`
`VERSION
`
`/_400
`
`‘ LOCAL MAP
`' FOR SERVER 1
`
`P400
`
`‘ LOCAL MAP
`FOR SERVER 2
`
`,
`
`,
`
`E LOCAL MAP
`' FOR SERVER n
`
`LOCAL MAP
`140
`(SERVER n) V
`CPU LOAD
`CPU INDEX
`SERVICEI DESCRIPTION /
`-SEV|CE NAME
`-STATE
`- CLIENT COUNT
`-VERS|ON
`
`SERVICEnDESCRIPTION K
`-SEVICE NAME
`-STATE
`- CLIENT COUNT
`- VERSION
`
`W6: 4
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 5
`
`

`

`
`
`onwaauas,oe"
`
`OZ!921AVMILV9DFol{LN
`
`
`
`
`
`
`
`dvW1V907dVWJOIANaS) (dVWNOISSISnos
`
`LNAI
`
`U.S. Patent
`
`
`
`OeSNOILYOIIdd¥
`
`
`SNOILVOMdd¥YOLVOOTpnB90E
`NNG‘LVHO“b’ePPON
`
`G2OS'55)YOLOIMIGSYWAGONBOS
`
`
`
`Jun. 30, 1998
`
`NJAV1
`
`dOHWLg
`
`
`
`YYOMLIN_jEdOHNOWoe
`
`Sheet 5 of 14
`
`5,774,668
`
`GOLS
`
`
`
`-dyvo1ddd
`
`LOECG
`
`Cot
`
`VGOL
`
`
`GY¥VOIGdd
`c'XQYVOS| SOL
`GOLLSAa
`
`LG
`
`Opes>YOMLAN‘YOMLINgis
`
`
`
`Y3AV1YSIAVIoe
`
`
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 6
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 6
`
`
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 6 of 14
`
`5,774,668
`
`OFEL
`
`GOOS
`
`OZ!YSAYSS
`
` GPOS|GAAS
`GOS
`
`YSIAV1MYOMLIN
`
`(T10'LVHO‘’b’a)
`
`a
`
`SOIAYSS
`
`SNOILVONddV
`
`GOLS
`
`
`
`duvo1dd9
`
`GEL
`
`O2S
`
`SLUG
`
`OPES
`
`POLS.
`
`ALG
`y
`
`GEL
`
`COG
`
`ZOl—"
`
`LINSINM9
`
`dVWSOIAYSSdVWNOISSSS
`
`LNJ3N9OS
`
`
`Cot|we10095YSAV)
`te
`MYOMLAIN
`GSDl
`YOLOSYIGSY
`YOLVOO)
`GHyVvodi/aJIAVI-MYOMLIN|OW
`AVMILVS
`FOLNL
`
`SOL
`
`WGOF
`
`GLGF
`
`ODL
`
`SNOILVONddV
`
`2205
`
`2G0F
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 7
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 7
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 7 0f 14
`
`5,774,668
`
`LOAD BALANCING
`BY GATEWAY
`
`RECEIVE REQUEST TO
`OPEN NEW SERVICE
`T
`ACCESS SERVICE MAP
`TO IDENTIFY SERVERS
`WITHIN SERVICE GROUP
`
`MULTIPLE
`ERVERS IN SERVIC
`GROUP
`'?
`
`506'
`
`600
`
`502
`
`604
`
`DOES SERVICE
`REQUIRE CUSTOM
`LOCQTOR
`'
`
`5,2
`\
`READ SERVICE MAP
`
`K570
`SPECIAL PROCESSING
`(e.g., USE CONF_ LCC
`SERVICE TO LOCATE
`SERVER HANDLING
`
`USE USERNAME To
`IDENTIFY MAIL
`SERVER)
`
`AND CPU INDEX FOR
`EACH SERVER WITHIN
`SERVICE GROUP
`I
`SELECT LOAD BALANCING /'574
`ALGORITHM FOR
`REQUESTED SERVICE
`*
`APPLY LOAD BALANCING
`ALGORITHM TO SELECT
`SERVER WITH "GREATEST"
`AVAILABLE CPU PROCESSING
`POWER
`(FIGS. 7 AND 8)
`
`K576’
`
`ROUTE "OPEN" REQUEST TO SERVER,
`OR RETURN ERROR CODE IF NO
`SERVER IS AVAILABLE
`
`6
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 8
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 8 0f 14
`
`5,774,668
`
`LOAD BALANCING
`(SELECT SERVER WITH HIGHEST
`AVAILABLE PROCESSING POWER)
`
`L = UID OF FIRST
`SERVER IN SERVICE GROUP
`
`I
`FREE CPUL = 100 - CPU LOADL
`
`K704
`r705
`AVAILABLE CPU/L = FREE CPUL X CPU INDEXL
`I
`7/0
`
`MODIFY L
`TO POINT TO
`NEXT SERVER
`IN SERVICE GROUP
`
`705 /
`
`SERVICE GROUP
`?
`
`/7/2
`
`SELECT SERVER
`WITH GREATEST
`AVAILABLE cPuL
`
`II
`
`RETURN
`
`W617
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 9
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 9 0f 14
`
`5,774,668
`
`LOAD BALANCING
`WITH RANDOMIZATION
`r502
`
`/L = UID OF FIRST
`SERVER IN SERVICE GROUP
`
`FREE cPuL =
`
`+
`
`II
`100 - CPU LoAoL
`
`804
`
`AVAILABLE CPUL = FREE CPUL x CPU INDEXL
`
`ASSIGN RANGE OF CONSECUTIVE INTEGERS
`(STARTING WITH 1) TO SERVER L,
`WITH RANGE PROPORTIONAL TO
`AVAILABLE CPUL
`
`570
`
`LAST
`SERVER IN
`SERVICE GROUP
`
`r572
`MODIFY L
`TO POINT TO
`NEXT SERVER IN
`SERVICE GROUP
`
`/5/4
`
`GENERATE RANDOM INTEGER R
`BETWEEN I AND M, WHERE
`M : HIGHEST ASSIGNED
`INTEGER
`
`PASS REQUEST TO SERVER
`THAT HAS R UNIOUELY
`ASSIGNED TO IT
`
`W615
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 10
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 10 0f 14
`
`5,774,668
`
`SERVICE
`REQUESTS
`
`//20
`
`SERVER
`
`|
`
`|
`
`.974
`I
`I
`l
`I
`l
`l
`/-900
`PROCESS
`thread
`thread
`
`'
`.902
`SERVICELDLL
`fthreod 905
`thread?
`
`9/04 -
`
`\ thr'eod /902
`ERVICEZDLL
`’ thread
`.905‘
`thread
`
`\ thrzecd
`
`£7619
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 11
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 11 0f 14
`
`5,774,668
`
`MPC
`
`,m/ MESSAGE LAYER
`
`2”
`
`7070/5
`
`X25
`
`F761 7U
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 12
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 12 0f 14
`
`5,774,668
`
`% 7/02
`BYTE #1; RACKET SEQUENCE NUMBER (0-127) /
`
`BYTE #2; ACKNOWLEDGEMENT NUMBER (0-127) /'‘’’0‘‘
`
`VARIABLE-LENGTH
`MESSAGE SEGMENTS
`
`(FIG. 11B)
`
`ORG-32 (4-BYTES)
`
`PACKET DELIMITER
`
`///05
`
`7720
`f‘
`
`7
`/ 7”
`
`\//00
`
`SEGMENT HEADER
`
`SEGMENT LENGTH (I BYTE-PRESENT ONLY
`IF SPECIFIED IN SEGMENT HEADER)
`
`7/72
`/
`
`/‘//74
`
`SEGMENT BODY
`
`/ 7/75
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 13
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 13 of 14
`
`5
`
`9
`
`774,668
`
`9¢1
`
`c0h
`
`(Ov=ALINOId)
`
`(09=ALINOId)
`
`NY
`
`
`
`JOVSSSW(O3dIAOLSANV9OSCIASSWVDOSdIA
`
`
`H3IAYNSS(IVIOLH444NdJOVSS3NTVH344NdSOVSSAWTVA
`
`
`
`
`HaAYaS(IVHOOLH444NdSDVSSSWLVHOH445NdJOVSSANLYHO
`
`
`HAAYSSSSNYD4444Nd
`IWHO Penge
`
`YW344NgSOVSSaW
`(SALA09)I)(SALAGOF)KY(Saado8)YY(Saag09)NY(SaLAgoF)VF
`INAW93SNLNSW93SNYLNSW9SSNLNSaW9aSNLNAW9aS
`LWHOTVWSAWy9
`
` JOHILNODINSWOSS-JOHINOD
`LaW0vd-
`
`
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 14
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 14
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 14 0f 14
`
`5,774,668
`
`TEST SERVICE GROUP LOAD
`FOR SERVICE L
`
`y
`IDENTIFY SERVERS IN
`SERVICE GROUP L
`
`/
`/ J00
`
`/_/J02
`I
`CALCULATE SERVICE GROUP LOAD
`SVGRP__ LOADL BY TAKING AVERAGE
`OF CPU LOAD VALUES OF ALL
`SERVERS WITHIN SERVICE GROUPL
`
`7.7
`f 04
`v
`CALCULATE AVERAGE SERVICE GROUP
`LOAD AVG_ SRVGRP_ LOADL
`BY TAKING AVERAGE OF SRVGRP_ LOAD;L
`OVER THE LAST N SERVICE MAPS
`
`AVG_ SRVGRP_ LOAD,; > MAX_ LOAD,L
`
`/J06’\
`‘’
`TAKE oNE sERvER
`FROM SERVICE GROUP/i
`AND ADD TO POOL
`
`UM
`‘I /
`ADD NEW sERvER
`TO SERVICE GROUP/L
`FROM POOL
`I
`
`~
`
`II
`I RETURN I
`
`F/GZ 7]
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 15
`
`

`

`1
`SYSTEM FOR ON-LINE SERVICE IN WHICH
`GATEWAY COMPUTER USES SERVICE MAP
`WHICH INCLUDES LOADING CONDITION
`OF SERVERS BROADCASTED BY
`APPLICATION SERVERS FOR LOAD
`BALANCING
`
`FIELD OF THE INVENTION
`
`The present invention relates to computer networks. More
`particularly, the present invention relates to large-scale com
`puter netWorks for providing information-related services
`and communications services to end users.
`
`10
`
`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 ef?cient 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 speci?c on-line
`services, so that ?uctuations in usage levels of speci?c
`on-line services can be ef?ciently 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.
`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
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,774,668
`
`2
`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 (“BBS”) 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 BBS
`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 X25, 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 identi?es 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
`server. The service map is updated on the order of every 30
`seconds to re?ect changes in application server loads, and to
`re?ect various changes in the system con?guration.
`Load balancing is preferably performed according to the
`speci?c dynamics of the individual services. One load
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 16
`
`

`

`3
`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
`server’s 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 ?le
`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 speci?ed) 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
`?uctuations 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.
`
`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;
`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;
`
`10
`
`15
`
`25
`
`35
`
`40
`
`45
`
`55
`
`65
`
`5,774,668
`
`4
`FIG. 4 illustrates hoW a service map may be generated
`from server-speci?c 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 How chart illustrating the steps taken by a
`GateWay microcomputer upon receiving a request from a
`user to open a service;
`FIG. 7 is a How chart illustrating a load balancing
`technique used to select an application server to handle a
`request to open a service;
`FIG. 8 is a How 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 How chart illustrating a technique for moni
`toring service group loads.
`Reference numbers in the draWings have three or more
`digits. The tWo least signi?cant digits are reference numbers
`Within the draWing, and the more signi?cant digits are the
`?gure number. For example, reference number 306 refers to
`an item ?rst 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; DYNAMIC ALLOCATION 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
`106. The Wide area netWork
`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 speci?cation of
`the Comite Consultatif Internaionale de Télégraphie et Télé
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 17
`
`

`

`5,774,668
`
`5
`phonie (CCITT)—an international standards organization in
`Geneva, Switzerland that recommends communications
`standards. The X25 standard documents the interface
`required to connect a computer to a packet-sWitched net
`Work. In addition to or in place of X25, 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
`Pentium-class (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 LAN s 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 netWork 122 preferably comprises at least
`one 100 Mbps LAN Which is based on the ISO/ANSI
`Copper Distributed Data Interface (CDDI) speci?cation.
`(The CDDI speci?cation is a variant of the Well-knoWn
`ANSI Fiber Distributed Data Interface speci?cation, but
`uses a single copper ring instead of a dual ?ber ring.) Various
`other types of LAN speci?cations may be used, such as
`IEEE token ring or sWitched ethernet. Further, various
`alternative transmission mediums may be used, including
`?ber optic lines.
`To increase LAN bandWidth, some or all of the micro
`computers of the host data center 104 may be interconnected
`by one or more additional LANs. For example, different
`LANs may be dedicated to different sets of application
`servers 120 (and to different services). Accordingly, the term
`“local area netWork” (or “LAN”), as used herein, should be
`construed to include a combination of local area netWorks,
`and should not be construed to be limited to a particular data
`transfer protocol or transmission medium.
`The host data center 104 provides a variety of
`communications-based and information-based on-line ser
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`6
`vices to end users. Typical services include, for example, a
`mail service for alloWing users to send email messages to
`one another, a bulletin board system (BBS) service for
`alloWing users to post and revieW messages on speci?c
`topics, a chat service for alloWing users to communicate in
`real time With each other on speci?c topics, an interactive
`games service for alloWing users to compete against each
`other in real time in on-line interactive games, various neWs
`services for alloWing users to access neWs and magaZine
`articles, a mediavieW service for alloWing users to vieW
`on-line multimedia titles, and a directory service for alloW
`ing users to vieW a hierarchy of services and data entities on
`the netWork. As described beloW, the server side of each
`on-line service is preferably implemented using one of the
`folloWing: (1) a single application server 120, (2) a set of
`“replicated” application servers (i.e., application servers
`Which run the same service application or applications) that
`provide access to replicated (and locally-stored) copies of
`service “content” data (i.e., data provided to end user’s of
`the service), or (3) a set of replicated application servers that
`provide access to server-speci?c (non-replicated) service
`content data.
`The host data center 104 also includes multiple Arbiter
`microcomputers 128 that monitor, record and process certain
`types of transactions to ensure consistency among replicated
`application servers. The various functions performed by the
`Arbiter microcomputers 128 are described beloW under the
`headings SERVICE GROUPS and ARBITER. The host data
`center 104 also includes one or more custom GateWay
`microcomputers 130 Which link the host data center 104 to
`one or more external service providers 132, such as a credit
`card service that validates and executes credit card transac
`tions. Each custom GateWay microcomputer 130 uses the
`communications protocol required by the external service
`provider 132 to Which the custom GateWay is linked. In
`other embodiments, the functionality of the custom Gate
`Ways 130 may be integrated into the application servers 120.
`The host data center 104 also includes a number of
`administrative servers 134. The administrative servers 134
`perform administrative functions such as accounting,
`billing, netWork management, backup, system security, per
`formance analysis, and server-to-service allocation. Because
`the description that folloWs focuses primarily on the appli
`cation servers 120 (rather than the administrative servers
`134), the term “server” Will hereinafter be used to refer to an
`application server 120 (unless indicated otherWise).
`The on-line services offered to end-users of the netWork
`100 are in the form of client-server applications programs
`(or “service applications”). Each service application
`includes a server portion (also referred to as a “server
`application”) that runs on one or more of the servers 120,
`and a client portion (also referred to as a “client
`application”) that runs on a microcomputer 102 of an end
`user.
`In the presently preferred embodiment, the client appli
`cations are in the form of Microsoft WindoWs ’95
`executables. These client applications are preferably Written
`such that, from the end user’s perspective, the various
`on-line services provided by the host data center 104 appear
`transparently as an extension to the ?le structure of the
`user’s hard disk. Server applications are preferably in the
`form of service dynamic link libraries (DLLs) that are
`executed by the application servers 120. Although the term
`“service application” Will be used herein to describe appli
`cations running on servers 120, it should be understood that
`only a server portion of the service application is actually
`running on the servers 120, and that the service application
`
`Petitioner Microsoft Corporation, Ex. 1022, p. 18
`
`

`

`5,774,668
`
`7
`also includes a client portion running on client microcom
`puters 102 (or running on other computers of the host data
`center 104 that act as clients).
`In accordance With one feature of the invention, service
`DLLs can be dynamically loaded and unloaded from the
`servers 120, thereby alloWing different services to be ef?
`ciently (and automatically) activated and deactivated on
`different servers. The preferred process by Which services
`are activated and deactivated on different servers is
`described beloW under the headings SOFTWARE I