Alessandra Colombelli

Jackie Krafft

Francesco Quatraro
email: francesco.quatraro@unice.fr

Cristiano Antonelli

Giulio Bottazzi

Alex Coad

Lionel Nesta

Marco Vivarelli

Pier Paolo

High Growth Firms and Technological Knowledge: Do gazelles follow exploration or exploitation strategies? 1

Keywords: Gazelles; Recombinant Knowledge, Schumpeterian innovation patterns JEL Classification Codes: L20, L10, 032

This paper analyses the contribution of high-growth firms to the process of knowledge creation. We articulate a demand-pull innovation framework in which knowledge creation is driven by sales growth, and knowledge stems from creative recombination. Building on the literature on high growth firms and economic growth, we investigate whether 'gazelles' follow patterns of knowledge creation dominated by exploration or exploitation strategies. We construct indicators for the structure of knowledge and identify firms' innovation strategies. The empirical results show that increasing growth rates are associated with exploration, supporting the idea that high growth firms are key actors in the creation of new technological knowledge, and showing also that firms that achieve higher than average growth focus on exploration based on familiar technology. This suggests that exploration is less random than has been suggested. Our main result is that high growth firms, especially gazelles, predominantly adopt exploration strategies that have the characteristics of organized search more often observed among firms following an exploitation strategy.

Introduction

The process of firm growth has long fascinated economists. Most empirical work draws on the seminal paper by [START_REF] Gibrat | Les inégalités économiques[END_REF], who proposed that firm growth is predominantly a random process (see Lotti, Santarelli andVivarelli, 2003, 2009).

In recent years, analysis of firm growth has gained momentum, with particular attention on the distributional properties of firm growth rates, their persistence over time, and their determinants [START_REF] Bottazzi | Explaining the Distribution of Firms Growth Rates[END_REF][START_REF] Coad | A Closer Look at Serial Growth Rate Correlation[END_REF]Coad andHölzl, 2011, Parker et al., 2010;[START_REF] Acs | Employment effect of business dynamics: mice, gazelles and elephants[END_REF][START_REF] Lee | A theory of firm growth: learning capability, knowledge threshold, and patterns of growth[END_REF].

Much of the focus of empirical work on the determinants of firm growth has shifted to analysis of firms showing growth rates that are much higher than the average. [START_REF] Henrekson | Gazelles as Job Creators -A Survey and Interpretation of the Evidence[END_REF] point out that this strand in the literature derives from [START_REF] Birch | The job generation process[END_REF][START_REF] Birch | Who creates jobs?[END_REF] contributions, which describe high growth firms as 'gazelles'. Birch maintains that these gazelles are the main source of job creation in the economic system. Understanding the conditions that make firms gazelles and the channels through which they contribute to the dynamics of aggregate economic growth could help policymakers to devise targeted supporting policy measures [START_REF] Nightingale | Gazelles and MUPPETS: Ideological and Methodological Biases in Entrepreneurship Research[END_REF].

The analysis of the relationship between innovation and faster rates of growth is a more recent exercise, conducted mostly within empirical settings and based on quantile regressions (Coad and[START_REF] Coad | Innovation and firm growth in high tech sectors: a quantile regression approach[END_REF]2010;Hoelzl, 2009). This literature uses firm growth as a dependent variable, and attempts to understand what are the main factors affecting the outperforming behaviour of gazelles. When other dependent variables (such as R&D, see [START_REF] Coad | Firm growth and R&D expenditure[END_REF] are taken into account, estimation of quantile regressions assigns firms to different classes according to rate of growth of R&D expenditure rather than firm growth. Therefore, the contribution of gazelles to innovation dynamics is still unclear.

In this paper we try to fill this gap by investigating the differential contribution of high-growth firms to the creation of technological knowledge. The literature on gazelles indeed emphasizes that their economic contribution is due mostly to the process of creative destruction that they engender, so that the net job creation ascribed to high growth firms stems from an ongoing dynamic process in which new opportunities emerge and likely replace obsolete activities [START_REF] Hölzl | Is the R&D behaviour of fast-growing SMEs different? Evidence from CIS III data for 16 countries[END_REF][START_REF] Hölzl | The Economics of Entrepreneurship Policy: Introduction to the Special Issue[END_REF][START_REF] Henrekson | Gazelles as Job Creators -A Survey and Interpretation of the Evidence[END_REF][START_REF] Daunfeldt | When is Gibrats law a law?[END_REF].

We are especially interested in the extent to which gazelles can be thought as featuring the population of firms in sectors dominated by Schumpeterian Mark I or Mark II patterns of innovation (Malerba andOrsenigo, 1995, 1997). Whether gazelles can be considered hybrids in relation to their innovation patterns is one of the main research questions investigated here. We combine a demandpull innovation background with an approach to technological knowledge that emphasizes its collective and recombinant nature, and allows the identification of properties that characterize innovation strategies as random screening or organized search [START_REF] Krafft | Evolution of the knowledge base in knowledge intensive sectors[END_REF]. While a similar approach has been used to analyse productivity performance at various levels [START_REF] Nesta | Knowledge and productivity in the world's largest manufacturing corporations[END_REF][START_REF] Quatraro | Knowledge Coherence, Variety and Productivity Growth: Manufacturing Evidence from Italian Regions[END_REF][START_REF] Antonelli | Recombinant Knowledge and Growth: The Case of ICTs[END_REF]Quatraro, 2010, Colombelli, Krafft and[START_REF] Colombelli | Properties of knowledge base and firm survival: Evidence from a sample of French manufacturing firms[END_REF], there are no studies to date that use it to investigate high-growth firms.

Our results show that gazelles cannot be strictly categorized as belonging to one mode or the other, but would appear to represent a mix, adopting a combination of exploration and organized search strategies.

The rest of the paper is organized as follows. Section 2 presents the theoretical underpinnings of the analysis, and outlines the working hypotheses. Section 3 describes the data and the methodology, with particular emphasis on the implementation of knowledge related indicators. Section 4 presents and discusses the empirical results and Section 5 concludes.

High-growth firms and technological knowledge: a Schumpeterian story?

There is a large literature on innovation. It consists of two main strands, one emphasizing the importance of the accumulation of skills and scientific knowledge as the drivers of innovation, the other emphasizing the role of economic mechanisms on the demand side. The first strand is usually described as technology-push and the second as demand-pull.

The pioneer of the demand-pull approach in its modern form was Jacob Schmookler. 2 He observed how time series on technology creation, proxied by patent applications, tended to follow time series on output [START_REF] Schmookler | The level of inventive activity[END_REF][START_REF] Schmookler | Economic Sources of Inventive Activity[END_REF]. He interpreted this as that "more money will be available for invention when the industry's sales are high than when they are low. Increased sales imply that both the producing firms and their employees will be in a better position than before to bear the expenses of invention" (Schmookler, 1962: p.17). In this framework, the ability to finance knowledge creation activities plays a central role [START_REF] Schmookler | Invention and Economic Growth[END_REF]. Empirical analyses of the effects of firm performance on knowledge creation have been confined to the level of innovation, without any attempt to qualify the patterns of innovation [START_REF] Griliches | Inventing and maximizing[END_REF][START_REF] Scherer | Demand-Pull and Technological Invention: Schmookler Revisted[END_REF]Crespi and[START_REF] Crespi | Demand and Innovation in European Industries[END_REF][START_REF] Nesta | Knowledge and productivity in the world's largest manufacturing corporations[END_REF].

In this context, the identification of two distinct Schumpeterian patterns of innovation by Malerba andOrsenigo (1995, 1997) is useful. They describe Schumpeter Mark I as characterized by 'creative destruction', ease of entry and the emergence of new firms based on business opportunities, which challenge incumbents and continuously disrupt current modes of production, organization and distribution. Schumpeter Mark II is characterized by 'creative accumulation', the relevance of industrial R&D laboratories and the key role of large firms. The authors also apply the labels of 'widening' and 'deepening' to these patterns. The former description applies to an innovative base that is continuously growing, the latter describes accumulation strategies based on existing technological premises. In this direction, the positive relationship between firms' growth and innovation may either be channeled by Schumpeter Mark I or Schumpeter Mark II dynamics.

The grafting of the recombinant knowledge approach onto the investigation of the relationship between high-growth firms and patterns of innovation may be far reaching. While traditional approaches to technological knowledge tend to represent it as a homogeneous stock [START_REF] Griliches | Issues in assessing the contribution of research and development to productivity growth[END_REF][START_REF] Mansfield | Basic research and productivity increase in manufacturing[END_REF], according to recombinant knowledge approach, the creation of new knowledge can be represented as a search process across a set of alternative components that can be combined with one another. Here the cognitive mechanisms underlying the search process are important for exploring the knowledge space to identify which pieces of knowledge might be combined [START_REF] Weitzmann | Recombinant growth[END_REF][START_REF] Kauffman | Origins of order: Self-Organization and selection in evolution[END_REF]. The set of potentially combinable pieces is a subset of the whole knowledge space. Search is supposed to be local rather than global; influenced by cognitive, social and technological factors. The ability to engage in a search process in more distant spaces is likely to generate breakthroughs based on combinations of new components [START_REF] Nightingale | A cognitive model of innovation[END_REF][START_REF] Fleming | Recombinant Uncertainty in Technological Search[END_REF].

If knowledge stems from the combination of different technologies, a firm's knowledge base can be represented as a web of connected elements. The nodes of this network represent the elements of the knowledge space that could be combined, while the links represent their actual combination. The frequency with which two technologies are combined provides useful information for how we characterize the internal structure of the knowledge base. Such characterization takes account of the average degree of complementarity of the technologies comprising the knowledge bases, and also the variety of the observed pairs of technologies, which allows us to define three properties of knowledge structure:

 Knowledge Variety is related to technological differentiation within the knowledge base, in particular with respect to the possible different combinations of pieces of knowledge in the sector, from the creation of radically new types of knowledge to more incremental recombinations of already existing types of knowledge.

 Knowledge Coherence can be defined as the extent to which the pieces of knowledge that agents within the sector combine to create new knowledge are complementary.

 Knowledge Similarity refers to the extent to which the pieces of knowledge used in the sector are close in the technology space.

The dynamics of technological knowledge, therefore, can be understood as the patterns of change to its internal structure, that is, the patterns of recombination across the elements in the knowledge space. This captures the cumulative character of knowledge creation and the key role played by the properties describing knowledge structure, and also the possible link to the relative stage of development in the technological trajectory [START_REF] Dosi | Technological paradigms and technological trajectories[END_REF][START_REF] Saviotti | Considerations about the production and utilization of knowledge[END_REF][START_REF] Saviotti | On the dynamics of generation and utilisation of knowledge: The local character of knowledge[END_REF][START_REF] Krafft | Evolution of the knowledge base in knowledge intensive sectors[END_REF]. This approach allows a better distinction between innovation strategies, that is, between exploration and exploitation [START_REF] March | Exploration and exploitation in organizational learning[END_REF]. The view of knowledge as an outcome of a recombination activity allows the idea of two nested dimensions, defined according to the degree to which agents decide to rely on exploration or exploitation, or a combination of the two, which has suggested concepts such as 'search depth' and 'search scope' [START_REF] Katila | Something old, something new: a Longitudinal Study of Search Behaviour and New Product Introduction[END_REF]. Search depth refers to degree to which agents draw upon prior knowledge, search scope refers to the degree to which agents rely on the exploration of new areas in the knowledge space.

Combining the demand-pull framework with the recombinant knowledge approach and analysis of Schumpeterian patterns of gazelles' innovation activities, allow us to refine our main working hypotheses as follows.

Sales growth is a key factor in high levels of innovations. For this reason, gazelles are expected to be characterized by demand-driven dynamics of knowledge creation based on search behaviours aimed at widening or deepening the firm's technological competences. Our main research question is whether the important contribution of gazelles to economic growth can be ascribed to search behaviours typical of a Schumpeter Mark I pattern of innovation activities or a Schumpeter Mark II pattern. In the first pattern, the positive impact of high-growth firms is based on their capacity to undertake search behaviours directed towards the exploration of untried technological fields, which broadens the existing knowledge base initially in a rather random way. Extending the knowledge base means extending beyond the boundaries of what the firm already knows. Exploration tends to be a key part of the destructive creativity of gazelles that follow a widening pattern. The search behaviour of high-growth firms can be expected to depart to some extent from established trajectories to discover new fields in the technology landscape in order to increase search scope.

According to this pattern, search behaviours will be more focused on a range of 'successful' technological fields, leading to a deepening of the existing knowledge base. Exploitation is intended to combine knowledge in a more organized way, and is likely to apply to high growth firms.

Figure 1 maps the paths followed by gazelles, distinguishing between: i) strategies (exploration versus exploitation); and ii) the way they implement these strategies (random search versus organized search). The result is a two-by-two conceptual matrix, with a horizontal axis (strategies) and a vertical axis (type of search). (1 st and 3 rd quarter). In Mark 1, firms are depicted as developing different characteristics of product innovation, in a situation of high uncertainty, which implies a predominance of trial and error system of development; in Mark 2, firms draw on their experience, which reduces uncertainty, in selecting the ways to innovate successfully. After a period of exploration where firms try several possible combinations to produce innovation, there is a period of more stabilized choice around a smaller set of possibilities.

