United States Patent
`Brendel et al.
`
`19
`
`54 WORLD-WIDE-WEB SERVER WITH
`DELAYED RESOURCE-BINDING FOR
`RESOURCE-BASED LOAD BALANCING ON
`A DISTRIBUTED RESOURCE MULTI-NODE
`NETWORK
`
`75 Inventors: Juergen Brendel, Redwood City;
`Charles J. Kring, Sunnyvale; Zaide
`Liu, Santa Clara; Christopher C.
`Marino, Mountain View, all of Calif.
`
`73 Assignee: Resonate, Inc., Mountain View, Calif.
`
`Appl. No.: 691,006
`21
`22 Filed:
`Aug. 5, 1996
`51
`Int. Cl. ............................. G06F 13/00; G06F 17/30
`52 U.S. Cl. ................................ 395/200.31; 395/200.32;
`395/200.33; 395/200.36; 395/200.49; 395/200.56;
`395/200.59; 395/200.66; 395/200.69; 395/670;
`395/674; 395/675
`58 Field of Search ............................ 395/2003-200.33,
`395/200.36, 200.47-200.5, 200.54–200.6,
`200.66, 200.69, 182.02, 182.08, 670-675
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,307,347 4/1994 Duault et al. ........................... 370/439
`5,341,499 8/1994 Doragh .................................... 395/681
`5,343,477 8/1994 Yamada .......
`... 395/182.02
`5,355.453 10/1994 Row et al. ..
`... 395/200.49
`5,355,472 10/1994 Lewis ...................................... 707/101
`5,400,335 3/1995 Yamada .......
`... 370/524
`5,404,534 4/1995 Foss et al. .............................. 395/683
`5,426,427 6/1995 Chinnock et al. ................. 395/200.69
`5,442,749 8/1995 Northcutt et al. ..
`... 395/200.49
`5,442,771 8/1995 Filepp et al.....
`395/200.49
`5,452,447 9/1995 Nelson et al. .......................... 707/205
`5,455,932 10/1995 Major et al. ............................ 211/152
`5,455,948 10/1995 Poole et al. ............................. 707/102
`5,495.426 2/1996 Waclawsky et al.
`395/200.56
`5,539,883 7/1996 Allon et al. ............................. 395/675
`5,603,029 2/1997 Aman et al. ............................ 395/675
`5,612,897 3/1997 Rege ...........
`395/200.49
`
`USOO577466OA
`Patent Number:
`11
`(45) Date of Patent:
`
`5,774,660
`Jun. 30, 1998
`
`OTHER PUBLICATIONS
`
`Dias et al., “A Scalable and Highly Available Web Server',
`Digest of Papers, Compcon 1996, Technologies for the
`Information Superhighway, Forty-First IEEE Computer
`Society International Conference (Cat. No. 96CB35911), pp.
`85-92, Feb. 1996.
`Attanasio & Smith, “A Virtual Multiprocessor Implemented
`by an Encapsulated Cluster of Loosly Coupled Computers”,
`IBM Research Report RC18442, Apr. 1992.
`(List continued on next page.)
`
`Primary Examiner Parshotam S. Lall
`ASSistant Examiner Bharat Barot
`Attorney, Agent, or Firm-Stuart T. Auvinen
`57
`ABSTRACT
`A multi-node Server transmits world-wide-web pages to
`network-based browser clients. A load balancer receives all
`requests from clients because they use a virtual address for
`the entire Site. The load balancer makes a connection with
`the client and waits for the URL from the client. The URL
`Specifies the requested resource. The load balancer waits to
`perform load balancing until after the location of the
`requested resource is known. The connection and URL
`request are passed from the load balancer to a Second node
`having the requested resource. The load balancer re-playS
`the initial connection packet Sequence to the Second node,
`but modifies the address to that for the second node. The
`network Software is modified to generate the physical net
`work address of the Second node, but then changes the
`destination address back to the virtual address. The Second
`node transmits the requested resource directly to the client,
`with the Virtual address as its Source. Since all requests are
`first received by the load balancer which determines the
`physical location of the requested resource, nodes may
`contain different resources. The entire contents of the web
`site is not mirrored onto all nodes. Network bottlenecks are
`avoided Since the nodes transmit the large files back to the
`client directly, bypassing the load balancer. Client browsers
`can cache the virtual address, even though different nodes
`with different physical addresses Service requests.
`
`16 Claims, 18 Drawing Sheets
`
`SERVER
`FARM
`52
`
`80 Y
`
`CLIENT
`"BrewsR"
`
`
`
`
`
`&LENT
`"RojSEr"
`
`O&O)
`iBALANCER
`
`
`
`i
`
`of
`233.
`Sc.8. 20
`st
`
`sRWR
`23.81 i 102
`230 hit .233
`s:
`
`v is
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 1
`
`

`

