Xuan-Nam Nguyen

Damien Saucez

Chadi Barakat

Thierry Turletti

Rules Placement Problem in OpenFlow Networks: a Survey

Keywords: Software-Defined Networking, OpenFlow, rules placement, survey Packets, Bytes

Software-Defined Networking (SDN) abstracts lowlevel network functionalities to simplify network management and reduce costs. The OpenFlow protocol implements the SDN concept by abstracting network communications as flows to be processed by network elements. In OpenFlow, the high-level policies are translated into network primitives called rules that are distributed over the network. While the abstraction offered by OpenFlow allows to potentially implement any policy, it raises the new question of how to define the rules and where to place them in the network while respecting all technical and administrative requirements. In this paper, we propose a comprehensive study of the so-called OpenFlow rules placement problem with a survey of the various proposals intending to solve it. Our study is multi-fold. First, we define the problem and its challenges. Second, we overview the large number of solutions proposed, with a clear distinction between solutions focusing on memory management and those proposing to reduce signaling traffic to ensure scalability. Finally, we discuss potential research directions around the OpenFlow rules placement problem.

I. INTRODUCTION

Computer networks today consist of many heterogeneous devices (e.g., switches, routers, middleboxes) from different vendors, with a variety of sophisticated and distributed protocols running on them. Network operators are responsible for configuring policies to respond to a wide range of network events and applications. Normally operators have to manually transform these high level policies into low level vendor specific instructions, while adjusting them according to changes in network state. As a result, network management and performance tuning are often complicated, error-prone and time-consuming. The main reason is the tight coupling of network devices with the proprietary software controlling them, thus making it difficult for operators to innovate and specify high-level policies [START_REF] Mckeown | Openflow: enabling innovation in campus networks[END_REF].

Software-Defined Networking (SDN) advocates the separation between forwarding devices and the software controlling them in order to break the dependency on a particular equipment constructor and to simplify network management. In particular, OpenFlow implements a part of the SDN concept through a simple but powerful protocol that abstracts network communications in the form of flows to be processed by intermediate network equipments with a minimum set of primitives [START_REF] Mckeown | Openflow: enabling innovation in campus networks[END_REF].

OpenFlow offers many new perspectives to network operators and opens a plethora of research questions such as how to design network programming languages, obtain robust systems with centralized management, control traffic at the packet level, perform network virtualization, or even co-exist with traditional network protocols [START_REF] Foster | Frenetic: a network programming language[END_REF], [START_REF] Voellmy | Procera: a language for high-level reactive network control[END_REF], [START_REF] Voellmy | Maple: Simplifying sdn programming using algorithmic policies[END_REF], [START_REF] Nunes | A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks[END_REF], [START_REF] Xia | A survey on software-defined networking[END_REF], [START_REF] Kreutz | Software-defined networking: A comprehensive survey[END_REF], [START_REF] Vissicchio | On the Co-Existence of Distributed and Centralized Routing Control-Planes[END_REF]. For all these questions, finding how to allocate rules such that high-level policies are satisfied while respecting all the constraints imposed by the network is essential. The challenge being that while potentially many rules are required for traffic management purpose [START_REF] Moshref | vCRIB: Virtualized Rule Management in the Cloud[END_REF], in practice, only a limited amount of resources, and in particular memory [START_REF] Stephens | PAST: Scalable Ethernet for Data Centers[END_REF], is available on OpenFlow switches. In this paper, we survey the fundamental problem when OpenFlow is used in production networks, that we refer to it as the OpenFlow rules placement problem. We focus on OpenFlow as it is the most popular southbound SDN interface that has been deployed in production networks [START_REF] Jain | B4: Experience with a globally-deployed software defined WAN[END_REF].

The contributions of this paper include:

• A generalization of the OpenFlow rules placement problem and an identification of its main challenges involved. • A presentation, classification, and comparison of existing solutions proposed to address the OpenFlow rules placement problem. • A discussion of potential directions around the OpenFlow rules placement problem.

The paper is organized as follows. In Sec. II, we provide a background on SDN and OpenFlow. In Sec. III, we formalize the OpenFlow rules placement problem, discuss the challenges and illustrate them through different use cases. We continue with existing ideas that address the two main challenges of the OpenFlow rules placement problem: memory limitation in Sec. IV, and signaling overhead in Sec. V. We finally discuss potential research directions in Sec. VI and conclude in Sec. VII.

II. BACKGROUND

Software-Defined Networking (SDN) is a new networking paradigm in which the control plane (i.e., how to handle traffic) is separated from the data plane (i.e., how to forward packets according to decisions from the control plane). OpenFlow [START_REF] Mckeown | Openflow: enabling innovation in campus networks[END_REF], depicted in Fig. 1, is the most popular implementation of the southbound interface of SDN [START_REF] Nunes | A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks[END_REF], [START_REF] Xia | A survey on software-defined networking[END_REF], [START_REF] Kreutz | Software-defined networking: A comprehensive survey[END_REF], [START_REF] Jain | B4: Experience with a globally-deployed software defined WAN[END_REF], [START_REF] Kobayashi | Maturing of OpenFlow and Software-defined Networking through deployments[END_REF].

In OpenFlow, forwarding devices are called OpenFlow switches and all forwarding decisions are flow-based instead of destination-based like in traditional routers. An OpenFlow switch consists of flow tables, each containing a prioritized list of rules that determine how packets have to be processed Fig. 1. OpenFlow Architecture. Network control functions are separated from the forwarding devices (i.e., OpenFlow switches) and moved to an entity called the controller. The controller manages the network using the OpenFlow protocol and exposes a northbound Application Program Interface (API) for the operator to write applications for the automation of management tasks, such as load balancing. by the switch. 1 A rule consists of three main components: a matching pattern, an actions field and a counter. The matching pattern forms a predicate whose value is computed on-the-fly by the switch based on packet meta-information (e.g., source IP address). All packets making true the matching pattern predicate are said to belong to the same flow. The actions specified in the actions field of the rule are applied to every packet of the corresponding flow. The most common actions are: forwarding, dropping, or rewriting the packets. Finally, the counter is used to count the number of packets that has been processed (i.e., that made the predicate hold true) along with the lifetime of this rule. As a packet may match multiple matching patterns, each rule is associated with a priority and only the rule with the highest priority that matches the packet is considered to take actions on it. The prioritization of rules permits constructing default actions that can be applied on packets only if no other rule can be used. Examples of default actions are dropping packets, forwarding packets to a default interface, or even to the controller. For efficiency and flexibility reasons, the latest versions of OpenFlow [START_REF] Openflow | OpenFlow Switch Specification[END_REF] support pipeline processing where a packet might be processed by several rules from different flow tables.

The control plane of OpenFlow is implemented with a controller. In general, the controller is logically centralized, but this does not prevent it to be physically distributed for scalability and fault tolerance reasons. The controller maintains a global view of the network with its state at any instant and updates flow tables in switches using the OpenFlow protocol. Many OpenFlow controller platforms are available to handle connections with OpenFlow switches and to provide basic functions like routing, flow table management, and topology discovery [START_REF] Gude | Nox: towards an operating system for networks[END_REF], [START_REF]Floodlight[END_REF], [START_REF] Erickson | The Beacon Openflow Controller[END_REF], [START_REF] Ryu | Ryu controller[END_REF], [START_REF] Opendaylight | OpenDaylight Controller[END_REF]. However, most of controller platforms still force operators to manage their 1 In this paper we follow the OpenFlow model terminology where a packet consists of any piece of information traveling through the network and a switch stands for any device processing such a packet. network at the level of individual switches, by selecting and populating flow tables to satisfy network constraints [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF].

For the sake of simplicity, we summarize the terminology and the notations used in this survey in Table I and Table II.

III. OPENFLOW RULES PLACEMENT PROBLEM

A. Motivation

OpenFlow facilitates network management by raising the level of network abstraction ( [START_REF] Foster | Frenetic: a network programming language[END_REF], [START_REF] Voellmy | Procera: a language for high-level reactive network control[END_REF], [START_REF] Voellmy | Maple: Simplifying sdn programming using algorithmic policies[END_REF], [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF], [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF]). High level of abstraction hides the complexity of the network devices, and exposes a simple interface to the operators. As a result, the operator models the network as a single big switch, a blackbox, and no longer needs to care about lowlevel details, such as how to configure devices and manage resources. Therefore, network management becomes simpler and more robust, which reduces the risk of errors and provides a higher degree of freedom in management.

A layer between the operators and the networks is required to transform the high-level policies from operators into lowlevel rules to be installed on OpenFlow switches. Therefore, it is necessary to solve the OpenFlow rules placement problem that consists in selecting the most relevant rules to place on each switch so that both the high-level policies and the network constraints are satisfied. A rule placement solution defines which rules must be deployed in the network and where.

F1

To Switch 2 F2

To Switch 3 F1

To E1 F2 To E2

Fig. 3. An example of forwarding rules placement. Forwarding rules are installed on appropriate paths to make sure that the endpoint policy is satisfied. Rules R1, R3 (R2, R4) are installed on switches 1,2 (1, 3) to route F1 (F2) towards its endpoint E1 (E2).

Many applications can benefit from OpenFlow, for example, monitoring, accounting, traffic shaping, routing, access control and load balancing [START_REF] Mckeown | Openflow: enabling innovation in campus networks[END_REF]. Each of these applications requires a dedicated rules placement solution. In multi-tenant clouds, each user has different policies (e.g., firewall policy), which also requires a dedicated rules placement.

In the following, we describe two representative scenarios, that motivate the need to solve OpenFlow rules placement problem:

a) Access Control: As a part of endpoint policy, the firewall policy is critical to the network security. Most of firewall policies can be defined as a list of prioritized access control rules, that specify which flows are authorized and where. OpenFlow is a potential candidate to implement the access control policy, due to its flexible matching patterns and actions.

Ideally, all access control rules should be placed on the ingress switches to limit unwanted network traffic. However, the switch memory constraints prohibit usually placing all rules in ingress switches. An alternative solution is to put all rules in the software switches that have large memory capacity and to direct all traffic to them. However, software switches are generally slower than hardware-accelerated solutions. Therefore, a solution is required to distribute rules over network such that the semantic of the original access control list is preserved and resource constraints are satisfied.

Fig. 2 shows an example of access control rules placement. The firewall policy must be applied on all flows originated from switch 1 and 3. A solution is to use rules R1, R2, R3 for blocking matching packets and use the default rules RD1, RD2 for forwarding non-matching packets towards endpoint E. Then, these rules are distributed on the switches, according to the memory capacity, to enforce firewall policy on all flows.

b) Traffic engineering: The role of the network is to deliver packets towards its destinations and to satisfy the operator's requirements (e.g., low latency, low loss rate). OpenFlow allows defining rules matching any type of packets and forwarding them on any paths.

Normally, the forwarding rules that match the packets should be placed on the shortest paths to forward them toward their endpoints. However due to memory limitation of the OpenFlow switch, all rules to be installed might not be fit into the shortest paths. Therefore, it is important to select the right paths and to make extensive usage of wildcard rules to satisfy requirements.

An example of forwarding rules placement is shown in Fig. 3. Forwarding rules are required to be installed on appropriate paths to make sure that the endpoint policy for F 1, F 2 is satisfied. To that aim, a solution is to install forwarding rules R1, R3 (resp. R2, R4) on switches 1, 2 (resp. 1, 3) to route F 1 (resp. F 2) towards its endpoint E1 (resp. E2).

B. Problem Formalization

In the following, we formalize the OpenFlow rules placement problem using the notations in Table II. The network is modeled as a directed graph G = (V, E), where V is the set of nodes and each node v ∈ V can store C v rules, E is the set of links. O is the set of endpoints where the flow used to exit the network (e.g., peering links, gateways, firewalls). A flow can have many endpoints o f ∈ O. P is the set of possible paths that flows can use to reach their endpoints o f ∈ O. Each path p ∈ P , consists of a sequence of nodes v ∈ V . F , R are the set of flows and rules for selection, respectively.

The output of the problem is the content of the flow table of node F T (v, t) = [r 1 , r 2 , ...] ⊂ R, which defines the set of rules required to install node v ∈ V at time t ∈ T . T = [t 1 , t 2 , ...] is set of the time instants at which F T (v, t) is computed and remains unchanged during the period [t i , t i+1 ]. Each rule r j is defined as a tuple, which contains values for matching pattern m, actions a, priority number q and timeouts t idle , t hard , selected by the solvers. 2 The flow table content of all nodes F T (v, t), ∀v ∈ V at a time t is defined as a rules placement solution. Furthermore, F T (v, t) changes over time t to adapt with network changes (e.g., topology changes, traffic fluctuation). In order to construct rules placement, the following inputs are considered:

• Traffic flows F , which stand for the network traffic.

The definition of a flow, implemented with the matching pattern, depends on the granularity needed to implement the operator policies. For example, network traffic can be modeled as set of Source-Destination (SD) flows, each flow is a sequence of packets having the same source and destination IP address. • Policies, which are defined by the operator, can be classified into two categories: (i) the end-point policy EP : F → O that defines where to ultimately deliver packets (e.g. the cheapest link) and (ii) the routing policy RP : F → P that indicates the paths that flows must follow before being delivered (e.g. the shortest path) [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF]. The definition of these policies is often the result of the combination of objectives such as cost reduction, QoS requirements and energy efficiency [START_REF] Giroire | Optimizing rule placement in software-defined networks for energy-aware routing[END_REF], [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF], [START_REF] Huang | The Joint Optimization of Rules Allocation and Traffic Engineering in Software Defined Network[END_REF], [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF], [START_REF] Li | Morule: Optimized rule placement for mobile users in sdn-enabled access networks[END_REF]. • Rule space R, which defines the set of all possible rules for selection, depending on applications. For example, an access control application allows selecting rules that contain matching m for 5-tuples IP fields (source/destination IP address, source/destination port number, protocol number) while a load balancing application requires rules that contain matching m for source/destination IP address [START_REF] Wang | Openflow-based server load balancing gone wild[END_REF]. The combination of fields and values forms a large space for selection. • Resource constraints, such as memory, bandwidth, CPU capacity of the controller and nodes. Rules placement solutions must satisfy these resource constraints. As an example, the total number of rules on a node should not exceed the memory capacity of the nodes:

|F T (v, t)| ≤ C v , ∀(v, t) ∈ V × T .
There might be a countless number of rules placement possibilities that satisfy the above inputs. Therefore, F T (v, t) is usually selected based on additional requirements, such as in order to minimize the overall rule space consumption v∈V |F T (v, t)|. Note that in general, the OpenFlow rules placement problem is NP-hard [START_REF] Nguyen | Optimizing Rules Placement in OpenFlow Networks: Trading Routing for Better Efficiency[END_REF], [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF].

C. Challenges

Elaborating an efficient rules placement algorithm is challenging due to the following reasons.

1) Resource limitations: In most of production environments, a large number of rules is required to support policies whereas network resources (e.g., memory) are unfortunately limited. For example, up to 8 millions of rules are required in typical enterprise networks [START_REF] Yu | Scalable flow-based networking with DIFANE[END_REF] and up to one billion for the management of tasks in the cloud [START_REF] Moshref | vCRIB: Virtualized Rule Management in the Cloud[END_REF]. According to Curtis 2 We focus on important fields only. The complete list of fields of an OpenFlow rule can be found in the OpenFlow specifications [START_REF] Openflow | OpenFlow Switch Specification[END_REF]. et al. [START_REF] Curtis | DevoFlow: scaling flow management for high-performance networks[END_REF], a Top-of-Rack switch in data centers may need 78,000 rules to accommodate traffic.

While the number of rules needed can be very large, the memory capacity to store rules is rather small. Typically, OpenFlow flow tables are implemented using Ternary Content Addressable Memory (TCAM) on switches to ensure matching flexibility and high lookup performance. However, TCAM is board-space costly, is 400 times more expensive and consumes 100 times more power per Mbps than RAM-based storage [START_REF] Katta | Infinite CacheFlow in Software-defined Networks[END_REF]. Also, the size of each flow entry is 356 bits [START_REF] Openflow | OpenFlow Switch Specification[END_REF], which is much larger than the 60-bit entries used in conventional switches. As a consequence, today commercial off-theshelf switches support only from 2k to 20k rules [START_REF] Stephens | PAST: Scalable Ethernet for Data Centers[END_REF], which is several orders of magnitude smaller than the total number of rules needed to operate networks. Kobayashi et al. [START_REF] Kobayashi | Maturing of OpenFlow and Software-defined Networking through deployments[END_REF] confirm that the flow table size of commercial switches is an issue when deploying OpenFlow in production environments.

Recently, software switches built on commodity servers (e.g., Open vSwitch [START_REF] Openvswitch | OpenvSwitch[END_REF]) are becoming popular. Such switches have large flow table capacity and can process packets at high rate (e.g., 40 Gbps on a quad-core machine [START_REF] Katta | Infinite CacheFlow in Software-defined Networks[END_REF]). However, software switches are more limited in forwarding and lookup rate than commodity switches [START_REF] Moshref | Scalable Rule Management for Data Centers[END_REF] for two main reasons. Firstly, software switches use general purpose CPU for forwarding, whereas commodity switches use Application-Specific Integrated Circuits (ASICs) designed for high speed throughput. Secondly, rules in software switches are stored in the computer Random Access Memory (RAM), which is cheaper and larger, while rules in commodity switches are stored in TCAM, which allows faster lookup but has limited size. For example, an 8-core PC supports forwarding capacities of 4.9 millions packets/s, while modern switches using TCAMs do forwarding at a rate up to 200 millions packets/s [START_REF] Moon | Bridging the Software/Hardware Forwarding Divide[END_REF].

To accelerate switching operations in software switches, flow tables can be stored in CPU caches. Nevertheless, these caches are rather small, which brings the same problem than with ASICs.

In Sec. IV, we extensively survey the techniques proposed in the literature to cope with the memory limitation in the context of the OpenFlow rules placement problem.

2) Signaling overhead: Installing or updating rules for flows triggers the exchange of OpenFlow messages. Bad rules placement solutions might also cause frequent flow table misses that would require controller to act. While the number of messages per flow is of the order of magnitude of the network diameter, the overall number of messages to be exchanged may become large. For instance, in a data center with 100,000 new flows per second [START_REF] Benson | Network Traffic Characteristics of Data Centers in the Wild[END_REF], at least 14 Gbps of overall control channel traffic is required [START_REF] Iyer | SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks[END_REF]. Comparably, in dynamic environments, rules need to be updated frequently (e.g., routing rules may change every 1.5s to 5s [START_REF] Moshref | vCRIB: Virtualized Rule Management in the Cloud[END_REF] and forwarding rules can be updated hundreds times per second [START_REF] Agarwal | Shadow macs: Scalable label-switching for commodity ethernet[END_REF]).

In situations with large signaling load, the controller or switches might be overloaded, resulting in the drop of signaling messages and consequently in potential policy violations, blackhole, or forwarding loops. High signaling load also impacts the CAPEX as it implies investment in powerful

R1 R2 R3 R4 LRU, FIFO, Timeout
Flow Table

New rule

Fig. 4. An example of eviction. Rule R2 in the flow table is reactively evicted using replacement algorithms (e.g., LRU, FIFO) when the flow table is full and a new rule R4 needs to be inserted. R2 can also be proactively evicted using, for example, a timeout mechanism.

hardware to support the load.

We provide a comprehensive survey of OpenFlow rules placement problem solutions that deal with signaling overhead in OpenFlow in Sec. V.

IV. EFFICIENT MEMORY MANAGEMENT

As explained in Sec. III-C, all required rules might not fit into the flow table of a switch because of memory limitations. In this section, we classify the different solutions proposed in the literature to manage the switch memory into three categories. In Sec. IV-A, we detail solutions relying on eviction techniques. The idea of eviction is to remove entries from a flow table before installing new entries. Afterwards, in Sec. IV-B, we describe the techniques relying on compression. In OpenFlow, compressing rules corresponds to building flow tables that are as compact as possible by leveraging redundancy of information between the different rules. Then, in Sec. IV-C, we explain the techniques following the split and distribution concept. In this case, switches constitute a global distributed system, where switches are inter-dependent instead of being independent from each other. Finally, we provide in Table III a classification of the related work and corresponding memory management techniques.

A. Eviction

Because of memory limitation, the flow table of a switch may be filled up quickly in presence of large number of flows. In this case, eviction mechanisms can be used to recover the memory occupied by inactive or less important rules to be able to insert new rules. Fig. 4 shows an example where the flow table is full and new rule R4 needs to be inserted. In this case, rule R2 in the flow table is evicted using replacement algorithms (e.g., LRU, FIFO). R2 can also be proactively removed using OpenFlow timeout mechanism.

The main challenge in using eviction is to identify high value rules to keep and to remove inactive or least used rules.

Existing eviction techniques have been proposed such as Replacement algorithms (Sec. IV-A1), Flow state-based eviction(Sec. IV-A2) and Timeout mechanisms (Sec. IV-A3).

1) Replacement algorithms: Well-known caching replacement algorithms such as Least Recent Used (LRU), First-In First-Out (FIFO) or Random replacement can be implemented directly in OpenFlow switches. Replacement algorithms are performed based on lifetime and importance of rules, and is enabled by setting the corresponding flags in OpenFlow switches configuration. As eviction is an optional feature, some OpenFlow switches may not support it [START_REF] Openflow | OpenFlow Switch Specification[END_REF]. If the corresponding flags are not set and when the flow table is full, the switch returns an error message when the controller tries to insert a rule.

Replacement algorithms can also be implemented by using the controller delete messages (OFPFC DELETE). If the flag OFPFF SEND FLOW REM is set when the rule is installed, on rule removal, the switch returns a message containing the removal reason (e.g., timeout) and the statistics (e.g., flow duration, number of packets) at the removal time to the controller [START_REF] Openflow | OpenFlow Switch Specification[END_REF]. From OpenFlow 1.4, the controller can get early warning about the current flow table occupation and react in advance to avoid flow table full [START_REF] Kim | A flow entry management scheme for reducing controller overhead[END_REF]. The desired warning threshold is defined by the controller.

Vishnoi et al. [START_REF] Vishnoi | Effective switch memory management in OpenFlow networks[END_REF] argue that replacement algorithms are not suitable for OpenFlow. First, implementing replacement algorithms on the switch side violates one of the Open-Flow principles, which is to delegate all intelligence to the controller. Second, implementing replacement algorithms at the controller side is unfeasible because of large signaling overhead (e.g., statistic collections and delete messages).

Among replacement algorithms, LRU outperforms others and improves flow table hit ratio, by keeping recently used rules in flow table, according to studies [START_REF] Zarek | OpenFlow Timeouts Demystified[END_REF], [START_REF] Kim | A flow entry management scheme for reducing controller overhead[END_REF]. However, the abundance of mice flow in data center traffic can cause elephant flows' rules to be evicted from the flow table [START_REF] Bu | An efficient flow cache algorithm with improved fairness in Software-Defined Data Center Networks[END_REF]. Therefore, replacement algorithms need to be designed to favor frequent used rules.

2) Flow state-based Eviction: Flows vary in duration and size [START_REF] Benson | Network Traffic Characteristics of Data Centers in the Wild[END_REF]. Therefore, flow state information can also be used to early evict rules before their actual expiration [START_REF] Zarek | OpenFlow Timeouts Demystified[END_REF], [START_REF] Cardoso | On Time-based Strategies for Optimizing Flow Tables in SDN[END_REF], [START_REF] Kannan | FlowMaster: Early Eviction of Dead Flow on SDN Switches[END_REF]. For example, based on observation of flow packet's flags (e.g., TCP FIN flag), the controller can decide to remove the rule used for that flow by sending delete messages. However, eviction algorithms relying on flow state can be expensive and not easy to implement, because of large signaling overhead [START_REF] Zarek | OpenFlow Timeouts Demystified[END_REF].

3) Timeout mechanisms: Rules in flow tables can also be proactively evicted after a fixed amount of time (hard timeout) t hard or after some period of inactivity (idle timeout) t idle using the timeout mechanism in OpenFlow switches [START_REF] Openflow | OpenFlow Switch Specification[END_REF], if these values are set when the controller installs rules.

Previous controllers have assigned static idle timeout values ranging from 5s in NOX [START_REF] Gude | Nox: towards an operating system for networks[END_REF], to 10s and 60s in De-voFlow [START_REF] Curtis | DevoFlow: scaling flow management for high-performance networks[END_REF]. Zarek et al. [START_REF] Zarek | OpenFlow Timeouts Demystified[END_REF] study different traces from different networks and observe that the optimal idle timeout value is 5s for data centers, 9s for enterprise networks, and 11s for core networks.

Flows can vary widely in their duration [START_REF] Benson | Network Traffic Characteristics of Data Centers in the Wild[END_REF], so setting the same timeout value for all rules may lead to inefficient memory usage for short lifetime flows. Therefore, adaptive timeout mechanisms [START_REF] Vishnoi | Effective switch memory management in OpenFlow networks[END_REF], [START_REF] Xie | An adaptive scheme for data forwarding in software Defined Network[END_REF], [START_REF] Kannan | FlowMaster: Early Eviction of Dead Flow on SDN Switches[END_REF], [START_REF] Zhu | Intelligent timeout master: Dynamic timeout for SDN-based data centers[END_REF], [START_REF] Wang | Rule Optimization for Real-Time Query Service in Software-Defined Internet of Vehicles[END_REF] have been proposed. In these studies, the timeout value is chosen and adjusted based on flow state, controller capacity, current memory utilization, or switch location in the network. These approaches lead to better memory utilization and do not require the controller to explicitly delete entries. However, obtaining an accurate knowledge about flow state is usually expensive as it requires a large signaling overhead to monitor and collect statistics at high frequency.

In the original scheme of OpenFlow, when a packet matches a rule, the idle timeout counter of the rule is reset but the gain is limited [START_REF] Xie | An adaptive scheme for data forwarding in software Defined Network[END_REF]. Therefore, Xie et al. [START_REF] Xie | An adaptive scheme for data forwarding in software Defined Network[END_REF] propose that switches should accumulate remaining survival time from the previous round to the current round, so that the rules with high matching probability will be kept in the flow table. Considering the observation that many flows never repeat themselves [START_REF] Benson | Network Traffic Characteristics of Data Centers in the Wild[END_REF], a small idle timeout value in the range of 10ms -100 ms is recommended for better efficiency, instead of using the current minimum timeout of 1s [START_REF] Openflow | OpenFlow Switch Specification[END_REF], [START_REF] Vishnoi | Effective switch memory management in OpenFlow networks[END_REF]. These improvements require modifications in the implementation of OpenFlow.

All of the above studies advocate using idle timeout mechanism, since using hard timeout mechanism may cause rules removal during transmission of burst packets and leads to packet loss, increased latency, or degraded network performance [START_REF] Cardoso | On Time-based Strategies for Optimizing Flow Tables in SDN[END_REF].

B. Compression

Compression (or aggregation) is a technique that reduces the number of required rules while preserving the original semantics, by using wildcard rules. As a result, an original list of rules might be replaced by a smaller one that fits the flow table. As an example in Fig. 5, R2 and R3 have the same actions field and are compressed into a single rule R23 that has matching pattern covering both matching patterns of R2 and R3. Thus, rule space consumption is reduced while the original semantic is preserved.

Traditional routing table compression techniques for IP such as ORTC [START_REF] Draves | Constructing optimal IP routing tables[END_REF] cannot be directly applied to compress Open-Flow rules because of two reasons. First, OpenFlow switches decide which rule will be used based on rule priority number when there are several matching rules. Second, rules may contain multiple actions and multiple matching conditions, not restricted to IP.

The challenge when using compression is to maintain the original semantics, keep an appropriate view of flows and achieve the best tradeoff between compression ratio and computation time. The limitation of this approach is that today not all the OpenFlow matching fields support the wildcard values (e.g., transportation port numbers).

In the following, we discuss the compression techniques used for access control rules in Sec. IV-B1 and forwarding rules in Sec. IV-B2. Compression techniques may reduce flow visibility and also delay network update; therefore, we discuss its shortcoming and possible solutions in Sec. IV-B3.

1) Access control rules compression: Most of firewall policies can be defined as a list of prioritized access control rules. The matching pattern of an access control rule usually contains multiple header fields, while the action field is a binary decision field that indicates to drop or permit the packets matching that pattern. Normally, only rules with drop action are considered in the placement problem since rules with permit action are complementary [START_REF] Zhang | An Adaptable Rule Placement for Software-Defined Networks[END_REF]. Because the action field is limited to drop action, access control rules can be compressed by applying compression techniques on rules matching patterns, to reduce the number of rules required.

To that aim, rule matching patterns are represented in a bit array and organized in a multidimensional space [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF], [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF], where each dimension represents a header field (e.g., IP source address). Afterwards, heuristics such as Greedy are applied on this data structure to compute optimized wildcard rules. For example, two rule with matching m 1 = 000 and m 2 = 010 can be replaced by a wildcard rule with m = 0 * 1.

Matching patterns usually have dependency relationships. For example, packets matching m 1 = 000 also match m 2 = 00 * , therefore m 2 depends on m 1 . When rules with these matching patterns are placed, the conflict between them needs to be resolved. An approach for compression and resolving conflicts is to build a rule dependency graph [START_REF] Katta | Infinite CacheFlow in Software-defined Networks[END_REF], [START_REF] Zhang | An Adaptable Rule Placement for Software-Defined Networks[END_REF], where each node represents a rule and a directed edge represents the dependency between them. Analyzing this graph makes it possible to compute optimized wildcard rules and to extract the dependency constraints to fetch for their optimization placement model.

The network usually has a network-wide blacklisting policy shared by multiple users, for example, packets from a same IP address are dropped. Therefore, rules across different access control lists from different users can also be merged to further reduce the rule space required [START_REF] Zhang | An Adaptable Rule Placement for Software-Defined Networks[END_REF]. Also, traditional techniques exist to compress access control rules on a single switch [START_REF] Applegate | Compressing Rectilinear Pictures and Minimizing Access Control Lists[END_REF], [START_REF] Liu | TCAM Razor: A Systematic Approach Towards Minimizing Packet Classifiers in TCAMs[END_REF], [START_REF] Meiners | Bit Weaving: A Non-Prefix Approach to Compressing Packet Classifiers in TCAMs[END_REF].

2) Forwarding rules compression: In OpenFlow networks, forwarding rules can be installed to satisfy endpoint and routing policies. A naive approach is to place exact forwarding rules for each flow on the chosen path. However, this can lead to huge memory consumption in presence of large number of flows. Therefore, compression can be applied to reduce the number of rules to install.

Matching pattern of forwarding rules are usually simpler than access control rules, but they have a larger palette of actions (e.g., bounded by the number of switch ports) and they outnumber access control rules by far [START_REF] Braun | Wildcard Compression of Inter-Domain Routing Tables for OpenFlow-Based Software-Defined Networking[END_REF]. In addition, forwarding rules compression has stricter time constraints than access control rules compression when it comes to satisfying fast rerouting in case of failure.

OpenFlow forwarding rules can be interpreted as logical expressions [START_REF] Braun | Wildcard Compression of Inter-Domain Routing Tables for OpenFlow-Based Software-Defined Networking[END_REF], for example, ('11 * ', 2) represents for rules matching prefix '11 * ' and the action field is to forward to port 2. Normally, rules with same forwarding behavior are compressed into one wildcard rule. Also, it is important to resolve conflicts between rules, for example, by assigning higher priority for rule ('11 * ', 3) to avoid wrong forwarding caused by rule ('1 ** ', 2). To compress and to resolve conflicts, the Expresso heuristic [START_REF] Braun | Wildcard Compression of Inter-Domain Routing Tables for OpenFlow-Based Software-Defined Networking[END_REF] borrowed from logical minimization can be applied to obtain an equivalent but smaller sets, which is then transformed to corresponding rules. Forwarding rules can also be compressed based on source or destination IP address [START_REF] Rifai | Too many SDN rules? Compress them with MINNIE[END_REF].

The routing policy plays an important role in applying compression techniques, as it decides the paths where forwarding rules are placed to direct flows towards their endpoints. Single path routing has been widely used because of its simplicity, however, it is insufficient to satisfy QoS requirement, such as throughput [START_REF] Huang | The Joint Optimization of Rules Allocation and Traffic Engineering in Software Defined Network[END_REF]. Hence the adoption of multipath routing. Normally, forwarding rules are duplicated on each path to route flows towards their destinations. By choosing appropriate flow paths such that they transit on the same set of switches, forwarding rules on these switches can be compressed [START_REF] Huang | The Joint Optimization of Rules Allocation and Traffic Engineering in Software Defined Network[END_REF]. For example, flow F uses path P 1 = (S1, S2, S3) and P 2 = (S3, S2, S4) that have Switch S2 in common. On the latter switch, two rules that forward F to S3, S4 can be compressed into one rule match(F ) → select(S3, S4). Also, forwarding rules may contain the same source (e.g., ingress port), that can also be compressed [START_REF] Wang | Rule Optimization for Real-Time Query Service in Software-Defined Internet of Vehicles[END_REF].

Generally, OpenFlow switches have a default rule with the lowest priority that matches all flows. Forwarding rules can also be compressed with the default rule if they have the same actions (e.g., forwarding with the same interface) [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF]. Also, forwarding paths for flows can be chosen such that they leverage the default rules as much as possible. In this way, flows can be delivered to their destinations with the minimum number of forwarding rules.

Even though the actions field of a rule may contain several actions (e.g., encapsulate, then forward), the number of combinations of actions is much less than the number of rules and can thus be represented with few bits (e.g., 6 bits) [START_REF] Chiba | Source Flow: Handling Millions of Flows on Flow-based Nodes[END_REF]. Several studies [START_REF] Chiba | Source Flow: Handling Millions of Flows on Flow-based Nodes[END_REF], [START_REF] Iyer | SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks[END_REF] propose to encode the actions for all intermediate nodes in a list. This list is added to the header of each packet (e.g., using VLAN field [START_REF] Iyer | SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks[END_REF]) by the ingress switch. Afterwards, each intermediate node identifies its actions in the list (e.g., using pop VLAN action) and executes them. Finally, the egress switch recovers the original packet and forwards it to the destination. This idea is similar to IP source routing [START_REF] Postel | Internet protocol. STD 5[END_REF]. This approach allows decreasing significantly the number of forwarding rules in the core nodes, but at the same time, it increases the packet size headers of all packets.

3) Shortcomings of the Compression approach: The compression approach reduces the number of rules required, but it makes flows less visible since the wildcard rule is not used for a single flow and consequently, the controller cannot control a flow (e.g., monitoring, rate limitation) without impacting other flows. In many applications, one rule is required for each flow to ensure flow visibility and controllability [START_REF] Jin | Dynamic Scheduling of Network Updates[END_REF]. Moreover, finding a rule placement with high compression ratio may require high computation time [START_REF] Luo | Fast incremental flow table aggregation in SDN[END_REF].

First, in many scenarios, full control and visibility over all flows is not the right goal as only some important, significant flows need full control [START_REF] Curtis | DevoFlow: scaling flow management for high-performance networks[END_REF]. For example, load balancing requires handling long lived, high throughput flows. According to traffic analysis studies [START_REF] Benson | Network Traffic Characteristics of Data Centers in the Wild[END_REF], only a few percentages of flows (called elephant flows), send a large number of bytes and the rest of flows, send a small number of bytes. Therefore, wildcard rules [START_REF] Curtis | DevoFlow: scaling flow management for high-performance networks[END_REF] or default rules [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF] can be used to handle these flows locally on switches and dedicated rules are installed for elephant flows. In this manner, the number of rules required can be reduced, since according to the flow size distribution [START_REF] Benson | Network Traffic Characteristics of Data Centers in the Wild[END_REF], the number of elephant flows is much smaller than the number of other kinds of flows.

Second, even if each flow requires full control, usually only one exact-matching rule for the flow in the network is needed [START_REF] Iyer | SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks[END_REF], and on the rest of the flow path wildcard rules are used to handle it. In [START_REF] Iyer | SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks[END_REF], a solution is proposed to install an exact forwarding rule for the flow at the first switch, which usually consists in a software switch with a high capacity flow table. At intermediate switches, forwarding rules that have the same output actions can be compressed into one rule [START_REF] Chiba | Source Flow: Handling Millions of Flows on Flow-based Nodes[END_REF], [START_REF] Iyer | SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks[END_REF].

Other solutions [START_REF] Nakagawa | DomainFlow: Practical Flow Man-agement Method Using Multiple Flow Tables in Commodity Switches[END_REF], [START_REF] Agarwal | Shadow macs: Scalable label-switching for commodity ethernet[END_REF] leverage exact-matching tables (e.g., MAC forwarding tables), beside the wildcard matching flow tables in switches. More precisely, the network is divided into two domains: one where flows are controlled through wildcard rules and the other with exact-matching rules in these tables. The controller computes and defines the best tuning point (i.e., where the flow starts to use exact-matching rules) per flow basis.

Above solutions can reduce the number of forwarding rules while preserving exact matching rules for flow management (e.g., monitoring, rate limitation). However, the first hop switch is required to have high capacity and to perform intensive computations (e.g., packets header changes), which incurs performance penalty.

Compression also incurs computational overhead and slows down the network configuration update. Moreover, during the updating time, forwarding errors such as reachability failures and loops are susceptible to occur [START_REF] Luo | Fast incremental flow table aggregation in SDN[END_REF]. Therefore, to be efficient, compression algorithms must achieve a trade-off between compression ratio and update time. In general, most of compressed rules do not change during the update, so, the designed algorithm only needs to identify and re-compress the affected rules. An example of such an algorithm is iFFTA [START_REF] Luo | Fast incremental flow table aggregation in SDN[END_REF].

C. Split and Distribution

In general, a single switch does not have sufficient TCAM to store all rules. Therefore, the set of rules is usually split and distributed over the network in a way that satisfies policies. As shown in Fig. 6, the list of access control rules R1, R2, R3, R4 is split and distributed on the switches, according to the device

R1 R2 R3 R4 R1 R2 R4 R3 Switch 1 Switch 2
Software Switch F Fig. 6. An example of distribution approach. The list of access control rules R1, R2, R3, R4 is split and distributed, according to the device capacity and such that every flow in F passes through all the rules in the list.

capacity and such that every flow F passes through all the rules in the list.

The common approach to distribute rules is to formalize an optimization model that decides which rules are placed on which node, such that policy constraints, memory constraints, and rule dependency constraints are satisfied. The objective functions are flexible and depend on applications, such as to minimize the total number of rules needed [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF], [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF], [START_REF] Zhang | An Adaptable Rule Placement for Software-Defined Networks[END_REF], to minimize energy consumption [START_REF] Giroire | Optimizing rule placement in software-defined networks for energy-aware routing[END_REF], or to maximize traffic satisfaction [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF]. Since the rules placement problem is NP-hard in most of the cases, these studies also propose heuristics to obtain near optimal rules placement solutions.

We first show in Sec. IV-C1 the different options to distribute rules over a network composed of multiple commodity OpenFlow switches built around TCAM-based flow tables. Finally, in Sec. IV-C2 we present how elementary network functions can be performed by software switches or additional network devices to reduce the controller overhead without impairing the management flexibility offered by OpenFlow.

1) Rules distribution among commodity switches: a) Access control rules distribution: There are different solutions to split and distribute access control rules in Open-Flow networks [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF], [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF], [START_REF] Zhang | An Adaptable Rule Placement for Software-Defined Networks[END_REF], [START_REF] Katta | Infinite CacheFlow in Software-defined Networks[END_REF], [START_REF] Huang | Heterogeneous Flow Table Distribution in Software-defined Networks[END_REF].

The first challenge is how to split original access control rules into small, semantic equivalent subsets to fit in flow tables. The common approach is to represent access control rules as a directed dependency graph [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF], [START_REF] Katta | Infinite CacheFlow in Software-defined Networks[END_REF], [START_REF] Zhang | An Adaptable Rule Placement for Software-Defined Networks[END_REF], which can be decomposed into subgraphs (e.g., using Cut Based Decomposition algorithm [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF]), corresponding to subsets of rules that maintain original semantics. Other approaches propose splitting rules based on range [START_REF] Yu | Scalable flow-based networking with DIFANE[END_REF] or using the Pivot Bit Decomposition algorithm [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF].

The second challenge is how to distribute and assign these subsets of rules to switches. To that aim, linear programming models are formalized to assign subsets of rules to switches. Kanizo's model [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF] distributes rules over all shortest paths from ingress to the egress node, such that each flow passes through all access control rules. However, as shown in [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF], this approach is suboptimal for two reasons. First, only some paths require enforcing all access control rules. Second, their algorithm cannot use all available switches when the shortest path's length is small. In Kang's model [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF], paths are derived from the routing policy and only the rules that affect packets traversing that path is installed. Zhang's model [START_REF] Zhang | An Adaptable Rule Placement for Software-Defined Networks[END_REF] captures the rules dependency and accounts for the compression across rules from different ingress points to further reduce the number of rules required.

b) Forwarding rules distribution: Different forwarding rules distribution algorithms have been proposed to implement forwarding plane for different objectives ( [START_REF] Agarwal | Shadow macs: Scalable label-switching for commodity ethernet[END_REF], [START_REF] Iyer | SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks[END_REF], [START_REF] Nakagawa | DomainFlow: Practical Flow Man-agement Method Using Multiple Flow Tables in Commodity Switches[END_REF], [START_REF] Huang | The Joint Optimization of Rules Allocation and Traffic Engineering in Software Defined Network[END_REF], [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF], [START_REF] Giroire | Optimizing rule placement in software-defined networks for energy-aware routing[END_REF], [START_REF] Li | Morule: Optimized rule placement for mobile users in sdn-enabled access networks[END_REF]). The key challenge in forwarding rules distribution is how to select paths to install the forwarding rules that satisfy the policies and network constraints.

Path choice plays an important role in forwarding rules placement. Flows use rules on the paths to reach their endpoints and each path requires different rules. Some paths are more efficient than others; for example, the shortest hop paths are preferred because the minimum number of forwarding rules is needed [START_REF] Iyer | SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks[END_REF], [START_REF] Nakagawa | DomainFlow: Practical Flow Man-agement Method Using Multiple Flow Tables in Commodity Switches[END_REF]. The path choice also depends on the traffic engineering goals (e.g., energy efficiency [START_REF] Giroire | Optimizing rule placement in software-defined networks for energy-aware routing[END_REF]). As shown in Fig. 7, to satisfy the endpoint policy (i.e. flow F exits at E1), rules can be placed on two different paths, one path needs two rules R1, R2 and the other needs three rules R3, R1, R2. In this case, the former path is preferred since less memory is consumed.

Proposed studies can be classified into two groups: one group enforcing routing policy (e.g., using shortest paths) [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF], [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF], [START_REF] Zhang | An Adaptable Rule Placement for Software-Defined Networks[END_REF], [START_REF] Nakagawa | DomainFlow: Practical Flow Man-agement Method Using Multiple Flow Tables in Commodity Switches[END_REF], [START_REF] Iyer | SwitchReduce: Reducing switch state and controller involvement in OpenFlow networks[END_REF], [START_REF] Li | Morule: Optimized rule placement for mobile users in sdn-enabled access networks[END_REF], [START_REF] Wang | Rule Optimization for Real-Time Query Service in Software-Defined Internet of Vehicles[END_REF] and another group that does not [START_REF] Huang | The Joint Optimization of Rules Allocation and Traffic Engineering in Software Defined Network[END_REF], [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF], [START_REF] Moshref | vCRIB: Virtualized Rule Management in the Cloud[END_REF], [START_REF] Yu | Scalable flow-based networking with DIFANE[END_REF], [START_REF] Katta | Infinite CacheFlow in Software-defined Networks[END_REF], [START_REF] Giroire | Optimizing rule placement in software-defined networks for energy-aware routing[END_REF]. In the first group, the path is an input to the problem, while it is an output in the second group. Strictly following the routing policy (e.g., using shortest paths) sometimes is necessary to obtain the required performance (e.g., throughput, latency). However, the paths specified by the routing policy may not always have enough capacity to place all the necessary rules [START_REF] Nguyen | Optimizing Rules Placement in OpenFlow Networks: Trading Routing for Better Efficiency[END_REF]. Relaxing routing policy is suggested [START_REF] Nguyen | Optimizing Rules Placement in OpenFlow Networks: Trading Routing for Better Efficiency[END_REF] to improve resource utilization while respecting the endpoint policy.

But relaxing routing policy may lead to numerous possible paths. Therefore, path heuristics are used to select the path the flow will use. For example, Nguyen et al. [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF] choose the flow path such that it shares some segments with the default path formed by sequence of default rules on each node. In this manner, the flow can leverage default rules to reach the destination, thus reducing memory requirements.

However, a flow may not always be carried on a single path (e.g., because of bandwidth constraints). Paths can be chosen such that they satisfy the requirements while maximizing the number of nodes between them, so that all the forwarding rules required can be reduced thanks to compression [START_REF] Huang | The Joint Optimization of Rules Allocation and Traffic Engineering in Software Defined Network[END_REF]. In context of user mobility, paths can be predicted based on velocity and direction, and then forwarding rules can be installed on potential paths to avoid transmission interruption [START_REF] Li | Morule: Optimized rule placement for mobile users in sdn-enabled access networks[END_REF], [START_REF] Wang | Rule Optimization for Real-Time Query Service in Software-Defined Internet of Vehicles[END_REF], [START_REF] Dong | Rule caching in SDN-enabled mobile access networks[END_REF].

2) Rules distribution among commodity switches and additional resources: Studies presented in Sec. IV-C1 aim to distribute rules on commodity switches and cannot directly be applied to under-provisioned networks where memory budget, in particular with TCAMs, is limited [START_REF] Nguyen | Optimizing Rules Placement in OpenFlow Networks: Trading Routing for Better Efficiency[END_REF], [START_REF] Katta | Infinite CacheFlow in Software-defined Networks[END_REF]. In practice, some flows are more sensitive to network conditions than others. For example, flows from delay-sensitive applications (e.g., VoIP) require lower latency than best effort traffic (e.g., Web browser). As a consequence, one can allow some flows to be processed on low performance paths and let room for critical flows on high-performance paths.

Recent studies suggest placing rules on additional, inexpensive devices without TCAM (e.g., software switches) to offload the memory burden for commodity switches [START_REF] Moshref | vCRIB: Virtualized Rule Management in the Cloud[END_REF], [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF], [START_REF] Katta | Infinite CacheFlow in Software-defined Networks[END_REF]. The default rules on the commodity switches can be used to redirect flows that do not match any rule to these devices (e.g., the controller). These devices usually have large capacity (e.g., large flow tables implemented in RAMs), they are cheap to build (e.g., using Open vSwitch on a general purpose CPU [START_REF] Openvswitch | OpenvSwitch[END_REF]) but have limitations in forwarding and lookup performance, compared to commodity switches. An example is shown in Fig. 8; since Switch 1 does not have enough capacity to place all necessary rules (R1, R2, R3), the default rule RD1 is used to redirect flows to software Switch 2 for further processing. Flows from IP 1 pass through Switch 1 to reach E, while flows from IP 2, IP 3 pass through Switches 1, 2 to reach E.

