Ahmad Abboud
email: a.abboud@numeryx.fr

Rémi Garcia
email: rgarcia003@enseirb-matmeca.fr

Abdelkader Lahmadi

Michaël Rusinowitch

Adel Bouhoula
email: a.bouhoula@numeryx.fr

Efficient Distribution of Security Policy Filtering Rules in Software Defined Networks

Keywords: Packet filtering, Software defined networks, Rule placement

Software Defined Networks administrators can specify and smoothly deploy abstract network-wide policies, and then the controller acting as a central authority implements them in the flow tables of the network switches. The rule sets of these policies are specified in the forwarding tables, which are usually accessed using very expensive and power-hungry ternary content-addressable memory (TCAM). Consequently, a given table can only contain a limited number of rules. However, various applications need large rule sets to perform filtering on diverse flows. In this paper, we propose several algorithms for decomposing and distributing a rule set on network switches of limited flow tables size, while preserving the network policy semantics. Through experiments on several rule sets with single and multiple dimensions, we evaluate and analyse the performance of our rule placement techniques. Our results show that our proposals are efficient in practice.

I. INTRODUCTION

In software-defined networks (SDN), the filtering requirements for critical applications often vary according to flow changes and security policies. SDN address this issue with a flexible software abstraction, allowing simultaneous and convenient modification and implementation of a network policy on flow-based switches. This single-point deployment approach constitutes a key feature for complex network management operations.

The growing number of attacks coming from diverse sources continually increasing the number of entries in access-control lists (ACL). To avoid relying on large and expensive memory capacities in network switches, a complementary approach to rule compression [START_REF] Abboud | Double mask: An efficient rule encoding for software defined networking[END_REF], [START_REF] Sun | Tree-based minimization of TCAM entries for packet classification[END_REF], [START_REF] Bremler-Barr | Space-Efficient TCAM-Based Classification Using Gray Coding[END_REF] would be to use multiple smaller switch tables to enforce in the network the accesscontrol policies. It paves the way towards distributed accesscontrol policies, which have been the topic of many previous studies [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] Chuprikov | How to implement complex policies on existing network infrastructure[END_REF]. However, most of them have a large rules replication [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] or even they modify the header of the packet [START_REF] Chuprikov | How to implement complex policies on existing network infrastructure[END_REF] to avoid the matching of a rule by a packet in the next switch.

In this work, we tackle the problem of rule-placement of ACLs, while focusing on three major challenges:

• Simplicity and efficiency of rule set decomposition to facilitate security policy deployment and updating; • Decomposition over diverse network topologies;

• Decomposition of complex network policies. In this paper we introduce new techniques to decompose and distribute filtering rule sets over a given network topology. Our approach is to design decomposition schemes for both simple and complex policies relying on a single or multiple dimensions, leading to multi-level network architectures to forward packets to the destination.

Like OBS [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF] and Palette [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF], we rely on rule dependency relations, but we generate less forward rules by taking the action field into consideration. Indeed, a packet is allowed to be matched by rules with two prefixes from successive switches, if their resulting action does not violate the initial policy semantics.

In the following sections, we introduce efficient decomposition and distribution algorithms for network policy management as well as the decomposition possibilities related to different topologies. Section II introduces some related work on the rule placement problem. In Section III, we state the general principles and distribution constraints in this problem. In Section IV, we perform a forward table decomposition using the commonly used Longest Prefix Matching (LPM) priority strategy in OpenFlow [START_REF] Mckeown | Openflow: Enabling innovation in campus networks[END_REF] wildcard matching. Section V details the distribution of rule tables with respect to relative positions of neighbour devices. In Section VI, we generalize the decomposition problem with filtering on multiple dimensions and arbitrary rule priority strategies. Section VII presents benchmarks and comparisons with the previous frameworks [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] Chuprikov | How to implement complex policies on existing network infrastructure[END_REF], using their and our own rule sets. We present our conclusions in Section VIII.

II. RELATED WORK

The decomposition of rules can be specific to application requirements regarding the matching fields. Some work aims to reduce the total number of rules used after the decomposition whereas others try to minimize energy consumption or maximize traffic satisfaction [START_REF] Nguyen | Rules placement problem in openflow networks: A survey[END_REF].

The type of rule sets used in each approach has a significant impact on the decomposition. Normally, in order to match a packet with a set of rules we use two strategies either according to the order of rules in a prioritized list, or according to the longest matching prefix (LPM).

Using a prioritized list, OBS [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF] tries to decompose rules using a two-dimensional endpoint policy. In their approach, overlapping rules lead to their replication in multiple switches. An optimization for choosing the best coverage on twodimension representation is proposed in [START_REF] Li | Hybridcuts: A scheme combining decomposition and cutting for packet classification[END_REF], in order to improve the storage and the performance of the decomposition of rules. More optimizations have been done in [START_REF] Li | Cutsplit: A decision-tree combining cutting and splitting for scalable packet classification[END_REF], [START_REF] Fong | Parasplit: A scalable architecture on fpga for terabit packet classification[END_REF], in order to choose the best cut while minimizing the tables size, the rule duplication and the pre-processing time for rule updates.

Using another approach, Palette [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF] proposes two methods for splitting a set of rules, the first one being called Pivot Bit Decomposition where a table can be divided in two subtables, by changing a wildcard bit "*" to 0 or 1 in each table. The second method called cut-based decomposition relies on a dependency graph to represent a set of rules. In this method each graph should be placed in the same switch, which can cause problems with large graphs due to a high number of overlapping rules.

A dependency graph has been introduced in [START_REF] Katta | Infinite cacheflow in software-defined networks[END_REF], in order to divide rules into two parts for an OpenFlow environment. The first part is cached and the second is deployed while preserving the semantics of the policies.

A near-zero decomposition overhead technique has been proposed in [START_REF] Chuprikov | How to implement complex policies on existing network infrastructure[END_REF]. This technique is based on adding an additional bit to the packet header. When a packet has matched a rule, this bit ensures that the packet will not be processed again. While costing only a bit per rule and in the packet, this stateful technique requires non standard modifications on the packet structure and leads to security issues when an attacker could manipulate this additional bit to bypass the filtering mechanism.

The rule distribution problem has been studied in [START_REF] Kannan | Raptor: Scalable rule placement over multiple path in software defined networks[END_REF] where a predefined set of rules can be shared by multiple paths across the network.

Our work shares with these previous works the problem of distributing a rule set among network switches to meet a policy. However, in our approach we rely on the properties of the LPM strategy and leverage action field information in order to handle overlapping rules and avoid replication in switch tables. Unlike [START_REF] Chuprikov | How to implement complex policies on existing network infrastructure[END_REF] we do not apply packet or rule modifications. In addition, we also exploit the structure of a series-parallel graph to resolve efficiently the rule placement problem for all-sized networks in tractable time, unlike many existing approaches [START_REF] Kannan | Raptor: Scalable rule placement over multiple path 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] that relies on Integer Linear Programming (ILP) techniques.

III. PROBLEM STATEMENT A. Problem definition

We consider a network N with SDN-enabled switches that are connected to each other using their respective ports. Each switch can store in its flow table different types of accesscontrol and filtering rules. Each flow table has a limited capacity regarding the number of stored rules. We assume that an SDN policy is a collection of rules generated by an administrator or by an external module. The size of the set of rules of the policy exceeds the capacity of a single switch table.

In this paper, we are mainly concerned by decomposing and distributing a set of filtering rules along the switches in the network N to accomplish an SDN policy while preserving its overall semantics and meeting the capacity limitation of each switch. In the network N , packets are controlled by rules stored in their Forward Information Bases or flow tables. A rule is specified by a priority, matching patterns on packet fields and an action. A matching pattern of a source (resp. destination) field is given by a list of 0, 1 followed by * 's (don't care bits), of global length w (word length) called a prefix p. Any bit matches wildcard character * . A rule with prefix p for source (resp. destination) applies to a packet if this packet source (resp. destination) field matches p, bit by bit. We call bit-prefix of the rule the sub-list of 0, 1 of p.

The matching process for a given set of rules can follow different strategies. A simple strategy prioritizes the rules by their order in the rule set. A packet matching the first rule will apply the action of that rule without considering the following ones. With a Longest Prefix Matching (LPM) strategy, one packet can match multiple rules, but only the one with the most specific matching prefix (i.e., the longest prefix) will be selected. In the example shown in Table I, if a switch receives a packet with 0001 as address, and using a prioritized list strategy, action A 1 of the first rule is applied. However, with an LP M strategy, the packet matches both rules 1 and 2, but only action A 2 will be applied since rule 2 covers the address field with a longer prefix.

