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]