With the support from additional devices, resources are split into two kinds: fast (e.g., TCAM matching) and default (e.g., software switch matching). Studies [START_REF] Moshref | vCRIB: Virtualized Rule Management in the Cloud[END_REF], [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF], [START_REF] Katta | Infinite CacheFlow in Software-defined Networks[END_REF] propose rules placement solutions that achieve the best trade-off between performance and cost. Basically, each rule is assigned an importance value, based on its priority and its dependency to other rules. Afterwards, linear programming models and heuristics are used to decide the most profitable rules to keep on commodity switches and the remaining rules to be installed on software switches. The aim of objective functions can be to minimize the redirection cost [START_REF] Moshref | vCRIB: Virtualized Rule Management in the Cloud[END_REF], or to maximize the whole values of rules installed on TCAM [START_REF] Katta | Infinite CacheFlow in Software-defined Networks[END_REF], [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF].

The split and distribution approach combines different types of resources to perform network-wide optimization and to reduce CAPEX. For example, a switch with a large flow table capacity can be more expensive than several switches with smaller flow tables. Most of the studies formalize an optimization model for rules placement to maximize or minimize an objective function while satisfying different constraints. The main advantage of this approach is the flexibility in objective functions it allows, and its capacity to handle many constraints in a single framework.

However, this approach usually induces a redirection overhead (e.g., redirecting packets causing a flow table miss to other nodes), computation overhead (e.g., solving the optimization model), or rules duplication. Some studies require prediction of the traffic matrix, or future location of users, to be able to solve some optimization models. Such an accurate prediction is costly, because it requires a large signaling overhead to collect network statistics and continuous calibration of the prediction model.

V. REDUCING SIGNALING OVERHEAD

As explained in Sec. III-C, the signaling overhead should not be neglected while solving the OpenFlow rules placement problem. Reducing the signaling overhead is a key factor to increase the scalability of any rules placement solution. In this section, we summarize the ideas that have been proposed to reduce the signaling overhead.

A. Reactive and Proactive rules placement

There are two approaches for rules placement in OpenFlow: reactive and proactive. 1) Reactive: With the Reactive approach, rules are populated on demand to react upon flow events. As stated in the OpenFlow specification [START_REF] Openflow | OpenFlow Switch Specification[END_REF], for each new flow, the switch enqueues the packet and informs the controller about the arrival of a new flow. Afterwards, the controller computes the rules to be associated with the new flow and installs them in the network. So normally, a new flow requires 2n messages, where n is the number of path hops. Once the rules are installed on the switches, packets are dequeued and forwarded in the network. Any subsequent packet of the flow will then be processed by the freshly installed rules without further intervention of the controller. An example of reactive rules placement is shown in Fig. 9, in which a flow is queued at two switches (Arrow 1, 4). Four OpenFlow messages are required, including two new flow messages (Arrow 2, 5) and two rule installation messages (Arrow 3, 6), to forward the packets of flows towards the endpoint E1 (Arrow 7).

Reactive rules placement is required to adjust network configuration continuously with the current network state. For example, a new coming flow requires the controller to setup the path, whereas a down link event requires the controller to reroute all the affected flows.

However, using a reactive approach for all the flows is not the right solution because the controller and the switch buffer may be overloaded, e.g., in presence of large number of new flows (e.g., 100k new flows per second in a cluster [START_REF] Kandula | The Nature of Data Center Traffic: Measurements & Analysis[END_REF]). Another drawback is the additional latency (e.g., 10ms to 20ms in data centers [START_REF] Curtis | DevoFlow: scaling flow management for high-performance networks[END_REF]). Therefore, the reactive approach should not be used for all flows.

2) Proactive: In this approach, rules are populated in advance, i.e., before the first packet of a new flow arrives. The proactive approach nullifies the setup delay of rules and reduces the overall number of signaling messages. An example of reactive rules placement is shown in Fig. 10. The controller installs rules for flow F 1 in advance (Arrow 1, 2), before the flow F 1 arrives (Arrow 3). So, two OpenFlow messages are required and there is no setup delay. This proactive approach is common in studies focusing on access control [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF], [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF], [START_REF] Zhang | An Adaptable Rule Placement for Software-Defined Networks[END_REF], [START_REF] Katta | Infinite CacheFlow in Software-defined Networks[END_REF], as access control rules are predefined by operators independently of the traffic. The same approach can be used to decide forwarding rules in the network but it requires predicting or estimating in advance, the traffic demand or the user location [START_REF] Giroire | Optimizing rule placement in software-defined networks for energy-aware routing[END_REF], [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF], [START_REF] Li | Morule: Optimized rule placement for mobile users in sdn-enabled access networks[END_REF], [START_REF] Huang | The Joint Optimization of Rules Allocation and Traffic Engineering in Software Defined Network[END_REF], [START_REF] Wang | Rule Optimization for Real-Time Query Service in Software-Defined Internet of Vehicles[END_REF]. In some practical situations, achieving accurate prediction is difficult as it incurs the collection of data and induces signaling messages [START_REF] Benson | MicroTE: Fine Grained Traffic Engineering for Data Centers[END_REF]. Therefore, the proactive approach is suitable only for the flows that can be predicted with high accuracy.

We classify the related work that uses proactive and reactive approach in Table III.

B. Delegating functions to OpenFlow switches

Rules placement solutions need to be frequently updated often to adapt with current network state. But updating network and collecting statistics incurs load on the controller (e.g., CPU, bandwidth, memory) when done frequently. In this section, we discuss several solutions that can be used to reduce the signaling overhead, Elementary network functions such as MAC learning and ICMP processing can be delegated to the switches, not only to reduce the signaling overhead, but also to keep basic network functions when controllers are not reachable [START_REF] Kreutz | Software-defined networking: A comprehensive survey[END_REF].

To reduce both signaling overhead and delay caused by new flow setup, several studies [START_REF] Curtis | DevoFlow: scaling flow management for high-performance networks[END_REF], [START_REF] Kreutz | Software-defined networking: A comprehensive survey[END_REF], [START_REF] Nakagawa | DomainFlow: Practical Flow Man-agement Method Using Multiple Flow Tables in Commodity Switches[END_REF] suggest delegating some functions to OpenFlow switches. Instead of querying the controller for each flow, switches can identify and process some flows (e.g., mice flows) and interrogate the controller when decisions are necessary.

Other mechanisms such as rule cloning and local actions also contribute to reduce the signaling overhead [START_REF] Curtis | DevoFlow: scaling flow management for high-performance networks[END_REF]. More precisely, rule cloning allows the switch to clone a rule from a pre-installed wildcard rule to handle a flow; local actions allows the switch to change the action field in rules, for example, fast re-routing to another path in case of link failures, without invoking the controller. Another approach is to use authority switches [START_REF] Yu | Scalable flow-based networking with DIFANE[END_REF], which are built on top of OpenFlow switches. Authority switches can be used to handle flow table misses from edge switches, thus keeping the packets causing misses in the data-plane.

On rule removal (e.g., because of a timeout), signaling messages are required to inform the controller. To reduce the removal and re-installation overhead, eviction mechanisms like LRU or timeouts (mentioned in Sec. IV-A) can be directly implemented on the switches to keep rules with high matching probability in the flow table while automatically freeing space for new flows, everytime without invoking the controller.

Rules placement is computed using statistics queried from the network. For example, by collecting the number of bytes sending so far, the controller can detect that some flows are elephant and then install forwarding rules using the shortest paths. In general, high accuracy inputs require intensive collection of traffic statistics.

To reduce the overhead due to the collection of statistics, the default pull-based mechanism (i.e., the controller requests and receives statistics) can be replaced by a push-based mechanism [START_REF] Curtis | DevoFlow: scaling flow management for high-performance networks[END_REF] (i.e., the switch pushes the statistics to the controller when defined conditions are satisfied, for example, when the number of packets exceeds a threshold). Another complementary solution is to replace current OpenFlow counters by software defined counters [START_REF] Mogul | You Darned Counters!: Get off My ASIC![END_REF], which support additional features such as data compression and elephant flows detection. In this manner, the statistics collection overhead can be further reduced.

Delegating elementary functions to switches is a way to reduce the signaling overhead between controllers and switches and to increase the overall scalability (e.g., the controller is less loaded) and the availability (e.g., basic network functionalities remain available upon controller failure). However, this approach requires more complex software and hardware than vanilla OpenFlow switches, which increases the cost of the device and may cause inconsistencies as each device makes its own decision [START_REF] Vissicchio | On the Co-Existence of Distributed and Centralized Routing Control-Planes[END_REF].

VI. FUTURE RESEARCH DIRECTIONS

Existing studies have proposed different solutions for various use cases, however, the OpenFlow rules placement problem is still a challenging research area with many remaining questions. In this section, we discuss some open questions that may be worth future research attention.

A. Hybrid rules placement

Rules can be placed in advance (proactive) or on demand (reactive). Each approach has pros and cons as discussed in Sec. V-A. We believe that an efficient rules placement solution should combine both proactive and reactive, to benefit from their respective advantages without having to pay the cost of their drawbacks. For example, using proactive mode for access control rules, predictable flows, and using reactive mode for non-predictable flows.

How to combine these two approaches, which flows, which switches use reactive or proactive mode, how to obtain the best trade-offs between them remain interesting questions.

B. Robustness and fault tolerance rules placement

Upon changes (e.g., policies, network topology, user mobility), the rules placement needs to be updated to adapt with varying network conditions. However, updating rules placement comes with the cost of computation overhead, signaling overhead, and setup delay. Most of proposed solutions recompute the rules placement to maximize or to minimize some performance metrics (e.g., total number of rules, energy consumption).