Rule

Address field Action

1 0 0 * * A 1 2 0 0 0 * A 2

B. Distribution and decomposition requirements

To ensure that distributing the rules along different switches does not change the initial policy compared to a single-switch placement, we must preserve its overall semantics, i.e., the action applied on a matched packet in a single switch with the initial policy rule set should be the same action in a chain of switches with the distributed policy rule set. Here, we consider that filtering rules have two possible actions: "Forward" or "Deny". In the following, the prefix of a rule r is denoted by P ref (r) and its action by Action(r). If P ref (r 1 ) matches P ref (r 2 ) and has a shorter bit-prefix than P ref (r 2 ), like Rule 1 with Rule 2 in Table I, then we say that r 1 > r 2 or r 1 overlaps r 2 . In the example of Table I, it is also true that P ref (r 1 ) is the next longest matching prefix i.e there is no r such that r 1 > r > r 2 . We express this by r 1 >: r 2 .

Let R be the initially given rule set of a policy. Let R 1 and R 2 be two subsets of R located in different switches along a path, with R 2 being located in a switch after the one of R 1 as illustrated in Fig. 1.

When applying the LP M strategy in a switch, a packet must be processed by the most specific matching rule. Thus,

S0 S1 S2 C=6 C=6 C=6
Fig. 1: Flow table capacities of switches along a single path.

if r 2 ∈ R 2 , there must not exist any r 1 ∈ R 1 such as r 1 > r 2 . To enforce this precedence property, when we place a rule r in a switch, we must also place in the same switch any rule r such as r > r .

When a packet has been accepted by a switch containing rule set R 1 and enters a switch containing rule set R 2 , if r 1 and r 2 are matching rules in R 1 and R 2 respectively, and r 2 > r 1 then r 2 should not block it. Thus, we must prevent blocking a packet when there is an action conflict. Given two rules r 1 ∈ R 1 and r 2 ∈ R 2 , we have an action conflict iff r 2 >: r 1 , Action(r 1 ) = "F orward" and Action(r 2 ) = "Deny".

In this work, we rely on forward rules to solve action conflicts: if two conflicting rules r 1 and r 2 belong respectively to two successive switch tables R 1 and R 2 , a rule f w with Action(f w) = "F orward" and P ref

(f w) = P ref (r 1 ) is added to R 2 .
When the policy preserving condition is respected, P ref (f w) has a higher specificity, thus priority, than P ref (r 2 ) by construction.

When decomposing R into subsets to be stored in the different switches and adding forward rules to solve action conflicts, the decomposition problem is formulated as a Bin Packing problem with fragmentable items [START_REF] Lecun | Bin packing with fragmentable items: Presentation and approximations[END_REF] where each fragmentation induces a cost.

IV. DECOMPOSITION OVER A PATH

Networks often have a blacklisting policy which specifies that packets originating from certain IPs are potentially harmful and need to be dropped, for instance when handling denial of service attacks [START_REF] Ferguson | Network ingress filtering: Defeating denial of service attacks which employ ip source address spoofing, bcp 38, rfc 2827[END_REF]. Thus, in a first step, we resolve the decomposition problem with a single filtering field and by using an LPM strategy, which could be sufficient for placing a blacklisting policy in the network.

A. Rule representation

We use a binary tree to represent the rules ordered by their prefix specificity. We study the single field case, so each rule contains one filtering field and there is at most one rule associated to a tree node. The sequence of edge labels taken from the root to a node represents the bit-prefix of the rule linked to this node. As shown in Fig. 2, the pattern 00 * of a rule r is at distance 2 from the root, reachable through the leftmost branch of the tree.

The complete prefix with wildcards of a node n represents a rule pattern. It is denoted as N odeP ref ix(n) and is equal to P ref (r), when a rule r is contained in n. We denote by f w(n) the forward rule with a matching pattern N odeP ref ix(n).

Once the rules are distributed among the switches, if in any switch no matching rule is found for an incoming packet, the packet will be forwarded to the next switch using a default rule.

B. Forward rules generation

We assume the set of rules R has been distributed along successive switches s 1 , . . . s n forming a path in the network graph. For this distribution to be correct with respect to the initial R and LP M semantics, we need to introduce additional forward rules in some switches.

The forward rule generation is illustrated in Fig. 3, where we install half of a rules in the first switch. For the first switch, we have selected rules with 00** as common prefix, so accepted packets with an IP matching this pattern must be accepted in the second switch. Thus, we have generated a forward rule with prefix 00** in the second switch. A default forward rule has also to be added to the first switch to allow the second one to receive any unmatched packets.

Given a set of rules R, two rule prefixes p 1 = w0 * , p 2 = w1 * can be merged to obtain a forward rule prefix p = w * . This operation can be iterated.

Fig. 4 illustrates a rule tree with merging possibilities. This tree contains 4 rules with prefixes 00 * , 01 * , 1 * , 10 * . We iteratively merge 00 * and 01 * to form a prefix 0 * , which is merged then with 1 * into a common forward prefix. In this example, only one forward rule is needed for this set. As shown in Fig. 4, the forward rule covers the subtree with rules at every branch above the blue line.

The set of resulting prefixes obtained by iterating the merging operation in R and that are maximal for > is called M axF wdM erges(R).

On a filtering path of length n, let R i be a rule subset placed in switch s i , 0 < i < n. The potentially necessary forward rules in s i+1 , i + 1 ≤ n after adding rules in s i is composed of successive M axF wdM erges results and called P otentialF wds. Considering R i+1 , only forward rules needed to resolve action conflicts with R 1,...,i are added in s i+1 . Thus, the forward rule set needed in switch s i+1 is a subset of P otentialF wds. If a prefix covers only deny rules in R, packets matching this prefix in s i will not travel to the next switch. Such a prefix is not added to P otentialF wds of s i+1 since there will be no packet to match.

C. Decomposition algorithm

Let us consider the binary tree shown in Fig. 5 which represents an ordered rule set. As an illustration example, each node contains one rule and we need to decompose the rule set along the path shown in Fig. 1. In this path, each switch has a maximal capacity of 6 rules. If we take into account the default rule in each switch, we need to find a set of 5 rules in order to completely fill the first switch. As depicted in Fig. 5, we select the set of nodes containing a total of 5 rules maximum (all nodes in red). After this selection step, all rules added to the switch will be removed from the binary tree. If some space remains in the switch, we will try to find rules candidate. Fig. 5: Choosing a set of candidate rules from the binary tree to be placed in a switch.

The rule distribution is performed in one pass following a bin-focused approach and a Minimum Bin Slack heuristic [START_REF] Gupta | A new heuristic algorithm for the one-dimensional bin-packing problem[END_REF]. Thus, each switch is filled as much as possible with a set of rules while trying to minimize the overhead caused by action conflicts with rules in previous switches. The required extra forward rules in switch i for a rule set R i is defined as N eededF wds(R i , P otentialF wds) = {f wd ∈ P otentialF wds | ∃r ∈ R i such that r >: f wd∧Action(r) = "Deny"}.

Algo. 1 is firstly called with an empty P otentialF wds and it describes the decomposition of a given rule set over switches in a single path.

The function ChosenCandidates searches in the rules tree R for a rule subset R i that can fit in switch s i , and has a maximal |R i | -|N eededF wds(R i , P otentialF wds)| value.

Algorithm 1 DecPath(R, s 1 , s 2 , . . . , s k , P otentialF wds) Input: set of rules R, k switches s i of capacities c i , set of forward rules P otentialF wds Output: ChosenRules, the rules added to the k switches; R, the remaining rules; P otentialF wds, the forward rules computed after adding ChosenRules.

1: Let ChosenRules ← ∅ 2: for i = 1 to k do 3:
Add a default forward rule to s i 4:

Let R i ← ChosenCandidates(R, s i , P otentialF wds) 5:

ChosenRules ← ChosenRules ∪ R i 6:

Add R i ∪ N eededF wds(R i , P otentialF wds) to s i , replacing the default forward rule if R i contains the default rule 7:

P otentialF wds ← M axF wdM erges(R i ∪ P otentialF wds) 8: R ← R \ R i 9: end for 10: return R, P otentialF wds, ChosenRules

D. Algorithmic complexity

