United States Patent
`US 6,883,028 B1
`(10) Patent No.:
`(12)
`Johnsonet al.
`(45) Date of Patent:
`*Apr. 19, 2005
`
`
`US006883028B1
`
`(54) APPARATUS AND METHOD FOR
`PERFORMING TRAFFIC REDIRECTION IN
`A DISTRIBUTED SYSTEM USING A
`PORTION METRIC
`Inventors: Richard A. Johnson, Santa Barbara,
`cA tus Baeaan Santa Cara,
`;
`Dalen
`D. Bosteder,
`San
`Jose,
`CA (US)
`
`(75)
`
`(73) Assignee: Cisco Technology, Inc., San Jose, CA
`(US)
`
`5,918,017 A
`6/1999 Attanasio et al.
`........... 709/224
`
`6,047,309 A *
`4/2000 Danet al. we 709/201
`6,078,943 A *
`6/2000 YU wee eeeeeeeeeeeeeee 718/105
`6,205,477 B1 *
`3/2001 Johnsonetal. ............. 709/220
`6,249,801 B1 *
`6/2001 Zisapel et al... 718/105
`
`ee BI : 3002 Yndal OE ad oeessseseseee roa
`
`7/2003 Bhaskaran et al. 1... 718/105
`6,601,084 Bl *
`OTHER PUBLICATIONS
`
`.
`. ,
`.
`Cisco Systems, Inc., “Cisco DistributedDirector,” 1996, 9
`pp.
`
`(*) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`US.C. 154(b) by 724 days.
`
`* cited by examiner
`
`patent is subject to a terminal dis-
`This
`claimes
`J
`,
`
`Primary Examiner—Kenneth R. Coulter
`(74) Attorney, Agent, or Firm—Beyer Weaver & Thomas
`LLP
`
`(21) Appl. No.: 09/753,641
`
`(22)
`
`Filed:
`
`Jan. 2, 2001
`
`Related U.S. Application Data
`.
`.
`(63) Continuation of application No. 09/175,195,filed on Oct.
`20, 1998, now Pat. No. 6,205,477.
`Tint, C0? eee ce eee ceteeeeeeeeeneene G06F 15/177
`(SV)
`(52) US. Ch. vcecccccecces 709/226; 709/223; 709/203;
`718/105
`i
`(58) Field of Search... 709/226, 203,
`709/223, 220; 718/105, 104, 102
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`(57)
`
`ABSTRACT
`
`A method and system for distributing a service request
`amonga plurality of servers is disclosed. A portion metric is
`assigned to each one of the plurality of servers, the portion
`metric designating a portion of total server requests to be
`allocated to the one of the plurality of servers. A server
`request may then be received. A total number of server
`requests processed bythe plurality of servers is incremented
`and a numberof server requests distributed to each one of
`the plurality of servers is maintained. The server request is
`then distributed
`to one of
`the plurality of servers using the
`then
`distributed
`f the
`plurality
`of
`ing
`th
`portion metric assigned to each one of the plurality of
`servers, the number of server requests distributed to each
`one ofthe plurality of servers, and the total numberof server
`requests.
`
`5,603,029 A *
`
`2/1997 Amanetal... 718/105
`
`52 Claims, 6 Drawing Sheets
`
`rs
`Configuration
`-Assoc, host name with IP
`9g —-| Addresses
`-Assign portion metric &
`leral
`tol
`
`Initiaiize variables for each
`server
`er
`
`X:X: Number
`29=Server_Requested [x]=0
`Total_Requests=0
`Recelve server requesthost name query
`Obtain IP addresses assoc. with the host name
`
`30
`32
`
`
`Tanges to each server
`
`
`
`
`
`Add portion metric[x] for each serverx
`36
`
`
`4 to obtainatotal portion metric
`For each serverx:
`Server_Request_Percentage[x}
`comp le
`
`For each serverx:
`compute
`
`Metric Value}
`Compare metric values
`
`
`
`Selected
`Apply “tie breaker"
`
`Server
`Return IP address associated with the selected server
`
`
`
`38
`
`40 4
`
`
`42 48
`
`48
`
`
`
`50
`
`Number_Server_Requests(selected server[++
`
`Total_Requests++
`
`
`Google Exhibit 1130
`Google v. VirtaMove
`
`Google Exhibit 1130
`Google v. VirtaMove
`
`

