Student Member, IEEE Kun Qiu

Jing Yuan

Member, IEEE Jin Zhao
email: jzhao@fudan.edu.cn

Member, IEEE Xin Wang
email: xinw@fudan.edu.cn

Stefano Secci
email: seccis@cnam.fr

Senior Member, IEEE Xiaoming Fu
email: fu@cs.uni-goettingen.de

J Qiu

X Zhao

Wang

FastRule: Efficient Flow Entry Updates for TCAM-based OpenFlow Switches

Keywords: Software-Defined Networks, TCAM, OpenFlow, greedy algorithm, flow update

published or not. The documents may come

I. INTRODUCTION

S OFTWARE-DEFINED NETWORKS (SDN) and Open- Flow [START_REF] Mckeown | OpenFlow: enabling innovation in campus networks[END_REF] are increasingly being adopted by enterprise networks and even carrier networks. The advantage brought by SDN is dynamic network reconfiguration thanks to the global view on network states. An increased spectrum of functionalities is being explored in SDN. How to enhance the response time to network update events such as failures or topology changes is critical, since it determines the agility of the SDN control loop [START_REF] Al-Fares | Hedera: Dynamic flow scheduling for data center networks[END_REF]. In the case of failure recovery in carrier networks, re-routing rules in switches has to be finished within 25ms [START_REF] Niven-Jenkins | Requirements of an MPLS transport profile[END_REF], to avoid congestion or packet loss. Meanwhile, traffic engineering applications, e.g., B4 [START_REF] Jain | B4: Experience with a globally-deployed software defined WAN[END_REF], also require fast switch reconfiguration to improve network efficiency.

Although many solutions are proposed to increase the controller processing power in order to shorten control-plane processing latency [START_REF] Hu | Scalability of control planes for software defined networks: Modeling and evaluation[END_REF]- [START_REF] Dutra | Ensuring endto-end qos based on multi-paths routing using sdn technology[END_REF], they cannot avert the considerable latency in the data plane, which is mainly caused by rule update of the switch [START_REF] Wen | Compiling minimum incremental update for modular SDN languages[END_REF]. According to the recent measurement results, a commercial OpenFlow switch can only process 42 rule updates in 1s [START_REF] Huang | High-fidelity switch models for software-defined network emulation[END_REF]. Thus, reducing the rule update latency of switch is a critical task.

Usually, the switching rule (flow entry) update latency is the time to add, delete, modify flow entries in the flow table of SDN switches [START_REF] Chen | Hermes: Providing Tight Control over High-Performance SDN Switchesx[END_REF]. The primary reason why OpenFlow switches can perform inefficiently in flow entry update is that they use ternary content addressable memory (TCAM) [START_REF] Long | Research on tcambased openflow switch platform[END_REF] -a memory architecture that can be seen as an ordered array with parallel look-up ability [START_REF] Pagiamtzis | Content-addressable memory (cam) circuits and architectures: A tutorial and survey[END_REF] -whose function is mainly designed for fast entry lookup, not for fast updating. Flow entries in TCAM are usually stored from top to bottom, ordered by decreasing physical addresses. If the header of an incoming packet matches with multiple flow entries, only the entry with the highest physical address is chosen. Thus, during the flow entry update, the switch cannot prevent maintaining the order of entries in the TCAM, which may cause a significant number of movements of existing flow entries [START_REF] Jin | Dynamic scheduling of network updates[END_REF], [START_REF] Vamanan | TreeCAM: decoupling updates and lookups in packet classification[END_REF]. In fact, not only OpenFlow-based switch, but also 5G mobile networks are highly dependent on TCAM update efficiency. It is reported that some new 5G firewall designs use TCAM to increase their detection, differentiation and selective blocking efficiency [START_REF] Ricart-Sanchez | Hardware-Accelerated Firewall for 5G Mobile Networks[END_REF].

The problem can be approached from two dimensions. One is to minimize the number of flow entry updates sent to switches from the control plane [START_REF] Jin | CoVisor: A Compositional Hypervisor for Software-Defined Networks[END_REF]- [START_REF] Vissicchio | Safe, Efficient, and Robust SDN Updates by Combining Rule Replacements and Additions[END_REF]. For example, a modular composition approach [START_REF] Monsanto | Composing software defined networks[END_REF]- [START_REF] Foster | Frenetic: A network programming language[END_REF] can minimize the number of updates by reducing redundant updates; and Dionysus [START_REF] Jin | Dynamic scheduling of network updates[END_REF] reduces multi-switch policy update latency caused by suboptimal scheduling. Another way is to design a new firmware with efficient algorithms [START_REF] Katta | Cacheflow: Dependency-aware rule-caching for software-defined networks[END_REF]- [START_REF] Shah | Fast updating algorithms for TCAM[END_REF] in switches that can decrease flow entry movements in TCAM. The minimum dependency graph, a kind of Directed Acyclic Graph (DAG), can avoid unnecessary flow entry movements in the procedure of flow entry update. Utilizing DAG in the firmware needs a policy compiler, whose function is to convert entry update requirement into DAG, and a TCAM update scheduler, whose function is to convert an update in DAG back into a sequence of TCAM entry movements. The state-of-the-art solution called RuleTris [START_REF] Wen | RuleTris: Minimizing rule update latency for TCAM-based SDN switches[END_REF] mainly focuses on designing an efficient policy compiler, but the poor performance of its TCAM update scheduler leads to large firmware time, say, up to 50ms for one update in a flow table with a size of 1k entries.

In order to overcome these limitations, we propose FastRule, an efficient and scalable flow entry update framework that can achieve 0.04ms firmware time per-update in a 1k size flow table by providing a high-performance TCAM update scheduler. Our scheduler reduces the time complexity of calculating update sequence to O(c avg (log n) 2 ) with only O(n) space complexity by a greedy algorithm and an efficient data structure based on Binary Indexed Tree (BIT), where n is the size of TCAM and c avg is the average diameter of subgraphs in the DAG. According to our measurement, a common value of c avg for a n = 40k flow table is less than 15, which is far less than n. We implement our scheduler in the firmware of ONetSwitch [START_REF] Onetswitch | Open Source Hardware for SDN[END_REF], a programmable hardware OpenFlow switch. Through hardware evaluation, our solution reveals to be 100x faster than the solution of RuleTris. The evaluation also demonstrates that our solution scales well with the flow table size increases, as shown in our large-scale hardware emulations. We also modify FastRule to satisfy the particular TCAM layouts [START_REF] Mishra | DUOS-Simple dual TCAM architecture for routing tables with incremental update[END_REF], [START_REF] Shah | Fast updating algorithms for TCAM[END_REF] in order to prove that FastRule can also be utilized in the different type of OpenFlow switches. We elaborate on the correctness of FastRule and prove that we can always find a solution with our algorithm.

The rest of this paper is organized as follows: we first describe the background of TCAM, flow dependency and DAG in section II. In section III, we describe the framework of FastRule. In section IV, we introduce a greedy algorithm for scheduling flow entry movement, and an efficient data structure, BIT, for querying minimum range. In section V, we discuss several flavors of FastRule in different TCAM layouts. In section VI, we evaluate FastRule and analyze the evaluation results. In section VII, we give the related work. We conclude in section VIII.

II. BACKGROUND

As above mentioned, the TCAM is designed for high-speed packet matching rather than for efficient entry updating in the flow table. The reason for the slow update is that the TCAM must keep the order of flow entries to satisfy a restriction called flow dependency [START_REF] Wen | Compiling minimum incremental update for modular SDN languages[END_REF], [START_REF] Wen | RuleTris: Minimizing rule update latency for TCAM-based SDN switches[END_REF]. Besides the priority (defined in OpenFlow specification), the minimum dependency graph, a kind of DAG, is a widely utilized way to handle flow dependency. In this section, we give a brief description of the flow dependency restriction, DAG, and how they decrease the TCAM update latency.

A. Flow dependency

Similarly to the route entry that includes a prefix and a forwarding port, the flow entry includes a match field and an action [START_REF] Mckeown | OpenFlow: enabling innovation in campus networks[END_REF]. If an incoming packet matches the match field of a flow entry, the corresponding action is executed. If the match field of two flow entries overlaps, i.e., two flow entries match a same incoming packet, a specific order must be provided to solve the matching ambiguity. The flow dependency is such a relationship between two flow entries. Since we can define a flow entry A is dependent on a flow entry B if B should be matched first, or A is dependent on B if A should be matched The number of flow entries or nodes in G

f u ∈ V , u ∈ [0, n]
A node in DAG, also indicates a flow entry in flow table

e fu , fv ∈ E An edge in DAG, indicates f u → f v m
The number of flow dependency requirements or edges in G c ma x

The largest diameter of the sub-graph in G c a v g

The average diameter of the sub-graph in G phyaddr ( f u )

The physical address that stores f u in TCAM val ( A)

The flow entry or node in physical address A first, without loss of generality, we define a flow entry A is dependent on a flow entry B if B should be matched first. We also use A → B to indicate A is dependent on B directly. Moreover, if there is an entry C, and A → B → C, we can say A is dependent on entry C indirectly.

B. Flow entry update in existing hardware switches

Previous research shows that the main reason for TCAM slow update is the flow dependency maintenance based on an integer index or priority [START_REF] Lazaris | Tango: Simplifying SDN control with automatic switch property inference, abstraction, and optimization[END_REF]. In the TCAM, each flow entry has its physical address [START_REF] Pagiamtzis | Content-addressable memory (cam) circuits and architectures: A tutorial and survey[END_REF], and the TCAM always returns the entry with the highest physical address if it matches multiple entries. When adding a new flow entry, the switch firmware finds a correct place: the physical address which must be higher than flow entries with lower priority, and moves all flow entries that physical addresses are lower than the newly arrived one to create a space (unused TCAM entry) in TCAM. Thus, updating a TCAM flow entry is similar to insert sorting algorithm, i.e., if we have n flow entries, we need n/2 movements on average to insert a new flow entry into the TCAM.

C. Dependency graph

Moving all flow entries that physical addresses is lower than the newly arrived flow entry will lead to a large number of entry movements. However, it is apparent that only moving flow entries that have a flow dependency relationship with the newly inserted flow entry also meets the flow dependency requirement.

