Spatio-temporal Factorization of Log Data for
Understanding Network Events
Tatsuaki Kimura∗ , Keisuke Ishibashi∗§ , Tatsuya Mori† , Hiroshi Sawada‡§ , Tsuyoshi Toyono∗ ,Ken Nishimatsu∗ , Akio Watanabe∗ , Akihiro Shimoda∗ and Kohei Shiomoto∗∗ NTT Network Technology Laboratories, NTT Corporation, Tokyo 180-8585, Japan† School of Fundamental Science and Engineering, Waseda University, Tokyo 169-8555, Japan‡ NTT Service Evolution Laboratories, NTT Corporation, Kanagawa 239-0847, Japan§ NTT Machine Learning and Data Science Center, NTT Corporation, Kyoto 610-0237, Japan

Abstract—Understanding the impacts and patterns of network
events such as link flaps or hardware errors is crucial for
diagnosing network anomalies. In large production networks,
analyzing the log messages that record network events has
become a challenging task due to the following two reasons. First,
the log messages are composed of unstructured text messages
generated by vendor-specific rules. Second, network equipment
such as routers, switches, and RADIUS severs generate various
log messages induced by network events that span across several
geographical locations, network layers, protocols, and services.
In this paper, we have tackled these obstacles by building two
novel techniques: statistical template extraction (STE) and log
tensor factorization (LTF). STE leverages a statistical clustering
technique to automatically extract primary templates from unstructured log messages. LTF aims to build a statistical model that
captures spatial-temporal patterns of log messages. Such spatialtemporal patterns provide useful insights into understanding theimpacts and root cause of hidden network events. This paper first
formulates our problem in a mathematical way. We then validate
our techniques using massive amount of network log messages
collected from a large operating network. We also demonstrate
several case studies that validate the usefulness of our technique.

I. I NTRODUCTION
With the increase in the number of network elements andservices (e.g. IPTV, VoIP), it has become extremely difficult
to understand the impacts and patterns of network events suchas link flaps or hardware errors. The diversity of services
complicates the interactions of events, a common link down
event leads not only to neighboring nodes going down, but
may cause virtual path disconnections or cause related services to go down. Typically, a Network Management System(NMS), e.g. [1]–[4], monitors network health to deal withthe enormous network events that occur on a daily basis byusing Simple Network Management Protocol (SNMP) traps or
syslog triggers. Predefined rules in NMSs are such that alarms
represent apparently critical states. In today’s networks, on theother hand, operators often care about temporally abnormal
events, e.g. whether customers can access the service eventhough its quality is low. In addition, NMS alarms are so
obscure that they fail to capture the impacts or structures of
events such as the network layer, protocol, service dependencies. However, understanding such complicated structures ofc 2014 IEEE
978-1-4799-3360-0/14/$31.00 ⃝network events is crucial for caring out a detailed diagnosisof network anomalies.
Network logs, including syslogs and alarm messages reported by the NMS, contain some of the most important
information for diagnosing network anomalies. Network operators usually start their troubleshooting processes with alarm
messages. Syslog messages are often used for more complex
drill-down processes, in which operators check the root causeof problems and decide what they should do to recover fromthe failure. However, despite the usefulness of network logs,
they are not fully utilized in large production networks for
two reasons: (i) log messages are composed of unstructured
text messages generated by vendor-specific rules. Since a large
network consists of multi-vendor elements, formats of logs
are highly diverse. (ii) Log data is very complex because
network equipment such as routers, switches, and RADIUS
severs generate various log messages induced by underlying
network events that span across several geographical locations,network layers, protocols, and services.
A simple example that illustrates the complexity of log
messages is shown in Fig. 1. In this example, a set of link
down/up log messages is generated by a link flap event, which
can be differentiated from the original link down event. Notethat the same log message pattern appears in different hosts
with the layer 2 relationship. In addition to this, during thelink flap event, other events (e.g. a cron job in the example
of Fig. 1) may happen in the network. Thus, log data can beconsidered to be a superposition of the spatial and temporal
patterns caused by underlying network events. Since various
events occur from hour to hour throughout the entire network,
extracting these spatial-temporal patterns of log messages from
unstructured and complex log data is far more challenging.
Understanding the spatial-temporal patterns of log messages
provides useful insights into the network anomaly diagnosis.
For instance, it enables us to correlate multiple link flap events
that occur at different equipment each working in different
network layers. Such analysis is crucial in understanding theroot cause and impacts of the network anomaly. It also enables
us to extract hidden network events that could lead to network
failures. The extracted information can be used for preventive
maintenance operation.

2

derived a simple algorithm for LTF.
We validated LTF fits well the spatial-temporal patternsof network events through the extensive analysis ofmeasurement data collected at a large operating network.
We also demonstrated case studies that clearly show theusefulness of LTF.
The rest of this paper is organized as follows. Section II
summarizes the works related to our research. In Section III,
we explain network logs, log templates and the definitionof network events to mathematically formulate our problem.
Section IV provides our main result, the log tensor factorization. In Section V, we conduct several validations for the
proposed method and present case studies in Section VI.
Finally, Section VII concludes our paper.
•

Fig. 1. Log data can be considered as a superposition of log message patterns
induced by network events; in this example, we observe messages associatedwith both link flap (msg1–3) event and cron job (msg4–6).

II. R ELATED W ORKThis paper presents a novel spatio-temporal factorization
technique, which automatically learns and identifies spatial
and temporal patterns of log messages from unstructured andcomplex log data without relying on any domain knowledge.
Here, spatio refers to relationships among hosts in the network.
To achieve our goal, we first develop a Statistical Template Extraction (STE) method that automatically converts
unformatted log data to primary templates using a statisticalclustering algorithm. We then mathematically formulate thepattern of log messages by regarding it as a rank-3 tensor(a template, a host, and a timestamp). To build a statisticalmodel that captures spatial-temporal patterns of log messages,
we develop Log Tensor Factorization (LTF) based on Nonnegative Matrix Factorization (NMF) [14] and Nonnegative
Tensor Factorization (NTF) [8], which are powerful techniques
for decomposing a mixture of nonnegative elements into raw
features in unsupervised manner. By using LTF, we can obtainspatial and temporal patterns of log message groups, which canbe considered to be caused by the underlying network events
according to our observation. We successfully model both thespatial and temporal relationships, which cannot be obtainedby existing approaches because they are insufficient to model
these multiple relationships. To the best of our knowledge,
this formulation is the first attempt to analyze log data.
Further, despite the special features of LTF, we derive a simple
algorithm for obtaining the solution. Finally, we describe ourvalidation of the proposed method using a massive numberof data sets collected from a large scale operating network.
Experimental results show that our techniques successfully
fit the spatial-temporal patterns of network events. We also
demonstrate several case studies that validate the usefulnessof our technique.
We briefly summarize our contributions as follows:
We developed a statistical template extraction method,
STE, that automatically extracts primary templates frommassive and unstructured network logs without using any
prior information about log format.
• We developed a novel tensor factorization method, LTF,
that enables us to model spatial-temporal patterns of log
messages from the templates extracted by STE. We also•

There are many commercial products that aim to increase
the efficiency of network management and operations [1]–[5].
Specifically, Splunk [5] is a log analytics platform that collects
machine log data in real time and helps achieve fast search andanalysis. Although NMSs [1]–[4] have a root cause analysis(RCA) function, they cannot identify detailed network eventsand require domain knowledge.
A lot of research has also been done in the areas of network
fault diagnosis and fault localization by using various network
data in enterprise network. Yamanishi et al. [26] proposed atechnique to detect system failure from server syslog using
a mixture of Hidden Markov Models. SCORE [13] andShrink [10] are both fault localization systems using a bipartite
graph that models relationships among network elements on
the same SRLG (shared risk link group). Sherlock [6] isan RCA system that learns a dependency graph between
multilevel resources in enterprise networks. Orion [7] extracts
the causal relationship among application traffic by analyzingeach traffic delay. eXpose [11] reveals flow generation rules
by learning the association rules of flows from packet trace
data while our objective is modeling and learning the patternsof network log messages. NetMedic [12] monitors acts ofapplications and conducts detailed diagnoses of fault eventsoccurring in enterprise. Meta [21] and TAR [22] are both fault
localization systems, which automatically learn fault eventsfrom the event data sets and find the root causes of faults
rapidly by indexing the network events. However, they used
the network events data collected by the NMS, whereas ourscope is to extract such events from raw primitive log data.
Additionally, various studies that use router syslog and
SNMP messages have been done for large ISP networks.
NICE [16] extracts the statistical correlation between temporal
network events with time lags. G-RCA [27] is an RCA systemthat identifies the root cause of the problem by matching a current event to a predefined decision tree, which represents thecausal relationships of the network events. MERCURY [17]and PRISM [18] detect maintenance induced performancechanges using change point analysis and PCA-based subspacealgorithm. SyslogDigest [19] is the most closely related workto our research. It constructs digest information from router3

TABLE IE XAMPLES OF LOG MESSAGES#

syslog

1
2
3%LINK-3-UPDOWN: Interface FastEthernet 0/9, changed state to down
%SYS-5-CONFIG I: Configured from console by vty2 (10.11.XXX.YYY)
System: Interface ethernet XXX, state down

#

alarm

1
2

Interface down: IF: XXX IFIndex: YYY IFStatus: ZZZ
Node down: ping timeout ( 0 / 5 )TABLE IIE XAMPLES OF LOG TEMPLATES#

syslog

1
2
3%LINK-3-UPDOWN: Interface FastEthernet *, changed state to down
%SYS-5-CONFIG I: Configured from console by * (*)
System: Interface ethernet *, state down

#

alarm

1
2

Interface down: IF: * IFIndex: * IFStatus: *Node down: ping timeout ( * / * )syslogs by extracting the templates of logs and grouping
them within relevant routers. Since they do not take into
account the fact that log data is a superposition of message
patterns, they require domain knowledge for extracting the
spatial relationship.
III. N ETWORK L OG , T EMPLATE AND N ETWORK E VENT

where parameters are replaced by “*” and each log template
corresponds to the log message with the same ID in Table. I.
Although log templates may be obtained from vendor support pages or manuals, these templates may change due tosoftware updates or operational issues. In addition, some ofthem may not be opened publicly. Therefore, we developed
a method of statistical template extraction (STE) from large
scale log messages without relying on any prior information
about log format. Log parsing technique has been reported inother studies [19], [25]. Specifically, Qiu et al. [19] presented
the template extraction from router syslogs. They selected
a similar approach to the spam detection by constructing asignature tree whose root is the message type of the log.
However, it is difficult to determine the root of the tree in thecase of general logs. Thus, STE takes another approach using
the following features of log messages: parameters appear lessfrequently than template words; and messages have similar
structures with the positions of words, among those generated
from the same templates. STE consists of two parts: (1)statistical word scoring and (2) score clustering.
1) Word scoring: We assume words are separated by whitespace in each message. In general, template words tend to
appear in the same position in messages that have the samewords length. From this observation, we score the tendency ofwords to be a template word as follows: if a word appears in
the p-th position in a log message that contains Len words,
then the score for the word is defined as

