[Docs] [txt|pdf] [Tracker] [Email] [Nits]

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


   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-

   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

   The list of Internet-Draft Shadow Directories can be accessed at

   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",
   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

   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

   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

   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]

Html markup produced by rfcmarkup 1.122, available from https://tools.ietf.org/tools/rfcmarkup/