Processing of UDP events

[lttv.git] / lttv / lttv / sync / README

Benjamin Poirier
benjamin.poirier@polymtl.ca
2009

+ About time synchronization
This framework performs offline time synchronization. This means that the
synchronization is done after tracing is over. It is not the same as online
synchronization like what is done by NTP. Nor is it directly influenced by it.

Event timestamps are adjusted according to a clock correction function that
palliates for initial offset and rate offset (ie. clocks that don't start out
at the same value and clocks that don't run at the same speed). It can work on
two or more traces.

The synchronization is based on relations identified in network traffic
between nodes. So, for it to work, there must be traffic exchanged between the
nodes. At the moment, this must be TCP traffic. Any kind will do (ssh, http,
...)

For scientific information about the algorithms used, see:
* Duda, A., Harrus, G., Haddad, Y., and Bernard, G.: Estimating global time in
distributed systems, Proc. 7th Int. Conf. on Distributed Computing Systems,
Berlin, volume 18, 1987
* Ashton, P.: Algorithms for Off-line Clock Synchronisation, University of
Canterbury, December 1995
http://www.cosc.canterbury.ac.nz/research/reports/TechReps/1995/tr_9512.pdf

+ Using time synchronization
++ Recording traces
To use time synchronization you have to record traces on multiple nodes
simultaneously with lttng (the tracer). While recording the traces, you have
to make sure the following markers are enabled:
* dev_receive
* dev_xmit_extended
* tcpv4_rcv_extended
* udpv4_rcv_extended
You also have to make sure there is some TCP traffic between the traced nodes.

++ Viewing traces
Afterwards, you have to make sure all the traces are accessible from a single
machine, where lttv (the viewer) is run.

Time synchronization is enabled and controlled via the following lttv options,
as seen with "-h":
--sync
                     synchronize the time between the traces
--sync-stats
                     print statistics about the time synchronization
--sync-null
					 read the events but do not perform any processing, this
					 is mostly for performance evaluation
--sync-analysis  -  argument: chull, linreg
                     specify the algorithm to use for event analysis
--sync-graphs
                     output gnuplot graph showing synchronization points
--sync-graphs-dir  -  argument: DIRECTORY
                     specify the directory where to store the graphs, by
					 default in "graphs-<lttv-pid>"

To enable synchronization, start lttv with the "--sync" option. It can be
used in text mode or in GUI mode. You can add the traces one by one in the GUI
but this will recompute the synchronization after every trace that is added.
Instead, you can save some time by specifying all your traces on the command
line (using -t).

Example:
lttv-gui -t traces/node1 -t traces/node2 --sync

++ Statistics
The --sync-stats option is useful to make sure the synchronization algorithms
worked. Here is an example output (with added comments) from a successful
chull (one of the synchronization algorithms) run of two traces:
	LTTV processing stats:
		received frames: 452
		received frames that are IP: 452
		received and processed packets that are TCP: 268
		sent packets that are TCP: 275
	TCP matching stats:
		total input and output events matched together to form a packet: 240
		Message traffic:
			  0 - 1  : sent 60         received 60
# Note that 60 + 60 < 240, this is because there was loopback traffic, which is
# discarded.
	Convex hull analysis stats:
		out of order packets dropped from analysis: 0
		Number of points in convex hulls:
			  0 - 1  : lower half-hull 7     upper half-hull 9
		Individual synchronization factors:
			  0 - 1  : Middle     a0= -1.33641e+08 a1= 1 - 4.5276e-08 accuracy 1.35355e-05
								  a0: -1.34095e+08 to -1.33187e+08 (delta=  907388)
								  a1: 1 -6.81298e-06 to +6.72248e-06 (delta= 1.35355e-05)
	Resulting synchronization factors:
		trace 0 drift= 1 offset= 0 (0.000000) start time= 18.799023588
		trace 1 drift= 1 offset= 1.33641e+08 (0.066818) start time= 19.090688494
	Synchronization time:
		real time: 0.113308
		user time: 0.112007
		system time: 0.000000

++ Algorithms
The synchronization framework is extensible and already includes two
algorithms: chull and linreg. You can choose which analysis algorithm to use
with the --sync-analysis option.

+ Design
This part describes the design of the synchronization framework. This is to
help programmers interested in:
* adding new synchronization algorithms (analysis part)
	There are already two analysis algorithms available: chull and linreg
* using new types of events (processing and matching parts)
* using time synchronization with another data source/tracer (processing part)
	There are already two data sources available: lttng and unittest

++ Sync chain
This part is specific to the framework in use: the program doing
synchronization, the executable linking to the event_*.o
eg. LTTV, unittest

This reads parameters, creates SyncState and calls the processing init
function. The "sync chain" is the set of event-* modules. At the moment there
is only one module at each stage. However, as more module are added, it will
become relevant to have many modules at the same stage simultaneously. This
will require some modifications. I've kept this possibility at the back of my
mind while designing.

++ Stage 1: Event processing
Specific to the tracing data source.
eg. LTTng, LTT userspace, libpcap

Read the events from the trace and stuff them in an appropriate Event object.

++ Communication between stages 1 and 2: events
Communication is done via objects specialized from Event. At the moment, all
*Event are in data_structures.h. Specific event structures and functions could
be in separate files. This way, adding a new set of modules would require
shipping extra data_structures* files instead of modifying the existing one.
For this to work, Event.type couldn't be an enum, it could be an int and use
#defines or constants defined in the specialized data_structures* files.
Event.event could be a void*.

++ Stage 2: Event matching
This stage and its modules are specific to the type of event. Event processing
feeds the events one at a time but event analysis works on groups of events.
Event matching is responsible for forming these groups. Generally speaking,
these can have different types of relation ("one to one", "one to many", or a
mix) and it will influence the overall behavior of the module.
eg. TCP, UDP, MPI

matchEvent() takes an Event pointer. An actual matching module doesn't have to
be able to process every type of event. It will only be passed events of a
type it can process (according to the .canMatch field of its MatchingModule
struct).

++ Communication between stages 2 and 3: event groups
Communication consists of events grouped in Message, Exchange or Broadcast
structs.

About exchanges:
If one event pair is a packet (more generally, something representable as a
Message), an exchange is composed of at least two packets, one in each
direction. There should be a non-negative minimum "round trip time" (RTT)
between the first and last event of the exchange. This RTT should be as small
as possible so these packets should be closely related in time like a data
packet and an acknowledgement packet. If the events analyzed are such that the
minimum RTT can be zero, there's nothing gained in analyzing exchanges beyond
what can already be figured out by analyzing packets.

An exchange can also consist of more than two packets, in case one packet
single handedly acknowledges many data packets. In this case, it is best to
use the last acknowledged packet. Assuming a linear clock, an acknowledged
packet is as good as any other. However, since the linear clock assumption is
further from reality as the interval grows longer, it is best to keep the
interval between the two packets as short as possible.

++ Stage 3: Event analysis
This stage and its modules are specific to the algorithm that analyzes events
to deduce synchronization factors.
eg. convex hull, linear regression, broadcast Maximum Likelihood Estimator

Instead of having one analyzeEvents() function that can receive any sort of
grouping of events, there are three prototypes: analyzeMessage(),
analyzeExchange() and analyzeBroadcast(). A module implements only the
relevant one(s) and sets the other function pointers to NULL in its
AnalysisModule struct.

The approach is different from matchEvent() where there is one point of entry
no mather the type of event. The analyze*() approach has the advantage that
there is no casting or type detection to do. It is also possible to deduce
from the functions pointers which groupings of events a module can analyze.
However, it means each analysis module will have to be modified if there is
ever a new type of event grouping.

I chose this approach because:
1) I thought it likely that there will be new types of events but not so
   likely that there will be new types of event groups.
2) all events share some members (time, traceNb, ...) but not event groups
3) we'll see which one of the two approaches works best and we can adapt
   later.

++ Data flow
Data from traces flows "down" from processing to matching to analysis. Factors
come back up.

++ Evolution and adaptation
It is possible to change/add another sync chain and to add other event_*
modules. It has been done. New types of events may need to be added to
data_structures.h. This is only to link between Event-* modules. If the data
does not have to be shared, data_structures.h does not have to be modified.

At the moment there is some code duplication in the last steps of linreg and
chull analysis: the code to propagate the factors when there are more than two
nodes. Maybe there could be a Stage 4 that does that?