News Column

Patent Issued for Server Load Balancing Using a Fair Weighted Hashing Technique

July 8, 2014



By a News Reporter-Staff News Editor at Information Technology Newsweekly -- Juniper Networks, Inc. (Sunnyvale, CA) has been issued patent number 8762534, according to news reporting originating out of Alexandria, Virginia, by VerticalNews editors.

The patent's inventors are Hong, Xinhua (Milpitas, CA); Wang, Hongbin (San Jose, CA); Zhang, Ying (Oakland, CA); Narayanaswamy, Krishna (Saratoga, CA); Nair, Rakesh (Milpitas, CA); Han, Henry (San Ramon, CA).

This patent was filed on May 11, 2011 and was published online on June 24, 2014.

From the background information supplied by the inventors, news correspondents obtained the following quote: "In computer networking, load balancing is commonly used to distribute workload across two or more resources. For example, a group of servers, storage devices, or other resources may collectively provide services to a number of clients. Each client that connects to the group of resources may be initially allocated to one of the resources.

"Hashing-based server load balancing is widely employed. Each incoming client may be associated with a key that is mapped, through a hashing function, to the resource that is to be used by the client. Ideally, a high performance load balancing scheme should be able to achieve the following goals simultaneously, without compromising another goal: (1) distribute client requests to resources evenly; (2) minimize traffic interruption even in the event of resource removal or addition; (3) handle a weight associated with each resource (e.g., a first server resource may have twice the capacity as a second server resource, and the first server resource should thus be assigned twice the weight as the first); and (4) optimize the hash lookup operation to reduce operation cost, as speed is a major concern for many load balancing applications.

"Existing hashing-based load balancing techniques include the known 'consistent hashing' and 'distributed hashing' techniques. Both of these techniques may support dynamic joining and removing of resources. The consistent hashing technique, however, can have a worst-case lookup cost of O(n), where n represents the number of resources or modules. The worst-case lookup cost may be experienced when most of the resources fail. The distributed hashing technique may not support weighted hashing and may have an average lookup cost of O(n) or, in some variations, O(log(n))."

Supplementing the background information on this patent, VerticalNews reporters also obtained the inventors' summary information for this patent: "One implementation is directed to a method that may include maintaining a table that relates how incoming client resource requests are to be distributed among modules. The method may further include updating the table, in response to an indication that an additional module, associated with a module identifier, is to be included in the modules, by: determining a number of entries to add to the table for the additional module; calculating a first hash value for each of the number of entries; and modifying the table by writing the module identifier to one or more sequential entries of the table, beginning at an index into the table corresponding to the first hash value. The method may further include looking up one of the modules to handle a particular incoming client resource request, based on a second hash value obtained from information in the incoming client resource request, the second hash value being used as an index into the table to lookup the module identifier of the module to handle the particular incoming client resource request.

"In another implementation, a device may include a hash table that includes, for each of a plurality of entries in the hash table, an index into the hash table, a hash value field, and a module identifier field, the module identifier field identifying modules of a group of modules that provide a computing or data storage service to client devices. The device may further include a table manager to update the hash table, in response to an indication that a module, associated with a module identifier, is to be added to the hash table, by writing the module identifier and a first hash value, associated with the module that is to be added, to one or more sequential entries of the table in the module identifier and hash value fields, respectively, beginning at the index into the table corresponding to the first hash value. The device may further include a module lookup component to lookup one of a group of modules, stored by the hash table, to handle a particular incoming client resource request, based on a second hash value obtained from information in the incoming client resource request, the second hash value being used as the index into the hash table to lookup the module identifier of the one of the group of modules to handle the particular incoming client resource request.

"In another implementation, a number of modules may provide computing or data storage services to client devices. Additionally, a load balancer may maintain a table that relates how incoming client resource requests are to be distributed among the modules; update the table, in response to an indication that an additional module, associated with a module identifier, is to be included in the modules, the updating of the table including determining a number of entries to add to the table for the additional module, calculating a first hash value for each of the number of entries, and modifying the table by writing the module identifier to one or more sequential entries of the table, beginning at an index into the table corresponding to the first hash value. The load balancer may additionally lookup one of the modules to handle a particular incoming client resource request, based on a second hash value obtained from information in the incoming client resource request, the second hash value being used as an index into the table to lookup the module identifier of the number of modules to handle the particular incoming client resource request."

For the URL and additional information on this patent, see: Hong, Xinhua; Wang, Hongbin; Zhang, Ying; Narayanaswamy, Krishna; Nair, Rakesh; Han, Henry. Server Load Balancing Using a Fair Weighted Hashing Technique. U.S. Patent Number 8762534, filed May 11, 2011, and published online on June 24, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8762534.PN.&OS=PN/8762534RS=PN/8762534

Keywords for this news article include: Juniper Networks Inc, Information Technology, Information and Data Storage.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Information Technology Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters