ALTO Working Group J. Zhang Internet-Draft Tongji University Intended status: Informational K. Gao Expires: April 21, 2016 Tsinghua University Y. Yang Yale University October 19, 2015 Experiences of Implementing ALTO in OpenDaylight draft-zhang-alto-opendaylight-impl-00 Abstract This text introduces some experiences of implementing ALTO in OpenDaylight (ODL). The main key issues about design and implementation are discussed. Some of these issues have been figured out in the current implementation, the others have not. This text also gives some possible designs to discuss. 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, 2016. Copyright Notice Copyright (c) 2015 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 Zhang, et al. Expires April 21, 2016 [Page 1] Internet-Draft Implementing ALTO in ODL October 2015 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 . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 2. Key Design Issues . . . . . . . . . . . . . . . . . . . . . . 3 3. Design and Implement ECS . . . . . . . . . . . . . . . . . . 4 3.1. Current Solution to Compute the Routing Path . . . . . . 5 3.2. Multi-Path in ECS . . . . . . . . . . . . . . . . . . . . 6 3.3. Reactive Flow Entry . . . . . . . . . . . . . . . . . . . 6 3.4. General Cost Computing Algorithm and the Customized Routing Cost . . . . . . . . . . . . . . . . . . . . . . 7 3.5. Available Bandwidth with Shared Links . . . . . . . . . . 8 3.6. A Comprehensive Architecture . . . . . . . . . . . . . . 8 4. Design and Implement Dynamic Maps . . . . . . . . . . . . . . 9 4.1. Challenges about handling dynamic network . . . . . . . . 9 4.2. Current Solution about Dynamic Network . . . . . . . . . 10 5. Achieve MD-SAL and Cross Platform Design . . . . . . . . . . 11 5.1. Overview of Current ALTO Server in ODL . . . . . . . . . 11 5.2. Implementation of Models . . . . . . . . . . . . . . . . 13 5.3. A Loose Coupling Design to Support the Cross Platform . . 16 6. Discussions . . . . . . . . . . . . . . . . . . . . . . . . . 16 6.1. ECS Extension . . . . . . . . . . . . . . . . . . . . . . 16 6.2. Network State Abstraction . . . . . . . . . . . . . . . . 16 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 8. Security Considerations . . . . . . . . . . . . . . . . . . . 16 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 16 10.1. Informative References . . . . . . . . . . . . . . . . . 16 10.2. Normative References . . . . . . . . . . . . . . . . . . 17 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 17 1. Introduction ODL is one of the most popular Software Defined Networking (SDN) controller. We have implemented an ALTO server in ODL. However, some issues are very important to make the design and implementation of ALTO server. In this document, we present some experiences of implementing ALTO in ODL, and discuss some key issues about the design and implementation. Zhang, et al. Expires April 21, 2016 [Page 2] Internet-Draft Implementing ALTO in ODL October 2015 1.1. Terminology o ECS: Endpoint Cost Service o ODL: OpenDaylight, an implementation of SDN controller o SSE: Server-Sent Event o MD-SAL: Model-Driven Service Abstraction Layer 2. Key Design Issues To implement ALTO in OpenDaylight, we identify a set of design and implementation issues: o T-ALTO-MDSAL: How to use MD-SAL to implement ALTO? The core of OpenDaylight is MD-SAL, which provides mechanisms to describe, store, and access state in ODL data store. To achieve a relatively native design, we should use MD-SAL. At the same time, ALTO has defined its own data types such as Endpoint, PID, Vtag, Network Map, Cost Map. Hence, a first, basic design issue is how to represent the basic ALTO data in ODL data store. o T-CrossPlatform: How to support cross platform? Balancing the preceding consideration, although we focus on implementing ALTO in ODL, we should also consider porting to other SDN controllers such as ONOS. Hence, we target a loose coupling architecture, to achieve an extensible, cross-platform design as much as possible. o T-ECS: How to implement ECS? Going from syntax to semantics, we first consider ECS, which is a basic service in ALTO. One may consider the map services as aggregation services on top of ECS. Hence, a key implementation design is how to compute the cost between two endpoints in ODL. o T-AutoMap: How to allow a network operator (ALTO server administrator) to define automatically generated network maps? One possibility to define a network map is to allow the network operator to upload a static file defining the PIDs of the network map. Although this approach is modular, it is inconvenient. See Section 16 in [RFC7285]. Conceptually, a network map defines a partition of endpoints according to the properties of the endpoints. A mechanism (e.g., a description language) which Zhang, et al. Expires April 21, 2016 [Page 3] Internet-Draft Implementing ALTO in ODL October 2015 allows a network operator to define the grouping conditions and then the ALTO server automatically to compute the partition can provide substantial value. After computing a network map, the ALTO server should also be able to compute the corresponding cost map, for each given cost metric. Since network state can be dynamic, we need to update network maps and cost maps when network state changes. o T-Push: How to push updates to ALTO clients? Client would like to receive update information as soon as possible. See Internet draft [DRAFT-SSE]. 3. Design and Implement ECS There are two key issues when we try to implement ECS in ODL: o How to get an exact forwarding path between two Endpoints. o How to get the cost in different 'cost-type's. We have not yet implemented the functionality of ECS completely because of some challenges. Some of these challenges are caused by the limitation of ODL, but some are not. Developers may face several challenges when implementing ECS in ODL. The following are the main challenges we face: About computing routing path: o Challenge 1: There is no general service to compute the routing path in ODL. o Challenge 2: There will be multiple paths between two Endpoints. o Challenge 3: The routing path may NOT be active when ECS try to look up Forwarding Rules Manager (FRM). About computing cost: o Challenge 4: How to define the 'routingcost'. o Challenge 5: How to get the available bandwidth when there are shared links. In the following several subsections, we will talk about details of these challenges and our solutions. Some challenges have not been Zhang, et al. Expires April 21, 2016 [Page 4] Internet-Draft Implementing ALTO in ODL October 2015 solved, and we discuss the reason and give some proposals in Section 6. 3.1. Current Solution to Compute the Routing Path There are more than one module involved into deciding the routing path in ODL, such as l2switch, BGP, NETCONF and so on. The API of computing the routing path in one module may not work in another module. But there is no general service to compute the routing path in ODL. We have provided a solution to deal with this challenge. This solution includes a basic algorithmic framework and a concrete algorithm about looking up the FRM to compute routing path. The basic framework to compute routing path is presented in Figure 1. if (routingService = getService(Module1) && path = routingService.getPath(src, dst)) { return path; } else if (routingService = getService(Module2) && path = routingService.getPath(src, dst)) { return path; ... } else if (routingService = getService(ModuleN) && path = routingService.getPath(src, dst)) { return path; } else { return lookupFRM(src, dst); } Figure 1: Basic Framework to Compute Routing Path. The ALTO server tries to get the routing path computing service of other modules in ODL at first. If a service exists and ALTO server can get the routing path through this service, the framework just returns this routing path. If not, the ALTO server will call a function to get the routing path by looking up FRM. The algorithm of computing routing path by looking up FRM is presented in Figure 2. Zhang, et al. Expires April 21, 2016 [Page 5] Internet-Draft Implementing ALTO in ODL October 2015 while (currentSwitchId != dstSwitchId) { r <- loopupFlowTable(switchId, srcIp, dstIp); if (!r) { forceComputeRoutingPath(switchId, srcIp, dstIp); r <- loopupFlowTable(switchId, srcIp, dstIp); } currentSwitchId = getNextSwitchId(r); } Figure 2: Algorithm about lookupFRM(). 3.2. Multi-Path in ECS In the actual environment of network, there may be more than one routing path from the source IP to the destination IP. The cost between two Endpoints is decided by the actual routing path, but we may not get the actual routing path from the pair of the source IP and the destination IP. One reason is related to Challenge (3), and the subsection will talk about the details. The other reason is that the ALTO server cannot get enough information from the input of ECS. For example, assume there are two hosts in the network, labeled as H1 and H2. And there are three switches in the links between H1 and H2. The topology is described as Figure 3. When H1 send data to the TCP port 22 of H2, the packet will be forwarded along the path "H1 - S1 - S3 - S2 - H2". But when H1 send HTTP request to H2, the packet will be forwarded along the path "H1 - S1 - S2 - H2". H1 ---- S1 ---- S2 ---- H2 \ / \ / S3 Figure 3: Multi-Path in Network. In this case, the ALTO server will get two paths when looking up FRM to compute the routing path. Since the ALTO server does not know which type of packet will be sent by H1, it cannot decide which path is the actual one. This problem is caused by the limitation of ALTO protocol. An possible solution is proposed in Section 6. 3.3. Reactive Flow Entry There may be some routing paths which are still not active. Only when the special packets are sent to the special destination, will Zhang, et al. Expires April 21, 2016 [Page 6] Internet-Draft Implementing ALTO in ODL October 2015 the rule be called to insert the Flow Table. So we may not get the routing path by looking up FRM. We do not have a good solution to handle it. Although several modules in ODL provide some routing services to compute the path (such as l2switch), we still cannot know which module will be active. And because of the statement in Challenge (1), the ALTO server may get multi-path from different modules, which will also cause Challenge (2). We have tried to extend the input and output format of ECS (see Section 6). But it is not enough to solve Challenge (3). 3.4. General Cost Computing Algorithm and the Customized Routing Cost It is still very hard to define a reasonable function to compute the 'routingcost' now. One possible solution is to support customized functions. Different 'cost-type's have been supported in the current ALTO server: {"cost-mode": "numerical", "cost-metric":"hopcount"} {"cost-mode": "numerical", "cost-metric":"bandwidth"} {"cost-mode": "numerical", "cost-metric":"routingcost"} Figure 4: 'cost-type' supported by ALTO. Following is the algorithm we design to compute 'cost' in different 'cost-metric'. switch (costMetric) { case hopcounts: return the length of shortest path in given multi-paths; case bandwidth: return the maximal bandwidth in given multi-paths; case routingcost: if user provides the routing cost function return the function's result; else return our default function's result; default: return null; } This algorithm is flexible in that it can compute the cost based on the customized cost function from users. But we have not implemented Zhang, et al. Expires April 21, 2016 [Page 7] Internet-Draft Implementing ALTO in ODL October 2015 this algorithm completely. It is because that the ALTO protocol does not define a mechanism for users to provide customized routing cost functions. There are two possible solutions to implement the customization: 1. Extend the request format of ECS. 2. Add new commands in the interface of management. 3.5. Available Bandwidth with Shared Links Some cost metrics requested by clients may be shared by different flows, such as 'bandwidth'. For example, a client sends an ECS request to get the available bandwidths between a list of source IPs and a list of destination IPs. The following example is a very common case: src1 --- s1 s5 --- dst1 \ / s3 --- s4 / \ src2 --- s2 s6 --- dst2 Figure 5: Bandwidth with Links Shared. In the case described in Figure 5, "s3 - s4" is a link shared by all flows between [src1, src2] and [dst1, dst2]. If the client would like to select two pairs from (srci, dsti), their paths must share bandwidth in the link "s3 - s4". So the ALTO server cannot compute the available bandwidth of each flow individually. An possible solution is to divide maximum bandwidth and available bandwidth into different 'cost-mode'. But it is still helpless to compute available bandwidth. Another solution is to introduce Routing State Abstraction (RSA). The details will be discussed in Section 6. 3.6. A Comprehensive Architecture The following is a comprehensive architecture to figure out our design: Zhang, et al. Expires April 21, 2016 [Page 8] Internet-Draft Implementing ALTO in ODL October 2015 HTTP +--------------+ Request----->| | | ECS Service | +-----------+ HTTP <-----| |---->| Routing | Response +------|-------+ | Path | +------|-------+ | Computing | | Cost |<----| Module | | Computing | +-----------+ | Module | +--------------+ Figure 6: A Comprehensive Architecture of ECS. 4. Design and Implement Dynamic Maps The ALTO server should be able to handle dynamic network. For example, when some nodes or links in the network topology change, the ALTO server must regenerate Network Maps and recompute Cost Map. According to our experiences of implementing ALTO in ODL, there may be also several challenges about handling dynamic network. We will indicate these challenges and our solutions below. Some challenges have been solved, and we will introduce our solution. But some challenges still remain to be dealt with. We will also discuss them and the possible solutions in Section 6. 4.1. Challenges about handling dynamic network The key challenges about dealing with dynamic network are indicated below: o How to regenerate Network Maps: Network Maps are dependent on the network topology. The ALTO server should update Network Maps when the topology changes. For example, when a new host H1 is added to the network, the ALTO server should assign a PID for H1 in one Network Map. The challenge is that different Network Maps may have different rules to decide PID, but it is difficult to describe these rules. So it is hard to regenerate Network Maps automatically. o When and How to recompute Cost Map: Every Cost Map depends on one Network Map. When the dependent Network Map is regenerated, the related Cost Map also need to be updated. Generally speaking, the ALTO server should recompute the cost for the PID which is updated. But sometimes, the update of Zhang, et al. Expires April 21, 2016 [Page 9] Internet-Draft Implementing ALTO in ODL October 2015 PID does not effect the cost. The ALTO server should decide when and how to recompute Cost Map. o How to handle updates incrementally and quickly: According to [DRAFT-SSE], the ALTO server may provide a service which allows user to require incremental updates using SSE. But the ALTO server must have the capability to listen, compute and maintain the incremental updates. The challenge is how to provide incremental updates service correctly and efficiently. 4.2. Current Solution about Dynamic Network 4.2.1. Basic Service to Handle Dynamic Network To handle the dynamic network, finding the updates of network is the basic capability. The update about hosts is the most basic type of updates. As the description in Section 5.1.1, the ALTO server introduces a module named 'hosttracker' to find new hosts in the network. For example, once a new host H1 is added to the network, ALTO server will get the address of H1, and record it to the default Network Map. 4.2.2. Solution to Regenerate Network Maps We have not yet had a reasonable solution to regenerate Network Maps. But we provide a management interface to operate Network Maps manually. 4.2.3. Solution to Recompute the Cost Map We have not yet had a reasonable solution to regenerate Cost Map. But we provide a management interface to operate the Cost Map manually. 4.2.4. Solution to Handle Incremental Updates We are implementing ALTO incremental updates using SSE in ODL. The following is a very simple design: Zhang, et al. Expires April 21, 2016 [Page 10] Internet-Draft Implementing ALTO in ODL October 2015 +----------------+ | Update Service | +----------------+ | | Get diff patch | +--------------+ | DAG for Data | +--------------+ | | Maintain | +-------------+ | Data Change | | Listener | +-------------+ Figure 7: A Simple Architecture of the Update Service. The update service is a top module to handle HTTP request from the client. The "DAG for Data" module computes JSON patches and store them to maintain all data changes from listener. 5. Achieve MD-SAL and Cross Platform Design 5.1. Overview of Current ALTO Server in ODL 5.1.1. Architecture ALTO server provides two types of user interfaces -- one for application developers and the other for network managers. The developer interface provides a HTTP server to handle request/response defined in [RFC7285]. And the manager interface is a command-line interface, which provides commands to operate (add/delete/change) the data in data store. Zhang, et al. Expires April 21, 2016 [Page 11] Internet-Draft Implementing ALTO in ODL October 2015 +--------------------------------------+ +-----------+ | ALTO-NorthBound | | Karaf-CLI | Front- +--------------------------------------+ +-----------+ End +--------------------------------------+ +-----------+ | ALTO-Services | | | +..........+---------------------------+ | ALTO- | | | +-------------------------+ | Manager | Back- | Simple- | | ALTO-Provider | | | End | Services | +-------------------------+ | | | | +-------------+ +---------+ | | | | | HostTracker | | Network | | | +----------+ +-------------+ +---------+ +-----------+ +----------------------------------------------------+ | ALTO-Commons | Model +----------------------------------------------------+ +----------------------------------------------------+ | OpenDaylight Data Store: | | +------------+ +---------------+ +---------------+ | | | Maps | | Hosts | | Topology | | Data | +------------+ +---------------+ +---------------+ | +----------------------------------------------------+ Figure 8: ALTO Architecture Overview. As depicted in Figure 8, the services in this server are model- driven, and the foundation of these services is the data store in ODL. The models in this ALTO server define two major things: data types and the interfaces of RPCs (See [DRAFT-ALTO-YANG]. ALTO- Services and ALTO-Provider are the back-end of ALTO-NorthBound. They are the components implementing the basic services in ALTO server. ALTO-Manager is the back-end of the management function in ALTO server. Its implementation is independent on ALTO-Services and ALTO- Provider. 5.1.2. Components The following is an introduction about the main components in this ALTO server. o ALTO-Commons: This component defines the serialization and converter of data types in the ALTO server, such as Network Map, Cost Map, Endpoint and so on. o ALTO-Provider: Zhang, et al. Expires April 21, 2016 [Page 12] Internet-Draft Implementing ALTO in ODL October 2015 This component implements the interfaces of RPCs, which provide necessary services to perform computation with the information of network dynamically. o ALTO-Services: This component has two sections now. The interface section provides all interfaces of ALTO services defined in [RFC7285], which can be called by ALTO-NorthBound. And the implementation section only provides some simple services, which do not need to do any computation. These simple services only read the data from OpenDaylight data store, and convert it to human readable JSON format. o ALTO-NorthBound: This component sets up a web server to handle the HTTP request from users. It will call the functions provided by ALTO-Services. o ALTO-Manager: This is a component which provides the user interfaces for network administrators. In some cases, administrators will want to operate the data in OpenDaylight data store directly. It should be noted that interfaces in this component currently does not support HTTP, you can only access it from command line. 5.2. Implementation of Models Programming in ODL is model-driven since Lithium release. So we should define the data types and RPCs by defining the YANG model. But when we try to use the YANG model defined in [DRAFT-ALTO-YANG] to implement the ALTO server in ODL, several problems occur, making some services not work. In the following, we present the problems about the YANG model and our corresponding solutions. 5.2.1. The definition of 'cost'. Outputs of the Cost Map and ECS both require a data type named 'cost', which stands for the cost between a source and a destination. Section A.1 of [DRAFT-ALTO-YANG] defines 'cost' as following: Zhang, et al. Expires April 21, 2016 [Page 13] Internet-Draft Implementing ALTO in ODL October 2015 grouping alto-cost { anyxml cost { mandatory true; description "ALTO cost is a JSONValue, which could be an object, array, string, etc. (Ref: RFC 7159 Sec.3.)"; } } In this definition, 'cost' is declared as the 'anyxml' statement, which is used to represent an unknown chunk of XML (see [RFC6020]). It is because that 'cost' is defined as a JSONValue in [RFC7285], which could be any valid types in JSON. But when we tried to implement the 'cost' type with its definition in the Lithium Release of ODL, we found that 'anyxml' was not implemented by the YANG parser as we expected. Actually, there are two problems needed to be solved: 1. The Cost Map and ECS need different definitions of 'cost' type to generate different JAVA classes in ODL. 2. 'cost' type could be different built-in types in different Cost Maps or outputs of ECS. For the first problem, the 'augment' statement in YANG model could solve it. For the second problem, however, we cannot use 'anyxml' statement because JAVA is not dynamically typed. In order to support different built-in types, we use 'string' to define 'cost' type. But ALTO server must parse the value of 'cost' by itself. Following is the current YANG model for the 'cost' type: Zhang, et al. Expires April 21, 2016 [Page 14] Internet-Draft Implementing ALTO in ODL October 2015 module alto-cost-default { namespace "urn:opendaylight:alto:costdefault"; prefix "alto-cost-default"; import alto-service {prefix alto-restconf;} augment "/alto-restconf:endpoint-cost-service/alto-restconf: output/alto-restconf:endpoint-cost-service/alto-restconf: endpoint-cost-map/alto-restconf:dst-costs" { leaf cost-default { type string; } } augment "/alto-restconf:resources/alto-restconf:cost-maps /alto-restconf:cost-map/alto-restconf:map/ alto-restconf: dst-costs" { leaf cost-default { type string; } } } 5.2.2. The definition of 'constraint' 'Constraint' is an optional capability in [RFC7285]. The definition provided by [DRAFT-ALTO-YANG] is presented as follows: typedef constraint { type string { pattern "(gt|ge|lt|le|eq) [0-9]+"; } ... } This definition cannot support float 'cost' type. And we give the following definition to replace with it. typedef constraint { type string { pattern "(gt|ge|lt|le|eq) [0-9]*\.?[0-9]+([eE][-+]?[0-9]+)?"; } ... } Zhang, et al. Expires April 21, 2016 [Page 15] Internet-Draft Implementing ALTO in ODL October 2015 5.3. A Loose Coupling Design to Support the Cross Platform The current architecture of the ALTO server couples with the implementation of ODL. A loose coupling architecture design is expected. It will be very helpful to support the cross platform. According to the discussion in Section 3, however, some services cannot decouple with ODL completely, such as ECS. 6. Discussions 6.1. ECS Extension To address some issues in Section 3, we need to extend the data format of ECS. For example, ODL must know the TCP port of the destination to compute the actual routing path. So the client must indicate this information in the JSON of request. 6.2. Network State Abstraction In some cases, the client send an ECS request to get the available bandwidths of some flows, which have shared links. The traditional method cannot give reasonable bandwidths for each flow. A possible solution to solve this issue is to introduce Routing State Abstraction. 7. IANA Considerations This document does not define any new media type or introduce any new IANA consideration. 8. Security Considerations This document does not introduce any privacy or security issue not already present in the ALTO protocol. 9. Acknowledgments The authors thank discussions with Xin (Tony) Wang and reviews by Dan Peng and Qiao Xiang. 10. References 10.1. Informative References Zhang, et al. Expires April 21, 2016 [Page 16] Internet-Draft Implementing ALTO in ODL October 2015 [DRAFT-ALTO-YANG] Shi, X. and Y. Yang, "A YANG Data Model for Base ALTO Data", 2015, . [DRAFT-SSE] Roome, W. and Y. Yang, "ALTO Incremental Updates Using Server-Sent Events (SSE)", 2015, . 10.2. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", March 1997, . [RFC6020] Bjorklund, M., "YANG - A Data Modeling Language for the Network Configuration Protocol (NETCONF)", Oct 2010, . [RFC7285] Alimi, R., Penno, R., Yang, Y., Kiesel, S., Previdi, S., Roome, W., Shalunov, S., and R. Woundy, "Application-Layer Traffic Optimization (ALTO) Protocol", 2014, . Authors' Addresses J. (Jensen) Zhang Tongji University 4800 Cao'an Road Shanghai 201804 China Email: jingxuan.n.zhang@gmail.com Kai Gao Tsinghua University 30 Shuangqinglu Street Beijing 100084 China Email: gaok12@mails.tsinghua.edu.cn Zhang, et al. Expires April 21, 2016 [Page 17] Internet-Draft Implementing ALTO in ODL October 2015 Y. Richard Yang Yale University 51 Prospect St New Haven CT USA Email: yry@cs.yale.edu Zhang, et al. Expires April 21, 2016 [Page 18]