World-wide-web server that finds optimal path by sending multiple syn+;ack packets to a single client

• US 6,587,438 B1
• Filed: 12/22/1999
• Issued: 07/01/2003
• Est. Priority Date: 12/22/1999
• Status: Expired due to Term

• Current Assignee: Resonate (AEG Holdings, Inc.)
• Original Assignee: Resonate (AEG Holdings, Inc.)
• Inventors: Brendel, Juergen
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Fox, Jamal A.
• Application Number:
  US09/470,143
• Time in Patent Office: 1,287 Days
• Field of Search: 370/238, 370/229, 370/235, 370/232, 370/233, 370/234, 370/255, 370/256, 370/254, 370/389, 370/395.31, 370/395.32, 370/410, 370/395.2, 370/392, 370/238.1, 370/393.21
• US Class Current: 370/238
• CPC Class Codes: H04L 1/1858 Transmission or retransmission of more than one copy of acknowledgement message
• CPC Class Codes: H04L 43/091 Measuring contribution of individual network components to actual service level
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 5/1438 Negotiation of transmission parameters prior to communication modified according to link quality H04L1/0001
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

An optimal path through the Internet to a client is determined by the server during connection establishment. During the 3-way handshake that establishes a connection, a web server ordinarily sends a single SYN+ACK packet to the client. Instead of sending just one SYN+ACK packet, the server is modified to send multiple SYN+ACK packets, each using a different path to the client. When the multiple SYN+ACK packets are sent from the server at the same time, the first packet that reaches the client used the fastest path through the Internet. The client responds to this first SYN+ACK packet with an ACK packet back to the server. The other SYN+ACK packets that use slower paths arrive at the client after the first SYN+ACK packet and are ignored by the client as being out-of-order. The server includes a different sequence number with each SYN+ACK packet. The client increments this sequence number and includes the incremented sequence number in the ACK packet. The server reads this incremented sequence number in the ACK packet to determine which packet reached the client first. The path used by this packet is then included in source-routing fields of all future packets in the connection.

Claims

1. A method for establishing a new connection with a client over an optimal network path by a server that considers path delays comprising:

receiving an initial packet from the client, the initial packet requesting the new connection with the server;

generating multiple initial reply packets, each initial reply packet of the multiple initial reply packets traversing at least a portion of different network paths from the server to the client;

generating a plurality of packet identifiers, and writing a different packet identifier to each of the multiple initial reply packets;

transmitting from the server the multiple initial reply packets with different packet identifiers, the multiple initial reply packets reaching the client over different network paths;

receiving an acknowledgement packet from the client, the acknowledgement packet including a packet identifier that uniquely identifies a first packet, the first packet being one of the multiple initial reply packets;

selecting as the optimal network path the network path used by the first packet; and

specifying for the other packets sent to the client at least a portion of the optimal network path from the server to the client,

whereby the optimal network path is selected from among the different network paths of the multiple initial reply packets sent to the client by the acknowledgement packet from the client.

2. The method of claim 1 wherein the client ignores other packets of the multiple initial reply packets that arrive at the client after the first packet arrives at the client.

3. The method of claim 1 wherein the client generates additional packets to the server for each of the multiple initial reply packets that arrive at the client after the first packet arrives at the client;

wherein the server ignores the additional packets from the client during connection establishment.

4. The method of claim 1 wherein the packet identifier in the acknowledgement packet that uniquely identifies one of the multiple initial reply packets is an increment of the packet identifier for a first of the multiple initial reply packets to arrive at the client,

whereby the client generates the acknowledgement packet for the first packet of the multiple initial reply packets to arrive.

5. The method of claim 4 further comprising:

generating an initial sequence number in the client;

including the initial sequence number from the client in a sequence field of the initial packet;

the server incrementing the initial sequence number from the initial packet to generate an incremented client sequence number; and

the server writing the increment client sequence number to an acknowledgement sequence field of each of the multiple initial reply packets,

whereby a same acknowledgement sequence number is used in all of the multiple initial reply packets to the client.

6. The method of claim 5 further comprising:

generating an initial server sequence number for the server;

the server generating the different packet identifiers from the initial server sequence number;

the server writing the different packet identifiers to the sequence field of the multiple initial reply packets, wherein a different sequence number is written to each initial reply packet,

whereby different sequence numbers identify the multiple initial reply packets.

7. The method of claim 6 wherein the plurality of packet identifiers are server sequence numbers that are incremented for each data or SYN packet sent or received by the server.

8. The method of claim 1 wherein the initial packet is a TCP packet with a SYN flag that is set, but an ACK flag that is not set;

wherein each initial reply packet of the multiple is a TCP packet with a SYN flag that is set, and an ACK flag that is also set; and

wherein the acknowledgement packet is a TCP packet with a SYN flag that is not set, and an ACK flag that is also set,

whereby path measurement and selection is integral with a 3-way handshake to establish the new connection between the server and client.