When building the rules tree, we can efficiently add information that will speed up the set selection part. That way, we record with every node i) the number of rules in its subtree, ii) whether this subtree is a blacklist, and iii) whether this node prefix is a valid result of prefix merges. When a rule r is inserted in a given node t n , every parent of t n can update these variables in O(w) since w (word length) is an upper bound for the length of the bit-prefix of r. The rule tree construction part is then achieved in O(nw) time.

Selecting the rules to be stored in a switch requires at most an entire tree traversal in O(nw) time. Given a node prefix p, searching for a rule conflict with it can be done in O(w) time, as the forward rules can also be represented in a tree data-structure. The decomposition can be done in O(nw) time for every switch.

We adopt a greedy approach where the potential forward rules tree representation of O(nw) size is the main runtime memory cost.

V. DECOMPOSITION OVER A GRAPH

In this section, we present a technique to enforce the same filtering policy across all paths in the network. We present our algorithm for distributing a set of rules on a network whose topology is a two-terminal series-parallel graph [START_REF] Duffin | Topology of series-parallel networks[END_REF]. This algorithm is not specific to LPM, it can be used on all types of rule matching strategies and with any dimensions. Then we will show how to handle more general two-terminal directed acyclic graphs.

A. Decomposition over a two-terminal series-parallel graph

Series-parallel graph are widely used in telecommunication networks [START_REF] Flocchini | Routing in series parallel networks[END_REF], since the failure of a network part can be mitigated by using a parallel path, especially in critical applications with low tolerance to network paths failure. These types of networks can be updated in order to easily add or remove some parts by dividing the network into parallel or series compositions. Definition 1. A two-terminal directed acyclic graph (st-dag) has only one source s and only one sink t. A series-parallel(SP) graph is an st-dag defined recursively as follows: (i) A single edge (u, v) forms a series-parallel graph with source u and sink v. (ii) If G1 and G2 are series-parallel graphs, so is the graph obtained by either of the following : (a) Parallel composition: identify the source of G 1 with the source of G 2 and the sink of G 1 with the sink of G 2 . (b) Series composition: identify the sink of G 1 with the source of G 2 .

A two-terminal series-parallel graph is a graph with distinct source and destination vertices, and obtained by a set of series and parallel compositions, merging the source and destination of components in case of series decomposition or by merging the two sources and the two destinations in case of parallel decomposition as shown respectively in Fig. 6 and Fig. 7. A series-parallel graph can be represented by a binary tree [START_REF] Valdes | The recognition of series parallel digraphs[END_REF], where each internal node of the tree is a series or a parallel composition operation and each leaf is an edge of the graph. Fig. 8 shows a binary tree representation of a seriesparallel graph. We define an S-component as an oriented path, that is either an edge or a series composition of edges (see Fig. 9). We can derive a more compact representation of seriesparallel graphs by replacing maximal subtrees built solely from series operators by the S-components they represent. Hence, leaves are S-components in this alternative representation. In the example of Fig. 8, edges 1 → 2 and 2 → 4 can be merged into one S-component, as edges 1 → 3 and 3 → 4. In order to determine if our algorithm can find a solution given Fig. 9: S-component. a rule set R to decompose, we need to try the decomposition on all paths of the directed network graph. We will then find the smallest rule set that can fit in all paths, taking into account the overhead in terms of forward rules and the compatibility between different paths that share some switches.

Algo. 2 outputs a rule set put in a specific path from s to t using a representation of the graph as a binary tree with S-components. Let R 0 be the initially given policy rule set, and N 0 the root of a binary tree T 0 representing the seriesparallel network graph. Each node N of the binary tree will be labelled with a triplet R , F , R , where :

R is the remaining rules to place in next switches. F represents the P otentialF wds set computed from R 0 \ R . R is the subset of rules from R 0 occurring in the subtree rooted at N . The obtained labelling can be interpreted as a solution of the distribution problem. We define the solution affected to a node n in T 0 to be the label of the subtree rooted at n. If node N corresponds to an S-component, the field N.switches above is by definition the sequence of switches in the S-component minus the first one if that S-component is in series composition with a previous one.

Algo. 2 has as parameters a node of T 0 , a set of rules R ⊆ R 0 , a set of forward rules F . In the main program the recursive procedure Algo. 2 is called with N equal to the root of T 0 , F empty, R equal to R 0 . Algo. 2 terminates successfully when at the end the first field R of the root label is empty: this ensures that all rules have been distributed successfully and no rule has been left out.

This algorithm can be used with other decomposition algorithms like those defined in [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] Chuprikov | How to implement complex policies on existing network infrastructure[END_REF] just by modifying the DecPath function in line 2 with another one. Note that, in our approach and unlike the Optimized Big Switch (OBS) [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF] technique, we do not create several rule table partitions for each path traversing an intersection switch. A packet will be processed by the same rule table at an intersection, regardless of the path it came from. This also facilitates policy updating, as the places where some specific rule occur are easier to localize.

B. Algorithmic complexity

The labels computed by Algo. 2 when successful, defines a solution to the rule distribution problem. The labels are obtained after exploring the entire graph, and the tree representation allows for a single processing of edges shared by several paths.

Several trial and error steps can be necessary for rule propagation, but in many cases the process is substantially faster, since only one propagation try has to be performed under a parallel node. Such cases include paths with switches of identical capacities, or rule sets in which action conflicts cannot happen, for example when the rules sets are blacklists. In this way, given a graph G = (V, E), Algo. 2 computes a rule set decomposition and distribution in O(p|E|) time where p is the number of parallel nodes. Since the cost for distributing rules on a switch is O(nw), we have an overall complexity of O(p|E|nw).

C. Generalization to st-dags

In Subsection V-A, we discussed how to distribute rule sets in series-parallel graph. Here, we show that this technique can be applied to arbitrary two-terminal directed acyclic graphs or st-dags. Duffin [START_REF] Duffin | Topology of series-parallel networks[END_REF] proved that a two-terminal st-dag is series-parallel if and only if it does not contain any subgraph homeomorphic to the Braess graph in Fig. 10. We could notice in such a graph that having the same rule sets in vertices A and B still leads to a correct distribution: a packet travelling from A to B would be applied the same rule and action a second time. To generalize the distribution mechanism, A and B could then be considered as only one vertex, eliminating a Braess graph to obtain a series-parallel one. We then merge them as illustrated in Fig. 11.

Let G = (V, E) the initial network graph, which is not series-parallel. Let a Braess component of G be a subgraph whose vertices are labeled as in Fig. 10. Let us define the set Inter to be the set of vertices occurring on any path from A to B including A and B. We perform a merge on A and B to obtain the graph G = (V , E ) defined as follows:

• V : (V \ Inter) ∪ {AB} with capacity(AB) = min(capacity(A), capacity(B)) • E : -if x → y ∈ E ∧x = A∧y / ∈ Inter then AB → y ∈ E -if x → y ∈ E ∧ x = B then AB → y ∈ E -if x → y ∈ E ∧ y ∈ {A, B} then x → AB ∈ E -if x → y ∈ E ∧ {x, y} ∩ Inter = ∅ then x → y ∈ E
Iterating the operation and once every Braess component has been eliminated, we apply our distribution algorithms on the resulting series-parallel graph. The decomposition and distribution is valid as shown by: By induction, we conclude that if we can build a solution for a graph obtained by eliminating successively Braess graphs then we can construct a solution for the initial st-dag.

VI. A TWO-TIER APPROACH FOR MULTI-FIELDS RULE SETS

In our first approach described in sections IV and V, we restricted the rule set as single field filtering rules, mainly to reduce the forward rules overhead for conflicting actions. Although this technique is useful for blacklisting policies, it is limited and becomes inefficient for decomposing and distributing complex policies that involve filtering rules with IPs and ports fields and overlapping. If we considered for example both source and destination IP fields, we could get a large overhead in terms of forwarding rules as shown in Fig. 12 since for each rule added in Switch 1 we need to generated a forward rule for it in the Switch 2. Unless we find mergeable prefixes on the second filtering field, we would generate as many rules as we have removed from the initial rule set, which limits the decomposition interest. Fig. 12: A counter-productive example of forward rules generation when using our first approach with multi-field filtering rules.

It is nevertheless feasible to apply this approach to several fields when the rule set overlapping rules reside in the same switches or when we are dealing with a blacklist. With all actions of rules being "Deny", all packets matching some rules are stopped and the other are captured by the default rule to be tested in the next switch, so non-default forward rules are unnecessary in a blacklist case. In [START_REF] Chuprikov | How to implement complex policies on existing network infrastructure[END_REF], the authors propose a technique to deactivate rule matching on next switches when a packet is matched in the current switch. However, their technique requires a nonstandard modification on the packet structure by adding an additional bit.