`

`U.S. Patent
`
`Apr.19, 2005
`
`Sheet 1 of 6
`
`US 6,883,028 B1
`
`
`
`
`24
`
`14
`
`18
`
`FIG. 1
`
`

`

`U.S. Patent
`
`Apr. 19, 2005
`
`Sheet 2 of 6
`
`US 6,883,028 B1
`
`y”
`
`v2
`
`
`
`Distributed
`Director
`
`San Jose
`
`Web Server
`
`78
`
`80
`
`Paris Web
`Server
`
`
`
`Info.
`Gathering
`Block
`
`82
`
`Info.
`Gathering
`
`Block
`
`82
`
`internet
`
`74
`
`FIG. 2
`
`

`

`U.S. Patent
`
`Apr. 19, 2005
`
`Sheet 3 of 6
`
`US 6,883,028 B1
`
`y 8
`
`28
`
`29
`
`
`
`Configuration
`-Assoc. host name with IP
`addresses
`-Assign portion metric &
`tolerance
`ranges to each server
`
`Initialize variables for each
`server X: Number
`Server_Requested [x]=0
`Total_Requests=0
`
`30
`
`32
`
`34
`
`36
`
`Receive server request/host name query
`
`Obtain IP addresses assoc. with the host name
`
`Add portion metric[x] for each server x
`to obtain a total portion metric
`
`For each server x:
`compute
`Server_Request_Percentage[x]
`
`38
`
`For each server x:
`compute
`Metric Value[X]
`
`40
`
`Compare metric values
`
`42
`
`N
`
`44
`
`v
`
`Apply "tie breaker"
`
`46
`
`Return IP address associated with the selected server
`
`48
`
`Number_Server_Requests{selected server]++
`
`50
`
`Total_Requestst++
`
`FIG. 3
`
`

`

`U.S. Patent
`
`Apr. 19, 2005
`
`Sheet 4 of 6
`
`US 6,883,028 B1
`
`
`
`Number_Server_Request[x]
`* Total Portion Metriic
`
`y
`
`o4
`
`
` Divide by
`Total.Requests
`
`
` 56
`to obtain
`Server_Requests_Percentage[X]
`
`60
`
`Is X Equal to
`Number of
`Servers N
`
`58
`
`
`
`
`FIG. 4
`
`

`

`U.S. Patent
`
`Apr.19, 2005
`
`Sheet 5 of 6
`
`US 6,883,028 B1
`
`ye
`
`64
`
`
`Metric_Value[x] =
`
`Server_Request_Percentage[x]
`Portion_Metric{x]
`
`68
`
`
`
`
`
`
`
`Is X Equal to
`Numberof
`Servers N
`
`66
`
`FIG. 5
`
`

`

`U.S. Patent
`
`Apr. 19,2005
`
`Sheet 6 of 6
`
`US 6,883,028 B1
`
`y
`
`Configuration
`
`86
`
`Accept HTTP Connection from
`Client
`
`Connect to Virtual Web Server
`
`89
`
`Obtain Clients IP Address
`
`90
`
`
`
`
`Determine Host Name Assoc.
`with the IP Address of the
`Virtual Web Server
`
`
`
`
`Construct a New Host Name
`Associated with the Host Name
`
`Obtain Set of IP Addresses of
`Real Web Servers Assoc.with
`
`the New Host Name
`
`92
`
`93
`
`94
`
`Select One of the Set of IP
`Addresses
`
`32-44
`
`Send HTTP Code 302 Redirect
`
`96
`
`Update Variables Corr. to
`ServerSelection
`
`48-50
`
`FIG. 6
`
`

`

