REGISTER  |  SIGN IN
United States Patent6058267
Kanai , ; et al.May 2, 2000
Title
Multiple processor transaction processing system using transaction routing and data management
Abstract
A multiple processor transaction processing system having both a transaction routing unit for routing each transaction generated by the transaction source to one of the transaction processors, and a data arrangement unit for determining data arrangement of the data to be used in processing the transactions by the transaction processors. The transaction routing unit routes each transaction to one of the transaction processors according to the feature parameters extracted from each transaction and the processing history information for past transactions processed by the transaction processors. The data arrangement unit determines a new data arrangement of the data in the data storage regions according to a data storage information indicating original arrangement of the data in the data storage regions and the correlation information indicating all sets of data which are accessed together in each series processing carried out by the transaction processors.
Inventors:Kanai; Tatsunori (Kanagawa-ken, JP), Yokokawa; Takeshi  (Kanagawa-ken, JP)
Assignee:Kabushiki Kaisha Toshiba (Kawasaki, JP)
Appl. No.:030397
Filed:February 25, 1998
Foreign Application Priority Data
Sep 06, 1993 [JP] 5-220353
Dec 28, 1993 [JP] 5-349306
Current U.S. Class:712/28 718/105 707/10 707/3 709/201 709/208 
Current International Class:G06F 9/46 (20060101)
Field of Search:707/10,3 395/200.31,200.68,200.54,200.78,800.28,675
U.S. Patent Documents
5048011September 1991Melen
5155851October 1992Krishnan
5170393December 1992Peterson et al.
5218676June 1993Ben-Ayed et al.
5289371February 1994Abel et al.
5347450September 1994Nugent
5404451April 1995Nemirovsky et al.
5430729July 1995Rahrema
5452350September 1995Reynolds et al.
5475813December 1995Cieslak et al.
5495582February 1996Chen et al.
5499237March 1996Richetta et al.
5504894April 1996Ferguson et al.
5537394July 1996Abe et al.
5546541August 1996Drew et al.
5586312December 1996Johnson et al.
5678010October 1997Pittenger et al.
Other References
Proceedings of the Twelfth International Conference on Very Large Data Bases, Aug. 1986, pp. 249-256, Philip S. Yu, et al., "On Affinity Based Routing in Multi-System Data Sharing"..~
Primary Examiner: Homere; Jean R.
Attorney, Agent or Firm:Oblon, Spivak, McClelland, Maier & Neustadt, P.C.
Parent Case Text


This application is a division of application Ser. No. 08/859,724, filed on May 21, 1997, now U.S. Pat. No. 5,864,679 which is a Con of Ser. No. 08/300,554, filed Sep. 6, 1994, abandoned.
Claims

What is claimed is:
1. A multiple processor transaction system, comprising:
at least one transaction source means for generating transactions to be processed by the system without specifying any particular transaction processor for processing any given transaction;
a plurality of transaction processors for processing the transactions generated by the transaction source means;
at least one transaction routing means for specifying a given one of the transaction processors for processing each transaction generated by the transaction source means and routing said each transaction to said given one of the transaction processors;
at least one data memory means connected with at least one of the transaction processors for storing data to be used in processing the transactions by the transaction processors; and
data arrangement means for determining data arrangement of the data to be used in processing the transaction by the transaction processors and stored in the data memory means.

2. The system of claim 1, further comprising at least one front-end processor connected between the transaction source means and the transaction processors, where the transaction routing means is provided on the front-end processor.

3. The system of claim 1, wherein the transaction routing means is provided on the transaction processors.

4. The system of claim 1, wherein the transaction routing means has a processing history information for past transactions, and routes each transaction to said given one of the transaction processors according to the processing history information.

5. The system of claim 4, wherein the processing history information includes each past transaction, an identifier of one of the transaction processors which had processed each past transaction, and a processing cost which had been required in processing each past transaction.

6. The system of claim 3, wherein the transaction routing means routes each transaction to said given one of the transaction processors for which the processing cost is expected to be minimum according to the processing history information.

7. The system of claim 1, wherein the transaction routing means has a data arrangement information concerning the data stored in the data memory means associated with each of the transaction processors, and routes each transaction to said given one of the transaction processors according to the data arrangement information.

8. The system of claim 7, wherein the data arrangement information includes the data arrangement determined by the data arrangement means.

9. The system of claim 7, wherein each of the transaction processors includes data management means for managing the data stored in the data memory means, and the data arrangement information includes information on the data managed by the data management means.

10. The system of claim 1, wherein the transaction routing means routes each transaction to said given one of the transaction processors according to a type of each transaction.

11. The system of claim 1, wherein the data arrangement means is provided at least one of the transaction processors.

12. The system of claim 1, wherein each of the transaction processors includes an application program to be executed in processing each transaction, and data management means for managing the data stored in the
data memory means according to data access requests from the application program.

13. The system of claim 12, wherein the data management means has an access history information concerning past data accesses made by the application program, and the data arrangement means determines the data arrangement according to the access history information stored by the data management means.

14. The system of claim 12, wherein the data management means of each transaction processor is directly communicable with the data management means of other transaction processors.

15. The system of claim 14, wherein each transaction processor is associated with one of a plurality of the data memory means, and the data management means of each transaction processor requests the data management means of one of the other transaction processors to make a data operation for the data stored in the data memory means associated with said one of the other transaction processors.

16. The system of claim 12, wherein the data management means also changes arrangement of the data stored in the data memory means according to the data arrangement determined by the data arrangement means.

17. The system of claim 12, further comprising means for presenting the data arrangement determined by the data arrangement means to a system manager.

18. A method of operating a multiple processor transaction processing system, comprising:
receiving transactions to be processed by the system from at least one transaction source
specifying a given one of a plurality of transaction processors for processing each transaction received at the receiving step based upon transaction processor selection criteria and routing said each transaction to said given one of the plurality of transaction processors;
determining data arrangement of data to be used in processing the transactions by each given transaction processor for storage in at least one data memory connected with at least one of the transaction processors;
storing the data in the data arrangement determined at the determining step; and
processing each transaction by said each given transaction processor to which each transaction is routed at the specifying step using the data stored at the storing step.

19. The method of claim 18, wherein at the specifying step, each transaction is routed to each given transaction processor according to a processing history information for past transactions produced from processing results obtained by the transaction processors at the processing step.

20. The method of claim 18, wherein at the specifying step, each transaction is routed to each given transaction processor according to a data arrangement information concerning the data arrangement determined at the determining step.

21. The method of claim 18, wherein at the determining step, the data arrangement is determined according to an access history information concerning past data accesses from the transaction source received at the receiving step.
Description
BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a transaction processing system using multiple processors, and more particularly, to schemes for transaction routing and data management in such a multiple processor transaction processing system.

2. Description of the Background Art

The transaction processing system for executing some kind of processing for the transactions received from the transaction sources such as a plurality of terminals, computers, and automatic teller machines which are coupled to the transaction processing system through communication paths is widely utilized today. Such a transaction processing system has been constituted by a single general purpose computer, but it has become necessary to constitute the transaction processing system from a plurality of processors in a case the higher processing power is required such as a case of handling a large amount transactions simultaneously, so as to share the load of processing a plurality of transactions among a plurality of transaction processors.

This multiple processor transaction processing system can take either a data non-sharing type configuration as shown in FIG. 1 or a data sharing type configuration as shown in FIG. 2. In either one of these configuration, a plurality of transaction processors 6'-1 to 6'-m having application programs 7'-1 to 7'-m and data management units 8'-1 to 8'-m, respectively, are coupled together by a coupling device 5' connected with a front-end processor 3' having a transaction routing unit 4'. This transaction routing unit 4' is connected with a number of transaction sources 1'-1 to 1'-n through a communication path 2' such that the transactions received from the transaction sources 1'-1 to 1'-n through the communication path 2' are routed through the coupling device 5' to the transaction processors 6'-1 to 6'-m distributedly.

In a case of the data non-sharing type configuration of FIG. 1, the transaction processors 6'-1 to 6'-m are associated with local data memory units 9'-1 to 9'-m, respectively, in which the data for each transaction processor 6' are separately stored in each local data memory unit 9', so that the data management unit 8' of each transaction processor 8' can make accesses only to the data in the corresponding data memory unit 9' connected with this transaction processor 6'. On the other hand, in a case of the data sharing type configuration of FIG. 2, all the transaction processors 6'-1 to 6'-m are associated with a common data memory unit 9A, so that the data management unit 8' of each transaction processor 6' can make accesses to any data in this common data memory unit 9A.

In the multiple processor transaction processing system of the data non-sharing type, the data in files or databases to be processed can be managed by being distributed among a plurality of processors. For this reason, a received transaction can be processed in shortest time with lowest load by processing this transaction at a processor on which the data required in processing this transaction are present. In other words, when this transaction is received at the processor which does not have the data required in processing this transaction, it is necessary to transfer the processing to the other processor which manages the relevant data or to transfer the data from the other processor which manages the relevant data, so that the required time and the load for processing this transaction are going to be increased.

Consequently, in order to improve the processing power of the multiple processor transaction processing system as a whole, it is necessary to provide the routing of each transaction to the optimum processor which can make access to the data required in processing each transaction at the lowest cost, which is furnished by the transaction routing unit 4' in the front-end processor 3' in the configuration of FIG. 1.

Here, however, the conventionally known transaction routing scheme includes a scheme for routing the transactions according to the prescribed order by using the prescribed correspondence table which indicates which transaction should be routed to which transaction processor, and a scheme for providing additional means for checking the loading state of each transaction processor and routing each transaction to the transaction processor which is judged as being less loaded by this additional means in the random order, and both-of these conventional schemes totally irrespective of the content of each transaction so that it has been difficult to take a full advantage of the available processing power of the system effectively.