For example, in Fig. 1(b), we need to move 4 flow entries to create a free space for the newly inserted entry if we utilize a priority-based solution, but in Fig. 1(c), only 2 movements are necessary. Thus, directly utilizing flow dependency rather than assigning a priority can significantly decrease the number of movements. The minimum dependency graph, which is a kind of Directed Acyclic Graph (DAG) [START_REF] Voellmy | Maple: simplifying sdn programming using algorithmic policies[END_REF], [START_REF] Wen | RuleTris: Minimizing rule update latency for TCAM-based SDN switches[END_REF], [START_REF] Song | Nxg05-2: Fast filter updates for packet classification using TCAM[END_REF] commonly used to describe the flow dependency in a flow table. We describe our notations in TABLE I. Specifically, we use a node to indicate a flow entry in the flow table, and we use a directed edge from node f b to f a to express node entry f a is dependent on entry f b . Also, if f a is dependent on entry f b , the physical address phyaddr ( f a ) must be higher than phyaddr ( f b ). In Fig. 1. An example of flow entry insertion in a TCAM based flow table. We firstly simply introduce how TCAM match works. There are 5 flow entries in the TCAM, and we use an uppercase letter to indicate an entry field in the flow entry. There are 3 match items in the match field: 'A,B,C' indicate a fixed item, and '*' indicate 'ANY' (omitted). 'ANY' means it will match any possible value in the packet header. If there is an incoming packet with packet header "CAA", the flow entry "CAA", "C*A" and "***" are matched, but only "CAA" is the match result. This is because "CAA" has the highest physical address. In (a), we need to insert a new entry with match field "C*A". (b) shows the movements if the flow dependency implied by priority, and (c) shows the movements if the flow dependency implied by DAG. Usually, utilizing DAG can significantly decrease the number of movements.

Fig. 1(c), we can see that it is easy to reduce movements in DAG.

The diameter of a graph is equivalent to the length of the "longest shortest path" between any two nodes in the graph. Intuitively, c ma x indicates how complex the flow dependency is in a flow table. In most cases, such as in routing tables and access control lists, c ma x n. Usually, a DAG, converted from a routing table or access control list, may have sub-graphs since the DAG is composed of several disconnected parts. The existence of disconnected parts will not affect the dependency between flow entries, It can decrease the expected number of movements. Thus, c avg < c ma x n.

D. TCAM update scheduler

For inserting a flow entry into the TCAM, after the correct place for the newly inserted entry is chosen, a sequence of flow entry movements is applied in order to make the chosen space free in the TCAM. Such a sequence is called update sequence, which is created by the TCAM update scheduler, part of the switch firmware.

We use (I, Due to the large time cost of the priority-based solution, a more efficient algorithm is needed to calculate an update sequence from graph elements (such as nodes and edges).

RuleTris utilizes a dynamic programming algorithm with the time complexity O(n 2 ) in the TCAM update scheduler to calculate the update sequence. However, it lacks efficiency when n is large. Motivated by our observation that the length of most update sequences is not longer than c ma x , and the average length is about c avg , we design an optimized algorithm whose time complexity is related to c ma x or c avg . Moreover, as deleting a flow entry from TCAM is simpler than inserting one in most cases [START_REF] Wen | RuleTris: Minimizing rule update latency for TCAM-based SDN switches[END_REF], we first discuss the flow entry insertion in Section III and IV.

III. THE WORKING FLOW OF FASTRULE

In this section, we give an overview of FastRule. We use Fig. 2 as an example to present the workflow of flow entry insertion in FastRule. The first stage is the compiler, which converts a request of flow entry insertion into a request of node insertion in DAG. There are many approaches to contribute a compiler, and we can apply existing approaches, e.g., the one in RuleTris [START_REF] Wen | RuleTris: Minimizing rule update latency for TCAM-based SDN switches[END_REF], to our framework. Usually, the output contains a node: a flow entry f , and all flow dependency requirements that f must satisfy. The third stage is the TCAM; we apply the update sequence into TCAM by TCAM API. In our evaluation, we use the API provided by ONetSwitch [START_REF] Onetswitch | Open Source Hardware for SDN[END_REF].

The second stage searches for a sequence of TCAM entry movements, i.e., an update sequence, which starts with the newly inserted flow entry and ends with a free space in TCAM. We design an algorithm using a greedy strategy, which is an approach that always takes the locally optimal choice. To put it simply, the algorithm constantly finds the address with the least number of movements for creating a free space for the newly inserted entry in a candidate address set. Each candidate address is associated with an integer metric. The smaller the metric is, the more optimal the address (using less number of movements to create a free space in this address) is considered to be.

Fig. 2 gives a brief workflow of the second stage. Firstly, we must find candidate addresses for f before the greedy algorithm, and these candidate addresses must satisfy the flow dependency requirements of f . Next, an address A with the minimum metric is chosen from the candidates set and its f p = val ( A) is obtained. Then, f is inserted in A to displace f p , and a TCAM operation (I, f , A) is added to the update sequence. Next, the f p becomes the new f , and we must find candidate addresses which satisfy the flow dependency requirements of the new f in a new loop. The loop is over if there exists at least one free space in candidate addresses, which means the new f can be put into a free address. Usually, the loop performs O(c avg ) times.

Choosing the minimum metric from candidates contributes to the most dominant portion of time in FastRule. In the bottom of the second stage, we give three methods, which have different time complexity to get the minimum metric:

1) On-demand: Computing the metric of all candidates from scratch every time. Choosing the minimum metric from candidates set has an O(c avg n) time complexity. 2) Pre-compute with array: Utilizing an array to save metrics of all candidates, and updating metrics after the loop is over. Choosing the minimum metric from candidates has an O(n) time complexity, while updating metrics has an O(c avg ) time complexity. 3) Pre-compute with BIT: Utilizing a modified Binary Indexed Tree (BIT) to save metrics for all candidates, and updating metrics after the loop is over. Choosing the minimum metric from candidates has an O(log n) time complexity, updating metrics has an O(c avg (log n) 2 ) time complexity.

The BIT is a data structure that is modified to get the minimum metric in all candidates within log time. In Section IV, we briefly introduce our greedy algorithm and BIT, and we also discuss how we optimize FastRule by transforming the on-demand version to the pre-compute with BIT version. The final time complexity of the on-demand version is O(c 2 avg n). The pre-compute with array version is O(c avg n), and the pre-compute with BIT version is O(c avg (log n) 2 ).

As we have mentioned above, the time for the second stage is called firmware time, and the time for the third stage is called TCAM update time. Compared to previous solutions, FastRule can significantly decrease the firmware time and does not increase TCAM update time in most cases. We evaluate FastRule in terms of firmware time and TCAM update time in Section VI.

IV. GREEDY ALGORITHM

In this section, we first describe how to find candidate addresses for f , and then we give a brief description of the greedy algorithm. We firstly introduce the on-demand version. Then, we introduce the pre-compute with array version, and describe the algorithm of updating metrics. Last, we introduce BIT, and describe how to update metrics in BIT. In this section, without loss of generality, we assume that the highest TCAM physical address and free space are in the top.

A. On-demand: finding candidate addresses

When receiving an incoming request from the DAG compiler, such as inserting a node f with flow dependency requirements f a → f → f b , it is precisely that candidate addresses for f range from phyaddr ( f a ) +1 to phyaddr ( f b ). In another case, if node f is an output of the greedy algorithm in the last loop, the flow dependency is f → f b , where phyaddr ( f b )phyaddr ( f ) is the minimum. In other words, f b is the nearest node which f depends on. Thus, candidate addresses for f range from phyaddr ( f ) + 1 to phyaddr ( f b ) in this case.

B. Address metric computation

As we have mentioned, the greedy algorithm needs to choose a candidate address A whose metric is the minimum. We use M ( A) to indicate the metric, whose formal definition is given below.

Definition 1. M ( A) is the number of nodes in a specific path P( A) in DAG that starts from val ( A) and ends with val ( A l ). The out-degree of val ( A l ) must be 0. For all pair of addresses

A i , A i+1 in path P = {val ( A), val ( A 1 ), val ( A 2 ), ...val ( A l )}, they satisfy A i+1 ≤ A t for any A t ∈ { A t |e val ( A i ), val ( A t ) ∈ G}.
Intuitively speaking, path P starts from the node in address A, and ends with a node that is not dependent on any nodes. For any pair of addresses A i , A i+1 in path P, the node in A i is dependent on the node in A i+1 , and A i+1 must be the nearest address from A i .

We can use a depth-first search (DFS) algorithm in Algorithm 1 to find P and its length M ( A) for any address A:

C. Greedy algorithm

After f , the node to be inserted, and its candidate addresses are available, we can start the greedy algorithm to get the update sequence. We describe the greedy algorithm in Algorithm 2.

We use a recursion form to describe the algorithm. The algorithm finds the address with minimum metric in candidates from line 5 to 9, insert f in A, and output a TCAM operation (I, f , A) to update sequence in 12. We invoke the algorithm with new f p and new candidate addresses in line 11 to 12. If there exists a free space, the recursion will stop at line 14.

We give an example to describe how it works in Fig. 3.

Algorithm 2: SCHEDULE: Output TCAM update sequence Input: Candidate addresses phyaddr ( f a ) to phyaddr ( f b ), node f Output: Update Schedule U ( f ) f p is the node whose address has the minimum metric A is the physical address of f p succ( A) is the address of the nearest (in address) successor of f p h is the current minimum metric

for k ∈ (phyaddr ( f a ), phyaddr ( f b )] do Compute M (k) if M (k) ≤ h then h ← M (k), A ← k f p ← val (k) 10 if exists succ( A) then 11 f a ← A + 1, f b ← succ( A) 12 U ( f ) ← (I, f , A)∪ SCHEDULE( f a , f b , f p ) 13 else 14 U ( f ) ← (I, f , A) 15 return U ( f )
Before we prove the correctness of our algorithm, we first give Proposition 1. Proposition 1. Suppose there is a node f which satisfies f a → f and the out degree of node f is 0. If there exists at least one free space that physical addresses is higher than phyaddr ( f a ) in the flow table, it can always find an address A to insert f . Proposition 1 tells us that if f is not dependent on any node, and the physical address of free space is higher than phyaddr ( f a ), it can always be inserted successfully.

Proof 1. In line 5, phyaddr ( f b ) is the entry with the highest TCAM physical address in the flow table. After running line 5 to 9, we can always find A with M ( A) = 0, and f is inserted at line 14.

Then, we can state the following proposition.

Proposition 2. The greedy algorithm can always find a solution if there exists at least one free space in the flow table.

Proof 2. For current node f , and candidate addresses phyaddr ( f a ) to phyaddr ( f b ), we have the following cases.