>>> INSERT FIGURE 1 ABOUT HERE <<<

Gazelles do not necessarily follow pure models of innovation patterns. Due to their multifaceted characteristics in terms of size, innovation behaviour, etc., it is necessary to consider them in a dynamic framework where they may evolve from one model to another (e.g. from Mark 1 to Mark 2), or extend the characteristics of one model to overlap with characteristics assumed to belong to the other model. For instance, gazelles may be small firms, highly oriented towards a model of innovation by exploration, but they may pursue this strategy in a more organized way than predicted by Mark 1. Alternatively, large gazelle firms, which engage in an exploitation strategy (i.e. Mark 2 characteristics), may adopt some random screening activities that combine pieces of knowledge that are usually exclusively attributed to Mark 1.

There is a growing literature on the relation between diversity in the knowledge base and the performance of firms (see also [START_REF] Ostergaard | Does a different view create something new? The effect of employee diversity on innovation[END_REF], for an investigation of the relationship between diversity in intangible assets and innovation), but the present paper is the first attempt to study the link between high growth firms and knowledge base heterogeneity, based on the properties of variety, coherence and similarity of the knowledge base.

In the next section we describe the data and the methodology used to provide an operational definition of the concept of recombinant knowledge and the properties of knowledge structure, and to characterize the search behaviour of high-growth firms.

Data, Variables and Methodology

Dataset

The dataset is an unbalanced panel of publicly traded firms in UK, Germany, France, Sweden, Italy and the Netherlands. Our main source of market and accounting data is Thomson Datastream. To obtain additional relevant variables, we include in the dataset information collected from AMADEUS by Bureau Van Dijk. The period of observation for all the countries examined is 1988 to 2005. We also use data from the OECD REGPAT database, which provides regional information on the addresses of patent applicants and inventors as well as on technological classes cited in patents granted by the European Patent Office (EPO) and the World Intellectual Property Organization (WIPO), under the Patent Co-operation Treaty (PCT), from 1978 to 2006.

In order to match the firm level data with data on patents, we draw on the work of [START_REF] Thoma | Harmonizing and combining large datasets -an application to firm-level patent and accounting data[END_REF], which develops a method for harmonization and combination of large-scale patent and trademark datasets with other sources of data, through standardization of applicant and inventor names.

We pooled the dataset by adding industry level information from the OECD STAN database. STAN is based on ISIC revision 3 sectoral classifications; Thomson Datastream uses the four digit level ICB industry classification ( Appendix B provides the sectoral concordance table used to link the two classifications).

Our final dataset is an unbalanced panel of 335 active companies listed on the main European financial market that submitted at least one patent application to the EPO in the period analysed. 3Table 1 reports the sample distribution by macro-sector, country and size classes. High and mediumhigh technology firms account for around 30% and 37% of observations, respectively. Medium low and low technology firms account for 3% and 10% respective, and knowledge intensive firms represent some 7% of observations. The other economic groups each account for less than 10% of the observations.

>>>INSERT TABLE 1 ABOUT HERE<<<

As expected, most of the sampled firms (80.9%) are large firms, that is, firms with more than 250 employees; 13.43% of the sample is medium sized firms. The country distribution is more diverse, although 34% of the sampled firms are German and 25% are French. Sweden and the UK follow with 13% and 14% of sampled firms respectively.

The Variables

Since we are interested in the dynamic aspects of the relationship between sales and knowledge creation, we use the growth rates of the relevant variables. At the general level, growth rates can be defined as follows:

) ln( ) ln( 1 , , ,    t i t i t i X X Growth (1)
where X is measured as sales, knowledge capital stock, knowledge coherence, cognitive distance, knowledge variety, related knowledge variety and unrelated knowledge variety. All these variables are explained below and in Appendix A, and are calculated for firm i at time t. In line with previous empirical work [START_REF] Bottazzi | Measuring Industry Relatedness and Corporate Coherence[END_REF][START_REF] Coad | Appropriate business strategy for leaders and laggards[END_REF], the growth rate distributions are normalized around zero in each year by removing the means as follows:

∑ (2)
where N is the total number of firms in the sample. This procedure effectively removes average time trends common to all the firms caused by factors such as inflation and business cycles.

Knowledge Indicators

To define our knowledge related variables, we start with the firm's knowledge stock. This is computed by applying the permanent inventory method to patent applications. We calculate it as the cumulated stock of patent applications using a rate of obsolescence of 15% per annum:

1 , , , ) 1 (      t i t i t i E h E  , where t i h , 
is the flow of patent applications and δ is the rate of obsolescence. Implementation of knowledge characteristics proxying for variety, coherence and similarity, rests on the recombinant knowledge approach. In order to provide an operational translation of these variables we need to identify a proxy for the bits of knowledge, and a proxy for their structural elements. We could use scientific publications as a proxy for knowledge, and use keywords or scientific classification (e.g. the JEL code for economists) to proxy for knowledge structure. However, we chose to use patents as a proxy for knowledge, and use the technological classes to which the patents are assigned as structural elements, that is, the nodes in the network representation of recombinant knowledge. 4 Each technological class j is linked to another class m if the same patent is assigned to both classes. The higher the number of patents assigned to both classes j and m, the stronger is the link. Since the technological classes attributed to patents are reported in the patent documents, we refer to the link between j and m as their co-occurrence within the same patent document. 5 This allows us to calculate the following three characteristics of the firm's knowledge bases (see appendix A for methodological details): Use of these variables represents progress in the operational translation of knowledge creation processes. They deal explicitly with the heterogeneity of knowledge and allow a better appreciation of the collective dimension of knowledge dynamics. Knowledge is viewed as the outcome of combinatorial activity in which intentional and unintentional exchange among innovating agents provides access to external knowledge inputs [START_REF] Fleming | Collaborative brokerage, generative creativity and creative success[END_REF]. The network dynamics of innovating agents constitute a foundation for the emergence of new technological knowledge, which in turn is represented as organic in structure, characterized by elementary units and the connections amongst them. The use of these variables implies a mapping between technology as an activity and technology as an artefact [START_REF] Arthur | The Nature of Technology. What It Is and How It Evolves[END_REF]Lane et al., 2009;Krafft and Quatraro, 2011). Co-occurrence matrices are similar to design structure matrices (DSM) [START_REF] Baldwin | Design Rules, Volume I, The power of Modularity[END_REF][START_REF] Murmann | Towards a systematic framework for research on dominant designs, technological innovations, and industrial change[END_REF][START_REF] Baldwin | Where do transactions come from? Modularity, transactions, and the boundaries of firms[END_REF], in that they can be considered adjacency matrices in which our interest is in both the link between the elements and the frequency of these links.

In other words, these measures capture the design complexity of the knowledge structure, and allow observation of firm behaviour in relation to innovation, and its evolution with the changing architecture of the knowledge structure [START_REF] Henderson | Architectural innovation: The reconfiguration of existing product technologies and the failure of established firms[END_REF][START_REF] Murmann | Towards a systematic framework for research on dominant designs, technological innovations, and industrial change[END_REF].

In this perspective, knowledge variety is likely to increase when new combinations of knowledge are introduced into the system. However, the balance between related and unrelated variety should be such that related variety dominates during the exploitation phase and unrelated variety dominates in exploration phases [START_REF] Krafft | Evolution of the knowledge base in knowledge intensive sectors[END_REF]). An increase in knowledge coherence is likely to signal the change to an exploitation strategy, while a decrease is likely to be linked to an exploration strategy. Increasing values for cognitive distance are likely to be related to random screening of the technology landscape, while decreasing cognitive distance is likely to be linked to organized search behaviour. Looking again at Figure 1, and bearing in mind the above trends, we can interpret the innovation behaviour of high growth firms. The inner boxes provide some clues about the expected signs of the knowledge variables for different innovation patterns.

The next section discusses the results of the empirical analysis.

Descriptive statistics

Figure 2 shows the distribution of firms' growth rates, for all the relevant variables. The empirical distribution of growth rates seems closer to a Laplacian than to a Gaussian distribution. This is in line with studies analysing the distribution of firm growth rates [START_REF] Bottazzi | Measuring Industry Relatedness and Corporate Coherence[END_REF][START_REF] Bottazzi | Common properties and sectoral specificities in the dynamics of U.S. manufacturing companies[END_REF][START_REF] Castaldi | The patterns of output growth of firms and countries: Scale invariances and scale specificities[END_REF]. Table 2 reports the descriptive statistics for knowledge indicators and the other variables in our model, expressed as growth rates normalized according to Equation 2. The values on kurtosis and on the percentiles confirm that growth rates are characterized by fat tailed (although highly skewed) distributions.

>>>INSERT FIGURE 2 AND TABLE 2 ABOUT HERE<<<

This suggests that standard regression estimators, such as ordinary least squares (OLS), and assuming Gaussian residuals, may perform poorly if applied to these data. To cope with this, a viable and increasingly popular alternative is to implement least absolute deviation (LAD) techniques, which are based on minimizing the absolute deviation from the median, rather than the squares of the deviation from the mean.

Figure 3 depicts the distribution of firm sales growth by macro-sector (see Appendix B for the definitions of macro-sectors). It shows that firm growth rates are highly dispersed in high-tech sectors and that the dispersion decreases from high-tech to low-tech sectors. Knowledge intensive sectors (denoted KIS) show highly dispersed growth rates.

>>>INSERT FIGURE 3 ABOUT HERE<<<

Table 3 presents the matrix of correlations among the variables used for the empirical exercise, at a significance level of 1%. Although some significant patterns of correlation can be identified, these involve mostly the variety-related variables, and (except for the three variety measures, which, as expected, are characterized by non-negligible correlations) the coefficients are not high enough to generate huge concern.

>>>INSERT TABLE 3 ABOUT HERE<<<

Methodology

Many of the empirical works analysing the determinants of firm growth are based on Gibrat's Law, which holds that firm growth is independent of firm size. However, some scholars claim that Gibrat's Law cannot be assumed to be a general law and its validity cannot be taken for granted ex ante (see Lotti, Santarelli and[START_REF] Lotti | Does Gibrats Law Hold Among Young, Small Firms?[END_REF]2009). Some studies find that growth rates are autocorrelated.

The original contribution of the present paper is that we reverse the traditional line of reasoning by adopting a demand-pull approach in which sales growth provides the incentive to commit resources to knowledge creation activities. Thus, our empirical strategy differs from other empirical work in the field based on the seminal contributions of [START_REF] Griliches | Inventing and maximizing[END_REF] and [START_REF] Scherer | Demand-Pull and Technological Invention: Schmookler Revisted[END_REF]. We directly test the effect of sales growth rates on knowledge creation, emphasizing the demand pull side of innovation. Another novelty of our approach is that we are not interested so much in understanding whether increasing sales affect the level of knowledge creation. Rather we investigate the qualitative aspects of the knowledge creation process by examining the properties of knowledge structure (i.e. variety, coherence and similarity). Our empirical implementation is described in the next section. It distinguishes the present analysis from contributions in the Schmooklerian tradition, and work that emphasizes the relative weak effect of firm sales on R&D intensity (see e.g. Pakes andSchankerman, 1977, 1984).

We are interested in the extent to which knowledge is (or is not) a determinant of firm growth, and whether the properties of the knowledge structure are related to one another and to the level of knowledge creation. An empirical strategy that investigates coevolution of the series is useful in not imposing any a priori relationship amongst the variables at stake. In order to identify the potential co-evolutionary patterns of the interdependent variables we implement the analysis in a (reduced form) vector autoregression (VAR) model [START_REF] Coad | Exploring the processes of firm growth: evidence from a vector auto-regression[END_REF]. First, recall the generic operational definition of the variables we use in the analysis s it , that is, growth rate detrended through normalization. The baseline VAR model can then be written as:

t i t i t i s a s , 1 , ,       (3)
where s it is an m1 vector of the random variables for firm i at time t,  is an mm matrix of the slope coefficients to be estimated. In our case m=7 and corresponds to the vector [sales growth (i,t), knowledge capital growth (i,t), coherence growth (i,t), increase in cognitive distance (i,t), increase in variety (i,t), growth of related variety (i,t), growth of unrelated variety (i,t)].  is an m1 vector of disturbances. The 7 structural equations are therefore the following (the variables has to be understood as normalized growth rates according to equation (2)):

t i t i t i t i t i t i t i t i t i UTV RTV TV CD COH E Sales a Sales , , 1 1 , 7 , 1 1 , 6 , 1 1 , 5 , 1 1 , 4 , 1 1 , 3 , 1 1 , 2 , 1 1 , 1 , 1 1 ,                         (3a) t i t i t i t i t i t i t i t i t i UTV RTV TV CD COH E Sales a E , , 2 1 , 7 , 2 1 , 6 , 2 1 , 5 , 2 1 , 4 , 2 1 , 3 , 2 1 , 2 , 2 1 , 1 , 2 2 ,                         (3b) t i t i t i t i t i t i t i t i t i UTV RTV TV CD COH E Sales a COH , , 3 1 , 7 , 3 1 , 6 , 3 1 , 5 , 3 1 , 4 , 3 1 , 3 , 3 1 , 2 , 3 1 , 1 , 3 3 ,                         (3c) t i t i t i t i t i t i t i t i t i UTV RTV TV CD COH E Sales a CD , , 4 1 , 7 , 4 1 , 6 , 4 1 , 5 , 4 1 , 4 , 4 1 , 3 , 4 1 , 2 , 4 1 , 1 , 4 4 ,                         (3d) t i t i t i t i t i t i t i t i t i UTV RTV TV CD COH E Sales a TV , , 5 1 , 7 , 5 1 , 6 , 5 1 , 5 , 5 1 , 4 , 5 1 , 3 , 5 1 , 2 , 5 1 , 1 , 5 5 ,                         (3e) t i t i t i t i t i t i t i t i t i UTV RTV TV CD COH E Sales a RTV , , 6 1 , 7 , 6 1 , 6 , 6 1 , 5 , 6 1 , 4 , 6 1 , 3 , 6 1 , 2 , 6 1 , 1 , 6 6 ,                         (3f) t i t i t i t i t i t i t i t i t i UTV RTV TV CD COH E Sales a UTV , , 7 1 , 7 , 7 1 , 6 , 7 1 , 5 , 7 1 , 4 , 7 1 , 3 , 7 1 , 2 , 7 1 , 1 , 7 7 ,                         (3g)
Since we are interested in the differential impact of high growth firms, we use indicator variables.

First, we build a simple dummy variable, which we call HGF, which identifies gazelles as firms whose average growth rate is at least 20% over the whole period. 6 This identifies 116 out of 335 firms as 6 Our data do not contain information on firm age; so we cannot use this in defining high growth firms. We acknowledge that high growth firms may be the result of rather heterogenous growth patterns. For example, merger and acquisition may introduce some noise in their identification (Delmar et al., 2003). Unfortunately, our dataset did not allow us to check for the influence of these issues.

high growth and allows us to investigate shifts in the intercept in the estimated equations for gazelles. We calculate the interaction variable [HGFsales growth(t-1)], which allows us to detect any modification in the slope coefficient of sales growth of gazelles.

Following [START_REF] Coad | Exploring the processes of firm growth: evidence from a vector auto-regression[END_REF], we do not include individual dummies in the analysis. Although unobserved heterogeneity, due, for example, to sector of activity, location, etc., can have important effects on the estimation results, the inclusion of firm-specific dummies along with lagged variables could produce biases in the fixed-effects estimation of the dynamic panel-data models, a problem known as Nickell-bias. An alternative approach would be to use instrumental variables (IV) or GMM estimators [START_REF] Blundell | Initial conditions and moment restrictions in dynamic panel data models[END_REF]. However, it is difficult to find good instruments, particularly when dealing with growth rates. If the instruments are weak, IV estimation of panel VAR could lead to imprecise estimates. [START_REF] Binder | Estimation and inference in short panel vector autoregressions with unit roots and cointegration[END_REF] propose a panel VAR model including firm-specific effects, which is based on the assumption of normally distributed errors, but this assumption does not apply to the growth rates of the variables in our regressions.

Since we are dealing with rates rather than levels of growth, in our view any firm-specific components have been mostly removed. We follow the large literature on analysis of firm growth rates which states that the non-Gaussian nature of growth rate residuals is a more important econometric problem and deserving of careful attention.

In view of this, equation ( 3) is estimated via reduced form VARs, to avoid any ex ante definition of the causal structure on the relationships between variables. Reduced form VARs correspond to a series of m individual regressions. Given the distributional properties of the variables, we prefer to implement LAD estimators.

Discussion of Empirical Results

Table 4 reports the results of the VAR estimation for the baseline model7 . The rows correspond to the regressions in the vector autoregression model. The columns present the differential effect of each (lagged) explanatory variable on each dependent variable. For the purposes of the present paper the first column contains the most important information because it shows the effect of lagged sales growth rates on the seven model variables. However, it should be noted that all the coefficients along the diagonal of the matrix are statistically significant, and with the exception of sales and knowledge capital, are negative. This suggests that while growth of knowledge properties shows little persistence, we observe some persistence in the case of sales and even more in the case of knowledge capital. This result contrasts with previous findings [START_REF] Coad | A Closer Look at Serial Growth Rate Correlation[END_REF][START_REF] Coad | Appropriate business strategy for leaders and laggards[END_REF] showing that the lagged values of sales growth has a negative effect on present values. However, this difference may be due to a peculiarity of the sampled firms, which is that they are all publicly listed and, therefore, may be affected by positive performance in final markets.

>>> INSERT TABLE 4 ABOUT HERE <<<

In relation to the coefficients, in the first column we observe a positive relationship between lagged sales growth and knowledge capital. This provides further support for the demand pull hypothesis according to which increasing sales provide firms with the resources required for the production of technological knowledge. For the effects on the properties of knowledge structure, we find that sales growth is negatively related to knowledge coherence and cognitive distance, but positively related to total variety. This suggests that the more firms grow, the more likely that their technology portfolios will show more variety. Technological variety is characterized by low levels of complementarity (coherence) (which supports the idea of an exploration strategy) but also by low levels of dissimilarity. This would suggest that increasing sales growth is associated with exploration directed towards the discovery of new, complementary fields that are not too distant from the firm's existing technological competences.

In order to understand whether high-growth firms show idiosyncratic patterns, Table 5 includes the dummy HGF as a regressor in all the VAR equations. If we look at the first two columns in Table 5, we can see that the results for patterns of persistence of the observed variables do not vary much. Note also that the effects of sales growth on these patterns are similar to the effects in Table 4. Increasing sales growth rates stimulates rates of growth of knowledge capital and knowledge variety, achieved by the adoption of search strategies directed to exploring new complementary fields that are still close to the firm's existing technological capabilities.

>>> INSERT TABLE 5 ABOUT HERE <<<

