Take the 2-minute tour ×
Ask Patents is a question and answer site for people interested in improving and participating in the patent system. It's 100% free, no registration required.

AN OVERBROAD PATENT ON BALANCING WEB TRAFFIC DISTRIBUTION - This patent from Microsoft seeks to patent the idea of using multiple load balancers with a shared virtual IP address to distribute website traffic loads.

TITLE: LOAD BALANCING ACROSS LAYER-2 DOMAINS

Summary: The present application relates to network configurations and specifically to scalable load balancing network configurations. One implementation includes an external client coupled to a scalable load balancing system. The scalable load balancing system includes a load balancing layer that is configured to encapsulate individual incoming packets of a packet flow from the external client. The load balancing layer is further configured to route the incoming packets to target devices on the system. The target devices can span multiple IP subnets. The incoming packets can pass through one or more load balancers of the load balancing layer before reaching individual target devices. Individual target devices can be configured to route at least some outgoing packets of the packet flow to the external client without passing through any of the one or more load balancers.

Translated from legalese: Microsoft is attempting to patent a system that comprises multiple load balancing servers that share a common virtual IP address that use a consistent hashing algorithm and IP-in-IP tunneling to distribute incoming traffic to a larger set of application servers.

There are multiple claims in the patent, all of which appear to be common features of existing load balancing and routing products. It's unclear to me whether the claim is over all of the below features, or only when they are all used in combination. The features are:

  • Equal-cost multi path routing to multiple load balancing servers that share a common IP address. Also known as "anycast" routing.
  • Use of a consistent hashing algorithm on a load balancing server to deterministically choose a destination server for any given incoming packet.
  • Encapsulation of incoming packets via IP-in-IP tunneling when forwarding to the application server.
  • The ability of the application server to respond directly to the client, using the original VIP IP address seen in the encapsulated packet as a source address. Also known as Layer 3 Direct Server Return.

Good prior art would be documentation of a system that supports any or all of the above features dating prior to May 28, 2009.

share|improve this question
    
Hi Alan, AskPatents is an online service in Q&A format where users help find prior art on US Patent Applications and US Patents and ask questions about the US Patent process. Questions about international patents are outside the scope of the Ask Patents site. I have modified the question to refer to US 8,416,692, which is the US patent family Member of WO2010138936 A3. If this isn't what you intended feel free to modify the question. Please see faq for more information about which topics are on topic for AskPatents. Sorry for any confusion. –  Micah Siegel Aug 5 '13 at 3:28
    
Related? security.stackexchange.com/q/29696/3290. –  TRiG Oct 14 '13 at 14:46
    
Is this site US-only, @MicahSiegel? That seems to contradict what was said on Meta. –  TRiG Oct 14 '13 at 14:49
add comment

4 Answers

The technique of consistent hashing was invented by Karger et al in their famous 1997 paper, "Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web":
http://dl.acm.org/citation.cfm?id=258660
http://thor.cs.ucsb.edu/~ravenben/papers/coreos/kll+97.pdf
It is to them that the claim of novelty and non-obviousness belongs. The "Use of a consistent hashing algorithm" claim in this patent is an obvious and non-novel repetition of their pioneering work.

The authors directly anticipate the "Use of a consistent hashing algorithm" claim in their conclusions:

This paper has focused on one particular caching problem—that of handling read requests on the Web. We believe the ideas have broader applicability. In particular , consistent hashing may be a useful tool for distributing information from name servers such as DNS and label servers such as PICS in a load-balanced and fault- tolerant fashion.

So load balancing server requests with consistent hashing was proposed in this 1997 paper. I find it curious that this very easy-to-find paper was not mentioned in the prior art section on the patent.

share|improve this answer
add comment

Breaking down the four bullets you highlighted:

Equal-cost multi path routing to multiple load balancing servers that share a common IP address. Also known as "anycast" routing.

This Amazon EC2 Article from 2008 explains how to setup two HAProxy servers with heartbeat - basically meaning if one fails it can take the other one's IP address - which is essentially sharing a common IP address.

Use of a consistent hashing algorithm on a load balancing server to deterministically choose a destination server for any given incoming packet.

Using "ip hash" load balancing with src-mac on the Ciscos from 2008.

Encapsulation of incoming packets via IP-in-IP tunneling when forwarding to the application server.

Is this not the definition of what iptables does?

The ability of the application server to respond directly to the client, using the original VIP IP address seen in the encapsulated packet as a source address. Also known as Layer 3 Direct Server Return.

IPTables does this too, I believe

Does this help?

share|improve this answer
add comment

Here's a reference to an implementation of Layer 3 DSR (although not referred to by that name), via the same IP-in-IP tunneling mechanism that the patent describes; there are also alternative L3DSR techniques not mentioned in this patent. This has been a feature of the Linux kernel's LVS subsystem since 2003. http://www.ultramonkey.org/papers/lvs_tutorial/html/

share|improve this answer
add comment

Not an answer but I hope it is helpful - the applicant made the examiner aware of several patent documents and many more journal articles regarding load balancing. They are listed on the front page of the US granted patent. Presumably you are looking for prior art not on this list that is more targeted than anything that is already known to the examiner. Documents already considered by the examiner are still fair game if you can identify specific things in the the examiner missed.

For a full history of the back-and-forth between the applicant and the examiner the whole history can be looked up on the USPTO Private PAIR site. This is one of the pages of the IDS:

enter image description here

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.