Internet DRAFT - draft-zhao-pce-distributed-sdn-path-computation
draft-zhao-pce-distributed-sdn-path-computation
PCE Working Group J. Zhao
Internet Draft Fudan University
Intended status: Informational Y. Xu
Expires: December 2017 BNC
June 16, 2017
A Distributed Path Computation Model for SDN Controller
draft-zhao-pce-distributed-sdn-path-computation-00
Abstract
Path computation in a large-scale SDN indeed requires a significant
amount of computation load. The SDN controller can easily suffer
from performance degradation resulting from the centralized design
of control plane.
In this document, we argue the necessity in building a distributed
model to speed up the path computation in SDN control plane. With
proper consistency model, path computation can be implemented among
multiple controllers.
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), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
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."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
This Internet-Draft will expire on December 16, 2017.
Zhao et al. Expires December 16, 2017 [Page 1]
Internet-Draft Distributed Path Computation for SDN June 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.
Table of Contents
1. Introduction ................................................ 2
2. Terminology ................................................. 3
3. Synchronization Model ....................................... 3
4. Distributed Path Computation ................................ 4
5. Allocator ................................................... 4
6. Security Considerations...................................... 5
7. IANA Considerations ......................................... 6
8. References .................................................. 6
8.1. Normative References.................................... 6
8.2. Informative References.................................. 6
1. Introduction
The control plane plays a critical role in providing the flexible
functionalities of the SDN network. To this end, the SDN controller
maintains the global network state, including the underlying
topology of switches and the transmission costs of links. With the
global information, the controller can in turn instructs SDN
switches how to forward packets in the data plane. For setting up
each new connection, the controller needs to compute the routing
path according to the destination, which is usually equivalent to
finding a shortest path on a weighted graph.
The performance of many SDN applications, such as traffic
engineering, is tightly related to the quality of path computation.
However, the path computation in a large-scale network indeed
requires a significant amount of computation overhead. Designing an
efficient path computation model would enable high-performance
controller and applications.
Zhao et al. Expires December 16, 2017 [Page 2]
Internet-Draft Distributed Path Computation for SDN June 2017
To improve the control plane performance, state-of-the-art SDN
controllers utilize multiple instances to manage the global
information. A logical centralized controller has the knowledge of
the entire network.
In this document, we seek to scale path computation by leveraging
the multiple controller instances in a distributed SDN control plane.
Distributed path computation needs to synchronize path information
among multiple controllers. We also discuss the synchronization
overhead as well as the involved performance tradeoff.
2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC-2119 [1].
3. Synchronization Model
We consider all-pairs path computation model for an SDN control
plane. Classic solutions for computing the paths between any two
nodes are based on single-source shortest path or all-pairs shortest
paths algorithms. Computing all the paths will spend roughly O(n^3)
time. The high time complexity makes it unpractical for large-scale
networks.
In the distributed controller architecture, each switch belongs only
to one controller at a given time. All controllers together
constitute a logically centralized controller. However, the topology
information may be physically distributed across multiple
controllers.
By leveraging the node parallism, a straightforward approach is to
distribute the path computation load among multiple controllers.
However, maintaining the consistency of topology view across
multiple controllers will be a challenge.
To maintain a network-wide topology view in the distributed
structure, the following network information needs to be exchanged
among controllers:
1. The link status, e.g. the cost of the link.
2. The assignment relation between switches and controllers.
3. The path information in each controller.
Zhao et al. Expires December 16, 2017 [Page 3]
Internet-Draft Distributed Path Computation for SDN June 2017
As described in Figure 1, each controller is in charge of only part
of the switches. Controllers will exchange link status, switch-
controller assignment, and path information between each other to
keep consistency. Otherwise, the inconsistent link status will make
an inconsistent topology view.
+------------------------------------------+
| Controller |
| +-------------------------------+ |
<---+--->| Path information | <---+--->
| +-------------------------------+ |
| |
| +-------------+ +-------------+ |
| | Assignment | | Link status | |
| +-------------+ +-------------+ |
+------------------------------------------+
| | |
| | |
+----------+ +----------+ +----------+
| Switch | | Switch | | Switch |
| #1 | | #2 |... | #n |
+----------+ +----------+ +----------+
Figure 1 Synchronization Model
4. Distributed Path Computation
There are several centralized algorithms to compute the shortest
path. For example, Floyd-Warshall and Dijkstra algorithms have a
O(n^3) time complexity for all-pairs shortest path in a n-node
network. To improve the efficiency, the path computation can be
distributed across multiple controllers. With the exchanged network
information, existing path computation algorithms can be designed to
work asynchronously among multiple controllers. With BSP
synchronization[2], Moore algorithm can be extended to the parallel
scenario.
The efficiency of distributed computing is affected by many factors,
such as the processing power of controller, the link status and the
efficiency of the transmission between controllers.
5. Allocator
An allocator performs switch allocation to a given controller. When
dealing with path computation, the physical topology may change over
time. Therefore switch-controller assignment optimization is
necessary for balancing the path computation overhead. Figure 2
Zhao et al. Expires December 16, 2017 [Page 4]
Internet-Draft Distributed Path Computation for SDN June 2017
describes the re-balance the association of switches to controllers
in order to get a total minimum transmitting overhead. The following
events will trigger the allocator's actions.
1. Adding a new switch.
2. Migrating switches from a failed controller to other controllers.
In the first case, the allocator must allocate the new switch to a
most appropriate controller, which has the minimum current
transmitting overhead. In the second case, the allocator must re-
balance the association of switches to controllers in order to get a
total minimum transmitting overhead.
+--------------+
| Allocator |
+--------------+
/ | \
/ | \
/ | \
/ | \
/ | \
+-----------+ +-----------+ +-----------+
| Controller|<->| Controller|<->| Controller|
| #1 | | #2 | | #n |
+-----------+ +-----------+ +-----------+
Figure 2 Controller Assignment
Suppose a situation that a controller is corrupted and the switches
in this controller have to be migrated into other controllers. The
objective is to minimize the total delay after migrating. This model
is similar to the traditional bin packing problem.
We assume that the transmission happen when a switch has link(s) to
switch(es) controlled by other controller(s). And each time, it
transfers its all information to others. So the transmission delay
of one switch can be calculate by using the total number of links
with other switches controlled by other controllers, the quantity of
data of its all link information and the transmission rate between
controllers. In practice, the problem can be solved using an
heuristic search.
6. Security Considerations
This document discusses a reference model for distributed path
computation. The model itself may have security concerns, such as
Zhao et al. Expires December 16, 2017 [Page 5]
Internet-Draft Distributed Path Computation for SDN June 2017
uncooperative controller nodes. This document does not propose any
protocol and therefore does not have any impact on the security of
the Internet.
7. IANA Considerations
This memo does not have any IANA considerations.
8. References
8.1. Normative References
[1] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
8.2. Informative References
[2] Goudreau, M., Lang, K., Rao, S., Suel, T., and Tsantilas, T.,
"Towards efficiency and portability: Programming with the bsp
model," in Proc. ACM SPAA. ACM, 1996, pp. 1-12.
Zhao et al. Expires December 16, 2017 [Page 6]
Internet-Draft Distributed Path Computation for SDN June 2017
Authors' Addresses
Jin Zhao
Fudan University
825 Zhangheng Rd., Shanghai 201203, China
Email: jzhao@fudan.edu.cn
Yanwei Xu
Shanghai Engineering Research Center for Broadband Networks and
Applications (BNC)
150 Honggu Rd., Shanghai 200336, China
Email: ywxu@bnc.org.cn
Zhao et al. Expires December 16, 2017 [Page 7]
