Distributed network traffic load balancing technique implemented without gateway router
First Claim
1. A method for routing traffic in a data network, the data network including a sub-network of client servers which include information corresponding to information stored on at least one host server, the method comprising:
- receiving, at a first device, a first packet from a source device destined to a host server;
identifying the source device using information from the first packet;
selecting, using the identified source device information, a first portion of the client servers for forwarding information relating to the first packet, wherein the first portion includes two or more client servers;
forwarding information relating to the first packet from the first device to the first portion of the client servers;
causing each of the first potion of client servers to respond to the source device at substantially the same time, wherein said causing is performed by the first devices;
determining a specific trigger time reference value for causing each of the first portion of client servers to transmit a respective spoofed response to the first request at a time corresponding to the trigger time reference value; and
transmitting said trigger time reference value to each of the first portion of client servers along with the forwarded first request information to thereby cause each of the first portion of client servers to transmit a respective response to the source device at substantially the same time.
1 Assignment
0 Petitions
Accused Products
Abstract
The technique of the present invention provides a solution to the problem of routing or redirecting a given client to a replica or proxy server which has a relatively shortest propagation delay to the client. According to the technique of the present invention, a network device referred to as an intercept server sits in front of a host server, and intercepts packets routed to the host server. When desired, packets which are intercepted by the intercept server are replicated, encapsulated and tunneled to selected client servers in the overlay network. The tunneled packets are received and processed by each of the selected client servers, whereupon each of the selected client servers generates a respective spoofed response to the source device identified in the header of the originally intercepted packet. Further, according to the technique of the present invention, each of the selected client servers transmits its respective spoofed response to the identified source device at substantially the same time. The client server associated with the spoofed response which is first received at the identified source device is considered to have the relatively shortest propagation delay to the identified source device, and is identified as the successful client server. Thereafter, the source device will be directed or redirected to communicate directly with the successful client server when subsequently attempting to access information from the host server.
-
Citations
76 Claims
-
1. A method for routing traffic in a data network, the data network including a sub-network of client servers which include information corresponding to information stored on at least one host server, the method comprising:
-
receiving, at a first device, a first packet from a source device destined to a host server;
identifying the source device using information from the first packet;
selecting, using the identified source device information, a first portion of the client servers for forwarding information relating to the first packet, wherein the first portion includes two or more client servers;
forwarding information relating to the first packet from the first device to the first portion of the client servers;
causing each of the first potion of client servers to respond to the source device at substantially the same time, wherein said causing is performed by the first devices;
determining a specific trigger time reference value for causing each of the first portion of client servers to transmit a respective spoofed response to the first request at a time corresponding to the trigger time reference value; and
transmitting said trigger time reference value to each of the first portion of client servers along with the forwarded first request information to thereby cause each of the first portion of client servers to transmit a respective response to the source device at substantially the same time. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
assigning a unique starting sequence number to each of the first portion of client servers, wherein each starting sequence number corresponds to a SYN, ACK segment of a TCP protocol, wherein the assigning is performed by the intermediary device.
-
-
3. The method of claim 2 further comprising causing each of the first portion of client servers to include its assigned starting sequence number in its response transmitted to the source device.
-
4. The method of claim 1 wherein the source device corresponds to a client system.
-
5. The method of claim 1 wherein said forwarding further includes:
-
encapsulating the received first packet in accordance with an encapsulation tunneling protocol; and
transmitting the encapsulated packet to each of the first portion of client servers using the encapsulation tunneling protocol.
-
-
6. The method of claim 5 further comprising:
-
receiving, at a first client server, the encapsulated packet;
generating, at said first client server using information from said received encapsulated packet, a first spoofed response to said first packet; and
transmitting said first spoofed response to the source device.
-
-
7. The method of claim 6 wherein the first packet utilizes a TCP protocol, and wherein the first spoofed response comprises a TCP acknowledgement segment having an associated sequence number, the sequence number including information relating to an identity of the first client server.
-
8. The method of claim 1 further comprising determining a respective propagation delay value associated with communicating with each client server of at least the first portion of client servers;
- and
using the propagation delay information to forward the information relating to the first packet to the first portion such that the forwarded first packet information is received at each of the first portion of client servers at substantially the same time.
- and
-
9. The method of claim 1 further comprising:
-
receiving, at the source device, a plurality of responses to the first packet from at least some of the first portion of client servers;
processing an earliest received response of the plurality of received responses in accordance with a first technique, wherein said first technique includes using information from the earliest received response at the source device to conduct subsequent communication transactions; and
processing at least one duplicate responses to the first packet in accordance with a second technique, wherein said second technique includes not using information from the at least one duplicate received response at the source device to conduct subsequent communication transactions.
-
-
10. The method of claim 9 wherein said plurality of responses are received using a TCP protocol.
-
11. The method of claim 1:
-
wherein said selecting includes identifying at least one preferred client server associated with the identified source device; and
wherein said first plurality of client servers includes said at least one preferred client server and at least one randomly selected client server from the sub-network.
-
-
12. The method of claim 11 further comprising:
-
identifying a successful client server of said first portion of client servers associated with generating a response to the first packet which was first received at the source device; and
if the identified client server is not classified as a preferred client server for communicating with the identified source device, classifying the identified client server as one of the at least one preferred client servers for communicating with the identified source device.
-
-
13. The method of claim 12 further comprising selecting a least preferred one of the at least one preferred client servers for preferred status degradation in response to the identified client server being classified as a preferred client server.
-
14. The method of claim 1 wherein the first packet utilizes a TCP protocol, the method further comprising:
-
receiving a TCP acknowledgement (ACK) segment from the source device, said ACK segment having an associated sequence number which includes information relating to an identity of a successful client server of the first plurality of client servers which generated a response to the forwarded first packet information that was first received at the source device;
identifying the successful client server using information from the received ACK segment;
encapsulating the received ACK segment in accordance with an encapsulation tunneling protocol; and
transmitting, using the encapsulation tunneling protocol, the encapsulated packet to the successful client server.
-
-
15. The method of claim 14 further comprising issuing a TCP reset packet to each of the other client servers of the first portion of client servers which are not identified as the successful client server.
-
16. The method of claim 1 further comprising:
-
identifying a successful client server of said first portion of client servers associated with generating a response to the first packet which was first received at the source device;
receiving a second packet from said source device, said second packet relating to a request to access data from said host server;
encapsulating the second packet;
tunneling the encapsulated second packet to the successful client server;
generating, at the successful client server, a spoofed response to the source device, wherein the spoofed response includes a redirect response.
-
-
17. A method for routing traffic in a data network, the data network including a sub-network of client servers which include information corresponding to information stored on at least one host server, the method comprising:
-
receiving, at a first client server, a tunneled packet and timing information from an intercept server, said tunneled packet including encapsulated information relating to a first packet intercepted by the intercept server, said first packet including a source address and a destination address, said source address corresponding to a source device which generated the first packet, said first packet information relating to a request to open a communication connection with a host server;
generating, at said first client server using information from said received tunneled packet, a first spoofed response to said request, wherein the first spoofed response includes information for identifying the first client server; and
transmitting said first spoofed response to the source device so that the first spoofed response is transmitted at a time specified by the timing information received from the intercept server. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26)
receiving, at a second client server, a tunneled packet from the intercept server, said tunneled packet including encapsulated information relating to a first packet intercepted by the intercept server, said first packet including a source address and a destination address, said source address corresponding to a source device which generated the first packet, said first packet information relating to a request to open a communication connection with a host server;
generating, at said first client server using information from said received tunneled packet, a second spoofed response to said request, wherein the second spoofed response includes information for identifying the second client server; and
transmitting said second spoofed response to the source device at substantially a same time that said first spoofed response is transmitted to the source device.
-
-
24. The method of claim 23 wherein the first packet corresponds to a SYN segment of a communication utilizing a TCP protocol, and wherein the second spoofed response comprises a SYN, ACK segment which includes a second sequence number, the second sequence number including information relating to an identity of the second client server.
-
25. The method of claim 17 wherein the tunneled packet includes information relating to a specific trigger time for transmitting a response to the source device;
wherein said transmitting includes transmitting the first and second spoofed responses from each respective client server to the source device at a time value corresponding to the specific trigger time.
-
26. The method of claim 25 further comprising synchronizing said intercept server, said first client servers and said second client server.
-
27. A method for routing traffic in a data network, the data network including a sub-network of client servers which include information corresponding to information stored on at least one host server, the method comprising:
-
receiving, at a first plurality of client servers, a respective tunneled packet and timing information from an intercept server, said tunneled packet including encapsulated information relating to a first packet intercepted by the intercept server, said first packet including a source address and a destination address, said source address corresponding to a source device which generated the first packet, said first packet information relating to a request to open a communication connection with a host server;
generating, at each of the first plurality of client servers a respective spoofed response to said first packet using information from said received tunneled packet, wherein the each spoofed response includes information for identifying a client server which generated the spoofed response; and
transmitting each of the respective spoofed responses at substantially a same time to the source device as specified by the timing information received from the intercept server. - View Dependent Claims (28, 29, 30)
receiving, at the source device, a plurality of responses to the first packet from at least some of the first portion of servers;
processing an earliest received response of the plurality of received responses in accordance with a first technique, wherein information from the earliest received response is used by the source device to conduct subsequent communication transactions; and
processing at least one duplicate responses to the first packet in accordance with a second technique, wherein information from the at least one duplicate received response is not used by the source device to conduct subsequent communication transactions.
-
-
29. The method of claim 28 wherein said plurality of responses are received using a TCP protocol.
-
30. The method of claim 28:
-
wherein the first packet corresponds to a SYN record query for a specific domain name;
wherein the source device includes a client for receiving the plurality of responses; and
wherein said processing includes;
determining, using information from said earliest received response, a specific IP address associated with the specific domain name, the specific IP address corresponding to a successful server which transmitted the earliest received response; and
binding the specific IP address with the specific domain name.
-
-
31. A computer program product for routing traffic in a data network, the data network including a sub-network of client servers which include information corresponding to information stored on at least one host server, the computer program product comprising:
-
a computer usable medium having computer readable code embodied therein, the computer readable code comprising;
computer code for receiving, at a first device, a packet from a source device destined to a host server;
computer code for identifying the source device using information from the first packet;
computer code for selecting, using the identified source device information, a first portion of the client servers for forwarding the first packet, wherein the first portion includes two or more client servers;
computer code for forwarding information from the first device relating to the first packet to the first portion of the client servers; and
computer code for causing each of the first potion of client servers to respond to the source device at substantially the same time, wherein said causing is performed by the first devices computer code for determining a trigger time value for causing each of the first portion of client servers to transmit a respective response to the first packet at the specified trigger time; and
computer code for transmitting said trigger time value to each of the first portion of client servers along with the forwarded first packet information to thereby cause each of the first portion of client servers to transmit a respective response to the source device at substantially the same time. - View Dependent Claims (32)
wherein said forwarding computer code includes computer code for transmitting said first packet information to each of the first portion of client servers at specific times such that the forwarded first packet information is received at each of the first portion of client servers at substantially the same time.
-
-
33. A computer program product for routing traffic in a data network, the data network including a sub-network of client servers which include information corresponding to information stored on at least one host server, the computer program product comprising:
-
a computer usable medium having computer readable code embodied therein, the computer readable code comprising;
computer code for receiving, at a first client server, a tunneled packet and timing information from an intercept server, said tunneled packet including information relating to a request from a source device to open a communication connection with a host server;
computer code for generating, at said first client server using information from said received tunneled packet, a first spoofed response to said first packet; and
computer code for transmitting said first spoofed response to the source device so that the age first spoofed response is transmitted at a time specified by the timing information received from the intercept server. - View Dependent Claims (34)
computer code for receiving, at a second client server, a tunneled packet from said intercept server, said tunneled packet including information relating to a request from a source device to open a communication connection with a host server;
computer code for generating, at said second client server using information from said received tunneled packet, a second spoofed response to said first packet;
computer code for transmitting said second spoofed response to the source device at substantially the same time that said first spoofed response is transmitted to the source device.
-
-
35. A system for facilitating a client device to access a specific server in a data network, the system comprising:
-
a sub-network of client servers which include information corresponding to information stored on at least one host server; and
at least one intercept server configured or designed to intercept at least one packet routed to the at least one host server, said intercept server being further configured or designed to identify a source device associated with generating the intercepted packet;
said intercept server being further configured or designed to forward information relating to the first packet to a selected portion of the client servers, wherein the first portion includes two or more client servers;
said intercept server being further configured or designed to cause each of the selected potion of client servers to respond to the source device at substantially the same times, wherein said intercept server is further configured or designed to determine a trigger time value for cause each of the selected portion of client servers to transmit a respective response to the first packet at the specified trigger time, and is further configured or designed to transmit said trigger time value to each of the selected portion of client servers along with the forwarded first packet information to thereby cause each of the selected portion of client servers to transmit a respective response to the source device at substantially the same time. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44, 45)
wherein said first plurality of client servers includes said at least one preferred client server and at least one randomly selected client server associated with the sub-network.
-
-
41. The system of claim 40 wherein said intercept server is further configured or designed to identify a successful client server of said selected portion of client servers associated with generate a response to the first packet which was first received at the source device, and is further configured or designed to classify the identified client server as one of the at least one preferred client servers for communicate with the identified source device if the identified client server is not classified as a preferred client server for communicate with the identified source device, classify the identified client server as one of the at least one preferred client servers for communicate with the identified source device.
-
42. The system of claim 41 wherein said intercept server is further configured or designed to select a least preferred one of the at least one preferred client servers for preferred status degradation in response to the identified client server bee classified as a preferred client server.
-
43. The system of claim 35 wherein the intercept server is configured or designed to communicate with the source device using a TCP protocol,
said intercept server being further configured or designed to receive a TCP acknowledgement (ACK) segment from the source device, said ACK segment having an associated sequence number which includes information relating to an identity of a successful client server of the first plurality of client servers which generated a response to the forwarded first packet that was first received at the source device; -
said intercept server being further configured or designed to identify the successful client server use information from the received ACK segment;
said intercept server being further configured or designed to encapsulate the received ACK segment in accordance with an encapsulation tunneling protocol; and
said intercept server being further configured or designed to transmit, using the encapsulation tunneling protocol, the encapsulated packet to the successful client server.
-
-
44. The system of claim 43 wherein said intercept server is further configured or designed to issue a TCP reset packet to each of the other client servers of the selected portion of client servers which were not identified as the successful client server.
-
45. The system of claim 35 further wherein said intercept server is further configured or designed to identify a successful client server of said selected portion of client servers associated with generate a response to the first packet which was first received at the source device;
-
said intercept server being further configured or designed to receive a second packet from said source device to access data from said host server;
said intercept server being further configured or designed to encapsulate the second first packet;
said intercept server being further configured or designed to tunnel the encapsulated first packet to the successful client server;
wherein said successful client server is configured or designed to generate a spoofed response to the source device, wherein the spoofed response includes a redirect packet.
-
-
46. A network device comprising:
-
at least one CPU;
memory, said memory including a first portion of memory configured or designed to store information associated with at least one host server in a data network; and
at least one interface for receiving a tunneled packet and timing information from an intercept server, said tunneled packet including encapsulated information relating to a first packet intercepted by the intercept server, said first packet including a source address and a destination address, said source address corresponding to a source device associated with generating the first packet, said first packet information relating to a request to open a communication connection with a host server;
said network device being configured or designed to generate, using information from said received tunneled packet, a first spoofed response to said request, wherein the first spoofed response includes information for identifying the first client server;
said network device being further configured or designed to transmit said first spoofed response to the source device so that the first spoofed response is transmitted at a time specified by the timing information received from the intercept server. - View Dependent Claims (47, 48, 49)
-
-
50. A system for routing traffic in a data network, the data network including at least one host server and an intercept server configured or designed to intercept packets directed to the at least one host server, the system comprising:
-
a plurality of client servers configured or designed to store information corresponding to information stored on the at least one host server;
wherein the plurality of client servers includes;
a first client server configured or designed to receive a tunneled packet and timing information from the intercept server, said tunneled packet including information relating to a request from a source device to open a communication connection with a host server;
the first client server being further configured or designed to generate, using information from the received tunneled packet, a first spoofed response to said first packet; and
wherein the first client server is further configured or designed to transmit said first spoofed response to the source device so that the first spoofed response is transmitted at a time specified by the timing information received from the intercept server. - View Dependent Claims (51, 52, 53, 54, 55)
said source device being further configured or designed to process an earliest received response of the plurality of received responses in accordance with a first technique, wherein information from the earliest received response is used by the source device to conduct subsequent communication transactions; and
wherein said source device is further configured or designed to process at least one duplicate responses to the first packet in accordance with a second technique, wherein information from the at least one duplicate received response is not used by the source device to conduct subsequent communication transactions.
-
-
54. The system of claim 53
wherein the first packet corresponds to a SYN record query for a specific domain name; -
wherein the source device includes a client for receiving the plurality of responses; and
wherein the client is configured or designed to determine, using information from said earliest received response, a specific IP address associated with the specific domain name, the specific IP address corresponding to a successful server which transmitted the earliest received response; and
wherein the client is further configured or designed to bind the specific IP address with the specific domain name.
-
-
55. The system of claim 53 wherein said source device is configured or designed to communicate using a TCP protocol.
-
56. A system for routing a client device to access a specific server in a data network, the system comprising:
-
a sub-network of client servers which include information corresponding to information stored on at least one host server; and
at least one intercept server configured or designed to intercept at least one packet routed to the at least one host server, the intercepted packet including information for identifying a source device associated with the packet, the intercept server being further configured or designed to forward information relating to the intercepted packet and timing information to a selected portion of the client servers in the sub-network, wherein the selected portion includes two or more client servers;
wherein each of the selected portion of client servers is configured or designed to transmit, at substantially the same time based on the received timing information from the intercept server, a respective spoofed response to the source device, wherein each spoofed response is generated using information from the intercepted packet. - View Dependent Claims (57, 58, 59)
wherein the intercept server is further configured or designed to determine a successful client server associated with generating a particular spoofed response which was received first at the source device, the successful client server being one of the selected portion of client servers, and is further configured or designed to bind an ID of the source device with an ID of the successful client server device. -
58. The system of claim 57 further wherein the system is configured or designed to cause the source device to communicate with the successful client server for accessing information associated with the at least one host server.
-
59. The system of claim 57 wherein the intercepted packet corresponds to a SYN segment for a communication with the at least one host server utilizing a TCP protocol, and wherein each spoofed response comprises a SYN, ACK segment which includes a sequence number relating to an identity of a client server generating the spoofed response.
-
-
60. A system for routing traffic in a data network, the data network including a sub-network of client servers which include information corresponding to information stored on at least one host server, the system comprising:
-
means for receiving, at a first client server, a tunneled packet and timing information from an intercept server, said tunneled packet including encapsulated information relating to a first packet intercepted by the intercept server, said first packet including a source address and a destination address, said source address corresponding to a source device which generated the first packet, said first packet information relating to a request to open a communication connection with a host server;
means for generating, at said first client server using information from said received tunneled packet, a first spoofed response to said request, wherein the first spoofed response includes information for identifying the first client server; and
means for transmitting said first spoofed response to the source device so that the first spoofed response is transmitted at a time specified by the timing information received from the intercept server.
-
-
61. A method for routing traffic in a data network, the data network including a sub-network of client servers which include information corresponding to information stored on at least one host server, the method comprising:
-
receiving, at a first device, a first packet from a source device destined to a host server;
identifying the source device using information from the first packet;
selecting, using the identified source device information, a first portion of the client servers for forwarding information relating to the first packet, wherein the first portion includes two or more client servers;
forwarding information relating to the first packet from the first device to the first portion of the client servers;
causing each of the first potion of client servers to respond to the source device at substantially the same time, wherein said causing is performed by the first device;
determining a respective propagation delay value associated with communicating with each client server of at least the first portion of client servers;
using the propagation delay information to generate a respective transmission delay time value for each of the first portion of client servers; and
transmitting said transmission delay time values to each respective client server of the first portion of client servers along with the forwarded first request information to thereby cause each of the first portion of client servers to delay transmission of its respective spoofed response to the source device until a time period corresponding to the transmission delay time value has elapsed. - View Dependent Claims (62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76)
assigning a unique starting sequence number to each of the first portion of client servers, wherein each starting sequence number corresponds to a SYN, ACK segment of a TCP protocol, wherein the assigning is performed by the intermediary device.
-
-
63. The method of claim 62 further comprising causing each of the first portion of client servers to include its assigned starting sequence number in its response transmitted to the source device.
-
64. The method of claim 61 wherein the source device corresponds to a client system.
-
65. The method of claim 61 wherein said forwarding further includes:
-
encapsulating the received first packet in accordance with an encapsulation tunneling protocol; and
transmitting the encapsulated packet to each of the first portion of client servers using the encapsulation tunneling protocol.
-
-
66. The method of claim 65 further comprising:
-
receiving, at a first client server, the encapsulated packet;
generating, at said first client server using information from said received encapsulated packet, a first spoofed response to said first packet; and
transmitting said first spoofed response to the source device.
-
-
67. The method of claim 66 wherein the first packet utilizes a TCP protocol, and wherein the first spoofed response comprises a TCP acknowledgement segment having an associated sequence number, the sequence number including information relating to an identity of the first client server.
-
68. The method of claim 61 further comprising determining a respective propagation delay value associated with communicating with each client server of at least the first portion of client servers;
- and
using the propagation delay information to forward the information relating to the first packet to the first portion such that the forwarded first packet information is received at each of the first portion of client servers at substantially the same time.
- and
-
69. The method of claim 61 further comprising:
-
receiving, at the source device, a plurality of responses to the first packet from at least some of the first portion of client servers;
processing an earliest received response of the plurality of received responses in accordance with a first technique, wherein said first technique includes using information from the earliest received response at the source device to conduct subsequent communication transactions; and
processing at least one duplicate responses to the first packet in accordance with a second technique, wherein said second technique includes not using information from the at least one duplicate received response at the source device to conduct subsequent communication transactions.
-
-
70. The method of claim 69 wherein said plurality of responses are received using a TCP protocol.
-
71. The method of claim 61
wherein said selecting includes identifying at least one preferred client server associated with the identified source device; - and
wherein said first plurality of client servers includes said at least one preferred client server and at least one randomly selected client server from the sub-network.
- and
-
72. The method of claim 71 further comprising:
-
identifying a successful client server of said first portion of client servers associated with generating a response to the first packet which was first received at the source device; and
if the identified client server is not classified as a preferred client server for communicating with the identified source device, classifying the identified client server as one of the at least one preferred client servers for communicating with the identified source device.
-
-
73. The method of claim 72 further comprising selecting a least preferred one of the at least one preferred client servers for preferred status degradation in response to the identified client server being classified as a preferred client server.
-
74. The method of claim 61 wherein the first packet utilizes a TCP protocol, the method further comprising:
-
receiving a TCP acknowledgement (ACK) segment from the source device, said ACK segment having an associated sequence number which includes information relating to an identity of a successful client server of the first plurality of client servers which generated a response to the forwarded first packet information that was first received at the source device;
identifying the successful client server using information from the received ACK segment;
encapsulating the received ACK segment in accordance with an encapsulation tunneling protocol; and
transmitting, using the encapsulation tunneling protocol, the encapsulated packet to the successful client server.
-
-
75. The method of claim 74 further comprising issuing a TCP reset packet to each of the other client servers of the first portion of client servers which are not identified as the successful client server.
-
76. The method of claim 61 further comprising:
-
identifying a successful client server of said first portion of client servers associated with generating a response to the first packet which was first received at the source device;
receiving a second packet from said source device, said second packet relating to a request to access data from said host server;
encapsulating the second packet;
tunneling the encapsulated second packet to the successful client server;
generating, at the successful client server, a spoofed response to the source device, wherein the spoofed response includes a redirect response.
-
Specification