If we look at the HGF dummy, we see that, as expected, the coefficient of sales growth is positive and significant. It is also positive and significant for rate of growth of knowledge capital, suggesting that the economic influences on knowledge creation operating via the demand side are even stronger in the case of gazelles. If we look at the effects on the properties of knowledge structure, we find that the dummy is significant only in the case of cognitive distance, where the coefficient is negative. This suggests that, provided that increasing growth rates are associated with a reduction in cognitive distance, high growth firms tend to adopt search strategies characterized, on average, by lower levels of dissimilarity. The dummy does not show any other significant effects on the knowledge variables.

In Table 6, we include the interaction variable [sales growth(t-1)HGF]. The pattern does not change much in relation to rates of growth rates of the variables under scrutiny; the coefficient relating the lagged to the present value of each of the properties of knowledge structure is negative and significant, but the sign on knowledge capital is positive and significant.

>>> INSERT TABLE 6 ABOUT HERE <<<

The effect of lagged sales growth on knowledge is in line with the previous estimates, suggesting that increasing growth rates are likely to provide economic incentives for the commitment of resources for knowledge creation activities. Even in this case, the patterns of effects on the properties of the knowledge base confirm that increasing growth rates lead to the introduction of knowledge variety through exploration strategies directed towards the widening of complementary technologies (coherence), which are similar to the existing technology portfolio. This interpretation is supported also by the positive and significant coefficient of related variety.

Columns 2 and 3 of Table 6 refer to the subgroup of high growth firms. The coefficients of the dummy variable suggest that it promotes higher rates of growth of knowledge capital. In addition, and importantly, gazelles are characterized on average by lower rates of growth of coherence, which is consistent with the tendency to adopt exploratory behaviours, although the negative coefficient of sales growth is mitigated by the coefficient of the interaction variables. That is, high growth firms on average tend to adopt exploration strategies, although in that subgroup increasing rates of growth do not lead to consistent variations in this behaviour. The value and the negative sign of the variety variables confirms that increasing growth rates in the group of gazelles are associated with fairly stable technological variety.

The analysis would seem to support the idea that gazelles cannot be unambiguously categorized as Schumpeter Mark I or Mark II innovating firms. They seem to follow a hybrid pattern of search behaviour, characterized both by exploration and implementation of organized search strategies. Thus, gazelles are associated more with an organized exploration pattern, and would fit in the bottom-left quadrant of Figure 1. On average, increasing sales growth rates stimulate the creation of new technological knowledge through the adoption of search behaviours directed more to screening new complementary fields, which are compatible with an exploration strategy. However, the screening activity is not random: it seems that fast growing firms prefer to remain reasonably close to their existing technological competences. In the group of gazelles this pattern of behaviour is especially marked since they appear to be characterized by lower rates of growth of coherence and cognitive distance, and related variety on average. We find therefore, that high growth firms, and especially gazelles, predominantly follow exploration strategies that have some of the characteristics of organized search more typical of an exploitation strategy.

Conclusions

The process of firm growth has attracted the attention of economists for many years. A relatively recent strand in the literature on high-growth firms refers to gazelles or fast growing firms, based on evidence of their exceptional contribution to aggregate economic growth. However, few studies look at the relationship between high-growth firms and innovation. The literature mostly analyses innovation as a determinant of high rates of growth. There are no studies of the contribution made by gazelles to the process of knowledge creation.

The main objective of this paper was to investigate the differential contribution of high growth firms to the process of knowledge creation drawing on the literature on Schumpeterian patterns of innovation to construct a demand-pull framework à la Schmookler in which sales growth is the motivation for the creation of new technological knowledge. We investigated whether gazelles are more likely to follow Mark I or Mark II patterns of knowledge creation.

The inclusion of recombinant knowledge theory in our framework allowed us to propose the concept of knowledge structure characterized by three properties -variety (related and unrelated), coherence, and similarity -which can be usefully employed to distinguish between 'random screening' and 'organized search' strategies.

The analysis was based on data on listed companies and patent applications. We implemented a series of VARs estimated by means of LAD estimators, including a dummy and interaction variable to detect differential performance by gazelles. The empirical results suggest that within the group of high growth firms, increasing sales growth rates stimulate the creation of new technological knowledge and also drive search behaviours characterized by the screening of complementary fields across the technology landscape that are not too far removed from the firm's existing technological competences. In this respect, the distinctive knowledge dynamics of gazelles are likely to shape their positive impacts on industry dynamics [START_REF] Bos | Gazelles and industry growth[END_REF]. This paper is a first attempt to investigate the contribution of gazelles to the process of knowledge creation. Future work could analyse the relationship by splitting the sample according to different quantile definitions. Empirical implementations of knowledge coherence, such as in this paper, have been criticized by [START_REF] Bottazzi | Measuring Industry Relatedness and Corporate Coherence[END_REF]; it would be interesting to use the corrected index they propose, to check whether our results still hold. It would be interesting also to check the robustness of our results, by implementing different estimators to account for the distribution of explanatory variables and the impact of outliers.

Moreover, the evidence provided by this paper constitutes a basis for further interesting investigations, and especially in the domain of innovation and technology policies. Because highgrowth firms are important knowledge producers, the dynamics leading them to be innovative and to take stock of their ability to broaden their knowledge bases, should be taken into account by policy makers. Moreover, they require special consideration as they are spread across all industries in the economy. Innovation policies should in this respect be careful and valorise the contribution made by gazelles through the processes of creative destruction. the subsets measuring the variety across them. It can be easily shown that the decomposition theorem also holds for the multidimensional case. Hence if one allows jS g and mS z (g = 1,…,G; z = 1,…, Z), we can rewrite H(X,Y) as follows:

     G g Z z gz gz Q H P H Y X H 1 1 ) , ( (A2)
where the first term on the right-hand-side is the between-group entropy and the second term is the (weighted) within-group entropy. In particular:

    G g Z z gz gz Q P P H 1 1 2 1 log (A2a)      g Z S j S m jm gz p P (A2b)              g z S j S m gz jm gz ij gz P p P p H / 1 log 2 (A2c)
Following [START_REF] Frenken | Related Variety, Unrelated Variety and Regional Economic Growth[END_REF], we can refer to between-group and within-group entropy respectively as unrelated technological variety (UTV) and related technological variety (RTV), while total information entropy is referred to as general technological variety (TV). The distinction between related and unrelated variety is based on the assumption that any pair of entities included in the former generally are more closely related or more similar to any pair of entities included in the latter.

This assumption is reasonable given that a type of entity (patent, industrial sector, trade categories etc.) is organized according to a hierarchical classification. In this case each class at a given level of aggregation contains 'smaller' classes, which, in turn contain yet 'smaller' classes. Here, small refers to a low level of aggregation.

We can reasonably expect then that the average pair of entities at a given level of aggregation will be more similar than the average pair of entities at a higher level of aggregation. Thus, what we call related variety is measured at a lower level of aggregation (3 digit class within a 1 digit macro-class) than unrelated variety (across 1 digit macro-classes). This distinction is important because we can expect unrelated (or inter-group) variety to affect productivity growth negatively, while related (or intra-group) variety is expected to be positively related to productivity growth. Moreover, the evolution of total variety is heavily influenced by the relative dynamics of related and unrelated variety, such that if unrelated variety is dominant the effects of total variety on productivity growth can be expected to be negative, while the opposite holds if related technological variety dominates the total index [START_REF] Krafft | The knowledge base evolution in biotechnology: A social network analysis[END_REF].

Knowledge Coherence

Third, we calculated the coherence (R) of firms' knowledge bases, defined as the average complementarity of any technology randomly chosen within the firm's portfolio with respect to any other technology [START_REF] Nesta | Knowledge and productivity in the world's largest manufacturing corporations[END_REF]Saviotti, 2005, 2006;[START_REF] Nesta | Knowledge and productivity in the world's largest manufacturing corporations[END_REF].

To yield the knowledge coherence index, a number of steps is required. In what follows we describe how to derive the index at the firm level. .. Applying this relationship to all possible pairs yields a square matrix  (n  n) whose generic cell is the observed number of co-occurrences:

                  nn mn n nj mj j n m J J J J J J J J J         1 1 1 1 11 (A1)
We assume that the number x mj of patents assigned to both technologies m and j is a hypergeometric random variable of mean and variance:

K O O x X E j m mj mj    ) (  (A2)                   1 2 K O K K O K j m ij mj   (A3)
If the observed number of co-occurrences J mj is larger than the expected number of random co-occurrences  mj , then the two technologies are closely related: the fact the two technologies occur together in the number of patents x ij is not casual. The measure of relatedness hence is given by the difference between the observed number and the expected number of co-occurrences, weighted by their standard deviation:

mj mj mj mj J      (A4)
It is worth noting that our relatedness measure has no lower and upper bounds:

      ; mj 
. Moreover, the index shows a distribution similar to a t-student, so that if

  96 . 1 ; 96 . 1    mj 
, one can safely accept the null hypothesis of non-relatedness of the two technologies i and j. The technological relatedness matrix ' may hence be thought about as a weighting scheme to evaluate the technological portfolio of firms.

Following [START_REF] Teece | Understanding Corporate Coherence: Theory and Evidence[END_REF], WAR j is defined as the degree to which technology j is related to all other technologies mj within the firm i, weighted by patent count P mit :

     i m mit j m mit jm jit P P WAR  (A3)
Finally, knowledge base coherence within the firm is defined as the weighted average of the WAR jit measure:

     m j j jit jit jit it P P WAR R (A4)
This measure captures the degree to which the technologies making up the firm's knowledge base are complementary. The relatedness measure  jm indicates that utilization of technology j implies utilization of technology m in order to perform specific functions that are not reducible to their independent use. This makes the coherence index appropriate for the purposes of this study.

Cognitive Distance

We implement a measure of knowledge similarity, proxied by cognitive distance [START_REF] Nooteboom | Learning and innovation in organizations and economies[END_REF], which expresses the dissimilarities amongst different types of knowledge. A useful index of distance can be derived from the measure of technological proximity, originally proposed by [START_REF] Jaffe | Technological Opportunity and Spillovers of R&D: Evidence from Firms' Patents, Profits, and Market Value[END_REF][START_REF] Jaffe | Real Effects of Academic Research[END_REF], who investigated the proximity of firms' technological portfolios. [START_REF] Breschi | Knowledge relatedness in firm technological diversification[END_REF] adapted the index in order to measure the proximity, or relatedness, between two technologies. The idea is that each firm is characterized by a vector V of the k technologies that occur in its patents.

Knowledge similarity can first be calculated for a pair of technologies l and j as the angular separation or uncentred correlation of the vectors V lk and V jk . The similarities between technologies l and j can then be defined as follows:

       n k jk n k lk n k jk lk lj V V V V S 1 2 1 2 1 (A5)
The idea behind the calculation of this index is that two technologies j and i are similar to the extent that they co-occur with a third technology k. The cognitive distance between j and i is the complement of their index of the similarity:

lj lj S d   1 (A6)
Once an index is calculated for all possible pairs, it needs to be aggregated at the firm level to obtain a synthetic index of technological distance. This is done in two steps.

Figure 1

 1 Figure 1 allows us to visualize the typical Schumpeterian Mark 1 and Mark 2 patterns of innovation

  a) Knowledge variety (KV) measures the degree of technological diversification of the knowledge base. It is derived from the information entropy index and can be decomposed into related knowledge variety (RKV) and unrelated knowledge variety (UKV). b) Knowledge coherence (COH) measures the degree of complementarity among technologies. c) Cognitive distance (CD) expresses knowledge dissimilarities amongst different types of knowledge.

  First, we need to calculate the weighted average relatedness WAR i of technology i with respect to all other technologies present in the sector. Such a measure builds on the measure of technological relatedness ,. The calculation of such a measure builds on the relatedness matrix. The technological universe consists of k patent applications. Let P mk = 1 if the patent k is assigned the technology m [m = 1, …, n], and 0 otherwise. The total number of patents assigned to technology m is thus the observed the number of observed co-occurrences of technologies m and

  Figure 1