1) if the out-degree of f is 0 ( f is not dependent on any nodes), then choose an address that is a free space in the candidate addresses set, and insert f into the free space.

A solution hence exists. 2) if the out-degree of f is not 0, and there is an address that is a free space in the candidate addresses set, insert f into the free space. A solution hence exists. 3) if the out-degree of f is not 0, and there is no free address in the candidate addresses set, then choose node f p whose addressing metric is the minimum in the candidate addresses set, and call the algorithm with f p as new f . From the definition of candidate addresses set, if there is only one address in the set, f p satisfies the existence condition, f → f p . As G is a DAG (no loop exists), the out-degree of f p selected in case 3) will reach 0 after a finite number of iterations. Thus, case 3) will turn into case 1) eventually. In case 1), the free space must be higher than phyaddr ( f a ). If the free space is lower than phyaddr ( f a ), it must be occupied by the previous call in case 2). Thus, according to Proposition 1, the algorithm can find a solution.

The time complexity of the greedy algorithm can be outlined as follows: the time complexity for line 5 to line 9 is O(c avg n), and the greedy algorithm needs c avg times to stop. Thus the total time complexity is O(c 2 avg n).

D. Using an array data structure to store metrics

In Algorithm 2, the function from line 5 to line 9 is choosing the minimum metrics in candidate addresses, which costs most of the time in the greedy algorithm. As we have mentioned above, in order to prevent computing metrics from scratch, we can use an O(n) array to store pre-computed metrics. The tradeoff is the maintenance time of updating the array after each loop. We also use M[] to indicate the array. We describe our maintaining algorithm in Algorithm 3 for M[] after inserting a new node into the flow table. ). The only selection in candidate address is 0x3, M (0x3)= 4, and P(0x3) is 0x3, 0x5, 0x7, 0x8. We insert node f = 9 at 0x3. The f p = 5, and we call SCHEDULE(0x4,0x5,5). We have two available selections for A in candidate addresses: 0x4 and 0x5. M (0x4)= 2 and P(0x4) is 0x4, 0x6. M (0x5)= 3 and P(0x5) is 0x5, 0x7, 0x8. We choose 0x4 as A since M(0x4)< M (0x5). The f p = 4, and we insert node f = 5 at 0x4. In e) and f), we insert node 4 and 2. Eventually, the flow table will become b). From Fig. 4 we can see that the algorithm updates M[] by two steps: 1) Update the metrics for addresses that are in the update sequence U ( f ). 2) Update the metrics for addresses whose nodes are directly or indirectly dependent on node f .

The time complexity can be depicted as follows. Modifying an element in array M[] costs O(1). From step 1) we have

Algorithm 3: UPDATE: Update M[] after inserting node f at A Input: A, U ( f ),M[] DAG G Output: An updated M[] 1 U ( f )
is the update schedule created by SCHEDULE 2 for let h be the last address to the first address in U ( f ) do

3 if h is not the last address in U ( f ) then 4 M[w] ← M[h] 5 w ← h 6 M[A] ← M[succ[A]] + 1 7 Q is a queue, Insert A to Q 8 while Q is not empty do 9 h is the head of Q, dequeue h from Q 10 if h is not A then 11 M[h] ← M[h] + 1 12
for w is the neighbor of h that satisfies succ[w] = j do E. Using a modified Binary Indexed Tree to store metrics

As we have mentioned in the previous section, utilizing Binary Indexed Tree (BIT) (also called Fenwick Tree) can decrease the time complexity of line 5 to line 9 in Algorithm 2 to O(log n). We discuss the design of BIT in detail in this section.

1) Original BIT data structure: The original BIT data structure is used for quickly calculating the cumulative frequency. Suppose there is an array R[] that has n elements, BIT can get the sum

R[1 . . . a] = a i=1 R[i], a ∈ [1, n]
in O(log n) with space complexity O(n) by maintaining an array B[]. As each integer p can be represented as

2 k 1 + 2 k 2 + • • • + 2 k q , For example. 11 = 1 + 2 + 8, the sum R[1 . . . 11] can also be represented by R[1 . . . 11] = R[11(1)]+R[9 . . . 10(2)]+ R[1 . . . 8(8)]. It is easy to decompose an integer p into 2 k 1 + 2 k 2 + • • • + 2 k q by utilizing a function LOWBIT(x) = x&(-x)
(& is bit and). LOWBIT(x) can get the integer whose value equals to the rightmost 1 in the binary presentation of x, such as LOWBIT(1011 2 ) = 0001 2 , LOWBIT(1010 2 ) = 0010 2 . BIT uses an another array B[] to store the sum 2) Minimum Range Query: In array based Algorithm 2, the function of line 5 to line 9 is to find the minimum metrics in array M[], which takes O(n) times. This is a minimum range query problem, which can be solved by a modified BIT in O(log n) times.

B[x] = x i=x-LOWBIT(x)+1 R[i], x ∈ [1, N] like B[11] = R[11], B[10] = R[9 . . . 10], B[8] = B[1 . . .
We can perform a minimum range querying by changing the definition of B[] from sum ( ) to minimum value: 3) Update: In the original BIT, if we update M[i] by increasing or reducing a value ∆, we only need to increase or decrease ∆ in all B[ j] whose range includes i. However, in the scenario of minimum range query, we need to recompute all B[ j] whose range includes i. However, if we directly compute each B[ j] by definition, the time complexity will be O(n log n). From Fig. 5(b), we can use computed

B[x] = min(M[i]), i ∈ [x -LOWBIT(x) + 1, x], x ∈ [1, n]
B[ j -2 k ], 2 k < LOWBIT( j) ≤ 2 k+1 to update B[ j]
. Thus, we give the updating algorithm in Algorithm 5. The time complexity is O((log n) 2 ). Thus, the time complexity of the greedy algorithm is decreased from O(c avg n) to O(c avg log n), and the time complexity of updating metrics is increased from O(c avg ) to O(c avg (log n) 2 ). Overall, the time complexity of the BIT version is O(c avg (log n) 2 ).

Algorithm 5: UPDATEBIT: Update M[i] in BIT Input: BIT B, new value M[i], n is size of M and B Output: The updated BIT B 1 j ← i 2 while j ≤ n do 3 B[ j] ← R[ j] 4 k ← 1 5 while k ≤LOWBIT( j) do 6 B[ j] ← min(B[ j], B[ j -k]) 7 k ← k * 2 8 j ← j+LOWBIT( j)

V. FASTRULE IN DIFFERENT TCAM LAYOUTS

A. Free spaces interleaved between non-free spaces

In most cases, all flow entries are arranged in the bottom (or top, depending on the arrangement of physical address) of the TCAM (such as in the leftmost figure in Fig. 6), and the free space is in the top (or bottom) of the TCAM. We call this layout as the original layout. The main disadvantage of this design is that it may occur a large number of entry movements if the new entry is inserted near the bottom (top) of the flow table. In some other interleaved layouts, the TCAM keeps j free spaces (unused TCAM entries) in every i non-free spaces [START_REF] Vamanan | TreeCAM: decoupling updates and lookups in packet classification[END_REF], as shown in Fig. 6, in anticipation of inserting and deleting of flow entries. The average loop times of the greedy algorithm improves to i.

j=1 i=2 j=2 i=2 j=1 i=1 a) b) c) d)
Fig. 6. The TCAM keeps j free spaces (unused TCAM entries) in every i non-free spaces. a) is the original layout, with the free space in the top of the TCAM. We assign i = 1 and j = 1 in b), which means there exists 1 free space in every 1 non-free space. In c), we assign i = 1 and j = 2, and in d), we assign i = 2 and j = 2. Obviously, it is convenient to find a free space for newly inserted entries.

However, it can decrease to c ma x if all intermediate spaces are filled up. In order to keep this layout, the firmware needs to re-arrange existing entries at intervals. This may involve extra entry movements during the re-arrangement, which is considered as overhead. We evaluate FastRule in this layout by varying i and j in Section VI.

B. Free spaces in the middle

Another TCAM layout is to separate all flow entries into two parts, one part in the bottom and the other part in the top, and the free spaces are in the middle [START_REF] Shah | Fast updating algorithms for TCAM[END_REF]. Moreover, the insert and delete behaviors in this layout are quite different from the original layout. In this section, we discuss insert/delete behaviors in this particular layout. In the original layout, the time complexity of the greedy algorithm is related to c avg . In this particular layout, we can reduce the time complexity by designing update policies. The largest movements can be upper bounded by

c a v g 2 .
As the example shown in Fig. 7 (b), we separate flow entries in the flow table into two parts: some entries in the bottom, and others in the top. Moreover, if we use m t and m b to indicate the largest number of movements for the bottom parts and top parts respectively, the largest m t and m b are smaller than c a v g 2 definitely. As the example shows in Fig. 7 (b), this separation moves free spaces into the middle, and it can lower the upper bound of the number of movements significantly. 1) Insert: If the newly inserted node f satisfies f a → f → f b , and phyaddr ( f a ) and phyaddr ( f b ) are both in the bottom part or top part of the TCAM, we just insert f at bottom part or top part. Otherwise, we need to insert f at the free space in the middle part. Before we insert f into the middle part, we need to judge whether the bottom or top is feasible to insert. We compare the number of flow entries m t and m b , and define a threshold t; if m tm b > t, which means the number of flow entries in the top part is larger than in the bottom part, we insert the new entry in the bottom part. Otherwise, we insert the new entry in the top part. Inserting f in the middle part does not cost any flow entry movements.

An alternative choice is to keep m t and m b smaller than

c a v g 2
all the time. This can decrease the maximum number of movements, but may also increase the number of movements during the maintenance, which is considered as overhead. Balancing m t and m b in a proper interval is a good choice.

There is another consideration when we insert flow entry into the free space. As an example in Fig. 8 b), inserting several flow entries in order into continuous free spaces may cost extra movements. An easy solution is to randomly choose a free space from these continuous free spaces each time when inserting the new flow entry.

2) Delete: Deleting a flow entry is more complicated than in the original layout. We have two options:

1) Dirty delete: Delete the flow entry, left the space available for newly inserted flow entries. 2) Balance delete: Delete the flow entry, and then use other existing flow entries to fill this space. Both two options have advantages and disadvantages. If we use the Dirty delete, free spaces are not in the middle of the flow table; this will waste much space in TCAM. If we use the Balance delete, as an example shows in Fig. 9 a) and b), we have to move other entries to the free space, which is considered as overhead. Moreover, we still have to balance entries between the top and bottom to make sure |m t -m b | ≤ t.