`5,774,660
`Page 2
`
`OTHER PUBLICATIONS
`Balancing Act: Web Server Load Balancers, PC Magazine,
`Dec. "... p. 42.
`9.
`BIG/ip Product Spec, FAQ from Website www.f5.com, F5
`Labs, 1996.
`“How Your Browser Finds the Page You Want” PC Maga-
`zine Mar. 12, 1996 p. 107.
`
`“Internet Server Market Draws Foes' San Jose Business
`Journal, Mar. 25, 1996, p. 8.
`HydraWEB Frequently Asked Questions, Apr. 23, 1996, pp.
`1-8.
`HydraWEB Load-Balancer Product Literature, 1996.
`Cisco Local Director WWW pp. 1–5, 1996.
`WomPlex WWW pp. 1–3, 1996.
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 2
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 1 of 18
`
`5,774,660
`
`CLIENT
`"BROWSER"
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`11
`
`HOST NAME
`
`PADDRESS
`
`230.101.17.101
`
`14
`
`
`
`DNS
`SERVER
`
`PRIOR ART FIG. 1
`
`
`
`PRIOR ART
`
`
`
`
`
`
`
`
`
`
`
`CLIENT
`"BROWSER"
`
`
`
`230.101.17.101
`FWWW. round.Com
`
`20
`
`HTML PAGE
`
`FIG.2
`
`22
`SERVER
`230.101.17.101
`
`22B
`SERVER
`230.101.17.102
`
`
`
`22C
`SERVER
`230.101.17.103
`
`
`
`
`
`
`
`
`
`
`
`
`
`FILE.HTML
`
`FILE.HTML
`
`FILE.HTML
`
`24'
`
`26'
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 3
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 2 of 18
`
`5,774,660
`
`YSAYdsS
`
`a
`
`YdAussS
`
`WavNNEINES
`
`Vcc
`
`0€
`
`LuV¥Oldd
`
`WLHAlls
`
`OOL'ZLLOL0&20
`
`TIWLHSTs
`LOLZLLOLO€¢
`
`YsAYysas
`
`LNAIN9
`
`wdISMOUE.,
`
`LNAM9 ,Occ‘VOL02
`
`IWLH'31I4cOLLLLOLO&¢LOLZLLOLO€Z
`"..WOPUNOMMM=
`
`.
`e.o*
`°.e?
`
`e
`o®
`
`paneceesneereeeeesaoas,,
`
`wdISMOUE,
`
`eols38
`
`
`
`W0d'puNnOs‘MMM=
`
`COLZLLOLO€¢
`
`ASNOdS3YON
`
`Petitioners Microsoft Corporation and HPInc.- Ex. 1020,p. 4
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 4
`
`
`
`
`
`
`
`
`
`
`

