Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-12-22
2003-07-01
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S254000
Reexamination Certificate
active
06587438
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to network routing, and more particularly to measurement and selection of network paths.
BACKGROUND OF THE INVENTION
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 ‘area’ 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 m
Auvinen Stuart T.
Chin Wellington
Fox Jamal A.
Resonate Inc.
LandOfFree
World-wide-web server that finds optimal path by sending... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with World-wide-web server that finds optimal path by sending..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and World-wide-web server that finds optimal path by sending... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3032074