9. The method of claim 8 wherein the different network paths from the server to the client are specified by source routing, by specifying a media-access-controller MAC address of a gateway, or by a tag for an intermediate network point.

10. The method of claim 8 wherein each of the multiple initial reply packets are transmitted from the server at substantially a same time,

wherein the optimal network path is a fastest path to the client.

11. The method of claim 8 wherein a subset of the multiple initial reply packets sent over less desirable network paths are sent after other initial reply packets sent through more desirable network paths,

whereby less desirable network paths are handicapped by delaying packet transmission.

12. A path-optimizing web server, the server comprising:

a network connection for receiving packets sent from a client over an Internet;

a sequence-number generator for generating an initial sequence number for a new connection;

a connection establisher that receives an initial packet from a client requesting a new connection with the server, the connection establisher generating several reply packets, each reply packet including;

a server sequence number generated from the initial sequence number, the server sequence number being different for each of the several reply packets;

wherein several of the reply packets are sent over different paths to the client in response to a single initial packet from the client;

a path selector, receiving a second packet from the client, the second packet being generated by the client in response to a first packet received by the client, the first packet being one of the reply packets that was received by the client before others of the reply packets, the path selector reading an acknowledgement sequence number generated by the client from the first packet;

wherein the path selector determines which of the several reply packets reached the client first by comparing the acknowledgement sequence number to the server sequence numbers of the several reply packets; and

a packet transmitter, generating other packets in the new connection to be sent to the client after the acknowledgement packet is received, the packet transmitter sending other packets on the path from the server to the client used by the first packet received by the client,

whereby the path-optimizing web server selects the path to the client by determining which of the several reply packets reached the client first.

13. The path-optimizing web server of claim 12 wherein the several reply packets are sent from the server at substantially a same time, but arrive at the client at different times due to varying path delays through the Internet,

whereby the first packet is sent over a fastest path of the different path to the client.

14. The path-optimizing web server of claim 13 wherein each reply packet further comprises:

a source-routing field with a list of addresses of intermediate routers on a path from the server to the client;

wherein each of the reply packets contains a different list of addresses of intermediate routers in the source-routing field;

wherein the path selector decrements the acknowledgement sequence number from the second packet to generate a decremented number, the path selector selecting the first packet as one of the several reply packets having a server sequence number that matched the decremented number,

whereby the server selects the optimal path using the server sequence number.

15. A computer-program product comprising:

a computer-usable medium having computer-readable program code means embodied therein for establishing a new connection at a server with a remote client over an optimal network path, the computer-readable program code means in the computer-program product comprising;

network connection means for transmitting and receiving packets from the remote client;

a server application, connected to the network connection means, for serving web pages to the remote client in response to requests from the remote client;

initial means for receiving an initial packet from the remote client, the initial packet requesting the new connection with the server;

multi-packet means for generating multiple initial reply packets, each of the multiple initial reply packets specifying at least a portion of different network paths from the server to the remote client;

multi-identifier means for generating a plurality of packet identifiers, and for writing a different packet identifier to each of the multiple initial reply packets;

multi-transmit means for transmitting from the server the multiple initial reply packets with different packet identifiers, the multiple initial reply packets reaching the remote client over different network paths;

acknowledgement means for receiving an acknowledgement packet from the remote client, the acknowledgement packet including a packet identifier that uniquely identifies a first packet, the first packet being one of the multiple initial reply packets;

select means for selecting as the optimal network path the network path used by the first packet; and

path means for specifying in the other packets sent to the remote client at least a portion of the optimal network path from the server to the remote client,

whereby the optimal network path is selected from among the different network paths of the multiple initial reply packets sent to the remote client by the acknowledgement packet from the remote client.

16. The computer-program product of claim 15 wherein the initial packet is a TCP packet with a SYN flag that is set, but an ACK flag that is not set;

wherein each of the initial reply packets is a TCP packet with a SYN flag that is set, and an ACK flag that is also set; and

wherein the acknowledgement packet is a TCP packet with a SYN flag that is not set, and an ACK flag that is also set,

whereby path measurement and selection is integral with a 3-way handshake to establish the new connection between the server and client.

17. The computer-program product of claim 16 wherein the plurality of packet identifiers are server sequence numbers that are incremented for each packet sent or received by the server.

18. The computer-program product of claim 16 wherein each of the multiple initial reply packets are transmitted from the server at substantially a same time,

wherein the optimal network path is a fastest path to the remote client.

19. The computer-program product of claim 15 wherein the computer-readable program code means further comprises:

handicap means for delaying a subset of the multiple initial reply packets sent over less desirable network paths, the subset being sent after other initial reply packets sent through more desirable network paths,

whereby less desirable network paths are handicapped by delaying packet transmission.

20. The computer-program product of claim 17 wherein the path means writes a list of intermediate IP addresses to headers of the other packets to specify at least a portion of the optimal network path from the server to the remote client, the intermediate IP addresses being Internet Protocol (IP) addresses of intermediate routers on the optimal path.