Formalization Streaming

Formalization: Stream Processing

Provides description of the implementation of the stream processing.

Stream Processing

To work with data streams approach based on their stream representation seems to be useful.

Data Stream

Data stream is understood a potentially infinite sequence of the same type of items (tokens) with a well-defined order.

Lets have the a set of all T tokens. Then the stream is defined as the function s:N → T. In the case of the XBUP protocol there are further restrictions applied on this function…

Data Stream With Limitations

In normal cases, you can find streams on which some form of sequential restrictions is applied. Stream is then a partial function f(S), which depends on the internal state, but usually can be expressed as a dependence on the value of the parameter functions. An example of a complete sequential restriction is the complete sequence, where f(S,S') returns the value when it is the direct successor of S', which means that it is not possible to move forward in then stream other way than just one step forward. Another option is to allow movement forward (skip), and also back.

Todo: Create more exact definition of the algorithms. Usual solution is to provide an interface for reading the next element, and possibly optional feature for the movement in the stream.

Aspects of the Stream Processing

It is possible to distinguish streams depending on the type of data stream items, the flow control type and amount of information transmitted in single step. In addition, different interfaces may be considered for the transfer of items (tokens). Various aspects leading to the possible implementation and hierarchy structures.

The draft of the protocol itself leads to the use of different types of tokens on the respective levels of the protocol. Also there is difference between whether the has stream-dependent or independent block types. Depending type is derived from the stream head and has a fixed type value, while the independent types are defined using an object, and before the transfer of data it is necessary to generate an encapsulation data header.

In addition to the item types it is possible to consider several other aspects of stream processing:

• Data passing methodology - How are items of data stream transmitted to the individual applications
• Data flow control - How is managed mutual exchange of data on the communication channel
• The possibility of movement in the stream - Data stream can provide the possibility of changing positions in the processed stream