In addition, in a case of the data non-sharing type configuration of FIG. 1 using a plurality of data memory devices 9', the transaction processing system can have a plurality of data storage regions and data management units for distributedly storing and managing the data in these plurality of data storage regions. and a plurality of accesses to the data in a plurality of data storage regions can be made in processing each transaction. In such a case, the time required in processing each transaction can be shortened if all the data required in processing each transaction are present in the same data storage region. In other words, in a case a plurality of data required in processing each transaction are not present in the same data storage region, even if they are stored in the different data storage regions within the same data memory device, an extra time is required for the data accesses for reading and writing of the data compared with a case in which all these data are present in the same data storage region.

Also, when a plurality of data are present in the different data storage regions on different data memory devices, the access time is further increased as it becomes necessary to request the data management unit managing the relevant data memory device to read out or transfer the data, and this in turn further increases the processing time for each transaction.

On the other hand, in a case it is possible to make accesses to a plurality of data storage regions simultaneously, the transaction processing power of the system as a whole can be improved by equalizing the access frequency with respect to each data storage region as much as possible, i.e., by loading the data memory devices as uniformly as possible. Consequently, in order to shorten the processing time for each transaction while taking a full advantage of the transaction processing power of the system as a whole, it is preferable to arrange the data such that the data necessary for each transaction are available within the same data storage region as much as possible and the access frequency with respect to each data storage region is equalized as much as possible.

Conventionally, the data arrangement in the data storage regions has been specified explicitly by a system manager. Namely, the system manager has been required to decide which data should be arranged in which data storage regions in order to take a better advantage of the system power according to the result of analysis of the data accessed by each transaction, the frequency of occurrences of each transaction, and the loading state of each data memory device to determine whether the available system power is currently utilized sufficiently or not, and if not, the cause in terms of the data arrangement which prevents the sufficient utilization of the available system power. Then, the system manager has been required to explicitly specify the correspondence between each data and the data storage region for storing each data to the data management units in order to realize the decided new data arrangement. As for those data for which the correspondence between the data and the data storage region for storing the data is not given, the data are arranged in the arbitrary memory devices by the system itself.

However. in order to analyze what kinds of data accesses are going to be made by a transaction, there is a need to analyze the source codes, but it has been quite difficult to analyze the source codes for all the transactions to be processed in the transaction processing system. Moreover, even if the source codes are analyzed somehow, some data access targets would not be apparent in cases the branching occurs or the data access target is determined according to the factors dynamically determined at a time of the transaction processing. Therefore, even when the new data arrangement is obtained to satisfy the above described requirement according to the result of analysis of the source codes, it is unlikely to be able to take a sufficient advantage of the available system power by such a data arrangement.

Furthermore, whenever a new transaction is added to the system, or the frequency of occurrences of the transaction to be processed on the system changes, it has been necessary to carry out the analysis again. Thus, this manner of changing the data arrangement requires an enormous amount of efforts. In addition, in this simple-minded scheme, the data are arbitrarily arranged once without the analysis, and then, by measuring the individual data and the loads of the data memory devices, the data are rearranged simply to make the difference in the loads of the data memory devices as small as possible, so that there is no consideration given to which sets of data are required by the same transaction processed on the system, and consequently it is unlikely to be able to take a sufficient advantage of the available system power in this regard as well.

On the other hand, instead of the scheme for rearranging the data after the arbitrary arrangement of the data to make the difference in the loads as small as possible, there are several propositions for a scheme for arranging the data according to prescribed rules so as not to make any difference in the loads from the beginning, without requiring the analysis. Examples of this type of data arrangement scheme includes a scheme for arranging the data randomly with respect to the data storage regions using the hash function. a scheme for dividing the range of values taken by the data into as many groups as a number of data storage regions and allocating each group to each data storage region. and a scheme for dividing the range of values taken by the data into a prescribed number of groups and allocating the groups to the data storage regions in the manner of round robin.

These schemes are all of the type which attempts to avoid the concentration of the loads; to a particular data memory device probabilistically, so that there are cases in which they can be successful, but they do not guarantee the avoidance of the concentration of the loads for any system configuration and any frequency of occurrences of the transactions. Moreover, in this type: of scheme, the data required for each transaction to be processed on the system are going to be arranged randomly, so that the processing time for each transaction can be longer not just when the concentration of the loads occurs but also when the concentration of the loads is avoided, and consequently it is unlikely to be able to take a sufficient advantage of the available system power in this regard as well.

Thus, in the conventional data management scheme, the analysis necessary for taking the sufficient advantage of the available system power has been quite difficult, and furthermore, the incompleteness of the analysis made it unlikely to be able to take the sufficient advantage of the available system power.

As described, in the multiple processor transaction processing system, in order to carry out the processing of the transaction efficiently by using a plurality of transaction processors, it is necessary to route each transaction to the transaction processor for which the cost for processing this transaction is low, and in addition when a plurality of data memory devices are used, it is also necessary to arrange the data distributedly among a plurality of data memory devices.

Conventionally, it has been a role of the system manager to analyze which data are going to be accessed by the application program executed in the system and determine the schemes for distributed data arrangement and the transaction routing appropriately, such that the transactions can be processed in parallel as much as possible, the data necessary for the processing of each transaction are present at the transaction processor for processing this transaction as much as possible, and the cost required for processing each transaction becomes as small as possible in view of the data arrangement and the frequency of occurrences of each transaction. However, in determining either one of the distributed data arrangement scheme and the transaction routing scheme, it is still necessary to analyze the dynamic characteristic of the system as a whole in order to take the full advantage of the available system power, but this analysis has been quite difficult.

Even when the transaction routing is dynamically determined somehow, if the data arrangement is fixed, it is impossible to route each transaction such that all the data required for this transaction are always present in the routed transaction processor, so that it is unlikely to take the full advantage of the available system power. To this end, in the conventional transaction processing system, it has been necessary for the system manager to make the rearrangement of the data in view of the newly determined transaction routing scheme, but this system management operation can be quite tedious.

Also, even when the data arrangement is changed according to the dynamic characteristic of the data accesses somehow, if the transaction routing is predetermined, all the data required for each transaction are not necessarily always present in the routed transaction processor as the data arrangement is no longer the same as that used in the transaction routing, so that it is still unlikely to take the full advantage of the available system power. To this end, in the conventional transaction processing system, it has also been necessary for the system manager to make the routing of the transactions in view of the newly determined data arrangement scheme and the frequency of occurrences of the transactions, but this system management operation can be quite tedious.

SUMMARY OF THE INVENTION

It is therefore an object of the present invention to provide a scheme for controlling the transaction processing system to take a full advantage of the available system power easily and the management and the tuning of the system can be carried out automatically.

It is another object of the present invention to provide a scheme for automatic transaction routing capable of taking a full advantage of the available processing power of the multiple processor transaction processing system, dealing with changes in a number of processors constituting the system or a data arrangement in the system, and balancing loads among a plurality of processors by reflecting the dynamic load distribution state in the transaction routing procedure.

It is another object of the present invention to provide a scheme for data management in the transaction processing system, capable of taking, a full advantage of the available processing power of the multiple processor transaction processing system, by automatically producing and analyzing the data necessary in determining the data arrangement.

According to one aspect of the present invention there is provided a multiple processor transaction processing system, comprising: at least one transaction source means for generating transactions to be processed; a plurality of transaction processors for processing the transactions generated by the transaction source means; at least one transaction routing means for routing each transaction generated by the transaction source means to one of the transaction processors; at least one data memory means connected with at least one of the transaction processors for storing data to be used in processing the transactions by the transaction processors; and data arrangement means for determining data arrangement of the data stored in the data memory means.

According to another aspect of the present invention there is provided a transaction routing apparatus for routing transactions from at least one transaction source to one of a plurality of transaction processors for processing the transactions, comprising: means for extracting feature parameters from each transaction; means for storing processing history information for past transactions; and means for routing each transaction to one of the transaction processors according to the feature parameters extracted by the extracting means and the processing history information stored by the storing means.

According to another aspect of the present invention there is provided an apparatus for managing data to be stored in a plurality of data storage

regions, comprising: means for receiving access requests for making accesses to the data from at least one processor; means for producing a correlation information indicating all sets of data which are accessed together in each series processing carried out by the processor according to the access requests received by the receiving means; and means for determining a new data arrangement of the data in the data storage regions according to a data storage information indicating original arrangement of the data in the data storage regions and the correlation information produced by the producing means.

According to another aspect of the present invention there is provided a method of operating a multiple processor transaction processing system, comprising: receiving transactions to be processed from at least one transaction source; routing each transaction received at the receiving step to one of a plurality of transaction processors; determining data arrangement of data to be used in processing the transactions by the transaction processors in at least one data memory connected with at least one of the transaction processors; storing the data in the data arrangement determined at the determining step; and processing each transaction by said one of the transaction processors to which each transaction is routed at the routing step, by using the data stored at the storing step.

According to another aspect of the present invention there is provided a method for routing transactions from at least one transaction source to one of a plurality of transaction processors for processing the transactions, comprising the steps of: extracting feature parameters from each transaction; obtaining processing history information for past transactions; and routing each transaction to one of the transaction processors according to the feature parameters extracted at the extracting step and the processing history information obtained at the obtaining step.

According to another aspect of the present invention there is provided a method for managing data to be stored in a plurality of data storage regions, comprising the steps of: receiving access requests for making accesses to the data from at least one processor; producing a correlation information indicating all sets of data which are accessed together in each series processing carried out by the processor according to the access requests received at the receiving step; and determining a new data arrangement of the data in the data storage regions according to a data storage information indicating original arrangement of the data in the data storage regions and the correlation information produced at the producing step.

Other features and advantages of the present invention will become apparent from the following description taken in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a schematic block diagram of one example of a conventional transaction processing system.

FIG. 2 is a schematic block diagram of another example of a conventional transaction processing system.

