Hash-based Load Balancing (Microsoft) - Issued Patent - PRIOR ART REQUEST

Question

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.

• Publication Number: US Patent 8,416,692

• Related Family Member: Patent Application WO2010138936 A3

• Assignee: Microsoft, Inc.

• Prior Art Date: Seeking Prior Art predating May 28, 2009

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.

Answer 1

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.

Answer 2

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?

Answer 3

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/

Answer 4

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: