WO2016062632A1

WO2016062632A1 - A method for designing a minimal aggregation topology for scalable computing

Info

Publication number: WO2016062632A1
Application number: PCT/EP2015/074014
Authority: WO
Inventors: Erwan Le Merrer; Bao-Duy TRAN
Original assignee: Thomson Licensing SAS
Current assignee: Thomson Licensing SAS
Priority date: 2014-10-22
Filing date: 2015-10-16
Publication date: 2016-04-28
Anticipated expiration: 2017-04-22

Abstract

An aggregation topology comprises L layers, each layer having at least one node and wherein the last layer has only one node and wherein no data is lost by the aggregation topology and the number of layers, L, minimizes latency in the aggregation topology.

Description

A METHOD FOR DESIGNING A MINIMAL AGGREGATION TOPOLOGY FOR

SCALABLE COMPUTING

BACKGROUND OF THE INVENTION

[0001] The present invention generally relates to a network of computers or processing units, such as, but not limited to cloud computing.

[0002] The rise of the Internet of Things and the general migration of IT (information technology) services to the cloud push for the adoption of practical low-latency processing solutions. Current applications include the monitoring of potentially thousands or millions of devices that stream information to a collection point in the background. A device analyzer may collect hundreds of thousands of data points per day per monitored device (e.g., see D. T. Wagner, A. Rice, and A. R. Beresford; "Device analyzer: Large-scale mobile data collection"; SIGMETRICS Perform. Eval. Rev., 41(4):53-56, Apr. 2014).

[0003] Real-time computation is made possible by the progress of stream processing platforms such as "Storm", and of algorithms requiring small space and update time (e.g., see O. Papapetrou, M. Garofalakis, and A. Deligiannakis; "Sketch-based querying of distributed sliding-window data streams"; Proc. VLDB Endow., 5(10):992_1003, June 2012). The support for stream aggregation operations is required for advanced analytics, since it allows for important and more advanced applications like identification of heavy hitters ( e.g., see G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava; " Finding hierarchical heavy hitters in data streams"; Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29, VLDB Ό3, pages 464_475; VLDB Endowment, 2003), or anomaly detection (e.g., see Q. Huang and P. P. Lee; "LD-Sketch: A distributed sketching design for accurate and scalable anomaly detection in network data streams"; INFOCOM, 2014).

[0004] There are of course technical challenges raised by this increasing amount of monitored resources. It is particularly well understood that no single computing unit can sustain millions of connections for aggregating device information. As a consequence, computing units (also referred to as processing units or nodes) are arranged in a network topology such as "aggregation topologies". In an aggregation topology, there are "L" layers, where each layer comprises a number of nodes. Devices stream data (packets) to the aggregation topology for processing. The first layer of the aggregation topology receives the data. Generally, the number of nodes in each layer decreases until, for the last layer, there is only one node that provides the output from the aggregation topology. As such, the information received is reduced layer by layer in a scalable fashion, until the desired result is obtained (e.g., see Q. Zhang, J. Liu, and W. Wang; "Approximate clustering on distributed data streams"; Data Engineering, 2008; ICDE 2008; IEEE 24^th International Conference on, pages 1131-1139, April 2008).

[0005] Currently, there is no systematic way to design an aggregation topology for a particular service (application), other than by using trial and error. One can for instance provision a tangibly high number of nodes, which will suffice for the service to run without losing device data. However, this may result in a high operational cost since there will likely be more nodes then required for the service. At the other extreme, if one designs an aggregation topology with too few nodes, then it is likely that the service will not be able to ingest the service load - resulting in packet loss.

SUMMARY OF THE INVENTION

[0006] Acknowledging the commercial or physical limits of processing nodes available for operation, there is thus a need for a systematic approach to design an aggregation topology on demand. This topology must be derived from the input characteristics (number of devices and their data sending rate) and on the operations to be achieved. Meanwhile, this topology should maintain the invariant that no node (also referred to as a shard) must be overwhelmed by received data from its neighbors in the topology. Trivially deriving the number of nodes from the raw traffic (divided by the rate limit) does not help, as it gives an indication on a minimal number of nodes to operate. It does not give information on the form of the topology, so nodes beyond the first layer can be overwhelmed too.

[0007] Therefore, and in accordance with the principles of the invention, an aggregation topology is designed such that no data is lost while employing the least number nodes in the least number of layers possible to reduce complexity and latency.

[0008] In an illustrative embodiment of the invention, an aggregation topology comprises L layers, each layer having at least one node and wherein the last layer has only one node and wherein no data is lost and the number of layers, L, minimizes latency.