Robustness and fault tolerance should also be taken into account when designing rules placement solutions. For this purpose, robust optimization techniques [START_REF] Bertsimas | Theory and Applications of Robust Optimization[END_REF] might be a promising approach. Such techniques account for uncertainty in inputs and produce an output that is the best among all the possible inputs.

C. Impact of additional devices

Recently, additional devices such as controllers and software switches have been used to offload the memory burden of OpenFlow switches (see Sec.IV-C2). In such a case, default rules are often configured to redirect flow table miss from OpenFlow switches toward these devices [START_REF] Moshref | vCRIB: Virtualized Rule Management in the Cloud[END_REF], [START_REF] Katta | Infinite CacheFlow in Software-defined Networks[END_REF], [START_REF] Nam Nguyen | OFFICER: A general Optimization Framework for OpenFlow Rule Allocation and Endpoint Policy Enforcement[END_REF].

The impact of the additional devices location, the default rules on the efficiency of rules placement are not well understood. It would be interesting to combine the controller placement [START_REF] Heller | The controller placement problem[END_REF] and the OpenFlow rules placement problem to overall optimize the network.

D. Multilevel table rules placement

OpenFlow 1.0 uses a flat table model that cannot handle possible state explosion. To address this issue, OpenFlow 1.1+ [START_REF] Openflow | OpenFlow Switch Specification[END_REF] supports multi-level flow tables and pipeline processing. Consequently, a large flow table on a switch can be split into smaller flow tables with less entries. Furthermore, some rules require to be placed in TCAM tables while the remaining rules are placed in non-TCAM tables. The multitables feature has been implemented in commercial devices, such as NoviSwitch 1248 [START_REF] Noviflow | NoviSwitch 1248 High Performance Switch[END_REF].

How to benefit from multi-level architecture, how to leverage pipeline processing ability, which rules to place in which sub-tables should be taken into account for future research.

E. Network Function Virtualization

Networks today consist of a large number of various middleboxes and hardware appliances (e.g., Firewall, Deep Packet Inspection). Usually, launching a new service requires other hardware-based appliances, which increases the cost of investments, energy, integration, operation, and maintenance.

Network Function Virtualization (NFV) [START_REF] Chiosi | Network Function Virtualisation White Paper[END_REF] aims to replace network equipments by software-based functions on high volume servers, switches, and storage devices. NFV requires flexible routing, dynamic instantiations and placement of network functions, which can be provided by OpenFlow. More precisely, some network functions are possible to implement by placing appropriate rules in OpenFlow switches (e.g., firewall functions). Furthermore, forwarding rules can be placed on switches to redirect flows through different network functions. How and where to place network functions, how traffic is routed through them are key challenges towards the deployment of NFV. Indeed, NFV is a fascinating use case and new rules placement solutions must be designed to implement NFV.

VII. CONCLUSION Software Defined Networking and OpenFlow offer the ability to simplify network management and reduce costs by raising the level of network abstraction.

An abstraction layer between operators and the network is desired to transform the high-level policies from operators into low level OpenFlow rules. To that aim, it is important to solve the OpenFlow rules placement problem, that decide the OpenFlow rules that must be deployed and where to install them in order to efficiently use network resources, such as bandwidth and memory, while respecting operational constraints and policies.

In this survey, we present the body of the literature that investigates the OpenFlow rules placement problem. We first formalize the problem and identify two main challenges: resource limitations and signaling overhead. We then discuss existing ideas and solutions to solve these two challenges. Finally, we point out several research directions for further exploration.

Fig. 2 .

 2 Fig.2. An example of access control rules placement. The firewall policy is transformed into a list of rules R1, R2, R3 used to block matching packets and two default rules RD1, RD2 for forwarding non-matching packets towards endpoint E. Then, these rules are distributed on several switches to ensure that flows F1 and F2 pass through all rules R1, R2, R3 to satisfy the policy.

Fig. 5 .

 5 Fig.5. An example of compression. R2 and R3 have the same actions field and are compressed into a single rule R23 that has matching pattern covering both matching patterns of R2 and R3. Thus, rule space consumption is reduced while the original semantic is preserved.

Fig. 7 .FlowsFig. 8 .

 78 Fig.7. An example of path choice. To satisfy the endpoint policy (e.g., flow F exits at E1), rules can be placed on two different paths, one path needs two rules R1, R2 and the other needs three rules R3, R1, R2. In this case, the former path is preferred since less memory is consumed.

Fig. 9 .Fig. 10 .

 910 Fig. 9. An example of reactive rules placement. Rules are placed on demand, after flows arrive.


A Sinatra

Quantum correlations of two optical fields close to electromagnetically induced transparency

Keywords: numbers: 42.50.Dv, 42.50.Gy, 42.65.Pc

We show that three-level atoms excited by two cavity modes in a Λ configuration close to electromagnetically induced transparency can produce strongly squeezed bright beams or correlated beams which can be used for quantum non demolition measurements. The input intensity is the experimental "knob" for tuning the system into a squeezer or a quantum non demolition device. The quantum correlations become ideal at a critical point characterized by the appearance of a switching behavior in the mean fields intensities. Our predictions, based on a realistic fully quantum 3-level model including cavity losses and spontaneous emission, allow direct comparison with future experiments.

Using optical nonlinearities it is possible to manipulate optical beams to the level of quantum fluctuations, producing squeezed states [START_REF] Bachor | A Guide to Experiments in Quantum Optics[END_REF] that are important resources for quantum information with continuous variables [START_REF] Braunstein | [END_REF]. Related to the field of squeezing is that of quantum non demolition (QND) measurements on an optical field, where quantum correlations between two different modes of the electromagnetic field are exploited to overcome the back-action noise of a quantum measurement [3]. Besides the fundamental interest in the theory of measurement, it was shown that QND correlations of propagating beams have direct application in quantum communication protocols as teleportation [4]. The best single back-actionevading measurement on optical beams was performed using cold atoms inside a doubly resonant cavity [5]. We suggest that these performances could be significantly improved by tuning the system close to the electromagnetically induced transparency (EIT) conditions [6].

Already in the nineties, theoretical studies showed that a lambda three-level medium close to EIT conditions in a cavity can be used to obtain squeezing [7]. Contrarily to previous proposals, here we assume that two different modes are resonant in the cavity. For small and symmetrical detunings from the upper level of Λ three-level atoms (see Fig. 1), absorption is suppressed and the dispersive non linear response gives rise to a rich scenario where either self correlations (squeezing) or cross QND correlations can be established in the output beams. The correlations become ideal at a critical point that we characterize analytically. The technique we propose is experimentally accessible, and first experimental steps in this directions were done in atomic vapors without a cavity [8]. Here we show that the presence of the cavity is a crucial advantage especially if one can reach the good cavity limit.

We consider N atoms in a cavity excited by two modes symmetrically detuned from the upper level of a Λ threelevel scheme as in Fig. 1. For j = 1, 2 let ω j be the frequency of field j and hω aj the energy of the corresponding atomic transition. We define ∆ j = ωaj -ωj γw the atomic detunings normalized to the decay rate of the optical coherences γ w = (γ 1 + γ 2 )/2 where γ 1 + γ 2 is the total population decay rate of the upper level; θ j = ωcj -ωj κj the cavity detunings normalized to the cavity decay rates κ j , and

C j = g 2 j N
γwκj the cooperativities where g j are the coupling constants for the two considered transitions. We use normalized variables proportional to the intracavity and input fields x j = √ 2gj γw a j and y j = √ 2gj γw

2

√ Tj E in j respectively, where T j is the (input-output) mirror transmissivity for the field j. We name v and w the normalized polarizations between levels 1-3 and 2-

3 v = -( √ 2/N ) R -, w = -( √ 2/N ) S -
where R and S are collective operators constructed from the single atom operators |1 3| and |2 3| as in [START_REF]Lugiato Progess in Optics XXI[END_REF]. The master equation and the semiclassical equations describing the Λ system with two cavity fields, with the same notations introduced here, are given and discussed in detail in [START_REF] Sinatra | [END_REF] where this model was successful to reproduce the experimental results of [5].

Let us consider a set of parameters symmetric for the two transitions: |y j | = |y|, C j = C, γ j = γ, κ j = κ, θ j = 0 (empty cavity resonance for both fields), and let ∆ 1 = -∆ 2 = ǫ be small and positive. In Fig. 2 A stable branch of this solution appears for Y > 1. The negative slope branch and the lower branch very close to zero intensity are both instable and play no role in the following. For Y < 1, apart from the solution I 1 = I 2 , we get two other solutions with I 1 = I 2 . In the figure we show one of them with I 1 > I 2 . The second one is obtained by exchanging I 1 and I 2 . Both solutions are stable in the considered case θ 1 = θ 2 = 0.

We choose now two values of the input intensity, in turn above and below the turning point Y = 1, and show the stationary solutions for intracavity fields intensities as the cavity detunings vary in Fig. 3. The stable branches of these curves (thick lines) can be easily obtained experimentally by sweeping the cavity length [START_REF] Sinatra | [END_REF]. We vary θ 1 and θ 2 keeping them always equal which would imply the use of two driving fields of close optical frequencies ∆λ/λ ≪ 1 (and for example different polarizations). For Y = 1.05 i.e. 5% above the turning point (upper half of Fig. 3) the stable solutions for the intracavity intensities are Lorentzian-looking curves symmetrically shifted by a small amount from their empty-cavity positions for both fields. Only for θ 1 = θ 2 = 0 the two fields have the same stationary amplitude in the cavity corresponding to the stable high-transmission branch of the S-shaped curve in Fig. 2. For Y = 0.95 i.e. 5% below the turning point (lower half of Fig. 3) the situation is rather different: the stable solution for the two fields switches between a high-intensity and a low-intensity curve being always I 1 = I 2 although |y 1 | = |y 2 |. In contrast with the previous case this situation is very far from the independent-fields EIT solution and the fields are in fact strongly coupled.