Figure 3 -

 3 Figure 3 -Box plot of sales growth by macro-sector

Table 1 -Distribution of sampled firmsby macro-sector, size and country, 1988-2005

 1

		Macro Sector	Country		Size
		Freq. Percent	Freq. Percent	Freq. Percent
	HT	102	30.45 France	83	24.78 Large	271	80.9
	MHT	123	36.72 Germany	114	34.03 Medium	45	13.43
	MLT	11	3.28 Italy	34	10.15 Micro	1	0.3
	LT	34	10.15 Netherlands	13	3.88 Small	18	5.37
	KIS	26	7.76 Sweden	43	12.84
	LKIS	1	0.30 UK	48	14.33
	OS	5	1.49
	Constr	23	6.87
	EP	10	2.99
	Total	335 100.00	335 100.00	335 100.00

Table 2 -Descriptive statistics (All variables are expressed in normalized growth rates according to Eq. 2).

 2

		Std. Dev. skewness kurtosis	p10	p25	p50	p75	p90	Obs.
	Sales Growth	0.395	1.716	33.500	-0.099	0.012	0.112	0.250	0.557	2819
	Knowledge Coherence	0.353	-0.628	33.390	-0.288	-0.104	-0.007	0.089	0.285	2819
	Knowledge Capital	0.178	2.351	13.146	-0.096	-0.032	0.041	0.138	0.272	2819
	Cognitive Distance	0.242	0.278	11.531	-0.169	-0.032	-0.006	0.029	0.177	1448
	Knowledge Variety	0.132	0.401	25.337	-0.058	-0.018	0.004	0.033	0.103	2554
	Related Variety	0.231	0.553	10.983	-0.180	-0.049	0.001	0.067	0.235	2287
	Unrelated Variety	0.167	0.088	10.986	-0.128	-0.031	0.006	0.043	0.151	2394

Table 3 -Spearman's Rank Correlation Matrix

 3

	Sales Growth	Knowledge Coherence	Knowledge Capital	Cognitive Distance	Related Variety	Unrelated Variety	Knowledge Variety
	Sales Growth	1.0000
	Kn. Coherence	-0.0048	1.0000
	Knowledge Capital	0.0114	0.0862*	1.0000
	Cognitive Distance	-0.0212	0.0651*	0.0211	1.0000
	Related Variety	-0.0618*	-0.1138*	0.3226*	-0.0624*	1.0000
	Unrelated Variety	-0.0225	-0.1224*	0.1262*	-0.0428	0.3677*	1.0000
	Knowledge Variety	0.0124	0.0150	0.2184*	-0.0098	0.4753*	-0.3906*	1.0000
	Note: * Significant at 5% level.

Table 4 -Results of VAR estimation, one-year lag. Baseline model (All variables are expressed in normalized growth rates according to Eq. 2).

 4

		Sales Growth(t-1)	Knowledge Coherence (t-1)	Knowledge Capital (t-1)	Cognitive Distance (t-1)	Related Variety (t-1)	Unrelated Variety (t-1)	Knowledge Variety (t-1)	N. Obs.
	Sales Growth	.101*** (.008)	.007 (.012)	-.103*** (.028)	.031* (.016)	-.026 (.039)	-.003 (.055)	.091 (.104)	1366
	Knowledge Coherence	-.021*** (.007)	-.303*** (.009)	.035 (.022)	.016 (.013)	.072** (.031)	.113*** (.044)	-.282*** (.082)	1366
	Knowledge Capital	.013*** (.003)	.006 (.005)	.699*** (.011)	.0001 (.006)	-.037** (.015)	-.044** (.022)	.119*** (.041)	1366
	Cognitive Distance	-.008*** (.003)	.002 (.004)	.011 (.009)	-.013** (.005)	.004 (.014)	-.012 (.019)	.057 (.037)	1288
	Related Variety	.0004 (.005)	.010 (.007)	.130*** (.017)	.020** (.010)	-.240*** (.024)	-.021 (.033)	.195*** (.063)	1366
	Unrelated Variety	-.00006 (.004)	-.0001 (.005)	.004 (.013)	.003 (.008)	.042** (.019)	-.072*** (.027)	.015 (.051)	1366
	Knowledge Variety	.005** (.002)	.001 (.003)	.081*** (.008)	-.010** (.004)	.026** (.011)	.036** (.016)	-.239*** (.030)	1366

Note: bootstrapped standard errors between parentheses. p<0.1; ** : p<0.05; *** : p<0.01.

Table 5 -Results of VAR estimation. One-year lag. Model including a dummy for HGFs (All variables are expressed in normalized growth rates according to Eq. 2).

 5

		Sales Growth(t-1)	HGF (dummy)	Knowledge Coherence (t-1)	Knowledge Capital (t-1)	Cognitive Distance (t-1)	Related Variety (t-1)	Unrelated Variety (t-1)	Knowledge Variety (t-1)	N. Obs.
	Sales Growth	.063*** (.009)	.218*** (.009)	.030** (.012)	-.097*** (.029)	.001 (.017)	.049 (.040)	.050 (.057)	-.066 (.107)	1366
	Knowledge Coherence	-.020*** (.006)	-.008 (.006)	-.299*** (.008)	.031* (.019)	.018* (.011)	.062** (.026)	.094*** (.038)	-.262*** (.071)	1366
	Knowledge Capital	.0137*** (.004)	.009** (.004)	.006 (.005)	.694*** (.012)	-.003 (.007)	-.025 (.018)	-.030 (.025)	.092** (.047)	1366
	Cognitive Distance	-.009*** (.003)	-.005* (.003)	.002 (.004)	.011 (.009)	-.011** (.006)	-.006 (.014)	-.028 (.020)	.093** (.038)	1228
	Related Variety	-.0002 (.005)	.001 (.006)	.010 (.007)	.129*** (.018)	.020* (.010)	-.236*** (.026)	-.018 (.036)	.187*** (.068)	1366
	Unrelated Variety	-.0007 (.004)	.005 (.004)	.0004 (.006)	.010 (.014)	.0014 (.008)	.051*** (.020)	-.065** (.029)	-.011 (.054)	1366
	Knowledge Variety	.005** (.002)	.002 (.003)	.001 (.003)	.081*** (.008)	-.009** (.004)	.025** (.011)	.035** (.016)	-.235*** (.031)	1366

Note: bootstrapped standard errors between parentheses. p<0.1; ** : p<0.05; *** : p<0.01.

Table 6 -Results of VAR estimation. One-year lag. Model including both the HGFs dummy and the interaction term (All variables are expressed in normalized growth rates according to Eq. 2).

 6

		Sales Growth(t-1)	HGF (dummy)	HGF*Growth	Knowledge Coherence (t-1)	Knowledge Capital (t-1)	Cognitive Distance (t-1)	Related Variety (t-1)	Unrelated Variety (t-1)	Knowledge Variety (t-1)	N. Obs.
	Sales Growth	.075*** (.011)	.232*** (.010)	-.043** (.021)	.034*** (.013)	-.097*** (.030)	.001 (.017)	.056 (.042)	.058 (.060)	-.080 (.112)	1366
	Knowledge Coherence	-.035*** (.007)	-.013* (.008)	.031** (.015)	-.307*** (.010)	.031 (.022)	.018 (.013)	.059* (.031)	.097** (.045)	-.250*** (.085)	1366
	Knowledge Capital	.017*** (.004)	.009** (.004*	-.005 (.009)	.007 (.005)	.698*** (.012)	-.003 (.007)	-.028* (.017)	-.031 (.025)	.094** (.046)	1366
	Cognitive Distance	-.007** (.003)	-.004 (.003)	-.004 (.007)	.003 (.004)	.010 (.010)	-.012** (.006)	-.004 (.015)	-.027 (.021)	.089** (.040)	1228
	Related Variety	.013** (.006)	.005 (.006)	-.027** (.013)	.011 (.007)	.135*** (.018)	.023** (.010)	-.231*** (.025)	-.018 (.036)	.162** (.068)	1366
	Unrelated Variety	-.0009 (.005)	.004 (.005)	.004 (.010)	.0003 (.006)	.008 (.015)	.002 (.009)	.044** (.021)	-.063** (.030)	-.002 (.056)	1366
	Knowledge Variety	.009*** (.003)	.002 (.003)	-.009* (.006)	.001 (.003)	.078*** (.008)	-.010** (.005)	.031*** (.012)	.043*** (.017)	-.244*** (.032)	1366

Note: bootstrapped standard errors between parentheses. p<0.1; ** : p<0.05; *** : p<0.01.

Of course, the seeds of the argument go back to Adam Smith (1776), who emphasized the indirect effects of increasing demand on technological change through the positive effects of the division of labour. This argument was developed and integrated by Marshall (1890) andYoung (1928).

This relatively small number of firms is the outcome of merging the dataset with company-level information and patent applications. They are firms that are listed on the relevant markets and which submitted more than 1 patent application during the observed period. The firms in the sample are observed for at least 6 years for the sales variable. Average observation time is 9.4 years.

The limitations of patent statistics as indicators of technological activities are well known. They include sector-specificity, existence of non-patentable innovations and the fact that they are not the only means of protection. Also, the propensity to patent tends to vary over time as a function of the cost of patenting, and is more frequent in large firms[START_REF] Pavitt | Patent statistics as indicators of innovative activities: Possibilities and problems[END_REF][START_REF] Griliches | Patent statistics as economic indicators: a survey[END_REF]. However, previous studies highlight the utility of patents as a measure of the production of new knowledge. Studies show that patents are very reliable proxies for knowledge and innovation compared to analyses that use data from surveys on the dynamics of process and product innovation[START_REF] Acs | Patents and Innovation Counts as Measures of Regional Production of New Knowledge[END_REF]. Alongside the debate on patents as outputs rather than inputs of innovation activity, empirical analyses show that patents and R&D are dominated by a contemporaneous relationship, providing further support for patents to proxy for technological activities[START_REF] Hall | Patents and R and D: Is there a lag?[END_REF].

Note that to compensate for intrinsic volatility in patenting behaviour, patent applications refer to the last five years.

The models discussed in this section have also been estimated by using OLS. The results obtained are similar to those obtained with LAD estimations in terms of coefficients' signs and significance, especially for what concerns the HGF dummy.

The authors acknowledge the financial support of the European Union D.G. Research with the Grant number 266959 to the research project 'Policy Incentives for the Creation of Knowledge: Methods and Evidence' (PICK-ME), within the context of the Cooperation Program / Theme 8 / Socio-economic Sciences and Humanities (SSH).

APPENDIX A -The properties of knowledge structure Knowledge Variety

We measure variety in the firm's knowledge base using the information entropy index. Entropy measures the degree of disorder or randomness of the system, so that systems characterized by high entropy will also be characterized by high levels of uncertainty [START_REF] Saviotti | Information, variety and entropy in technoeconomic development[END_REF].

The index was introduced to economic analysis by [START_REF] Theil | Economics and Information Theory[END_REF]. Its earlier applications aimed at measuring the degree of diversity of industrial activity (or of a sample of firms within an industry) against a uniform distribution of economic activities in all sectors, or among firms [START_REF] Attaran | Industrial diversity and economic performance in U.S. areas[END_REF][START_REF] Frenken | Related Variety, Unrelated Variety and Regional Economic Growth[END_REF][START_REF] Boschma | Related variety, trade linkages, and regional growth in Italy[END_REF].

Compared to common measures of variety and concentration, information entropy has some interesting properties [START_REF] Frenken | Entropy Statistics as a Framework to Analyse Technological Evolution[END_REF]). An important feature of the entropy measure, which we exploit in our analysis, is its multidimensional extension. Consider a pair of events (X j , Y m ), and the probability of their co-occurrence p jm . A two dimensional (total) entropy measure can be expressed as follows (firm and time subscripts are omitted for the sake of clarity):

