Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
2000-09-12
2004-08-31
Wiley, David (Department: 2143)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S239000, C370S235000, C370S238000
Reexamination Certificate
active
06785736
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a method and system for computing the shortest path in a communications network; more particularly, the invention optimizes the move within the network of an independent program having to execute itself on a list of designated nodes of the network.
BACKGROUND OF THE INVENTION
Network management applications, operating on network management workstations, remotely control various network components. More and more network management applications become system management applications by providing services to the network components such as handling of statistic collection, maintenance tests, software distribution etc . . . . The main principle is to bring the management program close to the component in order to better perform various tasks than when they were remotely performed. With the current solution of the prior art, each network component served by the system manager stores a copy of service programs the execution of which is remotely started from the system manager work station. This solution is costly because the network components have not always the storage capacity for all the programs corresponding to the services. As an example, in order to control from the system manager station what is the software level operating on such a network component (router, server etc . . . ), an inventory program should be installed on the network components in order to operate under the remote activation sent from the system management workstation. This means that if
500
machines are controlled by the system manager the same program is stored
500
times. As these programs are only temporarily used, it is not necessary to store them in the network component.
An improved method consists in managing from the system management workstation a program (so called a ‘mobile program’) able to travel over the network and to execute a service program on a given list of target network elements. Once the program is executed on one network element component, the mobile program chooses which will be the next network element to serve, and reach it having freed all the computing resources from the current previous network element. When all the network components have been served, there is no more trace of the mobile program in any visited network component. It is noted that the mechanism for transferring the mobile program from one node to the other is performed by programs to be run on the network nodes such as ‘Voyager’ from the company ‘ObjectSpace and documented in the following WEB page: http: //www.objectspace.com/.
With the constant need of limiting the computing resources in the network component, this method is an improvement because it reduces at least storage resources in the network components; however, when traveling inside the network, in order to save the global computing resources and to provide an efficient service in term of response time, it is necessary to optimize the travel of the mobile program inside the network when serving the network elements for which it is responsible.
Defining the best route of travel raises the well known Traveling Salesman Problem. The Traveling Salesman Problem is a classical problem in the field of combination optimization. A salesman must visit different cities spread across the country. In order to minimize the travel, the salesman has to visit each city once and only once. The problem is to define the order he should visit these cities to minimize the total distance of the travel. The solution consists in calculating all the possible orders, to compute the total travel distance and to select the order corresponding to the shortest distance. All exact methods to compute the shortest travel distance consume computing resources exponentially increasing with the number of cities. Practically, an exact solution can be attempted to be computed only for travels including no more than a few hundred cities.
The best path is not always the shortest physical path; the choice for the best path can be done on the basis of many criteria: one can choose to minimize the congestion by using the links between the machines that offer the biggest bandwidth or one can choose to minimize the response time by using the higher speed links; one can also choose a mixed approach or any other approach corresponding to a specific network criterion: CPU utilization, minimum protocol conversion etc . . . . For instance, traveling inside a LAN is quicker and less costly than using heterogeneous protocol lines implying protocol conversion.
Basically the Shortest Path problem may be solved today using two different well-known algorithms. The Dijkstra's algorithm or the Warshall-Floyd's algorithm described in the following URL:
http://www-unix.mcs.anl.gov/dbpp/text
ode35.html.
These methods imply sophisticated matrix mathematical calculations requiring a large coding effort and a significant amount of computing resources to execute the corresponding application.
SUMMARY OF THE INVENTION
It is therefore a purpose of the present invention to optimize the travel in a communication network in order to automatically obtain an optimized path within the network when visiting a predefined list of network nodes.
It is a further purpose of the invention to have this method able to take into account for optimization various criteria such as: path length, conversion protocol and line bandwidth.
It is a following purpose of the invention to find a method using a minimum of computing resources in the network nodes.
One advantage of the method when applied to mobile program traveling within the network is that it can dynamically adapt to any change collected at the nodes to be visited in order to compute the best path according to the criteria which have been chosen.
One other advantage is to have a method limiting the coding effort by using the services of a network management protocol and by using a neural network. The method also limits the computing resources on the nodes as the calculation is done from the network management station.
REFERENCES:
patent: 5701484 (1997-12-01), Artsy
patent: 5825772 (1998-10-01), Dobbins et al.
patent: 5933818 (1999-08-01), Kasravi et al.
patent: 6081722 (2000-06-01), Duque-Anton et al.
patent: 6226408 (2001-05-01), Sirosh
patent: 6260072 (2001-07-01), Rodriguez-Moral
patent: 6321216 (2001-11-01), Otte et al.
patent: 6385615 (2002-05-01), Haeri et al.
patent: 6584071 (2003-06-01), Kodialam et al.
patent: 6633544 (2003-10-01), Rexford et al.
patent: 6636742 (2003-10-01), Torkki et al.
Bui M et al.: “Randomized Adaptive Routing Based on Mobile Agents” Proceedings Fourth International Symposium on Parallel Architectures, Algorithms, and Networks (I-Span '99), Proceedings of 1999 International Symposium on Parallel Architecture, Algorithms and Networks, Perth/Fremantle, WA, Australia, Jun. 23-25, 1999, pp. 380-385, XP002130324 1999, Los Alamitos, CA, USA, IEEE Comput. Soc, USA ISBN: 0-7695-0231-8.
International Business Machines - Corporation
McConnell Daniel E.
Nguyen Phuoc
Wiley David
LandOfFree
Method and system for optimizing the network path of mobile... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for optimizing the network path of mobile..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for optimizing the network path of mobile... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3270486