Fluent Essays

In traditional networks, the routers in the core of the network are responsible for two actions: making routing decisions and forwarding packets. The routing algorithms form a distributed consensus of what the shortest path is to any particular IP address (or range of addresses). The output of the routing algorithm populates a forwarding table. This table is used by the forwarding action, which matches the destination IP address from each packet to determine the outbound link for the packet. Software Defined Networks create a programmable interface between these functions and extend the forwarding table to a flow table. In doing so, SDN networks become much more flexible and offer opportunities for research and more efficient traffic engineering. This relatively new field has created widespread network benefits and been adopted in data centers and internet service provider networks. This project will examine the growth and opportunities of SDN. Students will read the original OpenFlow paper to see the ways in which network research have benefitted from SDN. Followon papers from Google demonstrate the usage in data centers and the wide area network  this is main paper The goal is for the m goal is the summary and research of the main paper The goal is for the summary and research of the main paperLarge range is SDN but mainly research on Traffic EngineeringThe courseware I give is all about Traffic EngineeringIt means that I write a large research paper with the team members, the subject is SDN, and I only need to be responsible for the Traffic Engineering part.   https://www.overleaf.com/project/5daa4fd6a4bafe0001fe2738 email: [email protected] password:Lc185846 Agarwal 2018 is my part The rest are from my partner let me know, if u clear how it work. B4 Controller one Is the most suitable You can refer to it I have done the presentation part   It is equivalent to saying that Agarwal 2018 is my part, but I also feel dissatisfied. I want you to write another article So the work should be like the F19 Team SD attached  . Software Defined Networks Yichen Shao, University of California Santa Barbara, [email protected] Zhipeng Hui, [email protected] Sijie Zhang, Xiamen University, [email protected] Zongze Li, Cascadia Community College, [email protected] Tongyu Chen, Hangzhou Foreign Language School, [email protected] Abstract—This should be a very short overview of your entire paper. The reader should be able to figure out from the abstract if he/she wants to read the rest or not. I. INTRODUCTION A quick introduction to the idea of SDN and the differences with a conventionally managed network. II. BACKGROUND An overview of the SDN ideas. You should probabl specifi- cation. List important features of SDN that won’t be discussed in the rest of this paper, giving a paragraph or so of description of each. You might want to make subsections for each, in which case, follow this example. Make sure this section doesn’t overlap with McKeown, which has lots of the basic ideas of SDN. A. SDN for Blockchain Some text about this idea. Obviously, this is an example. You don’t need to write about the Blockchain unless you think it important. III. THE RISE OF SDN 1. Introduction Networks have been developed over decades. And it is both a blessing and a curse for networking researchers because that there is almost no practical way to experiment with some new network protocols in the real traffic. However, the OpenFlow surprised us with a whole new concept of a programmable networks model in campus networks.[1] Researchers discovered that most modern Ethernet switches and routers contain flow-tables which have a common set of functions running in the flow-tables of switches and routers. Exploiting the common set of functions in flow-tables, OpenFlow introduces a new protocal to program the flow- table and makes it possible to programs in different switches and routers. 2. Basic Model The basic model of OpenFlow Switches contain three parts: 1) A flow-table (a flow could be defined as all packets matching a specific header) 2) A Secure Channel that connects the switch to a remote control process(controller) 3) The OpenFlow Protocol that provides a way for a controller to communicate with a switch. An entry in the Flow-Table has three fields: 1) A packet header that defines the flow, 2) The action that defines how the packets should be processed, 3) Statistics that keep track of the number of packets and bytes for each flow. And each flow-entry has a simple action associated with it. There are three basic actions for ”Type 0” OpenFlow Switches: 1) Forward this flow’s packets to a given port which allows packets to be routed through the network. 2) Encapsulate and forward this flow’s packets to a controller. Packet is delivered to Secure Channel. Typically used for the first packet in a new flow, so a controller can decide if the flow should be added to the Flow Table. 3) Drop this flow’s packets. Typically used for security to curb denial of service attacks, or to reduce spurious broadcast discovery traffic from end- hosts. 4) Forward this flow’s packets through the switch’s normal processing pipeline. However, the model of OpenFlow Switches is not limited as ”type 0”. When a particular set of features emerges, such as rewrite portions of the packet header, match on arbitrary fields in the packet header to enable experiments with new non-IP protocols, we can also define a ”Type 1” switch. A controller in the Secure Channel adds and removes flow-entries from the Flow Table on behalf of experiments. A controller could also be more sophisticated that dynamically add/remove flows as an experiments progresses. Here could be a new topic of using neutral network to enable the functionality of dynamically adding and removing flow- entries. On the other hand, the restrictions could also be imposed with appropriate use of permissions or other ways to limit the powers of individual researchers to control flow entries. The exact nature of these permission-like mechanisms will depend on how the controller is implemented and the aim of research. 3. Conclusion and Concerns The model of OpenFlow in campus network is just a prototype which aims to achieve the goals: 1) Amenable to high-performance and low-cost implementations. 2) Capable of supporting a broad range of research. 3) Assured to isolate experimental traffic from production traffic. The first goal could be achieved by the OpenFlow Switches. The second aim could be achieved by the implementation of the controller. And the third goal could be achieved by the Secure Channel as a whole. However, I do think the paper lacks of the discussion of the OpenFlow Switches and security problems. As the OpenFlow Switch contains two parts: software and hardware. That implies that the switch should contain the application layer which is different from normal switches. That could lead to multiple problems. Moreover, as the paper states that a researcher might control the complete network of OpenFlow Switches and be free to decide how flows are processed. That could lead to some serious security problems as there’s no super user of the entire network. IV. GOOGLE’S DEPLOYMENT OF SDN WAN ARCHITECTURE Abstract Google deployed B4, a global Software Defined WAN, to connect Google’s data center in 2013. This paper discusses how B4 improves the network mechanism and how Google establishes the architecture of Software Defined Network globally. Comparing to the traditional WAN architecture, B4 define the priority of the applications which enables B4 to drive the link utilization to nearly 100% and has control over the edges servers and the network. Google’s Software Defined WAN architecture is mainly defined in three layers which consist of global layer, site controllers , and switch hardware layer. Furthermore, Google uses centralized Traffic Engineering (TE) in TE server as its new SDN application to control the network resources according to priority and allocate paths for data in transmission. Keywords: Centralized Traffic Engineering; Wide-Area Networks; Software Defined Networking; Routing 1. Introduction The Google company operates on two distinct WANS (wide area networks). The first one is user-facing networks for end users to deliver their requests and responses to Google’s data centers. The second one is the protagonist, B4, in this paper. B4 is used to connect data centers. The birth of B4 helps the network companies to save money on internet equipment. The traditional WAN architecture considers all the applications equally. In other words, it treats all bits equally no matter whether or not they deserve. As we all know, the packet loss is inevitable in data transmission because a queue preceding link only has finite capacity. Once it is full, it will drop the new coming packet. At that moment, the packet loss occurs. In order to prevent the users sensing the packet loss, network companies have to buy lots of high-end routing gears to increase the bandwidth. With the help of large bandwidth, even though the packet loss occurs, the network still has spare bandwidth to do the retransmission quickly. However, the shortcoming is obvious that the average utilization is only 30 ∼ 40%. The waste of network resources and expensive equipment leads to the deployment of B4. 2. Design Decisions 2.1 Separate hardware from software The core idea of SDN is to separate hardware from software. Let the hardware to do the simplest job and let the software to be the leader. Hence, the protocols on software have rapid iteration without the limitation or revision of the hardware. 2.2 Drive links to 100% utilization In order to achieve 100% utilization of the network, Google categorizes thousands of applications which run on B4 and define them in different levels and different priority. These triple traffic classes are ordered in increasing volume, decreasing latency sensitivity and decreasing overall priority. The top of the pyramid is user data copies, such as email, documents, and video files because users’ satisfaction is significant. The users care about the latency and availability most. Their satisfaction is significant. These things have lowest volume in general. The second one is remote storage access such as fragmenting data and put them in different data centers or doing the computation on distributed servers. The last one is synchronization. Like if doing the computation on lots of servers in different data centers, servers need to interact with each other and know the states on the other servers. The idea here is to fulfill the demand of the highest priority mission. And the rest of bandwidth is filled by other missions which are not urgent. The shortcoming is that packet loss becomes inevitable, or we can say it is more obvious to the servers. As mentioned before, the traditional routing treats all bits same, so everyone has packet loss. However, large bandwidth hides it and make users or servers cannot sense it. Network has free bandwidth to do the retransmission. Even though, suddenly large bandwidth is needed, we can afford it. However, when the utilization reaches nearly 100%, there is no free bandwidth to hide packet loss. Especially the applications with lower priority. Because the bandwidth is mostly used by higher priority application. Once the link failures happen, there is no free bandwidth and packet loss cannot be fixed in short time. Controllers have to allocate the bandwidth dynamically and robs the bandwidth from higher priority applications. It needs time, at this time, the servers or end users will sense it. 2.3 Centralized Traffic Engineering The first SDN application is called TE, the traffic engineering. It mainly has three missions. The network resources are constrained, it controls the resources at the edge to decide who gets the resources. According to priority, use multipath tunneling to leverage network capacity. Dynamically reallocate bandwidth when link failures or shifting application demands occur. (needs more information to fulfill it, just put aside for a while) 2.4 B4 routers The third decision is B4 routers build from merchant switch silicon. Google chooses not to invent new instruments but based on merchant’s existing switches. There are thousands of hardware and it is impossible to unify all of them in a new language. On the other hand, the traditional view is that the router must have great buffer capacity. The larger buffer means larger forwarding tables. Forwarding table maps addresses to outgoing link. However, this increases the complexity and cost of hardware. Hence, Google invents its own routers and switches which based on the merchant silicon. The central idea is to have smaller forwarding tables, stronger switches, and fewer data centers. 3 Three-layers Software Defined Network WAN architecture 3.1 Bottom layer: Switch hardware layer The bottom layer is switch hardware. It only forwards the traffic and has nothing to do with any complicated things, just like ergates who follow the queen ant’s orders and do the hardest job. Here, we can see the OFA, OpenFlow Agent. It’s a translator and supervisor. Its job is to translate the raw data, the status of the switch, into something OpenFlow controller can understand. Just like which ant is sick or busy. 3.2 Middle layer: Site controllers The middle layer is site controllers which hold OpenFlow controllers. Its mission is to decide how to forward the traffic according to switch hardware’s status. They are leaders of the departments in the company and give orders to workers. Now, OFC understands the working status. So, it communicates with Quagga by RAP. RAP is a bridge between them. The Quagga is three layers protocol stack. It contains all of the information about the sites, the paths, the ports. Then, the Quagga provides things back to OFC and OFC upload all of these information to TE agent. TE agent uploads to Gateway. 3.3 Top layer: Global layer The top layer is central traffic engineering server which logically controls the entire network. The Gateway is a secretary. It translates the topology, the raw data into something TE can understand and gives these data to central TE server. The TE server is CEO and does the calculations, like which application go which path. The following part is easy. CEO’s decision goes back to OFC and writes in switches. Now, switches know what to do. V. PROMISES AND LIMITATIONS OF SDN The concept of SDN was introduced about ten years ago. Representative work includes the previous two paper- OpenFlow and Google B4-and many other researches done on the structure design and model presentation of SDN. For a while, the public had much expectation on this emerging concept. Seeing that SDN has many seemingly attractive advantages, such as centralization and programmability, the business market and media hyped it up, praising it as an ideal structure. However, SDN is not as a perfect network as it seems to be. When in practical use, it in fact do not achieved its promises. White et al. gave a detailed analysis on the three promises and characteristics of SDN-centralization, flow control and programmability-and proposed the drawback and limitations of SDN in their research paper.[2] 1 Centralization 1.1 Centralization Structure One of the biggest differences between SDN and traditional network is the main structure. Traditional network, such as IS-IS and BGP, uses distributed control planes. The whole network consists of many network nodes, each of which includes a control plane and a data plane. The control plane is responsible for managing the node’s operations, and communicates with neighbor nodes. Each node can decide their own settings, which is to say it is configured individually. The drawback of traditional network is its distribution. Because the configurations of nodes are totally different, the network operator has to store the information for every node, and manage complex policies between them. The huge amount of information storage then leads to the adoption of large and expensive devices. By contrast, SDN uses a centralized structure to eliminate the complexity of traditional network. The core component of SDN is the controller. It works as a network operating system, which receives requirements from network applications, calculate the forwarding path according to a set of rules, and send the forwarding command to forwarding devices. Because there are no individual configurations for nodes, and only the controller, but no routers, takes charge of the topology and calculation process, it is easier for the network operator to manage information, and forwarding devices can be cheaper and lighter than the traditional ones. However, complexity still exists in this situation. In reality, in case the controller is crushed, and also to ensure the SDN service can have global coverage, there has to be multiple controllers to run simultaneously. Therefore, the problem lies in how to deal with their relationship. This topic will be discussed in 1.4. 1.2 Reactive Forwarding Traditional network takes a proactive method in the forwarding procedure. That is to say, the forwarding path will be determined before the first packet is transmitted in the network. This method is accomplished by information aggregation of the routers in the network. They hold the accurate information of their neighbors through the process of flooding, processing and managing, and thus can decide the correct path. However, for an SDN network, it takes a reactive plan. Forwarding devices can only know reachability information when it receives the first packet. This is because for the controller, due to the large scale and complication of the network it takes control, it does not store all the forwarding information. Therefore, it adopts some protocols and policies to decide possible paths as the forwarding paths of the first packet. If the packet arrives at a forwarding device successfully, the device will feedback this reachability information to the controller. The issue of reactive forwarding is that, before the forwarding devices receives the first packet and send the information back, the controller does not know the reachability of paths, which causes a disconnection to the real situation. For the same reason, there will be a lag between the first packet beginning to be transmitted and the path to be determined. 1.3 Reaction to Changes For a traditional network, when the state of a node changes, other nodes in the network receives the change information from its neighbor, and send it out to other neighboring nodes until all the nodes are aware of the change, and then new path will be calculated. Therefore, the reaction time is mainly spent on routers spreading messages and recalculation. When a local node changes or fails in SDN, first the message will be transmitted to the controller. The controller will then calculate and decide a new path, and transmit new forwarding rules to related nodes. Although the recalculation is much faster for a controller since it has limited information for nodes, still the spreading of new rules to the forwarding devices in the network is a slow process. Therefore, the reaction time for SDN is no faster than traditional network. 1.4 Reality of Centralization Centralization, one of SDN’s big promises, seems to be a very appealing advantage. Frustrated by complicated traditional distributed network, SDN’s method of centralizing control module will make management a lot easier. Totally physically centralized, however, is impossible in the real world. Firstly, to ensure reliability, there should be multiple controllers working together, while each of them gets a slice of workload. Secondly, to ensure scalability, controllers should be separated to different regions, with each region handled by an SDN system. As a result, SDN still deal with the whole network in distributed systems, which is inconsistent with its promise to be centralized, and the biggest problem emerges: how do different controllers communicate and exchange information? To make the SDN system uniform, we have to decide the format and new protocols applied between controllers. 2 Flow-based Network The forwarding of SDN is flow-based rather than the destination-based method of traditional network. It aims to assign different paths in the network for individual applications to ensure that files with special requirements are transmitted efficiently. Flow-based forwarding enables more flexible and individual transmission, but it has significant disadvantages. Firstly, it produces too much connections. For traditional network, since it is only addresses but not files that matter, only one TCP connection is needed between the source and destination, and all files are forwarded through it. However, for SDN, due to the different paths that different files take, it has to set up a TCP connection for each flow. The setup rate will also be slower because the format of the flow should be stored. Secondly, to store the huge amount of connection information, hardware cost will be quite high. Also, there will be more cost for each forwarding devices to examine the headers of flows to ensure they are in correct format and path. 3 Programmability The most appealing part of SDN which attracts the business market is that it promises to be open and programmable. This feature did hold true in the beginning stage, providing a clean and flexible platform for users to develop their own functionalities. However, as SDN become more and more widely covered, eventually venders dominated the market, and they compete with each other. In order to make themselves stand out, venders develop new models continuously, along with new hardware and software requirements. Meanwhile, they prefer to make their product vertically integrated, which means they tends to develop the whole functionality from application interfaces, to controllers, and finally down to forwarding devices in order to make more profit. As a result, the configurations of SDN is likely to be diverse because of different venders, and is no longer uniform as people expect it to be. And on the other hand, venders are reluctant to disclose their programs, which has led to the development of SDN models being closed within these venders, and thus is not programmable as it was originally guaranteed. In conclusion, the concept of SDN appeared bright when it was first proposed, but as it developed, the problems of its characteristics were also exposed. The three main features- centralization, flow control and programmability-are either flawed or invalid in the long run. Therefore, just as the author said, we should not view SDN as an ideal goal to reach. Instead, it is just a tool or a method that needs to be improved. VI. AGARWAL2018 “Traffic Engineering in Software Defined Networking.” it has come to be a flexible network that offers opportunities to the research activities and more well-organized traffic engineering. SDN has two main components, that is, SDN Controller (SDN-C) SDN Forwarding Element (SDN-FE). SDN Controller (SDN-C): The controller is a rationally central purpose. A net is characteristically skillful by one or a few supervisors. The supervisors control the advancing trail for apiece movement in the system. SDN Forwarding Element (SDN-FE): The SDN-FEs establish the net information flat. The reason for advancing the packs is strongminded by the SDN organizer and is applied in the advancing table at the SDN-FE. The traffic engineering’s main objective is Developing a Software-Defined Networking (SDN) placement arrangement, which dynamically and adaptively achieves circulation in a network to house diverse circulation designs. The main contri- bution includes: Addresses Network performance issues in an SDN placed incrementally, formulation of SDN supervisor’s question of optimization and list FPTAS to compute the problem of controllers, SDN examination with simulations improvements that are considerable in loss and delay perfor- mance in a low SDN amounts elements positioned in a net, and outlining the algorithm for placement of forwarding elements determination. The functions of SDN-FE include: 1. Forwarding – SDN works as a forwarding element. It is assumed that SDN-Fes can handle several hops that precede for a specific destination. If there are several preceding hops, the SDN-FEs can divide traffic to the terminus in a manner that is pre-specified across several preceding trips. 2. Measurement – The routing table has been modified a little, compared to other routing tables, to aid analysis at SDN-Fes. When SDN-FE handles a packet, it makes a long prefix match on the IP address it goes to for the determination of the previous hop. 3. Peering – SDN- C has routing logic and is coordinated with the routing of SDN-Fes so that excellent network performance is enhanced. The controller knows the actual weights of OSPF and the traffic flow amount on every link. 4. Route Computation – The controller computes the routing table for SDN-Fes in a network. Route computation computes the routing tables while considering the routing conducted by non-SDN-Fes, traffic at the link, and current traffic pattern. About Formulation of the SDN-C’s Problem objective of the SDN-C is to route the controllable traffic such that delay and packet loss at the links are minimized. Software-Defined Networking (SDN) is a new-fangled inter- acting model that differentiates network regulator flat from the pack advancing flat and delivers requests with an inattentive central opinion of the dispersed of the network state. Software -Defined Networks provides for flexibility, efficiency, and ease in functionality. Google has even decided to make use of SDN, showing that it is a good network option in the market today considering the status of the Google Company. VII. LANGUAGES FOR SOFTWARE-DEFINED NETWORKS Because managing networks in tasks such as routing and traffic monitoring is unnecessarily complicated and error-prone. SDN are poised to change this by offering an interface between networking devices and the software that controls them. Although SDN makes it possible to program the network, it is still inefficient. The three designing of simple abstractions for network management in order to reach SDN’s full potential are: (i) monitoring network traffic, (ii) specifying and composing packet-forwarding policies, and (iii) updating policies in a consistent way. Before, on each device, network operators must config- ure every protocol. However, the growing interests in SDNs nowadays promote a logically-centralized controller manages a distributed collection of switches. SDNs make it possible for programmers to control the behavior of the network directly, by configuring the packet- forwarding rules installed on each switch. Some may regard this as a centralized control, though, for a higher scalability and fault tolerance, the controller is replicated and distributed. SDNs can simplify applications and build up platforms for developing new applications. Conserving energy: Controllers selectively shut down links or even whole switches after directing traffic along other paths. Balancing the load between servers: The controller can split flows over several server replicas and migrate flows to new paths in response to congestion. As a matter of fact, for today’s SDN controller, platforms for writing applications remain in low-level distributed pro- gramming. 1.1 FRENETIC As a replacement to the low-level imperative interfaces, Frenetic offers abstractions for querying network state, defining forwarding policies, and updating policies. II. QUERYING NETWORK STATE This is made possible in part by the underlying run-time system, which follows OpenFlow rules. Frenetic demonstrate three ways of the “control loop” for running a network. The first is Querying network state: a high-level query language including traffic statistics and topology changes. 2.1 A. Query Language Design Considerations Many monitor applications classify traffic using packet headers. Instance: if the programmers want all web server traffic excluding the host with IP source address 1.2.3.4. There are two rules— the upper matches packets from 1.2.3.4 with TCP source port 80, the lower is associate with all remaining traffic. Frenetic specify predicates like “srcip!=1.2.3.4 srcport=80,”. Dynamic unfolding: The usage of efficient hardware, and the counters remain the information needed to implement. Limiting traffic: Sending the first packet to the controller, and install rules for dealing future packets. Polling and combining statistics: The run-time system queries the traffic counters, returning results to the application. 2.2 B. Example Frenetic Queries MAC learning and Traffic histogram: An Ethernet switch performs to identify what interface to use to reach a host. Select(packets) * GroupBy([srcmac]) * SplitWhen([inport]) * Limit(1) The result is a stream of packets to the ingress port. Frenetic’s language gives the programmer a sense of the cost of a query. The run-time system directs all packets to the controller, but gradually installs packet-forwarding rules after the first packet for the MAC-learning query. III. COMPOSING NETWORK POLICIES Reconfiguring the network: This is a way without having to manually install, actually allows programmers to reconfigure the network. The run-time system ensures that during an update, all packets (or flows) are processed with the old policy or the new policy, and never a mixture of the two. This guarantee ensures that functional invariants are never seperated and broken during periods of policies’ transition. 3.1 A. Creating Modular Programs A. Creating Modular Programs This is a method that consid- ering a program which blend in repeater functionality with web-traffic monitoring functionality. In comparison to Python program, Frenetic makes it easier for programmers to write and compose independent modules. def repeater(): rules=[Rule(inport:1, [fwd(2)]), Rule(inport:2, [fwd(1)])] register(rules) def web monitor(): q = (Select(bytes) * Where(inport=2 srcport=80) * Every(30)) q ¿¿ Print() def main(): repeater() monitor() The main function assembles components into a program. Eas- ily swapping out the given network monitor without touching repeater code or change the forwarding logic . 3.2 B. Efficient Run-Time System The flow table of switch is empty at the very beginning, so every packet is sent to the controller.When receiving a packet, the run-time system traverses the registered forwarding policies collecting a list of actions for that switch. The run- time system has the ability to refine the rules based on the actual traffic, supporting policies with arbitrary functions that the switches cannot implement. The run-time system can customize rules to make the switch more portable. According to the newest versions of the OpenFlow provide, an interface to the tables in modern hardware. In the future tasks, programmers plan to extend run-time system to represent sophisticated policies. IV. CONSISTENT UPDATES Programs need to transfer from one policy to another and changes in network load. As we have designed high-level network that traffic will be processed consistently, the update operations provides useful guarantees about network behavior during transitions. 4.1 A. Per-Packet Consistent Updates ”Guarantees that every packet flowing through the network is processed with exactly … 1 Traffic Engineering in Software Defined Networks Sugam Agarwal 1 Murali Kodialam T. V. Lakshman Bell Labs,Alcatel-Lucent Holmdel, NJ, USA {muralik, [email protected]} Abstract—Software Defined Networking is a new networking paradigm that separates the network control plane from the packet forwarding plane and provides applications with an abstracted centralized view of the distributed network state. A logically centralized controller that has a global network view is responsible for all the control decisions and it communicates with the network-wide distributed forwarding elements via stan- dardized interfaces. Google recently announced [5] that it is using a Software Defined Network (SDN) to interconnect its data centers due to the ease, efficiency and flexibility in performing traffic engineering functions. It expects the SDN architecture to result in better network capacity utilization and improved delay and loss performance. The contribution of this paper is on the effective use of SDNs for traffic engineering especially when SDNs are incrementally introduced into an existing network. In particular, we show how to leverage the centralized controller to get significant improvements in network utilization as well as to reduce packet losses and delays. We show that these improvements are possible even in cases where there is only a partial deployment of SDN capability in a network. We formulate the SDN controller’s optimization problem for traffic engineering with partial deployment and develop fast Fully Polynomial Time Approximation Schemes (FPTAS) for solving these problems. We show, by both analysis and ns-2 simulations, the performance gains that are achievable using these algorithms even with an incrementally deployed SDN. I. INTRODUCTION Software Defined Networking (SDN) is a new networking paradigm [1], [13], [14] that separates the control and forward- ing planes in a network. This functional separation and the im- plementation of control plane functions on separate centralized platforms has been of much research interest due to various expected operational benefits. Separating interdomain routing from individual routers and using a logically centralized Rout- ing Control System was proposed in [2], [4] as a means to make routing systems more manageable, less complex and be accommodative of new service needs. The SoftRouter architecture [12] proposed the disaggregation of routers into packet forwarding elements, with open standardized interfaces, that are controlled by centralized control plane servers. This was proposed as a means for quicker introduction of network functions such as traffic engineering, new VPN features, etc. and also to achieve various other cost, operational benefits. Re- architecting the control plane into a dissemination plane and a decision plane was proposed in [10]. The disseminaton plane reliably disributes information to the network elements and the decision plane makes all decisons that affect the network. 1 Work done while at Bell Labs This re-architecture makes it easier for the decision plane to have a global view of network state and permits operators to express desired network behavior more easily. Common to all the above approaches is that an SDN comprises of two main components: • SDN Controller (SDN-C): The controller is a logically centralized function [3], [8]. A network is typically controlled by one or a few controllers. The controllers determines the forwarding path for each flow in the network. • SDN Forwarding Element (SDN-FE): The SDN-FEs constitute the network data plane. The logic for forward- ing the packets is determined by the SDN controller and is implemented in the forwarding table at the SDN-FE. Openflow [14] is a standardized interface that can be used by the controller to communicate with the forwarding element. When a flow is initiated in the network the following actions are taken: (i) The first packet of the flow is sent by the SDN- FE to the SDN controller, (ii) The forwarding path for the flow is computed by the SDN controller (SDN-C), (iii) The SDN-C sends the appropriate entries to install in the forwarding tables at each SDN-FE on the path from the source to the destination, (iv) All subsequent packets in the flow are forwarded in the data plane and do not need any control plane action. The SDN controller is responsible for path selection and therefore all policy information resides at the controller. It is also possible to implement centralized or partially central- ized traffic management function at the SDN controller. For instance, Google has built a SDN with Openflow routers to interconnect its data centers (G-Scale) [5]. Google is expecting an improvement in network utilization of 20-30% as well as improved delay and loss performance [5] as a result of using an SDN. The traffic engineering problem that we consider is moti- vated by scenarios where SDNs are incrementally deployed in an existing network. In such a network, not all the traffic is controlled by a single SDN controller. There may be multiple controllers for different parts of the network and also some parts of the network may use existing network routing. The key question then is whether it is still possible to do effective traffic engineering when all the traffic in the network cannot be controlled centrally by a single SDN controller. In this paper, we consider traffic engineering in the case where a SDN controller controls only a few SDN forwarding elements in the network. The rest of the network does hop- by-hop routing using a standard routing protocol like OSPF. 978-1-4673-5946-7/13/$31.00 ©2013 IEEE 2013 Proceedings IEEE INFOCOM 2211 2 The objective of the paper is to develop a SDN deployment scheme that can adaptively and dynamically manage traffic in a network to accommodate different traffic patterns. Our main contributions in this paper are the following: • To our knowledge, this is the first paper to address network performance issues in an incrementally deployed SDN. • We formulate the SDN controller’s optimization problem and outline a Fully Polynomial Time Approximation Scheme (FPTAS) to solve the controllers problem. • We show by analysis and simulatons the considerable gains in delay and loss performance even when a limited number of SDN forwarding elements are deployed in the network. • Given a fixed number of SDN-FEs we outline an algo- rithm for determining the placement of these forwarding elements. Due to space limitations, we do not show extensions to the approach in this paper to the problem where the network is partitioned between multiple SDN controllers. II. SYSTEM DESCRIPTION We consider a network where a centralized SDN controller computes the forwarding table for a set of SDN forwarding elements. We assume that the SDN forwarding elements are a subset of the nodes in the network. The rest of the nodes in the network run some standard hop-by-hop routing protocol like OSPF. We assume that the SDN-C peers with the network and gathers link-state information. The SDN-FEs forward packets and the logic for computing the routing table at the SDN-FEs resides at the centralized SDN -C. In addition to forwarding packets, the SDN-FEs do some simple traffic measurement which they forward to the controller. The controller uses this traffic information along with information disseminated in the network by OSPF-TE to dynamically change the routing tables at the SDN-FEs in order to adapt to changing traffic conditions. The controller also exploits the fact that it can make co-ordinated changes across the different SDN-FEs that it controls to manage changing traffic effectively. The regular nodes in the network, also referred to as the non-SDN-FEs, are standard routers using the usual hop-by-hop forwarding mechanism. This hybrid network scenario with traditional networks intermixed with SDNs is also considered in [11]. Our objectives are considerably different from the objectives in [11]. We assume that no changes are made to the non-SDN- FEs and in fact they can be unaware of the existence of the SDN-FEs in the network. An example of a network with SDN-FEs and controller is shown in Figure 1. SDN-FEs 2, 9, 14 are controlled externally. We will use this network to illustrate some of the concepts that we outline in the rest of the paper. We assume that all the links in the network are bidirectional and all link weights are set to one. We now describe the SDN-FEs and the SDN-C in some more detail. The description is at a fairly high level especially for the SDN-C. The actual algorithm that are run at the controller is outlined in Section 3. Controller Flex Node Flex Node Flex Node 1 2 4 8 10 6 5 13 14 12 15 11 9 7 3 Fig. 1. SDN-FEs and SDN Controller A. SDN Forwarding Element The SDN-FEs perform the following functions: Forwarding: The SDN-FEs act basically as forwarding ele- ments. The routing table at the SDN-FEs is however computed by the SDN-C. We assume that the SDN-FEs can handle multiple next hops for a given destination. If there are multiple next hops for a given destination, then the SDN-FEs can split traffic to the destination in a pre-specified manner across the multiple next hops. It is relatively easy for the controller to compute multiple next hops and load the routing table to the SDN-FEs [12]. There are several ways of splitting traffic on multiple next hops [15] while ensuring that a given flow is not split across multiple next hops. Some of these approaches need extra measurements and it is relatively easy to extend the current approach to obtain the extra information. Therefore in the rest of the paper, we assume the the SDN-FEs can split traffic across multiple next hops for a given destination. We also assume that the SDN-FEs can perform traffic measurements using techniques such as those in [15]. Measurement: The routing table at the SDN-FEs is modified slightly, compared to a standard routing table, in order to aid traffic measurement at the SDN-FEs. A schematic representa- tion showing the difference between a standard routing table and the routing table at the SDN-FEs is shown in Figure 2. Note that there is an extra column for the node in the network that can reach the destination IP address. When a packet is processed by the SDN-FE it does a longest prefix match on the destination IP address to determine the next hop. It also increments a counter corresponding to the destination node by the packet length. This is done in order to determine the amount of traffic between the SDN-FE and all other nodes in the network. Consider the routing table at node 2. Assume that node 15(IP address 45.67.2.5) announces reachability to the subnet 135.23\16. Let node 11 with interface IP address 43.2.34.7, be the next hop on the shortest path from node 2 to node 15. A portion of the routing table at node 2 is shown in Figure 2. The column corresponding to the traffic tracks the number of bytes routed from node 2 to node 15 for the destination prefix 135.23\16. It is easy for the SDN-FE to also compute the total traffic sent from node 2 to node 15. 2013 Proceedings IEEE INFOCOM 2212 3 Hop Next Traffic 135.23/16 Prefix Node 45.67.2.5 43.2.34.7 Fig. 2. Enhanced Routing Table at the SDN-FE B. SDN Controller The SDN-C has all the routing logic and it coordinates the routing of all the SDN-FEs in order to achieve good network performance. The controller does the following functions: Peering: The SDN-C peers with the other nodes in the net- work exchanging link weights and other topology information using OSPF-TE. ( See [9] for an example.) Note that in OSPF- TE, the nodes also exchange available bandwidth information on the links in the network. Therefore the controller knows the current OSPF weights as well as the amount of traffic flow on each link (averaged over some time period). Route Computation: The controller is responsible for com- puting the routing table for all the SDN-FEs in the network. It computes these routing tables taking into consideration the routing done by non-SDN-FEs (based on OSPF link weights), the traffic at the links (derived from OSPF-TE information or) and the current traffic pattern (inferred from the measurements at the SDN-FEs). The algorithm for computing the routing table for the SDN-FEs has to ensure that routing will be along loop-free paths while minimizing the congestion in the network. We will describe the SDN controller’s problem formulation and solution technique in Sections 3 and 4. III. THE SDN CONTROLLER’S PROBLEM We now describe the problem that the SDN controller has to solve in detail. Assume that the network comprises of a set of nodes N interconnected by a set of directed links E. We assume that there are n nodes and m links in the network. Let C ⊆ N denote the set of SDN-FEs and D = N \ C denote the non-SDN-FEs. Let w(e) and c(e) denote the OSPF link weight and capacity respectively of a link e ∈ E. We use f(e) to represent the traffic flow on link e. The flow on all links e ∈ E is available to the controller from OSPF-TE. We use Tsd to represent the traffic rate from node s ∈ N to some other node d ∈ N and Wud to represent the total amount of traffic for destination d ∈ N that either originates or passes through SDN-FE u ∈ C. Note that in general Wud ≥ Tud. SDN-FE u can measure Wud for all destinations d using the enhanced routing table described in Section 2. The value of Tsd for all node pairs (s, d) will not be known to the controller. Each node computes the shortest path to all other nodes in the network. The routing table at node u ∈ N comprises of the next hop on the shortest path to each node in the network. We use NH(u, d) to denote the next hop node for destination d at node u. In other words, NH(u, d) is the first node on the shortest path from u to d. In the remainder of this paper, we assume that the next hop is unique for all the non-SDN- FEs, i.e, NH(u, d) has only one element for all u ∈ D. We make this assumption purely for the ease of exposition. The techniques in this paper extend directly to the case where there alternate shortest paths between two nodes and traffic is split between these two paths as in Equal Cost Multipaths. Note that while NH(u, d) is computed based on shortest paths for all nodes u ∈ D, NH(u, d) can be set arbitrarily when u ∈ C as long as there are no routing loops. We illustrate some of the ideas outlined in the above paragraph using Figure 3. We assume that all link weights are one and the solid links represent the shortest path tree to node 13. This is the tree that will result if the SDN-FEs also use the standard shortest path computation. Recall that nodes 2, 9, 14 are the SDN-FEs. Note that NH(6, 13) = 10, NH(1, 13) = 2 and so on. The dotted lines in the network that show the alternate links possible at the SDN-FEs. For example, node 2 can split the traffic to node 13 along two different next hops one going to node 5and the other to node 11. 1 4 8 10 6 5 13 14 12 15 11 7 3 2 9 Fig. 3. Shortest Path Tree to Node 13 Definition 1: Given a set of SDN-FE nodes C, a path s = u0 , u1, u2 , . . . uk = d from a source node s to a des- tination node d will be termed feasible if for j = 1, 2, . . . , k, (uj−1, uj) ∈ E and uj = NH(uj−1, d) if uj−1 ∈ D . A feasible path where u0 , u1, . . . , uk are distinct is called an admissible path. Let Psd denote the set of admissible paths between s and d. From the definition, note that a path is feasible if the next hop to a given destination for all the non-SDN-FEs is given by the shortest path algorithm. Further a feasible path is admissible only if it is loopless. Therefore we have to ensure that all the traffic between s and d has to be routed on P ∈ Psd. For example, in Figure 3, 3− 2− 5− 12− 13 is an admissible path from 3 to 13. Note that this is not the shortest path which is 3 − 2 − 11 − 13. The path 3 − 6 − 11 − 13 is not admissible since the next hop for node 3 which is a non-SDN-FE has to be the next hop on the shortest path, which is node 2. 2013 Proceedings IEEE INFOCOM 2213 4 Definition 2: Given shortest path routing at the non-SDN- FEs, traffic that goes from source to destination without tran- siting through a SDN-FE will be referred to as uncontrollable traffic. If the source of a packet is a SDN-FE, or if it passes through at least one SDN-FE before it reaches its destination then this traffic will be called controllable traffic. In other words, controllable traffic comprises of packets that pass through at least one SDN-FE if the packets are routed using standard OSPF. There is at least an opportunity at the SDN-FEs to manipulate the path of controllable traffic. For example the traffic from 6 to 13 is routed by OSPF along 6 − 10− 13, and since neither 6 nor 10are SDN-FEs, traffic from 6 to 13 is not controllable. In contrast, traffic from node 8 to 13 passes through node 9which is a SDN-FE and hence this traffic is controllable. Definition 3: We say that a SDN-FE u ∈ C injects a packet if • Node u is on the OSPF routing path for the packet. • The packet passes through u before it passes through any other SDN-FE. The traffic that is injected by SDN-FE u ∈ C to some destination node d ∈ N will be denoted by Iud. Therefore, for all controllable traffic there is a unique SDN- FE that injects this traffic. Note that the SDN-FE may or may not be the source of the traffic that it injects. We illustrate these ideas in Figure 4. In this figure, the number next to the node represents the traffic rate from that node to node 13. For example, the traffic from node 1 to node 13 (T1,13 ) is 3 units. By Definition 3, note that the traffic from 3 to 13 will be injected by the SDN-FE 2. If the values of Tsd are known for all source-destination pairs (s, d), then the value of Iud can be computed as follows: Remove the links going out of the SDN-FEs and let OSPF route all demands until it reaches the SDN-FEs or the destination. The traffic that accumulates at the SDN-FEs is the traffic that is injected by the SDN- FE. For example in Figure 3, I2,13 = 9 , I9,13 = 13 and I14,13 = 5. As stated earlier, the values of Tsd are not known to the SDN-C. The only measurements available at the SDN- C are the values of Wud which is the traffic for destination d that passes through node u ∈ C. 3 24 6 4 6 2 1 1 2 4 3 5 13 9 4 6 3 1 2 4 11 1 6 43 3 3 3 7 9 11 13 15 12 14 5 6 10 8 4 2 1 Fig. 4. Independently Routable Traffic at the SDN-FEs A. Formulation of the SDN-C’s Problem Since the only traffic that we can manipulate is the traffic that passes through the SDN-FEs, we just focus on the traffic injected at the SDN-FEs. Traffic Iud is injected by SDN-FE u ∈ C that has to reach destination d. It can only do so along one of the admissible paths P ∈ Pud. Let g(e) denote the uncontrollable flow on link e. (Note that g(e) is easy to computed if the source-destination traffic rates Tsd are all known in advance. As stated earlier, this will not be the case in practice. However, we still give the formulation below in order to motivate the actual dynamic routing problem solved by the SDN-C). The objective of the SDN-C is to route the controllable traffic such that delay and packet loss at the links are minimized. The delay and packet loss at the links are increasing functions of the link utilization and therefore we use the link utilization as a surrogate for the delay/losses at the link. One natural objective for the SDN-C is to minimize the maximum utilization of the links in the network. In the formulation, the variables are x(P), which is the flow in path P . Since the number of paths in the network can be exponential in the number of nodes and arcs, the formulation is also exponential. We prefer this path to the more compact node-arc formulation since it lends itself better to the development primal-dual approximation algorithms. The SDN-C solves the following optimization problem: minimize θ subject to g(e) + ! P :P ∋e x(P) ≤ θ c(e) ∀e ∈ E (1) ! P ∈Pud x(P) ≥ Iud ∀u ∈ C d ∈ N (2) x(P) ≥ 0 ∀P (3) • The first set of inequalities ensure that the total flow on the link which is the sum of the uncontrollable flow (represented by g(e)) and the controllable flow (which is the second sum term on the right hand side) is less than the product of the maximum link utilization (θ) and the capacity of the link (c(e)). • The second set of inequalities ensures that the total injected traffic is routed in the network. • The third set of inequalities ensures that the flow on any path is non-negative. The optimum value of θ is the maximum utilization of any link. Note that if the optimum value of θ < 1, then none of the links will be over-utilized. Once the SDN-C solves this optimization problem, it is easy to compute the next hops and the corresponding fractions at all the SDN-FEs for each destination. In the formulation above, we assumed that values Iud and g(e) are known. In reality both the quantities Iud as well as g(e) have to be computed by the SDN-C based on 2013 Proceedings IEEE INFOCOM 2214 5 the measurements made by the SDN-FEs and the OSPF-TE messages received by the SDN-C. B. Computing Iud and g(e) Dynamically The only measured quantities that are available to the SDN- C are • The link load f(e) for all links e ∈ E that can be got from OSPF-TE information. • The quantities Wud for all u ∈ C for all d ∈ N. This is measured by the SDN-FEs and sent to the SDN-C. Using these two quantities, the SDN-C has to compute the values of g(e) for all e ∈ E and Iud for all u ∈ C for all d ∈ N. We first outline the computation of Iud. Consider a fixed destination node d. The SDN-C knows the current routing to this destination node d. It knows all the next hops for all nodes in D and at all the SDN-FEs it not knows all the next hops for the destination and the traffic split if there are multiple next hops. Definition 4: Given a destination d and the current routing in the network, the routing order of the nodes in C with respect to this destination d is defined as an ordering of the nodes in C \ d such that if u ∈ C appears before v ∈ C in this list then there is no traffic whose destination is d that is routed from v to u. We denote the routing order for destination node d as R(d) and the fact that u appears before v in R(d) as u ≺ d v. This routing order is well defined for any destination node d since there cannot be any routing loops in the traffic flowing to destination d. (In fact it is possible to order all the nodes in the network not just the nodes in C, but we are interested only in the ordering of the nodes in C.) Assume that the current routing to node 13 is as shown in Figure 5. We only show the portion of the routing that is relevant for the SDN-FEs. In this case note that there is traffic from node 9that passes through node 14. Therefore 9≺ 13 14. One routing order is (2, 9, 14). Other orderings are possible but node 14 should appear after node 9in any ordering. 10 5 13 14 12 15 11 2 9 Fig. 5. Illustrating Routing Order The algorithm to compute the values of Iud is given below. Computing Iud For each destination d ∈ N 1. Compute the routing order R(d) 2. For the first node u in R(d) set Iud = Wud 3. Route one unit of flow from u to d and set βv(u, d) be the fraction of this unit flow that reaches node v ∈ C. 4. For each successive node w in R(d) Set Iwd = Wwd − " u≺dw βw(u, d)Iud. Route one unit of flow from w to d and compute βv(w, d) for all v ∈ C. Once the values of Iud are known for all u ∈ C for all d ∈ N, we use this to compute the values of the g(e) which is the uncontrollable traffic that flows on link e ∈ E. This is done as follows We inject one unit of flow at node u ∈ C for destination d ∈ N and computes αe(u, d) which is the fraction of this unit flow that is routed on link e. Since we know Iud for u ∈ C, we can compute g(e) = f(e) − ! u∈C ! d αe(u, d)Iud ∀e ∈ E. The SDN-C now knows the values of Iud for all nodes u ∈ C for all d ∈ N as well as the values of g(e) for all e ∈ E. C. Formulating the Dynamic Routing Problem The SDN-C routes traffic to minimize the maximum utilization of the links in the network. An equivalent problem that is more convenient to solve is to keep the capacities of the link fixed but scale the injected traffic so that it still fits in the network. This problem is the following: maximize λ subject to ! P :P ∋e x(P) ≤ c(e) − g(e) = b(e) ∀e ∈ E (4) ! P ∈Pud x(P) ≥ λIud ∀u ∈ C d ∈ N (5) x(P) ≥ 0 ∀P (6) If the optimal λ > 1 then the current traffic can be routed at the SDN-FEs while ensuring that all link utilizations are less than one. Note that the optimal solution to this scaling problem is the inverse of the optimal solution to the min-max utilization problem. In spite of the fact that the problem has an exponential number of variables, we can solve the problem to any desired level of accuracy using a primal-dual algorithm. In order to write the dual linear program to the dynamic routing problem shown above, we associate dual variables l(e) with each link capacity constraint (4) and zud for the 2013 Proceedings IEEE INFOCOM 2215 6 demand constraints (5). The dual can now be written as minimize ! e∈E b(e) l(e) subject to ! e∈P l(e) ≥ zud ∀P ∈ Pud ∀u ∈ C ∀d (7) ! u∈C ! d∈N Iud zud ≥ 1 (8) l(e) ≥ 0 ∀e ∈ E. (9) Assume that we set l(e) to be the weight of link e ∈ E. (We use the term weight instead of cost in order to avoid confusion with the OSPF link costs). Note from the first set of constraints zud is the lightest path from u to d. (Again we use the term lightest path to avoid confusion with the shortest path using OSPF costs). Let Lud denote the lightest path from u to d using the link weights l(e) on link e. The dual can now be re-written as minimize ! e∈E b(e) l(e) subject to ! u∈C ! d∈N Iud Lud ≥ 1 (10) l(e) ≥ 0 ∀e ∈ E. (11) In other words, given any non-negative set of link weights l(e), note that ! e∈E b(e)l(e)! u∈C ! d∈N IudLud is an upper bound on the dynamic routing problem. We now outline the solution of the dynamic traffic management problem. D. Solving the Dynamic Routing Problem We use a Fully Polynomial Time Approximation Scheme (FPTAS) to solve the dynamic routing problem at the SDN-C. The reason for solving the problem as an FPTAS instead of a standard linear programming problem is that the FPTAS is very simple to implement and runs significantly faster than a general linear programming solver especially on medium and large sized problems. An FPTAS provides the following performance guarantees: for any ϵ > 0, the solution has objective function value within (1 + ϵ)-factor of the optimal, and the running time is at most a polynomial function of the network size and 1/ϵ. The FPTAS in our case is a primal dual algorithm. The primal dual algorithm for our problem works as follows: The algorithm first computes a value δ that is a function of the desired accuracy level ϵ, the number of nodes n and the number of arcs m. The dual weight of each edge e ∈ E is initialized to l(e) = δ b(e) . The primal dual algorithm operates in phases where in each primal phase flow is routed to a given destination from all SDN-FEs along the lightest permissible path (using the dual vector l(e) as the link weight). Once each SDN-FE u has shipped a flow of Iud to destination d, the (dual) weights of the arcs on which flow has been sent is incremented. This process of augmenting flow and updating the dual lengths is repeated until the problem is dual feasible. The algorithm is given in more detail below: Algorithm COMPUTE THROUGHPUT: DL ← 0 l(e) ← δ/b(e) e ∈ E Rsd ← 0∀(s, d) while DL < 1 do for each destination d ∈ N d′(u) = Iud ∀u ∈ C while DL < 1 and d′(u) > 0for some u ∈ C do Pud : Shortest admissible path using l, ∀u with d′(u) > 0 c = mine∈∪ sPsd b(e) ρ(e) is the utilization of e ∈ E ρ = max{1, maxe∈∪ uPud ρ(e)} f(u) = min{d′(u), c} ∀u Route f(u) ρ flow from each u to d. d′(u) = d′(u) − f(u) ρ Rud = Rud + f(u) ρ l(e) = l(e) (1 + ϵρ(e)) Recompute DL = " e∈E b(e)l(e) end while end for end while λ = min Rud Tud Output λ The next result gives the running time of the algorithm and the proof of this result is almost identical to the one in Karakosatas [7]. Theorem 1: Set δ = 1 (1 + nϵ) 1−ϵ ϵ # 1 − ϵ m $1 ϵ then the running time of the primal-dual algorithm is O(ϵ−2 m2 logO(1) m) where m is the number of edges in the …