[0009] In another illustrative embodiment of the invention, a computer executes a design tool to design an aggregation topology comprising L layers, each layer having more than one node and wherein the last layer has only one node and wherein no data is lost and the number of layers, L, minimizes latency. [0010] In view of the above, and as will be apparent from reading the detailed description, other embodiments and features are also possible and fall within the principles of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

[0011] FIG. 1 shows an illustrative aggregation topology in accordance with the principles of the invention;

[0012] FIG. 2 shows an illustrative flow chart for use in a computer for providing a design tool to design an aggregation topology in accordance with the principles of the invention; and

[0013] FIG. 3 shows an illustrative computer for use in executing the flow chart of FIG. 2.

DETAILED DESCRIPTION

[0014] Other than the inventive concept, the elements shown in the figures are well known and will not be described in detail. For example, other than the inventive concept, an aggregation topology, a processing unit (or node), and the components thereof, such as a transceiver (communications block), processor, etc., are well known and not described in detail herein. Further, other than the inventive concept, familiarity with the Internet and cloud computing is assumed and not described herein. It should also be noted that the inventive concept may be implemented using conventional programming techniques, e.g., APIs (application programming interfaces) which, as such, will not be described herein. Finally, like-numbers on the figures represent similar elements.

[0015] An illustrative aggregation topology 10 in accordance with the principles of the invention is shown in FIG. 1. As described further below, the number of layers, L, and the total number of nodes spread across the topology are selected such that no data is lost while employing the least number nodes in the least number of layers possible to reduce complexity and latency.

[0016] Aggregation topology 10 comprises a number of layers, L. The input data to the aggregation topology 10 is provided by a number of source nodes (denoted by the label "100") n₀ (where the subscript "0" indicates a source node) and n₀ > 1. It is assumed that each source node emits data (packets) according to a homogeneous Poisson process with the same mean emission rate ο (where, again, the subscript "0" indicates a source node). As illustrated in FIG. 1, each source node uniformly routes data to every node in layer 1 (denoted by the label "101"), i.e., with a probability ri_i' where n is the number of nodes in layer 1 and n₁ > I. Likewise, each node in layer 1 uniformly routes data to every node in layer 2 (denoted by the label "102'), i.e., with a probability /_n , where n₂ is the number of nodes in layer 2 and n₂≥ 1. This pattern continues for the remaining layers. Generally, the number of nodes in each layer decreases until, for the last layer, L (denoted by the label "105"), there is only one node (the sink node) that provides the output from the aggregation topology. However, it should be noted that it may be the case that adjacent layers (other than layer L) may have the same numbers of nodes. The number of all nodes in the aggregation topology 10 is N. Each node in Layers 1 through L, processes their incoming data according to the same given aggregator function and provides the resulting output data to Othe node(s) in the next layer. An example of aggregator functions are average, maximum value, minimum value, sum, count, etc. Further, every node in aggregation topology 10 imposes the same ingest rate constraint, Θ. The ingest rate constraint, Θ, is the number of items/second (e.g., packets/second, that can correspond to an information quantity per unit of time, as IMB/s) that can be processed by a node before data is rejected, and thus data loss starts to occur. Each node deals with the aggregation of non-overlapping time windows. Each time window can, e.g., be identified by a "KEY". Each node accepts and aggregates data corresponding to one time window at a time. If the "KEY" corresponding to the time windows changes, the aggregation result is sent to the next layer and a new aggregation begins. An illustrative process for use in a node is shown below:

- null; b <- agg(6);

each tuple (T, v)received do

if T_Q = null then

T₀ *- T; b <- agg ({ })

else if T ≠ T₀ then

emit tuple (T_Q, b);

T₀ ^ T; b <- agg{{v});

else

b <- accum_aqq (b, v); In terms of the variables shown in process (1), the following definitions are provided:

(T, v) is a key-value tuple, where T is a time period (often called

an epoch) used as the KEY and v is a payload value;

T₀ is the current time period in a node;

agg({v}) is an aggregator function used by a node on a received

payload, v;

b stores the accumulation of the aggregator function results in a

node;

accum_agg (b, v) accumulates the aggregator function results in b;