`

`Jun. 30, 1998
`
`Sheet 3 of 18
`
`5,774,660
`
`U.S. Patent
`
`—
`
`IWLHAld
`OOLZLLOL0€Z
`
`YsaAdsS
`
`LNAIT9
`
`YwaAugs
`
`V9E
`
`WuvNeOL
`
`97vewdISMON
`
`9¢Tan
`
`
`
`YsAyssTHN
`
`WHS14b£1LOLO&e
`
`TTETNEzeVeT0021LoL0ez
`
`
`
`92veaNJALHWO"punosMMM=
`
`
`YsalLnow
`
`
`
`goe“dvol49vd
`
`02
`
`
`
`
`
`YAONVIVE“aAMaS00Z'Z1'Cun1———>LOLOz
`
`:ZOLLILOL0&2
`
`
`
`IWLHS14pqs.
`
`
`
`92iveJ9VdIWLH
`
`INaITo
`
`wdASMONE.
`
`-dSANSRS
`
`EO)LLLOLOzVOIAOO41101Ee
`.veSplat:
`
`Tuvdoled
`
`WOPpunol:MMM=
`
`voz
`
`Petitioners Microsoft Corporation and HPInc.- Ex. 1020, p. 5
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 5
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 4 of 18
`
`5,774,660
`
`SERVER
`FARM
`
`30
`
`N 22A
`SERVER
`
`22
`SERVER
`
`22B
`SERVER
`
`22C
`SERVER
`
`
`
`
`
`10
`
`
`
`CLIENT
`"BROWSER"
`
`10A
`
`
`
`
`
`
`
`CLIENT
`"BROWSER"
`
`URL'S
`50-150 BYTES
`
`HTML PAGES
`1 OK TO MBYTES
`
`HTML PAGES
`
`FIG.5
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 6
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 5 of 18
`
`5,774,660
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`10
`
`50
`
`HTML PAGES
`1 OK TO MBYTES
`
`LOAD
`BALANCER
`230.101.17.200
`
`
`
`
`
`
`
`
`
`50-150 BYTES
`
`CLIENT
`"BROWSER"
`
`
`
`
`
`230.101.17.200
`FWWW.round.com
`
`20
`
`10A
`
`CLIENT
`"BROWSER"
`
`
`
`
`
`230.101.17.200
`FWWW. round.Com
`
`34
`
`HTML PAGES
`S
`1OK TO MBYTE
`
`SERVER
`FARM
`
`52A
`SERVER
`230.101.17.101
`230.101.17.200
`52
`SERVER
`230.101.17.102
`230.101.17.200
`52B
`SERVER
`230.101.17.103
`230.101.17.200
`52C
`SERVER
`230.101.17.104
`230.101.17.200
`
`FIG.6
`
`20
`
`180 NIC ADDR
`(DEST)
`
`TCP/IP HEADER
`-N-uu-N
`SRC P DEST IP
`ADDR ADDR PROTOCOL DATA
`
`182
`
`184
`
`186
`
`188
`
`189
`
`FIG.7
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 7
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 6 of 18
`
`5,774,660
`
`CLIENT
`"BROWSER"
`
`1O
`
`66
`
`
`
`
`
`100, 102
`
`104
`
`
`
`SERVER
`230.101.17.1OO
`230.101.17.200
`56
`
`c
`
`SERVER
`230.101.17.101
`230.101.17.200
`
`SERVER
`230.101.17.102
`230.101.17.200
`
`52
`
`c
`
`58
`
`62
`
`26
`
`FIG.8
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 8
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 7 of 18
`
`5,774,660
`
`
`
`
`
`vSIYAAYASGANDISSVOL
`
`
`
`
`
`ISANOAYNOILOANNOOGYVMYOS
`
`cS/
`
`
`
`YSAYgSGANDISSVMOld
`
`
`
`
`
`ONIONVIVEGVOTWYO4YAd
`
`OS1
`
`SAISOSY
`dASMONGWOYSsLSANODAY
`
`
`NOILOANNOO
`
`6Sls
`
`QSL
`
`Lav
`
`dani
`
`14TWH
`yOlud
`O91€/1HONOYHLYASMON
`
`
`THN
`OlMOVEYSASNVUYLVLVG
`
`
`
`YOdLSAND]AY
`
`
`
`dNLASNOISSAS
`
`
`
`
`
`
`
`NOILOANNOOdOlYSAAYNRSAMV
`
`a
`
`YsaAdgs
`
`Petitioners Microsoft Corporation and HPInc.- Ex. 1020, p. 9
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 9
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 8 of 18
`
`5,774,660
`
`
`
`vOlYASMONUOLMOVE
`
`OlSls
`
`
`
`
`
`AILOAYICYSASNVULVLVO
`
`YSAYSS
`
`OcYSANRSOLd/1WOYS
`
`
`
`YSASNVYLALVLSdol
`
`Gc
`
`fL
`
`
`
`FJOUNOSAYGALSANDAYNOGasvad
`
`
`
`ONIONVWdGVO1WeOsdAd
`
`
`
`SAONNOSAYSTEVIIVAVGNV
`
`MOVEAV1dd/1
`
`YSAYASOL
`
`001
`
`ISANOIAYTHNHOSLivM
`
`
`
`4suvd‘AldTWLHYOS
`
`dq]
`
`Petitioners Microsoft Corporation and HPInc.- Ex. 1020, p. 10
`
`
`NOILOANNOOdolYAAYASAVA
`
`
`
`
`dNlasNOISSAS
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 10
`
`
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 9 of 18
`
`5,774,660
`
`CLIENT
`
`LOAD-BALANCER
`
`SERVER
`
`NITIATE
`CONNECT
`
`SYN(0)
`
`SESSION
`SETUP, FAKE
`SYN/ACK
`-- 1 OO
`
`SYN/ACK
`p-1
`CONNECTION
`ESTABLISHED
`
`ACK(0)
`
`FIRST
`USER
`PUSH(0)
`REGUEST N PARSE URL,
`SCHEDULE
`TO SERVER
`BASED ON FILE
`LOCATION
`
`102
`
`SYN'(O)
`N MIGRATE
`SYN'/ACK
`STATE
`PLAYBACK to-1
`SETUP TO
`SERVER
`SERVER GN CONNECTED
`ACK'(O)
`TO CLIENT
`
`h
`
`(
`12
`O
`
`(
`104
`
`PASS
`PUSH'(O)
`THROUGH
`FIRST USER N
`REGUEST
`HANDLE DATA
`REQUEST, SEND
`u- FILE(S)
`FIG.1 1A
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 11
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 10 of 18
`
`5,774,660
`
`CLIENT
`
`LOAD-BALANCER
`
`SERVER
`
`ANOTHER
`USER
`PUSH (1)
`REQUEST N
`PASS THROUGH
`USEiEAREGUEs, N.
`HANDLE DATA
`REQUEST, SEND
`u- FILEs)
`
`PUSH'(1)
`
`126
`
`FN
`SESSION CLOSE 1.
`(
`130 T- PASS THROUGH FIN
`
`CLOSE
`CONNECT
`
`C - C
`
`REMOVE SESSION 16.
`PASS THROUGH ACK
`
`ul
`
`FG.11B
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 12
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 11 of 18
`
`5,774,660
`
`S=Ydqvdl
`
`YAaAysAs
`
`YFONV1VE-dvVO]
`
`A=4ddVdi
`
`LNAIM19
`
`
`
`YAAYsSGd1LLH
`
`
`
`(YSAV1ddv)
`
`YaINGSHOS
`
`
`
`(YSAVIddv)
`
`
`
`(YSAV1ddv)
`
`daSMOud
`
`c6
`
`*dWV/dOl
`
`(A\dOL
`
`v6
`
`OVNI
`
`>
`
`*dV/dOL
`
`c8
`
`
`
`VIQAWTWOISAHd
`
`QZ
`
`My
`
`C|Ol(A)dOL
`
` OVNIwotsawsg(A)dOL(A)dOL
`
`dOYadavWOALUYIA
`YSANgSoe|‘Yddipl
`OVW1V3u
`(S)dXI.(A)dX!
`di/dOLaf~
`
`Gl
`
`(A)dOL
`
`OVA/INIT
`
`Petitioners Microsoft Corporation and HPInc. - Ex. 1020, p. 13
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 13
`
`
`
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 12 of 18
`
`5,774,660
`
`Z/
`
`dl/d0 L
`
`(O)CHOL
`
`a’
`
`06
`
`
`
`(HEXVI ddw)
`
`(O)?OL
`
`Z6
`
`xd1/d0 L
`
`
`
`
`
`No.yºWICIEW TVOISAHd , 94
`
`76
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 14
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 13 of 18
`
`5,774,660
`
`
`
`*IPINTRO)
`
`IP FORWARD()
`
`*IP OUTPUT()
`
`200
`
`2O2
`
`206
`
`
`
`84
`
`LINK LAYER (NIC/MAC DRIVER)
`
`FIG.14
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 15
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 14 of 18
`
`5,774,660
`
`200
`
`S
`PACKET FOR
`LOCAL NODE
`
`
`
`NO
`
`SEND TO
`IPFORWARD(), FIND
`NEXT HOP
`
`
`
`302
`
`
`
`YES
`
`
`
`306
`
`RE-ASSEMBLE IP
`DATAGRAM FROM
`PACKETS
`
`3O4
`
`XP
`PROTOCOL
`?
`
`YES
`
`CHANGE
`TO TCP
`
`312
`
`308
`
`
`
`
`
`
`
`
`
`
`
`310
`
`TCP
`PROTOCOL.
`VIRTUAL PADDR
`AND WEB
`PACKETP
`
`
`
`
`
`CHANGE TCP TO XP
`PROTOCOL.
`
`314
`
`YES
`
`318
`
`SEND TO TCP
`LAYER
`
`
`
`
`
`
`
`
`
`KNOWN
`PROTOCOL
`(TCP)
`2
`
`
`
`316
`
`NO
`
`SEND TO RAW
`SOCKET
`(SCHEDULER)
`
`320
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 16
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 15 of 18
`
`5,774,660
`
`*IPOUTPUT()
`
`READ DESTINATION IP
`RE
`ADDRESS
`
`330
`
`DETERMINE ROUTE AND
`NC ADDRESS
`
`332 FG 16
`
`
`
`
`
`
`
`
`
`
`
`XP
`PROTOCOL
`
`NO
`
`
`
`
`
`LOCAL
`DESTINATION
`
`
`
`
`
`CHANGE PROTOCOL
`TO TCP
`
`
`
`
`
`
`
`340
`
`CHANGE DEST. PADDR.
`TO VIRTUAL PADDR.
`
`344
`
`SEND TO LINK
`LAYER (MAC)
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 17
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 16 of 18
`
`
`
`?|E/\>|ES Old_L_LH>HETITICIEHOS
`
`
`
`
`
`(HEXVI ddV)(HEXVI ddV)
`
`>HES/WORJE
`
`
`
`(HEXVI ddV)
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 18
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 17 of 18
`
`5,774,660
`
`FIG. 18
`
`SCHEDULER
`LOAD-BALANCER
`
`
`
`350
`
`352
`
`354
`
`
`
`
`
`356
`
`
`
`
`
`ESTABLISH CONNECTION
`WITH BROWSER CLIENT
`
`WAIT FOR AND PARSE URL
`DETERMINE CONTENT LOCATION
`
`LOAD BALANCE AMONG SERVERS WITH
`RESOURCE REO UESTED IN URL
`
`REPLACE VIRTUAL PADDRESS WITH REAL IP
`ADDRESS OF ASSIGNED SERVER
`
`
`
`SENDTO() CALL
`TO “IPOUTPUT()
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 19
`
`