We believe that a more practical solution could be used in real-world environments, and avoiding modifications on the packet structure. To achieve this, we propose a novel approach with nearly zero rule space overhead in switch tables. When distributing a rule set in a network, a packet coming from the source switch needs to travel along a path towards the destination. Only a single filtering action needs to be applied to a given packet. Thus, if a packet is accepted in a switch, all the next switches have to transfer the packet to the destination since a match with a higher priority rule has already been applied. In our first approach, the forward rules mechanism allows us to do that, but increases the total number of rules in the switches. To avoid this overhead problem and allow the distribution of multi-fields rule set, we use two types of switches: Forward Switches (FoS) and Filtering Switches (FiS) as shown in Fig. 13 .

All FiS at distance 2 or more from the destination are connected to one FoS, as it would be impractical to connect all switches to the destination in practice. The role of a FoS is to transmit a packet directly to the destination in order to skip the next FiS on the path, reducing the path length and network latency. For the sake of simplicity we use three types of actions in a rule: "Forward", "Deny" and "Default forward". If the selected action is "Forward", the packet is sent to a FoS, Forward Switches Filtering Switches Fig. 13: Network topology using FoS and FiS. and if the action is "Deny", the packet is dropped. The default forward action sends the packet to the next filtering switch.

By using two types of switches, in this second approach, we eliminate the need for non-default forward rules, which reduces the total number of rules used over a path, and accelerates the processing time of each packet by forwarding it to the destination directly using FoS. A practical requirement for this technique is to rely on high throughput FoS. This technique is applicable in any priority strategy, assuming that every switch which enforces the network policy is linked to the destination, directly or through FoS. A suitable networking architecture for our approach could be the Flat-tree structure [START_REF] Xia | A tale of two topologies: Exploring convertible data center network architectures with flat-tree[END_REF], used in datacenters. In a flat-tree architecture, we can perform matching tests over successive switches by using neighbor-to-neighbor connections and benefit from a multi-tier topology. Indeed, once a packet matches a rule, it can be forwarded directly to the top-level switch instead of going through the other filtering switches.

To distribute the rules on a network graph, the approach described in Section V can be applied without forward rules. Therefore the decomposition algorithm can be simplified, since the F component of node label of the binary tree in Algo. 2 can be eliminated.

VII. EVALUATION A. Simulation setup

In our evaluation experiments of the different proposed algorithms, we rely on 12 rule sets available at [START_REF]Code for Palette, OBS and OneBit simulations[END_REF]. These rule sets and ours are generated using the ClassBench tool. All our algorithms were implemented in Java with single-threaded programs. The machine used for this evaluation is a desktop computer with Intel core i7-7700 3.6-GHz CPU, 32 GB of RAM and running the last version of Windows 10 operating system.

We define the overhead OH in terms of additional forward rules placed on the switches of a path for a given rule set as follows:

OH = Nt-Ni Ni where
N t is the total number of rules used in a path (initial rule set plus extra forward rules). N i is the number of rules in the initial rule set. The overhead depends on the length of the path, capacity of the switches on the path and the diversity of rules' actions in the rule set.

B. Results of LPM based decomposition with forward rules

The 12 rule sets used in our evaluations are the same as in [START_REF] Chuprikov | How to implement complex policies on existing network infrastructure[END_REF]. In this evaluation all switches have the same capacity (tables size), and the minimal capacity to find a solution by our distribution algorithm is defined as C min . We decompose the rule sets using the source IP address as a filtering field. Even with a synthetic rule set of 64000 random rules, no rule set takes more than 150ms to be decomposed and distributed. This processing time includes the tree building, rule set decomposition and rules distribution. This level of performance should enable a network administrator to react and deploy almost immediately an updated policy suited to a new kind of attack flow. Applying our approach on two classical rule sets, which are whitelists and blacklists, the forward rules overhead is very low since such rule sets contain few actions conflicts. For example, with a whitelist policy, only the last default rule has a "Deny" action, so only the last switch will need extra rules in its table. In terms of a blacklist policy, no forward rules are required, so the tree structure is only useful as a sorting and updating mechanism. The decomposition of multi-fields filtering policies is possible when dealing with blacklists, with only one default forward rule added to each switch except the last one. In our simulations, the action field is being used in order to study the effect of this field on the number of generated rules. If a set of rules R1 (0*,deny) and R2 (*,forward) need to be divided using OBS, a forward rule for R1 will be generated to avoid conflict with R2. But using our approach no forward rule should be generated since a packet matching R1 in a switch dose not continue to the next one. In order to show the effect of the action field on the overhead OH and the minimal capacity C min , we use two rule sets (fw1 and acl1), from the 12 rule sets [START_REF] Chuprikov | How to implement complex policies on existing network infrastructure[END_REF], with 0 to 100% percentage of rules having "Forward" action. The average values of OH and C min are computed by running 10 simulations for each percentage value since the "Forward" actions will be distributed randomly among prefixes. Fig. 14 shows the effect of the action field on both OH and C min metrics. When a set of rules has very low action diversity, the overhead is very low since the number of conflicting actions is very small. The situation where the half of the rules has a "Forward" action introduces the most high overhead, and we obtain similar results with the other rule sets.

Fig. 15 shows the overhead distribution using the 12 rule sets from Classbench while varying the path length. The overhead in the worst case is around 30% with 8 switches and for 50% of accepting rules. By using LPM, our approach does not necessarily introduce rule duplication with sets having overlapping rules like the OBS approach. If a rule r is selected, no rule r such as r > r is needed in the current switch. Only forward rules f w such as r > f w are added to to resolve action conflicts. However, the performance of our LPM based method can not be compared to OBS in terms of placement results, because of the single filtering field that we use. The OBS approach operates on both source and destination fields, which is not the case for our method. Contrary to Palette, we do not cut the packet header space by half, so our performance is not affected by the path length being or not a power of two as highlighted in OBS benchmarks. We also do not need to build classifiers such as rules from two different classifiers do not intersect. We only have to respect the rule precedence relation, which enables us to decompose a given rule set without the overhead of rule bits expansion. While Palette assumes that the classifiers have the same size at the end of the decomposition, our approach is not dependent on switch capacities, as each next switch receives as much rules as it can with our algorithm.

Our technique based on LPM is limited to rules composed of a bit-prefix followed by wildcards. For general rules with wildcards possibly occurring at any position, we have to perform a rule expansion like in Palette Pivot Bit Decomposition [START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF].

C. Results of forward switches based approach

Our second two-tier approach for multi-fields rule sets does not introduce rule space overhead except for the extra default rule in each switch, and provides results similar to the OneBit [START_REF] Chuprikov | How to implement complex policies on existing network infrastructure[END_REF] approach. However, our approach has low rule space overhead, it respects packets structure without introducing extra bits, and ensures in a stateless way that packets can perform a network traversal without being matched. Table II shows the different values of C min obtained from [START_REF] Chuprikov | How to implement complex policies on existing network infrastructure[END_REF], in addition to our two-tier approach results on the same datasets with a single path of 10 switches topology. Our approach similar to OneBit divides all rules over the path of 10 switches with an equivalent number of rules in each switch. In this case each switch will be ∼99% full. The only extra cost will be one default rule by switch. On the contrary, using Palette or OBS for example, and for a set of 9968 rule such as fw2, the value of C min is around 4000. In this case the number of used switches belonging to the path will be low, but these approaches introduce the cost of using switches with higher capacity and higher overhead because of rules duplication which affect the performance of the matching rule process along the network.

Our two-tier approach can be used with arbitrary rules priority criterion and can handle rule sets with multiple filtering fields. In this approach no packet will be modified and the only added rules are the default ones in each switch. In addition, the forwarding switches (FoS) will decrease the time needed for a packet to reach it destination since a FoS does not perform any rule matching test. Additionally, as a FoS is a very simple forwarding device, the cost of adding a few FoS to the network remains reasonable.

VIII. CONCLUSION AND FUTURE WORK

In this paper we propose a new decomposition technique based on LPM for one field. We then introduce a novel rule set distribution algorithm for series-parallel network graphs. Finally, we present a solution for multiple fields leveraging two levels of network switches in the SDN data plane. This solution also applies to other than LPM rule selection schemes. We conducted a series of experiments on rule sets generated from Classbench. Our results show reasonable rule space overhead in worst-case scenarios for LPM without Forward Switches, and close to zero overhead with our two-tier solution. Our future work consists of tackling the rule update strategy problem. We also plan to implement our solutions in real environments.