With the above definitions, process (1) operates in a node as follows. Initially, T₀ is set to a null value and b is set to a value of 0. For each data (tuple) received, if T₀ is equal to a null value, then T₀ is set to the value of the time period, T, in the received tuple (T, v) and b is set equal to the value of the aggregator function result . As long as the value of T₀ is equal to the value of the time period, T, in a received tuple (T, v), (in other words the time period hasn't changed) then b accumulates the aggregator function results via accur _agg b, v). However, once the time period changes, and T ≠ T₀ then the node emits a tuple to the next layer with the values of T₀ and b and then sets T₀ to the new value of T and a new value is stored in b to begin again to accumulate the aggregator function results for the new time period. Turning back to FIG.l, the last layer is the sink node 105. This is the last operational node and provides the overall aggregation result 111.

[0017] As noted earlier, there is no systematic way to design an aggregation topology for a particular service (application), other than by using trial and error. One can for instance provision a tangibly high number of nodes, which will suffice for the service to run without losing device data. However, this may result in a high operational cost since there will likely be more nodes then required for the service. At the other extreme, if one designs an aggregation topology with too few nodes, then it is likely that the service will not be able to ingest the service load - resulting in packet loss. It should also be noted that if packets are dropped later in the aggregation process rather than sooner in the aggregation process, there is a loss of more aggregation information.

[0018] Therefore, and in accordance with the principles of the invention, an aggregation topology is designed such that no data is lost while employing the least number nodes, N, in the least number of layers, L, to reduce complexity and latency. In particular, for a given number of source nodes, n₀, each having the same mean Poisson emission rate λο, and a known ingest rate constraint, Θ, for each node in the aggregation topology, the number of nodes can be determined for each layer, I, and the minimum number of layers, L, can be determined such that the resulting aggregation topology does not drop packets and reduces latency by iteratively executing equation (2), below:

<- 1 to + oo do

return L, n_x , n , ... n_L

In terms of the variables in equation (2) the following definitions are provided:

I represents the current layer, initially set to 1 ;

n₀ represents the number of source nodes;

ο represents the mean Poisson emission rate;

Θ represents the ingest rate constraint;

n_t represents the determined number of nodes for the

current layer, I; and

L represents the number of layers when it is determined that

a layer has only one node.

[0019] Equation (2) is iteratively performed as illustrated in the flow chart of FIG. 2. In step 205, the following data is input:

the number of source nodes, n₀ ;

the mean Poisson emission rate, ο; and

the ingest rate constraint, Θ .

In addition, the variable, I, representing the current layer is initially set to a value of one. In step 210, equation (2) is executed to determine the number of nodes, n in that layer, I. In step 215, a check is made to determine if there is only one node in that layer. If there is more than one node, then the value of I is incremented in step 225 and equation (2) is executed again in step 210 to determine the number of nodes for the next layer, etc. However, if, in step 215, there is only one node in a layer, then further execution of equation (2) stops and a value for the number of layers, L, is provided as well as values for the number of nodes in each layer. As a result, a systematic design approach is provided for designing an aggregation topology where there is no data loss and the number of layers is minimized to reduce latency.

[0020] Turning briefly to FIG. 3, an illustrative high level block diagram of a computer 500 for executing a design tool in accordance with the principles of the invention, as illustrated by the flow chart of FIG. 2, is shown. Only those portions relevant to the inventive concept are shown. As such, computer 500 can perform other functions. Computer 500 is a processor based system as represented by processor 505. The latter represents one, or more, stored-program controlled processors as known in the art. In other words, processor 505 executes programs stored in memory 510. The latter represents volatile and/or non-volatile memory, e.g., hard disk, CD-ROM, DVD, random access memory (RAM), etc.) for storing program instructions and data, e.g., for performing the illustrative flow chart shown in FIG. 2 for providing aggregation topology design. Computer 540 also has communications block 130, which supports communications of data over a data connection 541 as known in the art. Data communications can be wired, or wireless, utilizing 802.11, 3G LTE, 4G LTE, etc. Finally, mobile device 505 includes a display and keyboard 530 for providing information to a user, e.g., the output data from step 220 and receiving information from a user e.g., the input data in step 205.