In this section, we explain an overview of network log data
and a preprocessing technique for modeling the patterns of log
messages, called STE. We then define the network events tomathematically formulate the LTF problem.
Network logs such as router syslog and alarms captured
by NMS include various information: network faults, security
issues, and console logs. In general, they consist of three parts:
a timestamp, a host name (or IP address) and a message.
Examples of the message parts of network logs are given in
Table I. Although their format depends on the service type or
the vendor of each instrument, log messages consist of shortreadable texts. Therefore, common structures can be foundamong them; there are parts that represent event types orentities (%LINK-3-UPDOWN and System), parts that showchanges of states (down/up), and parameter parts (IP address,
host name, and process ID).

From the above definition, the score for the template words isgreater than the parameters.
2) Score clustering: Next, we need to determine whether
word is a parameter or template word. A simple approach is
to set a threshold for the score; however, such an approach
would fail because the range of scores depends on the feature
space with the same (p, Len). To avoid this, we take aclustering approach for scores and divide all the words in eachmessage into template words and parameters. The clustering
technique we use here is DBSCAN (Density Based Spatial
Clustering) [9], which makes clusters so that the distance
between clusters is greater than some threshold δ. We thenfinally obtain a template by choosing the top clusters so thatthe number of words is greater than β×Len, where 0 < β < 1.

A. Statistical Template Extraction

B. Definition of Network Events

Because of the variety and large volume of logs, it isunrealistic to extract patterns from raw log messages. For
example, we can easily find a strong correlation between%LINK-3-UPDOWN events and %LINEPROTO-5-UPDOWN
events because layer 2 down/up events often induce layer
1 down/up events. However, to extract such a correlation,
we need a sufficient number of samples of layer 1 and 2
down/up event co-occurrence at the same interface and link.
Therefore, our objective here is to obtain correlation among
not raw log messages, but log templates, i.e. messages withoutparameters. Examples of log templates are listed in Table. II,

We now give the definition of network events using log
templates. This definition will be used for LTF formulation.
Observations of log data indicate that there is a log templategroup that is likely to co-occur, and it represents the stateof individual network elements. Further, underlying network
events may cause log template groups to influence multiple
hosts (see Fig 1). Therefore, we consider such correlated log
messages with spatial impacts as network events. We first
define the log template group and then define the network
events. In what follows, we assume log templates for all log
messages are appropriately extracted and that all host names

Score(word, p, Len) = P(word | p, Len).

4and time stamps of log messages are also known. In addition,
we partition input log data by time-windows. Further, we writei ∈ I, h ∈ H, and j ∈ J to represent templates, hosts, andtime-windows, where I, H, and J are the total sets of i, h,and j, respectively.
Definition 1 (Template Group) A log template group l ∈ L
is defined as a set of templates that tends to co-occur at a single
host, where L represents the total set of template groups.
A template group represents an event at an individual host,e.g., router reboot, link flap, or configuration change. Notethat for a fixed template, its multiple allocation to different
template groups is allowed. The reason for this is that some
template groups may be a subset of other template groups. For
instance, although link flap is a combination of link down andup templates occurring at the same time-window, each link
down/up message can appear separately.
Definition 2 (Network Event) A network event e is definedas tuple sets of a host and a template group that tend
to co-occur, i.e. e = {(h1 , l1 ), (h2 , l2 ), . . . } (h1 , h2 , · · · ∈H, l1 , l2 , · · · ∈ L).
From the definition, network events are considered to be a
spatial extension of template groups. For example, with a link
flap, if a link flap occurs at some host, then similar log groups
appear at its neighbor hosts. Network events are described asa mixture of such relationships and the template groups.

Fig. 2. Concept image of LTF. The target tensor X is factorized into an
I × L matrix V , an L × K × H rank-3 tensor Z, and a K × J matrix W .