Fig. 2 :

 2 Fig. 2: Compact representation of rules prefixes in a binary tree.

Fig. 3 :

 3 Fig. 3: Illustration of forward rule generation with a rule set and two successive switches.

Fig. 4 :

 4 Fig. 4: Single-forward rule tree.

Fig. 6 :Fig. 7 :

 67 Fig. 6: Series composition.

Fig. 8 :

 8 Fig. 8: Tree representation of a series-parallel graph.

Algorithm 2

 2 DecGraph(N, R, F ) Input: N , node in T 0 ; R, set of rules; F , set of forward rules to be installed in the following switches. Output: label of N 1: if N.isS-Component then 2: R , F , R ← DecPath(R, N.switches, F ) refer to Algo. 1 3: return R , F , R 4: else if N.isSeries then 5: R , F , lef tR ← DecGraph(N.lef tChild, R, F ) 6: R , F , rightR ← DecGraph(N.rightChild, R , F ) 7: return R , F , lef tR ∪ rightR 8: else if N.isParallel then 9: R , F , lef tR ← DecGraph(N.lef tChild, R, F ) 10: R , F , rightR ← DecGraph(N.rightChild, R, F ) 11: while lef tR = rightR do 12: if |lef tR| < |rightR| then 13: R , F , rightR ← DecGraph(N.rightChild, lef tR, F ) , lef tR ← DecGraph(N.lef tChild, rightR, F )

Fig. 10 :

 10 Fig. 10: The Braess graph.

Fig. 11 :

 11 Fig. 11: Merging of vertices to eliminate Braess components.

Lemma 1 .

 1 If we have a solution for the distribution problem of the initial rule set R 0 in G , then we can construct a solution for the graph G. Proof: Leaving empty the intermediate vertices between A and B, we know exactly where the rules will be located. As AB contains a rule set which can fit in both A and B by definition, this rule set is duplicated in A and B. The solution in G is supposed valid, so precedence and intersection constraints at AB are satisfied. Thus, paths S → • • • → A and S → • • • → B contain the same rules from R 0 and the potentially necessary forward rule set F w is the same just after A and B. For the same reason, it is also true that paths A → • • • → T and B → • • • → T contain the same rules from R 0 and generate the same forward rules. Distribution constraints are then satisfied for paths S → • • • → T and the solution affected to G is valid.

Fig. 14 :Fig. 15 :

 1415 Fig. 14: Effect of action field on overhead OH and C min using two different rule sets.

TABLE I :

 I Example of a rule set in a switch table.

TABLE II :

 II Values of C min for different approaches on 12 rule sets with a single path of 10 switches.

			Palette	OBS	ONEBIT	TWO-TIER
	datasets	Size	C min	C min	C min	C min
	acl1	9928	2480	1030	997	994
	acl2	7433	2308	1214	746	745
	acl3	9149	3622	2687	919	916
	acl4	8059	2870	1706	809	807
	acl5	9072	2265	912	910	909
	fw1	8902	3776	2423	891	891
	fw2	9968	4308	3688	997	998
	fw3	8029	3877	2818	804	804
	fw4	2633	1196	800	268	265
	fw5	8136	2651	1780	814	815
	ipc1	8338	2260	1088	837	835
	ipc2	10000	4348	2406	1002	1001

ACKNOWLEDGEMENT

This work is supported by a CIFRE convention between the ANRT (National Association of Research and Technology) and the company NUMERYX Technologies.

APPENDIX A CORRECTNESS OF RULE DISTRIBUTION ON SERIES-PARALLEL GRAPHS

After applying Algo. 2 on the syntax tree of a seriesparallel graph, the relations between the labels in each node are partially determined by which rule sets are put in subtrees with a parallel node root. Taking the example of Fig. 8, we can draw labels dependency relations. In Fig. 16, the children of the parallel node contain the same subset of rules from R 0 , so they share a common label with their parent, which is denoted by their red color. The simplified tree at the right is the minimal one necessary to establish the final labels.

S

As stated, a subgraph G 2 labelling depends on the label affected to the subgraph G 1 whose switches lead to G 1 's source. These labellings must summarize a correct LPM rule distribution.

Assuming that DecP ath implements the LPM semantics of the initial rule set R 0 in the path directly given, we show it is also true for the series composition of path components on which DecP ath is called: Lemma 2. Switches in a given path enforce a correct LPM policy.

Proof: The first S-component encountered in a prefix traversal is constituted of the first switches in the path. Applying DecP ath on this component will ensure that LPM is respected among its switches. The recursive calls of Algo. 2 follow the prefix order, so the precedence relation between switches is maintained.

Lines 4-7 of Algo. 2 maintain the coherence between calls and resulting labellings under a series node. If N with label R , F , R has children, then for the left and right ones T 1 and T

With this precedence and forward relations, a series node's right child will receive the appropriate forward rules and rules from R 0 as base for distribution in its subtree.

DecP ath is called several times for different components of a path. The definition of N.switches guarantees that in a series composition, the common vertex between two components is not filled twice. With a path s 1 → s 2 → s 3 , DecP ath could then be called on s1 → s 2 then s 3 , so s 2 would not be filled again.

Consequently, the result of successive DecP ath calls on path components is equal to the one obtained with a single call on the whole path. This path contains a rule set decomposed with respect to the intended LPM policy.

When a packet has the option to take different paths towards a network location, each of these paths must be equivalent, filtering-wise. Algo. 2 must terminate correctly in this case. Lemma 3. Switches in parallel paths enforce the same filtering policy.

Proof: Lines 8-18 ensure that a parallel node will share the same labelling as its two children, i.e its children subtrees will contain the same rules from R 0 . Algo. 2 always terminates, because of the process of decomposition trial and error. After decomposing a part of R 0 in the two parallel subgraphs represented by T 1 and T 2 , we obtain R 1 and R 2 respectively fitting in those subgraphs. Three cases can occur:

• R 1 or R 2 has smaller size than the other.

• R 1 and R 2 are different rule sets of the same size. These last two cases indicate a decomposition mismatch. To correct it, Algo. 2 iteratively tries to propagate the smallest rule set resulting from T 1 or T 2 . If R 1 has to be propagated on T 2 , R 1 ⊆ R1 will fit in T 2 . Because of this inclusion relation, R 1 can fit in T 1 and Algo. 2 returns it once propagated. The process is symmetrical if R 2 has to be propagated on T 1 . Thus, Algo. 2 terminates after having ensured that two parallel subgraphs enforce the same filtering policy. Only one set of forward rules can be used at the common sink of these subgraphs.


M V Yakunin
email: yakunin@imp.uran.ru

S S Krishtopenko

S M Podgornykh

M R Popov

V N Neverov

B Jouault

W Desrat

F Teppe

S A Dvoretsky

N N Mikhailov

G M Gusev

A K Bakarov

T E Lamas

Unconventional Reentrant Quantum Hall Effect in a HgTe/CdHgTe Double Quantum Well

Keywords: numbers: 73.21.Fg, 73.43.-f, 73.43.Qt, 73.43.Nq

We report on observation of an unconventional structure of the quantum Hall effect (QHE) in a p-type HgTe/CdxHg1-xTe double quantum well (DQW) consisting of two HgTe layers of critical width. The observed QHE is a reentrant function of magnetic field between two i = 2 states (plateaus at ρxy = h/ie 2 ) separated by an intermediate i = 1 state, which looks like some anomalous peak on the extra-long i = 2 plateau when weakly expressed. The anomalous peak apparently separates two different regimes: a traditional QHE at relatively weak fields for a small density of mobile holes ps and a high-field QH structure with a 2 -1 plateau-plateau transition corresponding to much larger ps. We show that only a part of holes, residing in an additional light hole subband in the DQW, participate in QHE at weak fields while the rest of holes is excluded into the reservoir formed in the lateral maximum of the valence subband. All the holes come into play at high fields due to a peculiar behavior of the zero-mode levels.

I. INTRODUCTION