If p jm is assumed to be the probability that two technological classes j and m co-occur within the same patent, then the measure of multidimensional entropy focuses on the variety of cooccurrences of technological classes within firms' patent portfolios.

Moreover, the total index can be decomposed in a 'within' and a 'between' part whenever the events to be investigated can be aggregated to form a smaller numbers of subsets. Within-entropy measures the average degree of disorder or variety within the subsets, between-entropy focuses on

Appendix B -Sectoral classification and concordance


Frédéric Giroire
email: frederic.giroire@cnrs.fr

Joanna Moulierac
email: joanna.moulierac@unice.fr

Khoa Truong
email: truongkhoa.phan@inria.fr

Phan

Optimizing Rule Placement in Software-Defined Networks for Energy-aware Routing

Software-defined Networks (SDN), in particular OpenFlow, is a new networking paradigm enabling innovation through network programmability. Over past few years, many applications have been built using SDN such as server load balancing, virtual-machine migration, traffic engineering and access control. In this paper, we focus on using SDN for energyaware routing (EAR). Since traffic load has a small influence on power consumption of routers, EAR allows to put unused links into sleep mode to save energy. SDN can collect traffic matrix and then computes routing solutions satisfying QoS while being minimal in energy consumption. However, prior works on EAR have assumed that the table of OpenFlow switch can hold an infinite number of rules. In practice, this assumption does not hold since the flow table is implemented with Ternary Content Addressable Memory (TCAM) which is expensive and power-hungry. In this paper, we propose an optimization method to minimize energy consumption for a backbone network while respecting capacity constraints on links and rule space constraints on routers. In details, we present an exact formulation using Integer Linear Program (ILP) and introduce efficient greedy heuristic algorithm. Based on simulations, we show that using this smart rule space allocation, it is possible to save almost as much power consumption as the classical EAR approach.

I. INTRODUCTION

Recent studies have shown that ICT is responsible for 2% to 10% of the worldwide power consumption [START_REF] Chiaraviglio | Minimizing ISP Network Energy Cost: Formulation and Solutions[END_REF]. As estimation, energy requirement for European telecommunication can reach 35.8 TWh in 2020 [START_REF] Bolla | The Potential Impact of Green Technologies in Nextgeneration Wireline Networks: Is There Room for Energy Saving Optimization?[END_REF]. Backbone ISP networks currently consume around 10% of the total network power requirements and it can increase to 40% by 2017 [START_REF] Lange | Energy-related aspects in backbone networks[END_REF]. Therefore the green networking has been attracting a growing attention during the last years (see the survey [START_REF] Bianzino | A Survey of Green Networking Research[END_REF]). While the traffic load has a marginal influence, the power consumption is mainly due to active elements on IP routers such as ports, line cards, base chassis, etc. [START_REF] Mahadevan | A Power Benchmarking Framework for Network Devices[END_REF]. Based on this observation, the energy-aware routing (EAR) approach aims at minimizing the number of used network elements while all the traffic demands are routed without any overloaded links [START_REF] Chiaraviglio | Minimizing ISP Network Energy Cost: Formulation and Solutions[END_REF] [START_REF] Gupta | Greening of The Internet[END_REF]. In fact, turning off entire routers can earn significant energy savings. However, it is very difficult from a practical point of view as it takes time for turning on/off and also reduces life cycle of devices. Therefore, as in prior work [START_REF] Chiaraviglio | Sleep Modes Effectiveness in Backbone Networks with Limited Configurations[END_REF] [START_REF] Giroire | Minimization of Network Power Consumption with Redundancy Elimination[END_REF], we assume to turn off (or put into sleep mode) only links to save energy. Software-defined networking (SDN) in general, and Open-Flow in particular [START_REF] Mckeown | Openflow: Enabling Innovation in Campus Networks[END_REF], has been attracting a growing attention in the networking research community in recent years. In traditional networks, network devices such as routers and switches act as "closed" systems. They work as "black boxes" with applications implemented on them. Users can only control them via limited and vendor-specific control interfaces. Moreover, since the data plane (forwarding function) and control plane are integrated, it is difficult for current network infrastructure to evolve (e.g. to deploy new network protocols). SDN is a new networking paradigm that decouples the control plane from the data plane. It provides a flexibility to develop and test new network protocols and policies in real networks. Over past few years, many applications have been built using the OpenFlow API [START_REF] Mckeown | Openflow: Enabling Innovation in Campus Networks[END_REF].

In this paper, we focus on one application of the OpenFlow, that is to use OpenFlow to minimize power consumption for an Internet Service Provider (ISP). As shown in literature, many existing works have used OpenFlow as a traffic engineering approach to deploy EAR in a network [START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF] [START_REF] Wang | CARPO: Correlation-Aware Power Optimization in Data Center Networks[END_REF]. In these works, the flow table of each switch is assumed to hold an infinite number of rules. In practice, however, this assumption does not hold, and rule space becomes a significant bottleneck for large-scale SDN networks. It is because the flow table is implemented using Ternary Content Addressable Memory (TCAM) which is expensive and power hungry. Therefore, commodity switches typically support just from few hundreds to few thousands of entries [START_REF] Kang | Optimizing the "One Big Switch" Abstraction in Software-Defined Networks[END_REF][14] [START_REF] Stephens | PAST: Scalable Ethernet for Data Centers[END_REF]. Taking this limitation into account, we show that the rule space constraints are very important in EAR. An inefficient rule allocation can lead to an unexpected routing solution, causing network congestion and affecting QoS. In summary, we make the following contributions:

• To our best knowledge, this is the first work that defines and formulates the optimizing rule space problem in OpenFlow for EAR using ILP.

• As EAR is known to be NP-hard [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF], we propose heuristic algorithm that is effective for large network topologies. By simulations, we show that the heuristic algorithm achieves close-to-optimal solutions obtained by the ILP.

• Using real-life data traffic traces from SNDlib [START_REF] Orlowski | SNDlib 1.0 -survivable network design library[END_REF], we quantify energy savings achieved by our approaches. Moreover, we also present other QoS aspects such as routing length of EAR solutions.

The rest of this paper is structured as follows. We summarize related work in Section II. We present the ILP and heuristic algorithm in Section III. Simulation results are shown in Section IV. Finally, we conclude our work in Section V.

A. Limited Rule Space in OpenFlow Switches

To support a vast range of network applications, OpenFlow rules are more complex than forwarding rules in traditional IP routers. For instance, access-control requires matching on source -destination IP addresses, port numbers and protocol [START_REF] Casado | Rethinking Enterprise Network Control[END_REF] whereas a load balancer may match only on source and destination IP prefixes [START_REF] Wang | OpenFlow-based Server Load Balancing Gone Wild[END_REF]. These complicated matching can be well supported using TCAM since all rules can be read in parallel to identify the matching entries for each packet. However, as TCAM is expensive and extremely power-hungry, the on-chip TCAM size is typically limited. Many existing works in literature have tried to address this limited rule space problem. For instance, starting with OpenFlow v1.1 and beyond, rather than having one flow table, there is a pipeline made up of multiple flow tables. While this proposal can handle a large number of rules, it does add complexity to the standard [START_REF]OpenFlow Switch Specication version 1.1[END_REF]. The authors in [START_REF] Meiners | Bit Weaving: A Non-prefix Approach to Compressing Packet Classifiers in TCAMs[END_REF] have proposed algorithms to reduce the number of rules needed to realize policies on a single switch. To the best of our knowledge, the closest papers to our work are [START_REF] Kang | Optimizing the "One Big Switch" Abstraction in Software-Defined Networks[END_REF] and [START_REF] Kanizo | Palette: Distributing Tables in Software-defined Networks[END_REF]. These works present efficient heuristic rule-placement algorithms that distribute forwarding policies while managing rule-space constraints at each switch. However, they do not rely on the exact meaning of the rules and the rules should not determine the routing of the packet (e.g. access control rules) [START_REF] Kanizo | Palette: Distributing Tables in Software-defined Networks[END_REF]. Therefore, these techniques cannot directly solve the rule-placement problem in EAR. In this work, we focus on EAR with OpenFlow where rules explicitly determine routing of traffic flows. Besides an exact formulation ILP, we also propose an efficient heuristic algorithm for large networks.

B. Energy Savings with OpenFlow