We have evaluated both this layout (insert with dirty delete, insert with balance delete) and the original layout in our evaluation section to show the differences in efficiency.

VI. EVALUATION

We evaluate FastRule through experiments on ONetSwitch [START_REF] Onetswitch | Open Source Hardware for SDN[END_REF], which is an open-source hardware OpenFlow switch. ONetSwitch is a ZedBoard with an up to 800Mhz Cortex-A9, 512MB DDR3 RAM. We use C++ to implement our framework and use g++ provided by Xilinx to cross-compile without any optimization. We evaluate the average TCAM update time and firmware time by measuring 1, 000 random updates.

1) Large size TCAM emulation: The original TCAM in ONetSwitch is pretty small (256 entries in ONetSwitch45), which is not enough for the experimental evaluation. RuleTris solves this problem by emulating a large size TCAM in a Linux server; in the server, they evaluate their algorithm on the emulated TCAM and output the number of TCAM moves that is needed for TCAM update -as each TCAM move costs a constant amount of time (0.6ms), it uses the total number of TCAM moves times the average latency of a TCAM move to estimate the TCAM update time. We use a more accurate way to emulate large size TCAM. Similarly to RuleTris, we also use a Linux server to evaluate our algorithm, but it is only used to ensure the correctness of our algorithm (by checking whether flow entries in emulated TCAM are in the correct physical address). In order to emulate a large size TCAM with a small size (ONS HW 2) Data set: To confirm that our methods are robust and scalable enough, we evaluate FastRule on various type of flow tables: two from Access Control List (ACL4, ACL5), two from Firewall (FW4, FW5) and one from Routing Table (ROUTE). For ACL4, ACL5 and FW4, FW5, we firstly use the well-known policy generator ClassBench, with configuration names ACL4, ACL5, FW4, FW5 provided in ClassBench [START_REF] Taylor | Classbench: A packet classification benchmark[END_REF], to generate policies, and use ClassBench-ng [START_REF] Matoušek | Classbench-ng: Recasting classbench after a decade of network evolution[END_REF] to covert these generated policies into OpenFlow entries. For ROUTE, we download an L3 routing table(routeviews-rv2-20170606) from CAIDA [START_REF]Center for Applied Internet Data Analysis[END_REF], and use ClassBench-ng [START_REF] Matoušek | Classbench-ng: Recasting classbench after a decade of network evolution[END_REF] to convert a subset of prefixes into OpenFlow entries. We summarize characteristics of these flow tables in TABLE II. The number of flow dependency m ranges from 37 to 38225 in ACL4, 3 to 4557 in ACL5, 365 to 24130 in FW4, 168 to 40303 in FW5 and 169 to 31381 in ROUTE. From m we can see d in is small since 10% flow entries have a flow dependency. It is obvious that the number of flow dependency in FW4, FW5 are larger than the number in ACL4, ACL5. Moreover, ROUTE has a larger c avg than others. We also prepare a data set of flow updates to flow tables with each size. We generate 250 updates for the flow table with 250 entries, 500 updates for the flow table with 500 entries, and 1000 updates for the andd) is the final state of the flow table. In b), we insert flow entries in order, we can find we need to move the orange node 3 times, and to move the blue node 2 times. In c), we do not insert flow entries in order, we can find we do need any extra movements for the orange node and the blue node in the best case.

… … … … … … … … … … … … … … … … … … a) b) c) d)

a) b) d) c)

Fig. 9. An example of deleting flow entry. From a) and b), we can see that after the entry (orange node) was deleted, the free space was occupied by other flow (blue node) entry immediately. The situation is the same in c) and d). We just delete the entry (orange node), and we do not need any extra movement.

flow table with 1k, 2k, 4k, 10k, 20k, 40k entries. Moreover, we generate two types of update. The first type only contains entry insertion, and the second type contains an entry insertion and an entry deletion after the insertion. As for flow entry insertion, we create a new f that satisfies f a → f → f b , where f a and f b are randomly chosen from existing entries in the flow table. As for the deletion, we randomly delete a flow entry in the flow table. The reason why we choose random updates is that the time complexity of our algorithm only depends on n and c avg ; 1, 000 updates can keep a relatively stable log n, and random insertions will not change c avg much. If c avg increased significantly, newly inserted entries must be inserted like a chain, e.g., the new entry that needs to be inserted is always just dependent on the recently inserted entry.

3) Finite size of TCAM: In each evaluation, the TCAM size equals the sum of existing entries and inserted entries.

Thus, for first type, the TCAM sizes are 500 for 250 updates over 250 existing entries, and 1k for 500 updates over 500 existing entries respectively. For the second type, TCAM sizes are 1.1k, 2.1k, 4.1k, 10.1k, 20.1k and 40.1k. For the first type of update, the TCAM will be full of flow entries eventually, and for the second type of update, the number of entries in the TCAM will not change. Since the time complexity of our algorithm depends on n and c avg , which is the number of flow entries and the average diameter in the graph, the efficiency of our algorithm does not depend on the finite size of TCAM. If there is a free space in TCAM, our algorithm can find a way to insert a flow entry.

4) Layout and algorithm:

In section V, we have introduced the impact of layout and insert/delete behaviors. In the evaluation, we use FR-SB to indicate the separated layout with balance delete, FR-SD to indicate the separated layout with dirty delete, FR-O to indicate the original layout. Moreover, we use RuleTris to indicate the dynamic programming algorithm in RuleTris, and Naïve to indicate the widely used insertion sort algorithm. Also, we evaluate FastRule in TCAM layout with j free spaces in every i non-free spaces. Although the finite size of TCAM does not affect the algorithm efficiency, the separated layout may change c avg , which may result in higher inserting efficiency.

5) Firmware time and TCAM update time:

We measure the firmware time, which is the time of computing the update sequence from a DAG-based or priority-based flow entry update in the switch firmware: the time is measured from when the computation starts till it is ready to apply the update sequence to the TCAM. We also measure the TCAM update time, which includes all update times when applying the update sequence to the TCAM: we fetch the ADDENTRY(), DELETEENTRY() APIs from ONetSwitch SDK, and call these APIs to insert/delete entries in specific physical addresses in TCAM, then the time is measured from the TCAM updating start to the end. The firmware and TCAM update times are measured separately on the physical OpenFlow switch.

A. Firmware time: computing update sequence Firstly, we show the average firmware time on these flow tables in Fig. 10. We choose ACL4, FW5 and ROUTE with 250 to 40k entries in flow tables to show how the overhead increases. In the experiments, we feed 250 updates to the table with 250 entries, 500 updates to the table with 500 entries and 1, 000 updates to tables with other sizes. In Fig. 10(a), 10(b) and 10(c), each update only contains one insert to the ACL4, FW5 and ROUTE tables. In Fig. 10(d), 10(e) and 10(f), every two updates sequentially contain one insert and one delete to the ACL4, FW5 and ROUTE table. We do not add FR-SD in Fig. 10(a), 10(b) and 10(c) since the time used by FR-SB and FR-SD is equal if there is no delete update. The error bar indicates the maximum firmware time in the evaluation.

The firmware times evaluated in ACL4 table are shown in Fig. 10(a) and 10(d). In all cases, the naïve algorithm is the slowest, which takes more than 1, 000 times our algorithms in a 10k-entry table. The reason is that it needs to locate the suitable place in every update, and assign a new priority for all entries that need to be moved within the TCAM. The RuleTris performs better than the naïve solution (100 times the naïve algorithm in a 2k entries flow table), but it is still slower than our algorithms. Moreover, with the increase in flow table size, the time used by the RuleTris and naïve algorithm increase rapidly, but our algorithms can remain stable. Different layout and delete behavior can also affect the efficiency. If updates only contain insert, FR-SB is a little bit faster than the FR-O. However, If the update contains both insert and delete, FR-SB is slower than FR-SD and FR-O. We give a brief analysis in subsection VI-E. Moreover, the maximum firmware times of FastRule algorithms are shorter than the average time of others. delete entry operations does not depend on c avg . Moreover, it obviously shows that FR-SB is slower than FR-SD and FR-O in all types of flow tables due to the balance delete overhead, and FR-SD is the fastest method.

D. TCAM layout with j free spaces in every i non-free spaces

As we have mentioned above, there is another TCAM layout that keeps j free spaces (unused TCAM entries) in every i nonfree spaces. In order to confirm that FastRule is scalable in this TCAM layout, we evaluate FastRule in this layout with several combinations that have different i and j. Moreover, we also evaluate RuleTris for comparison. We give our evaluation result for the TCAM update time in TABLE III. We give the TCAM update time for ROUTE with flow table size from 250 to 20K. From the result we can see that with the same i, the TCAM update time is smaller when j is larger in most cases. It can be explained that more free spaces between non-free spaces makes fewer movements for the newly inserted entry (the average loop times of the greedy algorithm improves to i). Also, with the same j, the TCAM update time is larger when i is larger in most cases. Moreover, from the result we find that with the increasing size of the flow table, the TCAM update time decreased rapidly except j = 0. This conclusion also indicates that arranging free spaces between non-free spaces is better than arranging them in the top (or bottom) of the TCAM.

We give the comparison for the firmware update time between FastRule and RuleTris in Fig. 13. We give the firmware update time for ROUTE with flow table size from 250 to 10K.

From the result, we can see that with the increasing size of flow table, the firmware time of RuleTris decreased (except j = 0). The firmware time of FastRule is about 10 times than RuleTris in 10K size. In other words, if there are large amounts of free spaces between non-free spaces in the TCAM, the firmware time of RuleTris is smaller than FastRule. This is because utilizing BIT costs a constant time in finding the free space. However, the layout with j = 0 is the most utilized TCAM layout, which makes FastRule faster in most real-world scenarios.

E. Analysis

In this section, we give some brief analysis to explain the efficiency differences between our algorithms and RuleTris. Moreover, we also analyze the reason why efficiency differences exist among FR-SB, FR-SD and FR-O.

1) Comparison with DP-based solution (such as RuleTris): The efficiency of our algorithm derives from a lower time complexity than previous solutions. The DP-based solution needs a double nested loop: the first loop is iterating all addresses from the address that needs to be inserted to the highest, which needs to take O(n); the second loop is updating the number of movements from current address (the address in the first loop) to the highest address, which takes O(n). Overall, it takes O(n 2 ) for one insertion. The time complexity of our solution is based on the expected number of movements, which is O(c avg ).