FIG. 3 is a schematic block diagram of a first embodiment of a multiple processor transaction processing system according to the present invention.

FIG. 4 is a schematic block diagram of one possible modified configuration for the system of FIG. 3.

FIG. 5 is a schematic block diagram of another possible modified configuration for the system of FIG. 3.

FIG. 6 is a schematic block diagram of another possible modified configuration for the system of FIG. 3.

FIG. 7 is a schematic block diagram of a transaction routing unit in one modification of a multiple processor transaction processing system according to the present invention.

FIG. 8 is a diagrammatic illustration of a data arrangement table in the transaction routing unit of FIG. 7.

FIG. 9 is a diagrammatic illustration of a routing table in the transaction routing unit of FIG. 7.

FIG. 10 is a diagrammatic illustration of a transaction in one modification of a multiple processor transaction processing system according to the present invention.

FIG. 11 is a block diagram of a transaction routing unit in a second embodiment of a multiple processor transaction processing system according to the present invention.

FIG. 12 is a block diagram of a modified configuration of the transaction routing unit of FIG. 11.

FIG. 13 is a schematic block diagram of one possible system configuration for the second embodiment of the present invention.

FIG. 14 is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 15 is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 16 is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 17A is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 17B is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 18A is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 18B is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 19A is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 19B is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 20 is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 21 is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 22 is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 23 is a schematic block diagram of another possible system configuration for the second embodiment of the present invention.

FIG. 24A is a block diagram of a partial configuration in the transaction routing unit of FIG. 11.

FIG. 24B is a block diagram of a modified configuration for the partial configuration of FIG. 24A.

FIG. 25 is a block diagram of one possible modified configuration for the transaction routing unit of FIG. 11 incorporating the modified configuration of FIG. 24B.

FIG. 26 is a block diagram of another possible modified configuration for the transaction routing unit of FIG. 12 incorporating the modified configuration of FIG. 24B.

FIG. 27 is a block diagram of a further modified configuration for the transaction routing unit of FIG. 26 in a case of an application to the remote procedure call.

FIG. 28A is a diagrmmatic illustration of a byte sequence structure of the packet used in the configuration of FIG. 27.

FIG. 28B is a diagrammatic illustration of a data structure of the packet used corresponding to the byte sequence structure of FIG. 28A.

FIG. 29 is a diagrmmatic illustration of a transaction table and a processing history information memory unit in the transaction routing unit of FIG. 27.

FIGS. 30A to 30E are illustrations of exemplary data types for the argument in the transaction used in the transaction routing unit of FIG. 27.

FIG. 31 is a schematic diagram for an operation of an RPC compiler used in the transaction routing unit of FIG. 27.

FIG. 32 is a diagrammatic illustration of a packet information obtained by the RPC compiler of FIG. 31.

FIG. 33 is a diagrammatic illustration of a processing history information used in the transaction routing unit of FIG. 27.

FIG. 34 is a block diagram of a part of the transaction routing unit of FIG. 27 for showing flow of information among elements.

FIG. 35 is a diagram of a byte sequence for the transaction packet used in the transaction routing unit of FIG. 27.

FIG. 36 is a diagram for showing a manner of extracting feature parameters from the byte sequence of FIG. 35.

FIG. 37 is a flow chart for the operation of a feature parameter extraction unit in the transaction routing unit of FIG. 27.

FIG. 38 is a diagram for showing a manner of reversing bit position in the feature parameter.

FIG. 39 is a block diagram of a transaction processor selection unit in the transaction routing unit of FIG. 27.

FIG. 40 is a flow chart for the operation of an approximated cost selection unit in the transaction processor selection unit of FIG. 39.

FIG. 41 is a flow chart for the alterntive operation of an approximated cost selection unit in the transaction processor selection unit of FIG. 39.

FIG. 42 is a flow chart for the-operation of a minimum cost transaction processor selection unit in the transaction processor selection unit of FIG. 39.

FIG. 43 is a block diagram of a transaction processor number selection unit in the transaction processor selection unit of FIG. 39.

FIG. 44 is a flow chart for the operation of a probabilistic selection unit in the transaction processor number selection unit of FIG. 43.

FIG. 45A is a diagrammatic illustration of the transaction packet used in a modification of the transaction routing scheme of the second embodiment of the present invention.

FIG. 45B is a diagrammatic illustration of the processing result used in a modification of the transaction routing scheme of the second embodiment of the present invention.

FIG. 46 is a block diagram of a weight calculation unit in the transaction routing unit of FIG. 27.

FIG. 47 is a block diagram of a cluster calculation unit in the weight calculation unit of FIG. 46.

FIG. 48 is a block diagram of a preservable record number determination unit that can be used in the second embodiment of the present invention.

FIG. 49 is a flow chart for the operation of a preservable record number update unit in the preservable record number determination unit of FIG. 49.

FIG. 50 is a diagrammatic illustration showing one possible manner of obtaning featura parameters from a packet of unknown structure.

FIG. 51 is a diagrammatic illustration showing another possible manner of obtaning featura parameters from a packet of unknown structure.

FIG. 52 is a diagrammatic illustration showing another possible manner of obtaning featura parameters from a packet of unknown structure.

FIG. 53 is a diagrammatic illustration showing another possible manner of obtaning featura parameters from a packet of unknown structure.

FIG. 54 is a diagrammatic illustration showing another possible manner of obtaning featura parameters from a packet of unknown structure.

FIG. 55 is a diagrammatic illustration showing another possible manner of obtaning feature parameters from a packet of unknown structure.

FIG. 56 is a diagrammatic illustration showing another possible manner of obtaning feature parameters from a packet of unknown structure.

FIGS. 57A and 57B are diagrammatic illustrations of possible forms of a processing history information to be used in a case of routing packets of unknown structure.

FIG. 58 is a diagrammatic illustration showing one possible form of the packets that can be handled by the second embodiment of the present invention.

FIG. 59 is a block diagram of a data management unit in a third embodiment of a multiple processor transaction processing system according to the present invention.

FIG. 60 is a diagrammatic illustration of one possible configuration of data storage regions used in the third embodiment of the present invention.

FIG. 61 is a diagrammatic illustration of another possible configuration of data storage regions used in the third embodiment of the present invention.

FIG. 62 is a diagrammatic illustration of another possible configuration of data storage regions used in the third embodiment of the present invention.

FIG. 63 is a block diagram of one possible modified configuration for the data management unit of FIG. 59.

FIG. 64 is a block diagram of another possible modified configuration for the data management unit of FIG. 59.

FIG. 65 is a block diagram of another possible modified configuration for the data management unit of FIG. 59.

FIG. 66 is a block diagram of another possible modified configuration for the data management unit of FIG. 59.

FIG. 67 is a block diagram of another possible modified configuration for the data management unit of FIG. 59.

FIG. 68 is a schematic block diagram of one possible system configuration for the third embodiment of the present invention.

FIG. 69 is a schematic block diagram of another possible system configuration for the third embodiment of the present invention.

FIG. 70 is a schematic block diagram of another possible system configuration for the third embodiment of the present invention.

FIG. 71 is a schematic block diagram of another possible system configuration for the third embodiment of the present invention.

FIG. 72 is a schematic block diagram of another possible system configuration for the third embodiment of the present invention.

FIG. 73 is a block diagram of a correlation information management unit in the data management unit of FIG. 59.

FIG. 74 is a flow chart for the operation of a correlation information generation unit in the correlation information management unit of FIG. 73.

FIG. 75 is a flow chart for the operation of a correlation information table management unit in the correlation information management unit of FIG. 73.

FIG. 76 is a flow chart for the operation of a data arrangement determination unit in the data management unit of FIG. 59.

FIG. 77 is a schematic block diagram of one possible system configuration for the third embodiment of the present invention in a case of an application to an index sequential files.

FIG. 78 is a block diagram of data management units in the system configuration of FIG. 77.

FIGS. 79A and 79B are diagrammatic illustrations of an index and a disk capacity table used in a data storage information memory unit in the data management units of FIG. 78.

FIGS. 80A and 80B are diagrammatic illustrations of series processing and defalut processing defined by the series processing information memory table in the data management units of FIG. 78.

FIG. 81 is a diagrammatic illustration of an access history memory table in the data management units of FIG. 78.

FIG. 82 is a block diagram of a correlation information table management unit in the data management units of FIG. 78.

FIG. 83 is a flow chart for the operation of a correlation information table management unit in the data management units of FIG. 78.

FIG. 84 is a diagrammatic illustration of a correlation information memory table in the data managemenet units of FIG. 78.

FIG. 85 is a flow chart for the operation of a data arrangement determination unit in the data management units of FIG. 78.

FIG. 86 is a block diagram of one possible modified configuration for the system of FIG. 59 in a case of an application to read only data.

FIG. 87 is a block diagram of another possible modified configuration for the system of FIG. 59 in a case of an application to read only data.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Referring now to FIG. 3, the first embodiment of the multiple processor transaction processing system according to the present invention will be described.

In this first embodiment, the system comprises a plurality of transaction processors 6-1 to 6-m having application programs 7-1 to 7-m for processing transactions and data management units 8-1 to 8-m for managing the data necessary for executing the application programs 7-1 to 7-m, respectively, a plurality of data memory devices 9-1 to 9-m connected with the transaction processors 6-1 to 6-m for storing the data distributedly at least one front-end processor 3 having a transaction routing unit
4 which is connected with a number of transaction sources 1-1 to 1-n which generates the transactions through a communication path 2, and a coupling device 5 for coupling the front-end processor 3 with the transaction processors 6-1 to 6-m. Here, it suffices to provide at least one data memory device 9, and each data memory device 9 may be connected with all or some of the transaction processors 6-1 to 6-m.