I × H × J whose (i, h, j)-th element is xihj , where I = |I|,
H = |H| and J = |J |, respectively.
Our key insight for modeling the log is to regard log data ineach time-windows as a hierarchical superposition, i.e. log data
is a mixture of network events, which also consist of templategroups. According to this observation, we rewrite the network
event extraction problem from log data as the following tensor
factorization problem.
Problem (LTF: Log Tensor Factorization) For a giventensor X with the dimension I ×H ×J and integers K and L,
the log tensor factorization problem is to find a factorizationsuch that
]
[ L
K
∑
∑
X≃
v l ⊗ z lk ⊗ wk ,(1)
k=1

IV. L OG T ENSOR FACTORIZATION
Our main contribution in this paper is modeling the thepatterns of network log messages and mathematically formulating the extraction of network events from logs. The first
key idea for the event extraction is to regard network log data
as a rank-3 tensor (log templates, hosts, and time-windows),
and to extract template groups and host relationships thatare likely to co-occur in log data. On the basis of thisidea, we take a nonnegative tensor factorization approach,in which we directly model and learn the template groupand the network events defined in Section III-B. Our tensor
factorization problem is closely related to NMF [14] andNTF [8], which are powerful machine learning techniques fordecomposing a mixture component to nonnegative features. In
addition, they are widely applied to various areas such as audio
processing [20], text mining [23], image analysis [14] andbrain signal analysis [8]. However, these classical approaches
do not fit well to our problem because they cannot model boththe template groups and the spatial relationships (discussed indetail in Section IV-B). Therefore, we developed a novel tensor
factorization, LTF, and derived simple update rules for it. We
first introduce a definition of tensor expression of logs.
Definition 3 (Log Tensor) For a log template i ∈ I, a hosth ∈ H, and a time-window j ∈ J , let xihj ∈ {0, 1, . . . }denote the number of occurrences of a log message. A log
tensor X is defined as a rank-3 tensor with the dimension

l=1

where for l = 1, . . . , L and k = 1, . . . , K, v l = [vil ],z lk = [zlkh ] and wk = [wkj ] are nonnegative vectors withthe dimensions I, H, and J, respectively.
For convenience, we define an I ×L matrix V as V = [vil ],an L × K × H tensor Z as Z = [zlkh ], and a K × J matrix
W as W = [wkj ]. A conceptual image of LTF is shown in
Fig. 2. In what follows, we give intuitive interpretations for V ,Z, and W . First, matrix V can be considered as a templategroup matrix. A visualized image of V is shown in Fig. 3.
If a template i belongs to a template group l, then vil > 0,and otherwise vil = 0, i.e., each vector v l corresponds to thel-th template group, and L represents the number of templategroups. Second, rank-3 tensor Z can be regarded as a network
event tensor, and we call each H × L matrix z k an event
slice. A visualized image of Z is shown in Fig. 4. In each
event slice, if a template group l at host h belongs to the k-th
network event, then zlkh > 0. In other words, the k-th event
slice z k corresponds to k-th network events and K is equal to
the total number of network events. Finally, matrix W can beconsidered as a weight matrix. Each element wkj representsa weight that the k-th network event takes in time-window j.
In short, we can understand when the k-th network event has
occurred by observing wk .
Summarizing the above, we can interpret the LTF problem
as follows: (i) each v l corresponds to template groups; (ii) the
event slice z k represents the network events, i.e. which hosts

5

and j ∈ J ,∑vil :=
zlkh :=
hkj :=
Fig. 3. Visualized image of matrix V . The l-th vector of V , v l , represents
in each element whether a template i belongs to a template group l or not.
In this example, there are spikes at templates A and C, thus, they belong to
the same template group.

h,j,kz̆lkh w̆kj∑

k′ ,l′ v̆il′ z̆l′ k′ h w̆k′ j∑· xihjv̆il ,(4)∑z̆lkh ,

(5)∑w̆kj ,(6)h,j,k zlkh wkj∑
v̆il w̆kj∑· xihji,jk′ ,l′ v̆il′ z̆l′ k′ h w̆k′ ji,j vil wkj∑
v̆il z̆lkh∑· xihji,h,lk′ ,l′ v̆il′ z̆l′ k′ h w̆k′ ji,h,l vil zlkh

where v̆il , z̆lkh , and w̆kj represent older values in each iteration. After each update, it is necessary to normalize V and Z
with respect to the conditions in (2). We give complete proofs
for deriving (4)–(6) in the Appendix.
B. NTF and LTF
We here note the difference between the conventional NTF
problem and the LTF problem. Given a rank-3 tensor X, theNTF problem is to find a factorization such that

Fig. 4. Visualized image of tensor Z. The k-th event slice of Z, z k , represents
k-th network events. If template group l at host h is the k-th network event,then we can see zlkh > 0.

X≃

K
∑

v ′k ⊗ z ′k ⊗ w′k ,k=1

take a template group l; and (iii) X can be considered as asuperposition of event slices with weights {wk }.
A. Multiplicative Update Rules
We now develop an algorithm to calculate output tensorsof the LTF problem. As mentioned before, the LTF problem
is an extension of the NMF or NTF problems, which have
simple iteration algorithms for obtaining the solutions; thesealgorithm are known as multiplicative update rules [8], [14].
On the basis of their derivation, despite the special featuresof our model, we can derive very simple update rules for LTF
via an auxiliary function approach.
First, the LTF problem can be mathematically formulated
as the following minimization problem:
min D(X∥V , Z, W ),V ,Z ,W∑∑s.t. V , Z, W ≥ O,
vil = 1,zlkh = 1,
i

(2)

l,h

where D(·) represents the KL-divergence function and serves
as a cost function. More specifically,
D(X∥V , Z, W )∑=xihj log ∑
i,h,j

∑
xihj
− xihj +vil zlkh wkj .
k,l vil zlkh wkjk,l(3)
Note that the second and third equalities in (2) are normalization conditions. We then have the multiplicative update rules
for optimization problem (2) as follows: for i ∈ I, h ∈ H

where v ′k , z ′k , and w′k are rank-1 tensors with the dimensions
I, H, and J, respectively. Intuitively, the NTF finds thecorrelated patterns in the log tensor X and describes it with thesum of the tensor product of K rank-1 tensors. In coordination
with the expression of the LTF, each v ′k ⊗z ′k can be considered
as an insufficient expression of the network events: when weinterpret v ′k as a log template group, the corresponding tensor
product v ′k ⊗z ′k represents that the k-th template group occurs
at the hosts in z ′k ; however, this is different from Definition 2.
According to our observation, a certain log template group
may appear in different host groups; therefore, the numberof template groups and of network events should be different(L < K, in general). Consequently, we can say that LTF is anextension of the normal NTF in the sense that the NTF canmodel only groups of a set <log template, host> that tend
to co-occur. By contrast, the LTF models the template groups
that appear in these groups.
C. Noise Filter
There are long running logs that induce spurious correlations, such as the firewall logs. In addition, these logs increase
computational costs. Therefore, we apply a noise filter to thedata that remove sets of a host and a template that occur withhigh frequency. We define the frequency for template i andhost h as a fraction of the time-windows in which a tuple (i, h)
is observed. Specifically, we choose 0.01 as the threshold in
our experiments described in Section V.
V. E VALUATIONIn this section, we report our experimental validation of our
proposed method using real log data sets.

6

1150
1100
1050
1000
950
900

β = 0.70
β = 0.75
β = 0.80850
1e-05 0.0001 0.001

0.01

0.1

1

δ

Fig. 5. Comparison of the number offalse positive words.

-24

7000
β = 0.706500
β = 0.75
6000
β = 0.80
5500
5000
4500
4000
3500
3000
2500
2000
1500
1e-05 0.0001 0.001

-26
-28

-15
NTF
LTF L=30
LTF L=50

average log likelihood

1200# of templates# of failed words

1250

average log likelihood

1300

-30
-32
-34
-36
-38
-40
-42

0.01

0.1

1

δ

Fig. 6. Comparison of the number ofextracted templates.

B. LTF Evaluation
1) Evaluation metrics: We first explain our evaluation
metrics. Our primary goal is to model the generative rules oflog data and network events and to extract meaningful events
for network operations. Therefore we set the following two
metrics: (i) the expressive power of LTF for real log data; and(ii) the effectiveness of the outputs of LTF. To evaluate (i), we
selected a well-known quantitative measure, which evaluates
how we can predict non-zero elements in unknown log datawith a given input tensor. More specifically, we employ theaverage log likelihood for the test set, which consists of nonzero elements randomly chosen from the target data tensor
X. The predictions for the test set are calculated by the LTF
model that learned from X without chosen test data points.