We only move c avg flow entries for each flow entry update in TCAM. Usually, c avg is very small in real-world data sets. RuleTris utilizes a loop to calculate the potential movements in a range of flow entries that may be moved, and the range may be n. Although c ma x can also reach n in the worst case, but it seldom occurs in real-world data sets. Moreover, some timewasting initiation processes (Line 4 to Line 8 in Algorithm 1 of RuleTris [START_REF] Wen | RuleTris: Minimizing rule update latency for TCAM-based SDN switches[END_REF]) can also be observed in RuleTris, which makes it less efficient than our approach.

2) Efficiency among different layouts and delete behaviors: As we have mentioned above, differences exist between two layouts, and also between delete behaviors. It can be observed that the firmware time with FR-SB is slightly lower than FR-O with pure insert updates, but the firmware time with FR-SB is about 1.5 to 2 times the FR-SD and FR-O times, when the insert updates and deletes update parts count for half each. FR-SB separates all entries into top and bottom, and creates a space in the middle of the flow table. On the one hand, the newly inserted entry falling into the free space can decrease the firmware time of maintaining existing entries, and on the other hand, a separated flow table can decrease c ma x and c avg , which can also decrease the firmware time since the time complexity of our algorithm is based on n and c avg . However, the situation is different if the proportion of delete updates increased. FR-SB needs to continuously maintain free space in the middle of the flow table, which can increase the delete overhead. If the deleted entry is not near the middle free space, it costs at least one movement to fill the space created by the deleted entry. The FR-SD and FR-O do not cost any movements in delete update, which makes them more efficient than FR-SB.

VII. RELATED WORK

In this section, we introduce some related work aimed at enhancing update efficiency and range minimum querying. There are several existing approaches that can increase flow update efficiency by decreasing flow entry movements. Some approaches utilize new flow table design, e.g. CacheFlow or Mercury [START_REF] Katta | Cacheflow: Dependency-aware rule-caching for software-defined networks[END_REF], [START_REF] Chen | The case for making tight control plane latency guarantees in SDN switches[END_REF], others usually utilize DAG to decrease the flow entry movements in incremental TCAM update [START_REF] Vamanan | TreeCAM: decoupling updates and lookups in packet classification[END_REF], [START_REF] He | Partial Order Theory for Fast TCAM Updates[END_REF], [START_REF] Van Lunteren | Fast and scalable packet classification[END_REF]- [START_REF] Wen | RuleTris: Minimizing rule update latency for TCAM-based SDN switches[END_REF].

Hierarchical flow table design: As we have mentioned before, although TCAM has high-speed matching efficiency, the power and cost requirements limit its scale for supporting more storage capacity. Though slow in lookup, SRAM has larger storage size, which can be used to increase the capacity of the flow table. CacheFlow [START_REF] Katta | Cacheflow: Dependency-aware rule-caching for software-defined networks[END_REF] maintains a hierarchical flow table design (high-speed TCAM and low-speed SRAM). By utilizing "cover-set", CacheFlow can decrease unnecessary flow entry movements between TCAM and SRAM. Although our work does not utilize hierarchical design, CacheFlow still motivates us towards an efficient algorithm for solving flow dependency.

TCAM update cache: TCAM uses physical address to determine which rule (flow entry) need to be returned when multiple rules are matched. In other words, the TCAM firmware needs to maintain a correct order to keep dependency between flows in TCAM. Usually, the cost of keeping dependency increases with TCAM size. Mercury [START_REF] Chen | The case for making tight control plane latency guarantees in SDN switches[END_REF] is a framework that can decrease the number of entry movements by keeping a nominal amount of TCAM space as updating cache. In short, Mercury trades part of the TCAM space for update efficiency.

Incremental TCAM update: A partial order updating theory [START_REF] He | Partial Order Theory for Fast TCAM Updates[END_REF] has been proposed to explore the design space for incremental TCAM updating algorithm. It gives the lower bounds on the TCAM updating performance. Although DUOS [START_REF] Mishra | DUOS-Simple dual TCAM architecture for routing tables with incremental update[END_REF] and P 2 C [START_REF] Van Lunteren | Fast and scalable packet classification[END_REF] have considered the flow dependency problem and reduced the updating cost, these solutions still show limitations in computing the updated minimum dependency graph. In contrast, both RuleTris [START_REF] Wen | RuleTris: Minimizing rule update latency for TCAM-based SDN switches[END_REF] and our work can achieve the minimal updating cost by using the policy compiler, which can generate the minimum dependency information. Chain Ancestor Ordering (CAO) and its optimized version CAO OPT [START_REF] Vamanan | TreeCAM: decoupling updates and lookups in packet classification[END_REF], [START_REF] Shah | Fast updating algorithms for TCAM[END_REF] propose a separated layout design to decrease the number of TCAM updating movements. We have evaluated CAO OPT (separated layout) in our evaluation section.

Range Minimum Query: Besides the binary indexed tree (BIT), there are also other schemes that can perform minimum range querying in log n time complexity. The Range Minimum Query (RMQ) problem is defined as finding the minimum element in an array A[0 . . . n] from indexed L (query start) to indexed R (query end), where 0 ≤ L ≤ R ≤ n. The simplest solution is to perform a loop in the given range, from R to L. This solution needs O(n) time to query the minimum element. If the array A is static, Sparse Table (ST) [START_REF] Bender | The LCA problem revisited[END_REF] only has O(1) querying time complexity and O(n log n) preprocessing time complexity. However, the array A is not static in our situation. A data structure called segment tree [START_REF] Berg | More geometric data structures[END_REF], can be used to speed up the query. Preprocessing the segment tree takes O(n) time, and one range minimum query takes O(log n) time. Also, segment tree needs extra O(n) space to store the segment tree. Compared to BIT, which only needs an array to store the whole tree, segment tree has to maintain a real tree structure, which needs a significant constant time. Also, the querying algorithm for segment tree is a recursion-based algorithm that is much slower than the querying algorithm in BIT, which is only a loop-based algorithm.

VIII. CONCLUSION

In this paper, we propose a novel memory update algorithm, called FastRule, to efficiently address the issue of performance bottleneck in TCAM memory update for OpenFlow switches. To decrease the TCAM update latency, we design a greedy algorithm with a specific data structure. First, we propose a fast algorithm with time complexity of O(c 2 avg n) for quickly calculating the update sequence in a flow table of size n, where c avg is the average diameter of a directed acyclic graph. Second, we optimize this algorithm with binary indexed tree to further increase its efficiency, leading to the reduced time complexity of O(c avg (log n) 2 ). Moreover, we also optimize our algorithm in some special layouts of the flow table. Meanwhile, We prove the correctness of the greedy algorithm and prove that we can always find a solution with our algorithm. The evaluation results show that our algorithm can be about 100x faster than the state-of-the-art approach, in a 1k-entry flow table. Furthermore, we analyze the impact of TCAM layouts and delete behaviors on update efficiency. The results demonstrate that FastRule can also decrease the TCAM update latency in scenarios with different layouts and delete behaviors.

  A flow entry with match field "C*A" needs to be inserted into the flow table. We use the uppercase letter to indicate match items of the match field. Usually, an entry with wildcard match field must be dependent on a precise one. Such as "**A" → "C*A", "**B" → "A*B ". If the flow dependency is implied by priority, the firmware introduces a priority 20 to the new flow entry, and schedule the insertion according to 20 into space with physical address 0x5. It needs 4 movements in order to provide the space. We call it a priority-based solution, which is a naïve solution widely utilized in OpenFlow switches. If the flow dependency is implied by a DAG, the firmware finds that the newly inserted entry has no dependency on entry "A*B" and "**B" in DAG. It needs only 2 movements to provide the space. We call it DAG-based solution.

  f , A) to indicate the insert operation, and use (D, A) to indicate the delete operation. For example, we can use the sequence (I, C * A, 0x5), (I, * * A, 0x4), (I, A * B, 0x3), (I, * * B, 0x2) and (I, * * * , 0x1) to indicate the update sequence in Fig. 1(b). Also, we can use the sequence (I, C * A, 0x5), (I, * * A, 0x2), and (I, * * * , 0x1) to indicate the update sequence in Fig. 1(c).

Fig. 2 .

 2 Fig. 2. The working flow of FastRule. We give the input and output of algorithms in the greedy algorithm, and we explain how they work with quotation marks.

  Fig.3. An example of creating an update sequence for inserting f into DAG. From a) we can see there are 9 nodes (entries) in the DAG (table), and we need to insert a new node 9 that is dependent on node 5, and node 6 is dependent on the new node 9. b) shows the flow table after node 9 is inserted. The length of the update sequence is 4. Only nodes with blue color need to be moved, and the update sequence U(0x3) is (I,9,0x3),(I,5,0x4),(I,4,0x6),(I,2,0x9). We give the detail of the first two callings of algorithm SCHEDULE in remain figures to show how our algorithm works. We use green color to indicate candidate addresses. In c), we call SCHEDULE(0x3,0x3,9). The only selection in candidate address is 0x3, M (0x3)= 4, and P(0x3) is 0x3, 0x5, 0x7, 0x8. We insert node f = 9 at 0x3. The f p = 5, and we call SCHEDULE(0x4,0x5,5). We have two available selections for A in candidate addresses: 0x4 and 0x5. M (0x4)= 2 and P(0x4) is 0x4, 0x6. M (0x5)= 3 and P(0x5) is 0x5, 0x7, 0x8. We choose 0x4 as A since M(0x4)< M (0x5). The f p = 4, and we insert node f = 5 at 0x4. In e) and f), we insert node 4 and 2. Eventually, the flow table will become b).

Fig. 4 .

 4 Fig. 4. An example for updating M[] after the greedy algorithm. We update metrics (M[phyaddr (9)], M[phyaddr (5)], M[phyaddr (4)], M[phyaddr (2)]) whose addresses in U (9) and we also update metrics (M [phyaddr (6)], M[phyaddr (7)], M [phyaddr (8)]). These nodes (6, 7, 8) are directly or indirectly dependent on node 9. We use M[A] = M ol d[B] to indicate the update process. M ol d[B] is the metric of physical address B before update.