Let us now introduce the usefull correlations to caracterize the quantum fluctuation properties of the system. For a given quadrature of the j th field: X φ j = a j e -iφ + ia † j e iφ , the squeezing spectrum is defined as

S φ j (ω) = 1 + 2κ j ∞ -∞ e -iωt : δX φ j (t) δX φ j (0) : dt (1)
where δX φ j denotes the time dependent fluctuation of the operator X φ j around a steady state point. The column indicates normal and time ordering for the product inside the mean. S φ j = 1 is the shot noise and S φ j = 0 means total suppression of fluctuations in the quadrature X φ j . The crossed correlations between the two fields are described by the coefficients C s , C m and V s|m [11] characterizing a QND measure of the amplitude quadrature X in of one field, the signal, performing a direct measurement on the phase quadrature Y out of the other field, the meter. Among the three coefficients C s quantifies the non-destructive character of the measurement, C m its accuracy and V s|m refers to the to the "quantum state preparation" capabilities of the system.

C s = C(X in , X out ) , C m = C(X in , Y out ) , (2) V s|m = X out , X out 1 -C(X out , Y out ) (3)
where for two operators A and B we define

C(A, B) = | A, B | 2 A, A B, B with (4) A, B = +∞ -∞ e -iωt 1 2 A(t)B + BA(t) dt . (5)
Superscripts in and out refer to the input and output cavity fields. By calling φ in j and φ out j the phases of the input and output fields in steady state, and choosing field 1 as the meter and field 2 as the signal, we define

X out(in) = X φ out(in) 2 2 and Y out = Y φ out 1 +π/2 1
. For an ideal QND measurement C m = C s = 1, and V s|m = 0.

The quantum fluctuations counterpart of Fig. 3 (top) is shown in Fig. 4 (top) where squeezing of the output fields optimized with respect to the quadrature S best j (ω = 0) is plotted as a function of the cavity detuning. A large amount of squeezing is present in both fields close to θ 1 = 0. As one can see from Fig. 3 (top) the two fields are well transmitted by the cavity for θ 1 = 0, and the system efficiently converts the input coherent beams into bright squeezed beams. Correspondingly to Fig. 3 (bottom) for Y = 0.95, in Fig. 4 (bottom) we plot the coefficients C s , C m and V s|m across the cavity scan. The useful quantum correlations are calculated by a linearized treatment of quantum fluctuations around the stable stationary solution as in [START_REF] Sinatra | [END_REF]. Despite the fact that the two fields have different intracavity intensities at θ 1 = 0, they play here symmetrical roles for the QND scheme; the figure corresponding to the reversed scheme 1 ↔ 2 being obtained by reflection of the plots θ 1 ↔ -θ 1 . We show in Fig. 5 the frequency dependence of the quantum correlations both below and above the turning point Y = 1, for a fixed value of the cavity detuning close to zero. For values of the cooperativity parameters currently obtained in experiments, QND coefficients such as C s = 0.98, C m = 0.95, V s|m = 0.05 can be acheived in this regime, representing a significant improvement with respect to previously obtained results [5] based on the so called "ghost transition" scheme [12], [START_REF] Sinatra | [END_REF]. Although we concentrate here on the good cavity limit, in which as we will show the quantum correlations become ideal approaching the turining point Y = 1, some QND correlations between the two modes persist also in the bad cavity limit. For example for ǫ = 0.25, C = 25, κ = 3γ, θ 1 = 6 × 10 -3 , Y = 0.9 and ω = 0.1γ we get C s = C m = 0.72, V s|m = 0.26.

In the limit of weak atomic detunings, useful analytical results can be obtained. The analytical solution of the semiclassical equations of the system at steady state is given in [START_REF] Sinatra | [END_REF]. By expanding the steady state polarizations v and w to the first order in ǫ we obtain

v = i 4ǫ x 1 |x 2 | 2 (|x 1 | 2 + |x 2 | 2 ) 2 w = -i 4ǫ x 2 |x 1 | 2 (|x 1 | 2 + |x 2 | 2 ) 2 . (6)
By inserting (6) in the equations for the intracavity fields amplitudes, with |y j | = |y|, θ j = 0 and C j = C, we obtain at steady state a "universal solution" for rescaled field intensities. For Y < 1 there are two stable solutions

I 1 = Y 2 (1 ± η) ; I 2 = Y 2 (1 ∓ η) (7)
where η = √ 1 -Y 2 . For Y > 1, out of two solutions

I 1 = I 2 = I ; I = Y 2 1 ± 1 - 1 Y 2 (8)
the one with the plus sign is stable and the other one unstable. Solutions ( 7)-( 8) are indistinguishable from those of the full three-level model in Fig. 2. The phases of the input fields with respect to intracavity fields (which are taken real at steady state) are φ in 1 = atan I 2 /I 1 , φ in 2 = -atan I 1 /I 2 for Y < 1, and

φ in 1 = atan [1/2I] = -φ in 2 for Y > 1. For the output fields φ out 1 = -φ in 1 , φ out 2 = -φ in 2 in both cases.
In order to study the quantum properties of the system analytically we further assume that (i) γ ≫ κ so that the atomic fluctuations follow adiabatically the field fluctuations, and (ii) the noise from spontaneous emission is negligible, which we found true when the cooperativity is large enough. In this limit, using the steady state polarizations (6), we can solve analytically the equations for the field fluctuations and obtain the correlation functions.

For Y > 1 and I 1 = I 2 = I and taking κ -1 as the unit of time, we obtain

δ ẋj = -δx j + i (-1) 3-j 2I δx * j j = 1, 2 . (9)
These equations describe two independent two-photon processes for which instabilities and squeezing have been studied extensively [13]. The best squeezing spectrum for each field is

S best j (ω) = 1 - 4a (1 + a) 2 + ω/κ 2 , a = 1 2I , (10)
yielding perfect squeezing at zero frequency at the turning point where Y = 1, I = 0.5 and a = 1. For Y < 1 and I 1 = I 2 the fluctuations of the two fields are coupled. For I 1 > I 2 we get

δX 1 = -δX 1 -i 1 -η Y δY 1 (11)
δY 1 = -δY 1 + i 1 + η Y δX 1 -2i ηδX 2 . (12)
The equations for field 2 are obtained from ( 11) and ( 12) by changing the sign in front of η and of i. Simple analytical expressions can be obtained for the squeezing and the conditional variance V s|m of the fields at ω = 0

S int j = S best j = 1 ; S phase j = -3 + 4 η 2 (13)
V s|m = η 2 4 -3η 2 (14)
showing that the fields have diverging phase noise and become perfectly correlated at the turning point. We checked that the spectra in Fig. 5 are well reproduced by the analytical results.

In conclusion, in a symmetrically detuned EIT scheme, and for equal input intensities Y of the two fields we have shown the existence of a universal S-shaped steady state curve (Fig. 2) which divides the parameter space into two parts: for input intensities higher than the upper turning point of the curve, the quantum fluctuations of the fields become quadrature dependent and can be reduced in a quadrature, while for input intensities lower than the turning point, crossed phase-intensity quantum correlations build up between the two fields. The system becomes a perfect "squeezer" or an ideal QND device at the turning point. The "universal" point Y = 1, can be identified experimentally by the appearance of the switching behavior described in Fig. 3, and can be used as a reference in the parameter space to choose either the squeezing or the QND effect and to optimize it. An implementation using either a vapor [8], or a trapped cold atoms in an optical cavity [5], [14], [15] seems within the reach of present technology.

2 FIG. 1 :

 21 FIG.1: Two cavity modes interact with the atoms in a Λ configuration close to EIT conditions.

2 FIG. 2 :

 22 FIG. 2: Stationary intensities of the intracavity fields I1, and I2 as a function of the common intensity of the input fields Y1 = Y2 = Y . In solid line the solution I1 = I2. The thick (red thin) line correspond to stable (unstable) solutions. In dashed-dotted line one of the two stable solutions with I1 = I2. Parameters: 2ǫ = 0.125 and C1 = C2 = 250, γ1 = γ2 = 10κ1, κ2 = κ1, θ1 = θ2 = 0.

1 FIG. 3 :

 13 FIG. 3: Intracavity field intensities I1 (left half), I2 (right half) across the cavity scan. Upper half: Y = 1.05. Lower half: Y = 0.95. The thick (red thin) lines correspond to stable (unstable) solutions. The other parameters are as in Fig. 2.

1 FIG. 4 :

 14 FIG. 4: Top: Best squeezing of the fields across the cavity scan for Y = 1.05 and ω = 0. Squeezing of field 1 (2) is plotted with a solid (dashed) line. Bottom: QND coefficients across the cavity scan for Y = 0.95 and ω = 0. Cm (red dashed-dotted line), Cs (solid line), V s|m (blue dashed line). Parameters as in Fig.3.

FIG. 5 : 1 1

 51 FIG. 5: Top: Squeezing spectra of field 1, for Y = 1.05 in the center of the cavity scan (θ1 = 0.0013). Best squeezing in solid line and amplitude squeezing S φ out 1

I thank L. Lugiato and P. Grangier for useful discussions, M. Guerzoni for her contribution to this work and Y. Castin for comments on the manuscript. LKB is UMR 8552 du CNRS de l'ENS et de l'UPMC; support from IFRAF is acknowledged.