This invention relates to network routing, and more particularly to measurement and selection of network paths.
The Internet was designed from the beginning to be a de-centralized network providing many alternate connection paths. Failed nodes on the Internet can be routed around, ensuring that the network continues to operate even under the severest of situations.
Today""s commercial web sites often take advantage of this de-centralized topography. A web site may connect to the Internet through several different ports or gateways. Should one gateway fail, the web site remains accessible through the other gateways. Thus e-commerce may continue to operate despite equipment or network failures.
Communication between a client and a server is partitioned into packets that are sent over the Internet. These Internet Protocol (IP) packets are often sent and returned over the same path, although some web sites route outgoing packets through a different gateway. The IP packets contain a destination IP address. Intermediate routers along the path read the destination IP address and route the packet toward its destination. Intermediate routers typically choose the path with the fewest number of hops to the destination. Some routers may send packets over alternate routes when congestion is detected on the shortest route. However, this congestion-detection and re-routing is relatively localized to a small portion of the overall route.
Internet traffic patterns may change suddenly and without warning. A major news story develops, causing the routers and lines, which handle packets to news sites, to suddenly become overloaded, slowing down unrelated network traffic that passes through the same xe2x80x98areaxe2x80x99 of the Internet. A network provider may experience sudden technical difficulties and its network slows down. All clients connected to a web site through this provider""s network now suddenly experience a lower quality of service.
In today""s point-and-click economy, a consumer may not wait when web pages are slow to download. The consumer may simply move on to a competitor""s web site that is not experiencing slowness. Sales can be lost due to these temporary slowdowns caused by network congestion or failures. Sales are still lost even when the slowdowns or failures are not caused by the web site itself but are instead caused by intermediate network points.
The web site may exercise some control over the network path chosen. There are several ways to accomplish this. One control method is called IP source routing. When using IP source routing, a list of intermediate IP addresses can be included in the IP header of packets sent to the client. Intermediate routers then route the packet to the next IP address in the list. Such source-based routing allows a web site to choose the connection path to the client. Other methods to control the network path may be used, such as including the MAC address of a gateway in the packet header, or using tags that specify a network point. However, to choose the fastest path requires that the web site somehow measure delays within the Internet.
One method of measuring delays in a network path is by using a ping. A ping command causes a host to send one or more packets to a destination site. The destination site responds with an acknowledgement. The round-trip time of the packet and its acknowledgement packet can be measured. A related command, known as a trace route also sends multiple packets toward a destination. For a trace route, these packets have varying timeouts set that cause the packets to be returned to the host after different numbers of hops before reaching the destination. For example, one packet returns after 1 hop, another after 2 hops, a third after 3 hops, and others after 4, 5, and 6 hops. Another packet reaches the destination and returns. From the differences in round-trip delays, the host can calculate the delays between each of the intermediate routers and the number of hops to the destination.
FIG. 1 illustrates using a multi-cast ping to measure network delays. Server 12 connects to the Internet through gateway 14. Server 12 sends ping packets toward clients 10, 11, 13. The ping packets sent to client 10 reach intermediate router 22 after one hop, and after 2 hops reach router 24, and after 3 hops arrive at the client""s Internet Service Provider (ISP) 18. Client 10 responds to the ping packet with an acknowledgement packet sent to server 12 through ISP 18 and intermediate routers 22, 24. The overall delay is measured by the server from the round-trip delay of the ping packet.
Likewise, ping packets are also sent to client 11, through router 21 and ISP 17. Ping packets sent to client 13 are received by ISP 19 through routers 26, 25, but ISP 19 returns packets over a different route using routers 28, 23.
By periodically multicasting pings to clients 10, 11, 13, server 12 can detect slow parts of the Internet. See U.S. Pat. No. 5,727,002 by Miller et al., and assigned to Starburst Communications Corp.
Such ping multicasting to multiple clients is useful when the clients pinged are the ones being connected to. When other clients that are not pinged connect, information about routes to those clients may be incomplete. Multicasting to multiple clients, including clients that are not currently connected, is wasteful and creates network congestion itself. Furthermore, generating multiple ping packets to many different clients may raise security concerns with various ISPs, since they may be misunderstood as a possible beginning of a hacker attack. Also, it may not be known which clients will later connect to a web site.
FIG. 2 shows network monitoring. Another approach is to directly monitor one or more of the intermediate routers or network nodes. See U.S. Pat. No. 5,898,668 by Shaffer. Monitor 20 continuously monitors network traffic loads at routers 21, 22, 24. Server 12 can receive status reports from monitor 20 and route packets to the least-loaded of routers 21, 22, 24. For example, router 21 may be lightly loaded, and server 12 connects to client 10 and its ISP 18 using router 21 rather than routers 22, 24.
However, such network monitoring is rather limited. Monitor 20 does not monitor other network nodes, such as routers 23, 25, 26, 28. These routers may be on a more direct path to client 10, or may be along the only path to client 10. Since monitor 20 does not monitor these nodes, the best path among routers 23, 25, 26, 28 cannot be determined.
Such network monitoring requires specialized hardware or software that is not available on most Internet routers. Often only the nodes near a gateway are monitored. Thus such monitoring is limited at best.
While such methods of measuring speeds of Internet connections are useful, neither is ideal for standard client connections to a web-site. Multicasting to multiple clients is undesirable since network traffic is increased. Since knowledge of which of millions of clients will later connect to a public web site is often unobtainable, prior multicasting has limited utility for a web site. Measurements may not be useful when connecting to a client that was not multicasted to. Monitoring is limited to relatively few sites on the Internet and does not measure delays along the entire path to an arbitrary client. It is undesirable to add special multicasting or monitoring software to various sites. Continuous monitoring or multicasting is undesirable as it increases system overhead and network traffic. Monitoring devices may not measure actual packet delays, but rather measure node-specific parameters such as link or buffer loading.
What is desired is a network measurement that measures actual network delays to a client. It is desired to measure delays only when a new connection with a client is established. It is desired to avoid continuous monitoring. It is further desired to use standard network software without modifying intermediate network nodes. It is also desired to modify only the server software while not modifying the client. A network speed measurement is desired that measures delays to any arbitrary client with standard TCP/IP software. It is further desired to measure delays for multiple paths to a single client and to choose the fastest path for a new connection between a server and the client. Client-specific measurement for routing selection is desired.
A method is for establishing a new connection with a client over an optimal network path by a server that considers path delays. An initial packet is received from the client. The initial packet requests the new connection with the server. Multiple initial reply packets are generated. Each initial reply packet of the multiple initial reply packets traverses at least a portion of different network paths from the server to the client.
A plurality of packet identifiers are generated. A different packet identifier is written to each of the multiple initial reply packets. The multiple initial reply packets with different packet identifiers are transmitted from the server. The multiple initial reply packets reach the client over different network paths.
An acknowledgement packet is received from the client. The acknowledgement packet includes a packet identifier that uniquely identifies a first packet. The first packet is one of the multiple initial reply packets.
The network path used by the first packet is selected as the optimal network path. At least a portion of the optimal network path from the server to the client is specified for the any future packets sent to the client. Thus the optimal network path is selected from among the different network paths of the multiple initial reply packets sent to the client in response to the acknowledgement packet from the client.
In further aspects the client ignores other packets of the multiple initial reply packets that arrive at the client after the first packet arrives at the client, or 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.
In still further aspects, the plurality of packet identifiers are server sequence numbers that are incremented for each data or SYN packet sent or received by the server.
In still further aspects, the initial packet is a TCP packet with a SYN flag that is set, but an ACK flag that is not set. 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. The acknowledgement packet is an IP packet with a SYN flag that is not set, and an ACK flag that is also set. Thus path measurement and selection is integral with a 3-way handshake to establish the new connection between the server and client.
USPTO Backgrounds
USPTO Backgrounds