13

  Insert w to Q to update metrics in the update sequence and the c avg is the length of the update sequence, the time complexity of step 1) is O(c avg ). From step 2) we have to update metrics of the node that are directly or indirectly dependent on f . The time complexity of step 2) is O(c avg (1+d in )) while d in is the average in-degree of G. We find d in < 1 in all data sets, which means that most flow entries are not depended on by other entries. Thus, the total time complexity of updating metrics is O(c avg ). The time complexity of the greedy algorithm decreases to O(c avg n) since the time complexity of line 5 to line 9 decrease to O(n).

  8]. If we use binary to represent an integer, such as 11 = 1011 2 , we can find 11 can be decomposed by minus the rightmost 1 in its binary presentation. For example, 1011 2 = 1010 2 + 0001 2 , 1010 2 = 1000 2 + 0010 2 . Thus, R[1 . . . 11(1011 2 )] = B[11(1011 2 )] + B[10(1010 2 )] + B[8(1000 2 )]. For computing any R[a . . . b], a, b ∈ [1, n], we can compute R[1 . . . b] -R[1 . . . a] directly.

From Fig. 5 (

 5 a) we can see that querying the min(M[a . . . b]) by computing min(M[1 . . . b], M[1 . . . a]) is not possible. We can only query M[a . . . b] by decomposing the range [a, b] into several ranges in B[x] = min(M[(x -LOWBIT(x) + 1) . . . x]) and find the minimum value in these ranges. We give our algorithm in Algorithm 4. The time complexity is O(log n).

Fig. 5 .Algorithm 4 : 3 r 4 b ← b - 1 5 7 b

 543417 Fig. 5. An example for querying and updating BIT. In a), we query the minimum value in M[1 . . . 6], which can be decomposed as B[4] = M[1 . . . 4] and B[6] = M [4 . . . 6]. Thus, we can only compare B[START_REF] Niven-Jenkins | Requirements of an MPLS transport profile[END_REF] and B[START_REF] Hu | Scalability of control planes for software defined networks: Modeling and evaluation[END_REF] to get the minimum value is 1. In b). we update the value of M [6] from 9 to 2. Thus, we have to check all ranges that include M[START_REF] Hu | Scalability of control planes for software defined networks: Modeling and evaluation[END_REF]. The first is B[START_REF] Hu | Scalability of control planes for software defined networks: Modeling and evaluation[END_REF], which is the minimum value of M[START_REF] Jain | B4: Experience with a globally-deployed software defined WAN[END_REF] and M[START_REF] Hu | Scalability of control planes for software defined networks: Modeling and evaluation[END_REF], and we update B[6] = 2. The next is B[START_REF] Berde | ONOS: Towards an Open, Distributed SDN OS[END_REF], which is the minimum value of B[START_REF] Niven-Jenkins | Requirements of an MPLS transport profile[END_REF], B[START_REF] Hu | Scalability of control planes for software defined networks: Modeling and evaluation[END_REF], R[START_REF] Yeganeh | Beehive: Simple distributed programming in software-defined networks[END_REF], R[START_REF] Berde | ONOS: Towards an Open, Distributed SDN OS[END_REF]. Due to B[4] = 1, we do not change the value of B[START_REF] Berde | ONOS: Towards an Open, Distributed SDN OS[END_REF].

Fig. 7 .

 7 Fig.7. An example of inserting an entry into the original design and separated design. There are five entries in the flow table. In a), if the new entry is inserted in the bottom of the table, we need 4 moves to create a space for the new entry. In b), if we separate existing entries into two parts located in the bottom and top, only 1 move is necessary to create a space for the new entry.

Fig. 8 .

 8 Fig. 8. Inserting flow entries in order continuous free spaces may cost extra movements. a) is the initial state of the flow table,and d) is the final state of the flow table. In b), we insert flow entries in order, we can find we need to move the orange node 3 times, and to move the blue node 2 times. In c), we do not insert flow entries in order, we can find we do need any extra movements for the orange node and the blue node in the best case.

Fig. 10 .

 10 Fig.10. The firmware time in ACL4, FW5 and ROUTE. We do not put Naïve in 20k and 40k since Naïve can not finish in half an hour.

Fig. 10 (

 10 Fig. 10(b), 10(c) and 10(e), 10(f) show the result of firmware time evaluated in FW5 and ROUTE tables. Similarly to the previous experiment, we observe that our algorithms are at least 10 times faster than RuleTris due to the time saved in the firmware time.

Fig. 12 .

 12 Fig. 12. The firmware time among different layouts and delete behaviors.

FirmwareFig. 13 .

 13 Fig.[START_REF] Huang | High-fidelity switch models for software-defined network emulation[END_REF]. The firmware time in ROUTE with different i and j. We do not give figures of 20K and 40K since there are similar to 10K.

(logn)^2)

	The Greedy
	Algorithm
	A Flow Entry
	Update Request
	"Insert a flow entry f"
	Update Request
	(Flow Entry)
	to
	Update Request
	(DAG)
	Compiler
	TCAM update time
	A DAG Update
	Request
	"Insert a node f in
	DAG"
	On-demand:O((cavg^2)*n)
	Array:O(cavg*n)
	BIT:O(cavg* Firmware time

loop O(cavg) times

		(Input f. Output:
		candidate addresses)
		"Find candidate
		addresses for f"
			loop,f=fp
		(Input:f, candidate
		addresses. Output: fp, TCAM operation)	Update Schedule
		"Output node fp,		" I,f	"
		whose address A has
		minimum metric in
		candidates. Output
		TCAM operation:
		(I,f,A)"
							Apply Update
							Schedule in
		Minimum metric in candidates		TCAM
		Compute	Or	Fetch	Pre-	compute	TCAM API
		O(n*cavg)		Fetch
			Array:O(n)
			BIT:O(logn)
				Maintain
			Array:O(1)
			BIT:O((logn)^2)
	1st stage	2nd stage		3rd stage

  finding the nearest node that is depended by the node in the current address (the first address is A); using the searched nodes and its physical address as the input in next search turn. If there is no new node found, the search finishes. The time complexity of the DFS algorithm is O(c

Algorithm 1: FIND:Finding the path P Input: Address A, DAG G Output: P s is the neighbor of h with minimum physical address h ← val ( A), s ← ∞ for w that is the neighbor of h in G do if phyaddr (w) ≤ s then s ← phyaddr (w) P ← P∪ FIND (s) return P avg ). As G is a DAG that does not have any loop, the algorithm can always get a result.

  3. An example of creating an update sequence for inserting f into DAG. From a) we can see there are 9 nodes (entries) in the DAG (table), and we need to insert a new node 9 that is dependent on node 5, and node 6 is dependent on the new node 9. b) shows the flow table after node 9 is inserted. The length of the update sequence is 4. Only nodes with blue color need to be moved, and the update sequence U(0x3) is (I,9,0x3),(I,5,0x4),(I,4,0x6),(I,2,0x9). We give the detail of the first two callings of algorithm SCHEDULE in remain figures to show how our algorithm works. We use green color to indicate candidate addresses. In c), we call SCHEDULE(0x3,0x3,9

  table. In a), if the new entry is inserted in the bottom of the table, we need 4 moves to create a space for the new entry. In b), if we separate existing entries into two parts located in the bottom and top, only 1 move is necessary to create a space for the new entry.

  TABLE SIZE, defined in ONetSwitch) TCAM in ONetSwitch, we modulo the original address with ONS HW TABLE SIZE (such as (I, f , A%256), ONS HW TABLE SIZE=256 in ONetSwitch45 [34]) if the original address is larger than or equal to ONS HW TABLE SIZE, and update the TCAM with the modulo address. The update time is not affected by utilizing the modulo address.

  The TCAM update time in ACL4, FW5 and ROUTE. We do not put Naïve in 20k and 40k since Naïve can not finish in half an hour.

		FR-SB	FR-O	RuleTris	Naive		FR-SB	FR-O	RuleTris	Naive		FR-SB	FR-O	RuleTris	Naive
	TCAM Update Time (ms)							TCAM Update Time (ms)	1 10 100 1000							TCAM Update Time (ms)	1 10 100 1000
									0.1									0.1
									250	500	1K	2K	4K		10K 20K 40K		250	500	1K	2K	4K	10K 20K 40K
				Flowtable size						Flowtable size					Flowtable size
			(a) Insert, ACL4				(b) Insert, FW5					(c) Insert, ROUTE
		FR-SB	FR-SD	FR-O	RuleTris	Naive	FR-SB	FR-SD	FR-O	RuleTris	Naive		FR-SB	FR-SD	FR-O	RuleTris	Naive
	TCAM Update Time (ms)	1 10 100 1000						TCAM Update Time (ms)	1 10 100 1000							TCAM Update Time (ms)	1 10 100 1000
		0.1							0.1									0.1
		250	500	1K	2K	4K	10K 20K 40K	250	500	1K	2K	4K	10K 20K 40K		250	500	1K	2K	4K	10K 20K 40K
				Flowtable size					Flowtable size					Flowtable size
		(d) Insert and delete, ACL4		(e) Insert and delete, FW5			(f) Insert and delete, ROUTE
	0.01 0.02 0.03 0.04 Fig. 11. 0.00 Firmware Time (ms) Data type	Acl4	Acl5	Fw4	Fw5	Route
			FR-SB		FR-O

TABLE III THE

 III AVERAGE TCAM UPDATE TIME (MS) FOR ONE UPDATE W IN DIFFERENT i AND j (TABLE: ROUTE) (WITH j FREE SPACES (UNUSED TCAM ENTRIES) IN EVERY i NON-FREE

						SPACES)
	i	j	250	500	1K	2K	4K	10K	20K	40K
	1	0	1.15	1.13	1.13	1.13	1.08	1.04	1.13 1.07
	1	1	0.84	0.83	0.83	0.64	0.56	0.56	0.52 0.56
	1	2	0.60	0.58	0.58	0.56	0.52	0.52	0.58 0.53
	1	3	0.59	0.57	0.57	0.52	0.57	0.56	0.54 0.53
	2	1	0.91	0.91	0.88	0.69	0.55	0.52	0.52 0.52
	2	2	0.69	0.70	0.69	0.59	0.52	0.56	0.56 0.52
	3	1	0.99	1.00	0.99	0.81	0.64	0.56	0.58 0.52

The work was supported in part by Natural Science Foundation of China under Grant 61571136, and by 863 program under Grant 2015AA016106. Part of this work was reported in IEEE ICDCS 2018


Emmanuel Paradis

Interactions between spatial and temporal scales in the evolution of dispersal rate

Keywords: dispersal, extinction, polymorphism, selection, patchy populations

