Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
2000-06-30
2003-12-02
Meky, Moustafa M. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C709S224000, C709S241000, C370S254000
Reexamination Certificate
active
06658479
ABSTRACT:
COPYRIGHT NOTICE
Contained herein is material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent disclosure by any person as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all rights to the copyright whatsoever.
FIELD OF THE INVENTION
This invention pertains to the field of networking, and more particularly to Internet routing protocols.
BACKGROUND OF THE INVENTION
Congestion at the links and in the routers is the main cause of large delays in the Internet. The approaches proposed to date for minimizing congestion fall in two categories: minimizing link delays in the network and server load balancing.
The conventional approach to minimizing link delays in computer networks consists of using a heuristic to compute a single shortest path from a source to a destination. Routing algorithms based on single shortest-path heuristics are very responsive to topological and link-cost changes, making them far more preferable than optimal routing for implementation in real networks. However, except under light traffic loads, the delays obtained with this type of routing are far from optimal. Furthermore, if link costs are associated with delays, single-path routing exhibits oscillatory behavior and becomes unstable as traffic loads increase.
Many optimal routing algorithms for minimizing link delays exist (also known as minimum-delay routing algorithms), but they all assume the input traffic and the network topology are stationary or very slowly changing, and require global constants that guarantee convergence. This makes optimal routing algorithms impractical for real networks given the bursty nature of traffic at any time scale, the random occurrences of topology changes, and the impossibility of determining global time constants that work for all input-traffic patterns.
With server load-balancing, a computation is assigned to a server based on the current computational load on various other servers, possibly with provisions for failover to handle the loss of a server or communication link. Commercial products typically use round robin, least number of connections, weighted priority, and server load or response time to determine how to distribute traffic among servers, but treat server load and network load separately.
With the widespread use of Internet technology and the affordability of computing hardware today, it is desirable to distribute processing elements (servers) over a network or internet to perform a wide variety of computing services. By doing so, third parties can maintain the servers and the network accessed by users, such that users do not have to worry about system management and need not know where in the network the services are provided.
Since congestion at the links and in the routers is the main cause of large delays, a routing method is more effectively optimized when congestion at both links and at routers is considered. No approaches to date, however, have been presented for the joint minimization of congestion at the links and servers of a network.
SUMMARY OF THE INVENTION
A method for determining the cost of routing data is described herein, where a communication cost for routing data from a current node to a successor node over a communication channel is computed, and then a processing node cost for processing data at the current node is computed, where the processing node cost represents a ratio of data input rates to data output rates at the current node. The two computations are combined to formulate a link cost for the current node, or the cost of routing data through that node, where the link cost can then be used in a routing algorithm for routing data.
REFERENCES:
patent: 5649108 (1997-07-01), Spiegel et al.
patent: 5754543 (1998-05-01), Seid
patent: 5856981 (1999-01-01), Voelker
patent: 5881243 (1999-03-01), Zaumen et al.
patent: 6256295 (2001-07-01), Callon
patent: 6456599 (2002-09-01), Elliott
patent: 6584075 (2003-06-01), Gupta et al.
patent: 858189 (1998-08-01), None
patent: PCT/US01/21175 (2001-02-01), None
Zaumen et al., “A Practical Approach to Minimizing Delays in Internet Routing”, 5 pages, www.soe.ucsc.edu/research/ccrg.
Garcia-Luna-Aceves et al., “A Simple Approximation to Minimum-Delay Routing”, 12 pages, www.soe.ucsc.edu/research/ccrg.
Vitukury, S. et al.: “A Simple Approximation to Minimum-Delay Routing” Computer Communications Review Association For Computing Machinery. New York, US, vol. 29, No. 4, Oct. 1999, pp. 227-238, XP000852201, ISSN: 0146-4833.
Cassandras, C G et al.: “Distributed Routing With On-Line Marginal Delay Estimation”, Networks: Evolution or Revolution? New Orleans, Mar. 27-31, 1988, Proceedings fo the Annual Joint Conference of the Computer and Communications Societies. (INFOCOM), NewYork, IEEE, US, vol. CONF.7, Mar. 27, 1988, pp. 603-612, XP010011723, ISBN: 0-8186-0833-1.
Zaumen et al.: “Load-Balanced Anycast Routing in Computer Network”, Fifth IEEE Symposium on Computers and Communications (ISCC 2000), Jul. 3-6, 2000, pp. 566-574, XP002189124, Anitbes-Juan les Pins, France, ISBN: 0-7695-0722-0.
Garcia-Luna-Aceves Jose J.
Zaumen William T.
Blakely & Sokoloff, Taylor & Zafman
Meky Moustafa M.
Sun Microsystems Inc.
LandOfFree
Load-balanced anycasting and routing in a network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Load-balanced anycasting and routing in a network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Load-balanced anycasting and routing in a network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3162468