Quantum Hall effect (QHE) at a fixed carrier density manifests most typically as a sequence of plateaus in the Hall magnetoresistance (MR) ρ xy (B) located in a stair-like fashion at its monotonically increasing values ρ xy (B) = h/ie 2 for integer and fractional values of i 1 . This picture is disturbed by a nonmonotonic reentrant behavior of ρ xy (B) for the integer QHE (RIQHE) in some special cases: for two-subband conductivity due to a Landau level (LL) or subband mixing 2 ; in a traditional double quantum well (DQW) under tilted magnetic fields 3 where certain QH states are repeatedly destroyed as a function of the parallel field component B due to an oscillating behavior of the tunneling gap; and around the i = 7/2 and 5/2 fractional QH states where RIQH states i = 3 ↔ 4 and i = 2 ↔ 3 are observed at extra-low temperatures [4][5][6] due to repeated transitions between the collective quantum liquid and pinned quantum solid bubble or stripe states 7,8 . In this Paper we demonstrate a distinct RIQHE appearing in a complicated energy spectrum of the HgTe DQW that may be basically explained without recourse to the collective nature of the electronic phases.

A uniqueness of the energy spectrum of the HgTe QW and its strong dependence on the well width 9 make it suitable to construct various kinds of a nontrivial energy structure in a system of two HgTe layers separated by a thin Cd x Hg 1-x Te barrier, i.e. in a HgTe/CdHgTe DQW 10,11 . Different applications were predicted for this structure 12,13 as well as an opportunity to study fundamental phenomena in new conditions 14 . Experimentally, several remarkable novel features were found in quantum magnetotransport of the HgTe DQW of relatively wide HgTe layers, like a reentrant sign-alternating QH states, a possibility to enlarge and regulate the band overlap and the enhanced zero filling factor state 10 . In the present study we found that probably the most unusual features of quantum magnetotransport are manifest in a p-type HgTe/CdHgTe DQW with the width of HgTe layers close to the critical value d ≈ d c = 6.3 ÷ 6.5 nm, when a Dirac energy spectrum is formed in a single HgTe layer 9 . In this case, a RIQHE is revealed 15 that has indications of switching between two states with different densities of mobile holes. The only analog we know of such a kind of switching between different net carrier densities with magnetic field was reported for a multi-quantumwell structure made within a GaAs parabolic quantum well 16 , where the effect was attributed to a spatial redistribution of electrons between different wells. In our case, we show that the observed 'switching' is an inherent property of the collective DQW spectrum.

II. SAMPLES AND MEASUREMENTS

DQW structures were grown by molecular-beam epitaxy on a (013) orientated GaAs substrate above a series of subsequent buffer ZnTe and CdTe layers and consisted of two HgTe layers with thickness d = 6.5 nm separated by a 3-nm Cd x Hg 1-x Te barrier with x = 0.71 sandwiched between the layers with the same x; without deliberate doping. The sample was shaped by photolithography to form a double Hall bar with soldered contacts at the con-tact pads penetrating through both the HgTe layers. The field-effect transistors were fabricated with parylene as an insulator and aluminum as a gate electrode. We measured the longitudinal and Hall MRs, ρ xx (B) and ρ xy (B), at temperatures down to 0.3 K in fields up to 13 T. The measurements were performed on a series of ungated and gated samples cut from the same wafer: the obtained results are identical. The ungated samples show p-type conductivity.

III. ENERGY SPECTRUM

The energy spectrum as well as LL pictures were calculated in the single-electron 8-band k × p-approach with inclusion of terms describing the influence of elastic strain by solving the self-consistent system of Schrödinger and Poisson equations in the potential profile of the DQW 11 .

A picture of spatially quantized spectrum of a single HgTe QW is characterized by two groups of levels -of the heavy hole (HH) nature and light carriers (E), see insert to Fig. 1, -that move quickly towards each other with increasing layer thickness d. At the critical thickness d c the extreme levels of both series cross and the Dirac spectrum is formed at this meeting point. It is clear from this picture that small deviations in d will cause strong changes in the relative level positions. A DQW made of these HgTe has a specific energy spectrum as the E-levels are strongly tunnel-coupled, contrary to the HH-levels: Fig. 1. Noteworthy is that the high sensitivity of the relative level positions to d in a single QW means similar high sensitivity of the DQW spectrum to the sample structure.

p s = 1 . 6 x 1 0 1 5 m -2 [ 0 3 -1 ] E n e r g y ( m e V ) k ( n m -1 ) [ 1 0 0 ] H H 1 1 H H 1 2 E 1 2 E 1 1 H H 2 1 H H 2 2 E F f o r p s = 0 . 4 x 1 0 1 5 m -2 d = d c E 2 E 1 H H 4 H H 3 H H 2 H H 1 d ( n m )

FIG. 1:

Energy spectrum of the symmetric DQW under study. Insert: spatial levels of a single QW as a function of the layer thickness d. The upper index on the main figure ( 1 or 2 ) means the first or second split-off subband in a DQW originating from the corresponding level of a single well.

IV. EXPERIMENTAL RESULTS

We revealed a quite unusual structure of QHE in the described DQW (Fig. 2). In fields up to about 1.4 T, a traditional picture of QHE exists with plateaus of ρ xy (B) and transition regions between them centered around the straight line extrapolated from the classical Hall MR in weak fields. In this field region, ρ xy (B) corresponds to the two-dimensional hole density p s = 0.4 × 10 15 m -2 . However, the further behavior of ρ xy (B) with increasing field is unusual: the incipient 2-1 plateau-plateau transition (PPT) reverts to the plateau i = 2, which extends to an unexpectedly wide field interval. Thus, at temperatures above 1.8 K, a peak in the Hall MR of unknown nature is formed instead of the expected 2-1 PPT 15 . Further, the i = 2 plateau does go over to the stable i = 1 plateau, but the position of this 2-1 transition is shifted considerably to higher fields from the one extrapolated from the classical behavior of ρ xy (B) in weak fields. The hole density calculated for the field of this transition (i.e., for i = 1.5) is p s = 1.66 × 10 15 m -2 . The estimated positions of the Fermi level, E F , are presented in Fig. 1 for both values of p s . Remarkable is that, for the latter value, E F is below the lateral maximum (LM) in the valence subband, thus, considering a high density of states (DOS) in LM, it should substantially influence the physics in this case.

The 'anomalous' peak turns into a step at lower temperatures with its maximum turned into a short i = 1 plateau. Thus the crux of this anomalous peak is a transition into the i = 1 state with the further reentrance back into the i = 2 state.

The discovered anomalous peak in ρ xy (B), if it is narrow, is also seen as a similar peak in ρ xx (B) at the same

V g = -1 V ( 0 . 3 K ) ؒ x y , x x ( h / e 2 ) T = 1 . 8 K ( b e f o r e & a f t e r I R ) T = 0 . 3 K B ( T ) i = 5 i = 3 i = 1 i = 2
FIG. 2: MR with anomalous peak in ρxy(B) before and after IR illumination, at 1.8 K and 0.3 K (unilluminated). Also the curve for Vg = -1 V at 0.3 K added.

V g = 1 . 5 V 1 . 3 1 . 0 0 . 5 0 -1 ؒ X Y , X X ( h / e 2 ) B ( T ) ( a ) ؒ X Y ؒ X X ؒ X Y 4 . 5 3 . 0 V g = 2 . 4 V ؒ X Y , X X ( h / e 2 ) FIG. 3: Evolution of MR with the gate voltage: (a) Vg = -1 ÷ 1.5 V; (b) Vg = 2.4 ÷ 4.5 V. T = 0.3 K.
field. But with development of the ρ xy (B) peak into the step with the i = 1 plateau on its top, the corresponding peak in ρ xx (B) splits into two peaks positioned in the fields of the up and down slopes of this step. While the left peak of ρ xx (B) in this couple corresponds to a traditional 2-1 transition of E F through an extended state within a LL, the right one is something new and means in fact the crossing of the same (or similar) extended state in the backward direction. Also, ρ xx (B) exhibits a peak corresponding to the stable high-field 2-1 transition in ρ xy (B), which is positioned, as it should be, against its middle.

The weak-and high-field parts of MR behave quite differently in response to various impacts (Fig. 2): to IR illumination (that reduces p s persistently) and application of the gate voltage V g . The high-field 2-1 transition reacts sharply manifesting the changes in p s while MR below the anomalous peak remains almost unchanged. Only for V g > +1 V the whole MR curves start to change: (Fig. 3).

0 1 2 3 4 5 6 7 8 -2 -1 0 1 2 3 4 ( b ) ( a ) i = 2 i = 1 i = 2 i = 1 i = 0 i = -1 ؓ x y ( h / e 2 ) V g ( V )
-1 . 5 -0 . 5 0 0 . 5 0 1 . 5 2 . 5 3 . 5 4 . 5 5 . 5 6 . 5 7 . 5 8 . 5

