Internet DRAFT - draft-sircar-complexity-entropy
draft-sircar-complexity-entropy
Network Complexity Research Group R. Sircar
Internet-Draft Ericsson
Intended status: Informational M. Behringer
Expires: April 21, 2014 Cisco
October 21, 2013
Using Entropy as a Measure for Changes in Network Complexity
draft-sircar-complexity-entropy-00.txt
Abstract
For the evaluation of network designs it is desirable to express
their complexity in objective, measurable metrics. Previous work has
shown that a large number of distinct, partly dependent scales play a
role in overall complexity. This document proposes the use of multi-
scale entropy metrics to describe the complexity of a network. We
observe that the complexity of a network which undergoes no changes
over a longer time period is constant. Conversely, when a network
undergoes changes entropy is increasing; this is independent on
whether the changes make the network more or less complex. In other
words, also a simplification effort increases complexity temporarily.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 21, 2014.
Copyright Notice
Copyright (c) 2013 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
Sircar & Behringer Expires April 21, 2014 [Page 1]
Internet-Draft Network Complexity Entropy October 2013
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction and Problem Statement . . . . . . . . . . . . . 2
2. Components of Network Complexity . . . . . . . . . . . . . . 3
3. Multi-Scale Entropy Analysis . . . . . . . . . . . . . . . . 4
4. Applying MSE Analysis to Complexity . . . . . . . . . . . . . 5
5. Validation of the Approach . . . . . . . . . . . . . . . . . 6
6. Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 6
7. Informative References . . . . . . . . . . . . . . . . . . . 6
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 6
1. Introduction and Problem Statement
When designing networks, low complexity is an often cited goal.
There are complexity metrics for some aspects of a network, for
example graph complexity or software complexity. But there is no
scientific way to determine the overall complexity of a network.
Every network has a lifecycle of its own. A network is envisaged and
architected based on the requirements to provide certain services.
Based on the architecture, it is then designed, implemented and
finally managed. Each of these phases in the lifecycle of the
network is impacted by the complexity of the network.
The overall complexity of a network can be broken down into smaller
parts, such as software complexity (of the operating systems),
configuration complexity, or the complexity to trouble-shoot
problems. On a component level, tradeoffs can be observed between
various parts of the network as described in [draft-ncrg-network-
design-complexity]. For example various elements of state, such as
forwarding state show a tradeoff with other network properties, such
as optimal forwarding behaviour.
All networks undergo further changes based on network growth, changes
in the requirements or needs as well as goal, obsolescence of
equipment, addition of services, change of vendors or technology or
evolution of technology. In a steady state condition of the network,
complexity remains constant.
Each of these changes is impacted by existing complexity of the
network. The change impacts the complexity level of the network.
Sircar & Behringer Expires April 21, 2014 [Page 2]
Internet-Draft Network Complexity Entropy October 2013
Thus, change in the network becomes an important parameter to be
defined and measured. This document introduces a term Network
Complexity Entropy to measure this change of network's complexity.
This is based on multi-scale entropy. In this document we describe
network complexity using multi-scale entropy analysis. The
underlying assumption is that complexity is related to change. We
postulate that a network with a decreasing number of changes over
time gradually becomes less complex to operate. Conversely, an
increasing number of changes in the network means that the network is
becoming more complex.
To support our assumption we define a set of measurable variables
which influence the complexity of the network, for example
configuration state or resilience of the network. The overall
network entropy is a function of those variables. As those variables
become stable over time, the overall entropy goes down. In our
interpretation this is illustrating the decreasing operational
complexity of the network over time. We believe that entropy is a
good approach to capture time based aspects of network complexity.
2. Components of Network Complexity
The document "A Framework for Defining Network Complexity"
[I-D.irtf-ncrg-complexity-framework] gives a number of examples of
network components, such as configuration, protocol state, operating
systems, network hardware such as routers and transmission equipment,
etc. These components are used in this document as variables in for
the multi-scale entropy analysis.
For example, consider the configuration of all network devices.
While the network is evolving and growing, there will be permanent
change to the global configuration of the network. However, assuming
no changes in the services provided, for some period of time the
overall operating system state could be unchanged, because the same
OS is deployed in more locations. The entropy of the configuration
is increasing in this example, whereas the entropy of the operating
systems is constant.
There is no complete list of network components that should be
considered for the analysis proposed in this document, as XXX offers
only a categorisation with some examples. The actual analysis will
therefore depend on the variables chosed, and is likely to represent
only a partial view of the change in complexity of a network.
The following section explains in detail how multi-scale entropy
analysis can be applied to measure changes in network complexity.
Sircar & Behringer Expires April 21, 2014 [Page 3]
Internet-Draft Network Complexity Entropy October 2013
3. Multi-Scale Entropy Analysis
Entropy was first defined in thermodynamics to model real world
phenomena. Later it was used by Shannon to define the expected value
of information contained in a message. There has been a good amount
of research where entropy has been used to measure topological
structural complexity of the network. [XXX add references] In each
of these definitions, change was measured over regular periodicity of
univariate time series on a single scale. Certain authors have used
similar definitions or mathematical constructs to assess structural
complexity of the underlying traffic or signal generating mechanisms.
These are very useful to evaluate repetitive patterns which are
generally quite predictable (e.g., periodic). Some of these
approaches have also been used for completely unpredictable (e.g.,
uncorrelated random) signals, but the results are not always very
intuitive.
In summary, all the above mentioned approaches are based on ergodic
theory for dynamical systems with time as an invariant measure. As
suggested by Lloyd Demetriusa et. al. XXX , the importance of
entropy - and its applicability to network theory - rests on three
fundamental properties:
1. Network entropy is an invariant of the dynamical system. It
characterizes the structure and the ergodic behaviour of a
dynamical system operating on the network.
2. Network entropy is positively correlated with robustness.
3. Evolutionarily stable states are characterized by extremal values
of network entropy. Maximal values of entropy arise where
evolution changes Complexity.
In this draft, we reuse the definitions and research done previously
to Network Complexity Entropy.
Networks and their evolution are truly complex and long-range
correlations at multiple spatial and temporal scales may be required
to measure entropy. The multi-scale entropy (MSE) method proposed by
Costa et. al. [XXX] explicitly quantifies the amount of structure
(correlation)in real world time series. This should help in defining
the underlying system os system's complexity. This approach has been
used by many researchers in recent times to identify such structural
complexities in Internet Traffic flows XXX .
The MSE method evaluates sample entropy of coarse grained (averaged
over increasing sequential segment lengths) univariate time series;
Sircar & Behringer Expires April 21, 2014 [Page 4]
Internet-Draft Network Complexity Entropy October 2013
the underlying idea is that coarse graining defines temporal scales,
hence a system without structure would exhibit a rapid decrease in
entropy with an increase in time scale. The existing MSE algorithm
has been proven to be able to distinguish between time series with
different degrees of complexity and its extensions have included
more rigorous definitions of time scales.
For a discrete random variable X, taking values {x1, ..., xn} with
probabilities {p1, ..., pn}, the information entropy or Shannon
entropy of X is then defined as the mean information content,
yielding S(X) = Sum {(over i=1...n) pi log pi}. Logarithm used here
is the natural logarithm.
Since the networks generate variable amount of data as well as noise,
MSE uses Approximate Entropy (ApEn) Algorithm [XXX] developed by Steve
Pincus. This has been used successfully in various disciplines. In MSE
or MultiScale Entropy, Costa et. al uses ApEn, but constructs multiple
coarse-graining time series by averaging the data points within
non-overlapping windows of increasing length. Now, let us define
"Network Complexity Entropy", such that this is calculated using MSE
algorithm. Thus, Network Complexity Entropy is the MSE of the selected
variables measured over time.
The goal of every network designer would be to optimize this Function.
Then, the goal of the Network Complexity Entropy is to:
Minimize [Network Complexity Entropy for topological structure,
Network Complexity Entropy for Traffic, Network Complexity Entropy
for Control Plane State,...] ---- our Objective Function.
Now, we need to now formulate 'n' Network Complexity Entropy for the
network in study:
1. Network Complexity Entropy for Topology - Structural Complexity
2. Network Complexity Entropy for Systems of System - Complexity due
to overall Network Structure and interfaces including VNO and
multi-vendor aspects
3. Network Complexity Entropy for Control Plane State - Complexity
due to Signaling, Routing and other Protocol Complexity
4. Network Complexity Entropy for Traffic and Optimal Forwarding
State / Paths
5. Network Complexity Entropy for Configuration State
6. Network Complexity Entropy for Policy Architecture
7. Network Complexity Entropy for Cost and Human impact - Complexity
due to financial systems, management systems and Systems
Integration etc.
4. Applying MSE Analysis to Complexity
Sircar & Behringer Expires April 21, 2014 [Page 5]
Internet-Draft Network Complexity Entropy October 2013
[now we define a (small) set of the above variables, and create an
entropy function with those. We model this function, and show
results of the modelling.]
5. Validation of the Approach
[Ideally, we want to pick a real-life network, and check the above
results against this network. Not sure this is feasible...]
6. Future Work
[undoubtedly, there will be a lot of open questions...]
7. Informative References
[I-D.irtf-ncrg-complexity-framework]
Behringer, M. and G. Huston, "A Framework for Defining
Network Complexity", draft-irtf-ncrg-complexity-
framework-00 (work in progress), February 2013.
Authors' Addresses
Rana P. Sircar
Ericsson
Michael H. Behringer
Cisco
Sircar & Behringer Expires April 21, 2014 [Page 6]
