December 5, 2015 at 00:49Request Processing Priority Allocation Algorithm
- Tutorial
Consider the existing models for the optimal distribution of data among the nodes of a computer network. As performance criteria, we will use the average amount of data sent over communication lines when processing requests and distributing updates, the total cost of traffic generated by the operation of a distributed computing system for a unit of time, and the operational cost of the network ¹. As an example, we consider a model of optimal file allocation over a computer network with a performance criterion - the average amount of data sent over communication lines when processing requests and distributing updates.
Consider a computer network, each node, which consists of a computer, terminal devices and data transmission equipment. Suppose that a request arriving at the terminal device of any node implies access to a specific file in a distributed database, and the volume of the request and correct message to the same file depends on the node without which it arrived. We assume that the request processing scheme is as follows.
The request initiated at the terminal enters the input queue of the corresponding node. The computer processor processes the requests in the order they are received. If a copy of the desired file is contained in the local database of the node to the terminal of which the request was received, the request is processed and the result is displayed on this terminal. If a copy of the desired file is not contained in the local database of the node, then first, the directory containing the copy of the necessary file is determined from the directory of the local database. Then the request is sent to that node, it is processed there and the response is received by the original node. The procedure for servicing requests does not affect the amount of data sent over communication channels.
Corrective messages are served in the order of their queue. However, compared with message requests, they have the highest priority of service.
In the process of servicing request and correcting messages, a certain amount of data is sent over the communication channels over each unit of time, depending on the distribution of copies of files across local databases. The smaller the amount of data sent over communication channels per unit of time, the higher the speed of message processing.
Path
n is the number of network nodes;
t is the number of independence of the files included in the distributed database;
Kj is the jth communication node;
Fi- i-file of a distributed database;
аv - the amount of requested data when executing a request to a Fi file from the Kj node;
βv is the amount of requested data when executing a request to a Fi file from node Kj;
Yv is the volume of the correction message to the file Fi from the node Kj;
λv is the intensity of requests to the Fi file initiated at the node Kj;
λ`v is the intensity of the corrective messages to the file Fi from the node Kj;
bj - the amount of memory node Kj, designed to accommodate files;
Vj is the number of copies of the i-th file (Vj is the given value i <= Vji <= n);
Хv (I = I, m¸ j = I, n) - values determined by the formula.
{I, if a copy of the file Fi, is located in the node Kj;}
Хv {О¸ otherwise}
The intensity λi generates the amount of data
Vi = ΣAλ`v UVXi
5 - i
5 - j
needing transfer. If we put
nk
λ` = ΣΣAV
i = jj = i
then the average amount of data necessary for forwarding when processing the correction message in the system is equal.
nkх
V` =IΣΣΣλ`v УvХI
λ` i= j j= i 5 — i
5 – j
Интенсивность λ`v порождает объем данных λ`v (av+β) (I-Хv) нуждающихся в пересылке. Поэтому средний объем данных, необходимых при пересылке при выполнении запроса в системе равен
n k
V`= IΣΣλ`v (av+β) (I-Х v)
λ` i= jj= i
n k
гдеλ=Σ Σλ`v
i= j j= i
Таким образом, математическая модель задачи оптимального распределения копий файлов по узлам вычислительной сети для критерия оптимальности средней объем пересылаемых данных по линиям связи при обработке запросного и корректирующего сообщения будет следующей: требуется найти минимум линейной функции
L,= V+V'
при ограничениях
n
Σ xv=yi(i=I,m)
i = j
n
ΣL, xv ≤ bi (i = I, n)
i = j
Хv = (o ﮞ I) I'I, m, j = I, n)
To improve the performance of the system, restrictions can be used as an additional condition the expected time to complete the request from each node. Indeed, let aifz be the expected time required to execute the request initiated at the Kj node to the Fj file that is contained in the Kj node, Tif be the maximum allowable time to complete the request to the Fj file initiated at the Kj node. Then, between the values aifz and Тv, the relations
av5 (I-Хv) Х15 ≤ Тv hold
for j <> S, I <> i <> m.
In order to obtain restrictions from this relation, the values of aifz should be expressed in terms of the variables Xv. In the general case of network topology, this is very difficult to do. And only if you do not use a number of assumptions imposed on the characteristics of the network, you can find simple expressions of knowledge aifz through Хv.
The disadvantages of the developed models can be attributed to the fact that they contain a number of limitations and simplifications, do not reflect such a feature of the RDB as a fragment. The disadvantages of the developed models can be attributed to the fact that they contain a number of limitations and simplifications, do not reflect such a feature of the RDB as fragmentation, and also that they are static and do not take into account the dynamics of the processes occurring in the system.
As for the methods used to optimize the RDB — the branch and bound method, mathematical programming — they gave positive results, since for real folded computer information systems with DBD, the dimensionality of the problem is large, which requires considerable time and computational resources. Therefore, for this task, it is advisable to use genetic algorithms that implement directed random search based on the mechanisms of natural evolution.
Thus, despite the previous studies, the issues of modeling and optimization of computer information systems DBDs have not received a final solution, the models and methods used have a number of drawbacks, which necessitated their further improvement.
An equally important issue is the provision of the most accurate source data. The implementation of any mathematical model. The optimal placement of RBD files on the nodes of a computer network requires a number of information arrays of source data, a significant part of which can only be obtained in an average or reduced form. These are such characteristics as request intensities, time for sending and processing requests, volumes of requests and responses to requests. The accuracy of the collected static information will decisively affect the final result of the implementation of the selected mathematical model and, consequently, the performance of the system working with the RDB.
To obtain reliable numerical data, it is necessary to determine the cyclical nature of the information in the system. This period can vary between applications from one day to a quarter. In the further processing of the collected information, it is necessary to take into account as average bursts of activity. The numerical characteristics of processing time, volume, shipments and handling probabilities must be calculated with allowance for peak situations in order to protect the system from significant delays during the most intensive downloads.
In addition to the listed characteristics, in the process of working with the optimized database, it is necessary to accumulate information about the type of request (reading, searching, updating) the name of the file to which the request was issued, the number of the node from which the request was issued, and the time of the real response.
A knowledge base is a set of knowledge units that represent the formation, using some method of representing knowledge, the reflection of objects in a problem area and their relationships, actions on objects and, possibly, the uncertainties with which these actions are carried out.
As methods for representing knowledge, most often either rules or objects (frames), or a combination of them, are used. So, the rules are constructions.
If <condition> Then <conclusion> CF (certainty factor) <value>.
As determinants of certainty (CF), as a rule, one encounters either the conditional probabilities of the Bayesian approach (from 0 to 1) or the confidence coefficients of the odd logic (from 0 to 100). Examples of rules are as follows.
Rule 1. If Profitability Ratio>
Then Profitability = “Satisfied” CF 100.
Rule 2. If Debt = “no” and Profitability = “Satisfied”.
That is Enterprise Reliability = “Satisfied” CF 90.
At any given time in the system, there are types of knowledge:
Structured knowledge - statistical knowledge about the subject area. Once knowledge is identified, it no longer changes.
Structured dynamic knowledge - changeable knowledge of the subject area, they are updated as new information is discovered.
The quality of ES is determined by the size and quality of the knowledge base (rules or heuristics). The system operates in the following cyclic mode: selection (query) of the data or results of observation analyzes, interpretation of the results, assimilation of new information, advancing temporal hypotheses using the rules, and then selecting the next portion of data and analysis results. This process continues until there is enough information for a final conclusion.
Thus, an artificial intelligence system built on the basis of high-quality specialized knowledge about a certain subject area (obtained from experts - specialists in this field) is called an expert system. Expert systems - one of the few types of artificial intelligence systems - have become widespread and have found practical application.
Expert systems differ from other programs in the following ways:
1. Competence - in a specific subject area, the expert system must reach the same level as human experts, while it must use the same heuristic techniques and also reflect the subject area deeply and widely;
2. Symbolic reasoning–The knowledge on which expert systems are based represent in a symbolic form the concepts of the real world, reasoning also occurs in the form of transformations of symbolic sets;
3. Depth - the examination should solve deep, non-trivial problems marked by complexity either in terms of the complexity of knowledge that the expert system uses or in terms of their abundance, this does not allow the use of exhaustive search of options as a method of solving problems and makes it resort to heuristic, creative, informal methods ;
4. Self-awareness - the expert system should include a mechanism for explaining how it comes to solving the problem.
Literature
1. Moiseev VB Representation of knowledge in intelligent systems. / Informatics and education, No. 2, 2003.
2. Petrov V.N. Information Systems - St. Petersburg: Peter, 2003.
3. Rastragin L.Kh. Experimental control systems. - M .: Nauka, 1974.
4. Saak A.E., Pakhomov E.V., Tyushnyakov V.N. Management Information Technology: Textbook for high schools. St. Petersburg: Peter, 2005.
5. Semenov M.I. and others. Automated information technology in the economy. Textbook. - M .: Finance and statistics, 2003.
6. Sovetov B.Ya. Modeling systems: Textbook for universities. - 3 - ed. reslave. and dock. - M.: Higher School, 2001.
7. Suvorova N. Information modeling: quantities, objects, algorithms. - M .: Laboratory of basic knowledge, 2002.
Consider a computer network, each node, which consists of a computer, terminal devices and data transmission equipment. Suppose that a request arriving at the terminal device of any node implies access to a specific file in a distributed database, and the volume of the request and correct message to the same file depends on the node without which it arrived. We assume that the request processing scheme is as follows.
The request initiated at the terminal enters the input queue of the corresponding node. The computer processor processes the requests in the order they are received. If a copy of the desired file is contained in the local database of the node to the terminal of which the request was received, the request is processed and the result is displayed on this terminal. If a copy of the desired file is not contained in the local database of the node, then first, the directory containing the copy of the necessary file is determined from the directory of the local database. Then the request is sent to that node, it is processed there and the response is received by the original node. The procedure for servicing requests does not affect the amount of data sent over communication channels.
Corrective messages are served in the order of their queue. However, compared with message requests, they have the highest priority of service.
In the process of servicing request and correcting messages, a certain amount of data is sent over the communication channels over each unit of time, depending on the distribution of copies of files across local databases. The smaller the amount of data sent over communication channels per unit of time, the higher the speed of message processing.
Path
n is the number of network nodes;
t is the number of independence of the files included in the distributed database;
Kj is the jth communication node;
Fi- i-file of a distributed database;
аv - the amount of requested data when executing a request to a Fi file from the Kj node;
βv is the amount of requested data when executing a request to a Fi file from node Kj;
Yv is the volume of the correction message to the file Fi from the node Kj;
λv is the intensity of requests to the Fi file initiated at the node Kj;
λ`v is the intensity of the corrective messages to the file Fi from the node Kj;
bj - the amount of memory node Kj, designed to accommodate files;
Vj is the number of copies of the i-th file (Vj is the given value i <= Vji <= n);
Хv (I = I, m¸ j = I, n) - values determined by the formula.
{I, if a copy of the file Fi, is located in the node Kj;}
Хv {О¸ otherwise}
The intensity λi generates the amount of data
Vi = ΣAλ`v UVXi
5 - i
5 - j
needing transfer. If we put
nk
λ` = ΣΣAV
i = jj = i
then the average amount of data necessary for forwarding when processing the correction message in the system is equal.
nkх
V` =IΣΣΣλ`v УvХI
λ` i= j j= i 5 — i
5 – j
Интенсивность λ`v порождает объем данных λ`v (av+β) (I-Хv) нуждающихся в пересылке. Поэтому средний объем данных, необходимых при пересылке при выполнении запроса в системе равен
n k
V`= IΣΣλ`v (av+β) (I-Х v)
λ` i= jj= i
n k
гдеλ=Σ Σλ`v
i= j j= i
Таким образом, математическая модель задачи оптимального распределения копий файлов по узлам вычислительной сети для критерия оптимальности средней объем пересылаемых данных по линиям связи при обработке запросного и корректирующего сообщения будет следующей: требуется найти минимум линейной функции
L,= V+V'
при ограничениях
n
Σ xv=yi(i=I,m)
i = j
n
ΣL, xv ≤ bi (i = I, n)
i = j
Хv = (o ﮞ I) I'I, m, j = I, n)
To improve the performance of the system, restrictions can be used as an additional condition the expected time to complete the request from each node. Indeed, let aifz be the expected time required to execute the request initiated at the Kj node to the Fj file that is contained in the Kj node, Tif be the maximum allowable time to complete the request to the Fj file initiated at the Kj node. Then, between the values aifz and Тv, the relations
av5 (I-Хv) Х15 ≤ Тv hold
for j <> S, I <> i <> m.
In order to obtain restrictions from this relation, the values of aifz should be expressed in terms of the variables Xv. In the general case of network topology, this is very difficult to do. And only if you do not use a number of assumptions imposed on the characteristics of the network, you can find simple expressions of knowledge aifz through Хv.
The disadvantages of the developed models can be attributed to the fact that they contain a number of limitations and simplifications, do not reflect such a feature of the RDB as a fragment. The disadvantages of the developed models can be attributed to the fact that they contain a number of limitations and simplifications, do not reflect such a feature of the RDB as fragmentation, and also that they are static and do not take into account the dynamics of the processes occurring in the system.
As for the methods used to optimize the RDB — the branch and bound method, mathematical programming — they gave positive results, since for real folded computer information systems with DBD, the dimensionality of the problem is large, which requires considerable time and computational resources. Therefore, for this task, it is advisable to use genetic algorithms that implement directed random search based on the mechanisms of natural evolution.
Thus, despite the previous studies, the issues of modeling and optimization of computer information systems DBDs have not received a final solution, the models and methods used have a number of drawbacks, which necessitated their further improvement.
An equally important issue is the provision of the most accurate source data. The implementation of any mathematical model. The optimal placement of RBD files on the nodes of a computer network requires a number of information arrays of source data, a significant part of which can only be obtained in an average or reduced form. These are such characteristics as request intensities, time for sending and processing requests, volumes of requests and responses to requests. The accuracy of the collected static information will decisively affect the final result of the implementation of the selected mathematical model and, consequently, the performance of the system working with the RDB.
To obtain reliable numerical data, it is necessary to determine the cyclical nature of the information in the system. This period can vary between applications from one day to a quarter. In the further processing of the collected information, it is necessary to take into account as average bursts of activity. The numerical characteristics of processing time, volume, shipments and handling probabilities must be calculated with allowance for peak situations in order to protect the system from significant delays during the most intensive downloads.
In addition to the listed characteristics, in the process of working with the optimized database, it is necessary to accumulate information about the type of request (reading, searching, updating) the name of the file to which the request was issued, the number of the node from which the request was issued, and the time of the real response.
A knowledge base is a set of knowledge units that represent the formation, using some method of representing knowledge, the reflection of objects in a problem area and their relationships, actions on objects and, possibly, the uncertainties with which these actions are carried out.
As methods for representing knowledge, most often either rules or objects (frames), or a combination of them, are used. So, the rules are constructions.
If <condition> Then <conclusion> CF (certainty factor) <value>.
As determinants of certainty (CF), as a rule, one encounters either the conditional probabilities of the Bayesian approach (from 0 to 1) or the confidence coefficients of the odd logic (from 0 to 100). Examples of rules are as follows.
Rule 1. If Profitability Ratio>
Then Profitability = “Satisfied” CF 100.
Rule 2. If Debt = “no” and Profitability = “Satisfied”.
That is Enterprise Reliability = “Satisfied” CF 90.
At any given time in the system, there are types of knowledge:
Structured knowledge - statistical knowledge about the subject area. Once knowledge is identified, it no longer changes.
Structured dynamic knowledge - changeable knowledge of the subject area, they are updated as new information is discovered.
The quality of ES is determined by the size and quality of the knowledge base (rules or heuristics). The system operates in the following cyclic mode: selection (query) of the data or results of observation analyzes, interpretation of the results, assimilation of new information, advancing temporal hypotheses using the rules, and then selecting the next portion of data and analysis results. This process continues until there is enough information for a final conclusion.
Thus, an artificial intelligence system built on the basis of high-quality specialized knowledge about a certain subject area (obtained from experts - specialists in this field) is called an expert system. Expert systems - one of the few types of artificial intelligence systems - have become widespread and have found practical application.
Expert systems differ from other programs in the following ways:
1. Competence - in a specific subject area, the expert system must reach the same level as human experts, while it must use the same heuristic techniques and also reflect the subject area deeply and widely;
2. Symbolic reasoning–The knowledge on which expert systems are based represent in a symbolic form the concepts of the real world, reasoning also occurs in the form of transformations of symbolic sets;
3. Depth - the examination should solve deep, non-trivial problems marked by complexity either in terms of the complexity of knowledge that the expert system uses or in terms of their abundance, this does not allow the use of exhaustive search of options as a method of solving problems and makes it resort to heuristic, creative, informal methods ;
4. Self-awareness - the expert system should include a mechanism for explaining how it comes to solving the problem.
Literature
1. Moiseev VB Representation of knowledge in intelligent systems. / Informatics and education, No. 2, 2003.
2. Petrov V.N. Information Systems - St. Petersburg: Peter, 2003.
3. Rastragin L.Kh. Experimental control systems. - M .: Nauka, 1974.
4. Saak A.E., Pakhomov E.V., Tyushnyakov V.N. Management Information Technology: Textbook for high schools. St. Petersburg: Peter, 2005.
5. Semenov M.I. and others. Automated information technology in the economy. Textbook. - M .: Finance and statistics, 2003.
6. Sovetov B.Ya. Modeling systems: Textbook for universities. - 3 - ed. reslave. and dock. - M.: Higher School, 2001.
7. Suvorova N. Information modeling: quantities, objects, algorithms. - M .: Laboratory of basic knowledge, 2002.
A small piece of my term paper on Expert Systems.