Chedy Raïssi
email: chedy.raissi@inria.fr

Jian Pei
email: jpei@cs.sfu.ca

Towards Bounding Sequential Patterns *

Keywords: Towards Bounding Sequential Patterns H.2.8 [Database Management]: Database Applications-Data Mining; G.2.1 [Discrete Mathematics]: Combinatorics-Counting problems, generating functions Theory, Algorithms Sequential Pattern Mining, Combinatorics

published or not. The documents may come

INTRODUCTION

Sequence data is widely used in many applications. Consequently, mining sequential patterns and other types of knowledge from sequence data has become an important data mining task. The main emphasis has been on developing efficient mining algorithms and effective pattern representation [START_REF] Dong | Sequence Data Mining[END_REF]. However, an important fundamental problem still remains open: given a sequence database, can we have an upper bound on the number of sequential patterns in the database?

Any non-trivial answer to the question can find immediate applications in many sequence mining scenarios. For example, one issue in sequential pattern mining is that the runtime cannot be well estimated. That is, when a sequential pattern mining algorithm starts to run on a sequence database and keeps generating sequential patterns, one cannot tell how many more patterns will be generated and when the algorithm will stop. The progress of the mining algorithm cannot be estimated. If an upper bound on the number of sequential patterns can be obtained, the upper bound can be used to estimate the progress of the mining.

As another application example, building sequence data warehouses and conducting OLAP on sequences have found applications in, for example, web search [START_REF] Zhou | Olap on search logs: an infrastructure supporting data-driven applications in search engines[END_REF], customer trajectory analysis [START_REF] Lo | Olap on sequence data[END_REF], workflow analysis [START_REF] Gonzalez | Warehousing and analyzing massive rfid data sets[END_REF], and bioinformatics [START_REF] Cornell | Gims -a data warehouse for storage and analysis of genome sequence and functional data[END_REF]. Space is one of the central issues in building a sequence data warehouse. How much space does a data warehouse need on a given sequence database?

The problem of bounding sequential patterns is very challenging due to the combinatorial complexity of sequences. Unlike bounding frequent itemsets [START_REF] Geerts | A tight upper bound on the number of candidate patterns[END_REF], where each item can appear at most once in an itemset, an item may appear multiple times in a sequential pattern, which make the possible combinations much more numerous and complicated. To the best of our knowledge, no solid result has been reported in literature. Moreover, the difficulty of the problem has been well recognized. For example, Zaki [START_REF] Zaki | Spade: An efficient algorithm for mining frequent sequences[END_REF] affirmed, "It is difficult to derive a closed-form expression for the exact number of k-sequences".

In this paper, we tackle the problem of bounding sequential patterns. We make two significant contributions. First, we present, for the first time in the field of sequential pattern mining, strong combinatorial results on bounding the number of possible sequential patterns that can be generated for a given length k. Second, we introduce, as a case study, two novel techniques to estimate the number of candidate sequences. Fundamentally, our method is different from the results on bounding frequent itemsets [START_REF] Geerts | A tight upper bound on the number of candidate patterns[END_REF], since the Kruskal-Katona theorem [START_REF] Katona | A theorem of finite sets. Theory of Graphs[END_REF][START_REF]The number of simplices in a complex[END_REF], which is the major tool in bounding frequent itemsets, cannot be applied globally to sequences. We build different combinatorial tools based on the Whitney numbers of the poset of sequences and on prefix-itemset partitions. Using these combinatorial results, any sequence mining algorithm can efficiently compute upper bounds on the number of candidates to be searched. An extensive empirical study on both real data and synthetic data verifies the effectiveness of our methods. We believe that the results reported in this paper are a major breakthrough in the theory and foundation of sequential pattern mining, and may have a broad impact on other pattern mining problems.

The rest of the paper is organized as follows. Section 2 reviews the related work. Section 3 briefly reviews the preliminaries needed in our development. Section 4 introduces our new combinatorial results. In Section 5, we show how to apply our combinatorial results in different ways to derive an upper bound on the number of candidate sequences. An experimental study is reported in Section 6. We conclude our work and discuss several interesting directions in Section 7.

RELATED WORK

Since Agrawal and Srikant [START_REF] Agrawal | Mining sequential patterns[END_REF] introduced the problem of sequential pattern mining, many studies focused on developing efficient algorithms for sequential pattern mining, such as AprioriAll [START_REF] Agrawal | Mining sequential patterns[END_REF], GSP [START_REF] Srikant | Mining sequential patterns: Generalizations and performance improvements[END_REF] and SPADE [START_REF] Zaki | Spade: An efficient algorithm for mining frequent sequences[END_REF]. Several effective representations of sequential patterns have been proposed [START_REF] Yan | Clospan: Mining closed sequential patterns in large databases[END_REF][START_REF] Tzvetkov | Tsp: Mining top-k closed sequential patterns[END_REF]. However, to the best of our knowledge, no previous work obtains non-trivial results on estimating the number of candidates for sequential patterns.

A problem highly related to bounding sequential patterns is to bound frequent itemsets. A seminal paper by Geerts et al. [START_REF] Geerts | A tight upper bound on the number of candidate patterns[END_REF] shed light on the pure combinatorial problem that lies behind the estimation of candidates in frequent itemset mining [START_REF] Agrawal | Mining association rules between sets of items in large database[END_REF]. Using a well-known extremal combinatorics result, the Kruskal-Katona theorem [START_REF] Katona | A theorem of finite sets. Theory of Graphs[END_REF][START_REF]The number of simplices in a complex[END_REF], Geerts et al. [START_REF] Geerts | A tight upper bound on the number of candidate patterns[END_REF] provided hard and tight combinatorial upper bounds on the number of candidates. This result is also a theoretical basis for what is known as the inverse mining problem [START_REF] Ramesh | Feasible itemset distributions in data mining: theory and application[END_REF][START_REF] Ramesh | Distribution-based synthetic database generation techniques for itemset mining[END_REF], where the same Kruskal-Katona theorem is used to characterize properties of length distributions of frequent itemsets and their synthetic generation.

One may expect that the Kruskal-Katona theorem can be also used to tackle the sequential pattern bounding problem. Unfortunately, Leck [START_REF] Leck | Nonexistence of a kruskal-katona type theorem for subword orders[END_REF] affirmed that there is no theorem of the Kruskal-Katona type for sequential patterns. Therefore, in this paper, we explore other fundamentally different approaches to tackle the problem of bounding sequential patterns.

PRELIMINARIES

Let I = {i1, i2 . . . im} be a finite set of items. An itemset X ⊆ I is a non-empty subset of I. A sequence S over

I is an ordered list X1 • • • Xn , where Xi (1 ≤ i ≤ n) is an itemset. The length of a sequence S, denoted by |S|, is P n i=1 |Xi|.
A k-sequence is a sequence of length k. We denote by T(I) the (infinite) set of all possible sequences over I. A sequence database D over I is a finite set of pairs (SID, T ), where SID ∈ {1, 2, . . . , |D|} is an identifier and T ∈ T(I) a sequence over I.