In this configuration of FIG. 3, it is possible to realize the high performance transaction processing system using parallel processing by a plurality of transaction processors 6-1 to 6-m, while distributing the loads of a number of transactions among a plurality of transaction processors so as to be able to cope with the high load transaction processing.

The transaction routing unit 4 provided in the front-end processor 3 receives each transaction generated by any of the transaction sources 1-1 to 1-n- through the communication path 2, and routes this transaction selectively to one of the transaction,processors 6-1 to 6-m which has the application program 7 appropriate for processing this transaction.

In addition, one of the transaction processors 6-1 to 6-m (transaction processor 6-1 in FIG. 3) has a data arrangement determination unit 10 which receives the information concerning the data accesses from the data management unit 8 of each transaction processor 6, calculates the optimum data arrangement according to this information, and commands the change of the data arrangement to each transaction processor 6. It is to be noted that this data arrangement determination unit 10 may be provided in any one or more of the front-end processor 3, the transaction processors 6, and additional processors which are neither the front-end processors nor the transaction processors.

Moreover, the data management units 8 of all the transaction processors 6 and the data arrangement determination unit 10 are capable of directly communicating through the coupling device 5. Then, when the operation target data is not present on the data memory device connected to the transaction processor of this data management unit, the data management unit requests the data operation to the data management unit of the transaction processor which has the relevant data, whereas when the operation target data is present on the data memory device connected to the transaction processor of this data management unit, the data operation is carried out locally, such that all the data are transparently accessible from any application program on any transaction processor.

In a case of using a plurality of data memory devices 9-1 to 9-m, the data are distributedly stored among the data memory devices 9-1 to 9-m. Here, in order to distribute the data, the data may be classified by using keys for example and the classified data may be stored separately on different data memory devices 9-1 to 9-m.

In arranging the data distributedly among the data memory devices 9, the data may be arranged by being divided up without any overlap, or the data may be arranged such that copies of a part or a whole of the data are provided redundantly and stored in the data memory devices different from the data memory devices storing the originals, so as to improve the anti-obstruction property.

Each data memory device 9 can be formed by any of various known memory devices such as a hard disk, a semiconductor memory, a magnetic tape, floppy disk, CD-ROM, and MO (Magneto-Optical).

Now, this transaction processing system of the first embodiment operates as follows.

The transaction is transmitted from the transaction source 1 to the transaction routing unit 4 on the front-end processor 3 through the communication path 2, and then the transaction routing unit 4 routes the transaction selectively to the optimum transaction processor for processing this transaction.

Here, the optimum transaction processor for processing this transaction is the transaction-processor which can process this transaction at the lowest cost, where the cost can be indicated by the time required in processing this transaction. The cost may be indicated by the other quantity such as a number of communications required in processing this transaction for example.

The scheme for selecting the optimum transaction processor for processing the transaction can be provided by the transaction routing scheme described in detail below as the second embodiment of the present invention. In short, in this transaction routing scheme, the processing history indicating how much cost had been required in the past when which transaction was processed by which transaction processor is stored for each transaction, and whenever a new transaction arrives, the processing history is looked up to determine which transaction processor can process this transaction at the lowest cost. Usually, the routing of the transaction to the transaction processor which has the data necessary for processing this transaction requires the lowest cost.

In this transaction routing scheme, the optimum transaction processor is selected according to the past processing history, so that this is the probabilistic approach which does not necessarily guarantee the selection of the truly optimum transaction processor. Here, however, the system of FIG. 3 has a configuration in which all the data are transparently accessible from any application program on any transaction processor, so that the use of the probabilistic transaction routing scheme does not cause the failure to process each transaction even when the routed transaction processor is not truly optimum one.

In a case it is possible to select the optimum transaction processor by the deterministic algorithm according to which data is present in which data memory device of which transaction processor, it is also possible to implement such a deterministic algorithm as a program in the transaction routing unit.

The transaction routed to the transaction processor is then processed by the application program provided on this transaction processor. Here, because the system of FIG. 3 has a configuration in which all the data are transparently accessible from any application program on any transaction processor, the same application program may be provided in all the transaction processors. Consequently, it is possible in this first embodiment to realize the parallel processing while utilizing the application programs developed on the conventional single processor transaction processing system without any change.

The data management unit receives the data operation request for the data required in executing the application program from the application program, and carries out the requested data operation. Here, when the operation target data is not present on the data memory device connected to the transaction processor of this data management unit, the data management unit requests the data operation to the data management unit of the transaction processor which has the relevant data. On the other hand, when the operation target data is present on the data memory device connected to the transaction processor of this data management unit, the data operation is carried out locally. In this data operation, the operation target data is usually specified by the key. Consequently, by providing a table recording which transaction processor has each data when the value of the specified key is within which range, it is possible to judge whether the data operation is to be carried out locally or to be requested to the data management unit of the other transaction processor. Here, the scheme for carrying out the data operation can be provided by the known data access scheme.

Now, because of the use of the probabilistic transaction routing scheme, the processing time of each transaction may vary depending on the data arrangement, and the load balance among the transaction processors may be unstable. For this reason, the data arrangement determination unit acquires statistical information concerning an access to which data is involved in the processing of which transaction, and the frequency of this access from the data management unit of each transaction processor. Then, the data arrangement determination unit obtains the optimum data arrangement by considering what arrangement of the data can make the loads on the transaction processors balanced and the cost required for processing each transaction can be lowered, according to the statistical information acquired from the data management units. The scheme for determining the data arrangement can be provided by the data arrangement scheme described in detail below as the third embodiment of the present invention.

Then, based on this determination, the data management units are commanded to move the managed data to realize the optimum data arrangement. Here, the moving of the data can be carried out by commanding the data management unit of each transaction processor from the data arrangement determination unit, or by manually according to the new data arrangement obtained by the data arrangement determination unit.

The timings for the data arrangement determination unit to carry out the rearrangement of the data by determining the optimum data arrangement can be any one of the timings specified to the data arrangement determination unit by the operator, or prescribed timings with prescribed intervals, or the timings at which the prescribed amount of the statistical information are acquired, or the timings at which the bias in the number of data accesses made by the transaction processors becomes recognizable from the statistical information, or the timings at which the bias in the load information for the transaction processors arises, or the timings specified by the transaction routing unit when the bias in the routed transaction processors arises.

By this automatic optimum data arrangement by the data arrangement determination unit, the data arrangement can be optimized by following the change of the dynamic characteristics of the system as a whole such as the change of the data to be accessed by each transaction and the change of the frequency of occurrences of each transaction.

Moreover, in accordance with this optimized data arrangement, the transaction routing unit can route each transaction to the optimum transaction processor for processing each transaction, so that by means of the feedback loop relationship between the transaction routing operation according to the data arrangement and the data rearrangement operation, the loads of the transaction processing can be balanced automatically while achieving the optimization in terms of the costs as well, without requiring the new data arrangement or the transaction routing scheme based on this new data arrangement to be specified every time the data arrangement is change. As a consequence, the tuning of the transaction processing system as a whole can also be made automatic, and the system management can be simplified.

Moreover, even in a case the optimum transaction routing strategy is not apparent at the transaction routing unit or a case the optimum distributed data arrangement is not apparent at the data arrangement determination unit, by distributedly arranging the data in an arbitrary manner, it can be guaranteed to be operable as the transaction processing system even though there are some possibilities for the load balancing of the transaction processing to be unsuccessful.

It is possible to modify the configuration of FIG. 3 as shown in FIG. 4, in which a plurality of front-end processors 3-1 to 3-l are provided instead of just one in FIG. 3. By providing a plurality of front-end processors 3-1 to 3-l between the communication path 2 and the coupling device 5, it becomes possible to replace the disabled or malfunctioning front-end processor by the other front-end processor, so that the anti-obstruction property can be improved. Also, in a case the processing power required for the transaction routing operation cannot be obtained by just one front-end processor, the load of the transaction routing operation can be distributed over a plurality of the front-end processors. Moreover, the different front-end processors may be connected with different communication paths.

It is to be noted that this transaction processing system of the first embodiment is equally applicable to the on-line transaction processing as well as to the other on-line processing.

It is also possible to modify the configuration of FIG. 3 as shown in FIG. 5, in which only one data memory device 9A is provided and commonly shared by all the transaction processors 6, so that each transaction processor is accessible to any desired data stored in this data memory device 9A.

In this case, the data management unit checks whether the operation target data to be accessed has already been accessed by the other data management unit or not. If not, this operation target data is read into the region provided within the data management unit, and then the requested data operation is carried out on this region. After the requested data operation is finished, the operation target data may be returned to the data memory device, or in a case there is a high probability for making access to this same data again, this data may be retained in the region within the data management unit. In the latter case, the other data management unit will be unable to make a direct access to this data and the access to this data have to be requested to this data management unit.

As a consequence, in this case, the data arrangement determination unit determines which data management unit of which transaction processor may retain which data on the region within that data management unit, rather than which data is to be arranged in which data memory device.

In this manner, it is possible to apply the transaction processing system of the present invention to the data sharing type configuration as well.

It is also possible to modify the configuration of FIG. 3 as shown in FIG. 6, In which a plurality of transaction routing units 4-1 to 4-m are provided in the transaction processors 6-1 to 6-m and connected with the transaction sources 1-1-1 to
1-m-k through different communication paths 2-1 to 2-m on one hand and with the coupling device 5, the application programs 7 and the data management unit 8 on the other hand, while omitting the front-end processor 3.

Here, all or some of the transaction processors may be connected with the same communication path if desired. Also, it is not necessary for the transaction routing units to be provided in all the transaction processors, and may be provided only on one or some of the transaction processors.

It is also possible to further modify this configuration of FIG. 6 in the data sharing type configuration similarly as in FIG. 5.

