Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-10-19
2003-04-01
Kizou, Hassan (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S351000, C370S352000, C370S353000, C370S354000, C370S355000, C370S356000, C370S357000
Reexamination Certificate
active
06542468
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an apparatus for selecting an optimum path in a network environment where nodes are distributed and located via a network. More particularly, to an apparatus which estimates and selects an optimum path used to transmit data and its response according to a response times per unit data length of transmission data or of response data when one node transmits service request data to another node among the plural nodes distributed via the network and the response to the transmitted data is returned from the transmission destination node to the transmission source node.
2. Description of the Related Art
With the rapid popularization of the Internet in recent years, the amount of data transmitted/received over the Internet has been significantly increasing. The type and purpose of the data to be transmitted/received over the Internet are diversified. For example, the data of a home page downloaded from a WWW server, the file data of each type of software transmitted from an FTP server, e-mail from a company or an individual are diversified.
In such a situation, Internet users may frequently spend a long time in downloading data from a requested home page, that is, in displaying of the home page, or in downloading a file. This is because the users cannot determine which server is most efficient although mirror servers are provided.
Additionally, since network topology becomes complicated and the node configuration of a network continuously varies, an optimum network path dynamically and significantly changes in its form and its time. Therefore, selecting an optimum path is more difficult for network administrators or network engineers.
However, conventional protocols for selecting a path collect the information such as the number of routers (hop count) interposed between a transmission source address and a transmission destination address, a bandwidth (maximum data flow rate), and traffic (an actual data flow rate), etc., and calculate a path by using these items of information as indices, in each repeater. With these techniques, the response times per unit data length of transmission data and the response data are not used for the calculation of the path selection when one node transmits the data which requests a service to another node and this node returns the data which respond to the transmission data.
As typical examples of the conventional routing protocols, RIP and OSPF can be cited.
The RIP (Routing Information Protocol: RFC 1058) is a dynamic routing information exchange protocol between routers or between a router and a host in an autonomous system. The RIP adopts a distance vector algorithm, and is used by many UNIX systems and routers. According to the RIP, the numbers of routers (hop count) via which data reaches a transmission destination are exchanged between a router and its contiguous router at predetermined time intervals, and a communication path is selected in order to minimize the hop count. Note that the hop count that can be administered is up to 15.
The OSPF (Open Shortest Path First: RFC 1583) adopts a link state algorithm. According to this protocol, network link information (link state) are exchanged between routers, and each of the routers selects an optimum communication path based on the link information. The OSPF can select an optimum cost path in consideration of a network load, a line cost/speed, a delay, etc., and distributes a load by securing paths which costs the same.
Additionally, the example in which a genetic algorithm is applied to the RIP is disclosed as the paper titled “An Adaptive Network Routing Algorithm Employing Path Genetic Operators (Seventh International Conference on Genetic Algorithms (ICGA '97))” by Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato, et al. in 1997.
The genetic algorithm (GA) is a technique which simulates and applies the mechanism of inheritance of living things. In the evolution of living things, crossover of chromosomes possessed by an individual, or mutation of a gene in a chromosome, may occur when a new individual (child) is born from an old individual (parent). An individual which is not adaptive to an environment is not selected, and an adaptive individual survives and becomes a parent of a new descendant. In this way, a group of individuals which are adaptive to an environment will survive. To what degree each individual will adapt to an environment is determined by a chromosome or a genome.
In the genetic algorithm, a candidate of solution to a combinatorial optimization problem is represented as a character string corresponding to a chromosome which is a one-dimensional string of genes. An optimum solution is searched by repeatedly performing genetic operations such as selection by self-reproduction, crossover, mutation, etc. for a group of solution candidates (referred to as individuals). The above described character string may also be a numeral string represented by, for example, “0” and “1”.
Here, the evolution of a living thing corresponds to a process that the value of an objective function (function for evaluating the degree of fitness of a solution candidate) for a solution candidate approaches an optimum value. A fitness degree function whose value is larger as it makes the objective function more optimum is defined for a character string (chromosome). The selection operation is an operation for calculating the evaluation value of each character string by using the fitness degree function, choosing a character string with a high evaluation value from the group of solution candidates, and defining the selected string as a group of solution candidates of a next generation. The mutation operation is an operation for replacing some bits (some genes) included in a character string (bit string) with their values inverted at random (if the original bit is “1”, it is replaced with “0”, and vice versa). The crossover operation is an operation for exchanging parts of two character strings.
By repeating these operations, a character string with a higher evaluation value, that is, a solution candidate for further optimizing the objective function can be obtained. Genetic algorithms are said to be suitable for solving an optimization problem of a discrete variable, which is large-scaled and multi-peaked, and moreover, they can be easily applied to the above described optimization problem. Therefore, these algorithms are widely used.
In the above described paper by Munetomo et al., a substitute route is generated by a genetic algorithm which uses the mutation and crossover operations in addition to a default route in a routing table generated in a routing table in such a way that each router minimizes the hop count based on the RIP. The probabilities (frequencies) of thus generated paths are determined according to a communication wait time when each of the paths is used. If the evaluation value based on the wait time becomes lower than a predetermined value, this genetic algorithm is applied and another new path is generated.
Here, the mutation operation indicates an operation for changing, for example, one router to its contiguous router among routers structuring a path, and forming a new path by connecting the shortest path between the changed router and a transmission source node and the shortest path between the router and a transmission destination node. The crossover operation is an operation for choosing a combination of routers included in both of the above described pair of paths, choosing one router from the combination, replacing all of the routers existing on a route between the router and a transmission destination node; and generating a new path.
Additionally, TOKUGANHEI 5-87597 (Japanese Patent Laid-Open Publication) “Path Specifying Mechanism of Transaction Processing Server” discloses the mechanism for assigning a transaction whose class is the same as that of the transaction of a transaction processing server for performing an optimum process based on a response time of the transaction.
With the ab
Fujitsu Limited
Kizou Hassan
Logsdon Joe
Staas & Halsey , LLP
LandOfFree
Apparatus method and storage medium for autonomous selection... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus method and storage medium for autonomous selection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus method and storage medium for autonomous selection... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3032641