`

`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 18 of 18
`
`5,774,660
`
`CLIENT
`"BROWSER"
`
`10
`
`T1/T3
`
`
`
`
`
`CONNECTION
`ROUTER
`
`s
`
`T1/T3
`
`CONNECTION
`ROUTER
`
`70
`
`SERVER
`
`SERVER 70
`
`56
`
`51
`
`52
`
`A
`
`C
`
`s
`
`A
`B
`FILE.HTML
`
`B
`
`FILE.HTML
`
`s
`
`55
`Ce
`
`C
`
`58
`
`60
`
`26
`
`62
`
`26
`
`63
`
`FIG.19
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 20
`
`

`

`5,774,660
`
`1
`WORLD-WIDE-WEB SERVER WITH
`DELAYED RESOURCE-BINDING FOR
`RESOURCE-BASED LOAD BALANCING ON
`A DISTRIBUTED RESOURCE MULTI-NODE
`NETWORK
`
`2
`Internet-Protocol (IP) address. Each computer is typically
`assigned a different IP address So that no two machines have
`the same IP address. The IP address is often written as four
`decimal numbers separated by periods. Each decimal num
`ber represents an 8-bit binary number, from Zero to 255 in
`decimal notation. Thus a computer in IBM's domain might
`have the IP address 209.180.55.2 while another computer in
`that domain might have the address 209.180.55. 103.
`Client Browsers Accessing Web Servers
`FIG. 1 is a diagram of a client browser looking up the IP
`address of a host specified in a URL. Users of a remote
`computer use client Software known as an Internet browser
`or simply a browser. Popular browsers include Netscape
`Navigator by Netscape Communications, Inc. of Mountain
`View, Calif. and Internet Explorer by Microsoft Corp. of
`Redmond, Wash., although many other browsers and other
`types of client Software are used.
`Browser 10 initiates a communication session with a
`remote Server by the user Selecting a URL, perhaps by
`mouse-clicking on a hyper link to a new web page. Host
`name 11, “www.round.com”, in the URL “http://
`www.round.com/file.html, is sent to domain-name-system
`(DNS) server 14, which is a special Internet server with
`look-up table 16. DNS server 14 is often a special server at
`an Internet Service Provider which contains most or all
`domain names on the entire Internet, or in a local region of
`the Internet. One DNS server may have to refer the request
`to another DNS server for unknown host-names.
`DNS server 14 looks through look-up table 16 and finds
`an entry for the host www.round.com. This entry contains a
`physical IP address 18 for the web-server host in the domain
`round.com. This IP address 18230.101.17.101 is returned to
`browser 10. Browser 10 then stores this IP address in client
`cache 20 for future use, a process known as browser caching
`of the IP address.
`Browser 10 then uses cached IP address 18' to initiate a
`communication Session with the remote computer which
`physically has the desired web page, the www.round.com
`server having the file.html file. FIG.2 shows a browser using
`a cached IP address to retrieve a file from a remote server in
`a server farm. Browser 10 reads the cached IP address 18'
`from client cache 20 and uses cached IP address 18' to
`initiate a communication Session with remote Server 22.
`Once the session with server 22 is established, URL 12 is
`sent to server 22. Server 22 then accesses disk 24 which
`includes requested file 26, the file.html web page. A file copy
`26' of requested file 26 is sent back to browser 10, which
`re-constructs the web page from file copy 26' and displayS
`the web page to the user. Other files Such as graphic image
`files may also be transferred which were not directly
`requested by the URL, but are referenced by the file.html
`file.
`Server Farms for Large Web Sites Mirror Content
`While some smaller web sites can be served from a single
`computer, larger web sites require multiple computer
`machines acting as Servers. Some web sites receive as many
`as one million requests or “hits’ per hour, requiring many
`WorkStation computers.
`FIG. 2 shows server farm 30 which contains server 22
`serving browser 10, and servers 22A, 22B, 22C which are
`servicing other browsers (not shown). Servers 22A, 22B,
`22C each contain their own disks 24', each with a copy of all
`the web pages in the Site, including requested file 26. Server
`farm 30 is basically a group of replicated Servers which can
`Service requests from multiple browsers. Each Server has a
`copy of the entire web site. Any Server can Service any
`request Since the content is “mirrored” on all Servers.
`
`BACKGROUND OF THE INVENTION FIELD
`OF THE INVENTION
`This invention relates to network Servers, and more par
`ticularly to Internet Servers.
`BACKGROUND OF THE INVENTION
`DESCRIPTION OF THE RELATED ART
`Use of the global network known as the Internet has
`skyrocketed. Advertisers commonly feature their Internet
`addresses in television, billboard, and magazine ads. Con
`Sumers with a remote computer can access the Internet using
`client Software known as a browser. Explosive growth is
`occurring in the part of the Internet known as the World
`Wide Web, or simply the “web”. The web is a collection of
`millions of files or “web pages” of text, graphics, and other
`media which are connected by hyper-links to other web
`pages. These may physically reside on a computer System
`anywhere on the Internet-on a computer in the next room
`or on the other side of the world.
`These hyper-links often appear in the browser as a graphi
`cal icon or as colored, underlined text. A hyper-link contains
`a link to another web page. Using a mouse to click on the
`hyper-link initiates a proceSS which locates and retrieves the
`linked web page, regardless of the physical location of that
`page. Hovering a mouse over a hyper-link or clicking on the
`link often displays in a corner of the browser a locator for the
`linked web page. This locator is known as a Universal
`Resource Locator, or URL.
`Background of URL's, IP Addresses, HTML, HTTP
`The URL identifies a domain, a host within that domain,
`and Sometimes a resource or file within a directory Structure
`on the host computer. Domains can be thought of as a group
`of computers, Such as all computers on a company's net
`work. For example, the domain "ibm.com” identifies a
`domain for the commercial company IBM, which may
`include thousands of individual computers. Typically the
`URL identifies only those computers which are servers on
`the world-wide web by prefixing the domain with a host
`name. Thus the URL “http://www.ibm.com” identifies an
`individual host computer within the ibm.com domain which
`operates as a world-wide-web server for IBM. “HTTP” tells
`the host to use the hyper-text transfer protocol while deliv
`ering files over the Internet. The files delivered can be from
`resources Such as database queries or execution of Scripts by
`the host as well as traditional files.
`A web server Site may contain thousands of individual
`web pages. The location of the file or resource containing a
`desired page is identified by appending a directory-path file
`name to the host and domain names in the basic URL to form
`a new URL. Thus the URL “http://www.ibm.com/dira/dirb/
`dirc/intro.html identifies a hyper-text markup-language
`(HTML) file called “intro.html” which resides on a host
`named “www' within the ibm.com domain. The file resides
`in the dira directory and the dirb/dirc Subdirectory. Often this
`HTML file contains references to other files which are
`loaded automatically by the client's browser.
`While the URL is used to locate a file on a host within a
`domain, it does not contain a physical address for the host
`computer. Addresses of computer machines on the Internet
`are specified using a 32-bit numeric identifier known as the
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 21
`
`