a n t i c r o s s i = 2 i = 1 i = -1 i = 1 2 ( V g + 0 . 5 ) , p s = 1 . 7 2 -1 ( V g -1 ) p s = 2 . 4
p s = 0 . 3 , 0 . 4 , 0 . 5 , 0 . 7 , 0 . 9

E n e r g y ρ xy (B) is distinctly antisymmetric with respect to the field polarity for V g < 2 V, whereas ρ xx (B) is symmetric, that excludes any relation between the nature of the observed anomalous peak and a mixing of two MR components as well as a presence of macroscopic inhomogeneities. This conclusion becomes invalid only around V g ≈ 3 V where a large growth of ρ xx (B) in the charge neutrality state creates problems in the unaveraged ρ xy (B) as is seen in Fig. 3(b).

B ( T ) 2 -1 ( V g 0 ) p s = 1 . 9 n = -2 n = -1 n = 0 n = 1 n = 2 n = 3 i = 0 i = 0 i = 3 i = 2 2 -1 ( V g + 1 ) , p s = 1 . 2 4 < n < 4 5 1 0 0 0 < n < 1 0 0 5
The detailed evolution of QHE with V g is presented on Fig. 4 for the Hall conductivity σ xy (B, V g ) (which is more convenient than MR since it does not go to infinity at the high fields).

V. DISCUSSION

To understand the observed singularities in QHE, the experimental data are compared in Fig. 4 to the calculated pattern of the DQW LLs with the plotted E F (B) curves. The latter were calculated for LLs of finite DOS and a set of fixed values of p s , which in case of simultaneous population of the hole-like and electron-like LLs are the net values obtained as differences between the summary hole density and the electron density in these LLs 17,18 . It is important to distinguish correctly between the hole-like and electron-like LLs in such calculations. The issue is not trivial here due to anomalous behavior of certain LLs in the HgTe quasi-2D structures. An objective indicator of this attribution is a sign of the contribution from this LL to ρ xy : it is positive for the hole-like and negative for the electron-like LLs. We determined it by the direction in which this LL shifts on approaching to the sample edge 19,20 : it is an electron-like (hole-like) LL if it shifts upward (downward). In all the calculations we are aware of (e.g., 20,21 ), this direction coincides with the direction of the LL shift with increasing magnetic field. Thus we use the latter criterion in our analysis regardless of what subband the LL comes from. Then, the two n = -2 zero-mode LLs 22,23 in Fig. 4(b), slowly moving down with field, are the two topmost hole-like LLs and the n = 0 LL, moving upward, is an electron-like LL, in spite of that it splits off from the valence subband.

For a symmetric DQW potential profile, the two n = -2 LLs should coincide, in agreement with the zero gap energy spectrum in Fig. 1. The gap between two HH1 subbands (and between two n = -2 LLs) occurs with appearance of asymmetry in DQW. Existence of the i = 1 QH plateau at the highest fields even for V g = 0 indicates that these two LLs are split and, hence, that the DQW potential profile is initially asymmetric 11 . The asymmetry may be caused by imbedded charges on the surface or by geometrical deviations in DQW.

When an electron-like LL is imposed upon an array of the hole-like LLs, a special attention should be payed to the correct identification of filling factors in the gaps between LLs, to compare them with the corresponding QHE plateau numbers i. This numbering is trivial for the hole-like LLs below the electron-like LL as the latter is empty for E F positions in this part of the picture: Fig. 4(b). But a mixed electron-hole conductivity 17 appears for the energy range above the electron-like LL and below the topmost hole-like LLs. In this case the resulting filling factor (and the corresponding QH plateau number i) is a difference between the number of filled hole-like and electron-like LLs. This results in that the i = 1 gap consists of two sectors in high and low fields separated by a neck, while the low field part of the gap between two n = -2 LLs corresponds to i = 0. Sim-ilar situation occurs for the gaps with higher numbers i = 2, 3, . . . The specificity of the mixed electron-hole conductivity was taken into account when calculating E F (B) since not the pure hole density but the difference between the hole and electron densities is fixed (determined primarily by the balanced quantity of ionized impurities). When electrons appear in the electron-like LL then additional holes appear in the hole-like LLs in this balanced situation to preserve the electroneutrality.

The existence of lateral maxima in the valence subband in vicinity of the achievable E F positions creates quite a new situation here. A very large DOS in it is displayed in a dense grid of its LLs: Fig. 4(b). Noteworthy, to consider its influence in calculations of E F (B), a sufficiently big number of harmonics should be included (n < 45 in Fig. 4(b)). The upper envelope of this grid is at the LM energy and extrapolates to it for B → 0 and n → ∞ (see LLs for n = 1000 ÷ 1005 in Fig. 4(b)). This consideration clarify the issue that the LM LLs should start from the LM energy at B = 0: it is an envelope of infinite array of LLs that obey this rule.

When, on decreasing the field, E F tends to jump into a higher number LL (see the dashed step-like curve in Fig. 4(b) for E F (B) in a hypothetical case of missing LM) it falls into the energy range next to LM with a high DOS within the tails of its LLs. As a result, E F (B) is stabilized within a narrow energy range close to LM. Important is that, being in the tail, E F does not cross the extended state of LM LL located at its center. On the contrary, the stabilized E F (B) crosses the LLs in the light hole fan-chart indicating each such crossing with a PPT in the experiment. But these crossings occur at much weaker fields than they would be in case of no LM (compare, e.g., 2-3 PPT for the dashed line at ∼3.5 T and at ∼1 T for stabilized E F (B)). Considering also that LLs in the LM grid are in fact unresolved due to their high density, it becomes clear that the LM LLs do not contribute to the structure of QHE in this range of fields despite that they absorb a considerable part of holes. Thus QHE is formed solely by the light hole LLs here.

This situation looks like a part of holes is localized in the states of LM at weak fields and only the other smaller part residing in the central maximum of the light hole branch (see Fig. 1) is manifested in the experimental quantum features. With increasing field, E F (B) tends to reach the low number (n = -2) hole-like LLs, which are positioned much higher in energy than the rest of the hole-like LLs. Thus E F (B), on moving up in the wide i = 2 gap, leaves the range of high DOS at LM, and now all the holes participate in formation of QHE. Hence the total hole density is manifested in the high-field 2-1 PPT. In this sense LM may be considered as a reservoir 24,25 absorbing a considerable amount of holes at weak fields and excluding them from QHE. Contrary to the previous works, this 'reservoir' is not in a surrounding of the quasi-2D structure but within it being built into its own energy spectrum.

The superposition of the electron-like n = 0 zero-mode LL upon a fan chart of light hole LLs (Fig. 4(b)) creates some novel configuration with a quasi-triangular gap of i = 1 formed below two topmost hole-like LLs and above the n = 0 LL. This gap is surrounded by the gaps of i = 2 to the left and to the right. Important is that the lower corner of this quasi-triangle is in the vicinity of the LM energy. In this case the stabilized E F cuts the lower corner of this triangle thus entering the i = 1 gap in the limited range of fields and causing the step in ρ xy with i = 1 plateau on its top superposed on the i = 2 plateau. The corresponding behavior of ρ xy (B) for V g = 0 is highlighted in Fig. 4(a) by the long lightyellow horizontal and compared with the dash-dot E F (B) curve marked (V g0) calculated for p s = 1.9 × 10 15 m -2 in Fig. 4(b).

On decreasing V g from 0 to -1 V, the high-field 2-1 PPT moves to considerably higher fields (Figs. 2,3(a)) that is reflected in the general experimental picture of σ xy (B, V g ), Fig. 4(a), in a substantial slope of the border between the i = 2 and i = 1 phases at high fields. This corresponds to an increase of adjusted p s values (from 1.9 to 2.4)×10 15 m -2 in calculated curves of E F (B), Fig. 4(b). On the contrary, the forth and back transitions between the same QH phases in the weak-field range do not move with variation V g = 0 → -1 V and below in the experiment. Correspondingly, the low-field parts of the same E F (B) curves change little with V g as they get into the high DOS at LM. Only at the achieved extremely negative V g = -2 ÷ -2.5 V a narrowing of the i = 1 step is seen in Fig. 4(a) indicating the approach of E F (B) curve to the lower corner of the i = 1 quasi-triangle: Fig. 4(b). Some evolution of the picture of LLs with V g is seen in Fig. 4(a) in that the width of the i = 1 sloped stripe at high fields increases with negative V g manifesting an increase of the gap between the two n = -2 LLs.