It is also possible to modify the first embodiment described above as follows. Namely, instead of using the processing history, the transaction routing unit can use the data arrangement information indicating how data are stored in which data memory device of each transaction processor, such that when the new transaction is received, the transaction processor on which the appropriate application program for processing this transaction is selected by looking up the data arrangement information, and the processing of the transaction is commanded accordingly.

In this case, the transaction routing unit 4 has a configuration as shown in FIG. 7, which comprises a data arrangement table 4B storing the data arrangement information, a routing table 4C storing the routing scheme for each type of transaction, and a routing determination unit 4A for determining the transaction processor for processing the newly arrived

transaction according to the data arrangement table 4B and the routing table 4C and commanding the processing of the transaction accordingly.

The data arrangement table 4B has a configuration as shown in FIG. 8, where each entry indicates, for each database, data with the key having a value in which range are stored in which data memory device of which transaction processor. For instance, the example shown in FIG. 8 indicates that, for the database called "ACCOUNT", the data with the key having the value in a range of 0 to 999 are stored in the data memory device of the transaction processor No. 0.

This data arrangement table may be produced manually and given to the transaction routing unit if desired. Alternatively, this data arrangement table may be produced by recording the information concerning the new data arrangement whenever the data arrangement determination unit determines the new data arrangement, or by recording the information concerning which data are going to be managed by each data management unit supplied from each data management unit to the transaction routing unit.

The routing table 4C has a configuration as shown in FIG. 9, where each entry indicates, for each type of transaction which can be processed by the application programs on the transaction processors, a name of the argument to be used in making the transaction routing and name of the database to be used in making the transaction routing.

Also, in this case, each transaction TR is given in a form shown in FIG. 10, which includes a header TR-1 indicating the type of transaction and a number of arguments TR-2-1 to TR-2-4 required in processing this transaction. For instance, the example of FIG. 10 shows the transaction called "WITHDRAW" which carries out the withdrawal of the deposit from the bank account, and which has four arguments including "ACCOUNT.sub.-- ID" indicating the bank account number, "TELLER.sub.-- ID" indicating the number assigned to the automatic teller machine, "BRANCH.sub.-- ID" indicating the number assigned to the branch of the bank, and "AMOUNT" indicating an amount to be withdrawn from the deposit.

The example of the routing table; shown in FIG. 9 indicates that, for the transaction "WITHDRAW", the transaction routing is made by looking up the argument "ACCOUNT.sub.-- ID" and the database "ACCOUNT". Namely, when the transaction "WITHDRAW" arrives at the transaction routing unit, the routing determination unit 4A looks up the routing table 4C to ascertain that this transaction "WITHDRAW" is to be routed according to the values of argument "ACCOUNT.sub.-- ID" and the database "ACCOUNT". Then, the value of the argument "ACCOUNT.sub.-- ID" in the transaction is taken out. Then, the transaction routing unit looks up the data arrangement table 4B to check whether there exists the data in the database "ACCOUNT" which has the whose value is the same as the value of the argument "ACCOUNT.sub.-- ID" of the transaction or not. Then, the processing of the transaction is commanded to the transaction processor checked in this manner.

The routing table may be produced manually and recorded in the transaction routing unit.

It is to be noted that in this case, the transaction routing unit is operated by the deterministic algorithm which can always select the optimum transaction processor when the routing table and the data arrangement table are given correctly, rather than the probabilistic algorithm used in the first embodiment described above. Consequently, in a case of using the deterministic algorithm, there is an advantage that it is possible to obtain the transaction routing according to the new data arrangement immediately after the data arrangement is changed. On the other hand, in a case of using the probabilistic algorithm, there is an advantage that it is unnecessary to provide the information concerning the transaction routing such as that in the routing table to the transaction routing unit.

Referring now to FIG. 11, the second embodiment of the multiple processor transaction processing system according to the present invention will be described in detail. This second embodiment mainly concerns with the transaction routing scheme which is suitable for use in the transaction routing unit in the first embodiment described above.

In this second embodiment, the system has a configuration as shown in FIG. 11 or FIG. 12, which generally comprises at least one transaction source processors 102-1 to 102-n and a plurality of transaction processors 110-1 to 110-m which are connected through a transaction routing unit 101 or 111. The transaction routing unit 101 or 111 receives the transactions generated by the transaction source processors 102-1 to 102-n, selects the optimum transaction processor for processing each transaction among the transaction processors 110-1 to 110-m. and selectively routes each received transaction to the selected transaction processor The transaction routing unit 111 of FIG. 12 differs from the transaction routing unit 101 of FIG. 11 in its internal configuration, and in the following, the description concerning the transaction routing unit 101 of FIG. 11 as a whole equally applies to the transaction routing unit 111 of FIG. 12 as a whole.

As shown in FIG. 13, the system has a physical configuration in which the transaction source processors 102-1 to 102-n are coupled with the transaction routing unit 101 through a coupling path 114-1 such as an exchanger. channel, or network, while the transaction processors 110-1 to 110-m are also coupled with the transaction routing unit 101 through another similar coupling path 114-2, and the transaction routing unit 101 is connected between the coupling paths 114-1 and 114-2. Here, the transaction source processors 102-1 to 102-n can be the terminal devices such as the automatic teller machines which generate the some kinds of transactions.

It is possible to use another physical configuration shown in FIG. 14 in which a plurality of transaction routing units 101-1 to 101-l are provided to share the load of the transaction routing processing, such that a number of transaction routing processings can be carried out simultaneously. In this case, when one transaction routing unit is broken, another transaction routing unit can be used as a substitute, so that it is possible to construct the system which is well protected against any accident.

It is also possible to use another physical configuration shown in FIG. 15 in which each one of the plurality of transaction routing units 101-1 to 101-l is coupled with a number of transaction source processors 102 independently from the other transaction routing units through one of a plurality of coupling paths 114-1-1 to 114-1-l.

Instead of providing the transaction routing unit 101 as an independent device as in FIG. 13, it is also possible to realize this transaction routing unit 101 as a function provided by a processor 115 connected between the coupling paths 114-1
and 114-2, as shown in FIG. 16, either by means of software or hardware.

The coupling paths 114-1 and 114-2 for coupling the transaction source processors 102-1 to 102-n and the transaction processors 110-1 to 110-m with the transaction routing unit 101 may not necessarily be provided separately as in FIG. 13 or FIG.
16, and as shown in FIG. 17A, a common coupling path 114 can be used in coupling all of the transaction source processors 102-1 to 102-n, the transaction processors 110-1 to 110-m, and the transaction routing unit 101. Further, as shown in FIG. 17B, the transaction routing unit 101 may be realized as a function of the processor 115 connected with the transaction source processors 102-1 to 102-n and the transaction processors 110-1 to 110-m through the common coupling path 114.

In a case of realizing the transaction routing unit 101 as a function of a processor, this processor for providing the function of the transaction routing unit 101 may not necessarily be an additional processor 115 as in FIG. 16 or FIG. 17B, and can be any of the transaction source processors 102 or the transaction processors 110 as follows.

Namely, as shown in FIG. 18A, a plurality of transaction routing units 101-1 to 101-l can be provided as functions of all or some of a plurality of transaction source processors 102-1 to 102-n, where each transaction source processor 102 directly transmits the transaction to one of the transaction processors 110 selected by the transaction routing unit 101 provided therein through the common coupling path 114.

It is also possible to provide the transaction routing unit 101 as a function of only one of a plurality of transaction source processors 102-1 to 102-n as indicated in FIG. 18B. In this case, each transaction source processor 102 which does not have the transaction routing unit 101 therein directly transmits the transaction to this one transaction source processor (102-1 in FIG. 18B) which has the transaction routing unit 101 through the common coupling path 114.

On the other hand, as shown in FIG. 19A, a plurality of transaction routing units 101-1 to 101-l can be provided as functions of all or some of a plurality of transaction processors 110-1 to 110-n. In this case, each transaction source processor
102 directly transmits the transaction to an arbitrary one of the transaction processors 110. Then, the transaction routing unit 101 provided in this one transaction processor 110 determines the optimum transaction processor 110 for processing this transaction, and the transaction is processed in this one transaction processor 110 if the determined optimum transaction processor is this same transaction processor 110 itself, whereas otherwise the transaction is transferred to the determined optimum transaction processor through the common coupling path 114.

It is also possible to provide the transaction routing unit 101 as a function of only one of a plurality of transaction processors 110-1 to 110-m as indicated in FIG. 19B. In this case, each transaction source processor 102 directly transmits the transaction to this one transaction processor (110-1 in FIG. 19B) which has the transaction routing unit 101 through the common coupling path 114.

Next, the manner of processing the transaction at each transaction processor 110 to which the transaction has been routed by the transaction routing unit 101 or 111 will be described. As shown in FIG. 20, each transaction processor 110 is equipped with an application program (transaction processing unit) 116 for processing the transaction, and a data manager (data management unit) 117 for managing the data necessary in executing the application program 116, and associated with a data memory device 118 such as a disk device for storing the data.

In FIG. 20, the application program 116 which received the transaction and started its execution requests the reading/writing of the data necessary in its execution to the data manager 117. The data manager 117 which received the request for data reading/writing carries out the requested data reading/writing operation when the target data is stored in the data memory device 118 associated with its own transaction processor 110, or requests the data manager 117 of the other transaction processor 110 to carry out the requested data reading/writing when the target data is stored in the data memory device 118 associated with the other transaction processor 110. For this reason, it is not necessary for the application program 116 to be conscious about which data is present on which transaction processor, but a case of carrying out the data reading/writing on the other transaction processor has an overhead as it is more time consuming compared with a case of carrying out the data reading/writing on its own transaction processor.