-25
-30
-35
-40
-45

40

60

80
K

100

120

Fig. 7. Comparison of the averageof test log likelihood with different K
and L values. Error bars represent the
95% confidence interval of a mean.

A. STE Evaluation
We first show the evaluation results for the template extraction, STE. We used over 5 million lines of logs captured
in a certain small network. In this evaluation, we set two
metrics: accuracy and effectiveness. However, because of alack of ground truth, it was difficult to measure the accuracy. Therefore, we assumed the following two scenarios:(i) calculate the number of false positive words, which arewords without numbers removed by STE; and (ii) calculate
the number of extracted templates. We observed that words
without numbers tend to be template words; however, they
may be template words such as a hostname and a path name,e.g. /usr/local/path.
The result for (i) is shown in Fig. 5. The vertical axis
represents the number of false positive words. It is clear
from the graph that if parameter δ increases, STE removed
too many words. Since our data set include more than ahundred of thousands of unique words, we can confirm that
our method has sufficient accuracy. Next, Fig. 6 shows theresult for scenario (ii). The graph shows that our template
extraction method can reduce the size of log data to lessthan 1%. We can see that if δ or β increases, then the total
volume of templates also increases. This character of β is
obvious, because β determines the threshold for the numberof parameter words in each log messages. On the other hand,
if δ increases, then DBSCAN algorithm split words into lessclusters, hence, the number of templates decreases. Finally,
we choose β = 0.75 and δ = 0.01 as practical values in thefollowing all experiments by observing the output templates.

NTF
LTF L=30
LTF L=50-20

180 300

600
time window size

900

Fig. 8. Comparison of the averageof test log likelihood with different L
and time-window sizes and K = 60.
Error bars represent the 95% confidence interval of a mean.

The average log likelihood is then defined as
1 ∑log p(xn ; x̃n ),N n=1
Nwhere p(·) is a Poisson distribution function, N is the numberof non-zero elements, and x̃n represents the prediction of eachelement. Note that a higher average log likelihood indicates
better modeling of the data. For the validation of (ii), we
calculated the false positive rate of output template groups bymanual inspection. To obtain the false positive rate, we labeled
all template groups of LTF as ‘related’ or not by checking thelocations or protocols described in the messages. Note that we
do not check network events. This is because if the templategroups are accurately extracted, we can find the meanings ofthe network events.
2) Comparison with NTF: In the first scenario of ourexperiments, we verify that our model fits well to real data. We
choose the NTF as the baseline of our model. As we discussed
in Section IV-B, the LTF can be considered as an extensionof the NTF because the LTF extracts template groups andnetwork events at the same time. The input data we used hereis over 600,000 lines of 1-day log data from a certain network,with the dimension roughly 100 (I) × 150 (H) × 150 (J). We
set the number of masked elements N to 5 and iterate 50
times for both parameter estimation and learning processes.
In Fig. 7, we show the average test log likelihood results of
the NTF and LTF with different K and L values. We can seethat the LTF achieves higher log likelihood than NTF for all
K and L values. This result indicates that the LTF model fitsbetter to the real data than the NTF model. We can also seethat the NTF achieves the highest value when parameter K is80, and if K turns away from 80, its log likelihood decreases.
The reason for this can be considered as follows: if K is lessthan the proper value (K = 80 in this case), the NTF fails
to sufficiently model the input data, and if K is higher thanthe proper value of K, then they over-fit the test data and can
not predict the removed entries. On the other hand, the LTF
takes higher values when K > 80. This is because the LTF
expresses the log data with L template groups, whereas the
NTF expresses the log data with K the rank-1 tensors. This
fact means that there certainly exist template groups that tend
to co-occur, and our modeling is valid for the real data.