`US 6,883,028 B1
`
`1
`APPARATUS AND METHOD FOR
`PERFORMING TRAFFIC REDIRECTION IN
`A DISTRIBUTED SYSTEM USING A
`PORTION METRIC
`
`RELATED APPLICATIONS
`
`This application is a continuation of U.S. patent applica-
`tion Ser. No. 09/175,195 filed Oct. 20, 1998, now U‘S. Pat.
`No. 6,205,477, naming Richard A. Johnson et al. as
`inventors, and entitled “Apparatus and Method for Perform-
`ing Traffic Redirection in a Distributed System Using a
`Portion Metric.” That application is incorporated herein by
`reference in its entirety and for all purposes.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`The present invention relates generally to traffic redirec-
`tion in a distributed system. More particularly, the present
`invention relates to a method and apparatus for redirecting
`traffic among a numberofservers using a portion metric for
`each server.
`
`2. Description of the Related Art
`A computer network may be defined as an interconnected
`collection of autonomous computers.
`In a distributed
`system, the existence of these multiple autonomous com-
`puters is transparent
`to the user. To achieve this
`transparency, allocation of jobs to processors and all other
`system functions must be automatic. These automated sys-
`tem functions are typically provided by an operating system.
`In general, the operating system hides the details of the
`hardware from the user and provides the user with a con-
`venientinterface for using the system. Moreparticularly, the
`operating system is responsible for allocating resources
`within the distributed system and schedules the execution of
`various services accordingly. Thus,
`the operating system
`selects the best processor, locates and transfers all corre-
`sponding appropriate location. In this manner, the operating
`system ensures that system resources such asfile servers are
`used in an efficient manner.
`
`The resource allocation provided by the operating system
`includesthe retrieval and processing of data. Often, this data
`is stored on one or more sharedfile servers. Users in such a
`
`system are called clients. Communication from a client
`generally comprises a request message asking for a particu-
`lar service to performed. The service request messageis then
`sent to an appropriate server. The server then does the work
`requested and sends back a reply. Thus, data is accessed and
`processed by the server in accordance with the service
`request message.
`In order to send a service request messageto a server, the
`operating system must first select an appropriate server.
`Typically, the operating system selects a server according to
`criteria that may be applied through the use of a metric. By
`way of example, a commonly used metric distributes the
`service request message to a serverclosest in distance to the
`client. Accordingly, the operating system maydirecttraffic
`to a server according to a specified metric.
`Although various metrics exist for allocating resources
`within a network, these metrics do not adjust assignment of
`server requests in accordance with the load capacity of each
`server. By way of example, each server may have different
`processing capabilities. As yet another example, a server
`may be entirely unavailable. Metrics traditionally used in
`distributed systems do not adjust assignment of requests
`according to such situations. As a result,
`these metrics
`
`10
`
`15
`
`20
`
`30
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`cannot adequately maximize the throughputof a distributed
`system having servers with heterogeneous load capabilities.
`It would be desirable if a metric were provided such that
`server requests could be distributed in accordance with the
`load capacity of each server.
`Every host and router on the Internet has an IP address.
`The Domain Name System (DNS)is often used to map host
`names to these IP addresses. By way of example, a client
`typically sends a DNS query to a DNSserver whichincludes
`a host name and an indication that an IP addressis requested.
`The DNSserver then returns an IP address associated with
`the host name. It would therefore be desirable if a DNS
`
`server were designed to accomplish load distribution com-
`patible with the Internet and DNS.
`In addition to ensuring adequate load distribution, it is
`necessary to accommodate for shifts of information. Infor-
`mation is commonly transferred from one web server to
`another web server on the Internet. Typically, a web server
`will redirect a client to a new location due to this physical
`shift of information between web servers. However, the host
`of the client is typically not taken into consideration during
`selection of the web server in providing this redirect. In
`many instances it would be desirable if the information
`could be selectively varied according to the particular client
`requesting the information. It would therefore be desirable if
`the host of the client were considered during selection of an
`appropriate web server in order to provide such a redirect.
`Moreover, it would be beneficial if the client could easily
`identify the server to which the server request is redirected.
`In view of the above, a system and methodfor redirecting
`traffic in a distributed system according to individual server
`capabilities would be desirable. Additionally, it would be
`beneficial if such a system distributedtraffic in proportion to
`individual server portion metrics.
`SUMMARYOF THE INVENTION
`
`The present invention provides a method and apparatus
`for distributing server requests amonga plurality of servers
`in a distributed system. This is accomplished throughassign-
`ing a portion metric to each server. In this manner,
`the
`portion metric allows capabilities of each candidate serverto
`be taken into consideration during distribution of each server
`request.
`In accordance with one aspect of the present invention,
`each server request is distributed in accordance with the
`Domain Name System (DNS). Configuration is performed
`in several steps. First, a Domain Name System host nameis
`associated with a plurality of servers, each one of the servers
`having a unique IP address. By way of example, a DNStable
`on a DNSserver typically includes a plurality of entries,
`each of the entries containing an IP address-host name
`association. Second, a portion metric is then assigned to
`each one of the plurality of servers. The portion metric
`designates a portion of total server requests to be allocated
`to the one of the plurality of servers. As a result, each web
`server is assigned a portion metric. Each portion metric
`designates a portion of total server requests to be allocated
`to the corresponding server. Once configuration is
`completed, server requests may be allocated.
`Each server request is separately allocated to a selected
`web server. The server request may include a DNS host
`name query received from a client. By way of example, a
`DNShost name query may include a host nameto be looked
`up and an indication that an IP address is requested. A
`plurality of IP addresses associated with the host name may
`then be obtained, each one of the IP addresses being asso-
`
`

`