Starting from the pioneering work of Gupta [START_REF] Gupta | Greening of The Internet[END_REF], the idea of power proportionality has gained a growing attention in networking research area [2][6]. Since power consumption of router is independent from traffic load, people suggested putting network components to sleep in order to save energy. OpenFlow is a promising method to implement EAR in a network. Without setting entries manually, OpenFlow can collect traffic matrix, performs routing calculation and then installs new routing rules on routers. For instance, the authors in [START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF] have implemented and analyzed ElasticTree on a prototype testbed built with production OpenFlow switches. The idea is to use OpenFlow to control traffic flows so that it minimizes the number of used network elements to save energy. Similarly, the authors in [START_REF] Wang | CARPO: Correlation-Aware Power Optimization in Data Center Networks[END_REF] have set up a small testbed using OpenFlow switches to evaluate energy savings for their model. OpenFlow switches have also been mentioned in existing work as an example of the traffic engineering method to implement the EAR idea [START_REF] Curtis | DevoFlow: Scaling Flow Management for High-Performance Networks[END_REF]. However, as we can see, the testbed setups with real OpenFlow switches are quite small. For instance, in [START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF], 45 virtual switches onto two 144-port 5406 chassis switches are used; or in [START_REF] Wang | CARPO: Correlation-Aware Power Optimization in Data Center Networks[END_REF], there is a testbed with 10 virtual switches on a 48-port Pronto 3240 OpenFlow-enabled switch. We argue that when deploying EAR in real network topologies, much more real OpenFlow switches should be used and they have to handle a large amount of traffic flows. In this situation, limited rule space in switches becomes a serious problem since we can not route traffic as expected. Therefore, we present in next Section a novel optimization method to overcome the rule placement problem of OpenFlow for EAR.

III. OPTIMIZING RULE PLACEMENT

Routing decision of an OpenFlow switch is based on flow tables implemented with TCAM. Each entry in the flow table defines a matching rule and is associated with an action. Upon receiving a packet, a switch identifies the highest-priority rule with a matching predicate, and performs the corresponding action. A packet that matches no rule is processed using the default rule, which has the lowest-priority. Depending on applications of OpenFlow, the default rule can be "drop packets" or "forward packets to the controller" over the OpenFlow channel. In this work, to avoid delay communication between routers and the centralized controller, we consider that the default rule is "forward packets to a default port" (without contacting the controller), and each switch has exactly one default port [START_REF] Nunes | A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks[END_REF].

TABLE I: Traffic demands and routing solutions

Traffic demand

Volume Routing solution Routing solution (Fig. 1b) (Fig. 1c)

(0, 4) 1 0 -2 -4 0 -1 -3 -4 (0, 5) 2 0 -2 -5 0 -1 -3 -4 -5 (0, 6) 2 0 -2 -5 -6 0 -2 -5 -6 (1, 4) 1 1 -0 -2 -6 -5 -4 1 -3 -4 (1, 5) 3 1 -0 -2 -4 -5 1 -0 -2 -5 (1, 6) 3 1 -0 -2 -6 1 -0 -2 -6 (2, 4) 1 2 -4 2 -0 -1 -3 -4 (2, 5) 1 2 -5 2 -6 -5 (2, 6) 1 2 -6 2 -6 ! !
Fig. 2: Routing table at router 2 for routing of Fig. 1b We show in Fig. 1 how the limited rule space impacts EAR solution. Assume that there are 9 traffic demands with volumes as shown in Table I. The network topology and capacity on links are shown in Fig. 1a. For ease of reading, Table I also shows the routing of each traffic flow in Fig. 1b and Fig. 1c. These routing solutions are found by using the ILP in Section III.A. As the classical EAR approach, Fig. 1b shows an optimal solution since it satisfies capacity constraints and uses a minimum number of active links (7 links). It is noted that, as the objective of EAR is to minimize the number of used links, some traffic flows may be routed via long paths. For instance, the flow (1, 4) is routed via 5 hops while its shortest path is only 2 hops. One possible way to avoid this is to have some constraints that limit the stretch of the path of each flow.

Assume that the routing table of router contains rules which are the mapping of [(src, dest) : port-to-foward]. As the routing in Fig. 1b, the router 2 needs to forward 9 flows, hence a simple routing table can be as Fig. 2a. However, we can reduce the size of the routing table by using a default rule (Fig. 2b), or combining default rule and wildcards (Fig. 2c). Note that the rules [(0, 5): port-5] and [(0, 6): port-5] of Fig. 2b can not be combined as [(0, *): port-5]. Indeed, in this case, the flow (0, 4) will go to port-5 when it should go to port-4. In Fig. 2c, as the rule (1, 5) has higher priority than the rule (1, *), the flow (1, 5) is forwarded to port-4 while the flows (1, 4) and (1, 6) are forwarded to port-6 with the rule (1, *). Assume that we implement EAR on SDN network where each router can install at most 4 rules. As a result, the router 2 can install only 3 distinct rules and 1 default rule. However, as we have shown, the minimum routing table contains 5 rules (Fig. 2c). Therefore, in this situation, some flows need to be routed using the default port. For instance, if the flow [START_REF] Bianzino | A Survey of Green Networking Research[END_REF][START_REF] Chiaraviglio | Minimizing ISP Network Energy Cost: Formulation and Solutions[END_REF] in Fig. 2c goes to the default port-5, then the link (2, 5) will be overloaded. It is also easy to check that, when the rule capacity is equal to 4 and with a set of active links as in Fig. 1b, it is not possible to find a routing solution that satisfies both capacity constraints on links and rule space constraints on routers. However, if we consider the rule space constraints as inputs of the problem, we can find a feasible solution as Fig. 1c. Actually, since we add more constraints, the EAR with rule space is able to save less energy with respect to the classical EAR. For instance, there is only 1 inactive link in Fig. 1c while we can turn off 2 links and save more energy in Fig. 1b.

As we have shown in this example, the limited rule space is very important in EAR. Inefficient rule placement can cause unexpected routing solution, and hence result in network congestion. To overcome this problem, we present in this section a precise formulation (Integer Linear Program) and heuristic approach for large networks. However, we note that the current algorithms can find optimal solution of energy consumption (or close-to-optimal if it is heuristic) if we consider the default rule but not the wild-card. If the rule space is scarce, we can apply the work of "compressing policy on a single switch" [START_REF] Meiners | Bit Weaving: A Non-prefix Approach to Compressing Packet Classifiers in TCAMs[END_REF] as a post-processing step to further reduce the routing table size.

A. Integer Linear Program

We consider a backbone network as an undirected graph G = (V, E). The nodes in V describe routers and the edges in E present connections between those routers. We denote by D st the demand of traffic flow from node s to node t such that D st ≥ 0, s, t ∈ V, s = t. We assume that the capacity of links and the rule space at routers are constant. The objective is to find a feasible routing for all traffic flows, respecting the capacity and the rule space constraints and being minimal in energy consumption.

We first define the following notations and then formulate the problem as Integer Linear Program:

• D: a set of all traffic demands to be routed.

• D st ∈ D: demand of the traffic flow from s to t.

• C uv : capacity of a link (u, v).

• µ ∈ (0, 1]: maximum link utilization that can be tolerated. It is normally set to a small value, e.g. µ = 0.5.

• C u : maximum number of rules can be installed at router u.

• N (u): the set of neighbors of u in the graph G.

• x uv : binary variable to indicate if the link (u, v) is active or not.

• f st uv : a flow (s, t) that is routed on the link (u, v) by a distinct rule. We call f st uv as normal flow.

f st vu + g st vu -g st uv -f st uv =    -1 if u = s, 1 if u = t, 0 else ∀u ∈ V, (s, t) ∈ D (2) f st uv + f st vu + g st uv + g st vu ≤ 1 ∀(u, v) ∈ E, (s, t) ∈ D (3) (s,t)∈D D st (f st uv + f st vu + g st uv + g st vu ) ≤ µC uv x uv ∀(u, v) ∈ E (4) (s,t)∈D v∈N (u) f st uv ≤ C u -1 ∀u ∈ V (5) v∈N (u) k uv ≤ 1 ∀u ∈ V (6) g st uv ≤ k uv ∀(u, v) ∈ E, (s, t) ∈ D (7) x uv , f st uv , g st uv , k uv ∈ {0, 1} ∀(u, v) ∈ E, (s, t) ∈ D (8)
The objective function (1) minimizes the power consumption of the active links. The flow conservation constraints [START_REF] Bianzino | A Survey of Green Networking Research[END_REF] express that the total flows entering and leaving a router are equal (except the source and the destination nodes). It is noted that a normal flow entering a router can become a default flow on outgoing link and vice versa. Constraints (3) ensure that a flow (s, t) on a link (u, v) cannot be both normal (f st uv ) and default flow (g st uv ) at the same time. Constraints (4) are capacity constraints. We consider an undirected link capacity model [START_REF] Raack | On Cut-based Inequalities for Capacitated Network Design Polyhedra[END_REF] in which the capacity of a link is shared between the traffic in both directions. This model is not common but it allows to reduce the number of variables without impacting the general idea of our proposal. Constraints (5) denote rule capacity constraints where we reserve one rule at each router to be the default rule. Constraints ( 6) and ( 7) are used to fix only one default port for each router.

B. Heuristic Algorithm

Since energy-aware routing problem is known to be NP-Hard [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF], it is very challenging to find an exact solution. Therefore, we present in this section an efficient greedy heuristic for large networks. In summary, the heuristic algorithm works through two steps:

-Step 1: starting from the whole network, we compute a feasible routing which respects the capacity and the rule space constraints as described in Algorithm 1, 2 and 3. For each router u ∈ V , we keep the two sets F u and G u containing normal and default flows, respectively. At the beginning of the algorithm, we are freely to assign distinct rules for flows (line 10 -Algorithm 1) until the routing table is full (|F u | = C u ). Then, we try to shrink it (line 9 -Algorithm 1) as Fig. 3 by setting the port that carries most of traffic flows as the default port. As a result, the number of installed rules is reduced and there is some more space to install new rules. Ouput: routing solution on graph G. Algorithm 4). The aim of this step is to turn off the low loaded links and to accommodate their traffic on other links in order to reduce the total number of active links.

Fig. 3: Routing table at a router

1 Residual capacity R e = C e ∀e ∈ E; 2 Initially, F u = ∅ and G u = ∅ ∀u ∈ V ; 3 Creating directed graph G ′ = (V, E ′ ) from G where ∀(u, v) ∈ E,
An example of computing link weights (Algorithm 2) is shown in Fig. 4. The link weight is used to perform rulebalancing between routers. Assume that the next demand is (A, D), then the routing solution using shortest path is (A, C, D). It is better than (A, B, D) since node C still has much more available rule space. 1 Create a digraph G ′ = (V, E ′ ) as Fig. 4.