7

0.4

tensor with the dimensions of about 100 × 100 × 1000 roughly
within a day. LTF can be easily applied to parallel processing
by splitting the inputs, therefore the performance of LTF canbe considered to be sufficient for an event extraction purpose.
We selected appropriate parameters K and L for each input,
and we fixed the time-window size at 5 min.

1
L = 20
L = 30L = 50false positive rate

false positive rate

0.5

0.3
0.2
0.1
0

0.8
0.6
0.4
0.2
0

180 300

600
time window size

900

30

40

50
K

60

70

A. Case: Self-generating Events
Fig. 9. The FPR with different timewindow sizes and L’s.

Fig. 10. The FPR with different K’s
and fixed time-window size and L.

Next, Fig. 8 shows the impact of the time-window sizeon the average log likelihood. We also can see that the LTF
achieves better results than the NTF in all time-windows. In
particular, when the time-window size is 180 sec. (= 3 min.),the average log likelihood is the highest. This fact means thatmost of the network events tend to occur within 3 min. The
graph also shows that if the time-window size is greater than180, then the average log likelihood decreases. The reason
for this fact is that when the time-window is too large, eachtime-window may contain irrelevant network events.
3) False positive template groups: In the second experiment, we confirmed that LTF could efficiently output accurate
information from the network operators’ viewpoints. We used
the same input data as in the previous experiment. Due tothe lack of ground truth data, we calculated the false positive
rates (FPR) of LTF outputs by manually checking all templategroups whether they were ’related’ or not. Fig. 9 shows FPR
with different time-window sizes and L, where K was fixedat 60. Clearly, approximately 80–90% of the outputs of LTF
can be considered to be meaningful events. We can also seethat time-window sizes larger than 300 sec. result in larger
FPR, except for the case of L = 50. The reason for this issimilar to the case of evaluating the average log likelihood withdifferent time-window sizes. The case in which only L = 50
has a different tendency can be explained as follows: when L
is too large, the LTF outputs more redundant template groups,
i.e. it over-fits the input data. In Fig. 10, we show the FPR
with different values of K where L and the time-window size
are fixed at 30 and 5 min., respectively. We can observe thatthe value K does not have much effect on L. This fact meansthat the number of template groups are selected independently
with the number of network events. This character is also seenin Fig. 7.
VI. C ASE S TUDY
In this section, we present several interesting network events
obtained by the LTF as case studies. We conducted an LTF
experiment to one week of log data of a certain large scale network where tens of thousands of hosts are working. The input
data include daily maintenance, temporally abnormal logs andeven critical network faults. Since our dataset was large, we
split it into independent host groups that are considered to berelated, in order to avoid computational costs. As our primary
implementation, we can finish each experiment of a one-week

Although one of our objectives is to find relationships
between multiple hosts, there are self-generating events that
only appear at a single host and do not have any influenceon other hosts. Table III lists the examples of them. The firstexample is a simple user login event, which is a very common
event in the daily network operation. We can confirm thateven if a template group contains only one element (template),
the proposed method was able to extract it accurately, byobserving that the corresponding weight value is 1.0. The
second example is a fan speed-up event at a certain host. This
type of event can be found on some other hosts and is not
related to alarms, thus, operators do not pay much attention
to them. By observing the raw log messages, we can see thatthe time intervals between each messages of this events areapproximately 3–5 minutes. As as result, the time-window
size should be more than 180 sec. to capture this event. It
is understood that the router fan speed-up implies an increasein the temperature, which may cause an unintended shutdownof components. Thus, even if it does not directly relate to acomplete fault, we believe that this template group is important
for the daily operation. The third example is an administrative
link down event, which does not have any influence on otherhosts. This is because the neighboring nodes are outside of
their monitoring area, and thus log data are not collected. We
can also see that even this simple link down event has threelog templates because of protocol interaction.
B. Case: Neighboring Nodes Flap Event
One of the interesting outputs of LTF is a network eventwith a neighbor relationship. An example is presented inTable IV. This example shows that an interface flap has
occurred at the CoreRouterA, and then a related interface andlink flap has occurred at its neighbor EdgeRouterB. As we
mentioned in Section IV-B, it can be seen that these neighboring interface events result in different template groups.
Further, in EdgeRouterB’s flap event, we can see that thelayer 1 protocol flap induces layer 2 protocol flap. We notethat link flap events are common in real network, because they
are caused by typical operations including adding new ports orreloading modules. Thus, they do not always represent criticalfaults, which would have an impact on users’ experience.
However, it is also known that link flaps may occur before
nodes completely down. Therefore, we can find importance inextracting and identifying such temporally abnormal events.
We also note that the LTF can extract the complete link down
event separately with this link flap event.

8

TABLE IIIE XAMPLES OF SELF - GENERATING NETWORK EVENTS ( ONLY TEMPLATE GROUPS ARE SHOWN )#Weights1

1.0

login : LOGIN INFORMATION : User * logged in from host * on device *

2

0.5
0.5

chassisd [ * ] : CHASSISD BLOWERS SPEED : Fans and impellers are now running at normal speed
chassisd [ * ] : CHASSISD BLOWERS SPEED FULL : Fans and impellers being set to full speed [ system warm ]

0.33
0.33
0.33

* : TIME : %LINK-5-CHANGED : Interface * , changed state to administratively down
* : * : %LINK-3-UPDOWN : Interface * , changed state to down
* : TIME : %LINK-3-UPDOWN : SIP * : Interface * , changed state to down

