This study describes the network design solution to the problem of connecting heterogeneous computer systems based on analysis of multipartite hypergraphs. To do this proposes a mathematical model of reliability for the two modes of operation of the system: with redundancy communication subsystem and the division of communication load. As the evaluation criteria applied solutions expected changes in processing capacity, latency communication and system reliability. Solution design task is sought in the collection Pareto optima, which describes a method for selecting a particular solution in case of equivalence with respect to the vector of the objective function.
Another important feature of modern processing systems is the variety of offered services. Nowadays, in the same network they are different, often incompatible with communication services (eg. Isochronous and synchronous transfer). This issue requires a change of quality of provided services, through the dynamic allocation of independent communication channels to users or services present in the network specifically in particular, this applies to multimedia services rendered in real-time or services comprising critical infrastructure. Modern distributed systems are also characterized by high dynamics of changes in operating parameters. Load elements of computing and communications is changing rapidly, which prevents the design and execution of the network to meet even medium-term requirements of the users. Another disadvantage occurring in communication subsystems ubiquity of traffic is bursty traffic, obstructing, and sometimes preventing proper functioning of the network. Currently, the solution to the above problems is the use of load leveling, both communications and computing. Moreover, an effective solution to most of these problems can be also providing a flexible reconfiguration of connections, preferably at the logical level, without having to modify the hardware architecture. In this way, links can be dynamically adapted to the current traffic pattern.
Effective methods of reconfiguring connections should be seen in the use of modern communication technologies, especially those that allow to realize it at the logical level and which additionally improve the utilization of physical communication channels. An interesting issue is the construction of multi-channel network of bus-sharing bus logic dynamic range conversion of a set of buses to which the user is attached. Because of that it becomes possible to adapt to the existing network architecture in the traffic patterns. However, the use of such architecture requires solving a specific design task, which for obvious reasons should be characterized by an acceptable time complexity and memory. Because of the combinatorial nature of the task it is difficult to meet.
These issue may include the design task to build large class of system configuration
tasks. This task is mostly decomposed into three basic subtasks: a. The selection of
system components; b. their deployment; c. determining the connection between them. In
previous work, component selection subtask is solved inter alia by implemented using
for this purpose methods seeking the shortest path [
The Fig. 1 shows a distributed system consisting of KN node calculation - decoration, each of which has a Kl retunes elements of the transceiver and the KB communication buses. Buses Bi (i = 1, . . . , KB) are logical and can be implemented on the basis of methods of reproduction of wave-go in one physical bus DF . The addition of logical channels to any node Ni physical bus BF is done by using a physical connection channels l and distributors of bus channels C.
Interconnect architecture of the analyzed system can be dynamically reconfigured by tunable elements transmitter - receiver. If you change the traffic pattern elements of the transmitter - receiver extent of the wave changes, and indeed attach themselves to another logical bus. The system can operate in two modes: a. redundancy communication subsystem; b. the communication load sharing. To evaluate the operating characteristics of the system in one of these modes, the probabilistic model suggested combinatorial, and in particular evaluating the reliability R. In this model, the kit: the transceiver - receiving (≈), the physical connection cable (l), and a manifold physical channel (C) are treated as a single device connection. Let pio - the probability of performance transceiver - the receiving node computational pl - probability of physical fitness connecting channel; pc - the probability of the distributor channel efficiency Trunk, the pfk - probability of physical fitness BUS channel. Then, the probability of pku efficiency of connecting the node to the logical channel BUS is defined as: pku = pioplpc and puku probability of the merger selected node with other nodes calculation is equal to puku = pioplpcpfk.
Trunk consider the reliability of a distributed system with connections complete (each compute node is connected to each bus logic) and equal rights computational nodes, which is the most general example of this class of systems. The probability pwe (kwe) efficiency connection sets providing connection to the bus channel not less than kwmein compute nodes with their total number KN determined by the expression: KN
X i=kwmein pwe (kwe) = pfk
(1)
Let KB to be the amount of bus logic (ie. The maximum multiplicity system interface), pswpe - likely performance computing node. Then, using expression (1), according to the proposed condition for the system in redundancy, reliability R is defined by the following formula:
R =
KN
X j=kwmein
KB
j
k=1
Consider the current system of equal rights computational nodes working in load sharing mode of communication. Let W (kwe, km, σ) to be the amount of system efficiency states consisting of kwe compute nodes, connected with km canals system, which can be selected with the existence of σ denials transceiver components. In order to determine the amount of W (kwe, km, σ) state performance of the system in the event of damage, etc., it is proposed to use the methods of include - exemption. H1 (σ) number of states malfunction of the entire system in case of refusal not less than one minimum section for a system with equal rights nodes is equal to:
H1 (σ) = KN C(σK−NK−B1)KB + CK2N C(σK−NK−B1)KB PαK=B1−1 CKαB =
C(σK−NKeB−1)KB KN + CK2N PαK=B1−1 CKαB (3)
Then, the value of W is equal to W (kwe, km, σ) = Ckσwekm + Piiσ=1 (−1)i Hi (σ), where: Ckσwekm - total number of states σ denials system for transmitting elements receiving; iσ - the maximum number taken into account when assessing the minimum cross sections; Hi (σ) - the number of states of a computing system failure, refusal to transmit elements - receiving no less than the minimum i sections. The probability Pku (kwe, km, σ), kwu ensures consistency nodes by km bus for refusals σ is defined by the expression:
Pku (kwe, km, σ) = W (kwe, km, σ) pkkwuekm−σ (1 − pku)σ
Using the expression (4), the likelihood of Pku (kwe, km) ensures the consistency of computing nodes kwe, km buses, with denials of the existence of σ can be written as: (kwe−1)km
X σ=0 Pku (kwe, km) =
Pku (kwe, km, σ) Puku (kwe) = PlK=Bkmmin CKlB plfk (1 − pfk)KB−l Pku (kwe, l),
Using the expression (5), it will determine the likelihood of consistency Puku (kwe), kwe compute nodes: where: kmmin - the minimum required number of buses needed to provide the required bandwidth. In this way, the reliability of calculation system is equal to: R =
KN
X n=kwmein
CKnN (pswpe)n (1 − pswpe)KN −n Puku (n) (4) (5) (6) (7) (8)
For computing system client-server mode redundancy it will determine the likelihood of Pks (KK , KS ) efficiency BUS communication channel to which, through the operational elements transmitter - receiver including no less than kmin customers with k their total number of KK and ksmin servers with the total number of KS : Pks (KK , KS ) = pfk
KK KS
P P i=kkmin j=ksmin
Let pskpand pssp be the likelihood of efficiency for clients and servers nodes, respectively. Then, using the expression (7), reliability Rcan be written as: R =
KK
P m=kkmin KS
P n=ksmin
Km P CKlm (Pks (KK , KS ))l (1 − Pks (KK , KS ))Km−l .
l=1
Let’s consider the reliability of client-server system with a complete blend of computing and communication subsystem working in load sharing mode. Let W (ks, kk, km, σ)to be the number of states efficient system consisting of servers ks, kkclients, kmbus, in the presence of σ denials transceiver components. For the clientserver system, the number of failure conditions the H1 (σ) no less than a minimum cross section can be determined using the expression: a number of states proper functioning as: (9) (10) (12) (13) (14)
W (kk, ks, km, σ) = Ckσm(kk+ks) + Piiσ=1 (−1)i Hi (σ) ,
Where: Ckσm(kk+ks)- the total number of computing system states that may occur at σ refusals. The probability Pks (ks, kk, km, σ) ensures consistency ks servers and kk clients using km bus in case of refusal elements σtransmitter - receiver can be written as:
Pku (ks, kk, km, σ) = W (ks, kk, km, σ) p(kkus+kk)km−σ (1 − pku)σ . (11)
The probability of Pku (ks, kk, km) servers to ensure coherence ks and kk clients using km bus in the event of a refusal elements transmitter - receiver has been defined as:
Pku (ks, kk, km) = P(sk=s0+kk)km Pku (ks, kk, km, σ) , and the probability Pku (ks, km) of consistency ks servers and kk clients as:
Pku (ks, kk) = PkKmm=1 CKkm pfkmk (1 − pfk)Km−km Pku (ks, kk, km) . Using the expression (11), (12), and (13) the sought reliability R will be written as:
R = PkK=kkkmin CKkk (pskp)k (1 − pskp)Kk−k ·
PsK=sksmin CKss (pssp)s (1 − pssp)Ks−s Pku (s, k)
The above-described methodology we will use for further connections to network design measuring system. 3
We will consider hypergraph H = (V, E) comprising a set V = {v} of vertices and a set of E = {e} of edges, which represent a subset of the set V, i.e. e ⊆ V . Hypergraph H is a k-regular if each of its edge e ∈ E consists of k vertices. On the other hand, hypergraph H is l-partite graph, if the set of its vertices is divided into l subsetsV1, V2, . . . , Vl, in such a manner that the vertices of each of the edges e = (v1, v2, . . . , vl) ∈ E belong to different parts of the graph, ie. vi ∈ Vi, where i = 1, . . . , l. For the determination of l- partite hypergraphs we will use record form H = (V1, V2, . . . , Vl).
Let’s consider the l- partite hypergraph H = (V1, V2, . . . , Vl). In this graph, the part a = V1A, . . . , ViA, . . . , VlA, EA , for i = 1, . . . , l and VlA ⊆ Vl, where any two edges e1, e2 ∈ EA overlap in one and the same vertex v ∈ V1A and do not overlap at any vertex v ∈ V A l , will be called star. This means that the cardinality of V1Ais 1, and the vertex v ∈ V1A, will be called the center of the star. We distinguish the simple and complex stars. If any pair of edges e1, e2 ∈ EA covers only in one vertex v ∈ V A 1 , then the star is called simple. Otherwise, a star will be called complex. The number of edges of the star will be called degree. For the edge e = (v1, v2, . . . , vl) ∈ E of the star verticesv1and vlwe will call end. In turn, the vertices v2, . . . , vl−1 will be determined as internal. Vertices set of the part of graph V2, . . . , Vl−1 are composed of empty pairs of disjoint sets Vi (vj ), vj ∈ Vj , where: i = 2, . . . , l − 1, j = i + 1.
For hypergraph H = (V, E) its subhypergraph H1 = (W, U ) we’ll be called hypergraph for which set of the vertices W is the vertices subset V of hypergraph H, ie. W ⊆ V and the edge set U is the edges subset E of the hypergraph H, wherein if the (x, y) ∈ E and x, y ∈ W , then (x, y) ∈ U . Hypergraph cohesion component will be called the set of its vertices, such as any of two of its elements there is a path between them, but there is no path leading from the vertex of belonging to this collection to any other vertex outside. If there is in the subhypergraph H1 = (V1, E1) of hypergraph H consistency of each component there is a star with center at some vertex v ∈ V1, the H1we will call the coverage of hypergraph H stars.
Fixed design task was to find such a connection structure that will ensure the maximization or minimization of operating parameters, such as communication delay, errors in access to the communication medium as a result of his occupation, performance computational processing nodes and others. Such a task can be solved by seeking the cover at least the stars of trigeminal graph. Let’s consider the task.
Input data. As an input data we use the design task:
1. B = {b} - A set of logical communication bus dedicated by physical channel under
communication using any of the methods of reproduction communication;
2. F = {f } - A set of access protocols, which describes the functioning logical BUS
communication [
Customers are divided into groups d ∈ D taking their communication requirements into account, where D = {d} - is a set of types of communication requirements. Elements of the set D shall be as follows: d = 0 – service streams sensitive to errors and latency; d = 1 – support for latency-sensitive flows; d = 2 – service streams are sensitive to transmission errors; d = 3 – handling sensitive streams not being sensitive to these factors.
The definition of design task. Each of the compute nodes n ∈ N should be assigned a set of M bus b, which is a subset of B, ie. M ⊆ B, each of which will operate on the basis of one of the access protocols f ∈ F .
The mathematical model. The task design is iteratively solved. In each of the steps and for each of the compute nodes there is sought one bus b ∈ B providing for node communication services using Access Protocol f ∈ F . To avoid multiple of includes a node on the same bus at each successive step from the available buses the client is excluded from those for whom it has already been connected.
The mathematical model is based on the 3-partite hypergraph H = (V, E) = (X, Y, Z, E). Busses from the set B = {b} correspond to the vertices of the first part x (x ∈ X). Each of them (at the same time each logical bus) is assigned to the label η (x) determining the transmission characteristics of the bus, in the simplest case, the number of nodes measured, that it can handle.
The f elements of the set F bus access protocols correspond to the vertices y of the second part of hypergraph H (y ∈ Y ), and the elements n from N compute nodes correspond to the vertices zof the third part of hypergraph (z ∈ Z).The set of edges E = {e} includes all three vertices (x, y, z)such that x ∈ X_, y ∈ Y , z ∈ Z. There are permitted only those edges, for which a selected bus the client can handle bi ∈ X using a communication protocol fl ∈ Y2. Collection E = {e} of all edges is determined essentially by a set of all admissible triples e = (x, y, z). Taking account of the value of the parameter n (x) for x ∈ Xin hypergraph H = (V, E) = (X, Y, Z, E) permissible step design task solution will be any of his sub hypergraph β = (Vβ , Eβ ) forVβ ⊆ V and Eβ ⊆ Eof which each component represents the simple consistency star of stage with the center in the apex x ∈ X. As S = S (H) = {s}we denote the set of all feasible solutions of tasks covering hypergraph H stars.
Each of edges e ∈ E of hypergraph H = (V, E) there is assigned three scales
describing the following characteristics solutions:
1. ω (e) = φ (x, y, z) - Expected customer conversion processing performance in a
system in which the client is supported in communication with the bus X, which
uses a communication protocol y. To evaluate the performance characteristics of
the proposed process there were used in [
Solution design task. The rating of the solutions will be shown as a multi-criteria. The proposed set of criteria is obviously exemplary, and his selection depends on the needs of the designer, in particular concerning the nature of the future operation of the network merger. For the case of under consideration there are the three functions described below.
Let’s consider the set A = {a} of acceptable solutions of design task. For each of them we define the following characteristics assessing the quality of solutions: 1. Criterion performance computing: Φ1 (a) = max min ω (e), where: Ea– sub of a∈A e∈Ea edge of hypergraph H belonging to solution a. Using this criterion, we strive to maximize the minimum level of performance (computing or communication) system. 2. Communication delay criterion: Φ2 (a) = min Pe∈Ea ξ (e), which provides network search junction with minimal delay summary. For systems with varying levels of validity of nodes, the value ξ (e) of expected changes in the communication delay is called using vertex priority. 3. The criterion of reliability: Φ3 (a) = max Pe∈Ea ψ (e). This criterion provides a network architecture search for which the total reliability is maximum likewise in the case of a delay criterion communication Φ2.
The possibilities of the above method is not limited to the application of the summation as a min or max. To assess the quality of solutions it can be used any of the method of folding (convolution) parameters, including methods taking the weight of each sub-parameters into account. These sub-criteria are related by a function to form Φ (a) = (Φ1 (a) , Φ2 (a) , Φ3 (a)). Multi-criteria objective function Φ (a)defines a set A feasible solutions, a set of Pareto Apcomposed of Pareto optima ap. If two solutions a1, a2 ∈ A vector objective function Φ (a) are equivalent, then the set of Ap is secreted full set of alternatives AA, which is, in fact, a maximum system vectorially different optima Pareto. 4
The work approach used to create a multi-channel design methodology destined for fieldbus communication service systems, client-server computing. The existing methodology is focused on providing definite level of computing capacity of the entire system, regardless of its reliability parameters. In the presented in the work version, methodology seeks the optimal solution with respect to multi-criteria objective function that one of the criteria is reliability. Depending on how sub-criteria ties and a set of restrictions proposed methodology also allows you to specify the connection architecture, characterized by: a. maximum reliability with certain: the minimum efficiency and maximum delay network communication links; b. the minimum communication delay with the reduction in the minimum reliability and performance; c. maximum computing performance of a specified acceptable level of reliability and delays. There was also tested solution, the aim of which was to design load leveling various communication buses. For each of the solutions sought there are limited the maximum cost of construction. We analyzed the network of connections complete and partial, flat and hierarchical.
Simulation studies of obtained architectures for computing model client-server
based on the methodology presented in [
Further research will focus on finding effective methods of searching for coverage of celebrities simple multipartite hypergraph, which will allow the use of graphs in the design process of any of valor, and this will introduce further design criteria.