FIG. 21 shows another manner of processing the transaction at each transaction processor 110 to which the transaction has been routed by the transaction routing unit 101 or 111, in which the application program 119 which received the transaction and started its execution itself requests the reading/writing of the data necessary in its execution to the data manager 120 of the transaction processor 110 on which the target data is present. In this manner of FIG. 21, there is also an overhead in a case of carrying out the data reading/writing on the other transaction processor similarly as in FIG. 20, and it is necessary for the application program 119 itself to be conscious about which data is present on which transaction processor.

FIG. 22 shows another manner of processing the transaction at each transaction processor 110 to which the transaction has been routed by the transaction routing unit 101 or 111, in which the application program 121 which received the transaction judges whether the received transaction should be processed on its own transaction processor or not. When it is judged that the transaction should be processed on the other transaction processor, the transaction is transferred to that other transaction processor, whereas when it is judged that the transaction should be processed on its own transaction processor, its execution is started. The reading/writing of data necessary for its execution is requested to the data manager 122 on its own transaction processor, and the reading/writing of the data on the other transaction processor can be requested from the data manager 122 to the data manager of the other transaction processor as in a case of FIG. 20, or from the application program 121 itself to the data manager of the other transaction processor as in a case of FIG. 21.

FIG. 23 shows another manner of processing the transaction at each transaction processor 110 to which the transaction has been routed by the transaction routing unit 101 or 111, in which the application program 123 which received the transaction judges whether the received transaction should be processed on its own transaction processor or not. When it is judged that the transaction should be processed on the other transaction processor, the application program 123 notifies the transaction routing unit 101 that this transaction cannot be processed there. In response to this notice, the transaction routing unit 101 stores the fact that this transaction cannot be executed in that transaction processor in the processing history information by setting the processing cost for this transaction at that transaction processor to be infinitely large, and routes this transaction to another new optimum transaction processor. On the other hand, when it is judged that the transaction should be processed on its own transaction processor, the execution of the application program 123 is started. The reading/writing of data necessary for its execution is requested to the data manager 124 on its own transaction processor, and the data reading/writing of the data on the other transaction processor can be requested from the data manager 124 to the data manager of the other transaction processor as in a case of FIG. 20, or from the application program 123 itself to the data manager of the other transaction processor as in a case of FIG. 21.

Now, the internal configuration of the transaction routing unit in the system of FIGS. 11 and 12 will be described in detail.

In the transaction routing unit 101 of the system shown in FIG. 11, the transaction transmitted from the transaction source processor 102 is received by the transaction reception unit 103, which supplies the received transaction to the feature parameter extraction unit 104 and the transaction transmission unit 106. The feature parameter extraction unit 104 extracts the feature parameters from the supplied transaction, and supplies it to the transaction processor selection unit 105 as well as to the processing history information memory unit 108 in which it is stored as the feature parameters of this transaction. The transaction processor selection unit 105 compares the values of the feature parameters supplied from the feature parameter extraction unit 104 and the processing history information of the past recorded in the processing history information memory unit 108, to select the optimum transaction processor for processing the transaction, and notifies the selected transaction processor to the transaction transmission unit 106 as well as to the processing history information memory unit 108 in which it is stored as the transaction processor which processed this transaction. The transaction transmission unit 106 transmits the transaction supplied from the transaction reception unit 103 to the transaction processor 110 notified from the transaction processor selection unit 105, to complete the transaction routing processing.

The processing history information management unit 107 manages the processing history information stored in the processing history information memory unit 108, and delete the old processing history information stored in excess to a prescribed period of time or a prescribed number of processings. The transaction processor 110 which

received the transaction from the transaction routing unit 101 then processes this transaction, and notifies the processing cost required in actually processing this transaction to the processing cost detection unit 109 of the transaction routing unit 101. The processing cost detection unit 109 then supplies the received processing cost to the processing history information memory unit 108 in which it is stored as the processing cost for this transaction. Then, whenever necessary, the transaction processor 110 transmits the processing result of this transaction to the transaction source processor 102 by using an appropriate communication device.

The transaction routing unit 111 of the system shown in FIG. 12 similarly as the transaction routing unit 101 of the system shown in FIG. 11 up to a point at which the transaction is transmitted from the transaction transmission unit 106 to the transaction processor 110.

The transaction processor 110 which received the transaction from the transaction routing unit 111 then processes this transaction. but unlike the case of FIG. 11, the processing cost required in actually processing this transaction is not explicitly notified to the transaction routing unit 111. Instead, the transaction processor 110 returns the processing result of this transaction to the transaction routing unit 111, in which the returned processing result is received by the processing result reception unit 112 and supplied to the processing result transmission unit 113 while notifying the fact concerning the reception of the processing result to the processing cost detection unit 109. The processing result transmission unit 113 which received the processing result then returns the processing result of this transaction to the transaction source processor 102 which generated this transaction.

On the other hand, the processing cost detection unit 109 which is notified about the reception of the processing result obtains the cost required in processing this transaction accordingly, and supplies the obtained processing cost to the processing history information memory unit 108 in which it is stored as the processing cost for this transaction. In the processing cost detection unit 109, the processing cost can be obtained by a scheme for setting a time difference between a time at which the transaction is received and a time at which the processing result for this transaction is received as the processing cost, or a scheme for setting a number of transactions which were received after this transaction and for which the processings were completed before the processing of this transaction was completed as the processing cost.

In the configurations of FIG. 11 and FIG. 12, the feature parameters extracted from the received transaction are stored in the processing history information memory unit 108, and the transaction processor selection unit 105 selects the optimum transaction processor according to the feature parameters of the past processing history recorded in the processing history information memory unit 108, as indicated in FIG. 24A.

Alternatively, it is also possible to store the transaction itself in the processing history information memory unit 108 instead of the feature parameters. In this case, as indicated in FIG. 24B, the the transaction reception unit 103 stores the received transaction as it is into the processing history information memory unit 108, and the transaction processor selection unit 105 looks up the processing history information through additional feature parameter extraction unit 104A provided between the transaction processor selection unit 105 and the processing history information memory unit 108 which extracts the feature parameters from the transaction stored in the processing history information memory unit 108 and supplies it to the transaction processor selection unit 105. When this modification is incorporated into the configuration of FIG. 11, the system has the transaction routing unit 101A in a modified configuration as shown in FIG. 25. Similarly, when this modification is incorporated into the configuration of FIG. 12, the system has the transaction routing unit 111A in a modified configuration as shown in FIG. 28.

Now, the operation principle of the transaction routing unit in this second embodiment of the present invention will be described in detail.

In the transaction routing unit of this second embodiment, when the new transaction is received, the feature parameters of this transaction are extracted first. Here, the feature parameters are given as a set of a plurality of values for each transaction in general.

Then, the feature parameters of the new transaction and the feature parameters in the stored processing history information for the past transactions are compared, to select out the processing history information which has the feature parameter value closest to that of the new transaction, for each transaction processor and for each feature parameter.

Namely, when there are M transaction processors which can process this new transaction, the feature parameters comprise a set of N values, and the feature parameters of this new transaction are set as X[n] (0.ltoreq.n<N), M.times.N pieces of the processing history information H[m, n] (0.ltoreq.m<M, 0.ltoreq.n<N) are selected out such that the following condition is satisfied. ##EQU1## where A is a set of all the processing history information currently stored, H[m, n][p] is a p-th value in the set of feature parameter values for the processing history information H[m, n], and node(F) is a transaction processor number of the transaction processor which had processed the transaction recorded in the processing history information F.

Then, among M.times.N pieces of the processing history information H[m, n] selected out in this manner, the transaction processor P[n] (0.ltoreq.n<N) which can be a candidate for processing the transaction is selected for each feature parameter such that the following condition is satisfied. ##EQU2## where cost(F) is the processing cost of the transaction recorded in the processing history information F.

In other words, among a plurality of selected processing history information H[m, n], for each feature parameter, the processing history information with the lowest cost is selected, and the transaction processor which had processed this transaction corresponding to this selected processing history information is set as a candidate transaction processor P[n]. Here, in a case the processing cost of the processing history information H[P[n], n] selected as the candidate is significantly lower than the processing costs of the other processing history information having the same feature parameter, there is no problem in selecting this processing history information as the appropriate candidate transaction processor.

However, in a case the processing cost of the processing history information H[P[n], n] has no significant difference from the processing costs of the other processing history information, even when the processing history information with the lowest cost is simply selected, the possibility for this to be actually the appropriate candidate transaction processor is small. Consequently, in order to remove such processing history information with small possibility from the consideration of the candidate transaction processor, the candidate transaction processor which does not satisfy the following condition is removed from the candidate transaction processors. ##EQU3##

In other words, when the average value of the costs of the processing history information H[m, n] having the same feature parameter is larger than the cost of the processing history information H[P[n], n] for the selected candidate transaction processor P[n] by as many times as a prescribed number T, it is considered that there is a significant difference, and otherwise this selected candidate transaction processor is removed from the candidate transaction processors. Here, the number T has a value such as 1.1 for instance. In this algorithm, when there is no candidate transaction processor, the value of P[n] is set to a value such as -1 which is actually invalid as the transaction processor number.

Then, among N candidate transaction processors P[N] selected in this manner, the actual optimum transaction processor is selected. Here, the weight information W[N] for each feature parameter is used. Each element W[k] of the weight information W[N] indicates the strength of correlation between the k-th feature parameter value of the corresponding transaction and the transaction processor for processing that transaction. When the corresponding elements of P[N] and W[N] arranged in an order of largeness of the value of W[N] are set as PP[N] and WW[N], the actual procedure for selecting out the optimum transaction processor for processing the transaction can be described in the C language as follows. ##EQU4## where random() is a function which generates a random number in a range of the real number values between 0 and 1, and "pickednode" is a variable for substituting the transaction processor number for processing the transaction, whose initial value is -1 that does not corresponds to any transaction processor. In an order of the largeness of the weight, the random number is generated and when its value is less than the weight, this transaction is selected, whereas otherwise the above selection procedure is continued for the next candidate. In a case the candidate cannot be determined eventually, the transaction processor for processing this transaction is selected by an appropriate manner. In the exemplary procedure described here, one of the M transaction processors is selected by the random number.

