Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2001-07-27
2004-08-17
Marcelo, Melvin (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S248000, C370S252000
Reexamination Certificate
active
06778502
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer networks, and more specifically to a mechanism for finding improved communication paths through a heterogeneous computer network by means of an overlay network.
BACKGROUND AND PRIOR ART
The Internet today consists of a collection of interconnected administrative domains. Each domain is under the control of one or more administrators who decide what hardware equipment to employ and what control software to run. This localized control of the administrative domains requires the coexistence of a number of disparate, heterogeneous systems. The basic communication protocol through which different domains communicate is IP (Internet Protocol). Each Internet data communication is translated into the delivery of a sequence of varying sized IP protocol packets that travel across one or more administrative domains until they reach the final destination.
In IP, the sender of the data only specifies the destination address, whereas the network (the collection of hardware and software systems distributed through several administrative domains) chooses a forwarding path through which to route the IP packets. Routing protocols cooperate across different administrative domains, and through a variety of different software and hardware techniques, to monitor the presence and/or the state of connections in the Internet. Because of the great size and heterogeneous nature of the Internet, and the complexity of the routing task, these routing protocols are typically minimalistic and tend to focus on guarantee of connection and minimizing routing hops rather than optimizing performance. The result, among other problems, is the familiar, frustrating user experience of protracted delay when attempting to access information through the World Wide Web, particularly during periods of heavy usage.
Many proposals to improve the utilization of the Internet exist and feature a wide variety of sophistication and/or response time in changing forwarding paths and thus providing the best routing performance. In practice, these proposals are hardly being used because it is very hard to coordinate their deployment into the Internet. Inter-operation among different administrative domains is crucial and any change to the protocols affecting the forwarding paths may greatly affect the availability of connections. As a result, in practice the forwarding paths between endpoints are determined using very simplistic cost functions and/or heuristics and/or manual intervention. This scheme tends to greatly under-utilize the networks. Depending on local configurations, when faults occur, previously chosen forwarding paths that experience a breakage will be followed for several minutes or hours until the fault is remedied or some manual forwarding path reconfiguration occurs.
Several companies, such as Inktomi (Traffic Server product, www.inktomi.com) and Akamai (FreeFlow product, www.akamai.com) are currently offering and/or developing technology for improving Internet communications speeds by mechanisms which essentially replicate or cache copies of frequently-referenced Internet content, and strategically distribute such copies “closer” to the end-user clients who need the information. Such approaches are valuable, but are often limited or ineffective with respect to dynamically generated content (such as cgi-scripted web pages). Moreover, these approaches generally entail significant costs for using large-capacity computer servers to physically store extra copies of massive volumes of data, and for maintaining synchronization among the various repositories of frequently updated content.
What is needed is a mechanism enabling the selection of optimized network paths for the transmission of data, including dynamically generated data, without requiring any change whatsoever to firmly entrenched communication protocols like IP. Furthermore, preferably the mechanism should be essentially transparent to users of the network.
SUMMARY OF THE INVENTION
The present invention provides an on-demand method and system for discovering optimized paths for the transmission of data between source and destination points on a heterogeneous, computer-based communications network. The invention further provides methods and apparatus for transmitting data along such optimized paths, in a transparent manner that does not require modification of existing communication protocols. The data to be transmitted can (but need not) include pages that are dynamically generated in response to an initial request received by the source from the destination, such as an http request to get a cgi-scripted web page.
Briefly, the present invention discloses steps and means, responsive to requests for transmission of data, for measuring a cost of communicating data from the source point to the destination point along a default path, the default path being derived by means of one or more existing routing mechanisms of the communications network. The invention further provides steps and means for measuring the costs of transmitting the message from the source to the destination along one or more non-default, alternative paths passing through a special group of intermediate nodes. In a preferred embodiment, those intermediate nodes are referred to as an “overlay network”. An optimized path for sending the requested transmission is ultimately selected by comparing the default cost against the alternative costs.
Further, the present invention discloses steps and means for transmitting messages along an optimized non-default path passing through overlay nodes, including forwarding of the message from the source to a first one of the intermediate overlay nodes, and from a last one of the intermediate nodes to the destination, in a manner that does not require modification of existing network communication protocols. In a further embodiment, the invention includes steps and means for returning a reply to the transmitted message back along the optimized non-default path from the destination to the source.
Note that whenever referring to “optimized” or “optimal” paths throughout this patent, we simply mean paths that are deemed preferable with respect to selected cost/performance criteria and with respect to a set of identified alternative paths. We are not speaking of global optimality.
REFERENCES:
patent: 4112488 (1978-09-01), Smith, III
patent: 4345116 (1982-08-01), Ash et al.
patent: 4669113 (1987-05-01), Ash et al.
patent: 4788721 (1988-11-01), Krishnan et al.
patent: 4839892 (1989-06-01), Sasaki
patent: 4905233 (1990-02-01), Cain et al.
patent: 4985830 (1991-01-01), Atac et al.
patent: 4987536 (1991-01-01), Humblet
patent: 5058105 (1991-10-01), Mansour et al.
patent: 5088032 (1992-02-01), Bosack
patent: 5115495 (1992-05-01), Tsuchiya et al.
patent: 5128926 (1992-07-01), Perlman et al.
patent: 5218676 (1993-06-01), Ben-Ayed et al.
patent: 5233604 (1993-08-01), Ahmadi et al.
patent: 5253248 (1993-10-01), Dravida et al.
patent: 5321815 (1994-06-01), Bartolanzo, Jr. et al.
patent: 5377262 (1994-12-01), Bales et al.
patent: 5430729 (1995-07-01), Rahnema
patent: 5452294 (1995-09-01), Natarajan
patent: 5471467 (1995-11-01), Johann
patent: 5491690 (1996-02-01), Alfonsi et al.
patent: 5519836 (1996-05-01), Gawlick et al.
patent: 5526414 (1996-06-01), Bëdard et al.
patent: 5532939 (1996-07-01), Psinakis et al.
patent: 5559877 (1996-09-01), Ash et al.
patent: 5596722 (1997-01-01), Rahnema
patent: 5608721 (1997-03-01), Natarajan et al.
patent: 5721916 (1998-02-01), Pardikar
patent: 5754790 (1998-05-01), France et al.
patent: 5774526 (1998-06-01), Propp et al.
patent: 5787271 (1998-07-01), Box et al.
patent: 5787470 (1998-07-01), DeSimone et al.
patent: 5790541 (1998-08-01), Patrick et al.
patent: 5802503 (1998-09-01), Sansone
patent: 5854899 (1998-12-01), Callon et al.
patent: 5918021 (1999-06-01), Aditya
patent: 5922049 (1999-07-01), Radia et al.
patent: 6016307 (2000-01-01), Kaplan et al.
patent: 6185598 (2001-02-01), Farber et al.
patent: 6275470 (2001-08-01), Ricciulli
patent: 6473405 (2002-10-01), Ricciulli
pa
Davidson Berquist Klima & Jackson LLP
Marcelo Melvin
Savvis, Inc.
LandOfFree
On-demand overlay routing for computer-based communication... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with On-demand overlay routing for computer-based communication..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On-demand overlay routing for computer-based communication... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3283833