`

`5,774,660
`
`15
`
`25
`
`35
`
`40
`
`3
`Each machine typically has its own unique IP address.
`Since a domain can have many computer machines with
`many IP addresses, Some way to provide to a client one of
`the many server machines’ IP address is needed. One simple
`approach is known as rotating DNS or DNS round-robin
`load-balancing.
`DNS server 14 of FIG. 1 contains look-up table 16 which
`is used to return IP addresses to host-lookup requests from
`client browsers. Look-up table 16 contains entries for dif
`ferent host names. The entry for a host name specifies the IP
`addresses for that host and each entry can contain Several IP
`addresses for that host. The entry for www.round.com host
`on the domain round.com contains four IP addresses:
`230.101.17.100
`230.101.17.101
`230.101.17.102
`230.101.17.103
`for the four servers 22A, 22, 22B, 22C of server farm 30
`serving the www.round.com web site. When a client
`requests a DNS look-up, one of these IP addresses is chosen
`in a round-robin fashion. Each time a different client looks
`up the host www.round.com, a different IP address is
`returned until all the available IP addresses are used. Then
`the first IP address is returned again. Thus the first browser
`is sent the IP address for server 22A, the second browser is
`sent the IP address for server 22, the third browser sent the
`IP address for server 22B, and the four browser sent the IP
`address for server 22C. The fifth browser request to DNS
`Server 14 is Sent the first Server 22A, and So on in a
`round-robin fashion.
`Each DNS server operates independently of other DNS
`servers. Thus optimal load balancing is not always achieved.
`Other more Sophisticated assignment Schemes have been
`used, such as “load-balancing DNS” which sends requests to
`Servers based on a balancing algorithm which attempts to
`balance the load on each server. With this approach more
`powerful Servers could be assigned more requests than
`weaker Servers.
`IPAddresses of Servers Cached on DNS Server
`DNS servers 14 (FIG. 1) often cache the results of
`domain-name lookups which were passed or forwarded to
`other DNS servers for completion. The administrator of the
`www.round.com web site has no way of actively updating
`the contents of many DNS caches containing IP addresses of
`servers in server farm 30. Instead, the administrator must
`rely on the remote DNS servers periodically flushing their
`own cached IP addresses and looking up the www.round
`.com host again. DNS servers may flush their cached IP
`addresses every few minutes or not for several weeks. IP
`addresses can thus remain in a DNS server's cache long after
`the server with the cached IP address is removed from
`Service. The IP address of the removed server can continue
`to be assigned by the DNS server until the cached entry is
`replaced or flushed.
`For the example in FIG. 3, when server 22C crashes, its
`IP address 230.101.17.103 remains in use in DNS server
`caches. Users that look-up the www.round.com host name
`can be assigned the IP address of crashed server 22C. Users
`sent the IP address of crashed server 22C are unable to
`access Server farm 30, even though Several other Servers
`22A, 22, 22B at server farm 30 are operational.
`DNS Caching Blocks Some Users From Partially-Crashed
`Web Site
`Several hours or even days may be required to flush the
`IP address of the crashed server 22C from all DNS caches.
`Thus DNS servers can continue to send the IP address of the
`crashed Server to browsers long after the Server has crashed.
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`Browsers attempting to use this IP address and connect with
`the crashed Server receive no response from the www.round
`.com web site. These browsers are frozen out of the
`www.round.com web site.
`Since the browser itself caches the IP address from the
`DNS server until the browser application is closed, browsers
`can Still attempt to access a crashed Server after the crash has
`occurred. FIG. 3 shows a browser using a cached IP address
`to access a crashed Server which is not responding. Browser
`10A had previously cached IP address 18C for server 22C
`for the www.round.com host. When browser 10A attempts to
`connect to www.round.com, Server 22C is accessed. No
`response is received from Server 22C since the Server is not
`functioning. To Browser 10A, the web site www.round.com
`appears to be non-functional, even though to another
`browser 10, the web site is functional.
`Though the user of browser 10A may repeatedly try to
`connect to the www.round.com web site, each time no
`response is received until server 22C is fixed. Since DNS
`server 14 of FIG.1 may continue to use the IP address of the
`crashed Server 22C, many users may be locked out from the
`Web Site, even though other users can access the Site.
`When browser 10A also caches IP address 18C, the
`browser may not be informed that the IP address is no longer
`valid even after DNS server updates its own cache. These
`browser caches may persist for Several hours, preventing the
`user from accessing the web site. Should the server 22C be
`removed from Service permanently, perhaps being
`re-assigned to another web site, the user is effectively
`blocked from accessing the web site until the user flushes his
`IP cache, which may not occur until the user exits the
`browser application.
`Of course, with a large Server farm, the loSS of one Server
`blocks out only 1/N of the users, where N is the number of
`servers in the server farm. Thus for FIG. 3, one-fourth of the
`current users are blocked out while %ths of the current users
`have access to the web site. One-fourth of the new users
`looking up the host on a DNS server which still uses the old
`IP address of the crashed server are also blocked from the
`web site.
`Router-Based Web Site
`An approach which mitigates Some of these problems
`inserts a multiplexer or router between the browser clients
`and the server farm. FIG. 4 illustrates a router-based server
`farm. A single IP address of router 32, 230.101.17.200, is
`available to all DNS servers as the single IP address for the
`web site. Browser 10 caches this IP address as cached IP
`address 34. Requests from browser 10 are sent to router 32
`since cached IP address 34 points to router 32.
`Router 32 receives all packets in the transmission from
`browser 10. Router 32 might be a dedicated personal com
`puter (PC) which uses an algorithm to determine which of
`servers 36A, 36,36B, 36C in server farm 38 should service
`the request from browser 10. Router 32 may use a fairly
`complex load-balancing Scheme which takes into account
`requests from other browsers and the capability of each
`Server when Some Servers are powerful WorkStations while
`other servers are older, slower PCs.
`All the packets in the session from browser 10 received by
`router 32 are re-transmitted to server 36, with the destination
`IP address changed to the IP address for server 36,
`230.101.17.101. Server 36 retrieves the requested file 26
`from its local disk 24 and transmits it back to router 32,
`which then re-transmits the file to browser 10.
`When a server crashes, such as crashed server 36C, only
`those browsers which are currently connected to server 36C
`experience server failure. Client caching of the router's IP
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1020, p. 22
`
`