3

Templates

TABLE IVN EIGHBORING LINK FLAP EVENT
Host NameTG Weights

Weights

CoreRouterA

0.666

0.4
0.4
0.2

TIME : ifmgr [ * ] : %PKT INFRA-LINK-3-UPDOWN : Interface * , changed state to Up
TIME : ifmgr [ * ] : %PKT INFRA-LINK-3-UPDOWN : Interface * , changed state to Down
TIME : %SYS-3-LOGGER DROPPED : System dropped * console debug messages.

0.333

0.4
0.17
0.17
0.17
0.05

* : * : %LINK-3-UPDOWN : Interface * , changed state to up* : TIME : %LINK-3-UPDOWN : Interface * , changed state to administratively down
* : * : %LINEPROTO-5-UPDOWN : Line protocol on Interface * , changed state to up* : * : %LINEPROTO-5-UPDOWN : Line protocol on Interface * , changed state to down
* : * : %LINK-3-UPDOWN : Interface * , changed state to down

EdgeRouterB

Templates

C. Case: Tunneling Disconnection Event
The final case we present is a network event with tunneling
relationships. In this example, network operators did not
notice the spacial impact of the network event because of thecomplexity of it. In general, tunneling or virtual path protocols
are widely accepted in existing networks. However, they are
difficult to maintain because virtual paths change from hour tohour. In Table V, we show an example of a tunneling network
event. First, according to network operators, the templategroup of CoreRouter indicates a module reload event, due
to the module error. Since this reload event includes a lotof templates, we can see that the corresponding weight given
to each template in the template group is low. Second, virtual
path disconnections are caused at EdgeRouters C and D. Since
the CoreRouter has more than a hundred connections withother hosts, the corresponding weight given to the templategroup is low (less than 0.02). From the observation of the raw
data, we found that there was a pattern of the template groupthat occurred periodically at the CoreRouter, and they were
information for debugging generated by a certain periodic job.
Since a number of these log messages appeared during theduration of the event (approximately 5 minutes), it was difficult
to find this module reload and tunneling disconnection event.
Further, the volume of not only the other events, but also of
the virtual path disconnection messages was large. Thus, theyalso became an obstacle to identify the network event. As aresult, the LTF can accurately extract a complex network event
when it is difficult to identify from the raw log data.

the complexity of log messages, we developed a statistical
template extraction method, STE. Using log templates, wemathematically modeled the patterns of network logs. To
formulate spatial and temporal patterns of log messages, wedeveloped a novel tensor factorization technique, LTF. We
verified that our model fits well to real data and also showed
several case studies in which the proposed methods can extract
various useful network events for the network operation.
Understanding the spatial-temporal patterns of log messages
provides useful insights into various network operations. Associating learned network events with NMSs enables us tomonitor both normal and abnormal events with their spatial
impacts even though such relationships are difficult to maintainas in the example of Table V. The extracted information can beused for preventive maintenance operation, such as a link flap
event or a fan speed-up event. In addition, by learning normal
network events, LTF can detect the abnormal log group or
network events that cannot be expressed as a superpositionof learned network events in the past. For example, a routerreboot event causes various logs such as process initialization.
With the network events learned by the LTF, we can detect thatcertain process did not start because in such cases, the costfunction increases. This is an interesting application, becausea typical anomaly detection system with threshold monitoring
fails to detect the event.
ACKNOWLEDGMENT
The authors would like to thank to Masayasu Miyazaki for
helping in the experiments.

VII. C ONCLUSION
In this paper, we proposed a spatio-temporal factorization method, which automatically learns underlying network
events from unstructured and complex log data. To overcome

A PPENDIX :U PDATE RULE D ERIVATION
In what follows, we derive only the update rule for V . The
cases of Z and W can be derived in the same way. Thus, we9TABLE VT UNNELING PATH DISCONNECTION EVENT
Host NameTG Weights

Template Weights

Templates

0.43750.08330.08330.0833.
.
.

SNMP Trap: a status change for a module. Software image for the module is missing or invalid....
os: loader: * for * is *id of requester is *OsCrashDump: invalid crash record skipped, ...
.
.
.

CoreRouter

0.0253

EdgeRouterC

0.01656

0.92805

Tunneling Virtual Path * is disconnected, hardware unavailable.

EdgeRouterD.
.
.

0.01594.
.
.

0.98308.
.
.

Tunneling Virtual Path * is disconnected, hardware unavailable.
.
.
.

omit them. We define the auxiliary function D+ (·) as
D+ (X∥V , Z, W , R)∑∑
vli zlkh wkj=−rihjlk xihj log
rihjlki,h,j k,l

+ vli zlkh wkj + xihj log xihj − xihj ,(7)

rihjlk is a nonnegative variable such thati,j,h,l,k rihjlk = 1 and R denotes a total set of rihjlk . Due
to Jensen’s inequality and the convexity of the log function,
we obtain for any rihjlk ,∑∑vli zlkh wkj
vli zlkh wkj
rihjlklog
rihjlk log≥,
rihjlkrihjlk
where
∑

k,l

k,l