On increase in V g from 0 to +0.5 V the E F (B) curve is gradually pushed out of the high-field i = 2 gap (Fig. 4(b)) so that it only weakly enters it within a small range of fields for V g = +0.5 V (see a short light-yellow horizontal at 2 ÷ 3 T in Fig. 4(a)) resulted in a vanishing minimum on a quasi-continuous i = 1 plateau (Fig. 3(a)). This minimum disappears at all for the higher V g as E F resides entirely in the i = 1 gap. To be more exact, it resides in two sectors of this gap as is seen in Fig. 4(b). Surprisingly, passing of E F (B) through the neck between these two sectors does not manifest in ρ xy (B) although some bump appears in ρ xx (B) between B = 2 and 4 T for V g = 1 ÷ 1.5 V. These data mean that in fact there is an anticrossing between the zero-mode n = -2 and n = 0 LLs so that a continuous connection is formed between these two sectors while the feature in ρ xx (B) indicates a local narrowing of the i = 1 gap. Manifestations of anticrossings in QHE were found in a similar case of InAs/GaSb electron-hole system 26 and in experiments on magneto-optics in the same HgTe/CdHgTe structures that we use. In the latter case the anticrossings were explained as being due to the bulk inversion asymmetry in this material 22,26,27 not considered in our calculations.

The lower-field border of the low-field 2-1 PPT still remains unchanged at positive voltages while V g < +1 V (Fig. 4(a)), in agreement with a calculated weak raise of E F at B ≈ 1 T with a p s decrease, and it is only with a further increase in V g that this PPT noticeably shifts to lower fields (Figs. 3(a),4(a)). Accordingly, the calculated E F shifts upward with a p s decrease below 1.2 × 10 15 m -2 at B ≈ 1 T. It means that just at these small enough p s the Fermi level starts rising here, freed from being captured in the high DOS range of LM.

A zero filling factor state i = 0 is revealed as σ xy (B, V g ) → 0 at high positive V g and high fields: Fig. 4(a). It means that the infinite growth of ρ xy (B) is delayed in fields with respect to the growth of ρ xx (B): Fig. 3(a). A divergent shape of this i = 0 state in the experimental (B, V g )-map, Fig. 4(a), dramatically reproduces the shape of the high-field i = 0 gap formed within the calculated picture of LLs, thus confirming our hierarchy of the gap numbering. The only problem is a quantitative disagreement between the calculated and experimental positions of the convergence point -it is at ∼2 T in the experiment while at ∼4.5 T in the picture of LLs, Fig. 4(b). As reasons of this discrepancy may be: a similar anticrossing between LLs with the same numbers, the upper n = -2 LL and n = 0 LL, that creates a tail for the upper i = 0 gap extended to lower fields; an evolution of the picture of LLs with V g (while that in Fig. 4(b) is for a fixed V g = 0) and deviations of the DQW potential profile from the technologically preset one as well as some other unconsidered factors in calculations. A high sensitivity of the relative subband positions and, consequently, of the LL pattern to the smallest changes in the DQW potential profile has already been mentioned.

With transition of E F (B) through the convergence point in decreasing field, it must pass from the i = 0 divergent gap at high fields into a gap between two n = -2 LLs, which also corresponds to i = 0 in our hierarchy. It is remarkable that the state i = 0 is absent in the experimental map to the left from the convergence point within some field range. The functions σ xy (V g )[B] taken at fixed fields manifest a pronounced σ xy = 0 plateau for the high fields but continuously pass from the i = 1 to the electron phase with i = -1 without i = 0 plateau at B ≈ 0.5 ÷ 2 T. The σ xy = 0 state reappears at the weakest fields but in fact the term 'filling factor' is no more valid at this classical field range. The missing i = 0 state at the fields below the convergence point means that the gap between two n = -2 LLs is absent at the corresponding V g = +3 V and the DQW structure becomes symmetric. Thus, on application of V g , our structure becomes more asymmetric with negative V g but symmetric for V g = +3 V.

Observation of a distinct linear ρ xy (B) part as B → 0 (Fig. 2) that yields p s much smaller than the value obtained at high fields may look controversial. To resolve this problem, QHE is compared with MR at 30 K when QHE is quenched: Fig. 5. In these conditions, ρ xy (B) also consists of two parts with significantly different slopes, the low-field slope being the same as at low temperatures and the high-field part of ρ xy (B) crossing the high-field plateau for i = 1. This high temperature ρ xy (B) is reproduced by classical magnetotransport of two kinds of holes, a small amount of high-mobility holes: p 1 = 0.27 × 10 15 m -2 , µ 1 = 3.6 m 2 /V•s, and a large density of low mobility holes: p 2 = 1.3 × 10 15 m -2 , µ 2 = 0.16 m 2 /V•s. These densities are of the same order as those determined from QHE. As seen in Fig. 1 the two kinds of holes may originate from the central valence subband maximum and LM.

VI. CONCLUSIONS

Concluding, we can single out a combination of factors responsible for the formation of the observed anomalous QHE structure in the investigated DQW: (i) a lateral maximum in the valence subband on the background of a light-hole fan chart and proximity to it of E F in p-type structures; (ii) two topmost zero-mode hole LLs (n = -2) that are significantly raised in energy with respect to other hole LLs; (iii) a zero-mode electron-like LL (n = 0) superimposed on the array of light-hole levels.

It is interesting to understand why the QHE peculiarities observed here are not found in a single p-type HgTe layer with Dirac or inverted energy spectrum of a thickness close to critical (see, e.g., Ref. 28 , the LLs pictures for these cases may be seen in Ref. 29 ). The three conditions listed above for observation of RIQHE seem to be realized here as well: LM not far from E F , highly raised topmost hole LL and an electron-like n = 0 LL. But the differences are that there is a single topmost hole n = -2 LL in a single QW, not two such levels as in DQW, and there is no additional array of light hole LLs that would create a background for the superimposed electron-like level. Due to the former, the corresponding filling factors and QH plateau numbers will be shifted one unit down in a single QW with respect to our case of DQW. As a result, E F (B) stabilization near LM would be developed in the gap with i = 1, not i = 2 as in a DQW. Then the approach of the Fermi level to the upper hole LL in a single QW will manifest in a different way since the i = 1 QH plateau does not has a distinct high-field border (and an extra-long i = 1 plateau was observed in some experiments 30 ) while the high-field border for the i = 2 plateau in the DQW is distinctly at i = 1.5. Also, there is no cause for formation of an anomalous peak in a single QW since there is no additional light-hole array of LLs upon which the electron-like level could superimpose thus forming a quasi-triangular gap. The center part of the DQW energy spectrum resembles the fragments of the bilayer graphene spectrum around K points 31 , but the latter has no LM and no anomalous LLs 31,32 .

FIG. 4 :

 4 FIG.4:(a) Evolution of the Hall conductivity σxy(B, Vg) at T = K and its comparison with (b) the calculated picture of LLs. The latter is drawn for a fixed Vg(= 0) although it also changes with Vg. Dash-dot curves EF (B) are calculated for the given picture of LLs for a finite DOS and a set of net hole densities ps (indicated at the arrows in 10 15 m -2 together with the plateau numbers and Vg in Volts). Short-dash red curves illustrate schematically supposed anticrossings between n = 0 and n = -2 LLs. Arrows continued by dashed verticals connect characteristic features in the experimental map (indicated at certain Vg by light-yellow horizontals), like i -j PPT or incipient i plateau, with positions of EF (B)[Vg] vs. corresponding LLs. The area segments are marked with i values for the corresponding plateau numbers (negative for electrons). The dashed curve for ps = 2.4 is EF (B) for a hypothetical case of no LM.

FIG. 5 :

 5 FIG.5: QHE at 1.8 K and MR at 30 K (circles) with a two-carrier fit for the latter (lines).

Acknowledgments

Authors are grateful to G. M. Minkov and A. A. Sherstobitov for advice on making photolithography and for deposition of the gate. The research was carried out within the state assignment of the Russian Ministry of Education and Science (theme "Electron" No. AAAA-A18-118020190098-5), supported in part by the Ural Branch of RAS Program (project No. 18-10-2-6) and RFBR (project No. 18-02-00172). Partially supported by MIPS department of Montpellier University through the "Occitanie Terahertz Platform", by the ANR project "Dirac3D", by the Occitanie region via the "Gepeto Terahertz platform", and by the CNRS through LIA "TeraMIR". A part of measurements was done in the Testing center for nanotechnology and advanced materials at M. N. Miheev Institute of Metal Physics UB RAS.