`

`25
`
`S
`address causes all new Sessions to be routed to router 32,
`only Sessions in progreSS to crashed Server 36C receive no
`response from the web site. Thus when one of the servers
`fails, only 1/N of the currently active requests fail, where N
`is the number of servers. New requests do not fail since
`router 32 detects when crashed server 36C is not functioning
`and no longer directs new requests to the down Server.
`A commercial embodiment of a router-based web server
`has been announced by SOS Corp. of New York, N.Y., under
`the name “HydraWEB', and product literature indicates that
`a patent is pending. A Second commercial embodiment is the
`Cisco Local Director, manufactured by Cisco Systems of
`San Jose, Calif. Each server 36A, 36, 36B, 36C contains a
`local copy of all content on the web site on disks 24, 24'.
`Mirroring the full content of the site to all servers is a
`disadvantage for web sites with a large amount of content,
`because of the size and cost of the local disks. Certain web
`applications Such as multimedia and Video delivery can
`require a particularly large amount of disk Space. These
`applications are expensive to implement and thus minimiz
`ing the number of copies at the Server farm is desirable.
`Another disadvantage with the router web site is that all
`data transferS go through router 32. Since many web pages
`contain graphics or even video or Sound, the amount of data
`transferred from the server through the router to the browser
`is large. Router 32 must be fast and efficient to handle load
`balancing and routing of incoming and outgoing packets. AS
`the Web Site becomes more popular and traffic grows, router
`32 can quickly become a bottleneck and limit performance
`of the web site. Router 32 is also a single point of failure.
`Load-Balancing Granularity Determines Users Affected by
`Server Failure
`For round-robin DNS, the IP address of the web server is
`assigned once to the client browser and all Subsequent
`accesses use this IP address until the browser's client cache
`is purged. This is client-level load-balancing granularity,
`Since each client is assigned one Server machine for all
`requests from that client. When the assigned Server crashes,
`the clients using that Server are blocked for all future
`requests until the client application is closed.
`The router-based web site has request-level load
`balancing granularity. Servers are assigned to handle indi
`vidual requests from browsers. When the assigned server
`crashes, the outstanding requests to the Server are blacked
`out but clients can Still access other Servers in the farm.
`Server Problems Plague the Internet
`Many Internet users can testify to the utter frustration
`when the “SERVER NOT RESPONDING” error message is
`displayed on their browser while trying to connect to a web
`Site. Users often blame the company which administers the
`unavailable web site. Web sites are not as fault-tolerant as
`possible despite large investments in replicated Servers. An
`intelligently-designed web-site architecture with better
`fault-tolerance is needed.
`It is desired to reduce the frequency of “SERVER NOT
`55
`RESPONDING” messages that Internet users often receive.
`While many web sites use server architectures such as DNS
`round-robin and router-based load-balancing, a more effi
`cient and fault-tolerant web-site architecture is desired. It is
`desired to avoid the data bottleneck and Single point of
`failure at the router for router-based web sites. It is also
`desired to use inherent characteristics of web traffic to more
`efficiently design a web-site architecture. Mirroring the
`content of the entire web site to all servers at the site is
`undesirable, but having differing content on different Servers
`is desired while Still performing load balancing. A web site
`with request-level load-balancing granularity is desired So
`
`35
`
`40
`
`45
`
`50
`
`60
`
`65
`
`5,774,660
`
`15
`
`6
`that fewer users experience a browser lock-up when a Server
`at the web site fails. A web site that can use the standard
`DNS mechanism is desired to overcome the limitations of
`DNS caching and complex maintenance of round-robin
`DNS.
`
`SUMMARY OF THE INVENTION
`A web site Sends resources to a browser on a client
`connected to a computer network. The Web Site has a
`network connection point for receiving incoming data pack
`ets from the computer network and for transmitting outgoing
`data packets to the computer network. A local network is
`coupled to the network connection point and transferS data
`packets. A plurality of network nodes contain Web Servers
`with resources. The plurality of network nodes is connected
`to the local network. The plurality of network nodes transmit
`the resources as outgoing data packets over the local net
`work to the network connection point through the computer
`network to the client.
`A balancer network node contains a load balancer that
`receives the incoming data packets transmitted over the local
`net