Apparatus method and storage medium for autonomous selection of a path by tuning response times
First Claim
1. A path selecting apparatus directing a computer or computers to perform selecting a network path of data transmitted from a transmission source node to a transmission destination node, and a network path of data returned from the transmission destination node to the transmission source node in an environment where nodes are distributed and located via a network, comprising:
- a path calculating module running software for obtaining an estimated response time for each of paths that can connect the transmission source node and the transmission destination node by using estimated information, and transmitting a service request message by using a path with a minimum estimated response time, when the transmission source node transmits the service request message to the transmission destination node in order to request a service of the transmission destination node;
a response information management module running software for storing as response information information about a transmission of the service request message, which includes at least a path on which the transmission is performed and a request data length of the service request message, in correspondence with the transmission of the service request message by said path calculating module, and further storing as the response information information about a reception of a response, which includes at least a response data length of the response and a value about a response time required from the transmission of the service request message till the reception of the response, when the transmission source node receives the response to the service request message from the transmission destination node; and
an estimation information managing module running software for updating contents of the estimated information based on the response information in correspondence with the reception of the response by said response information managing module.
1 Assignment
0 Petitions
Accused Products
Abstract
The present invention provides a system, which relates to request and response processes between a transmission source node and a transmission destination node, for autonomously selecting an optimum path by obtaining an actual response time per unit data length and estimating a response time for each path. Upon receipt of a response, which is returned from a transmission destination node 111, to a service request issued from the transmission source node (client), a path selecting apparatus calculates and stores an actual response time. The system comprises estimation individuals to be used for estimating a response time for each of clients, and makes each of the plurality of estimation individuals evolve into an estimation individual which can make a more preferable estimate by using a genetic algorithm, each time the actual response time is stored. When any of the clients requests a service of any of servers, the system calculates an estimated response time for each of the paths which can make a data communications with any of the servers by using the estimation individual, selects the path with the minimum estimated response time, and transmits the service request on the selected path.
203 Citations
37 Claims
-
1. A path selecting apparatus directing a computer or computers to perform selecting a network path of data transmitted from a transmission source node to a transmission destination node, and a network path of data returned from the transmission destination node to the transmission source node in an environment where nodes are distributed and located via a network, comprising:
-
a path calculating module running software for obtaining an estimated response time for each of paths that can connect the transmission source node and the transmission destination node by using estimated information, and transmitting a service request message by using a path with a minimum estimated response time, when the transmission source node transmits the service request message to the transmission destination node in order to request a service of the transmission destination node;
a response information management module running software for storing as response information information about a transmission of the service request message, which includes at least a path on which the transmission is performed and a request data length of the service request message, in correspondence with the transmission of the service request message by said path calculating module, and further storing as the response information information about a reception of a response, which includes at least a response data length of the response and a value about a response time required from the transmission of the service request message till the reception of the response, when the transmission source node receives the response to the service request message from the transmission destination node; and
an estimation information managing module running software for updating contents of the estimated information based on the response information in correspondence with the reception of the response by said response information managing module. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
the value about the response time is an actual response time indicating a response time per unit data length, and the actual response time is obtained by a following equation;
-
-
3. The path selecting apparatus according to claim 1, wherein:
-
each of nodes includes the estimated information, the estimation information including at least one response time estimation individual, the response time estimation individual including a bit string signifying a chromosome and a degree of fitness, and the chromosome including at least one gene block corresponding to a parameter of a response time estimation function;
said estimation information managing module comprises a generation alternating module running software for generation-alternating the chromosome upon receipt of the response to the service request message;
said generation alternating module comprises a fitness degree calculating module running software for calculating the estimated response time by using the parameter of the response time estimation function set in each gene block included in the response time estimation individual, assigning a larger value to the degree of fitness of a response time estimation individual which estimates a more optimum response time, and assigning a larger lifespan value to the response time estimation individual as the degree of fitness becomes higher;
a response time estimation individual deleting module running software for determining a response time estimation individual whose lifespan expires and deleting the response time estimation individual; and
a response time estimation individual generating module running software for selecting a plurality of existing response time estimation individuals with a higher degree of fitness with a higher probability, and performing a genetic operation with a predetermined probability for a chromosome of any of the plurality of response time estimation individuals in order to generate a new response time estimation individual for supplementing the response time estimation individual deleted by said response time estimation individual deleting module, and wherein;
the optimum path is autonomously estimated by evolving the response time estimation individual with a repetition of a generation alternation process performed by said generation alternating module in order to allow the optimum response time to be dynamically estimated.
-
-
4. The path selecting apparatus according to claim 3, wherein:
-
each of a plurality of schools including the estimated information and the response information is corresponded to at least one estimation information managing module;
within said generation alternating module included in said estimation information managing module;
said fitness degree calculating module can use the response information in another school when calculating the estimated response time; and
said response time estimation individual generating module can select a response time estimation individual in another school when selecting an existing response time estimation individual in order to generate a new response time estimation individual for a corresponding school, and wherein;
a path is estimated while behaving cooperatively with other nodes to which said estimation information managing module corresponded with another school belongs.
-
-
5. The path selecting apparatus according to claim 4, wherein:
the value of the lifespan is obtained by an equation
-
6. The path selecting apparatus according to claim 3, wherein the estimated response time is obtained by using:
-
actual response times in a plurality of pieces of response information, which are obtained by receiving a plurality of responses;
a first index indicating how much difference exists between a time at which each of the actual response times is measured and a time at which the degree of fitness is assigned; and
a second index indicating how a distance of a path between the transmission source node and the transmission destination node, on which each of the actual response times is measured, influences a calculation of the estimated response time.
-
-
7. The path selecting apparatus according to claim 6, wherein the estimated response time is calculated based on:
-
the actual response times in the plurality of pieces of response information, which are obtained by receiving the plurality of responses, and times at which the actual response times are measured;
a coefficient of a degree of recency of the time at which each of the actual response times is measured, a coefficient of the distance of the path whose estimate target path and actual response time are measured, and a coefficient indicating a weight of the distance of each portion of address information about each node on each path whose estimate target path and actual response time are measured, which are stored in respective gene blocks in the response time estimation individual; and
a constant of the degree of recency of the time at which each of the actual response times is measured, and a constant of the distance whose estimate target path and actual response time are measured.
-
-
8. The path selecting apparatus according to claim 7, wherein:
-
the estimated response time is obtained by using the actual response times RTi (i=1 to N) in the plurality of pieces of response information, which are obtained by receiving the plurality of responses, the times at which the actual response times are measured, a most recent influence coefficient (cnew), a distance influence coefficient (cdist), and four inter-subnetwork distance influence coefficients (csnet1, csnet2, csnet3, and csnet4), which are stored in each gene block in the response time estimation individual, based on an equation where RIRi=e(−
C1×
cnew×
TAi)(C1 is a positive constant, and TAi is a value obtained by subtracting a time at which an “
i”
th actual response time is measured from a time at which the estimated response time is calculated), and
-
-
9. The path selecting apparatus according to claim 6, wherein the degree of fitness is obtained based on:
-
the actual response times in the plurality of pieces of response information, which are obtained by receiving the plurality of responses;
an index indicating how much difference exists between the time at which each of the actual response times is measured and the time at which the degree of fitness is assigned by said fitness degree calculating module; and
an absolute value of a difference between the estimated response time calculated by said fitness degree calculating module when each of the actual response times is measured, and each of the actual response times.
-
-
10. The path selecting apparatus according to claim 9, wherein the degree of fitness is calculated based on:
-
the estimated response time;
the actual response times in the plurality of pieces of response information, which are obtained by receiving the plurality of responses, and the times at which the actual response times are measured;
the coefficient of the degree of recency of the time at which each of the actual response times is measured, which is stored in each gene block in the response time estimation individual; and
the constant of the degree of recency of the time at which each of the actual response times is measured.
-
-
11. The path selecting apparatus according to claim 10, wherein:
-
the degree of fitness is obtained by using the actual response times RTi(i=1 to N) in the plurality of pieces of response information, which are obtained by receiving the plurality of responses, the times at which the actual response times are measured, and a most recent influence coefficient (cnew) stored in each gene block in the response time estimation individual, based on an equation where RIRi=e(−
c1×
cnew×
TAi)(C1 is a positive constant, and TAi is a value obtained by subtracting a time at which an “
i”
th actual response time RTi is measured from the time at which the actual response time is measured), and dRTi is an absolute value of a difference between the estimate response when the “
i”
th actual response time RTi is calculated and the actual response time RTi.
-
-
12. The path selecting apparatus according to claim 3, wherein:
the value of the lifespan is obtained by an equation
-
13. The path selecting apparatus according to claim 1, further comprising:
-
a path information managing module running software for providing at least one mirror server name corresponding to a name of a representative server when the transmission source node transmits the service request message to the representative server; and
providing at least one PROXY server name which can be used for transmitting the service request message when the transmission source node transmits the service request message via a PROXY server.
-
-
14. A node in an environment where nodes are distributed and located via a network, comprising:
-
a response information managing module running software for managing path information used for a previously issued service request, information of a response time of a service to the service request, and information of an amount of data exchanged for the service request; and
a path calculating module running software for selecting a path with a minimum estimated response time for a certain service request, based on the information managed by said response information managing module.
-
-
15. A node in an environment where nodes are distributed and located via a network, comprising:
-
an estimation information managing running software for managing estimated information used for estimating a response time of a service request on each path used for transmitting the service request issued from a service request source node to a service request destination node, and a response to the service request returned from the service request destination node to the service request source node, based on path information used for a previously issued service request, response time information of the previously issued service request, and an amount of data exchanged for the previously issued service request; and
a path information managing module running software for managing information of the service request destination node and information of a PROXY server used for transmitting the service request to the service request destination node.
-
-
16. A transmission source node for transmitting a service request to a transmission destination node via a network in an environment where nodes are distributed and located via the network, comprising:
-
a path calculating module running software for obtaining an estimated response time for each path that can connect the transmission source node and the transmission destination node by using estimated information, and transmitting a service request message by using a path with a minimum estimated response time, when the transmission source node transmits the service request message to the transmission destination node in order to request a service of the transmission destination node;
a response information managing module running software for storing as response information information about a transmission of the service request message, which includes at least a path on which the transmission is performed and a request data length of the service request message, in correspondence with the transmission of the service request message by said path calculating module, and further storing as the response information information about a reception of a response, which includes at least a response data length of the response and a value about a response time required from the transmission of the service request message till the reception of the response, when the transmission source node receives the response to the service request message from the transmission destination node;
an estimation information managing module running software for updating the contents of the estimated information based on the response information in correspondence with the reception of the response by said response information managing module; and
a path information managing module running software for providing at least one mirror server name corresponding to a name of a representative server when the transmission source node transmits the service request message to the representative server, and providing at least one name of a PROXY server which can be used for transmitting, the service request message, when the transmission source node transmits the service request message via a PROXY server.
-
-
17. A transmission source node for transmitting a service request to a transmission destination node via a network in an environment where nodes are distributed and located via the network, comprising:
-
a path calculating module running software for obtaining an estimated response time for each path that can connect the transmission source node and the transmission destination node by using estimated information, and transmitting a service request message by using a path with a minimum estimated response time, when the transmission source node transmits the service request message to the transmission destination node in order to request a service of the transmission destination node; and
a response information managing module running software for storing as response information information about a transmission of the service request message, which includes at least a path on which the transmission is performed and a request data length of the service request message, in correspondence with the transmission of the service request message by said path calculating module, and further storing as the response information information about a reception of a response, which includes at least a response data length of the response and a value about a response time required from the transmission of the service request message till the reception of the response, when the transmission source node receives the response to the service request message from the transmission destination node.
-
-
18. A node in an environment where nodes are distributed and located via a network, comprising:
-
an estimation information managing module running software for managing estimated information used for estimating a response time of a service request on each path used for transmitting the service request issued from a service request source node to a service request destination node, and a response to the service request returned from the service request destination node to the service request source node, based on path information used for a previously issued service request, response time information of the previously issued service request, and a data length exchanged for the previously issued service request; and
an estimation information updating module running software for obtaining the path information, the response time information, and the data length of the response, and updating the estimated information managed by said estimation information managing module based on the obtained information, each time the response to the service request is received.
-
-
19. A path selecting apparatus comprising a first node and a second node, which are distributed via a network wherein:
-
said first node comprises an estimation information managing module running software for managing estimated information used for estimating a response time of a service request on each path used for transmitting the service request issued from a service request source node to a service request destination node, and a response to the service request returned from the service request destination node to the service request source node, based on path information used for a previously issued service request, response time information of the previously issued service request, and a data length exchanged for the previously issued service request;
an estimation information updating module running software for obtaining the path information, the response time information, and the data length of the response, and updating the estimated information managed by said estimation information managing module based on the obtained information, each time the response to the service request is received; and
said second node comprises a path information managing module running software for managing the information about the service request destination node and the information about a PROXY server, which is used for transmitting the service request to the service request destination node.
-
-
20. A path selecting method for selecting a network path of data transmitted from a transmission source node to a transmission destination node, and a network path of data returned from the transmission destination node to the transmission source node in an environment where nodes are distributed and located via a network, comprising:
-
a path calculating operation obtaining an estimated response time for each path that can connect the transmission source node and the transmission destination node by using estimated information, and transmitting a service request message by using a path with a minimum estimated response time, when the transmission source node transmits the service request message to the transmission destination node in order to request a service of the transmission destination node;
a response information managing operation storing as response information information about a transmission of the service request message, which includes at least a path on which the transmission is performed and a request data length of the service request message, in correspondence with the transmission of the service request message by said path calculating operation, and further storing as the response information information about a reception of a response, which includes at least a response data length of the response and a value about a response time required from the transmission of the service request message till the reception of the response, when the transmission source node receives the response to the service request message from the transmission destination node; and
an estimation information managing step of updating contents of the estimated information based on the response information in correspondence with the reception of the response by said response information managing operation. - View Dependent Claims (21, 22, 23, 24, 25, 31, 32)
the value about the response time is an actual response time indicating a response time per unit data length, and the actual response time is obtained by an equation
-
-
22. The path selecting method according to claim 20, wherein:
-
each of nodes includes the estimated information, the estimation information including at least one response time estimation individual, the response time estimation individual including a bit string signifying a chromosome and a degree of fitness, and the chromosome including at least one gene block corresponding to a parameter of a response time estimation function;
said estimation information managing operation comprises a generation alternating operation of generation-alternating the chromosome upon receipt of the response to the service request message;
said generation alternating operation comprises a fitness degree calculating operation calculating the estimated response time using the parameter of the response time estimation function set in each gene block included in the response time estimation individual, assigning a larger value to the degree of fitness of the response time estimation individual which estimates a more optimum response time, and assigning a larger lifespan value to the response time estimation individual as the degree of fitness becomes higher;
a response time estimation individual deleting operation determining a response time estimation individual whose lifespan expires and deleting the response time estimation individual; and
a response time estimation individual generating operation selecting a plurality of existing response time estimation individuals with a higher degree of fitness with a higher probability, and performing a genetic operation with a predetermined probability for a chromosome of any of the plurality of response time estimation individuals in order to generate a new response time estimation individual for supplementing the response time estimation individual deleted by said response time estimation individual deleting operation, and wherein;
the optimum path is autonomously estimated by evolving the response time estimation individual with a repetition of a generation alternation process performed by said generation alternating operation in order to allow the optimum response time to be dynamically estimated.
-
-
23. The path selecting method according to claim 22, wherein:
-
each of a plurality of schools including the estimated information and the response information is corresponded to at least one estimation information managing operation;
within said generation alternating operation included in said estimation information managing step;
said fitness degree calculating operation uses the response information in another school when calculating the estimated response time; and
said response time estimation individual generating operation selects a response time estimation individual in another school when selecting an existing response time estimation individual in order to generate a new response time estimation individual for a corresponding school, and wherein;
a path is estimated while behaving cooperatively with a system which executes said estimation information managing step corresponded with another school.
-
-
24. The path selecting apparatus according to claim 23, wherein:
the value of the lifespan is obtained by an equation
-
25. The path selecting method according to claim 22, wherein the estimated response time is obtained by using:
-
actual response times in a plurality of pieces of response information, which are obtained by receiving a plurality of response;
a first index indicating how much difference exists between a time at which each of the actual response times is measured and a time at which the degree of fitness is assigned; and
a second index indicating how a distance of a path between the transmission source node and the transmission destination node, on which each of the actual response times is measured, influences a calculation of the estimated response time.
-
-
31. The path selecting method according to claim 22, wherein:
the value of the lifespan is obtained by an equation
-
32. The path selecting method according to claim 20, further comprising:
-
a path information managing operation providing at least one mirror server name corresponding to a name of a representative server when the transmission source node transmits the service request message to the representative server; and
providing at least one name of a PROXY server which can be used for transmitting the service request message when the transmission source node transmits the service request message via a PROXY server.
-
-
26. The path selecting method according to claim wherein the estimated response time is calculated based on:
-
the actual response times in the plurality of pieces of response information, which are obtained by receiving the plurality of responses, and the times at which the actual response times are measured;
a coefficient of a degree of recency of the time at which each of the actual response times is measured, a coefficient of the distance of the path whose estimate target path and actual response time are measured, and a coefficient indicating a weight of the distance of each portion of address information about each node on each path whose estimate target path and actual response time are measured, which are stored in respective gene blocks in the response time estimation individual, and a constant of the degree of recency of the time at which each of the actual response times is measured, and a constant of the distance whose estimate target path and actual response time are measured. - View Dependent Claims (27, 28, 29, 30)
the actual response times in the plurality of pieces of response information, which are obtained by receiving the plurality of responses;
an index indicating how much difference exists between the time at which each of the actual response times is measured and the time at which the degree of fitness is calculated; and
an absolute value of a difference between the estimated response time calculated when the actual response times are measured, and each actual response time.
-
-
28. The path selecting method according to claim 27, wherein the degree of fitness is calculated based on:
-
the estimated response time;
the actual response times in the plurality of pieces of response information, which are obtained by receiving the plurality of responses, and the time at which each of the actual response times is measured;
the coefficient of the degree of recency of the time at which each of the actual response times is measured, which is stored in each gene block included in the response time estimation individual; and
the constant of the degree of recency of the time at which each of the actual response times is measured.
-
-
29. The path selecting method according to claim 28, wherein:
-
the degree of fitness is obtained by using actual response times RTi (i=1 to N) in a plurality of pieces of response information, which are obtained by receiving a plurality of responses, times at which the actual response times are measured, and a most recent influence coefficient (cnew) stored in each gene block in the response time estimation individual, based on an equation where RIRi=e(−
C1×
cnew×
TAi)(C1 is a positive constant, and TAi is a value obtained by subtracting a time at which an “
i”
th actual response time RTi is measured from the time at which the actual response time is measured), and dRTi is an absolute value of a difference between the estimate response when the “
i”
th actual response time RTi is calculated and the actual response time RTi.
-
-
30. The path selecting method according to claim 26, wherein:
-
the estimated response time is obtained by using actual response times RTi (i=1 to N) in a plurality of pieces of response information, which are obtained by receiving a plurality of responses, times at which the actual response times are measured, a most recent influence coefficient (cnew), a distance influence coefficient (cdist), and four inter-subnetwork distance influence coefficients (csnet1, csnet2, csnet3, and csnet4 ), which are stored in each gene block in the response time estimation individual, based on an equation where RIRi=e(−
C1×
cnew×
TAi)(C1 is a positive constant, and TAi is a value obtained by subtracting a time at which an “
i”
th actual response time is measured from a time at which the estimated response time is calculated), and
-
-
33. A path selecting method for selecting a path on which a service request is transmitted from a transmission source node to a transmission destination node via a network in an environment where nodes are distributed and located via the network, comprising:
-
obtaining an estimated response time for each path that can connect the transmission source node and the transmission destination node by using estimated information, and transmitting the service request message by using a path with a minimum estimated response time, when the transmission source node transmits a service request message to the transmission destination node in order to request a service of the transmission destination node;
storing as response information information about a transmission of the service request message, which includes at least a path on which the transmission is performed and a request data length of the service request message, in correspondence with the transmission of the service request message, and further storing as the response information information about a reception of a response, which includes at least a response data length of the response and a value about a response time required from the transmission of the service request message till the reception of the response, when the transmission source node receives the response to the service request message from the transmission destination node;
updating the contents of the estimated information based on the response information in correspondence with the reception of the response; and
providing at least one mirror server name corresponding to a name of a representative server when the transmission source node transmits the service request message to the representative server, and providing at least one name of a PROXY server which can be used for transmitting the service request message when the transmission source node transmits the service request message via a PROXY server.
-
-
34. A path selecting method for selecting a path on which a service request is transmitted from a transmission source node to a transmission destination node via a network in an environment where nodes are distributed and located via the network, comprising:
-
obtaining an estimated response time for each path that can connect the transmission source node and the transmission destination node by using estimated information, and transmitting the service request message by using a path with a minimum estimated response time, when the transmission source node transmits a service request message to the transmission destination node in order to request a service of the transmission destination node; and
storing as response information information about a transmission of the service request message, which includes at least a path on which the transmission is performed and a request data length of the service request message, in correspondence with the transmission of the service request message, and further storing as the response information information about a reception of a response, which includes at least a response data length of the response and a value about a response time required from the transmission of the service request message till the reception of the response, when the transmission source node receives the response to the service request message from the transmission destination node.
-
-
35. A computer-readable storage medium, which stores a program implementing a method for selecting a path on which a service request is transmitted from a transmission source node to a transmission destination node via a network in an environment where nodes are distributed and located via the network, for directing a computer to perform:
-
obtaining an estimated response time for each path that can connect the transmission source node and the transmission destination node by using estimated information, and transmitting the service request message by using a path with a minimum estimated response time, when the transmission source node transmits a service request message to the transmission destination node in order to request a service of the transmission destination node;
storing as response information information about a transmission of the service request message, which includes at least a path on which the transmission is performed and a request data length of the service request message, in correspondence with the transmission of the service request message, and further storing as the response information information about a reception of a response, which includes at least a response data length of the response and a value about a response time required from the transmission of the service request message till the reception of the response, when the transmission source node receives the response to the service request message from the transmission destination node; and
updating contents of the estimated information based on the response information in correspondence with the reception of the response.
-
-
36. A computer-readable storage medium, which stores a program implementing a method for selecting a path on which a service request is transmitted from a transmission source node to a transmission destination node via a network in an environment where nodes are distributed and located via the network, for directing a computer to perform:
-
obtaining an estimated response time for each path that can connect the transmission source node and the transmission destination node by using estimated information, and transmitting the service request message by using a path with a minimum estimated response time, when the transmission source node transmits a service request message to the transmission destination node in order to request a service of the transmission destination node;
storing as response information information about a transmission of the service request message, which includes at least a path on which the transmission is performed and a request data length of the service request message, in correspondence with the transmission of the service request message, and further storing as the response information information about a reception of a response, which includes at least a response data length of the response and a value about a response time required from the transmission of the service request message till the reception of the response, when the transmission source node receives the response to the service request message from the transmission destination node; and
updating the contents of the estimated information based on the response information in correspondence with the reception of the response; and
providing at least one mirror server name corresponding to a name of a representative server when the transmission source node transmits the service request message to the representative server, and providing at least one name of a PROXY server which can be used for transmitting the service request message when the transmission source node transmits the service request message via a PROXY server.
-
-
37. A computer-readable storage medium, which stores a program implementing a method for selecting a network path of data transmitted from a transmission source node to a transmission destination node, and a network path of data returned from the transmission destination node to the transmission source node in an environment where nodes are distributed and located via a network, for directing a computer to perform:
providing at least one mirror server name corresponding to a name of a representative server when the transmission source node transmits a service request message to the representative server, and providing at least one name of a PROXY server which can be used for transmitting the service request message when the transmission source node transmits the service request message via a PROXY server.
Specification