The evolution of dispersal rate is studied with a model of several local populations linked by dispersal. Three dispersal strategies are considered where all, half, or none of the offspring disperse. The spatial scale (number of patches) and the temporal scale (probability of local extinction) of the environment are critical in determining the selective advantage of the different dispersal strategies. The results from the simulations suggest that an interaction between group selection and individual selection results in a different outcome in relation to the spatial and temporal scales of the environment. Such an interaction is able to maintain a polymorphism in dispersal strategies. The maintenance of this polymorphism is also scale-dependent. This study suggests a mechanism for the short-term evolution of dispersal, and provides a testable prediction of this hypothesis, namely that loss of dispersal abilities should be more frequent in spatially more continuous environments, or in temporally more stable environments.

Introduction

Dispersal (permanent movement of individuals among local populations) is a ubiquitous characteristic of living beings. Clearly, any species that has not the ability to move in space at one moment or another is greatly exposed to extinction risks. The evolution of dispersal rate (the proportion of dispersing offspring) has received considerable attention from theoreticians (e.g., [START_REF] Johnson | Evolution of dispersal: theoretical models and empirical tests using birds and mammals[END_REF][START_REF] Ludwig | Evolutionary stability of plant communities and the maintenance of multiple dispersal types[END_REF][START_REF] Mcpeek | The evolution of dispersal in spatially and temporally varying environments[END_REF][START_REF] Olivieri | Metapopulation genetics and the evolution of dispersal[END_REF] that showed an apparent paradox: some theoretical studies, based on either ecological or population genetic models, showed that dispersal is counter-selected in a spatially heterogeneous but temporally stable environment [START_REF] Balkau | Selection for migration modification[END_REF][START_REF] Teague | A model of migration modification[END_REF][START_REF] Asmussen | Evolution of dispersal in density-regulated populations: a haploid model[END_REF][START_REF] Hastings | Can spatial variation alone lead to selection for dispersal?[END_REF][START_REF] Holt | Population dynamics in two-patch environments: some anomalous consequences of an optimal habitat distribution[END_REF]. This paradox is not surprising if we look at the long-term fitnesses of the disperser and philopatric strategies. The fact that some offspring disperse towards unfavourable habitats decreases the fitness of the disperser strategy relative to the philopatric one. Only the strategy with no dispersal can persist in the long-term [START_REF] Morris | On the evolutionary stability of dispersal to sink habitats[END_REF]. Temporal variability in the environment, however, favors non-null dispersal rates [START_REF] Kuno | Dispersal and persistence of populations in unstable habitats: a theoretical note[END_REF]. Competitve interactions also favors dispersal when the environment is temporally constant [START_REF] Hamilton | Dispersal in stable habitats[END_REF][START_REF] Comins | Evolutionary stable dispersal strategies[END_REF][START_REF] Frank | Dispersal polymorphisms in subdivided populations[END_REF]. It has been suggested by some theoreticians that a combination of spatial and temporal variations is required to select for dispersal [START_REF] Gadgil | Dispersal: population consequences and evolution[END_REF][START_REF] Roff | Population stability and the evolution of dispersal in a heterogeneous environment[END_REF][START_REF] Levin | Dispersal strategies in patchy environments[END_REF]. Furthermore, some observations of polymorphism in dispersal strategies in natural populations suggest that selection against dispersal could be actually important [START_REF] Harrison | Dispersal polymorphisms in insects[END_REF][START_REF] Venable | The evolutionary ecology of seed heteromorphism[END_REF][START_REF] Gouyon | A conflict between two sexes, females and hermaphrodites[END_REF][START_REF] Olivieri | The genetics of transient populations: research at the metapopulation level[END_REF][START_REF] Peroni | Seed size and dispersal potential of Acer rubrum (Aceraceae) samaras produced by populations in early and late successional environments[END_REF]Roff, 1994a;[START_REF] O'riain | A dispersive morph in the naked mole-rat[END_REF]. Most theoretical studies on the evolution of dispersal focus on the equilibrium conditions (often by means of ESS techniques), and do not consider the transient behaviours of their model, thus ignoring the time scale of the evolution of dispersal rate. Nevertheless, such a time scale has been suggested to be critical in the maintenance of dispersal polymorphism in some insects (Roff, 1994a).

In this paper I examine the temporal scale of the evolution of dispersal rate in a variable and heterogeneous environment, and propose a mechanism for the maintenance of dispersal polymorphism. This theoretical study results in testable predictions on the short-term evolution of dispersal rate.

Model

I considered a model where space was structured into several discrete habitat patches.

Population growth during reproduction was modelled by the discrete-time exponential logistic model:

Nit+1 = Nit exp(ri(1 -Nit/Ki)),
where Nit is size of population i at time t, ri is the growth rate of population i, and Ki is the carrying capacity for population i.

After breeding, a fraction f (determined genetically) of the offspring dispersed and were then distributed equally in all patches. No mortality during dispersal was assumed. Each generation consisted of a population growth episode and a dispersal episode. The existence of two kinds of habitat was assumed: a high-quality habitat (source habitat)

where ri > 0, and a low-quality habitat (sink habitat) where ri < 0. Persistence in sink habitats may be allowed by dispersal, since an isolated population in this kind of habitat declines to extinction. Three genotypes were considered which differed in the fraction of offspring dispersing: f = 0, 0.5, or 1, respectively. Each genotype can mutate to any others at a rate of 10 -4 . The evolutionary dynamics of this model were studied by numerical simulations. I considered different values of population growth rates in source (rs) and sink habitats (rk), of carrying capacity in both habitats (Ks and Kk, respectively), and number of patches of both habitats (xs and xk, respectively). For a given combination of these parameters simulations were replicated and run with various initial conditions to check the repeatability of the results and the stability of the equilibria observed. Most simulations were run for 2,500 generations; for some combinations of parameters, equilibrium was not reached after 2,500 generations and were run for longer times (up to 200,000 generations). The initial model was set with rs = 1, rk = -1, Ks = Kk = 1000, xs = xk = 1. This two-patch source-sink model was then modified in order to evaluate: (i) the effect of fragmentation of source and/or sink habitats (by varying xs and/or xk and keeping total carrying capacity constant), (ii) increase of 'quality' in the sink habitat (by increasing rk but keeping it negative), (iii) and variation in patch sizes (by varying Ks and/or Kk). Temporal variability in the environment was then included in the model in the form of local extinction. Extinctions in each patch occurred with a probability pe varying between 0.001 and 0.5, and were not temporally or spatially correlated.

Further simulations were made to evaluate how critical are some assumptions on the dynamics of the model. It was assumed that only three dispersal strategies can exist to make the model more tractable but also because this is realistic with respect to some empirical studies that showed, for some organisms, dispersal strategies to have a similar categorization [START_REF] Gouyon | A conflict between two sexes, females and hermaphrodites[END_REF]Roff 1994a). Some simulations were replicated with a fuller range of genotypes; specifically two situations were examined: 11 genotypes with f = 0, 0.1, 0.2, … or 1; and 21 genotypes with f = 0, 0.05, 0.1, 0.15, … or 1. The assumption on the mutation rate was also tested by replicating some simulations with different values for this parameter (10 -5 or 10 -6 ). The importance of the assumed genetic mechanism (i.e., three clones with mutations) was evaluated by running simulations with no mutation at all and five individuals of each genotype in each population as initial conditions. There were no selective values associated with the different genotypes, they grew equally within each population during the population growth process. Differential growth of genotypes was only caused by differential reproductive output in the whole set of populations.

In the present model variations in spatial and temporal scales were modelled by variations in the grain of the environment, and in the rate of local extinction, respectively [START_REF] Fahrig | Relative importance of spatial and temporal scales in a patchy environment[END_REF]. The scale of dispersal did not vary since in all situations the modelled organisms could reach all patches during dispersal; however, the grain of the encountered environment varied when the number of patches did so. This also applies to the temporal scale of the organisms which was modelled by the time step of the simulations; on the other hand, the temporal scale of the environment varied when the rate of local extinction did so.

Results

In all simulations with a constant environment (pe = 0) the equilibrium was finally reached when the f = 0 genotype was fixed in all populations. However, the convergence towards this equilibrium was markedly different in relation to the spatial structure of the environment. Results below are with five f = 1 individuals in a source patch as initial conditions. For the initial model described above, the mean value of f among populations (denoted μ), quickly decreased and was equal to zero after around 200 generations (Fig. 1). A similar result was observed when both source and sink habitats were fragmented (2 ≤ xs = xk ≤ 50). When only the source habitat was fragmented (2 ≤ xs ≤ 200, xk = 1), the convergence towards the equilibrium μ = 0 was slower: the stronger the fragmentation, the slower the convergence (Fig. 1a). When only the sink habitat was fragmented (xs = 1, 2 ≤ xk ≤ 200), the convergence towards the equilibrium was quick. When the rate of population growth in the sink habitat was increased (-0.5 ≤ rk ≤ -0.005), the convergence towards the equilibrium μ = 0 was critically slower (Fig. 1b). When patch sizes varied (50 ≤ Ks ≤ 5000, 50 ≤ Kk ≤ 5000), convergence was always quick. I examined the interactions between spatial and temporal scales of the environment by including local extinctions in the simulations with xs = 1, 5, 20, or 100. As expected, selection of high dispersal rates occurred in these simulations, the intensity of this selection being stronger when the rate of local extinction pe increased (Fig. 2).

Important differences, however, were apparent with respect to xs. When xs was large (20 or 100) μ quickly increased with increasing pe and the f = 1 genotype was selected for even for moderate values of pe. For xs = 5, μ was equal to 0.5 for some range of extinction probability (0.05 ≤ pe ≤ 0.2). Examination of the genotypic frequencies for these simulations shows that the mixed dispersal strategy (f = 0.5) was selected for (Figs. 3 and4). For a relatively high extinction rate (pe = 0.4), two genotypes coexisted (Fig. 5). For a very high extinction rate (pe = 0.5), the pure dispersal strategy (f = 1) was fixed. When xs = 1, the situation was similar to the one just previously described for xs = 5 as long as pe ≤ 0.2 (Fig. 2). If pe increased further then there was no transition with a stable polymorphism as previously described, that is for pe = 0.25 the f = 0.5 genotype was fixed, and for pe = 0.3 the f = 1 genotype was fixed.

Simulations done to evaluate some of the assumptions gave different output for some aspects of the present model. When a larger range of dispersal rates was assumed and there was no temporal variability in the environment, the final result was not changed.