In the following, the exemplary case of applying the transaction routing scheme of this second embodiment to the remote procedure call (RPC) based transaction processing system will be described in detail.

In this case, the system has a configuration as shown in FIG. 27, which differs from the configuration of FIG. 26 described above in that the weight calculation unit 127, the transaction table 128 and the transaction table management unit 125 are additionally provided, while the feature parameter extraction unit 104 and the additional feature parameter extraction unit 104A are renamed as the feature parameter extraction unit I 128 and the feature parameter extraction unit II 129 in the transaction routing unit 111B. Namely, in this configuration of FIG. 27, the configuration of FIG. 26 which is for the transaction routing for only one type of transaction is expanded to be capable of dealing with more than one types of transaction.

In this configuration of FIG. 27, the transaction reception unit 103 receives the transaction packet transmitted from the transaction source processor 2 through a coupling path. In a case the coupling path is provided by the ethernet, the packet arriving at the particular port of the UDP protocol is received. Here, the packet is the data having the byte sequence structure as shown in FIG. 28A, and in the transaction packet of the RPC, this byte sequence of FIG. 28A will be interpreted as the data of the structure as indicated in FIG. 28B. Namely, the top of the packet has the data indicating the type of transaction. Actually, a unique identification number corresponding to "proc1" is registered as a numerical value occupying the top 4
bytes of the packet. Thereafter, as many arguments associated with the transaction as necessary are registered. In the example of FIG. 28B, three 4 bytes length data x, y, and z are arranged there. There are many other packet structures for the RPC, and the present invention is applicable to any packet structure other than that shown in FIG. 28B.

A position of the type of transaction in the packet of the RPC is fixed, so that the transaction reception unit 103 which received the packet can extract the type of transaction from the received packets and the transaction reception unit 103
supplies the extracted type of transaction to the transaction table 128. Here, it is also possible to provide a configuration in which the transaction reception unit 103 can receive the transaction packets arriving at a plurality of ports. In such a case, it is also possible to produce the transaction table for recording the information concerning the transactions arrived at that port for each port, such that when the packet is received, the transaction reception unit 103 supplies the type of transmission to the transaction table corresponding to the port from which this transaction has been received.

The transaction table 126 is in a form shown in FIG. 29 in which each entry has five fields for registering the type of transaction, the argument information, the weight information, the transaction processor information, and the processing history information pointer pointing to the processing history information in the processing history information memory unit 108 in correspondence.

The type of transaction is given by a value indicating the type of transaction at the top of the transaction packet. In the example shown in FIG. 29, "proc1" and "proc2" are the values indicating the types of transaction, and actually the numerical values corresponding to these "proc1" and "proc2" are registered. The argument information registers the data types of the arguments of the transaction for each type of transaction. In the example shown in FIG. 29, the type of transaction "proc1" has three arguments, whose data types are "int" (integer type), "string" (character string type), and "float" (floating point type). Actually, an array of numerical values assigned to "int", "string", and "float" are registered.

It is to be noted that the data types such as "int". "string", and "float" used in FIG. 29 are all in a form without any structure, but in a case of using a structural entity as indicated in FIG. 30A as an argument, the argument information is given, as shown in FIG. 30B, as a set of a numerical value for "struct" which indicates that it is a structural entity, a number of members constituting this structural entity such as "2", and numerical values for the data types of the members such as "int" and "char". Also, in a case of using an array as indicated in FIG. 30C, the argument information is given, as shown in FIG. 30D, as a set of a numerical value for "array" which indicates that it is an array, a number of elements of the array such as "10", and a numerical value for the data type of each element such as "int". It is also possible for such a structural entity or an array to have its constituent element given by a structural entity or an array.

In many RPC systems, the format of the packet to be used for the actual communication is determined from the interface description as shown in FIG. 30E. This is usually done by the program called RPC compiler, which operates as indicated in FIG.
31. Namely, the RPC compiler 31-1 takes the RPC interface description 31-0 as input, and outputs a client stub 31-2 for the purpose of transmitting the transaction in the packet format corresponding to the interface description, a server stub 31-3 for the purpose of receiving this transaction packet, and a header file 31-4 describing the information commonly used by the client and the server. This RPC compiler 31-1 is provided as a program "rpcgen" in the ONC RPC, and as a program "idl" in the DCE RPC.

In addition, in this second embodiment, the RPC compiler 31-1 also outputs a packet information 31-5 in a form shown in FIG. 32, which includes data to be registered as the type of transaction and the argument information in the transaction table
126. Namely, when the interface description shown in FIG. 30E is given, the type of transaction "proc1" and the argument information "int", "string", and "float" are generated. Here, as described above, "proc1", "int", "string", and "float" are actually given by the uniquely assigned numerical values. In the configuration of FIG. 27, the transaction table management table 125 reads this packet information, and registers the type of transaction and the argument information contained therein into the transaction table 126.

The weight information in the transaction table 126 of FIG. 29 is a set of numerical values indicating weights for the arguments of each type of transaction. This weight information indicates which element of the feature parameters is to be given more consideration in a case of predicting the transaction processor to which the transaction is to be routed, and is in a form of an array having elements in one-to-one correspondence to the elements of the feature parameters. In the example of FIG. 29, the type of transaction "proc1" has three arguments but the

weight information is in a form of a vector having four elements, because the feature parameters include all the arguments as well as a numerical value in which a bit position is changed in a part of these arguments. More specifically, in this example, a numerical value in which a bit position is changed for the argument of the integer type is also included in the feature parameters, so that the weight information is in a form of a vector having four elements.

The method for extracting the feature parameters from the RPC packet, the method for changing the bit position, and the method for determining an element of the feature parameters for which the bit position changed value is to be included in the feature parameters will be described later.

The transaction processor information in the transaction table 126 of FIG. 29 enumerates the transaction processors which can process each type of transaction, which are actually expressed by the network address of the transaction processors and the port number on the transaction processors which are used at a time of transferring the transactions. In the example of FIG. 29, the first transaction processor information for "proc1" indicates that the network address of the transaction processor is 62.31 and the port number is 70.

The processing history information pointer in the transaction table 126 of FIG. 29 is pointing to a group of those processing history information stored in the processing history information memory unit 108 which belong to the each type of transaction. As shown in FIG. 33, each processing history information comprises a content of the transaction, the processor number of the transaction processor which processed the transaction, the processing cost (time in this example) required in processing the transaction, and an information on the transaction source processor which is necessary at a time of returning the processing result and which can be given by the network address and the port number for example. Here, rather than recording the transaction as it is, the feature parameters extracted from the transaction or only the elements of the feature parameters having large weights which significantly contributes to the prediction of the transaction processor may be recorded if desired.

FIG. 34 shows the flow of the information centered around the transaction table 126 in the configuration of FIG. 27. In this FIG. 34, only those modules in the configuration of FIG. 27 which contribute to the determination of the transaction processor are selectively shown, and the information exchanged among these modules is indicated.

The information recorded in the transaction table 126 is generated as the packet information by the RPC compiler of FIG. 31. This packet information is generated in a form of the file, read by the transaction table management unit 125, and registered in the transaction table 126. Here, the initial values of the weight information in the transaction table 126 may be given by a programmer or a system manager, or set to a particular initial value such as 0.9 for all the elements. The transaction processor information may be given by a programmer or a system manager, or registered by a name server which checks the transaction processors which can process the transaction. It is also possible to use a scheme in which each transaction processor 110 reports the types of transaction that can be processed thereon to the transaction routing unit and the transaction processor information is registered into the transaction table 126 according to this report. The initial value of the processing history information pointer in the transaction table 126 is set to point any processing history information of the relevant type of transaction still left in the processing history information memory unit 108, or to a set of empty processing history information when there is none left in the processing history information memory unit 108.

When the transaction reception unit 103 received the RPC packet of the transaction from the transaction source processor 102, this transaction packet is supplied to the feature parameter extraction unit I 128 and the transaction transmission unit
106 of the next stage. Also, the transaction and the transaction source processor which generated this transaction are registered in the processing history information memory unit 108 as a new processing history information. In addition, the information indicating the type of transaction which is present at the top of the received transaction packet is extracted and supplied to the transaction table 126.

The transaction table 126 is looked up by using the type of transaction received from the transaction reception unit 103 as a key, and as a result, the argument information is supplied to the feature parameter extraction unit I 128 and the feature parameter extraction unit II 129, the weight information is supplied to the transaction processor selection unit 105, the transaction processor information is supplied to the transaction transmission unit 106, and the processing history information pointer is supplied to the processing history information memory unit 108.

The feature parameter extraction unit I 128 which received the transaction packet and the argument information from the transaction reception unit 103 and the transaction table 126, respectively, then extracts the feature parameters of the received transaction and supplies them to the transaction processor selection unit 105.

Here, the transaction packet is in a form of the byte sequence as shown in FIG. 35, which has the data indicating the type of transaction at its top. For example, when the top one word (4 bytes) indicates the type of transaction, the numerical value "372" in decimal ("174" in hexadecimal) indicates the type of transaction, where "372" indicates "proc1" in this example. After the data indicating the type of transaction, the arguments associated with the transaction are indicated. In a case of "proc1", as also given as the argument information in the transaction table 126, the first argument is the integer type ("int"), the second argument is the character string type ("string"), and the third argument is the real number type ("float").

There are many manners for expressing each of these data types on the network packet, and the present invention is applicable to any of these manners. In this example, the integer and the real number are expressed as 4 byte data, while the character string is expressed by 4 byte integer indicating the character string length followed by 1 byte indicating a series of characters. For instance, in FIG. 35, the first argument is the integer value "6700", the second argument is the character string "abcdefg", and the third argument is the real number value "12.5".

