`US 6,167,427
`
`6,167,427
`PATENT:
`INVENTORS: Rabinovich, Irina
`Rabinovich, Michael
`
`TITLE:
`
`Replication service system and method
`for directing the replication of
`information servers based on selected
`plurality of servers load
`
`APPLICATION
`NO:
`FILED:
`ISSUED:
`
`US1997979611A
`
`28 NOV 1997
`26 DEC 2000
`
`COMPILED:
`
`15 AUG 2017
`
`MIT 2007
`Limelight v. MIT
`IPR2017-00249
`
`1
`
`
`
`UTILITY
`SERIAL
`
`PARTS OF Apmcrmou
`FILED SEPARATELY
`; NOTICE OF ALLOWANCE MAILED
`
`'
`
`’
`
`..
`
`_
`
`.
`('1! 8-
`. .' =
`.
`'1 Examine
`CLAIMS A LOWED
`
`.
`
`-
`
`‘
`
`'
`
`Assls'tan! Examiner
`
`‘3
`
`I
`
`c
`11’1M010g4 00
`
`7
`
`
`
`IEN LUU
`8
`PRIMARY EXAMINER
`I
`Primaryr Examiner NUMBER @ag
`
`,.. 5-
`
`PREPARED FOR lSSUE
`
`WARNING: Th3 infonnallon disclosed herein may be restricted. UnautImrizad disclosure may be prohibiied
`by the Unltad Slates Code Trlfa 35. Sections 122. 1'81 and 353. Possession outside Ihe U.S.
`Palanl E. Trademark (Mine is reminded to authorizad Bmplwaas and cunlracwts only.
`
`3:: 337““
`
`tag
`CA
`;'~----""'"
`
`Issue Fee
`
`“Mg-m an.
`
`2
`I FACE)
`
`
`
`2
`
`
`
`(cid:3)
`
`6,167,427
`REPLICATION SERVICE SYSTEM AND METHOD FOR DIRECTING
`THE REPLICATION OF INFORMATION SERVERS BASED ON
`SELECTED PLURALITY OF SERVERS LOAD
`Transaction History
`
`Transaction Description
`Date
`Initial Exam Team nn
`12-22-1997
`02-09-1998 Change in Power of Attorney (May Include Associate POA)
`03-07-1998
`IFW Scan & PACR Auto Security Review
`03-11-1998 Notice Mailed--Application Incomplete--Filing Date Assigned
`04-16-1998
`Preexamination Location Change
`05-11-1998 Case Docketed to Examiner in GAU
`04-12-1999 Non-Final Rejection
`04-12-1999 Case Docketed to Examiner in GAU
`04-20-1999 Mail Non-Final Rejection
`10-27-1999 Workflow - Drawings Finished
`10-27-1999 Workflow - Drawings Matched with File at Contractor
`10-27-1999 Workflow - Drawings Received at Contractor
`10-27-1999 Response after Non-Final Action
`10-27-1999
`Incoming Letter Pertaining to the Drawings
`10-27-1999 Correspondence Address Change
`10-27-1999 Request for Extension of Time - Granted
`11-02-1999 Date Forwarded to Examiner
`01-13-2000 Mail Final Rejection (PTOL - 326)
`01-13-2000
`Final Rejection
`07-14-2000 Response after Final Action
`07-17-2000 Date Forwarded to Examiner
`07-26-2000
`Examiner Interview Summary Record (PTOL - 413)
`08-03-2000 Mail Notice of Allowance
`08-03-2000 Notice of Allowance Data Verification Completed
`08-08-2000 Mail Examiner's Amendment
`08-08-2000
`Examiner's Amendment Communication
`08-29-2000 Mail Examiner's Amendment
`08-29-2000
`Examiner's Amendment Communication
`09-11-2000
`Issue Fee Payment Verified
`09-21-2000 Workflow - File Sent to Contractor
`11-03-2000 Workflow - Complete WF Records for Drawings
`11-07-2000 Application Is Considered Ready for Issue
`12-07-2000
`Issue Notification Mailed
`12-26-2000 Recordation of Patent Grant Mailed
`03-30-2015 Correspondence Address Change
`03-31-2015 Change in Power of Attorney (May Include Associate POA)
`06-11-2017 Correspondence Address Change
`06-12-2017 Change in Power of Attorney (May Include Associate POA)
`
`(cid:3)
`
`3
`
`
`
`
`PATi'af APPLIémoAIH'
`
`WWIIWNWIWIWW
`0897961 I
`
`'_ -_;.'CONTENTS .,9;
`
`
`
`
`
`
`
` H 4
`
`{FRONT}
`
`.
`
`4
`
`
`
`8T”LE
`
`Ann
`
`u U 5. GOVERNMENT PRINTING OFFICE IN?“
`
`
`
`
`ASMTAHT ERA
`
`'I'FIERSE STEM? DR PM? FUILNAIEJ
`
`
`
`
`
` ,‘i-.
`
`
`
`\
`
`\
`
`
`
`
`
`.n...m;-
`
`-—-_._.
`
`ww‘uui
`
`P]
`
`
`
`“.3u
`|||
`'0 a.
`mI“
`1l
`Nw
`
`Na
`NU1
`H
`.J
`M 'Hl
`I
`I“.u:
`PO‘0
`
`uD1
`
`In} a
`(JN
`
`
`
`.
`
`._
`
`.
`
`1
`
`
`
`G) 3.0 .9 §__6_O ®_© O O
`
`
`- .2736 mv-sfixfmflrwiasefimm W 'WM .u.‘ .
`
`
`”7-1
`
`'E''
`“L.
`1.".
`
`
`
`
`3!HIE?Illlflflflfiflflflflflflfl
`aaahnfiinfifla‘
`
` "man}!mInL
`
`
`
`
`u“‘2':—as.HiI
`
`
`
`
`
`
`
`
`
` 43
`
`
`
`Efififififimfifififi8
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`uh!LU
`(a
`
`
`
`u E”
`
`
`
`
`
`
`5m: 5
`
`(LEFT INSIDE)
`
`5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` INDEX OF CLAIMS
`
`
`
`
`
`
`
`
`
`
`
`
`
`“HI-I-nnnl-lmnm-l—l.-_m__
`
`
`
`“---.---Iv![bl
`
`
`
`
`
`Sawfly
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`I
`
`r.J.
`
`Jn.
`
`
`
`{LEFT' INSIDE]
`
`
`
`344.444453fl_[IhI..45_.J?39):.31455?89D1.23455?B123.4.5678D11111Tam22222£22333333333840
`
`
`
`
`
`
`
`
`
`
`
`
`6
`
`
`
`
`
`
`
`
`
`
`
`
`inmate; new“
`
`Sub.
`
`Date
`
`SEKHCHED
`
`vij- 2 mam-i amw. cuts
` @cuflua urn-may
`
`{RIGHT OUTSIDE)
`
`7
`
`
`
`5 Trademark Office ‘
`* RECONNECTED TO U.S. Patent
`*
`* * ' i
`SESSION RESUMED IN FILE rUSPAT' AT 13:02:13 on 11 APR 1959
`FILE ‘USPAT' ENTERED AT 13:02:13 on 11 APR 1999
`=> act a919611/1
`
`*
`
`*
`
`*
`
`* *
`
`03/9?9,611
`
`Page 1
`
`(
`
`(
`
`(
`
`L1
`TRI
`L2
`H P
`L3
`OR
`L1
`L5
`LE
`IFF
`L1
`(DI
`(
`LB
`(
`L9
`LID t
`TFF
`L11 t
`NTE
`L12 (
`LAN
`L13 (
`L14 (
`L15 (
`L5
`L16 (
`L1? (
`L13 (
`L19 (
`L20 (
`L21 (
`L22 (
`
`(
`(
`(
`
`(
`
`L23 (
`L24 (
`L25 (
`L26 (
`L27 (
`“1
`L22 (
`[.29 {
`L30 (
`IFF
`L31 (
`(DI
`L32 L
`L33 (
`L31 (
`IFF
`L35 (
`NTE
`L36 {
`LAN
`L37 (
`L38 (
`
`TUISSBISER FILE=USPAT [LOAD BALANCING OR ALLOCAT? OR SHAH? OR DTS
`
`531002}SBA FILE=DSBAT L1 AND {TECHNIQUE
`
`OR METHOD OR ALGORITHM D
`
`19390)SEA FILE=DSPAT L2 AND [MAXIMUM AND MINIMUM] AND THRESHOLD
`
`192:SEA EILE=USPAT L3 AND CLIENT AND SERVER
`thsEA F1LE=USPAT Lq AND (TREE STRUCTURE OR HIERARCH?)
`BEJSEA F1LE=USPRT LOAD BALANC? AND (BENCHMARK OR MARK) AND (D
`
`12115EA EILE:USBAT LOAD BALANC? AND (BENCHMARK? OR MARK21 AND
`
`4315}SEA FILE=USPAT TREE(3A)(STRDCTUR? 0R HIERARCH?)
`15)SRA 21LE=USDAT L1 AND LB
`0:5EA FILE=USDAT LOAD BALANC? AND (BENCHMARK 0R MARK) AND (D
`
`51215152A F1LE=USPAT (DOMAIN NAME SERVERH 0R DNSJ OR (BERKELEY I
`
`ISJSEA EILB=USPAT L11 AND REPLICA? AND OBJECT§ AND LOAD(3A)BA
`
`2353A EDLE=USDAT L12 AND (URL# AND IPEJA]ADDRESS?J
`22JSSA EILE=USPAT REPLICA?(PJSERVER#(9)OBJECT*(PINAMEH
`115EA FILEEUSPAT 345/335ICCLS AND ass/200.33. 200.31. 335/CC
`
`171(5EA ETLEaDSPAT 395/200.33,200.31,335lCCLS
`322)SEA FILE-USPRT 345/335/CCLS OR L16
`32E}SEA FILE=USPAT L17 OR L16
`é)SEA FILB=USDAT LIE AND L14
`]}SEA FILE-USPAT 4530251/PN
`12273)SBA FILE=USPAT LDAD(3A:(DALANC OR DISTRIBUT?)
`1121A!SEA F1LE=USBAT LOAD<3AJ£BALANC2 OR DISTRIBUT? OR ALLOCA121
`
`3BD)SEA FILE=USPAT MAXIMUM LOAD AND MINIMUM LOAD
`4102581533 F1LE=USPAT DIFFER? AND (MARK? OR THRESHOLD?)
`103}SEA FILE=USPRT L23 AND L21
`11}SEA FILE=DSPAT L25 AND L22
`235BJSEA FILE=DSPAT DIFFERENCE(3AJ(BETWEEN(3A)MAXIMUMI3A:MINIMU
`
`3?}5EA F1LE=USPAT L21 AND L22
`JISEJ‘L FILE=USPAT HIT 1:28,
`1
`62ISSA FILE=DSPAT LOAD BALANC? AND (BENCHMARK OR MARK} AND (D
`
`121}SEA FILEFUSPAT LOAD BALANC? AND (BENCHMARK? OR.MARK?J AND
`
`43TBJSEA F1LE=USPAT TREE!3A}KSTRUCTUR? OR HIERARCH?)
`lalsaA SILE=USPAT L21 AND L32
`D)SEA FILE=USPAT LOAD‘BALANC? AND (BENCHMARK 0R MARK} AND (D
`
`5721515BA FILE=DSPAT (DOMAIN NAME SERVER! OR ONE} OR (BERKELEY I
`
`ISISER FILE-USPAT L35 AND REPLICA? AND OBJECT# AND LOAD(3AJRA
`
`2]SBA FILE=USPAT L36 AND (URL# AND IP{3A}ADDRESS?)
`2213BA FILE=USPAT REPLICA?(P(SERVSB1(P1OSJECT¢(B)NAME#
`
`dIDQIBB Rabinovich et. a].
`
`8
`
`
`
`”fl...”—
`Hanan-A
`
`“harp.
`
`L39
`L5
`L10
`L41
`L42
`L43
`L44
`
`L45
`L46
`L4?
`L45
`L49
`OR
`L50
`AC1
`L51
`ND
`L52
`AL
`L53
`IER
`L54
`OR
`L55
`CT
`L56
`IFF
`L5?
`(DI
`L58
`L59
`L60
`IFF
`L61
`NTE
`L62
`LAN
`L63
`L64
`L65
`LS
`L66
`L67
`L68
`L69
`L70
`L71
`L12
`
`L73
`L74
`L75
`L75
`L77
`H)
`L73
`L79
`L80
`EFF
`L81
`{UL
`L82
`L83
`L84
`IFF
`L35
`
`l!SEA
`
`FILE-USP?
`
`l71l5EA
`322PSEA
`32235EA
`41533
`1721dISEA
`
`FILE-USPAT
`FILE=USPAT
`EILE‘USPAT
`FILE=USPAT
`FILE=USPAT
`
`345/335/CCLS AND 395/200.33. 2f
`
`31, BBS/CC
`
`395/200.33,ZDD.31,335/CCLS
`345/335/CCLS 0R L40
`L41 0R L40
`142 AND L38
`LOAD(3A)[BALAEC? DR DISTRIBET? 0R ALLOCAT?}
`
`37ZBISEA
`645926)SER
`49BUB¢}SEA
`23521039EA
`ZDOZZJSEA
`
`PILE=USPAT
`FILE=USPBT
`FILE=USPAI
`FILE=USPAT
`FILE=USPRT
`
`MAXIMUM AND MINIMUM AND L44
`{THRESHOLD 0R ?MBRK?}
`L46 AND DIFFER?
`PLU=ON RELHON DIFFEE
`PLU=0N REL‘ON LOAD{33}(BBLBNC? OR ALLOCAT?
`
`ISSBZISEA
`
`FILE=USPAT
`
`PLU=DN
`
`REL=DN L49 AND (MAXIMUM LOAD OR CAP
`
`183655EA
`
`F1LE=USPAT
`
`ELUwON REL-0N L50 AND lDlEFER? 0R DELTA) A
`
`GJSEA
`
`F1LE=USPRT
`
`zaaysan
`
`FLLE=USPAT
`
`1421553
`
`FILE‘USPBT
`
`142JSEA
`
`FILE=USPAT
`
`ezysan
`
`F1LE=USPAT
`
`1271333
`
`FILE‘USPET
`
`PLU=0N REL=0N (({LOAD/EBIBA](BALANC?/AS OR
`
`PLU=0N RELHON L51 AND {TREE STRUCTURE 0R H
`
`PLU=ON RBLHON L53 AND {DIFFERENCE BETWEEN
`
`PLU=0N REL=DN L54 AND {APPLICATION OR OEJE
`
`LOAD BALANC? AND {BENCHMARK 0R MARK} AND {D
`
`LOAD HELENE? AND (BENCHMARK? OR MARK?) AND
`
`43TE}SEA
`1€ISEA
`CJSEA
`
`FILE=USPAT
`FILEHUSPRT
`FILE=USPAT
`
`TREEI3A}ISTRUCTUR? OR HIERARCH?)
`L57 AND L55
`LOAD BHLANC? AND {BENCHMARK 0R MARK} AND ID
`
`5721EJSEA
`
`FILE‘USPET
`
`[DOMAIN NAME SEBVERfi UR ENS) 0R [BERKELEY I
`
`lEJSEA
`
`FILE=USPAT
`
`:}SEA
`221533
`1:333
`
`FILE-USPRT
`FILE=DSPAT
`EILE=USPAT
`
`17]}SEA
`3221333
`322:5EA
`fl}SEA
`E)SEA
`IZZTJJSEA
`ITEIAJSEA
`
`aauassa
`410259}SER
`103)SEA
`IIJSEA
`2a531523
`
`FILE=USPAT
`EILE-USPAT
`FILE=USPAT
`FILE=USPAT
`FTLE=USPAT
`FTLE=USPAT
`FILEiUSPAT
`
`FILE=U5PRT
`FILE=USPAT
`FILE=USPAT
`FILE=USPAT
`FILEflUSPAT
`
`L61 AND REPLICA? AND OBJECTfl AND LDAD{33}BH
`
`L62 AND (uaLfi AND IPI3AIADDRESS?)
`REPLICA?{PjsERVEa#(P103JECT#:P}NAMEH
`345/335/CCL5 AND 395/200.33. 200.31, 335xcc
`
`395/200.33.200.31,335/CCLS
`345/335/CCLS DR L66
`L67 OR L66
`LEE AND L54
`4530264/PN
`LOBD(BA}[BALANC 03 015731307?)
`LOADI3A1(BALANC? 0R DISTRIBUT? on ALLOCAT?)
`
`MAXIMUM LORD AND MINIMUM LOAD
`DIFFER? AND lMARK? DR THRESHOLD?)
`L73 AND L74
`L15 AND L72
`DIFFERENCEISA}{BETWEEN(3R)MAKIMUM{BA)MINIMU
`
`3W}SER
`0158A
`62)SEA
`
`FILE=USPAT
`FILE-UBPAT
`F1LE=USPRT
`
`L77 AND L72
`HTT L73,
`1
`LOAD BBLRNC? AND [BENCHMARK OR MARK} AND [D
`
`12?}SEA
`
`PILE=USPAT
`
`4376)SEA
`16)5EA
`3}3EA
`
`FILE=USPAT
`FTLE=USPRT
`F1LE:USPAT
`
`LOAD BfiIflNC? AND (BENCHMARK? DR MARK?) AND
`
`TREEIBA}{STRUCTUR? 0R HIERARCH?)
`L31 AND L82
`LOAD BALANC? AND (BENCHMARK on MARK} AND (D
`
`57215;san
`
`FILE-USPAT
`
`[DOMAIN NAME SERVERfi 0R ENS} DR {BERKELEY I
`
`4/D9/99 Rabinovich at. al.
`
`9
`
`
`
`NTE
`L86
`
`L8?
`[.38
`1:8 9
`L3
`L90
`L91
`L92
`L93
`
`IBISEA
`
`FILE=USR
`
`LS5 AND REPLICA? AND OBJECT# A;
`
`.DADI3RIBA
`
`2}SEA
`22)saa
`liSEA
`
`FILE=USPAT
`FILE=USPAT
`FILE=USPAT
`
`L86 AND (URL? AND IP{3A]RDDRESS?1
`REPLICA?lP)SERVER#[PJOBJECT#IPJNAME#
`345/335/CCLS AND 395/20D.33. 200.31,
`
`335/CC
`
`171)SEA
`322}san
`3221533
`4133A
`
`FILE=USPBT
`ELLE=USPAT
`FILE=USPAT
`FILE=USPRT
`
`395/2DU.33.200.31,335/CCLS
`345/335/CCLS DR L90
`L91 OR L90
`L92 AND LEE
`
`“09/99 Rabinovich et. a1.
`
`10
`
`10
`
`
`
`Ulllted States Patent
`[19]
`|11| Patent Number:
`6,167,427
`
`Rahinovich at al.
`|45| Date ril' Patent:
`Dec. 26, 2000
`
`
`
`USUUG I 67427A
`
`[S4] REPLICATION SERVICE SYSTEM AND
`METHOD FOR DIRECTING THE
`REPLICA'I‘ION 01" INFORMATION SERVERS
`
`293531;“: SJREEECTED PLURMJTY OF
`Inventors:
`Irina Rablnuvich; Michael
`Rahinm'ich. hulh [ll-Gillcllc‘ NJ.
`
`|75]
`
`|73] Air-igncc: Lucen! Tochnnlugies Inc. Murray Hill,
`NJ
`
`[51]
`a
`'5‘]
`53
`I‘
`1
`
`.
`1
`I'll AWL NU" “81979.6“
`|22
`Filer]:
`Nov. 23, 1997
`
`Int. CI.T
`GflfiF 15/lfi; Gllfil’ 15mm
`'
`‘
`-
`1
`-
`7
`>
`
`“'5' (.I.
`769'7l‘i'Egg/£1011}jiggigdjiififillé
`
`F. Id f S
`r— =
`h
`r- x ,
`7091,03 €211
`In
`0 W731i) 1013,17 L;"8"119f;31' 373'
`WELZ'Q 71;: ‘71 : 31 El“ 011;;
`, 365’
`“ ' “ ‘ "' '
`‘ “' 6‘ ”4'
`’ 7 7' “ ’4' ”106
`“
`.
`‘
`.
`Reterenm-s Cited
`US PNI‘ENF DOCUMENTS
`
`_
`4 07
`170
`mun C
`I
`(“$382 lif'ifmri Aillria ii] 304;:
`
`{$814} ”1.1%“ My“; cilia-l"-
`'mw’l
`limos VD" Dyke 21 i1].
`395]“;
`EEDBZSQ
`71mm
`5.745.fits3
`4mm Lee 61 al.
`
`SUSMJILSS
`5.774.008
`UHWB Choquicr
`
`[56]
`
`
`7075201
`7!!”‘13 Hitchericl all
`.
`5381442
`
` §KQZJU “119.93 Pena; at all 3952mm;
`
`5.923.837
`711999 Matias .....
`714:2.5
`
`OTHER PUBLICATIONS
`Microsol'l Press Compmcr Dicliunur‘y. 3rd. Ed., Microsoll
`Press. Sup. [997.
`[mad balancing slralcgy [in
`liamngariner cl all Glnhal
`distributed uumpuler syslcm. IEliL. Jul. 1983.
`Dandamudi mi all, A hierarchical
`load sharing policy i'ur
`disln'hulch systems, IEEE, Sap 1997.
`.
`Primrrrr' El‘fi'rlll'rler—LE. [lion Luu
`Assiflmir Exmnfrwr—Bcalriz Priclrn
`Armrrrqv. Agerrr. or Firm—William Ryan
`
`ABSTRACT
`[57l
`A syslern an mclhud I'ur clficicnlly providing accuse; by a
`larg: number ul' cliunls [u nhjecls Inualed al a large [llllTli‘lflf
`of infomaLion servers. A nun—lmlllcncck snlulinu is pm-
`Vided [0 sharing load among servers by migraling or repli—
`caring uljjccls over from highly loaded servers Lu 1:55 highly
`Iaadcd servers. Ulnjculs lhal cxperiencu low loading are
`deleted to make room [or more highly used rabjccls and lo
`perrrlil make space for new uhjccts. A naming service is
`provided lo provide rapid access to a replica of a rcqucslcd
`nhjccls, while avoiding directing access rcqucsm Iu servers
`from Which replicas nl'requcsled cshjecls have been dcleled.
`Hierarchical ordering of replication and naming [auctions
`pcmlilsu variety (ifpurlicular access rncllmds In he realized,
`13 Claims, 5 meing Sheets
`
`l'lll
`
`< urcrw: LDAD Irrorumo—u >
`I
`5702
`BETERH‘NE SM“. SHIN
`
`l
`
`
`
`
`
`ID!
`ETD-l
`SEMI} OFFLGAD TD
` NO
`lOADMnXSHIX * LOADM|N,5HIN Dd ?
`WALSH“
`
`_
`m5
`5m mmnonrr
`
`70mm uses
`nrrrnumc ma
`r
`LL70“
`
`
`
`, m
`OFFLDAD MSG SEN] ?
`loaquxfi = |Dudm|hfi=u~LuudR
`
`
`ND
`
` find S'mor S'min such rhur
`lmdmalrs'mur = maxi=hn(bul
`i noi=$muh5min Lmdmar‘si
`inadninfi’vrin
`
`miiié'lmiiwl
`l nol = Emir-Samar lunar-mm
`prrmfi Z pnurfi‘mu]
`pmin,R = = pmin,$'min
`
`
`
` (712
`lusdmuxfi = luuflmnermm:
`\audminjl : Icnflan.Smln'
`amoxrfl : Dmulrfi : pmu:,5mnx;
`pminfi : pminjm‘m
`Jill
`sum gram TO Harm]
`
`
`
`J7]!
`srrn mom 1o mew |
`
`11
`
`11
`
`
`
`US. Patent
`
`Dec. 26, 2000
`
`Sheet 1 MS
`
`6,167,427
`
`FIG.
`
`1
`
`
`
`REPLICATOR
`
`12
`
`12
`
`
`
`US. Patent
`
`Dec. 26,2000
`
`Sheet 2 of5
`
`6,167,427
`
`FIG.
`
`3 1
`
`3
`
`13
`
`
`
`US. Patent
`
`Dec. 26,2000
`
`Sheet 3 of5
`
`6,167,427
`
`FIG.
`
`5
`
`500
`
`501
`
`READ LOAD FROM
`SUBORDINATE SERVERS
`
`502
`
`MORE SERVERS ?
`
`
`
`
`
`
`PASS LOW AND HIGH LOADS5
`
`TO HIGHER SERVER
`
`SOS
`
`504
`
`MSGS TO HIGH AND SERVERS
`TO PERFORM DISTRIBUTION EVENT
`
`
`
`FIG.
`
`6'
`
`500
`
`READ LOAD FROM
`
`SUBORDINATE SERVERS
`
`
`
`MORE SERVERS ?
`
`
`
`
`'5':
`
`EDS
`
`MSGS TO SUBORDINATE
`ROOT SERVER ?
`YES
`HIGH AND LOW SERVERS
`
`
`TO PERFORM DIST EVENT
`
`EOE
`MSGS TO SUBDRDINATE
`
`
`HIGH AND LOW HOSTING SETS
`
`
`TO PERFORM DIST EVENT
`
`PASS LOW AND HIGH LOADS
`
`
`O HIGHER SERVER
`
`
`14
`
`14
`
`
`
`US. Patent
`
`Dec. 26,2000
`
`Sheet 4 of5
`
`6,167,427
`
`FIG.
`
`7
`
`70
`
`1
`
`RECEIVE LOAD INFORMATION
`
`7
`
`02
`
`DETERMINE SMAX, SHIN
`
`_
`
`SEND OFFLOAD TO
`
`PMAX,SMAX
`LOADMAXSMAX
`LOADMINSMIN >d ?
`
`SEND ADDITIONAL
`
`OFFLOAD MSGS
`
`705
`
`
`
`707
`-NO
`YES
`
`@710
`
`705
`DETERMINE nvLoad
`
`
`[703 YES
`
`loodmaxfi = |oadmin,R=uvLoadR
`
`I711
`
`Find S'max S'm'ln such that
`
`709
`
`"0
`
`I noI=Smux.Smin)(Loadmnx.Si)
`loadmax,5’mux = maxi=1.n(bul
`loadmin,5’min = mixI=1,n(buI '| n01 = Smin,Smux(loudmIn,5i)
`pmuxfi = pmux,5’mux
`
`pmin,R : = pmin.S'mIn
`
`712
`
`|asdmax,R = loudmax,3mux;
`loadrnl'n,R = loadmin,5min'
`pmux,R : pmux,R = pmox,3max;
`
`pmin,R = pmin,Smin
`SEND REPORT TO PARENT
`
`713
`
`714
`
`SEND REPORT TO PARENT
`
`15
`
`15
`
`
`
`
`
`
`
`
`
`REDIRECTOR DELETES THE HOST
`
`FROM REPLICA SET, RESPONDS
`WITH RESOLVED_CNT(Xp)
`
`RESOLVED_CNT = SATISFIED_CNT ?
`
`US. Patent
`
`Dec. 26, 2000
`
`Sheet 5 MS
`
`6,167,427
`
`FIG.
`
`8
`
`801
`
`802
`
`HOST SENDS DELETEREPLOO
`T0 REDIRECTOR
`
`805
`
`
`
`WAIT
`
`
`
`NO
`
`YES
`
`005
`
`
`
`p DELETES X
`
`
`
`807
`
`
`
`16
`
`16
`
`
`
`6,167,427
`
`2
`the less-loaded server
`a certain distribution threshold d,
`would obtain some replicas of objects kept on the higher—
`loaded server, thus taking up a portion ofits load. Due to the
`randomness of choice, all pairs of servers would be
`involved. An approach similar to this is presented in “Adap-
`tive load sharing in homogeneous distributed systems," by T.
`L. Casavant and J, G. Kuhl, IEEE Traits. on .S‘oflware Eng,
`vol. 2(14), pp, 1414154, Feb. 1988. The Casavant, et a]
`paper also delines a threshold for which nodes with a load
`below the threshold are constrained to not
`initiate load
`comparison.
`However, as the number of servers grows, each server
`must initiate load comparison more frequently. Otherwise,
`the average time between load distribution events for any
`given pair of nodes will grow linearly with the number of
`nodes, as will the lag between load changes and detection of
`these changes. Since a server has a limit on how frequently
`it can perform load distribution, this solution is not scalable
`[0 large systems.
`Aflother approach is to Organize hosting servers in a
`connected graph structure, with neighboring nodes perform-
`ing pair-wise load distribution. Since the graph is connected
`the load distribution involves all servers. This technique is
`similar to an algorithm described in “Simulations of three
`adaptive, decentralized controlled,
`job scheduling
`algorithms,” by J. A. Stankovic, Computer Network; 8, pp.
`199-217, August .1984, One dilferenee is that in the Stank—
`ovic paper, when a node sends its load data to a neighbor, it
`includes its information about all other nodes. These tech—
`niques also prove to not be scalable as required for large
`networks.
`Another important consideration in establishing a global
`or other large information system is that of a naming service
`for objects and servers. In general, naming services are used
`to map a logiCal name of an object into the physical name of
`a replica. The main limiting factors for the name service are
`the number of clients (which determines the number of
`requests for name resolution), and the number of objects
`(which determines the size of the name~mapping database).
`Another factor is the number of requests from hosting
`servers for updates of name mappings:
`Name services are well known in the art, including the
`Domain Name Service (DNS) used in today‘s Internet and
`described, c.g.,
`in P. V. Mockapetris, "Domain Names#
`Concepts and Facilities," Request
`for Comments 1034,
`DDN Network Information Center, SRI
`International,
`November, 1987. Also used in Internet naming is CCITI'
`(now ITU) Recommendation X500.
`However, mappings between host name and [P address
`seldom change in the DNS scheme. Rather, DNS is prima-
`rily an append-only database that permits the addition of
`new host name/1P address mappings; current DNS imple—
`mentations support little or no dynamic mapping of host
`name to IP address.
`Using current DNS naming service techniques to map
`logical object names to physical replicas, name server
`responses cached by clients become incorrect much more
`quickly. Thus, clients must query the name service much
`more often, greatly increasing the burden on the name
`service. Weak-consistency schemes for replicating the map-
`ping database such as that described in B. W. [.arnpson,
`"Designing a global name service," Prue. ofACM Confi on
`Princtpics of Distributed Simeon. ppl~10, 1986 result in
`many incorrect
`responses to clients. These incorrect
`responses result in the use of an incorrect physical name to
`access an object—With resulting failure and qucht renewal.
`
`1
`REPLICATION SERVICE SYSTEM AND
`METHOD FOR DIRECTING THE
`REPLICA'I‘ION OI" INFORMATION SERVERS
`BASED ON SELECTED PLURALITY OF
`SERVERS LOAD
`FIELD OF THE INVENTION
`
`invention relates generally to tile field of
`The present
`distributed information systems. More particularly,
`the
`present invention relates,
`in one aspect, to SelectiVe repli-
`cation and distribution of data objects and services between
`and among a plurality ol‘ information systems. Still more
`particularly, aspects of the present invention relate to dis
`tributed systems and methods for efficient provisioning of
`objects and services to clients in large (including global)
`networks
`BACKGROUND OF THE INVENTION
`
`Ut
`
`It)
`
`IS
`
`2t)
`
`30
`
`40
`
`45
`
`As networked computers and databases, and users of
`these systems, have proliferated in numbers and geographic
`spread. interest has grown in efliciently providing access to
`information objects and services (hereinafter “objects") at
`host computers or information servers. Presently,
`for
`example, thousands of Internet servers provide a very large
`number of objects to millions of User clients worldwide ‘
`These servers are located in many countries around the
`world and typically at many locations in each country. In
`other particular cases, network service providers and private
`corporations locate server nodes at widely separated points
`in their networls.
`A particular challenge laced by developers of these net-
`wrtrks of servers is that of providing access to a widely
`distributcd set of clients without overloading particular
`hosts. The overload may occur, eg. because a server stores
`objects that are in high demand and/or the server is a
`repository [or large numbers of objects. Meeting this chal-
`lenge proves especially diflicult when the demand for par—
`ticular objects varies considerably with time. Thus, while a
`straightforward replication of all objects at all servers would
`generally improve availability of a particular object to a
`range 01’ clients, the cost of such replication is prohibitiVe. In
`fact, the economics of replication, distribution and storage
`do not usually permit design for a worstrcase predicted
`demand condition in such large network;
`The load on each server is an important consideration in
`adequately meeting demand from clients for objects;
`in
`general, it is desirable to balance the load among servers. In
`many existing replicated object systems, with relatively few
`servers, this question is quite tractable: system administrate
`tors or a dedicated computer system process can monitor the
`load of servers and decide on selective replica placementl
`When the number of servers increases, however, such
`human or dedicated process cannot be expected to efficiently
`direct the creation and deletion of replicas.
`Current object-location techniques used in distributed
`server netwmks assume that sets of object replicas are well
`known to clients, However, when the number and geo—
`graphic distribution of servers increases to dense national
`and international proportions this assumption proves unre—
`alistic;
`the ability or clients to efficiently locate desired
`objects at servers increases markedly.
`One possible solution to the scalability problem of the
`replication service would be to use a localized "greedy"
`approach. For example, each hosting server might choose
`another hosting server at random, and perform load com-
`parisons with this other sch/err lithe load difference exceeds
`
`St]
`
`55
`
`tit]
`
`65
`
`17
`
`17
`
`
`
`6,167,427
`
`3
`Wurld—Wide—Web (Web) syntax and semantics for object
`names (URLs) are quite dili’erent from those in DNS or
`X500. Use of DNS or XSOO-compliant symbolic names in
`networks Like the Web would require extensive changes in
`Web browsers.
`
`m
`
`SUMMARY OF THE INVENTION
`
`4
`FIG. 7 is a flowchart [or a preferred illustrative load
`balancing arrangement.
`FIG. 8 is a flowchart showing an illustrative method for
`deleting a replica.
`DE’I‘AILED DESCRIPTION
`Illustrative System Overview
`FIG. 1 shows an illustrative application of the present
`invention. There, a wide area network [00 comprises a large
`number of servers 140-1} i-I, 2,
`.
`.
`. M and clients 110-},
`j=l,2, .
`.
`A N. Servers 140-1' host objects publicly accessible
`to clients 110—}. A node may play a dual role as a server for
`some objects and a client for other objects.
`Clients access objects by their names. The name of an
`object alIOWS a client to infer the identity of hosting server
`(cg, its domain name or IP address) and access method (i.e.,
`the protocol to be used to access the server). For illustrative
`purposes, it will be assumed that object names embed a
`domain name of the server that hosts the object. One
`instance of this environment
`is the Internet, which
`comprises, inter alia, Web servers and Web browsers. Such
`servers typically include computers and related equipment
`for controlling (often very large) databases, while browsers
`are typically associated with client ICrruinals or (usually
`smaller) computers, all as is well known in the art.
`The network of FIG.
`1 is a network of information
`systems, where objects provide access to information. and
`thus do not change as a result of an access by a client.
`Ilowever, an access may result in extensive processing by
`the server to compute the result of the client's query. For
`example, in a geographical database, a request for the map
`of a specified area in a specified scale may require genera
`tion of line map, which typically is an expensive operation in
`terms of server resources.
`A load measure exists for each server 1404‘ in FIG. 1 to
`allow comparison of load on each server. For example, when
`the servers operate using the UNIX operating system, the
`length of the input queue (as measured. e.g., by the output
`of the uptime command) proves to be convenient for this
`purpose. In other particular environments. other measures of
`load may be preferable.
`In addition, each individual server can estimate the frac-
`tion of its total load due to a given object on the servert In
`typical operation this is accomplished by monitoring
`resource consumption (cg, CPU time, 10 operations, etc.)
`due to requests for individual objects and dividing up the
`total load between objects in proportion to their consump-
`tion. While the illustrative scrvel‘s 140 in FIG. 1 may be
`quite dilfcrent in total system resources, a server with an
`average queue length of 1.5 is more heavily loaded than a
`server with an average queue length of 0.8, regardless of the
`quantity of processing needed at each server to achieve these
`queue lengths
`In achieving purposes of the present invention, the illus—
`trative embodiment of FIG.
`1 provides for replicating an
`object located on a particular server, say server p, on another
`serVer, server q. Alternatively an object may be migrated
`from server p to server qr it” will denote a replication of
`object it: on server p. Ioad(p) denotes the load of node p, and
`load(px) denotes the load on node p due to object
`it.
`In
`general, if x is migrated from node p to node q, the reduction
`of load on p may not be equal to the increase of load on q,
`due to difl'erenee in processing power of p and q.
`Typically,
`there are two ways by which a system can
`balance the load: directing client requests to less loaded
`servers (among those with replicas of the requested object),
`and migrating or replicating objects betwacn servers Server
`
`It)
`
`15
`
`30
`
`limitations of the prior art are overcome and a technical
`advance is made in accordance with the present invention
`described in illustrative embodiments herein.
`In one illustrative embodiment. a method is described for
`achieving the number and placement of object replicas in a
`network of seerrs. This result is achieved without the need
`for bottleneck—causing global decisions. Using the present
`inventive methods and resulting network, a server network
`is realized in which creation and deletion of replicas is
`minimized when a steady demand [or all objects persisLs for
`an appropriate period of time. Moreover, when such steady
`demand exists the load can be distributed among servers in
`a substantially equal manner.
`In accordance with an illustrative embodiment, the deci~
`sion on lhe number and placement of replicas is made within
`the network. Moreover, the process is dynamic, with replicas
`being created and deleted as demand and geographic origins v
`of requests change. The illustrative replication is advanta—
`geously transparent to end—user clients, except in improved
`network response.
`the illustrative
`In accordance with an aspect of
`embodiment, no high demand bottlenecks arise which might
`require an increase of processing power at any node. Rather,
`as load increases, the number of nodes can be increased to
`handle the increased demand. This result obtains whether the
`high demand is based on the number of clients requesting
`objects increases, or whether the demand arises from an
`increase in the number of objects.
`In accordance with one aspect of the present invention, a
`new naming service is introduced for finding object replicas.
`Advantagenusly, the existing DNS name services can be
`used as a first level of indirection in the new naming service.
`In other particular contexts, such as when the character-
`istics of languages for specifying object content or when
`certain network protocols are used, the illustrative inventive
`techniques, or their application, may be modified as required
`to achieve desired results.
`
`40
`
`45
`
`BRIEF DESCRIPTION OF THE DRAWING
`
`The above—summarized description of illustrative
`embodiments of the present invention will be more fully
`understood upon a consideration of the following detailed
`description and the attached drawing, wherein:
`FIG. 1 is an overall view of an illustrative network system
`embodiment of the present invention.
`FIG. 2 shows a replication service arrangement compris—
`ing a hierarchy of replicators for use in the network of FIG.
`1.
`
`FIG. 3 shows an application of the replication service
`arrangement of FIG. 2.
`FIG. 4 shows a naming service arrangement for use in the
`system of FIG. 1.
`FIG. 5 is a flowchart illustrating a load balancing system
`and method in accordance with one embodiment of the
`present invention.
`I-‘l (i. 6 is. a [botched for a modified Version of the system
`and method of FIG 5.
`
`til]
`
`65
`
`18
`
`18
`
`
`
`6,167,427
`
`6
`it resolves into the name
`identifies the object. However,
`service irlentity rather than the identity ofthe server hosting
`the object.
`The symbolic name is advertised to the users; it is the
`name known to the clients. When a client wants to access the
`object, it uses its symbolic name, Since this name resolves
`into the name service identity,
`the request for the object
`actually arrives at the name service 120 as shown by the link
`between typical client 110-1 and name service 120. Name
`server 1.20 finds a corresponding physical name (due to
`replication, a symbolic name can map into multiple physical
`names) and sends it as a special "re-direct“ response to the
`client. The client, such as 110-1 in FIG. 1 then uses the
`physical name received to access the object at the identified
`Server, such as 140-1 in FlGi 1t
`Asynchronously, hosting servers periodically report their
`load to the replication service unit 130. The replication
`service 130 uses these reports to migrate or replicate objects
`so that the load is shared among all hosting servers, and
`replicas are placed close to a majority of requests for the
`corresponding objects.
`When a hosting server 1401' creates or drops a replica of
`an object. it records this fact at the name service 1241111115,
`the name service keeps a mapping of the symbolic name of
`an object to a set of physical names of curremly available
`replicas, When resolving a symbolic name, the name service
`chooses one of the current set of physical names, applying
`a fair procedure and taking into account the geographical
`location of the requesting client.
`The Replication Service
`One potential bottleneck in the system of FIG. 1 is the
`replication service. Indeed, as the number of hosting servers
`and hosted objects increases, the number at toad reports the
`replication service must process grows, and so does the
`search space for deciding on replica placement. This section
`describes a scalable distributed architecture for the replica—
`tion service 130. Scalability is of interest
`to the present
`discussion because important target networks are assumed to
`be large.
`The following description of a policy for replica place
`ment
`is based on the objective of load distribution. A
`challenge in designing such a policy is that the policy must
`ensure globally desirable system behavior (according to
`criteria such as the stabilizing and oontiguity criteria dis-
`cussed above) without creating any bottleneck—producing
`global decision points. Those skilled in the art will develop
`other detailed policies and heuristics Within the scope of the
`presently described architecture and infrastructure.
`An illustrative structure for the replication service 130 of
`FIG. 1 is shown in FIG. 2. There,
`it will be seen that
`replication service 130 comprises a hierarchy of replieator
`servers. Each replicator server in FIG. 2 comprises standard
`network computer functionality, including a central process-
`ing unit, main and auxiliary memory and inputfoutput
`facilities, all arranged to receive information from informa—
`tion servers and other rcplicators to perform,
`inter alia,
`analyses of load il'lliDlTnalion, and to generate control mes-
`sages relating to these analyses and to creation and deletion
`of object replicas. The highest level replicator is at node 210
`and replicators 2203i appear at nodes directly below node
`210‘ Only two levels are shown explicitly in the hierarchy of
`FIG 2, but other levels of replicators will appear as required
`for particular networks at respective nodes at other levels in
`the hierarchy. For very large networks, the level of such
`nodes may extend over many such levels in a hierarchy.
`Direct descendants of a node in the hierarchy ot‘ replicators
`in ”CL 2 are referred to as subordinates. For a server 5, let
`
`or
`
`it)
`
`IS
`
`30
`
`40
`
`45
`
`5
`selection for a particular client request is typically based on
`the geographic origin of the request (i.e., the closest replica
`is chosen), but
`the selection may be based on another
`criterion, or at
`random. Thus,
`the load,
`is illustratively
`balanced by replication or migration of objects. The client 01"
`migrating an object [rum server [I to server i], or creating a
`new replica of an object on L] by copying it from pl is called
`a distribution event. Servers p and
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ ChargeStill Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site