Internet DRAFT - draft-wehmuth-nmrg-sdn-model
draft-wehmuth-nmrg-sdn-model
Internet Engineering Task Force K. Wehmuth
Internet-Draft A. Ziviani
Intended status: Informational LNCC
Expires: December 23, 2017 June 21, 2017
A Reference Model for Representing SDN Environments
draft-wehmuth-nmrg-sdn-model-00
Abstract
Software-Defined Networks (SDNs) are multilayer systems. In this
context, this draft defines a graph-based reference model capable of
properly representing such complex multilayer networks. The defined
reference model thus eases the management and planning of SDN
environments.
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 December 23, 2017.
Copyright Notice
Copyright (c) 2017 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
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.
Wehmuth & Ziviani Expires December 23, 2017 [Page 1]
Internet-Draft SDN Reference Model June 2017
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Why modeling SDNs as multilayer networks . . . . . . . . . . 3
3. How to model a SDN as a multilayer network . . . . . . . . . 4
3.1. Introduction to MultiAspect Graphs . . . . . . . . . . . 4
3.2. Multilayer graph (MLG) definition . . . . . . . . . . . . 4
3.3. Algebraic representations and structures . . . . . . . . 5
3.4. MLG adjacency matrix . . . . . . . . . . . . . . . . . . 5
3.5. SDN reference model . . . . . . . . . . . . . . . . . . . 8
4. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 9
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
6. Security Considerations . . . . . . . . . . . . . . . . . . . 9
7. Informative References . . . . . . . . . . . . . . . . . . . 9
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10
1. Introduction
Software-Defined Networks (SDNs) are inherently multilayer systems.
In addition to the traditional layers associated with the separated
data and control planes, other layers can be considered to support
structures, such as hierarchical controllers, structured interaction
between applications, use of Network Functions Virtualization (NFV)
on SDN environments, among others. It is important to properly
represent such a complex structure in a convenient way that allows
modeling and analysis of a SDN environment with a single object.
In this context, we propose the use of a theoretical graph framework
[Wehmuth2016], capable of modeling multilayer complex networks, for
representing SDN environments. This framework is capable of
representing complex networks containing an arbitrary (finite) number
of layers, thus allowing the representation of SDN systems with any
number of associated layers. In this framework, if desired, the
usual SDN layers can be divided into sub-layers allowing the creation
of more detailed and structurally rich SDN reference models.
Therefore, this framework is capable of modeling various distinct SDN
architectures, such as ForCES [RFC3746], SDN systems adherent to
[RFC7426], [draft-irtf-sdnrg-pop-00], or any other layered networking
architecture. Further, the considered framework has the property of
guaranteeing that any model created in it is necessarily equivalent
(isomorphic) to a directed graph. Therefore, all knowledge available
for directed graph analysis can be directly applied to representation
based on this framework. Additionally, the graph theoretical
knowledge can be extended in the framework in order to allow for
results based on advanced aggregation of layers that are present on
the represented models.
Wehmuth & Ziviani Expires December 23, 2017 [Page 2]
Internet-Draft SDN Reference Model June 2017
Since SDN reference models created using the proposed framework are
guaranteed to be equivalent to directed graphs, they can be
represented in their canonical compact form, or by means of matrices
usually employed for graph representation (e.g., adjacency matrices).
Further, well-known graph algorithms can be applied directly to the
representation based on the considered framework, allowing for the
straightforward computing of distances among objects on a SDN system,
the evaluation of the flow capacity of any given path on the system,
the finding of structurally relevant objects or edges in the system
(i.e. centrality evaluation), the construction of flow matrices, or
any other operation possible for directed graphs.
The proposed SDN reference model fully reflects the complexity of SDN
systems, while also allowing the straightforward usage of the model
as a directed graph. Moreover, the fact that the whole network
structure can be represented by a single mathematical object greatly
contributes to the consistency of the obtained results. Therefore,
the proposed framework can be useful either in an offline
environment, where it can be used for system design and simulation of
what-if scenarios, or as an online environment deployed, for
instance, in the SDN controller(s), allowing for real-time evaluation
of the structural properties of the whole system network. The
proposed reference model for representing SDN environments thus
contributes to the management and planning of these environments.
2. Why modeling SDNs as multilayer networks
Since SDNs are intrinsically layered systems, it is natural to model
it as a multilayer network. Moreover, the usage of such a model has
the advantage of clearly exposing the SDN layered structure. In a
multilayer model, not only the natural layers visible on a SDN are
clearly represented, but also, if desired, it is possible to divide
each SDN layer into a set of sub-layers. In this way, structures
such as hierarchical distributed control architectures, where
multiple controllers with distinct hierarchy can be allocated to
distinct control sub-layers. In this manner, not only the
topological structure of the controllers is clearly modeled, but
also, their hierarchical structure. Further, structures that may
sometimes be attached to a SDN system, such as NFVs, can be modeled
in layers specifically reserved for them, making the whole structure
clear.
Moreover, by modeling a SDN as a multilayer network, it becomes
possible to take advantage from the body of knowledge already
established in graph theory for analyzing the SDN structure.
Wehmuth & Ziviani Expires December 23, 2017 [Page 3]
Internet-Draft SDN Reference Model June 2017
3. How to model a SDN as a multilayer network
3.1. Introduction to MultiAspect Graphs
A MultiAspect Graph (MAG) is a graph generalization introduced in
[Wehmuth2016] that is shown to be equivalent to a directed graph. In
this generalization, the set of vertices, layers, time instants, or
any other independent features are considered as an aspect of the
MAG. For instance, a MAG is able to represent multilayer or time-
varying networks, while both concepts can also be combined to
represent a multilayer time-varying network and even other higher-
order networks. Since the MAG structure admits an arbitrary (finite)
number of aspects, it hence introduces a powerful modeling
abstraction for networked complex systems.
3.2. Multilayer graph (MLG) definition
We propose to model SDN systems by using a Multilayer Graph (MLG)
model, that is a particular case of a MultiAspect Graph~(MAG)
[Wehmuth2016], in which the vertices and layers are the key features
(i.e., aspects) to be represented by the model. Formally, a MAG can
be defined as an object H=(A,E), where E is a set of edges and A is a
finite list of sets, each of which is called an aspect. In our case,
for modeling a MLG, we have two aspects, namely vertices and layers,
i.e. |A|=2. For the sake of simplicity, this 2-aspect MAG can be
regarded as representing a MLG with an object H = (V, E, L), where V
is the set of vertices, L is the set of layers, and E is a subset of
(V X L X V X L), that is the set of edges. As a matter of notation,
we denote V(H) as the set of all vertices in H, E(H) the set of all
edges in H, and L(H) the set of all layers in H.
An edge e in E(H) is defined as an ordered quadruple e = (u, la, v,
lb), where u,v in V(H) are the origin and destination vertices, while
la, lb in L(H) are the origin and destination layers, respectively.
Therefore, e = (u, l_a, v, l_b) should be understood as a directed
edge from vertex u at layer la to vertex v at layer lb. If one needs
to represent an undirected edge in the MLG, both (u, l_a, v, l_b) and
(v, l_b, u, l_a) should be in E(H).
An edge e= (u, la, v, lb) in our model may be classified into four
classes depending on its characteristic:
o Intralayer edges connect two vertices in a same layer, e is in the
form of e =(u, la, v, la)$, where u and v are distinct;
o Interlayer edges connect the same vertex in two distinct layers, e
is in the form of e=(u, la, u, lb), where la and lb are distinct;
Wehmuth & Ziviani Expires December 23, 2017 [Page 4]
Internet-Draft SDN Reference Model June 2017
o Mixed edges connect distinct vertices in distinct layers, e is in
the form of e=(u, la, v, lb)$, where u and v are distinct and $la
and lb$ are distinct;
o Intralayer self-loop edges connect the same vertex in the same
layer, e is in the form of e=(u, la, u, la).
Further, we define a composite vertex as an ordered pair (u, la),
where u in V(H)$ and l_a in L(H). The set VL(H) of all composite
vertices in a MLG H is given by the Cartesian product of the set of
vertices and the set of layers, i.e. VL(H) = V(H) X L(H)$. As a
notation note, a composite vertex is represented by the ordered pair
that defines it, e.g. (u, l_a), where u in V(H) and la in L(H).
3.3. Algebraic representations and structures
In this section, we discuss ways to properly represent a MLG using
our proposed model. Similarly to static graphs, a MLG can be fully
represented by an algebraic structure, like the MAG structure from
which our MLG model is derived. In this work, we adopt matrix-based
representations, in particular the adjacency matrix.
In order to illustrate such representations, we use the MLG W
presented in Figure 1.
3.4. MLG adjacency matrix
Since every MAG has a directed graph that is equivalent to it, the
same holds for our MLG model, since it is a particular specialized
case of a MAG. Consequently, it follows that the MLG can be
represented by an adjacency matrix. For the sake of standardization
and without loss of generality, we define that in a MLG the first
aspect represents the vertices (i.e. the objects that compose the SDN
system) and the second aspect represents the layers of the
represented system.
In the more general environment represented by a MAG, a companion
tuple is used in order to properly identify and position each
composite vertex of the equivalent graph in the adjacency matrix.
Since the case we present in this work is restricted to MAGs with 2
aspects, it follows that the companion tuple is reduced to a pair,
which in the first entry has the number of vertices and the second
entry has the number of layers. For instance, considering the MLG
example of Figure 1, the companion tuple associated with its
adjacency matrix is (10,3), since there are 10 vertices and 3 layers.
The function of the companion tuple is only to ensure that the order
by which the composite vertices are placed in the adjacency matrix is
the one shown in Figure 2. Since in the case where the number of
Wehmuth & Ziviani Expires December 23, 2017 [Page 5]
Internet-Draft SDN Reference Model June 2017
aspects is restricted to 2 this placement can be easily achieved, in
this work we do not further mention the companion tuple.
To get the MLG adjacency matrix, we only need to consider that each
composite vertex (u,la) can be thought of as a vertex in a directed
graph. This directed graph has |V| * |L| vertices and, as a
consequence, its adjacency matrix has |V| * |L| * |V| * |L| = |V|^2
* |L|^2 entries. Since the non-zero entries of this matrix
correspond to the edges of the MLG, further analysis show that this
matrix is usually sparse and can therefore be stored in an efficient
way.
+---+ +---+ +---+
| A | | A | | A |
| 1 +-----+ 2 | | 3 |
| | | | | |
+-+-+ +-+-+ +-+-+ Application Layer
......|.........|.........................|.........................
| | |
+----+---------+----+ +--------+---------+
| | | |
| C1 +-----------+ C2 |
| | | |
+-+--+---------+----+ +---+----------+---+
| | | | | Control Layer
.../..|.........|....................|..........|...................
/ | | | | Data Layer
/ +-+-+ +-+-+ +-+-+ +-+-+
| | D | | D | | D | | D |
| | 1 +-----+ 3 | | 4 +------+ 5 |
| | | | | | | | |
| +-+-+ +-+-+ +---+ +---+
| | |
| | |
| | +---+ |
| +--+ D | |
+-------+ 2 +--+
| |
+---+
Figure 1: SDN Example
Figure 2 shows the adjacency matrix obtained for the illustrative MLG
W shown in Figure 1. From Figure 2, we highlight that the adjacency
matrix form of the MLG has interesting structural properties.
Wehmuth & Ziviani Expires December 23, 2017 [Page 6]
Internet-Draft SDN Reference Model June 2017
+- -+
|0 1 1 0 0 0 0 0 0 0|0 0 0 0 0 1 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D1
|1 0 1 0 0 0 0 0 0 0|0 0 0 0 0 1 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D2
|1 1 0 1 0 0 0 0 0 0|0 0 0 0 0 1 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D3
|0 0 1 0 1 0 0 0 0 0|0 0 0 0 0 0 1 0 0 0|0 0 0 0 0 0 0 0 0 0|D4
|0 0 0 1 0 0 0 0 0 0|0 0 0 0 0 0 1 0 0 0|0 0 0 0 0 0 0 0 0 0|D5 Data
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|C1 Layer
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|C2
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|A1
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|A2
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|A3
|...................|...................|...................|
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D1
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D2
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D3
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D4
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D5 Ctrl
|1 1 1 0 0 0 0 0 0 0|0 0 0 0 0 0 1 0 0 0|0 0 0 0 0 0 0 1 1 0|C1 Layer
|0 0 0 1 1 0 0 0 0 0|0 0 0 0 0 1 0 0 0 0|0 0 0 0 0 0 0 0 0 1|C2
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|A1
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|A2
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|A3
|...................|...................|...................|
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D1
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D2
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D3
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D4
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|D5 Apps
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|C1 Layer
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0|C2
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 1 0 0 0 0|0 0 0 0 0 0 0 0 1 0|A1
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 1 0 0 0 0|0 0 0 0 0 0 0 1 0 0|A2
|0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 1 0 0 0|0 0 0 0 0 0 0 0 0 0|A3
+- -+
D D D D D C C A A A D D D D D C C A A A D D D D D C C A A A
1 2 3 4 5 1 2 1 2 3 1 2 3 4 5 1 2 1 2 3 1 2 3 4 5 1 2 1 2 3
Data Control Apps
Layer Layer Layer
Figure 2: SDN Matrix Example
First, each one of the ten vertices (identified as D1, D2, D3, D4,
D5, C1, C2, A1, A2 and A3) of the MLG W clearly appears as a separate
entity in each of the three layers (l0 - Data, l1 - Control, and l2 -
Applications) that compose the MLG W. Second, the main block
diagonal contains the entries corresponding to the intralayer edges
of each layer. In these blocks, the entries corresponding to the
Wehmuth & Ziviani Expires December 23, 2017 [Page 7]
Internet-Draft SDN Reference Model June 2017
intralayer edges of the MLG carry value 1. Finally, the entries at
the off-diagonal blocks correspond to the interlayer edges. The
eight interlayer edges present at the MLG W are indicated by the
value 1 on the off-diagonal blocks. Further, we remark that all
these structural properties derive from the order adopted for
representing the vertices and layers present in the MLG and can be
readily verified in the matrix form in a quite convenient way.
3.5. SDN reference model
From the MLG definition, it follows that a MLG can represent
multilayer networks with an arbitrary (finite) number of layers. At
a first glance, this would be enough to represent a multilayer
system, such as a SDN. However, additional definitions can be made
in order to provide a clear description of a SDN. For instance, a
SDN reference model could benefit from an adequate name structure for
its layers.
We start by naming the four basic layers considered in this work as
Ld for the data layer, Lc for the control layer, La for the
application layer, and Ln for the NFV layer. Further, each basic
layer can be defined in a number of sub-layers, yielding Ld1 to Ldj
for data plain layers, Lc1 to Lck for control plan layers, La1 to Lam
for application layers and Ln1 to Lni for NFV layers. In this way,
the total number of layers in the SDN model is given by |L| = j + k +
m + i. Note that not all layers need to be necessarily represented.
For instance, a simple SDN with 1 data plan layer, 1 control plan
layer, 1 application layer, and no NFV layer, can be modeled by a 3
layer MLG, where j = k = m = 1 and i = 0.
We remark that since a MLG is equivalent to a directed graph, all
extensions usually applied to graphs, such as edge weights and
vertices weights can be directly applied to MLGs, and also, all
algorithms known for directed graphs can be directly applied to MLG.
In addition to the traditional directed graph algorithms, it is
possible to construct algorithms that use the full information
present on the MLG and deliver aggregated results (e.g. results for
vertices; disregarding layers). By using these algorithms, the
results do not consider the artifacts generated by the traditional
aggregation operation. This means, for instance, that aggregated
paths are calculated using only paths that are actually present on
the MLG.
Wehmuth & Ziviani Expires December 23, 2017 [Page 8]
Internet-Draft SDN Reference Model June 2017
4. Conclusion
In this work, we presented a SDN reference model based on MLGs, which
are a special case of a MultiAspect Graph (MAG). In particular, a
MLG is a MAG with exactly 2 aspects, named vertices and layers.
Since the MLG has a fix number of aspects, it can be constructed with
a simpler structure than a MAG.
We show that a MLG can properly represent a SDN system and that since
the MLG inherits the basic properties of a MAG, in particular, the
equivalence (isomorphism) to directed graphs, the knowledge present
in the theory of directed graphs can be applied to our proposed
reference model for representing SDN environments. This makes our
model a convenient way of representing a SDN, by both expressing it
as a multilayer system, while also providing a well established
theoretical ground and available algorithms to build analytics.
5. IANA Considerations
This memo includes no request to IANA.
6. Security Considerations
Similarly to [RFC7426], this document does not propose a new network
architecture or protocol and therefore does not have any impact on
the security of the Internet. However, security in SDN environments
is discussed in the literature, e.g. in [SDNSec], [SDNSecSrv], and
[SDNSecOF].
7. Informative References
[Wehmuth2016]
Wehmuth, K., Fleury, E., and A. Ziviani, "On
MultiAspect graphs", Theoretical Computer Science Vol.
651, pp. 50-61, DOI 10.1016/j.tcs.2016.08.017, October
2016.
[SDNSecOF]
Kloti, R., Kotronis, V., and P. Smith, "OpenFlow: A
Security Analysis", 21st IEEE International Conference
on Network Protocols (ICNP) pp. 1-6, October 2013.
[SDNSecSrv]
Scott-Hayward, S., O'Callaghan, G., and S. Sezer, "SDN
Security: A Survey", In IEEE SDN for Future Networks
and Services (SDN4FNS), pp. 1-7, 2013.
Wehmuth & Ziviani Expires December 23, 2017 [Page 9]
Internet-Draft SDN Reference Model June 2017
[SDNSec]
Kreutz, D., Ramos, F., and P. Verissimo, "Towards
Secure and Dependable Software-Defined Networks", In
Proceedings of the second ACM SIGCOMM workshop on Hot
Topics in Software Defined Networking, pp. 55-60, 2013.
[I-D.irtf-sdnrg-pop]
Tian, Y., "Programming Model for Protocol Oblivious
Forwarding SDN Networks", draft-irtf-sdnrg-pop-00 (work in
progress), January 2017.
[RFC3746] Yang, L., Dantu, R., Anderson, T., and R. Gopal,
"Forwarding and Control Element Separation (ForCES)
Framework", RFC 3746, DOI 10.17487/RFC3746, April 2004,
<http://www.rfc-editor.org/info/rfc3746>.
[RFC7426] Haleplidis, E., Ed., Pentikousis, K., Ed., Denazis, S.,
Hadi Salim, J., Meyer, D., and O. Koufopavlou, "Software-
Defined Networking (SDN): Layers and Architecture
Terminology", RFC 7426, DOI 10.17487/RFC7426, January
2015, <http://www.rfc-editor.org/info/rfc7426>.
Authors' Addresses
Klaus Wehmuth
LNCC
Avenida Getulio Vargas, 333
Petropolis, RJ 25651-075
Brazil
Phone: +55 24 2233-6000
Email: klaus@lncc.br
Artur Ziviani
LNCC
Avenida Getulio Vargas, 333
Petropolis, RJ 25651-075
Brazil
Phone: +55 24 2233-6199
Email: ziviani@lncc.br
Wehmuth & Ziviani Expires December 23, 2017 [Page 10]