Definition 1 (Subsequence

). A sequence S = X 1 • • • X n is a subsequence of another sequence S = X1 . . . Xm , denoted by S S, if n ≤ m and there exist 1 ≤ i1 < i2 < • • • < in ≤ m such that X j ⊆ Xi j (1 ≤ j ≤ n).
S is said to be a supersequence of S . S is called a proper subsequence of S, denoted by S ≺ S, if S S and S = S.

Immediately, we have the following property.

Property 1. The set T(I) with the binary relation is a partially ordered set (i.e., it is reflexive, antisymmetric and transitive).

Following with Property 1, we call (T(I), ) the partially ordered sequence set.

Definition 2 (Whitney numbers). In the context of the partially ordered sequence set (T(I), ), the Whitney numbers wi (i ≥ 1) are the numbers of i-sequences.

Definition 3 (Concatenation and merge). For sequences

S = X1 • • • Xn and S = X 1 • • • X m , we define the concatenation operator • such that S • S = X1 • • • XnX 1 • • • X m . S • S is called a concate- nation supersequence of S. We also define the merge operator such that S S = X1 • • • (Xn ∪ X 1 ) • • • X m . S S is called a merge supersequence of S.

Definition 4 (Prefix equivalence). Two sequences

S = X1 • • • Xn and S = X 1 • • • X n are said to be pre- fix equivalent, denoted by S ≡π S , if |S| = |S | and for (1 ≤ i < n), Xi = X i .
Let C be a set of sequences. We denote by [S]π(C) the set of the last itemsets of the prefix equivalence class of S, which is the set of the last itemsets in the sequences in C equivalent to S, i.e., [S]

COMBINATORIAL RESULTS

To find an upper bound on the number of sequential patterns, we start from calculating an upper bound on the number of potential sequential patterns of length k for every positive integer k. We tackle this problem by calculating the Whitney numbers for partially ordered sequence set.

The number of potential sequential patterns of length k is closely related to the number of different combinations made using the sequence extensions introduced in Definition 3. However, a direct estimation is difficult because it has to take into account the redundancy of some combinations. For instance, {a}{b, c, d}{a, b} can be constructed in many different ways: {a}{b} {c, d}{a, b} , {a}{b, c} {d}{a, b} , {a} • {b, c, d}{a, b} , etc. Developing a combinatorial formula that takes into account those redundancies is very difficult, if possible at all.

A simple observation can help to deal with the problem. A k-sequence S can only contain at most k itemsets. In fact, the number of possible k-sequences can be calculated by the number of concatenation extensions. For instance, for I = {a, b}, the number of 2-sequences is the number of sequences that are obtained from the following two ways.

• The concatenation extension from the empty sequence using a 2-itemset: ∅ • {a, b} ; and

• The sequences of 2 length-1 itemsets, which are concatenation extensions of all possible sequences with 1itemsets: {a} • {a} , {a} • {b} , {b} • {a} and {b} • {b} .

Clearly, this way of enumerating the sequences avoids the redundancy problem described earlier. The correctness was established as part of the PrefixSpan algorithm [START_REF] Pei | Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth[END_REF]. Using this observation, counting the number of k-sequences can be described by the following recurrence relation:

w k = k-1 X i=0 wi n k -i ! , ( 1
)
where n = |I|, w0 = 1, w1 = n, and k ≥ 01 . When |I| and k are both small, the above recurrence relation may be efficient for calculation. However, we would like to obtain an explicit formula. From the combinatorial point of view, this formula may help us understand the relations between counting sequential patterns and some other wellknown combinatorial problems. The understanding may lay down new ways of handling the sequential pattern mining problem.

In order to obtain such a formula, we want to represent the Whitney numbers w k in a generating function [START_REF] Wilf | Generatingfunctionology[END_REF][START_REF] Flajolet | Analytic Combinatorics[END_REF]

2 S(x) = X k w k x k (2)
From Equation ( 2), it follows that

w k = S k (0) k! , ( 3
)
where S k (x) is the k th derivative of S(x).

Obtaining the generating function in our case is far from trivial. One of the popular methods to find generating functions is to compute the discrete convolution of two formal power series, in other words, their Cauchy product. Recall that for two formal power series

P k a k x k and P k b k x k , their Cauchy product is P ∞ k=0 z k x k with z k = P k i=0 aib k-i .
As noted by Wilf [START_REF] Wilf | Generatingfunctionology[END_REF]: "It is certainly this product rule that accounts for the wide applicability of series methods in combinatorial problems".

In our case, we use one known formal power series, which can be trivially derived from the binomial theorem:

n X i=0 n i ! x n-i = (1 + x) n = D(x). ( 4
)
We apply the Cauchy product with S(x):

X k z k x k = S(x) • D(x) = ( X k w k x k ) • ( n X i=0 n i ! x n-i ) = ∞ X k=0 k X i=0 wi n k -i ! x k (5)
Thus, we have,

z k = k X i=0 wi n k -i ! (6)
Two cases are possible for z k , depending on the value of k. First, if k = 0, then z0 = w0. Second, if k > 0, then, from Equation (1), we have

z k = w k + k-1 X i=0 wi n k -i ! = 2w k (7)
Using ( 5), we can exhibit the generating function S(x):

X k z k x k = S(x) • (1 + x) n = z0 + X k≥1 2w k x k = w0 + 2 X k≥1 w k x k = 1 + 2(S(x) -1) (8)
Finally,

S(x) = 1 2 -(1 + x) n (9)
From this generating function, we can deduce an expression on the number of k-sequences that can be formed using n = |I| different items. From (9) it follows

S(x) = 1 2 " 1 1-1 2 (1+x) n " = 1 2 " 1 1-Z " = 1 2 X i≥0 Z i with Z = 1 2 (1 + x) n , = 1 2 X i≥0 1 2 i (1 + x) ni (10)
Therefore, the k th derivative of S(x) is:

S k (x) = X i≥0 ni! (ni-k)! (1 + x) ni-k 2 i+1 = k! X i≥0 ni! (ni-k)!k! (1 + x) ni-k 2 i+1 = k! X i≥0 `ni k ´(1 + x) ni-k 2 i+1 (11)
From Equation (3), we have

w k = X i≥0 `ni k 2i+1 (12)
We do not discuss the convergence case for the series S(x) with x = 0. In fact, the analytic nature of the generating function does not interest us here. Thus, we limit our view of a generating function to serving as only a formal power series, i.e., as an algebraic object rather than as an analytic one. The multiple links between the previous expression and well-known combinatorial problems are discussed in Section 7.

Example 2. Let I = {a, b}. The number of possible 2sequences can be calculated using the recurrence relation in Equation ( 1):

w2 = w0 2 2 ! + w1 2 1 ! = 1 + 4 = 5
The same result can be obtained with Equation ( 12):

w2 = P i≥0 ( 2i 2 ) 2 i+1 = 5.
Likewise, the number of possible 3-sequences can be computed through the recurrence relation in Equation ( 1):

w3 = w0 2 3 ! + w1 2 2 ! + w2 2 1 ! = 0 + 2 + 10 = 12
Using the formula in Equation ( 12), we have

