United States Patent [191
`
`[11] Patent Number:
`5,341,477
`
` Pitkin et a]. [45] Date cf Patent: Aug. 23, 1994
`
`
`||||||||||||||||||||i|l|||||||||||||l|||||||||||||i||||||llilllliliillllll
`
`usmssimm
`
`[54] BROKER FDR COMPUTER NE'IWOBI
`SERVER SELECTION
`_
`_
`Inventors: Rachard P. Min, Lowe"; John P.
`Meme-v, Chelmsfcrd, both of Mass.
`
`[15]
`
`lifl9‘fl9 Samuelson ......................... 364K191
`4.353.121}
`4,391,131 mm Chang et ai.
`364x209
`4,914.51]
`112’1990 Brat: ctel. ................. SHEDIG. 1
`emcee mayo Cue .................................... 345mm
`3,005,111 4H9“ Griflin er. a].
`364x209
`
`['33] Assignee: Digital Equipment Dalmatian,
`Maynard, Mass.
`
`Primer}: Bummer—Eddie P. Chen
`Attorney, Agent, or wwwn Sc Kenyon
`
`[2!] Appl. Ne: 1113,72:
`
`[3?]
`
`ABSTRACI‘
`
`[22] Filed:
`
`Aug. 6, 1993
`
`[63]
`
`In a eemputer netwerk, a broker mechanism allocates s
`plurality of servers. each having an available resource
`capacity, Le a plurality cf clients for delivering one of
`Related [1.5. Application Date
`5599531 513% 10 the clienfi- The broker 09mm hat
`Continuation cf Ser. No. 924.390. Aug. 3. 1992, Ihen-
`mum-urine a subset of all available servers capable of
`dulled. which is e ecnt'meticn cf Sect. Ne. 314,353.
`delivering the requested service. The leccuticn is based
`Feb. 24. 1939. abandoned.
`”'1 51’9“” ‘1' .“E‘wmk ““5”? f” "1“- P‘mfiw “f
`Int. cu ....................... GHEF tame; GUfiF lfiflfi
`[51]
`“m” it “flew 3 ““1 P011“? far PM“ 0““ W‘
`[52] us. ca. .................................... sssrzcu; assess;
`BIS. The: WERE-T receives CIJfll-I Ifiq'flfifi III}: the WES
`364E113. 1: 3E4f231j; SHIZMA; 364K264;
`364mm and based 0n the network pciscy and available resource
`[53] Fieitloffieareh ........................ 395m. 325. 1'25
`09139“!!! SW15 WE 0f the servers, monitors in 1135
`[56]
`Ret
`{flied
`subset fur that particular service, to one cf the clients
`making a request. The server suggested enforces its
`13.3. PATENT DDCU MENTS
`local policy by not efluwing any connections exceeding
`4,751.35?
`72"]?35 Riskin .....
`its. available resnurce capacity.
`4.130.321 WINES Crowley ..........
`4;“.453 ”1939 Agrswel etai.
`
`354m
`
`379K“?!
`nweca
`
`24 animus, 19 Drawing Sheets
`
`I
`
`IIIlIIIIII
`
`__1____I__
`
`'I‘
`
`II...___ I
`
`'—
`
`I I I I_-I'
`
`EE. E5
`
`Page 1 cf 19
`
`LG Electronics Exhibit 1015
`
`

`

`US. Patent
`
`Aug. 23, 1994
`
`Sheet 1 of II]
`
`5,341,477
`
`E3255
`
`
`
`
`
`llllllllllllllllllllllllllllllllllllllllllllllllllll
`
`Page 2 of 19
`
`
`
`
`

`

`US. Patent
`
`Aug. 23, 1994
`
`Sheet 2 01" 1:)
`
`5,341,477
`
`44
`
`#2
`
`33
`
`m H
`
`a
`
`Lu
`w—i
`
`P-Lr':
`1-11"!
`
`m'fi‘
`‘41-!
`
`m
`W-‘fl
`
`N
`Iq—I
`
`2
`
`LD-
`
`a
`
`"If
`U
`
`W
`
`1—!
`
`lb!-
`W
`
`[In
`W
`
`[‘3
`
`1r
`W
`
`P!
`N
`
`N
`ru
`
`E
`
`Ci
`
`I d
`
`t
`;n:_C|".l
`
`I'LI
`
`{E
`
`m
`
`N
`
`.:=.=.
`(9“
`H
`
`it
`H
`-Q:
`
`CU1|:
`w-i
`.q;
`
`w—IL'U.
`
`{I
`
`“Fl
`
`{I
`
`Page 3 of 19
`
`

`

`U.S. Patent
`
`Aug. 23, 1994
`
`Sheet 3 of 10
`
`5,341,477
`
`Em
`
`N-d:
`LIJu
`:I-
`
`Page 4 of 19
`
`

`

`U.S. Patent
`
`Aug. 23, 195:4
`
`Sheet 4 of 10
`
`5,341,477
`
`FIG. 3
`
`SERVER
`PAHIHETEHS
`
` SERVICE
`CHARACTERISTICS
`REQUIRED PER SERVICE
`
`
`
`
`
` VARV THE
`
`PARAMETERS DF THE
`SERVER ANDIDR THE
`
`SERVICES
`
`
`
`CAPABILITV DE SERVER
`TD DELIVER SERVICE
`
`DDES CAFARILITV
`HATCH INTENDED
`PDLICV?
`
`
`
`
`
` STDRE
`
`LDCAL FDLICV
`
`IN NAHE SERVICE
`
`
`INPUT NEAT SERVER
`'
`AND REPEAT
`
`Page 5 of 19
`
`
`
`
`
`lS SERVER LIST
`CDHPLETED?
`
`
`
`
`
`CDLLECT LDCAL
`RDLICIES FDH
`NETNDRN PDLICV
`
`
`
`
`
`ASSIGN SCAN HEIGHT
`RATID DE SERVERS
`TD DVERALL_RDLICV
`
`
`
`
`

`

`1.1.5. Patent
`
`Aug. 23, 1994
`
`Sheet 5 of 111
`
`5,341,477
`
`£23.28Em:d
`
`@:.@@@@®@®@®@
`
`Page 6 of 19
`
`
`

`

`US. Patent
`
`Aug. 23, 1994
`
`Sheet 6 of II]
`
`5,341,477
`
`mmmrmmmflE...$m
`
`mémega
`
`T.“B_Emm
`
`E:z:
`
`«2H:
`
`taqacuEma
`
`m-m5min;
`
`:53553.5
`
`Tm”@152
`
`
`
`SEEK.EEG
`
`m-“mei
`
`25:5EEG
`
`T“59.5:
`
`Page I" of 19
`
`
`
`

`

`US. Patent
`
`Aug. 23, 1994
`
`Sheet T of 10
`
`5,341,477
`
`“NH
`
`WHH
`
`m“
`
`mfi—
`
`h
`
`m
`
`m
`
`ma"
`
`hzm_gu
`
`m-Hhogm
`
`pzmh4u
`
`w-“HaAm
`
`ma“
`
`mafi
`
`p=m_4u
`
`fi-wha4m
`
`Ham—Au
`
`m-wp=4m
`
`(m.wHu
`
`mmurmwm
`
`wmmamwm
`
`
`
`
`m-¢muhhmmm
`
`H-¢muHhmmm
`
`mlmmu_:¢mm
`
`“-1mafiammm
`
`an“
`
`ma“
`
`NQH
`
`“a“
`
`Page 3 of 19
`
`
`
`
`
`

`

`US. Patent
`
`Aug. 23, 1994
`
`Sheet a of 19
`
`5,341,477
`
`FIG. 5
`
`
`EET SERVIEE HARE
`FRUH DIRECTURV
`
`
`
`
`STARTUP EUNHEBTIUHS T9
`SERVERS FUR HINDU!
`UF EAEH SERVICE
`
`
`
`
`BET SERVICE HARE IHFURHATIUH
`IVIHUUH SIZE. UTHER hTTHIBUTESI
`
`
`
`
`ALLUEATE DATA STRUCTURE FUR
`HARE. HIHUUVS. LUEATIUHS
`
`
`
`
`
`
`SET SERVERS
`IHFURHATIUN
`
`
`
`
`
`ALLUEATE DATA STRUCTURE FUR SERVER
`HARE. PULIEV. SEAN HEIGHT
`FILL IN VALUES FRUH LUEATIUH IHFRUHATIUH
`
`Page 9 of 19
`
`

`

`US. Patent
`
`Aug. 23, 1994
`
`Sheet 9 of 111
`
`5,341,477
`
`RECEIVE MESSAGES IIITH
`SERVICE NAME FFIDH CLIENT
`
`nu
`
`
`DflES SERVICE
`LIST 5x151?
`
`
`
`
`TEE
`
`f=TIIEi.
`
`liifll
`
`
`
`
`
`FOUND NINE
`IN BERNICE
`NAME LIST?
`
`
`
`TES
`
`BET mp
`ENTHV
`
`
`
`HINDflH
`HA5 ENTRIES?
`
`
`
`BET F'IEIILIC‘Ir
`INFDFHATIEIN
`
`
`
`
`
`HDVE TDP HII'IIIH
`POINTER IIIHN
`EHDVE CDNNECTIDN
`ID SERVER
`DECREASE HIMJDH SIZE
`
`
`
`
`
`
`
`PDLICY LIHIT
`HEACHED?
`
`
`HDVE TCP HINDDH
`
`
`FEHJND ENTFITIr
`PDIHTEH [D‘n'N
`
`
`
`SCAN HEIGHT
`TEHPDRAFI‘I' HAHN IN USE
`REHflIfE CDNNECTIDN
`
`
`
`
`ZEHD?
`DECREASE SCAN HEIGHT
`TD SEFWEFT
`
`
`
`DECFEASE HIIDJH SIZE
`
`
`
`
`
`
`
`
`SEND HESSAEE HlTH
`EFlFTDFI TD CLIENT
`
`SEND MESSAGE |NITH
`ENTFlIr
`ID CLIENT
`
`
`
`FILL HINDDH IF NEEDED
`
`Page 1Dof19
`
`

`

`US. Patent
`
`Aug. 23, 1994
`
`Sheet 1a of 10
`
`5,341,“?
`
`IG.
`
`7 F
`
`Page11of19
`
`

`

`1
`
`5,341.47”
`
`2
`aefiou. This grouping of servers can be seen as a "net.
`work service”. To overcome shortcomings of the prior
`artanidcnlsyatemforaclicnttorequestasen'ioeina
`complex network should fulfill two requirements. First.
`the request must include generic accessing ofa particu-
`lar network Service name to provide a higher level
`interface abstraction than the current practice where
`each client knows of all server possibilities. This has the
`advantage of substantially simplifying the decin'on pro-
`cem for the client in the case where multiple servers can
`deliver the requested service. The only requirement is
`the network service name rather than the name ofcach
`and even; server offering the requested service. Sec-
`ond, the requested service must be guaranteed to exist
`for the client within the server for the duration of a
`connection.
`To supply a service to a client. it is known to use a
`broker mechanism coupled to the network for schedul-
`ing a server to a requesting client. The broker receives
`a request for atoms to a service from a client and trans-
`mits to the client the name ofa server which can deliver
`
`the service to the client. One known type of broker
`operates by assigning an entire server to a client irre-
`spective of the capacity needed by the client.
`a problem with the above broker method is the inef‘
`ficient use of network resources. Prior brokers must
`continuously monitor all of the setters coupled to the
`network. increashig the brokers overhead and the net—
`work traffic. Because the resource capacities of the
`servers and the necessary performance level to be allo-
`cated to the client are dynamic factors. a broker mecha-
`nism which can dynanueally allocate servers to clients
`using a predetermined policy is needed.
`
`SUhIh'LARY OF THE INVENTION
`
`BROKER FOB. cosmonaut NEI'WDRK SERVER
`SELECTION
`
`S
`
`Ill
`
`15
`
`EU
`
`This is a oondnuntiou of application Ser. No.
`DTI‘QN-Jl-lll, filed Aug. 3. 1992, abandoned. which in
`turn is
`a
`coutinuation of application Ser. No.
`mifillliiififl, filed Feb. 24. ”'39 1:an abandoned.
`
`FIELD OF THE INVENTION
`
`This invention relates generally to the allocation of
`resources within a computer network architecture and,
`more particularly. to the use of a broker mechanism
`which responds to a client‘s or end user's request for
`some service and suggests a server to the client capable
`of supplying the requested service.
`
`BACKGRGUND OF THE IM'ENTIUN
`
`Present day computer network architectures have
`bucornc more and more complex. For example. a net.
`work may comprise multiple deviom. such as several
`computer systems, terminals, periphemls. etc.. all linked
`together in order to exchange information and share
`resources.
`
`Other more complex networks may comprise thou-
`sands of devicm of varying technical capabilities. In
`many applications, bod-1 local area networks We)
`and wide area networks {WAKE} are connected to form
`parts of a single network. For example. a network can
`include a local area component, a wide area component
`and a component involving connnunication between
`computes of different vendors, such as a mold-vendor
`communication network.
`
`The process for designing computer networks of this
`type involves a complex analysis of the customer re-
`quirements. the price factor for the various products.
`the necessary communication lines. and other technical
`and business considerations The allocation and planned
`use of the various resources to support the network
`noedsisnowpartofthe normalcapecityplanningoycle
`done by a network manager when setting up the net-
`work for a customer.
`
`35
`
`till
`
`The present invention is a broker mefltod. and appara-
`tus which. on one hand monitors the dynamic status of
`a set of servers and. on the other hand. responds to
`requestsfrom accessingclientsconcerning whichmem-
`ber of that server set is capable of providing the re-
`quested. service
`The service linutations for the requested service are
`preferably established as a matter of policy during the
`network design and modelling process by a system or
`network manager. Based upon the policy. the broker
`thus suggesm to the client a server which is best able to
`satisfy the client's service request. The broker enables a
`client to use a service even though the client is unaware
`of the presence or absence of any individual servers
`within the network.
`
`45
`
`5D
`
`55
`
`Because of the potential to form complex networks. a
`osmputer network client has a wide range of resources
`available to supply requested service. This advantage,
`however. also adds to the problem of networks and
`resource management. It is therefore desirable to obtain
`delivery of these services through network service
`names. A service cfi'ers clients capacity to use resources
`accessible through the network.
`In these computer networks. a server. made up of
`According to one aspect of the invention. the client
`then requests the service from the recommended server.
`both hardware and software. may be used as an agent
`between a client and one or more resources to deliver
`andthescrverisrespomtiblcforgrantingtherequest
`the reqnmtted service to the client. The server’s toll.-
`only if the server currently has the required capacity
`ware program provides “actions" for a client using one
`available for that sen-ice. Since the server makes the
`final determination of whether it has the available ea-
`or more rmources. These actions. for example. may be
`transmimicn of packets over a communication line—a
`pucity to provide the requested service. there is no risk
`communication server; computations in a problem—a
`of overloading a server because the broker has out of
`date status information—for sample. as when a server
`CPU server; information access in a date base—a data
`base server; network addressing information distributed so becomes busy subsequent to its last static message trans-
`throughcut a network and associated with a requested
`mitted to the broker.
`service—a narne server; or other similar and multiple
`As indicated above. the suggestion of a server prefer-
`combinations of these functions.
`ably is band on the network policy developed by the
`Because networks may include multiple servers gen-
`network manager for the particular network. Because
`orally delivering the same action. a client may access 65 of the complcx nature of present nemorlrs. a modelling
`any one of these servers with equal delivery of the
`process is used to develop a local policy for each server
`in thenetwork to deliver a sets-ice. based on the indit'id-
`action. One of the disadvantages in the prior art is the
`inability to group these servers providing the same
`uelcustomcr requirements for the network.Thecollec~
`
`Page 12 of 19
`
`

`

`5,341.43?
`
`4
`
`3
`tion of local policies determines the overall network
`policy for a given service.
`In most cases. the network policy it based on the
`servers' capacity to deliver a given service. The capao
`ity of the given service, however. can be changed with 5
`the addition or subtraedcn oi' scrvers to the network. In
`either case. the changes are made known to the broker
`and are transparent to the clients in the network.
`Upon startup. the broker develops a linked list data
`structure containing sets of server entries for each of- ID
`fered tended corresponding to the local policy obtained
`for each center. According to one aspect of the inven-
`tion. at any given time, the broker monitors a subset of
`these entries as a “preview window". The broker regu-
`larly rotates different servers into and out of the pre-
`view window. The broker suggests an entry in the pre-
`view window. upon receiving a client request. provided
`the entry has the available resources for the client.
`An advantage of the preview window is to substan‘
`tially decrease the number of servers which must be
`monitored by the broker in a network. Because the
`broker maintains current stuns: information on only a
`subset of the servers during a giv- time interval. the
`number of status messages required to be transmitted
`over the network is reduced. This results in a reduction
`of computational overhead for the broker and column.
`nications overhead on the network.
`
`FIG. 3 is a flow chart describing the modelling of a
`network policy according to the present invention.
`FIG. 4 is a conceptual block diagram of the broker
`mechanism in FIG. 2.
`
`FIGS. 5 and 5A are caarnples showing the operation
`of server data structures used in the present invention.
`FIGS. 6 and dill. are flow charts desmibhrg the operas
`tion of the broker mechanism of the present invention.
`FIG. 7 is a conceptual block diagram of an embodi-
`ment of the present invention
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`I. Network Environment
`
`Referring to FIG. 1. there is shown a model bio-ck
`diagram of a system enhanced by the present invention.
`In a network 5. a plurality cfusers or clients. generally
`designated 1|}, each have access to a plurality ofservers.
`generally designated 21]. home number of the servers Ill
`can provide access to services Arrhnrequeuted'by one
`of the clients 10. When the client 1!] requests access to
`a service via one of the servers as. a connecn'on is made
`from the selected client It! through the server 211. As
`can be seen in FIG. 1. a plurality ofservcra 2|] are avail-
`able tc make the requested connection. Therefore. it
`becomes a problem to know which client 10 should
`connect to which server Ell. Further. the resource ca-
`pacity of the server 21] must be known in order to make
`an appropriate connection. Because the server
`re-
`sources have various and different capabilities,
`i.e..
`small CPU 551% large CPU size. used and unused capac-
`ities. different serial line speeds. etc.. different servers 1b
`are more appropriate for a particular client request.
`Also. itisuoseusary toknowthesenricelerveldesircd by
`the client 1d.
`
`FIG. 2 is an example cfa hemoflt architecture incor-
`porating the present invention. The network 5 includes
`a plurality of servers 21-2? and clients ll—lllI conpied to
`a communications medium 6. eg. an Ethernet. A. bro-
`ker. conceptually shown as block at. is also coupled to
`the communhzations medium 6. Further. a dhtributed
`repository 42 or Ill-Il- ia illuau-arively coupled to me com-
`munication medium a for storing network policy. These
`repositories may be replications of each other distrib-
`uted throughout the network. Each server can provide
`access to various servicm slit-n... for a requesting client
`11-19. In operation. the broker 30 receivm the local
`policies from the repository 42 or 44 for building data
`structures for each service supported by the servers.
`processes client requests for a service. and responds in
`accordance with network policy with one or more
`server suggestions to the client
`FIG. 2A conceptually illustrates the architectural
`diagram ofFIG.2.Ahrckernicchanism3llisusedtc
`suggest to cheats It‘ll! an appropriate server 11—36 for
`delivering the requested service {service A1 or A2).
`Further. individual servers 13. 2d and 15 can provide
`more than one service. While HG. an only illustrates
`two services, it is apparent that the broker so can sug-
`gest servers to clients requesting any number of dutch
`ent services. When a particular client. Show as client
`13. requests access to service At. the cit-1t 13 places a
`request with the broker 3|] on path 5d. The broker an
`suggests an appropriate server from server set 21-44 to
`the client 13.
`
`15
`
`20
`
`25
`
`ill
`
`55
`
`in this embodiment. the broker assigns servers in a
`round robin fasluon to ensure that the loss of a single
`server does not have a major impact upon chants that
`request access at similar times. The application of the
`round robin server distribution. however. is regulated
`by use of a “scan weight” parameter for each server.
`The scan weight is defined as the number of client re-
`quests which can be satisfied by a sewer before that
`server is removed from the preview window.
`The advantages of the broker can be achieved with
`only a minimal increase in cement time from client to
`server. This is because the broker uses the preview
`Window to monitor server status information prior to
`receiving any client requests. The broker also uses the
`scan weight value to reduce the frequency by which the
`preview window is changed thus further increasing
`accurate server suggestions by the broker. Therefore.
`the incremental client ccmtect time. as opposed to a
`direct client-server connection. is only increased by the
`data needed to contact the broker and receive a sugges-
`tion.
`
`In a further embodiment. the broker 311ng to a
`client both the top server entry and the neat active
`server entry in the pretdew window. By suggesting two
`possible servers. the broker compensates for the case in
`which a failure of the first server is alleviated without
`the need to recontaet the broker. thus decreasing the
`load on the network.
`
`Another embodiment of the present invention makes
`use of multiple brokers for suggesting servers to multi-
`pla different clients. The ability to have multiple bro-
`kers running simultaneously provides a highly reliable
`service by alleviating any ahrgle point of failure.
`
`SD
`
`55
`
`I50
`
`BRIEF DESCRIPTION OF THE DRAWG’S
`
`FIG. 1 is a block diagram illuan-aring the environ-
`ment of the present hivention.
`FIG. 1 is a block diagram cfa oenvork architecture 65
`including the present invention.
`FIG. an is a block diagram conceptually illustrating
`the broker mechanism of the present invention.
`
`Page 11lol‘1EII
`
`

`

`5
`
`II. Modelling
`
`5,341.47”
`
`ii
`
`IV. Broker
`
`5
`
`A modelling process is ttsed to efficiently determine
`the allocation of resources when designing a network.
`The modelling is accomplished by the network tunn~
`agar both prior to implementing the nerwork and upon
`making subsequent changes to the network. In the mod-
`elllng process factors are takm into account such as
`whether data transmissions timing the use of a particu-
`lar network service are ofa bulk or interactive lbursty}1
`nature and their efiect on resource capacifica. Because
`bulk data transfers usually have a high transfer rate i.e..
`an entire floppy diskette of data is transferred and, on
`the other hand. interactive data transfers generally are
`of a short. bursty centre. it is generally possible in a
`given server to support more interactive data transfers
`than bulk data transfers.
`
`15
`
`An advantage of the present invention allows the
`broker 3t] (FIG. 2A.] to operate when there is: a net-
`work policy for a given scrvice; a method to easily
`determine the current usage of the server relative to the
`republished local policy; and sewers which can enforce
`their local policy eg. by rejecting any connection at-
`tempted beyond their local policy limit. These factors
`flareusedbythebrokermcchanismalltos
`aserver
`21—16 to a requesdng client 13 hand on the collection of
`local server policies in the broker.
`The data sn‘ucnirescfthebrokermechaniamdliare
`formed from an application cfthe distributed repository
`storing the network policy for each service from which
`the broker linked list data structures can he built. Many
`conventional means such as name server computer pro-
`grams are available to facilitate the creation of these
`broker linked list data structures. The distributed rcpos-
`itory is a non-volatile storage area which holds the
`collection of local policies and the attributes of how
`each supporting server supports a service.
`The repository is distributed throughout the network.
`As part ofthe broker startup procedures. the broker as
`extracts from the repository attribute information about
`each of the condom it implements. i.e, service iii—Anus
`shown in. FIG. 1. The repository is necessary to score
`the network policy in the event of a broker failure as the
`broker functions to compare cut-rem server capacity to
`network policy.
`FIG. 4 is a conceptual diagram showing an example
`ofthe data structureeprnduccrl by the code in thobrc—
`ker mechanism so The data soncmre shown inside the
`broker Ellare linked lists ofentries created by thebroker
`code.
`
`El]
`
`FIG. 3 is a flow chart depicting the modelling pro-
`cess that occurs in the development of the network
`policy to be implemented by the broker mechanism for
`each service. The modelling begins. by determining the
`service characteristics that are dmired by the customer.
`to the various possible actions, and the parameters of
`theservminthenetworhie. thereonurcesofthe
`server. Both the server parameters and required service
`eharsetenstlcs are inputs to a modelling process such as
`is described in “know—sharing queuing model for
`time-shared systems with bulk arrivals" Kleinrock et a1.
`Networks v.1 11.1 pp. 1—13 {1911} or “Models for Com- in
`paint Networ
`" Kleinrock. IEEE. Int Conference on
`Communications. Cot-f. Rec. Boulder. Unto. June Ell-l1.
`Session 2] pp. 9—115 (1969] .
`
`15
`
`III. Network Policy
`
`3-5
`
`The modelling process produces a prediction of the
`measured performance characteristics of each server
`base-don the periormance desired foreachscrvice of-
`fered by that server. This prediction ‘3 compared to the
`desired performance for each service to check if the 49
`server meets the performance limitations. If the predic-
`tion matches the desired performmtce, then the local
`policy for that particular server has been obtained.
`However, if the prediction does not match the desired
`pm-fonnance, then the local policy parameters of the
`server auditor the service characteristics are varied
`
`before being modeled again. This process continues
`until the server prediction matches the desired perfor-
`mance thus developing the local policy for the server.
`Next. the modelling process checks whether a local
`policy has been established for each server in the net.
`work If not, then the above process is repeated. Once
`all local policies have been determined, the local poli-
`cies are collected to form a network policy for the
`entire network. The network policy is stored in the
`ditt'ibuted repository 42 or 44 as shown in FIG. 1.
`When customers set up their network, they therefore
`establish anetwork policy to allocate resources for each
`service. Policy decisions must he cognizant of all of the
`available factors made prior to implementing the sys-
`i.e... basodon thephysical constraints ofthehard
`“whtheconimUnicadcnhneathepricefacbirfortbo
`product. the usage load, i.e., heavy, medium. light, fast
`CPUs. slow CPUa and other appropriate factors. a
`broker implements the network policy when suggreting
`an appropriate server to matimise the efl'iciency of the
`complex network.
`
`SD
`
`55
`
`so
`
`65
`
`The broker obtains the entries to create the data
`struonircs from the distributed repository 41. A. sen-tire
`list '111s generated for those services found'to the repos
`itory 41. Further. a server list 1'4n: created for each
`service in the service list “it to hold the local policy
`information for the particular servers 21-26 that sup-
`porttheservice.1.astly.thebrokerereatcsa“server
`status block" which contains a number of server con-
`
`nection entries 912, 5'23. 934 and 926, there being one
`connection entry in the server status block for each
`server 22, 23. 24 and hi which currently1a in the "pre-
`view windcw” of at least one service. {Preview status
`will be defined below] Each connection entry storm
`the current status information for its corresponding
`server. The policy information contained in the server
`listanriaervlce listsremainsstatic.whilctheserver
`status block information is of a dynamic or volatile
`nature.
`
`A server connection section 75 ofthe broker Elicitati-
`liahes communication paths 31—34 with the servers re-
`ferred to in the preceding paragraph. The communica-
`ticn paths 31-3! allow the broker to poll each coupled
`aerver{22,23,1l, 16} to receive its status. The status of
`theserverszt, B,1ttaa1d toisstoredinoonnectinn
`entries 922 913, 92a and 916, respectively, within the
`server status block. In response to subsequent client
`reopens for service. the broker examines these romeo
`tion entries to determine each coupled server's capacity
`or availability to deliver a requested service, as will he
`described below with coherence to FIGS. 5 and 5A. The
`server connection section 1'5 therefore supports a list of
`connection entrim 922-926 that map {till-34] to a select
`number of server entries in the server lists 14 for each of
`
`Page 14 of 19
`
`

`

`7
`the services in service list 1'1. As shown in FIGS. 4-. a
`server 24 can overlap between service offerings. The
`server connection section 1': may therefore have sev-
`eral server lists “is with entries pointing to a single
`server connection. This pooling of server connections is
`important for providing multiple service offerings from
`one broker location.
`
`1. Preview Window
`
`During the broker’s startup. data structures are devel-
`oped in the broker. The data structures include aservice
`list 1'1 and server lists 1'4 having sets of server entries
`{121-125} and (223-226) corresponding to the servers
`{21—25} and {23-236} for each service [A1 dc. A2} in the
`service list 71. The data structure information is pro-
`vided from the repository 4.2. The broke: ED than moni-
`tors. via couplings dill-34. subsets {22. 23 d: 24} and [24
`dt 26] of the servers from the above sets to form a pre-
`view window for each service. The size of the preview
`window is predetermined according to the network
`policy and stored as an attribute of the network policy
`in the repository 42. The preview Windows 72 ensure
`that a sufficient number ofseivers. l.e.. based upon the
`network policy for each service. are coupled and pro-
`viding status to the broker 30 for each son-ice before a
`client request is made. The site of the preview window
`generally reflects the number of mm necessary to
`satisfy the average rate of client requests received by
`the broker. By using preview windows. the connection
`time from client to servant h reduced by accumulating
`status and policy information in the broker in advance
`of the client request.
`Without using the pres-view windows 12. the precon-
`necticn time for a client to receive data from a service
`would be the accumulation of: [client connect time to
`broker) [broker comes! time to server location}+-
`{server startnp time}+[accumulatiort of connect times
`needed to find a server location having unassigned ca-
`pacity]. By monitoring the resources of the servers
`contained in the preview windows via communication
`paths 31-31 associated with each Service. the broker 30
`can suggest the top entry in the preview window to a
`client requesting that particular service. The suggestion
`is made provided the enuy has the available resources.
`If an entry done not have the available resources it is
`removed from the preview window. Servers are thus
`regularly rotated in and out of the preview window.
`FIGS. 5 and 5d. illustrate by examine the data struc-
`mres within each server [shown here as servers 1 and 2}
`to indicate server capacity and status to deliver a re-
`quested service. The status information is provided to
`the broker as for comparing the capacity to the local
`policy for each server as shown by commmtication
`paths 31—34 in FIG. 4.
`In FIG. 5. server 1 is shown supporting two services
`101 and 102 having service names A1 and A2. respec-
`tively. Similarly. server 1 supports services. 103 and 104
`having service
`A: and Ag. Associated with each
`service lot—104 is a client capacity number 111-114 so
`iridicatiug the number of clients that can be processed
`by each server for the particular service. The client
`Capacity number reflects the server‘s local policy far
`each service. its shown at FIG. 5. the client capacity
`nuinber can be a scalar value which is reduced as the as
`server increasm its load. The current value of the capac-
`ity number 111-114 is therefore checked by the broker
`whenever the broker tries to cm the server.
`
`5,341.47?
`
`5
`
`it!
`
`15
`
`3-0
`
`35
`
`45
`
`53
`
`55
`
`8
`A second implementation of the database of sewer 1
`is shown in FIG. 5A. wherein client slots 105-103 are
`assigned to each service an and A: (101 and 102}. For
`example. assuming each server has four client slots. two
`client slots {105. 11115 and 101'. 10d] can be allotted for
`each service 101 and 1132. reapcctively in sm'ver 1. This
`is equivalent to a client capacity number oftwo for each
`service 101 or 1'12. Client slob: allow the broker to
`determine the availability of servers by checking a flag
`indicating Whether particular client slots are used.
`However, a more powerful use of client slots is
`achieved in server 2 as shown in FIG. Ed. by allowing
`certain client slots to provide multiple services. Again.
`only four client slots are educated for server 2. The first
`client slot 115 is dedicated for use with service AKIN)
`and the second client slot 113 is provided For service A:
`{104}. In this case. however. the. third and fourth client
`slots are much: available to each sort-rice TM. 117. 119'. 12
`1. Therefore. if three requests are received for service
`Agaud only oncrequcat for scrvicoAl. then by mating
`the client slots available for use with each service. all of
`the requests can be satisfied. Again. this is implemented
`by the server connection section 1'5 (FIG. a) checking
`flags to determine the availability of each client slot.
`These flags indicate the status for the servers against
`which the local policies are checked in connection
`entries ceases.
`
`Through theusaot'tbeprevicw wdndowand the
`overlapping of servers to provide different services. the
`broker mechanism 30 thus reduces the number of active
`network connections [31-34] necessary to poll the serve
`ers to obtain their status. Dtherwise. active connections
`would be required from all of the servers in the note
`work. Therefore. only a reasonably managed subset of
`servers is maintained by the broker 30 as active connec-
`tions to reduce message traffic on the network and to
`simplify the computational overhead in the broker.
`
`B. Scan Weights
`
`Referring again to FIG. 4. because the capacity of
`each server to deliver a given service may not be equal
`depending upon the neurotic policy. an additional pa—
`rameter termed scan weight 73 is added. The scan
`weight 73 is the number ofth requests which can be
`satisfied from a server before the particular server is
`removed from the preview window '12. Each server is
`assigned a particular scan weight value for each service
`by the network manager. The scan weight '13 allows the
`network manager to apply the network policy to more
`efficiently assign clients to to servers in a round-robin
`manner. The values chosen for the scan weight are
`developed as part ofthe capacity planning modelled in
`FIG. 3.
`
`An example ofscan weight operation is given in the
`server list 1'4 for service A] as shown in FIG. 4. Five
`servers 2‘]. 22. 23. 245. and 25 having server entries
`111-125. respectively. are determined to have the fol-
`lowing capacities to access a service for a client: saver
`21.1 clientsflli); server 22.6 clientsfltl]; server 23.2
`clientsf‘lll); server 24.4 clientstld]; and server 25.2
`chesitsflll). Without scan weight. the broker mechanism
`at]. using a purely round robin mediod of assigning
`serversl would reduce the list of five available servers
`21-25 to just two available servers 2: and 24 after only
`lit client requests have been suggested. This occurs
`because the servers having the least capacity, in 21. 23
`and 15. are suggested as often as the other servers. thus
`quickly using their capacity. After the first ten requests.
`
`Page 15oi‘15lI
`
`

`

`ll]
`don section To receives the request and checks whether
`the service list T1 exists in the broker. If the service list
`Tl artists, the broker to checks whether the particular
`service requested [in