[0021] Other approaches in accordance with the principles of the invention for determining an aggregation topology as a function of a given number of source nodes, n₀, each having the same mean Poisson emission rate λο, and a known ingest rate constraint, Θ, for nodes in the aggregation topology can also be used. For example, a process can be used that utilizes mixed-integer non-linear programming (MINLP) and employs off-the-shelf MINLP solvers like "SCIP" (Solving Constraint Integer Programs) or "MIDACO (Mixed Integer Distributed Ant Colony Optimization) Solver". One such approach is shown in FIG. 4. As shown in FIG. 4, the inputs are at least a given number of source nodes, n₀, each having the same mean Poisson emission rate λο, and a known ingest rate constraint, Θ, for nodes in the aggregation topology. This approach caps, or limits, the value for the number of layers, L, to 1 < L < L_max. As such, L_max, is now also an input as shown in FIG. 4. The variable m_z is a binary mask such that for 1 < I < L, the value of m_z is one and for L + 1 < I≤ L_max the value of m_z is zero. As shown in FIG. 4, the output is the number of layers, L, and the number of nodes in each layer. Other than the inventive concept, the remainder of FIG. 4 is the problem statement for input to, e.g., either the "SCIP" or "MIDACO" MINLP solvers as known in the art.

[0022] In view of the above, the foregoing merely illustrates the principles of the invention and it will thus be appreciated that those skilled in the art will be able to devise numerous alternative arrangements which, although not explicitly described herein, embody the principles of the invention and are within its spirit and scope. It is therefore to be understood that numerous modifications may be made to the illustrative embodiments and that other arrangements may be devised without departing from the spirit and scope of the present invention.

Claims

1. A method for use in determining an aggregation topology, the method comprising: receiving data representing a number of source nodes, a mean Poisson emission rate and an ingest rate constraint;

determining from the received data a number of nodes for a layer of the aggregation topology;

wherein if the number of nodes for the layer is greater than one, repeating the determining step for the next layer and if the number of nodes for the layer is equal to one, providing the number of layers for the aggregation topology and the number of nodes in each of the layers of the aggregation topology.

2. The method of claim 1, wherein the number of nodes in each layer of the aggregation topology results in no data loss and the number of layers for the aggregation topology minimizes latency for the aggregation topology.

3. The method of claim 1, wherein the determining step executes the following equation:

wherein I represents the current layer, initially set to 1 ;

n₀ represents the number of source nodes;

ο represents the mean Poisson emission rate;

Θ represents the ingest rate constraint; and

Ui represents the determined number of nodes for the current

layer, I .

4. The method of claim 1, wherein the determining step uses a mixed- integer nonlinear program solver.

5. An aggregation topology comprising:

a first layer comprising a plurality of nodes for receiving data from a number of source nodes having the same mean Poisson emission rate;

a plurality of other layers, each layer having a plurality of nodes for receiving aggregated data from a previous layer; and

a last layer having only one node for receiving aggregated data from a previous layer and providing an aggregation result;

wherein the number of all layers in the aggregation topology is L; and

wherein the number of nodes in the aggregation topology across all L layers is N, and each node has the same ingest rate constraint, and each node performs the same aggregator function for providing the aggregation result;

wherein the number of layers, L, and the number of nodes in each layer are selected as a function of the number of source nodes, the mean Poisson emission rate and the ingest rate constraint.

6. The aggregation topology of claim 5, wherein the number of nodes in each layer of the aggregation topology results in no data loss and the number of layers for the aggregation topology minimizes latency for the aggregation topology.

7. The aggregation topology of claim 5, wherein the aggregator function is at least one of average, maximum value, minimum value, sum, and count functions.

8. The aggregation topology of claim 5, wherein the function is:

wherein I represents the current layer, initially set to 1 ;

n₀ represents the number of source nodes;

ο represents the mean Poisson emission rate;

Θ represents the ingest rate constraint; and

Ui represents the determined number of nodes for the current

layer, I .

9. A computer for use in determining an aggregation topology, the computer comprising:

a memory for storing a program and data representing a number of source nodes, a mean Poisson emission rate and an ingest rate constraint; and

a processor for executing the stored program, wherein the processor determines from the stored data a number of nodes for a layer of the aggregation topology; and wherein if the number of nodes for the layer is greater than one, repeats the determining step for the next layer and if the number of nodes for the layer is equal to one, provides the number of layers for the aggregation topology and the number of nodes in each of the layers of the aggregation topology.

10. The computer of claim 9, wherein the number of nodes in each layer of the aggregation topology results in no data loss and the number of layers for the aggregation topology minimizes latency for the aggregation topology.

11. The computer of claim 9, wherein the stored program includes instructions to evaluate the following equation:

wherein I represents the current layer, initially set to 1 ;

n₀ represents the number of source nodes;

ο represents the mean Poisson emission rate;

Θ represents the ingest rate constraint; and

Ui represents the determined number of nodes for the current

layer, I .

12. The computer of claim 9, wherein the stored program uses a mixed-integer nonlinear program solver.