`US 6,883,028 B1
`
`3
`ciated with one ofthe plurality of servers. A total numberof
`server requests processed by the plurality of servers is
`incremented. In addition, a numberof server requests dis-
`tributed to each oneof the plurality of servers is maintained.
`Oneof the plurality of servers is selected using the portion
`metric assigned to each one of the plurality of servers, the
`number of server requests distributed to each one of the
`plurality of servers, and the total numberof server requests.
`An IP address associated with the selected server is then
`
`provided to the client from which the server request was
`obtained. Accordingly, when each server requestis received,
`one of the plurality of IP addresses is determined and
`provided to the client. In this manner,traffic sent to geo-
`graphically distributed web servers in multiple networks
`may be distributed and monitored. Moreover, the present
`invention may be and is preferably geographically distant
`from the web servers. Thus, connections distributed to each
`web server may be monitored and load averages of each web
`server may be subsequently queried.
`In accordance with another aspect of the present
`invention, the portion metric is used in combination with
`other metrics. A portion metric is assigned to each one of a
`plurality of servers. The portion metric for each one of the
`FIG. 1 is a block diagram illustrating an exemplary
`plurality of servers is added to obtainatotal portion metric.
`25
`distributed system in which the portion metric of the present
`A numberof server requests distributed to each one of the
`invention may be implemented.
`plurality of servers is maintained. In addition, a total number
`of server requests processed by the plurality of servers is
`FIG. 2 is a block diagram illustrating a distributed system
`incremented. A server request is then received. A server
`in which the distributed director of the present invention is
`request percentage is computed for each one ofthe plurality
`implemented.
`of servers. The server request percentage for each one of the
`FIG. 3 is a flow diagram illustrating a method for oper-
`plurality of servers is a product of the number of server
`ating the distributed director in DNS mode according to one
`requests distributed to the one of the plurality of servers and
`embodimentof the present invention.
`the total portion metric divided by the total numberof server
`FIG. 4 is a flow diagram illustrating a method for calcu-
`requests received. In addition, a metric value is calculated
`lating the server request percentage for one of the plurality
`for each one of the plurality of servers. The metric value for
`of servers according to an embodiment of the present
`oneof the plurality of servers is defined by the server request
`invention.
`percentage for the one of the plurality of servers and the
`portion metric for the one of the plurality of servers. The
`metric values for the plurality of servers are compared to
`obtain a selected server.
`
`4
`tion is accepted. A total numberof server requests processed
`by the plurality of servers is incremented. In addition, a
`numberof server requests distributed to each of the servers
`is maintained. Oneofthe plurality of servers is then selected
`using the portion metric assigned to each of the servers, the
`numberof server requests distributed to each of the servers,
`and the total number of server requests. An HTTP code
`redirect is then sent to the client. Therefore, information
`provided to a client may beselectively varied according to
`the particular client requesting the information.
`The advantages of assigning a portion metric to a set of
`servers and distributing a service request in accordance with
`such portion metric assignments are numerous. The present
`invention may be used to allow capabilities of each candi-
`date server to be taken into consideration during distribution
`of each server request. By way of example, portion metric
`assignments may be used to maximize the throughput of a
`distributed system having servers with diverse processor
`speeds. Similarly, portion metrics may be reassigned upon a
`determination that a server is unavailable.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 5 is a flow diagram illustrating a method for deter-
`mining the metric value for one of the plurality of servers
`according to one embodimentof the present invention.
`FIG. 6 is a flow diagram illustrating a method for oper-
`ating the distributed director in HTTP redirect mode accord-
`ing to one embodimentof the invention.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`The present invention provides a method and system for
`redirecting traffic among a numberofservers. This is accom-
`plished through ascertaining the host for the client, deter-
`mining a plurality of servers associated with the host, and
`selecting one of the plurality of servers. The selection may
`be based upon defined portion metrics as well as other
`metrics. Various embodiments of the invention are possible.
`By way of example, the present invention may be imple-
`mented in accordance with the Domain Name System as
`well as the HTTP protocol. In addition, the invention can be
`implemented in numerous ways, including as a method, an
`apparatus such as a switching element (e.g., router or
`brouter), or a computer readable medium. Several embodi-
`ments of the invention are discussed below.
`
`Referring first to FIG. 1, a block diagram illustrating an
`exemplary distributed system in which the portion metric of
`the present invention may be implemented is presented. A
`distributed system 10 will typically include one or more
`clients 12 and a plurality of servers. As illustrated,
`the
`plurality of servers includesa first server 14, a second server
`16, and a third server 18. Typically, a client 12 will send a
`
`10
`
`15
`
`20
`
`30
`
`35
`
`40
`
`The selected server may include a set of servers. The set
`of servers may include those servers having an identical
`metric value. Alternatively, a tolerance range may be con-
`figured for the portion metric. The tolerance range may then
`be used in comparing the metric value for each of the
`servers. Thus, a set of the plurality of servers having a metric
`value within the tolerance range may be obtained. An
`alternate metric may then be applied to the set of servers to
`obtain a single selected server. By way of example,
`the
`alternate metric may include a distance metric. The selected
`server is then provided to the client.
`In accordance with yet another aspect of the invention,
`load imbalance may be detected. As described above, a set
`of the plurality of servers is obtained upon application of the
`portion metric. When the set of the plurality of servers
`includes only one server, this may indicate the presence of
`load imbalance. By way of example, if there is a large
`disparity in the amountof server requests distributed to each
`server, there will be one server that has received the least
`amountof server requests, and this server will therefore be
`selected. A report may be generated indicating the presence
`of this load imbalance in the distributed system. Moreover,
`the detection of load imbalance permits reallocation of
`servers as well as the reconfiguration of portion metrics and
`tolerance ranges.
`In accordance with a further aspect of the invention, a
`portion metric is assigned to each server. An HTTP connec-
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`US 6,883,028 B1
`
`5
`request for a service which will be distributed to one of the
`plurality of servers. To distribute each such service request,
`one or more metrics may be used in the selection process. In
`a commonly used metric, the service request is distributed to
`the server closest in distance to the client. The first server 14
`is a first distance 20 from the client 12, the second server 16
`is a second distance 22 from the client 12, and the third
`server 18 is a third distance 24 from the client 12. As shown,
`the second distance 22 indicates that the second server 16 is
`
`closest in distance to the client 12. Accordingly, the service
`request would be distributed to the second server 16 if such
`a metric were applied. However, in circumstances where
`each one ofthe plurality of servers 14, 16, 18 is equidistant
`from the client 12, another metric may be used as a “tie
`breaker.” Moreover,
`the distance between the client and
`selected server may be deemed insignificant in comparison
`to factors such as the processor speed of each available
`server. In such instances, an alternate metric may be desir-
`able.
`
`Referring next to FIG. 2, a block diagram of a distributed
`system in which the distributed director of the present
`invention according to one embodiment
`is presented. A
`distributed system 70 in which the present invention may be
`implemented is illustrated. According to the present
`invention,a distributed director 72 may be provided for each
`host. As shown,the distributed director 72 is provided for an
`Internet host 74. As will be described, a client 76 connecting
`to the Internet 74 may wish to connect to a web server
`located in another geographical
`location. By way of
`example, the San Jose web server 78 and Paris web server
`80 are shown. Thedistributed director 72 determinesa host
`associated with the client 76 (e.g., patents.com). The dis-
`tributed director 72 may be configured to be the primary
`DNSserver for a particular host. Thus, once the host is
`determined, the IP addresses associated with this host may
`easily be obtained. In this manner, available web servers
`associated with these IP addresses are made available for
`selection.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`In responseto a server request, the distributed director 72
`utilizes one or more metrics to select one of these web
`
`40
`
`servers. Metrics utilized by the distributed director 72 may
`include a variety of metrics, including the distance metric.
`An information gathering block 82 may be utilized to gather
`metric information such as the distance to each server. The
`
`information gathering block 82 may include a router and
`therefore must have access to all routing tables relating to
`the geographically distributed Web servers. By way of
`example, the distributed director 72 may query the infor-
`mation gathering block 82 for distance metrics between the
`distributed servers 78, 80 and the client 76. According to one
`embodiment,
`the information gathering block 82 may
`include a Direct Response Protocol (DRP) agent, available
`from Cisco Technology, Inc., located in San Jose, Calif. In
`addition,
`the distributed director 72 provides a portion
`metric which allows capabilities of each candidate server to
`be taken into consideration during distribution of each server
`request. The distributed director 72 may therefore direct
`clients to an appropriate server that is also closest in dis-
`tance. In this manner, the distributed director 72 provides
`dynamic, transparent, and scalable Internettraffic load dis-
`tribution between multiple geographically dispersed servers.
`Referring next to FIG. 3, a flow diagram illustrating a
`method for operating the distributed director in DNS mode
`according to one embodimentof the invention is shown. As
`shown, a service request is distributed among a plurality of
`servers 26. First, at step 28,
`the distributed director is
`configured. Configuration may include associating each host
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`with a plurality of IP addresses correspondingto a plurality
`of web serversin the distributed system, assigning a portion
`metric to each server, assigning other metrics to each server,
`and specifying a tolerance range for application of each
`specified metric.
`A portion metric PORTION_METRIC[X]is assigned to
`each one of the plurality of servers, where X=1 to the total
`number of servers N. Each portion metric designates a
`portion of total server requests to be allocated to the corre-
`sponding one of the plurality of servers. For example,
`portion metrics 20%, 32%, and 60% may be assigned to
`three servers, respectively. The portion metrics do not nec-
`essarily need to total a value of one hundred. Thus, if
`percentages have been overassigned as in the previous
`example, then the percentage of server requests assigned to
`each server will automatically be scaled down by each
`server’s portion metric suchthat they total 100% of requests
`and retain their relative configured portion of requests.
`According to one embodiment, a portion metric is
`assigned to each server in the distributed system using the
`DNS host name. For example, “HOST SERVER1 POR-
`TION 32”could be used to indicate that the portion of server
`requests for the DNS host “SERVER1”is 32. These portion
`metrics may then be used to determine a percentage of server
`requests to send to each server. Moreover, a default portion
`metric may be provided. By way of example, the default
`portion metric may be zero. As a result, servers with a higher
`portion metric will receive a larger number of server
`requests than servers with a lower portion metric. This
`allows a network administrator to adjust server load distri-
`bution across heterogeneousdistributed servers, resulting in
`improved performance as seen byclients.
`The portion metric may be used in combination with other
`metrics or alone to distribute server requests in a network or
`distributed system to select an appropriate server for each
`client. Similarly, any of these metrics may be turned off or
`on to add or remove metrics which are to be considered. For
`example, a command “PORTION X METRIC2.. .” may be
`provided to add the portion metric and a second metric,
`“METRIC2”. Similarly, a command “NO METRIC3”could
`be used to turn off a third metric, “METRIC3”. When the
`portion metric is used in combination with other metrics, the
`order in which these metrics are consideredis specified. By
`way of example, the first metric specified in the command
`line may be consideredfirst, followed by each following
`metric specified.
`In addition to specifying a portion metric as well as other
`metrics for each server, a tolerance range may be configured.
`The tolerance range supplies a range used to determine,
`relative to a lowest or highest value, whether any distributed
`servers should be equally preferred for a given client. For
`example, assume there are three servers: SERVER1,
`SERVER2 and SERVER3associated with values 100, 119
`and 125, respectively. If the tolerance value is set to 20
`percent, SERVER1 (associated with value 100) and
`SERVER2 (associated with value 119) would be equally
`preferred since 119 is within the 20 percent tolerance range.
`SERVER3(associated with value 125) would be eliminated
`from consideration.
`
`The present invention may be configured to function in a
`DNS mode as well as in HTTP redirect mode. Additional
`DNS resource records must be added to the primary
`domain’s primary DNSserver to identify the distributed
`director as the authoritative name server for a given host in
`DNS mode, or as the actual Web server requested by the end
`user in HTTP redirect mode. Moreover, DNS resource
`
`