from which, (3) and (7), it follows that D(X∥V , Z, W ) ≤D+ (X∥V , Z, W , R), where the equality attained if and only
if vli zlkh wkj /rihjlk is the same for all l, k, i.e.,vli zlkh wkj
rihjlk = ∑
.
(8)
′
′ ′
′
′
k ,l′ vl i zl k h wk j
Next, we minimize D(X∥V , Z, W ) by V . Substituting (8)into (7) yields
D+ (X∥V , Z, W , V̆ , Z̆, W̆ )∑∑v̆ z̆ w̆∑ li lkh kj=· xihj′′ ′′k′ ,l′ v̆l i z̆l k m w̆k j
i,h,j k,l[]v̆li z̆lkh w̆kj
× log ∑− log vli zlkh wkj′′ ′′k′ ,l′ v̆l i z̆l k h w̆k j+xihj log xihj − xihj + vli zlkh wkj .
Finally, differentiating the above equation by vli and substituting 0 into both sides leads to (4).
2R EFERENCES[1] CA Spectrum. http://www.ca.com/us/root-cause-analysis.aspx.
[2] EMC ionix platform. http://www.emc.com/products/family/ionix-family.
htm.
[3] HP Software. http://www8.hp.com/us/en/software/enterprise-software.
html.
[4] IBM Tivoli. http://www-01.ibm.com/software/tivoli/.
[5] Splunk. http://www.splunk.com/.
[6] P. Bahl, R. Chandra, A. Greenberg, S. Kandula, D. A. Maltz, and
M. Zhang, Towards Highly Reliable Enterprise Network Services via
Inference of Multi-level Dependencies, In Proc. of SIGCOMM, 2007.

[7] X. Chen, M. Zhang, Z. M. Mao, and P. Bahl, Automating Network
Application Dependency Discovery: Experiences, Limitations, and New
Solutions, In Proc. of OSDI, 2008.
[8] A. Cichocki, R. Zdunek, A. H. Phan, and S. I. Amari. Nonnegative Matrix
and Tensor Factorizations: Applications to Exploratory Multi-way Data
Analysis and Blind Source Separation. Wiley. 2009.
[9] M. Ester, H. P. Kriegel, J. Sander, and X. Xu, A Density-based Algorithm
for Discovering Clusters in Large Spatial Databases with Noise, In Proc.
of KDD, 1996.
[10] S. Kandula, D. Katabi, and J. P. Vasseur, Shrink: a Tool for Failure
Diagnosis in IP Networks, In MineNet, 2005.
[11] S. Kandula, R. Chandra, and D. Katabi, What’s Going on? Learning
Communication Rules in Edge Networks, In Proc. of SIGCOMM, 2008.
[12] S. Kandura, R. Mahajan, P. Verkaik, S. Agarwal, J. Padhye, and P. Bahl,
Detailed Diagnosis in Enterprise Networks, In Proc. of SIGCOMM, 2009.
[13] R. R. Kompella, J. Yates, A. Greenberg, and A. C. Snoeren, IP Fault
Localization via Risk Modeling, In Proc. of NSDI, 2005.
[14] D. D. Lee and H. S. Seung, Learning the Parts of Objects by NonNegative Matrix Factorization, Nature, 401, pp.788–791, 1999.
[15] D. D. Lee and H. S. Seung, Algorithms for Non-negative Matrix
Factorization, In Proc. of NIPS, 2000.
[16] A. Mahimkar, J. Yates, Y. Zhang, A. Shaikh, J. Wang, Z. Ge, andC. T. Ee, Troubleshooting Chronic Conditions in Large IP Networks,
In Proc. of CoNEXT, 2008.
[17] A. Mahimkar, H. H. Song, Z. Ge, A. Shaikh, J. Wang, J. Yates, Y. Zhang,and J. Emmons Detecting the Performance Impact of Upgrades in Large
Operational Networks, In Proc. of SIGCOMM, 2010.
[18] A. Mahimkar, Z. Ge, J. Wang, J. Yates, Y. Zhang, J. Emmons, B. Huntley, and M. Stockert, Rapid Detection of Maintenance Induced Changes
in Service Performance, In Proc. of CoNEXT, 2011.
[19] T. Qiu, Z. Ge, D. Pei, J. Wang, and J. Xu, What Happened in my
Network? Mining Network Events from Router Syslogs, In Proc. of IMC,
2010.
[20] P. Smaragdis and J. C. Brown, Non-negative Matrix Factorization for
Polyphonic Music Transcription, In Proc. of WASPA, 2003.
[21] T. Wang, M. Srivatsa, D. Agrawal, and L. Liu, Learning, Indexing, andDiagnosing Network Faults, In Proc. of KDD, 2009.
[22] T. Wang, M. Srivatsa, D. Agrawal, and L. Liu, Spatio-temporal Patterns
in Network Events, In Proc. of CoNEXT, 2010.
[23] W. Xu, X. Liu and Y. Gong, Document Clustering Based on Nonnegative Matrix Factorization. In Proc. of SIAM, 20111.
[24] W. Xu, L. Huang, A. Fox, D. Patterson, and M. I. Jordan, Mining
Console Logs for Large-Scale System Problem Detection, In Proc. of
SysML, 2008.
[25] W. Xu, L. Huang, A. Fox, D. Patterson, and M. I. Jordan, Detecting
Large-Scale System Problems by Mining Console Logs, In Proc. of SOSP,
2009.
[26] K. Yamanishi and M. Maruyama. Dynamic Syslog Mining for Network
Failure Monitoring, In Proc. of KDD, 2005.
[27] H. Yan, L. Breslau, Z. Ge, D. Massey, D. Pei, and J. Yates, G-RCA: a
Generic Root Cause Analysis Platform for Service Quality Managementin Large IP Networks, In Proc. of CoNEXT, 2010.