The argument information which is another input data of the feature parameter extraction unit I 128 is an array indicating the data types of the arguments for each type of transaction. This argument information is an example of the information on the data structure of the transaction, and with reference to this information, the basic data units are extracted from the transaction and set as the feature parameters. For instance, as indicated in FIG. 36, when the data types are coded such that the integer type is represented by a value 1, the real number type is represented by a value 2, and the character string type is represented by a value 3, then the argument information of "proc1" is in a form of a vector (or array) having three values of
1, 3, and 2 in this order.

The feature parameter extraction unit I 128 which received these transaction packet and argument information then extracts the feature parameters by the operation according to the flow chart of FIG. 37, and supplies it to the transaction processor selection unit 105. Namely, the feature parameter extraction unit I 128 takes the argument portion of the transaction packet P and the argument information T as its inputs (step 3701), and unless the argument information T is empty (step
3702), the feature parameter extraction unit I 128 extracts the argument portion of the transaction packet corresponding to each element t of the argument information sequentially (step 3703). Then, according to the data type of the element t of the argument information (step 3704), the feature parameter extraction unit I 128 obtains and outputs the corresponding feature parameter values sequentially as follows.

Namely, in a case the data type of the argument registered in the argument information is the integer type (represented by a value t=1), the top 4 byte data I is extracted from the argument portion of the transaction packet and converted into the integer (step 3705), and then this data I is outputted as the feature parameter value given by the one word integer value as it is (step 3706). Although not shown in FIG. 37, the character type and the enumeration type arguments are similarly handled by extracting the data of a necessary number of bytes, reading it as the integer value, and outputting that integer value as the feature parameter.

In a case of the real number type (represented by a value t=2), the top 4 byte data F is extracted from the argument portion of the transaction packet and interpreted as the real number value (floating point number) of the single precision (step
3708), and then this value of the data F is outputted as the feature parameter value (step 3709). The same procedure can also be used for the case of the real number value of the double precision.

In a case of the character string type (represented by a value t=3), several schemes can be used. In the example of FIG. 37, the top 4 byte data L is extracted from the argument portion of the transaction packet and converted into the integer (step 3710). Then, the top L byte data S is extracted from the argument portion of the transaction packet (step 3711) while supplementing 0 or blank space when it is less than 4 bytes, and the top 4 byte data I is extracted from the L byte data S and converted into the integer (step 3712). Then, this data I is outputted as the feature parameter value given by the one word integer value as it is (step 3713).

In this manner, the character string is cut off at a predetermined length, and read as if it is a numerical value so as to obtain the feature parameter. Here, the cutting off the character string is done by a manner of extracting a prescribed length from the top of the character string, or a manner of extracting a prescribed length from the end of the character string, or a manner of extracting a prescribed length from the top and the end of the character string and combining them. Moreover, there is also a scheme for including the length of the character string as the feature parameters in addition to the extracted character string. Furthermore, there is also a scheme in which the character string is supplied to the transaction processor selection unit 105 as it is as the feature parameter instead of setting it into the numerical value, such that the selection of the transaction processor can be made by comparing this feature parameter in a dictionary-like order.

Although not shown in FIG. 37, the data type used in the argument information also includes the composite type such as an array or a structural entity. In a case of the array of a fixed length, the simplest scheme is to extract the feature parameters of all of its elements and set them as the feature parameters of the array. In a case of the array of a fixed length or a variable length, just as in a case of the character string type, a prescribed number of them from the top, or a prescribed number of them from the end, or a combination of a prescribed number of them from the top and the end can be used as the feature parameters. Moreover, in a case of the array of a variable length, it is also possible to include the size of the array as the feature parameters. In a case of a structural entity, the feature parameters of the constituting elements are sequentially extracted and they are set as the feature parameters of the structural entity. The feature parameters can be obtained in the similar manner even in a case of the combinations of the above described cases such as those of the array of structural entities or the array of character strings.

In this second embodiment, the value in which a bit position is permutate in some element of the feature parameters is also included in the feature parameters. This inclusion of a bit position inverted value in the feature parameters is effective when there is a correlative relationship between the upper bit values of the argument of the transaction and the optimum transaction processor for processing this transaction, as it becomes possible to make the feature parameter values of the transactions which are preferably processed by the same transaction processor to be close to each other, and therefore the judgment at the transaction processor selection unit 105 can be strengthened by utilizing this fact. Also, the bit position inverted value in the feature parameters of the argument having a correlative relationship with the optimum transaction processor is going to be the random feature parameter which has no correlative relationship with the optimum transaction processor. On the contrary, in a case the bit position inverted value in the feature has a correlative relationship with the optimum transaction processor, the value before the bit position inversion is going to be the random feature parameter which has no correlative relationship with the optimum transaction processor.

Consequently, by the inclusion of a bit position inverted value in the feature parameters, the random component which can be a reference in comparing the correlative relationship between each feature parameter value and the optimum transaction processor is going to be always present in the feature parameters. Then, by the presence of such a random component, it becomes possible to eliminate the situation in which it is difficult to judge if there is a correlative relationship between each element of the feature parameters and the optimum transaction processor uniformly, or if there is no correlative relationship between all the elements of the feature parameters and the optimum transaction processor uniformly.

As for a scheme for inverting the bit position, there are many possible schemes, and any such schemes can be utilized in the present invention. The most promising scheme for inverting the bit position is a bit reverse scheme for reversing the bit position as indicated in FIG. 38. Namely, the feature parameter value is obtained by reversing the upper bits and the lower bits of the feature parameter, and reading the resulting bit sequence as if it is a numerical value.

As a scheme for determining the argument whose bit position inverted value should be included in the feature parameters, there are a scheme for including the bit position inverted value of every element of the feature parameters, a scheme for including the bit position inverted values of those elements of the feature parameters which are in a prescribed particular data type, and a scheme for including the bit position inverted values of those arguments which are specified by a programmer or a system manager.

In the example of FIG. 37, a scheme for including the bit position reversed value for the arguments of the integer type in the feature parameters is used. Thus, in a case the data type of the argument registered in the argument information is the integer type (represented by a value t=1), after the step 3706, the bit position reversed value for the data I is also outputted as the feature parameter value (step 3707).

The feature parameter extraction unit II 129 which receives the argument information and the processing history information from the transaction table 126 and the processing history information memory unit 108, respectively, carries out the feature parameter extraction by the same procedure as the feature parameter extraction unit I 128 described above. The processing history information memory unit 108 sequentially transmits a plurality of processing history information belonging to the particular type of transaction specified by the processing history information pointer received from the transaction table 126 to the feature parameter extraction unit II 129. Then, the feature parameter extraction unit II 129 which received the processing history information extracts the feature parameters from the transaction recorded therein by the same scheme as the feature parameter extraction unit I 128, and supplies it to the transaction processor selection unit 105. At this point, the transaction processors and the processing costs recorded in the processing history information for that transaction are also supplied to the transaction processor selection unit 105.

The transaction processor selection unit 105 has a configuration as shown in FIG. 39. This transaction processor selection unit 105 receives the feature parameters of the newly arrived transaction 390 from the feature parameter extraction unit I
128, and the feature parameters, the transaction processor, and the processing cost 391 taken out from the processing history information having the same type of transaction that

had been processed in the past sequentially from the feature parameter extraction unit II 129, and supplies them to the respective approximated cost selection units 130.

For one of a plurality of feature parameters and for one of a plurality of transaction processors which had processed the transaction of the same type in the past, each approximated cost selection unit 130 selects out the processing cost of one of the processing history information processed by that transaction processor in the past for which the corresponding feature parameter value is closest. Namely, the approximated cost selection unit 130 for the i-th feature parameter and the j-th transaction processor carries out the operation according to the flow chart of FIG. 40 as follows.

First, the feature parameter number i and the transaction processor number j of this approximate cost selection unit 130 set out (step 401). Then, the i-th feature parameter value of the feature parameters of the newly arrived transaction is set to be P while a set of the processing history information for transactions of the same type which had been processed in the past by the j-th transaction processor is set to be H (step 402). Then, the approximate cost C and the difference "diff" are initialized to 0 and .infin., respectively (step 403). Then, unless the set H becomes empty (step 404) in which case the current value of the approximated cost C is outputted (step 405), each processing history information h of the set H is taken out (step 408), and an absolute value of the difference between P and the i-th feature parameter value of the processing history information h taken out by the feature parameter extraction unit II 129 is obtained and set as "tmp" (step 407). Then, when the obtained value "tmp" is smaller than the difference "diff" (step 408), this value "tmp" is set as a new value for the difference "diff", while the approximated cost C is changed to the processing cost of the processing history information h (step 409). Then, either when "tmp" is not smaller than the difference "diff" at the step 408 or after the step 409, the steps 404 and below are repeated for the next element h of the set H.

In this manner, the processing cost of the processing history information for which the resulting difference is the smallest is output as the approximated cost C. In this scheme of FIG. 40, when there is no transaction which had been processed by the transaction processor, the processing cost is set to be 0.

On the other hand, the approximated cost selection unit 130 for the i-th feature parameter and the j-th transaction processor may carry out the operation according to the flow chart of FIG. 41, where there is no transaction which had been processed by the transaction processor, the processing cost is set to be a at the step 413 replacing the step 403 in FIG. 40. Thus, when the processing cost is 0, the transaction is routed to that transaction processor at the highest priority, whereas when the processing cost is .infin., the transaction is not going to be routed to that transaction processor. In the scheme of FIG. 40 or FIG. 41, the comparison of the feature parameter values is made arithmetically. It is also possible to utilize the Hamming distance in this comparison, it is also possible for the character string that the comparison based on a dictionally-like order can be used. It is further possible to utilize a plurality of the above described schemes in parallel.

Apart from the ab