`

`US 6,883,028 B1
`
`7
`records used bythe distributed director may be configured in
`an external serveror, alternatively, in the distributed direc-
`tor.
`
`Next, at step 29, initialization of variables is performed.
`During this step, a variable storing a total numberof server
`requests processed by the plurality of servers, TOTAL_
`REQUESTS, is initialized to a constant.
`In addition, a
`variable for each one of the plurality of servers storing a
`number of server requests distributed to each one of the
`plurality of servers, NUMBER_SERVER_REQUESTS[X]
`are each initialized to a constant. According to a preferred
`embodiment, the variables are initialized to zero. However,
`another constant maybe used to avoid the potential problem
`of dividing by zero.
`Once the distributed director is configured and initializa-
`tion is performed, a server request may then be received at
`step 30. By way of example, the server request may include
`a DNShost name query that is received from a client. ADNS
`host name query typically includes a host nameto be looked
`up and an indication that an IP address is requested.
`After the server request is received, the portion metrics
`may be utilized as well as other metrics to select an
`appropriate server in response to each server
`request.
`According to one embodiment, each server request is dis-
`tributed in accordance with the Domain Name System
`(DNS). At step 32, a plurality of IP addresses associated with
`the queried host nameare obtained. Each oneofthe plurality
`of IP addresses are associated with one of a plurality of
`servers in the distributed system. In this manner, a set of
`servers are obtained from whichoneisto be selected. At step
`34,
`the portion metrics for each one of the plurality of
`servers are addedto obtain a total portion metric, TOTAL_
`PORTION.
`
`In order to distribute the server request to an appropriate
`server, metric values for each oneof the plurality of servers
`are computed. A metric value for a selected server X is
`computed using the numberof server requests distributed to
`the selected server, the portion metric for the selected server,
`the total portion metric, and the total number of server
`requests processed by the distributed system where
`METRIC_VALUE[X]=SERVER_REQUEST_
`PERCENTAGE[X]-PORTION_METRIC[X]. At step 36, a
`server request percentage is calculated for each one of the
`plurality of servers. For each server,
`the server request
`percentage is calculated using the numberof server requests
`distributed to the server, the total portion metric, and the
`total number of server requests received where SERVER__
`REQUEST_PERCENTAGE[X]=NUMBER_SERVER__
`REQUESTS[X]* TOTAL_PORTION/TOTAL_
`REQUESTS. Thus,
`the server
`request percentage is a
`percentage of total requests distributed to a server X which
`is normalized to the portion metric assignments. Next, at
`step 38, a metric value is determined for each one of the
`plurality of servers. For each server, the metric value is
`determined using the server request percentage for
`the
`server, the portion metric for the server, and the total number
`of server requests received. According to one embodiment,
`the metric value is obtained by subtracting the portion metric
`from the server request percentage, METRIC_VALUE[X]=
`SERVER_REQUEST_PERCENTAGE[X]-PORTION__
`METRIC[X]. However, a constant such as TOTAL_
`REQUESTS maybe added to this value to ensure that the
`METRIC_VALUE[X]is a positive number.
`If multiple metrics have been specified for each server, the
`metrics may be combined to form a single metric value prior
`to server selection. In addition, each metric or selected
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`metrics may be assigned a weight during configuration
`indicating a metric priority. If multiple metrics have the
`same metric priority, the metrics may be added to obtain a
`composite metric. For example, if two metrics have the same
`metric value, the metric values may each be multiplied by
`their respective weight values (if specified) and then added
`together to form the composite metric for the corresponding
`server. According to one embodiment, the default weight
`values are set to 1.
`
`The metric value for each one of the plurality of servers
`are then compared to choose one or more “selected” servers
`(e.g., aserver having a lowest or highest metric value) at step
`40. In the embodimentdescribed below,it is assumed that
`the server having the lowest metric value is selected.
`Moreover, a set of the plurality of servers having metric
`values within the tolerance range may be “selected”.
`If multiple servers are determined to have been “selected”
`at step 42 (the metric values associated with the selected
`servers are within the tolerance range), an alternate metric
`may be used as a “tie breaker” at step 44. By way of
`example, the server closest in distance to the client may be
`selected. As yet another example, the next metric may be
`used to select the “best” server.
`
`the IP address associated with the
`Next, at step 46,
`selected server is provided to the client from which the
`server request was obtained. By way of example,
`the IP
`address may be returned to the client’s local DNS.
`Therefore, the server request is distributed using the portion
`metric assigned to each one of the plurality of servers, the
`number of server requests distributed to each one of the
`plurality of servers, and the total number of server requests
`as described above. As a result,
`the distributed director
`effectively functions as a