w3 = P i≥0 ( 2i

ESTIMATION OF CANDIDATES

In this section, we use the combinatorial results to compute the upper bounds on the number of candidates in sequential pattern mining, which are naturally the upper bounds on the number of sequential patterns. We discuss two techniques.

A Basic Upper Bound

The first technique relies on the recurrence relation in Equation [START_REF] Agrawal | Mining association rules between sets of items in large database[END_REF]. Instead of using the Whitney numbers wi (0 ≤ i < k) to compute the number of candidate ksequences, we use the number of sequential patterns of every length i. Formally, we define C k , an upper bound on the number of k-sequence candidates as follows.

C k = k-1 X i=0 |F i D,σ | |F 1 D,σ | k -i ! with |F 0 D,σ | = 1 ( 13
)
Example 3. Consider our running example using the database Dex in Table 1.

Suppose σ = 5 8 .

The set of length-1 sequential patterns in

Dex is F 1 D,σ = { {a} , {b} , {c} , {d} }.
Accordingly, an upper bound on the number of length-2 candidates that can be generated from these 1-sequences is

C2 = |F 0 D,σ | `|F 1 D,σ | 2 ´+ |F 1 D,σ | `|F 1 D,σ | 1 = |F 0 D,σ | • 6 + |F 1 D,σ | • 4 = 6 + 16 = 22
The number 22 includes the 6 possible 2-sequences with only 1 itemset: { {a, b} , {a, c} , {a, d} , {b, c} , {b, d} , {c, d} }, and the 16 2-sequences with 2 itemsets, such as {a}{a} , {a}{b} , {d}{a} , etc. Unsurprisingly, any breadth-first search algorithm based on the Apriori paradigm generates exactly those 22 sequences. In such a case, the upper bound is tight and realizable.

Similarly, we have

C3 = |F 0 D,σ | `|F 1 D,σ | 3 ´+ |F 1 D,σ | `|F 1 D,σ | 2 ´+ |F 2 D,σ | `|F 1 D,σ | 1 = |F 0 D,σ | • 4 + |F 1 D,σ | • 6 + |F 2 D,σ | • 4 = 4 + 24 + 44 = 72
Notice that this basic upper bound is effective for sequence databases of a small number of items, that is, n = |I| is small, since it only relies on multiplying binomial coefficients. However, for real-world data sets containing thousands of items, this bound may be very loose.

Prefix-based Bound

The bounding method discussed in Section 5.1 is easy to implement in any breadth-first search sequence mining algorithm. However, it only uses very little information in bounding, and can be improved substantially. In sequential pattern mining, an algorithm often can access to more information than just the number of sequential patterns of a certain length. Often, all sequential patterns up to a certain length k are available. We develop a prefix-based bound to make use of this extra information to achieve a better estimation by locally applying the Kruskal-Katona theorem.

Theorem 1 (l-binomial representation [START_REF] Katona | A theorem of finite sets. Theory of Graphs[END_REF][START_REF]The number of simplices in a complex[END_REF]). Given two positive integers m and l, there exists a unique representation of m in the form

m = a l l ! + a l-1 l -1 ! + . . . + at t ! where a l > a l-1 > . . . > at ≥ t ≥ 1.
For instance, when m = 26 and l = 4, we have 26 = `6 4 ´+ `5 3 ´+ `2 2

´. The next theorem, the Kruskal-Katona theorem, gives a tighter upper bound on the size of the shade for a set of k-subsets.

Definition 6 (Shade). An itemset X ⊆ I is a k- subset if |X| = k. Let A
Theorem 2 (Kruskal-Katona Theorem [START_REF] Katona | A theorem of finite sets. Theory of Graphs[END_REF][START_REF]The number of simplices in a complex[END_REF]).

Let A be a set of k-subsets of I (k < |I|). |A| can be written as a k-binomial representation:

|A| = m = a k k ! + a k-1 k -1 ! + . . . + at t ! .
The cardinality of pA is bounded by In order to reflect this condition and generalize it to ksequences, we will use locally the Kruskal-Katona theorem, since it computes efficiently a tight upper bound on the shade of the set of the last itemsets for a given prefix equivalence class. Let us look at an example.

| p A| ≤ a k k + p ! + a k-1 k -1 + p ! + .
Procedure PB(): regrouping the sequences in prefix equivalence classes.

Data: F k D,σ

Result: Prefix-based upper bound value for the number of candidate k + 1-sequences P B ← 0;

1 foreach set A = [ S ]π(F k D,
(i) U = { {a, b} , {a, c} } (ii) V = { {a}{a} , {a}{b} , {a}{c} , {a}{d} } (iii) W = { {b}{a} , {b}{b} , {b}{c} } (iv) X = { {c}{a} , {c}{b} }

For each of these equivalence classes, we compute an upper bound based on the Kruska-Katona theorem. This theorem can be applied because the elements of the set

[ S ]π(V) are sets. For instance, from (ii), |[ {a}(a} ]π(F 2 D,σ )| = `4 1 ´= 4.

The cardinality of 1V is bounded by

| 1 V| ≤ 4 1 + 1 ! = 6 Similarly, | 1 U| ≤ 0, | 1 W| ≤ 3 and | 1 X | ≤ 1.
Thus, the upper bound on the number of sequences that can be generated using the operator is 0 + 6 + 3 + 1 = 10.

The •-extension case: Each of the sequences in F 2

D,σ

can be extended with one of the frequent items present in F 1 D,σ = { {a} , {b} , {c} , (d} }. In this example, the upper bound on the number of sequences that can be generated using the operator

• is |F 2 D,σ | • |F 1 D,σ | = 11 • 4 = 44.
In conclusion, P B3 = 10 + 44 = 54. That is, the maximum number of candidate patterns of length 3 that can be generated is at most 54, smaller than C3 in Example 3.

The only requirement for this approach is to regroup the sequences in prefix equivalence classes. This is usually implicitly done thanks to the data structures used in the sequential pattern mining algorithms, such as prefix-trees (i.e., trie structures). The pseudocode of the procedure is given in Procedure PB().

Further Improvements

The prefix-based upper bound works well with any breadthfirst search algorithms. Still, some further improvements are possible.

One may notice that handling the case of the operator • is quite trivial as it involves multiplying the number of frequent k-sequences with the number of frequent 1-sequences.

However, this way allows some false positives since not all 2-sequences of 2 items are frequent. Recall that any mining algorithm has access to the sequences in the database. Instead of blindly multiplying with the cardinality of the frequent 1-sequences, we can multiply only with the cardinality of the 2-sequences that can really result in sequence expansions. Let us illustrate this improvement using an example.

Example 6. Suppose that we want to extend the sequences from the prefix equivalence class A = { {a, b} , {a, c} } with the operator

|{ {a, b} }| • 3 + |{ {a, c} }| • 2 + |{ {a}{a} }| • 4 + |{ {a}{b} }| • 3 + |{ {a}{c} } • 2 + |{ {a}{d} }| • 0 + |{ {b}{a} }| • 3 + |{ {b}{b} }| • 3 + |{ {b}{c} }| • 2 + |{ {c}{a} }| • 2 + |{ {c}{b} }| • 2 = 26
The improved prefix-based upper bound in this case is

P B imp 3 = 10 + 26 = 36.
The implementation of this improvement bears negligible overhead in practice because all the needed sequences along with their extensions are already present in the data structures used by many sequence mining algorithms.

EMPIRICAL STUDY

In this section, we report an extensive empirical evaluation of our bounding techniques using real and synthetic data sets. All experiments were performed on an Apple MacBook computer with 2.8 Ghz Intel Core 2 Duo CPU and 4 Gb main memory, running Mac OS X 10.6.6 operating system. The bounding procedures were implemented in C++ along with a version of the algorithm SPADE using the Data Mining Template Library [START_REF] Zaki | Towards generic pattern mining[END_REF]. All the mathematical computation was processed using the GNU Multiple Precision Arithmetic Library3 . The source code and the data sets are available at http://www.loria.fr/~raissi/.

Data sets. In our experiments, we used one real data set and a group of synthetic data sets generated by the QUEST software 4 . The Amazon data set consists of a collection of 100, 000 product reviews from the website amazon.com. This is a sample of the data set used in [START_REF] Jindal | Opinion spam and analysis[END_REF]. Each review is a data sequence that has been lemmatized and grammatically filtered to remove uninteresting terms. Each sentence Amazon data set, σ = 0.15%. in a review is transformed into an itemset. The data set is very dense and contains 32, 140 items. The average sequence length is 8. For synthetic data sets, various kinds of parameters and distributions were used to generate different data sets. We used the following convention to name the synthetic data sets: Cx means that the data set contains x × 1, 000 sequences, T y means that the average number of items in an itemset is y, and Iz means that the data set contains z × 1, 000 distinct items.

Efficiency. The first batch of experiments focused on efficiency. As previously discussed, the upper bound computation depends on the number of sequential patterns. How does the computation time change when the number of sequential patterns increases? Using the Amazon data set, we varied the minimal support threshold and recorded for each bounding method its total computation time and the total number of sequential patterns. 240 thresholds were tried. Figure 1 shows these results. The experimental results verify the theoretical analysis. The three bounding methods scale linearly with respect to the number of sequential patterns.

We also compared the runtime of the bounding methods with respect to the candidate generation runtime in SPADE. If the bounding procedures are too slow comparing to the candidate generation time, then bounding candidates of sequential patterns would not help much in improving sequential pattern mining efficiency. Table 2 shows the results. Clearly, the computation cost for the upper bounds is negligible comparing to the candidate generation process.

Accuracy. Our second batch of experiments focused on the accuracy of the bounds. Figure 2 shows the results on two different synthetic data sets. As discussed in Section 5, the basic upper bound is much looser. For instance, on data set C500T 4I10 with a minimal frequency threshold σ = 10%, at level k = 3, the number of generated candidates by SPADE is 2, 265 but the basic bound is 167, 567, 925, 000. At the same level, the prefix-based bound is 2, 599, which is very close to the actual number of generated candidates. This observation is further confirmed by the rest of our experiments, and indicates that the prefix-based bound is viable and useful. Surprisingly, the improved prefix-based bound is 847, dramatically less than the number of candidates generated by SPADE, and much closer to the number of sequential patterns. In fact, in more than 89% of the cases in our experiments, the improved prefix-based bound is lower than the number of candidates generated by SPADE, and is closer to the actual number of sequential patterns.

To further test the effectiveness of the improved prefixbased bound, we compared it with some other representative sequential pattern mining methods. We selected two algorithms that have radically different candidate generation strategies: SPAM [START_REF] Ayres | Sequential pattern mining using bitmap representation[END_REF] and PSP [START_REF] Masseglia | The PSP approach for mining sequential patterns[END_REF]. Please note that SPAM is a depth-first search method and is reported to outperform PrefixSpan. The results are shown in Figure 3. Our improved prefix-based bound is lower than what is actually generated by the SPADE and SPAM algorithms. Two explanations are possible. First, SPAM is a depth-first algorithm and thus cannot fully use the Apriori principle in pruning unfruitful candidates. Second, the candidate generation process in SPADE produces some false positive candidates. Recall that the candidate generation method in SPADE is based on a prefix equivalence constraint. For example, let S 1 = {a}{b}{a} and S2 = {a}{b}{b} , then three candidates, {a}{b}{a}{b} , {a}{b}{b}{a} , and {a}{b}{a, b} , are generated. However, no prior check is done to see if {a, b} is actually frequent. This kind of candidates are quite often generated in many sequential pattern mining algorithms. Our improved prefix-based bound avoids such candidates in counting.

CONCLUSIONS AND FUTURE WORK

In this paper, we reported a breakthrough in the theory and foundation of sequential pattern mining. We presented, for the first time in the field of sequential pattern mining, strong combinatorial results on computing the number of possible sequences that can be generated at a given length k. Two novel techniques were developed to estimate the number of candidate sequences. The effectiveness and efficiency of our methods were well verified by an extensive empirical study on both real data and synthetic data.

Motivated by the theoretical challenge of computing the Whitney numbers for sequential patterns, we provided in this paper novel ways of bounding sequential patterns. However, our findings are not solely restricted to this unique purpose. In this section, we discuss as future work several other applications in the domains of combinatorics, data mining and machine learning that can benefit from this study.

Bridging combinatorial problems and sequence mining problems. Closed form expressions and generating functions act like identification cards for combinatorial problems. Using 12, we notice that for n = 2 (i.e., 2 items), the first few terms of the sequence of Whitney numbers are 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, . . . which are known as the "Pell numbers" (A000129 in OEIS5 ). In fact, counting the number of sequences on I = {a, b} is similar to counting the number of 132-avoiding two-stack sortable permutations [START_REF] Egge | 132-avoiding two-stack sortable permutations, fibonacci numbers, and pell numbers[END_REF], which is a special type of pattern-avoiding permutations. We believe our work may help to investigate combinatorial techniques associated with pattern-avoidance problems and applying them for constrained sequence mining [START_REF] Pei | Constraint-based sequential pattern mining: the pattern-growth methods[END_REF].

Generalized spectrum kernel. Leslie et al. [START_REF] Leslie | The spectrum kernel: A string kernel for svm protein classification[END_REF] introduced a new sequence-similarity kernel, the spectrum kernel, to deal with classification of protein sequences with supportvector machines (SVMs) and other kernel methods. The basic idea of applying SVMs on sequence data is to map sequences into feature spaces by means of kernel functions and compute the maximum-margin hyperplane to separate two classes. The k-spectrum of a sequence is the set of all length-k contiguous subsequences that it contains. The feature map is indexed by all possible length-k subsequences (i.e., k-mers) from I and its dimensionality is |I| k . Notice that this kernel works for simple sequences (i.e., ordered list of items). To generalize this kernel to sequential patterns we have to, first, be able to count the size of the feature map, and, second, develop an efficient computation method based on the "kernel trick", that is, mapping sequences into an inner product space. For the first task, it is easy to notice that for a given length k, the size of the feature map is equal to w k defined in Equations ( 1) and [START_REF]The number of simplices in a complex[END_REF]. For the second task, efficient computation could be carried by a traversal of a trie data structure like the one used by several sequential pattern mining algorithms. So far, the overall complexity of computing the kernel of 2 sequences remains an open problem. We believe that based on our work, further research on the generalization of the sequence kernels could be applied in natural language processing applications where sequential patterns may represent different sentences or grammatical groups (for instance, a nominal group could be represented in a sequence by its own itemset).

Sequence inverse mining problem and privacy issues. From the privacy point of view, data owners may not want to share their original data sets. Instead, they may consider sharing some anonymized or synthetic data sets that respect the same pattern distribution. However, one concern is how many data sets exist that respect the same pattern distribution, and how much they can be different from each other. Can an attacker "enumerate" or "characterize" such data sets sufficiently precisely? In frequent pattern mining, the performance of frequent itemset mining algorithms depends on the length distribution of the patterns. To improve the experimental procedures, data miners may want to generate data sets (i.e., benchmarks) with a given distribution on the number of patterns. This approach was successfully applied to itemset mining in [START_REF] Ramesh | Feasible itemset distributions in data mining: theory and application[END_REF][START_REF] Ramesh | Distribution-based synthetic database generation techniques for itemset mining[END_REF] and is mainly based on the Kruskal-Katona theorem. With the theoretical results in this paper, the reverse mining problem for sequential patterns can be investigated with a strong theoretical basis. For instance, suppose that I = {a, b} and we want to generate a data set that contains exactly 2 sequential patterns of length 1, 7 patterns of length-2, and 1 patterns of length 3. The upper bound feasability condition [START_REF] Ramesh | Feasible itemset distributions in data mining: theory and application[END_REF] can be answered simply using Equation [START_REF] Agrawal | Mining association rules between sets of items in large database[END_REF]. In this case, the answer is "no" because, with n = 2 and w 2 = 5, one cannot generate 7 different 2-sequences. However, the lower bound feasibility condition remains an open problem.

  be a set of k-subsets of I, where k < |I|. The set p A = {D ⊆ I : |D| = k + p, ∀ k-subset D ⊂ D → D ∈ A} is called the shade of A, where p ≥ 1. Let B be a set of k-sequences such that B ⊆ T(I). The set p B = {S ∈ T(I) : |S| = k + p, ∀S ≺ S, |S | = k → S ∈ B} is called the shade of B. In other words, p B consists of all (k + p)-sequences that can be constructed by using operators • and on the set of sequences B. For instance, let I = {a, b, c, d} and A = {{a, b}, {a, c}, {a, d}, {b, c}, {b, d}} then 1A = {{a, b, c}, {a, b, d}} and {a, c, d} ∈ 1A because {c, d} ∈ A.

Figure 1 :Figure 2 :Figure 3 :

 123 Figure 1: Time needed to compute the three upper bounds vs. the number of frequent sequences.

Table 1 : The sequence database used as the running example

 1 π(C) = {X|S ≡π S • X, S • X ∈ C}. {b} , {c} , {d} , {a}{a} , {a}{b} , {b}{a} , {a, b} , {a}{c} , {a}{d} , {c}{a} , {a, c} , {c}{b} , {b}{b} , {b}{c} , {a}{a}{a}) , {a}{a}{b} , {a}{a, b} , {a}{a}{c} , {b}{a}{b} , {c}{a}{b} , {c}{a, b} }.

	For instance,	{a}{a, b}{a}	≡π	{a}{a, b}{b} ,
	but	{a}{a, b}{a}	≡π		{a}{a, b}{b}{a}	be-
	cause they do not have the same length.	Let
	C = { {a}{a} , {a}{b} , {a}{c} , {a}{d} }.	The
	set of last itemsets of the prefix equivalence class for
	sequence {a}{a} is [ {a}{a} ]π(C) = {{a}, {b}, {c}, {d}}.
	Definition 5 (Support and frequency). The sup-
	port of a sequence S in a sequence database D is
	Support (S, D) = |{(SID, T ) ∈ D|S	T }|. The frequency
	of S in D is freq D S = Support(S,D) |D|	.
	Given a minimum frequency threshold σ, sequential pat-tern mining finds all sequences S such that freq D S ≥ σ,
	which are called the sequential patterns. We denote by
	FD,σ = {S|freq D S ≥ σ} the set of all sequential patterns, and by F k D,σ the set of sequential patterns of length k.
	Example 1 (Running Example). In this paper, we
	use the sequence database Dex in Table 1 as a running
	example. It contains 8 data sequences with I = {a, b, c, d}.
	Given a minimum frequency threshold σ = 5 8 , FD,σ = { {a} ,

  To understand the prefix-based technique, recall that a candidate sequence can be generated through the sequence extension operators. However, with the recurrence relation in Equation[START_REF] Leck | Nonexistence of a kruskal-katona type theorem for subword orders[END_REF], some of the candidate sequences that are counted are obviously infrequent.

		!
	. . +	at t + p
	No other bounds can be tighter.
	Example 4. To count the number of candidates C3 in Example 3, |F 1 D,σ | `|F 1 D,σ | ´is used to compute the number of 2 1-sequences extended with itemsets of size 2. In this case,
	{b}{a, d} , {b}{b, d} , {b}{c, d} are counted as possible
	candidates, however, {b}{d} is not frequent. In fact, the
	number of sequences of length 1 extended with itemsets of
	cardinality 2 should be constrained by the sequences of length
	2 and with 2 itemsets: {b}{a} , {b}{b} , {b}{c} , which
	are from the prefix equivalence class of sequence {b}{a} .

For instance, let I = {a, b, c, d} and A = {{a, b}, {a, c}, {a, d}, {b, c}, {b, d}}. Then, |A| = 5 = `3 2 ´+ `2 1 ´. Moreover, | 1 A| ≤ `3 3 ´+ `2 2 ´= 2, which is a tight upper bound because 1A = {{a, b, c}, {a, b, d}}.

  σ ) do

	2
	3	local ← Compute the upper bound 1A;
	4	P B ← P B + local;
	5	P B ← P B + |F k D,σ | • |F 1 D,σ |;
	6	Return PB;
		Example 5. Let P B k be the prefix-based upper bound on
	the size of k-sequences candidates. To compute P B3, we
	need to compute the bounds on the sequences generated from
	the length-2 sequential patterns with extension operators •
	and , respectively.
		The -extension case: there are 4 prefix equivalence classes
	in F 2 D,σ : 1 prefix equivalence class based on the sequences
	containing 1 itemset with cardinality 2, and 3 prefix equiva-
	lence classes based on the sequences of 2 itemsets:

  b}{a} , {a, b}{b} , {a, b}{c} , {a, b}{d} , {a, c}{a} , {a, c}{b} , {a, c}{c} , {a, c}{d} } Yet, some of the sequences should not be generated as their sub-sequences are infrequent. For instance, {b}{d} is infrequent. However, {a, b}{d} is counted as a possible candidate sequence. {a, b} should be extended only with the items in the set {a, b, c}, since only {a}{a} , {a}{b} , {a}{c} , {b}{a} , {b}{b} , and {b}{c} are frequent (notice how item d is not expanded here). Applying the same process to each element of the equivalence classes yields the following

	•.	Based
	on Procedure P B(), this equivalence class generates |A| • |F 1 D,σ | = 8 candidate sequences, which are
	{ {a,

Table 2 : Candidate generation time vs. upper bound computation time (in seconds).

 2

	Length k Cand. gen. time	Ck	P Bk	P B opt k
	1	16.4534	0	0	0
	2	117.57	0.000003 0.001984 0.001984
	3	778.726	0.000025 0.013382 0.045356
	4	24.5185	0.000006 0.002798 0.004168
	5	0.0618551	0.000009 0.001266 0.002395
		C100T4I10 data set, σ = 8%.
	Length k Cand. gen. time	Ck	P Bk	P B opt k
	1	16.1838	0	0	0
	2	77.9223	0.000005 0.000124 0.000124
	3	285.861	0.000005 0.006093 0.032533
	4	352.146	0.000006 0.240952 0.169538
	5	283.433	0.000006 0.039826 0.340521
	6	121.09	0.000006 0.035317 0.329862
	7	32.4553	0.0000010 0.019776 0.147073
	8	5.18174	0.0000010 0.007598 0.039192
	9	0.624778	0.0000012 0.003519 0.007164
	10	0.0670125	0.0000010 0.002802 0.001828

Note that: `n k ´= 0 if k > n

For a brief introduction to generating functions, please refer to http://en.wikipedia.org/wiki/Generating_function.

http://gmplib.org/

http://www.almaden.ibm.com/cs/projects/iis/hdb/ Projects/data_mining/

On-Line Encyclopedia of Integer Sequences: http://oeis. org.

We thank the anonymous reviewers for their comments and suggestions. Jian Pei's research is supported in part by an NSERC Discovery Grant and a BCFRST NRAS Endowment Research Team Program project. All opinions, findings, conclusions and recommendations in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.


INTRODUCTION

Over the preceding 40 years, the Internet has grown to a network that connects an estimated 1.8 billion users that now has reached a penetration rate of almost 25 percent globally. What was once a tool known and used by only a small number of high-profile researchers has, within one generation, become a universal commodity, like electricity, in the daily lives of hundreds of millions of users within one generation. Such an unmatched phenomenon rightly justifies the paramount importance appended to the ongoing discussion on the "future Internet." Academia and researchers around the globe now attempt to envision the definition, the design, and the construction of the future Internet and its imperatives. On the research side, for instance, among the different initiatives undertaken on the subject of "future Internet" worldwide, reference could be made to the U.S.-based Global Environment for Network Innovation (GENI) initiative [START_REF] Elliott | An Update on the GENI Project[END_REF] and the European Union Future Internet Research and Experimentation (FIRE) initiative [START_REF] Gavras | Future Internet Research and Experimentation: the FIRE Initiative[END_REF]. The United Nations World Summits on Information Society, held in 2007 and 2009, while addressing the theme of the Internet, further augmented its scope as the main component of the Information Society of the future and formally introduced cultural aspects into it as well. This flurry of interest in the future of the Internet is also a source of confusion; different and competitive requirements as well as architectural concepts are blurring our vision of it.

I give here my personal views, presented initially to the Kaleidoscope 2010 conference, and share them with the readership of IEEE Communications Magazine for further discussion and criticism. To trigger the discussion on my perspectives regarding the future Internet, I ask for the liberty to be a little more radical than usual, as I really think that it is important to be provocative, at least in some ways.

I have two positions in this article: first, that the future Internet should be polymorphic; that is, it will need to conciliate different architectural paradigms. Particularly, the future Internet (at least in a long transitory period) would have to support the evolution of the current Internet in the form of IPv6 or any other evolution of the current IP architecture along with other more revolutionary paradigms. Therefore, it is imperative to consider flexibility as the main property of the future Internet to provide smooth coexistence of evolutionary and revolutionary paradigms. My second position is that we should build the future Internet on the strong scientific foundations of networking science. The assumption of this science is that ancient networks, like roads, the postal service, and telephony, have some common principles with the latest developments of networks, like the Internet and online social networks. Networking science borrows some of its principles from well established disciplines, such as computer science, physics, social science, and economics, but it also maintains its own particular fundamental laws and principles. The multidisciplinary concept of networking science is therefore imperative to better understand and analyze the future Internet. Admittedly, networking science is under development, and ongoing research is still underway

ABSTRACT

In this article, I develop two major propositions. First, the future Internet should be polymorphic, and it should conciliate different architectural networking paradigms. The second proposition is that the future Internet should necessarily build on a strong theoretical basis from a networking science that is in the course of development. Particularly, I describe how virtualization makes possible a polymorphic future Internet and provides for easy deployment of new cooperation schemes. Then I attempt to expound on the aspects of security and scalability of the future Internet. This analysis also hopes to account for some justification as to the need for a clean-slate approach to fundamentally tackle the shortcomings of the current Internet and why a polymorphic future Internet is needed to for the coexistence of evolutionary and revolutionary schemes. Admittedly, the future Internet has to be built on strong foundations of networking science. A global theory of cooperation over networks is therefore most needed to foresee the important issues in the design and deployment of the future Internet. Methodologies for experimenting and validating large-scale mechanisms by reproducible large-scale experiments are, moreover, among the expected outcomes of the emerging networking science, which I also discuss in this article.

ITU KALEIDOSCOPE CONFERENCE

Kavé Salamatian, Université de Savoie

Toward a Polymorphic Future Internet: A Networking Science Approach

to define all its dimensions. Yet there is an explicit consensus in academia on some basic concepts. Among the founding concepts of this new discipline, I wish to expound on the principle of cooperation as a reading lens for understanding the main issues of the future Internet.

COOPERATION: THE VERY ESSENCE OF NETWORKING

A network can be defined as a set of nodes that are cooperating with each other to distribute (exchange) The classical view tends to consider the role of a network element in processing packets only. By considering that the network element can decide which type of cooperation it will implement, networking science broadens its scope considerably. The decision is based not only on network objectives defined by the network operator or the service provider, but also on selfish goals of the person or entity that owns the node. 1Selfishness might drive a node to go into standby mode to reduce battery consumption or drop packets that are not of interest. The observation that nodes might be selfish is a major change. It is motivated by several application scenarios, like ad hoc wireless networks, inter-AS routing, and peer-to-peer networks. Selfishness means a node cannot assume that its neighbors will fully cooperate, and it needs to react accordingly. Therefore, the node might have to implement a palette of different profiles for different contexts and appear polymorphic. Integrating selfishness is then a central motivation for proposing that the future Internet architecture be polymorphic.

As economics purports to address the production, distribution, and consumption of services and goods, networking science addresses the production, distribution, and consumption of "information." Understanding, formalizing, and shaping cooperation for the distribution of infor-mation are the major goals of network science. However, economics is a science that applies to resources that are scarce and have alternative uses. What differentiates digital information from other goods is that information is universal and infinitely reusable; that is, once produced, information supply becomes infinite, and there is almost no cost in reproducing it. Moreover, information is ambiguous (discriminating wrong from correct information is hard), whereas other goods and services are unambiguous. Therefore, a new cooperation theory, different from classical economical theory, must be developed to integrate network cooperation and the economical value of information.

TO CLEAN THE SLATE OR NOT? IS IT REALLY AN ISSUE?

The Internet was always designed, developed, and deployed simultaneously. More precisely, whenever a problem arose, a solution was proposed and analyzed, following a technical consensus at the Internet Engineering Task Force (IETF), resulting in a Request for Comments (RFC) that solved the issue or implemented a new feature. The IETF consensus guaranteed that the proposed evolution of the Internet was backward-compatible and complied with the sacrosanct axiom of "no harm to what works." This process is one of the main explanations for the huge success and relative stability of the current Internet.

The clean-slate approach comes from the belief that it is impossible to resolve the challenges facing todays Internet without rethinking the fundamental assumptions and design decisions underlying its current architecture. The incremental approach changes the Internet architecture by backwardcompatible patches; the clean-slate approach advocates out-of-the-box thinking with an architectural redesign, based on ameliorated concepts and abstractions to answer the current challenges.

Deciding between a clean slate and an evolutionary approach has become a major subject of controversy in the Internet community. Clean slate critics advocate that it is not wise to destruct something that works. Clean slate adepts state that the current Internet architecture constrains future evolution and hinders the deployment of radical solutions that attack existing problems (to be described later).

Indeed, the future Internet (at least in a long transitory period) should have to support the evolution of the current Internet. However, the future architecture should not hinder the design and deployment of other more revolutionary paradigms. This means that the key property of the future Internet architecture is having enough flexibility to enable the coexistence of the evolution of the current Internet (via incremental patches) with clean-slate revolutionary approaches. We should design the future Internet so that the question of cleaning the slate becomes irrelevant. I describe later why I believe that such flexibility is achievable with current virtualization technologies.

Nonetheless, imagining a new architecture is

FUTURE INTERNET MOTIVATIONS AND RATIONALES

There is broad consensus that the current Internet has some shortcomings that make its evolution and/or revolution inevitable. I give some of the main rationale along three directions here: flexibility, security, and scalability. This critical analysis sheds some light on the directions to go to design the future Internet.

FLEXIBILITY OR THE FUTURE INTERNET CONTORTIONIST

I have already presented some arguments as to why the future Internet has to be flexible enough to accommodate different cooperation models simultaneously. Another rationale relates to new application deployment. The current Internet does not provide architectural hooks to deploy services beyond the socket interface; developers have no access to routing and addressing. For this reason, during the past decade, developers have frequently raised routing and addressing into the application level, where they can access it. Peer-to-peer and overlay networks are examples of this approach, and implement a complete cooperation scheme in the application level (more precisely, above the socket interface). While this approach has been very successful, it is not optimal, as the packets still have to go through the underlying narrow hourglass of IP that acts as a bottleneck. A network where one could implement and deploy new network protocols or cooperation schemes without disturbing other running protocols would solve the application deployment issue and moreover provide an efficient way for innovative service deployment.

The network research community has pursued the quest for a flexible experimentation platform for future Internet research. This has resulted in the development of Planetlab [START_REF] Paterson | The Design Principles of PlanetLab[END_REF]; its European counterpart, OneLab [START_REF] De La Oliva | A Multihoming Architecture for OneLab[END_REF]; and GENI [START_REF] Elliott | An Update on the GENI Project[END_REF]. The flexibility in these experimental platforms was attained0, thanks to the wide generalization of vir-tualization approaches [START_REF] Anderson | Overcoming the Internet Impasse through Virtualization[END_REF]. Virtualization ensures full isolation (fault, software, and performance isolation) between virtual machines. Because it enables the parallel execution of different networking systems (routing, addressing, etc.), it opens the way for a polymorphic future Internet.

Virtualization techniques encapsulate a full virtual machine into a single file that can be easily migrated and executed over any virtualized hardware. The encapsulation property opens the perspective of easy deployment of services just by distributing the encapsulated virtual machine. Thus, it is possible to implement the service over a large infrastructure of virtualized servers/ routers. Last but not least, virtualization ensures interposition, because all activities go through a monitoring layer. Nowadays, commodity hardwares have enough processing power to build virtual routers over clusters of multicore routers [START_REF] Egi | Towards High Performance Virtual Routers on Commodity Hardware[END_REF]. This opens the perspective of building realistic routers, implementing the polymorphic future Internet.

SECURITY: THE ACHILLES'S HEEL OF THE CURRENT INTERNET

One of the major rationales for the development of a future Internet is security. Indeed, the current Internet is plagued with spam, phishing, denial of service attacks, exploiting security breaches, and so on. However, only a small proportion of security-related problems could be traced back to the Internet architecture. Network security can be defined along three directions: communication security (ensuring that communication remains secret), cooperation security (ensuring that cooperation in networks is possible and secure), and, finally, application security (ensuring that an application is doing what it is supposed to do). Future Internet architecture should support each of the above components. Security was not considered to be an essential component of the current Internet architecture. While support for communication security through IPSec exists (as an optional element in IPv4 and a mandatory one in IPv6), no support for the two other aspects of security exists. This has resulted in the current security status, where several external services, like virtual private networks (VPNs), firewalls, proxies, and Secure Sockets Layer (SSL), compensate for the lack of support built into the architecture.

The current status of Internet security has motivated extreme positions. On one hand, some suggest the integration of all security primitives inside the architecture, so that applications can fully rely on architectural security services. However, this could degrade the performance of network elements significantly. An opposite viewpoint advocates a "keep it simple, stupid" (KISS) approach, where the architecture should remain simple by focusing only on packet forwarding, and security mechanisms should remain on the network edges, like firewalls and IPSec mechanisms. This viewpoint is also problematic, as one cannot control the network completely without acting on the core of the architecture. In between these two extremes, the future Internet will have to determine the least common denominator of security support; in other terms, what should be mandatorily integrated into the archi- tecture and what could be considered as an applicative service that will cooperate with other components through the architecture.

The experience of IPSec shows that communication security can be supported satisfactorily through solutions that do not need to go deep into the core of the architecture. By looking at security through the cooperation lens, the future Internet architecture needs to integrate mechanisms to secure cooperation. This means that at least three basic security mechanisms have to be integrated to the future Internet architecture: an isolation mechanism shielding components running in the same execution environment strictly and at the deepest level, an authentication mechanism authenticating the source of a running code, and a monitoring mechanism that will evaluate the cooperation behavior of executing components and compare it with normal or expected behaviors. None of these mechanisms exists in the current Internet. However, virtualization provides mechanisms to guarantee fault, performance, and execution isolation. It also guarantees interposition. This means that a virtualized and polymorphic architecture for the future Internet will provide two out of the three needed basic security mechanisms. The scope of the authentication service is still a research topic, as it is not yet clear if a global authentication and/or identity mechanism is mandatory, or if only a local and trust-based scheme will be enough to cover the large spectrum of scenarios.

Permanent monitoring is a trade-off between performance and security; the more security we need, the more exhaustive the monitoring should be. We also have a trade-off between flexibility (in terms of the range of acceptable behaviors) and security; detecting abnormal behaviors entails reducing the range of acceptable behaviors to be able to differentiate them from abnormal ones.

It is worth recalling that security is a negative concept: you do not appreciate it when you have it; you only realize its significant importance when you have lost it. This means that rather than speaking about providing security, one should talk about reducing vulnerabilities. Almost 30 years of experience in Internet security has taught us that it is too costly and even impossible to remove all risks. The consequence of this is that we have to increase the resilience of the future Internet architecture to ensure survivability and to reduce the impact of security risks. In other terms, security risks should be assumed as a plausible operational hypothesis in the design of networked systems, and architectural solutions should be provided to detect and to contain them. This is a radically different position from the current approaches, where the emphasis is put on authentication of users through passwords/biometrics and assuming that authenticated users are entitled to do whatever they do. In the collaborative approach, we have to assume that users (even authenticated) can misbehave, and we should be able to detect and contain them. This is another shift in the security paradigm.

A noteworthy action that is supporting the paradigm change mentioned above is the ITU-Cybex action, aiming to develop a standard cybersecurity information exchange framework [START_REF] Rutkowski | CYBEX: the Cybersecurity Information Exchange Framework (x.1500)[END_REF]. ITU-Cybex is based on the observation that security risks are now internationally endemic. In this context, information about security events should be shared rather than being considered as private issues.

SCALABILITY, OR A DELUSION OF GRANDEUR

Scalability is another cardinal issue for the future Internet. The past decade has seen almost a doubling of Internet traffic per year. The size of routing tables, which are the main indicator of the complexity of the routing operation, has seen yearly growth of 19.4 percent from 2002 to 2008. 2Before dealing with scalability, we have to answer the question of why we need an address and how to answer this need. Initially, IP addresses were designed to identify resources on the network and locate them. However, this mixing of roles leads to some contradictions. On one hand, using an IP address as an identifier means that a unique IP address should be assigned to each resource in the network. On the other hand, using the IP address as a locator means that the address should change when the location of the resource changes. The locator address should satisfy some topological constraints (the locator address of nearby resources should be close), whereas identifiers should meet some semantic constraints (the addresses of all resources of the same operator should be close). The contradiction between the requirement of these two roles has resulted in the fragmentation of the IP address space and the scalability problem. While IPv6 solved the issue of identification address space exhaustion, it does not resolve the address space fragmentation that is the source of the scalability problem.

During the past two decades, several propositions have reduced address space fragmentation. In 1989, BGP introduced AS-level IP address aggregation; in 1993 classless Internet domain routing (CIDR) was used to regain the address waste resulting from past class-based allocations. However, address allocations had to remain compatible with previously allocated addresses because of the identification role of IP addresses. The Routing Research Group (RRG) of the Internet Research Task Force (IRTF) is currently investigating ways to improve the scalability of the current Internet in the current IP architectural framework. I do not give an exhaustive view of the proposed schemes. However, the main rationale of almost all of these proposals [START_REF] Farinacci | Locator/ ID Separation Protocol (LISP)[END_REF][START_REF] Atkinson | Evolving the Internet Architecture Through Naming[END_REF] is to decouple the identifier and locator roles of the address. For example, Locator/Identifier Separation Protocol (LISP) [START_REF] Farinacci | Locator/ ID Separation Protocol (LISP)[END_REF] proposes a mapping system between the identifier and locator through an Alternative Topology (ALT) service. This mapping enables one to find the location of a given identifier, similar to what a Domain Name Service (DNS) server does. Identifier-Locator Network Protocol (ILNP) [START_REF] Atkinson | Evolving the Internet Architecture Through Naming[END_REF] has a similar mapping, but is done through DNSSEC rather than a specific service.

A "clean slate" approach to scalability does not enforce compatibility with the current IP architecture. New network scenarios, like delaytolerant networks, showed that routing might not be possible in some scenarios. It was even shown that in order to optimize the throughput, network coding, which is not based on routing, should be used. Fundamentally, addressing is a topological embedding adapted to a particular cooperation need; that is, it is a function that accepts an identifier and returns the position of the needed information to a topological space. It was shown that when the embedding is compact (i.e., when two nearby items are mapped by the addressing embedding into close addresses), addressing implies routing and vice versa. In other words, if one knows the identifier of what s/he wants, s/he can derive it from the path directly to reach it. This property means that scalable routing is possible and even trivial when compact embedding exists. IP (v4 or v6) addressing is not compact, as close nodes are not necessarily close in the IP address space. Nonetheless, compact embedding does exist. For example, the Content Addressable Network [START_REF] Ratnasamy | A Scalable Content-Addressable Network[END_REF] (with the assumption of no node withdrawal) defines compact embedding. The question of knowing whether we can embed the particular addressing need of a specific cooperation scheme into compact embedding is one of the major questions of networking science. Peer-to-peer (P2P) and overlay networks have demonstrated that by lifting the IP addressing backward compatibility constraints, scalability can be achieved, and address fragmentation avoided. This advocates a clean-slate approach for the future Internet to enable deployment of new addressing/ routing schemes. Indeed, one can note that IP addresses are still needed, even on P2P and overlay networks. However, this is more a kind of link layer connectivity issue than a fundamental need of IP addressing.

A polymorphic future Internet should provide for the coexistence of traditional IP addresses with a more revolutionary addressing scheme and enable gradual introduction of new routing schemes. IPv6 showed the difficulty of introducing radical changes into the network. Nearly a decade after most of the IPv6 standard was completed, the vast majority of software and hardware still uses IPv4.

CONCLUSION

In this article, I define two main positions: the future Internet should be polymorphic, and it should be built on a strong networking science foundation.

I call for the development of a networking science that will provide the foundations for the future Internet. Networking science will be built mainly around the concept of cooperation. This cooperation theory is different from classical economics because it integrates network cooperation and the economic value of information. Another potentially high-impact area of networking science pertains to experimental validation. The networking research community still lacks largely agreed-on methodologies describing how to do reproducible large-scale experiments and how to validate large-scale mechanisms before deploying them in the wild. Answering these two needs is of the utmost importance for the future Internet.

I also recommended a polymorphic architecture for the future Internet. The rationale behind this proposal is that a polymorphic view reduces the importance of the "clean slate vs. evolutionary" controversy greatly. In particular, a polymor-phic architecture will make the gradual deployment of noncompatible clean slate solutions possible along with IP-based evolutionary developments. Virtualization techniques can provide the flexible technology needed to build such a polymorphic future Internet. Moreover, these techniques will ensure isolation and interposition, two properties that are needed in a future architecture. The security paradigm would have to shift from schemes based only on encryption/authentication to monitoring schemes that permanently observe the cooperation behavior of network elements. The last topic developed in the article is scalability. My position is to promote infinitely scalable addressing and routing schemes by using suitable embeddings. This is an argument in favor of a clean-slate approach. Thus, the future Internet will support different addressing schemes suitable for different applications.

In summary, we should aim at designing a polymorphic Internet architecture that will let us benefit from innovations without harming the existing and successful current Internet.

BIOGRAPHIES

KAVÉ SALAMATIAN (kave.salamatian@univ-savoie.fr) is a full professor in computer science at the University of Savoie. His main areas of researches are Internet measurement and modeling, and networking information theory. He was previously a reader at Lancaster University, United Kingdom, and associate professor at University Pierre et Marie Curie. He graduated in 1998 from Paris SUD-Orsay University where he worked on joint source channel coding applied to multimedia transmission over Internet for his Ph.D. In a former life, he graduated with an M.B.A., and worked on the market floor as a risk analyst and enjoyed being an urban traffic modeler for some years. He is working these days on figuring out if networking is a science or just a hobby; and, if it is a science, what are its fundamentals.

The owner of a computer in a peer-to-peer network or the owner of an autonomous system (AS) border gateway router.

See BGP table size evolution at http://bgp.potaroo.net/cidr/.

ACKNOWLEDGMENTS

At the end, I would like to thank Serge Fdida for interesting discussions about the architecture of the future Internet, Dr. Mostafa Hashem Sherif for helpful comments, and the anonymous reviewers for their valuable advice.