2 for (u, v) in E ′ do 3 compute rule utilization at v: U v = C max × |F v |/C v ;
Algorithm 3: Updating F u and G u Input: An undirected graph G = (V, E), the shortest path P st found in Algorithm 1, the set F u and G u ∀u ∈ P st and the default port of each router d(u) ∀u ∈ P st . Ouput: Updated sets of F u and G u ∀u ∈ V .

1 for u ∈ P st do 2 for v ∈ G.neighbor(u) do 3 if (u, v) ∈ P st and v == d(u) then 4 G u = G u ∪ g st uv 5 else if (u, v) ∈ P st and v = d(u) then 6 F u = F u ∪ f st

IV. SIMULATION RESULTS

We solved the ILP model with IBM CPLEX 12.4 [START_REF] Ilog | [END_REF]. All computations were carried out on a computer equipped with 2.7 Ghz Intel Core i7 and 8 GB RAM. We consider reallife traffic traces collected from SNDlib [START_REF] Orlowski | SNDlib 1.0 -survivable network design library[END_REF]. To compare the optimal and the heuristic solutions, we use a small network as Atlanta network (V = 15, E = 22, |D| = 210). As mentioned in [START_REF] Kang | Optimizing the "One Big Switch" Abstraction in Software-Defined Networks[END_REF] [START_REF] Kanizo | Palette: Distributing Tables in Software-defined Networks[END_REF], the routing table can support from 750 to few thousands of rules. To show that this is a realistic problem, we use three of the largest network topologies in SNDlib: ta2 (Telekom Austria: V = 65, E = 108, |D| = 4160), zib54 (Zuse-Institut Berlin: V = 54, E = 81, |D| = 2862) and germany50 (V = 50, E = 88, |D| = 2450). In our test instances, five traffic matrices (D1 -D5) are used to represent daily traffic pattern (Fig. 5). Since traffic load is low, the traffic matrix obtained from SNDlib is considered as D1. To achieve a network with high link utilization, we scale D1 with a factor of 1.5, 2.0, 2.5 and 3.0, and they form D2 -D5, respectively. Note that we can play with finer granularity traffic matrices by changing these factors.

A. Optimal vs. Heuristic Solutions

Assume that each router on the network has the same rule capacity represented by C u = (p × |D|) where p ∈ (0, 1] and |D| is the total demands. The value of C u is varied as we change the parameter p. Energy savings is computed as the number of links to sleep divided by the total number of links of the network (|E|).

As shown in Table 1 andTable 2, the ILP model can find solution for very limited rule space (p = 5%) while the heuristic algorithm needs p = 16% (if p is less than this value, no feasible solution can be found). Similarly, the heuristic algorithm is able to save less energy when p is small (e.g. p ≤ 16%). However, when the rule space capacity is large enough, e.g. p = 30%, the gaps between the optimal and the heuristic solutions are small. Moreover, the heuristic algorithm is better in computation time. For instance, the ILP model can take up to 9000 (s) to find solution while it is always less than 10 (s) for the heuristic algorithm.

B. Heuristic Solutions for Large Networks 1) Rule allocation at routers:

We assume that all the routers have the same rule space capacity C u = 750 [START_REF] Kanizo | Palette: Distributing Tables in Software-defined Networks[END_REF]. As the EAR approach, we use the heuristic algorithm in [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF] to represent the case where there is no limit of rule space. We run this algorithm on germany50, zib54 and ta2 networks to see if the rule space constraints are violated or not. As shown in Fig. 6a, Fig. 6b and Fig. 6c, most of the cases (except D5 of germany50 network), there are routers that use more than 750 rules in their routing tables. In zib54 network (resp. ta2 network), from 6% to 11% (resp. 11% to 16%) of routers exceed their rule space capacities. In germany50 network, with the D5 traffic matrix, there is no router that uses more than 750 rules. For other traffic matrices, from 2% to 10% of the routers are overloaded in rule space (Fig. 6a). Therefore, the limited rule space is really a problem in real networks. This problem is extremely important since we cannot route traffic as expected. The number of routers overloaded in rule space depends on the traffic matrix. However, an accurate explanation is difficult (e.g. less overloaded routers when traffic load is high) since the algorithm in [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF] does not care at all about the rule capacity. To take a closer look at rule space allocation, we draw cumulative distribution function (CDF) for rule utilization at each router (Fig. 7a, Fig. 7b and Fig. 7c). When a rule space utilization is larger than 100%, it means that the router has used more than 750 rules. Based on Fig. 6a, Fig. 6b and Fig. 6c, we can find the traffic matrices that cause the maximum and the minimum number of routers violating their rule space constraints. We call these traffic matrices as the max-over-rule and the min-over-rule, respectively. For instance, in case of germany50 network, D1 is the max-over-rule and D5 is the min-over-rule. For each network, we draw two CDFs of rule utilization for the max-over-rule and the min-over-rule cases. As shown in Fig. 7a, Fig. 7b and Fig. 7c, the CDF of rule space allocation of the two cases are quite similar. However we can see in the max-over-rule case, more fractions of routers are overloaded. For instance, in Fig. 7b, only 89% of routers are less than 100% rule space utilization in the max-over-rule case (D1), meanwhile it is 94% of routers in the min-over-rule case (D5). In general, the larger the network is, the more rule space is needed at routers. For example, the maximum rule utilization of germany50, zib54 and ta2 networks are 165%, 220% and 310%, respectively.

2) Energy savings: We collect energy savings for each network in three cases: the minimum, the standard and the unlimited rule spaces. In the standard case, each router can install at most 750 rules (C u = 750). To find the minimum rule space, we reduce the value of C u until we get a minimum value of C u for which it is possible to find a feasible solution. The minimum values of C u for germany50, zib54 and ta2 networks are 227, 670 and 695, respectively. The unlimited rule space case is equivalent to the classical EAR model in which we do not consider at all rule space constraints at routers. In general, as shown in Fig. 8a, Fig. 8b and Fig. 8c, the larger the rule space at routers is, the more flexible routing solutions we have and more energy can be saved for the network. The energy savings gap between the standard and the unlimited rule space cases is small. In some traffic matrices, both cases offer the same amount of energy savings. For instance in germany50 network, the standard and unlimited cases offer the same amount of energy savings. It means that if we use a smart rule allocation, it is possible to achieve equivalent energy savings as the classical EAR approach. The maximum energy savings gaps of the standard and the unlimited cases are 3% and 5.6% for zib54 and ta2 networks, respectively. As expected, less energy is saved in the minimum rule space case as we do not have enough installed rules to route traffic in a better way. As shown in Fig. 8a, there is a big gap of the energy savings between the minimum and the standard cases. This can be explained as the difference between the minimum and the standard values of C u in germany50 network is large.

3) Route length: Intuitively, EAR would affect the length of routing flows as we redirect traffic flows to minimize the number of active links. In Fig. 9a, Fig. 9b and Fig. 9c, we evaluate the impact of EAR on routing length with respect to the shortest path routing. For each traffic demand, we collect the length of its routing flow and the corresponding shortest path. We use the notation over-length to denote the difference (in number of hops) between the length of the routing solution and the shortest path. When over-length is equal to 0, it means that the routing solution is exactly the shortest path. As shown in Fig. 9a, Fig. 9b and Fig. 9c, a large fraction of the demands follow their shortest paths. Indeed, in the heuristic algorithm, we use the shortest path to find routing solution. In germany50 and zib54, the maximum number of additional hops for a demand is 3 and 5 hops, respectively. The ta2 network is larger, up to 6 hops can be added to a demand, but it happens only for 1.4% of the demands. However, if latency is important, especially for sensitive delay applications such as voice or video streaming, we can add constraints to limit the route length so that it will not excess a predefined threshold value. To our best knowledge, this is the first work considering rule space constraints of OpenFlow switch in energy-aware routing. We argue that, in addition to capacity constraint, the rule space is also important as it can change the routing solution and affects QoS. Based on simulations with real traffic traces, we show that our smart rule allocation can achieve high energy efficiency for a backbone network while respecting both the capacity and the rule space constraints.

Fig. 1 :

 1 Fig. 1: Example of EAR with and without rule space constraints II. RELATED WORK

Fig. 4 : 1 :

 41 Fig. 4: Example of updating link weight

Algorithm 2 :

 2 Updating link weightInput: An undirected graph G = (V, E), a set of normal flows F u ∀u ∈ V and a maximum value of rule space capacity C max = max(C u ) ∀u ∈ V . Ouput: weight setting on links of G ′ .

4 :

 4 Removing less loaded links Input: An undirected graph G = (V, E), link capacity C e and residual capacity R e ∀e ∈ E. Ouput: routing solution on a set of active links. 1 while edges can be removed do 2 remove the edge e that has not been chosen and has smallest value C e /R e ; 3 compute a feasible routing with the Algorithm 1; 4 if no feasible routing exists, put e back to G; 5 end 6 return the feasible routing if it exists.

Fig. 5 :

 5 Fig. 5: Daily traffic in multi-period

Fig. 6 :Fig. 7 :

 67 Fig. 6: Number of overloaded routers in the three networks with unlimited rule-space algorithm

Fig. 8 :Fig. 9 :

 89 Fig. 8: Energy savings in daily time in the three networks

  • g st uv : a flow (s, t) that is routed on the link (u, v) by a default rule. g st uv is called default flow to distinguish from the normal flow f st uv . • k uv : binary variable to indicate if the default port of the router u is to go to v or not.

	min	x uv	(1)
	(u,v)∈E
	s.t.

v∈N (u)

  while D st ∈ D has no assigned route do 5 find the shortest path P st on G ′ such that R e ≥ D st ∀e ∈ P st ;

	11 end
	12 return the routing (if it exists) assigned for D
	-Step 2: remove in priority links that are less loaded
	(

we add both directions (u, v) and (v, u) to E ′ (Fig.

4

). Initial weight on link w e = 1 ∀e ∈ E ′ ; 4 6 assign the routing P st to the demand D st ; 7 update R e := R e -D st ∀e ∈ P st ; 8 update link weights proportionally to the size |F u | as Algorithm 2; 9 if |F u | == C u , shrink table at u ∀u ∈ P st ; 10 update F u and G u ∀u ∈ P st using Algorithm 3;

TABLE II :

 II Atlanta network (optimal solution)

	Rule capacity (p -%)	energy savings (%)	computation time (s)
	5%	9	2200
	10%	22.7	9000
	20%	22.7	445
	30%	22.7	540
	40%	22.7	300
	100%	22.7	400
	TABLE III: Atlanta network (heuristic solution)
	Rule capacity (p -%)	energy savings (%)	computation time (s)
	16%	4.5	< 10
	20%	13.6	< 10
	30%	18.2	< 10
	40%	18.2	< 10
	100%	18.2	< 10

update w uv = max(U v , 1);