i.e. the f = 0 genotype was fixed; fixation occurred after longer times (two to three times compared to the same habitat structure) as on average more mutation events were necessary for this genotype to appear in the populations. When local extinctions occurred (pe > 0), the results changed remarkably. In the different situations examined, there was one genotype almost fixed (one or two other genotypes remained at low frequencies) but fixation occurred after considerably more time (between 10,000 and 20,000 generations), and fluctuations in genotypic frequencies still occurred. There was a positive association between pe and the f-value of the fixed genotype, the genotypes persisting at low frequencies had an f-value close to that of the fixed genotype (for instance, when the f = 0.8 genotype was nearly fixed, the f = 0.75 and f = 0.85 genotypes persisted at frequencies lower than 0.05).

When the genotypic mutation rate was varied, the only difference with the results described above was that they were observed after a time that was inversely proportional to the mutation rate. When absence of mutation was assumed, no change was noticed relative to the equilibria, the only difference was that they were reached far more quickly (less than 10 generations with the initial model) because the occurrence of the different genotypes was no more conditioned on mutation (note that now the model is fully deterministic when there is no local extinction). Nevertheless, the same differences were observed with respect to the time to reach equilibrium.

Discussion

The present study suggests that interactions between spatial and temporal scales are critical in the evolution of dispersal. Two results emerge that seem fairly new: (i) the difference in selective advantage between a disperser and a philopatric strategy is critically affected by the fragmentation of the favourable habitat, and (ii) a polymorphism in dispersal strategy can be maintained provided the favourable habitat is fragmented and the probability of local extinction is correctly tuned.

The first result can be explained by a mix of effects previously observed in models of the evolution of dispersal. When the environment is constant in time and all patches are of equal quality there is a selective advantage for dispersal because this strategy can replace the philopatric one in all sites while the latter can compete only on the sites where it is present [START_REF] Hamilton | Dispersal in stable habitats[END_REF]. On the other hand, when habitat quality varies among sites then there is a selective disadvantage for dispersal since some offspring disperse in patches of less quality decreasing the long-term fitness of this strategy [START_REF] Hastings | Can spatial variation alone lead to selection for dispersal?[END_REF][START_REF] Morris | On the evolutionary stability of dispersal to sink habitats[END_REF]. In the present model with environment constant in time, the selective advantage of the philopatric strategy could be considerably decreased by fragmentation of the favourable habitat, and needs considerably more time to be fixed when this fragmentation is high than in the twopatch model.

The fact that dispersal is selected for when there is temporal variation in the environment is not surprising [START_REF] Kuno | Dispersal and persistence of populations in unstable habitats: a theoretical note[END_REF][START_REF] Levin | Dispersal strategies in patchy environments[END_REF]. More interesting is that different results were observed depending on the number of patches of source-habitat and the probability of local extinction. How to explain such results? In the present model no selective values were assigned to the different genotypes, and their relative growth is only due to the dynamic properties of the model. It has been argued that the evolution of dispersal is dictated by the opposite forces of individual and group selections [START_REF] Van Valen | Group selection and the evolution of dispersal[END_REF][START_REF] Craig | Group selection versus individual selection: an experimental analysis[END_REF][START_REF] Olivieri | Metapopulation genetics and the evolution of dispersal[END_REF]. Individual selection favours the genotype that produces the largest number of offspring by differential growth within each site; group selection favours the genotype that produces the largest number of offspring by differential extinction and colonization among sites. One can question whether it is appropriate to invoke group selection for the evolution of dispersal since dispersal is an individual trait and so should evolve in response to individual selection. The controversy about group selection comes from that some authors claimed that it is not necessary to invoke group selection since individual selection can account for the evolution of individual traits in general [START_REF] Wilson | The group selection controversy: history and current status[END_REF].

Several recent studies, however, showed that group selection can be an effective evolutionary force on individual traits acting in the same direction than individual selection or in an opposite direction [START_REF] Goodnight | Contextual analysis of models of group selection, soft selection, hard selection, and the evolution of altruism[END_REF][START_REF] Avilés | Interdemic selection and the sex ratio: a social spider perspective[END_REF]. Individual selection and group selection have the same effects, changes in the frequencies of genes or genotypes through time, but with different processes that are described above. Both selective forces are potentially present in a spatially structured population model (and in all real populations) and need to be considered equally.

In my model all genotypes experience the same extinction rate, so dispersal accounts for differences in the intensity of each type of selection. Dispersal is counter-selected by individual selection since it lowers growth within a patch compared to philopatry, but is selected for by group selection since it has a non-null colonization rate. When the number of patches increases there are greater opportunities for group selection to occur as well as when the probability of local extinction increases. For moderate number of patches and moderate extinction probability, individual selection and group selection balance each other so that the mixed strategy (half of the offspring disperse) is selected for. If the extinction probability slightly increases (for instance pe = 0.3) then a polymorphism is maintained only if the source-habitat is fragmented (xs = 5). On the other hand, the pure dispersal strategy is fixed and there is no polymorphism if xs = 1. This seems contradictory with the above statement that selection for dispersal is more intense when the number of patches increases. The contradiction is only apparent since with this value of pe the probability of simultaneous extinctions of all populations is relatively high if xs = 1 (0.3 2 = 0.09) compared to the case with xs = 5 (0.3 6 = 0.0007) leading to more opportunities for group selection to operate.

Several theoretical studies on the evolution of dispersal have been published. The originality of the present study is that I considered varying numbers of habitat patches. Roff (1994b) studied a model where dispersal evolved in relation to habitat persistence time, however, he assumed a different genetic mechanism for the transmission of dispersal rate. Roff concluded that the gene coding for a positive dispersal rate, even if recessive, is maintained in any population occupying a habitat with finite persistence time. The gene coding for a null dispersal rate can invade the population but is never fixed (Roff, 1994a(Roff, , 1994b)). The present model goes further than Roff's, and shows that there could be a relation between habitat persistence time and number of patches influencing the selective advantages of the different dispersal strategies. [START_REF] Mcpeek | The evolution of dispersal in spatially and temporally varying environments[END_REF] showed that a polymorphism for dispersal rate could be maintained in a two-patch model when habitat quality varied spatially and, either habitat selection was assumed, or the environment was temporally variable. In this latter situation, however, a strategy with habitat selection was able to invade the system and the polymorphism collapsed. [START_REF] Mcpeek | The evolution of dispersal in spatially and temporally varying environments[END_REF] modelled environmental temporal variability by random draws from a bivariate normal distribution. In the present study, the mechanism maintaining polymorphism in dispersal strategy is distinct from the one evidenced by [START_REF] Mcpeek | The evolution of dispersal in spatially and temporally varying environments[END_REF] and I showed that it is scaledependent.

Among the assumptions made in the model that could affect the conclusions, the one relative to no mortality cost of dispersal may be important since many models suggest that this parameter is critical [START_REF] Johnson | Evolution of dispersal: theoretical models and empirical tests using birds and mammals[END_REF]. However, dispersal is selected for in some situations even when there is greater mortality of dispersing individuals, the optimal dispersal rate being inversely proportional to the mortality cost [START_REF] Hamilton | Dispersal in stable habitats[END_REF]. It seems likely that a cost of dispersal would have changed the present results in that greater habitat fragmentation and extinction probability would have been required to select for dispersal, however, the general qualitative result would have remained unchanged.

Another assumption was that dispersal occurred spatially at random, i.e. there was no habitat selection. [START_REF] Morris | On the evolutionary stability of dispersal to sink habitats[END_REF] showed that habitat selection was necessary to select for dispersal in a temporally constant environment, a similar result was obtained by [START_REF] Mcpeek | The evolution of dispersal in spatially and temporally varying environments[END_REF]. These latter authors showed that a pure dispersal strategy with habitat selection is strongly selected in a temporally and spatially variable environment [START_REF] Mcpeek | The evolution of dispersal in spatially and temporally varying environments[END_REF]. This is due to the strong advantage of those strategies able to track environmental changes. These results seem to be easily extended to the present study: habitat selection would have selected for dispersal in all situations. A similar result relative to the maintenance of dispersal polymorphism would also have been obtained by correctly tunig the parameters of habitat selection.

Other assumptions of the present model have been evaluated by simulations. The value of the mutation rate is important in that when it is decreased, unsurprisingly, the dynamics of the model are slower. This shows that the time scale of mutation has also a role in the dynamics of the model. Mutation is critical here as it allows the philopatric strategy to appear in other populations. For some organisms (e.g. insects), passive dispersal may play the same role than mutation in allowing the philopatric strategy to disperse in distant patches; such passive dispersal being much less frequent than active dispersal.

Most of the simulations were run assuming that only three dispersal strategies could exist. Assuming more strategies showed that in most cases an intermediate strategy was selected for. This suggests that for each combination of habitat fragmentation and temporal variation there exists an optimal dispersal rate. Assuming continuous variation in dispersal rate may not be a realistic for some organisms. Further informations on the range of possible dispersal rates seem necessary in order to use the present model for particular organisms.

The present model gives rise to predictions on the short-term evolution of dispersal.

Selection for dispersal is expected to occur when the environment is fragmented or variable in time. To give testable predictions, the argument should be reversed: that is loss of dispersal abilities (for instance, brachyptery in insects) should be more frequent in spatially more continuous environments all other things being equal, or in temporally more stable environments all other things being equal.

Figure 1 .

 1 Figure 1. Evolution of the mean dispersal rate (denoted μ in the text) in a theoretical metapopulation (see the text for a detailed description of the model and the parameters), (a) the parameters are: rs = 1, rk = -1, Ks = Kk = 1000, xk = 1, xs varies as indicated on the curves, (b) the parameters are: xs = xk = 1, Ks = Kk = 1000, rs = 1, rk varies as indicated on the curves.

Figure 2 .

 2 Figure 2. Mean dispersal rate in the metapopulation averaged along several time steps, (a) along the 2,500 time steps of the whole simulation, (b) along the last 500 time steps in order to remove possible transients effects.

Figure 3 .

 3 Figure 3. Evolution of genotypic frequencies in the metapopulation with xs = 5 and pe = 0.05. Other parameters as in Fig. 1.

Figure 4 .

 4 Figure 4. Same as in Fig. 3 except pe = 0.2.

Figure 5 .

 5 Figure 5. Same as in Fig. 3 except pe = 0.4.

Acknowledgments

I thank Derek Roff for useful comments on a previous version of the manuscript.

Financial support for this study was provided by NERC grant GST/02/1197 as part of the NERC/SOAFED special topic on Large Scale Processes in Ecology and Hydrology.