David Guerrero
email: david.guerrero@ifsttar.fr

Laurent Proulhac
email: laurent.proulhac@enpc.fr

Forthcoming in Research in Transportation Business & Management Special Issue "Managing Freight in Urban Areas" FREIGHT FLOWS AND URBAN HIERARCHY

Keywords: freight transport, urban hierarchy, manufacturing, wholesale trade, France

Varying hierarchy of freight flows between urban areas is the focus of this study. The results of a French survey that describes shipments sent by firms are used for understanding freight flows. The survey shows that the pattern of freight flows between urban areas in France is hierarchical, but varies depending upon whether the flows are generated by wholesale trade activities or by manufacturing. The differences are explained by the specific organizational characteristics of each of these two activities. Wholesale trade broadly reflects the traditional spatial organization of service activities, with interlocking areas of influence. The spatial organization of manufacturing flows is more complex, which can be attributed to the regional specialization of activities.

INTRODUCTION

Urban centers are not isolated as they maintain intense relations with their immediate surroundings and with other urban centers. Scholars have long recognized that the classification of an urban center is linked to its position in the network of interurban exchanges. To describe the position of the urban center in the network, researchers often employ the notion of hierarchy, implying that relations between urban centers can be represented by a tree structure, characterized by a rank/size distribution. In some cases, the hierarchy is just a ranking of urban centers based on population distributions [START_REF] Zipf | National unity and disunity: the nation as a bio-social organism[END_REF] while in other cases the criterion is functional differentiation [START_REF] Lyons | World cities, multinational corporations, and urban hierarchy: the case of the United States[END_REF] or integration into global networks (Sassen, 1991). These studies usually rank the most visible and obviously dominant cities at the top: New York, London, and Tokyo in global hierarchies [START_REF] Sassen | Cities in a world economy[END_REF], and London and Paris at the European level (Friedman, 1986[START_REF] Hall | Forces shaping urban Europe[END_REF]. However, the criteria used to empirically situate urban centers within such hierarchies is limited to highly selective features, such as the presence of advanced service producers in those centers for example [START_REF] Beaverstock | A roster of world cities[END_REF], and often do not take into account the basis of urban hierarchies. Studies that integrate the top and bottom of urban hierarchies remain scarce (Rozemblat and Pumain, 1993), and such studies focus only on corporate links between companies.

Among the multiple features that are used to define interurban networks, perhaps the most attention has been devoted to transportation networks [START_REF] Neal | From central places to network bases: A transition in the US urban hierarchy, 1900-2000[END_REF] and the focus is more specifically on passenger flows. Besides a few studies that looked at other means of transport (see for example [START_REF] Green | Community of Interest Areas: Notes on the Hierarchy of Central Places and their Hinterlands[END_REF][START_REF] Godlund | The Function and Growth of Bus Traffic within the sphere of Urban Influence[END_REF] on coach networks), most of these works are focused on air links. In this respect, the pioneering study by [START_REF] Taaffe | The Urban Hierarchy: An Air Passenger Definition[END_REF] on connections between urban areas in the United States demonstrated that air networks were strongly hierarchical at the beginning of commercial aviation (the major centers were New York, Chicago, Los Angeles, and San Francisco). Deregulation and a series of technical changes starting from 1978 radically modified market conditions in the United States [START_REF] Goetz | Air passenger transportation and growth in the US urban system, 1950-1987[END_REF] and across the world [START_REF] Goetz | Air transport globalization, liberalization and sustainability: post-2001 policy dynamics in the United States and Europe[END_REF]. Thus the evolution of aviation has led to significant changes in connectivity and flow patterns, notably through the emergence of hub-and-spokes networks (Ivy, 1990). While the major urban centers keep their dominant position in the air network (i.e., New York, London, Paris, Tokyo), the strategies of airlines dictate the roles and positions of other urban centers that keep shifting considerably (Shaw, 1993, Smith and[START_REF] Smith | World City Networks and Hierarchies, 1977-1997 An Empirical Analysis of Global Air Travel Links[END_REF]. It nonetheless remains true that the vast majority of medium-sized and small urban centers remain at the periphery of the air network despite the advent of low-cost carriers serving secondary airports [START_REF] Dobruszkes | An analysis of European low-cost airlines and their networks[END_REF]. Insofar as these secondary urban centers are at the periphery of or absent from the air network, the aspect of their interurban relationships has been kept out of these studies.

The purpose of this paper is to help fill this void, by integrating higher and lower levels of urban hierarchy. In order to do this, freight flows are analyzed to understand what they highlight on the economic interactions between the urban centers. However, beyond simply deploying a new indicator to analyze interurban relationships, the article seeks to elucidate the roles of urban centers of different sizes in the transport system. The rest of the paper is structured as follows. The next section sets out our hypotheses and outlines the data and methods used. Section 3 analyzes the location of the manufacturing industry and wholesale activities. Section 4 describes the distribution of freight flows between urban centers as it relates to their size. It proposes a macroscopic approach to examine the spatial organization of productive systems. The final section offers some concluding remarks and identifies main research priorities.

METHODOLOGY Data

The analyses are based on the 2004 French national shipper survey ECHO, which threw light on transport practices and their logistical determinants [START_REF] Guilbault | Transport and logistics demand: New inputs from large shipper's surveys in France[END_REF]. Indeed, the survey becomes a useful tool for observing demand by shippers and by physical and organizational transport chains, from the shipper to the end consignee. The survey is mainly focused on business-to-business freight flows. The sample survey in the study consists of 2935 plants, 10,462 shipments, and 9742 complete transport chains. The scope of the survey covers all firms in mainland France, excluding Corsica, with 10 employees or more, operating in wholesale trade, manufacturing (excluding the extractive industries and construction), mail-order sales, agricultural cooperatives, warehousing services, and industrial waste processing centres. Overall, the survey covers approximately 70,000 plants and estimated after-adjustment transport volumes of 985 million metric tons and 738 million shipments [START_REF] Guilbault | Connaissance des chaînes de transport de marchandises et de leurs déterminants logistiques[END_REF].

Moreover, the location of freight activities is identified using the SIRENE database for the year 2004. The survey also contains economic and spatial information on firms, in particular their plant (physical facilities operated by a firm or government department) and their jobs by business sector. Further, it identifies the location of economic activities within the national space and provides a detailed reading of the economic functioning of the flows generated by firms.

The geographical area of observation of interurban flows

This paper takes into account urban area (UA) to determine the organization of freight flows between the different levels of urban hierarchy. Then determining the urban unit of observation is important. The past decades were characterized by spatial deconcentration of activities, i.e., the tendency for jobs and logistics activities to move from urban to suburban areas [START_REF] Dablanc | Atlanta: a mega logistics center in the Piedmont Atlantic Megaregion PAM[END_REF]. The urban sprawl results in an expansion of the urban perimeter in large areas. In this context, the scale of observation must include a wider definition of urban entities. We argue that the urban area is the most adapted scale to analyze interurban freight flows. We adopted the definition of the urban perimeter in this research from the French National Institute of Statistics and Economic Studies (INSEE) definition. The definition is that the urban area is a geographic unit that provides more than 10,000 jobs and includes a suburban unit in which at least 40% of the resident working population works within the central zone or within its catchment area.

Methodological choices

Size classes of urban areas

The shipper survey's fine stratification by firm activity and size means that its traffic data is statistically representative and it can be used for breaking down the activities economically into major production types. However, it should be kept in mind that the sampling plan does not include a regional breakdown or origin-destination analysis. This means that the shipper survey does not segment shipments by different levels of urban areas. In order to overcome this deficiency, the location (urban areas) of the firms' shipping and receiving freight flows were aggregated into several categories (appendix A). They were broken down into five levels by size of the urban area, ensuring that the total weight of each one was comparable in terms of population, jobs, and shipments (table I). The levels are as follows:

1. The Paris urban area 2. 18 large urban areas (with a population between 400,000 and 1.6 million), which include a dozen regional capitals "outside the Paris area" (i.e., Lyon, Marseille, Lille, Nice, Toulouse, Bordeaux, Strasbourg)

3. 58 medium-sized urban areas (population between 100,000 and 399,000) 4. 85 small urban areas (population between 40,000 and 99,000) 5. 189 very small urban areas (population less that 40,000) 6. Rural areas.

Two units of measurement of flows

Shipment and tonnage are the two units of measurement used in the present study. We chose shipment because it provides an enhanced level of observation for reconstituting traffic chains and is a logistical indicator of shipper practices. The tonnage was also considered because it is a classic value used in transportation research.

In our analysis, freight flows were restricted to the two ends of the shipping chain only. In other words, only the urban areas of origin, at the level of the shipping firm, and the urban areas of destination, at the level of the consignee firm, were only considered. Intermediate logistics platforms in urban areas through which these shipments may transit are not included, because we are only concerned with logistics rather than production or consumption. Our results do not take into account the internal flows within urban areas.

Two sectors of activity

To make our findings statistically representative by territory and economics and to overcome the deficiency in the shipper survey's source data, we aggregated the 36 sectors of activity covered in the survey into two sectors: wholesale trade and manufacturing.

The wholesale sector in our study includes wholesale trade in intermediate goods, production, and consumer goods. Warehousing and mail-order sales are also included in wholesale trade.

The manufacturing sector in our classification includes industries that deal with chemicals, specialty chemicals, metallurgy, waste processing, construction, object manufacturing, and the automotive, agri-food, pharmaceutical, etc.. The division of activities into two categories conceals heterogeneity within the categories themselves. In order to avoid misinterpretations caused by this lack of homogeneity, we geographically linked the main components of each of the two categories (manufacturing and wholesale trade). Where geographical linking is not possible, for example between the automotive industry and chemicals within the manufacturing sector, the different geographical distributions have been highlighted (appendix B).

THE LOCATION OF MANUFACTURING AND WHOLESALE TRADE IN FRENCH URBAN AREAS

The geographical location of manufacturing and wholesale trade in France is detailed in this section. It gives a brief overview of the current territorial distribution of the economic activities that generate freight flows in France. At the national level, location issues are well documented in the literature through models and theories [START_REF] Polèse | Economie urbaine et régionale. Introduction à la géographie économique[END_REF]. The location of economic activities is usually chosen depending upon on the location of natural resources, production factors (including labor), transport costs, and markets. In other words, firms make a trade-off between the proximity advantages and scale advantages when choosing the location of economic activity. However, the relative importance of these factors varies from one business sector to another. To illustrate this diversity, we look into where the main components of manufacturing and the wholesale trade at located at different levels of the urban hierarchy. The geographical distribution of the activities is deduced from the number of jobs. In our study, manufacturing activities constitute 81% of the jobs. These activities take place all locations represented by five levels of urban hierarchy described earlier, but are highly concentrated in smaller urban areas: urban areas with a population of less than 100,000 account for 25% of manufacturing jobs whereas they have only 20% of the total population (figure 1). There are a number of factors that can be used to explain the presence of manufacturing activities in urban areas of very different sizes. Sometimes, firms are prepared to pay the costs arising from locating their plants in urban areas so that they can be closer to their markets and suppliers. At times, firms opt for smaller towns to run their operations in view of lower real estate and labor costs [START_REF] Polèse | Economie urbaine et régionale. Introduction à la géographie économique[END_REF]. These corporate choices therefore give rise to a wide variety in manufacturing location strategies. By contrast, wholesale trade activities are highly concentrated in locations higher in urban hierarchy, although their location varies from one specific subsector to another. If wholesale trade in non-food consumer products is considered, it is an essentially metropolitan activity (appendix B) and so the Paris urban area alone accounts for 51% of jobs in this sector. Wholesale trade in production goods is also concentrated in locations at higher level of urban hierarchy as evident by the fact that 60% of workers in this sector work in Paris and in urban areas having a population of more than 400,000. Now it is obvious that the location of wholesale trade activity is very closely linked with population size unlike manufacturing.

Wholesale trade activities are mainly located at the higher levels of urban hierarchy

The hierarchical approach developed here shows the location strategies of firms engaged in wholesale and manufacturing activities, but it is inadequate to explain the location choices adequately because it considers the different levels of hierarchy as homogeneous groups of urban areas. So the analysis should also include a regional analysis of business location.

A typical North-East/South-West manufacturing split, but only affecting small and very small urban areas

In Figure 2, the general profile of activity in urban areas is mapped by measuring the proportion of people working in wholesale trade using the national average as a reference. Simply put, the reverse of this map holds good for the other activity in our research, namely, manufacturing. Many large and medium-sized urban areas present an average profile, particularly the Paris region and eastern France. This makes it obvious that these urban areas, e.g. Lyon, retain a significant proportion of manufacturing jobs, unlike most other urban areas of comparable size. Conversely, other urban areas have a greater concentration of wholesale trade jobs than the national average. For example, Paris alone has 32% of jobs in the wholesale trade sector. Similarly, most of the large urban areas, such as Lille, Marseille, Strasbourg, Bordeaux, Nice and Toulouse, demonstrate a very high degree of specialization in this sector. Figure 2 also shows how medium-sized and small residential urban areas specialize in wholesale trade activities, particularly those on the Mediterranean coast. A majority of tourists, unemployed, and retired people in Languedoc-Roussillon and the French Riviera explains this feature.

Region-wise analysis reveals that wholesale trade is less concentrated in many urban areas in north-east France. This is a trend from French industrial history since the metallurgical, refining, automotive, and chemical industries mostly grew in the north-eastern regions of France in the 19th and 20th centuries. Even now, the trend continues keeping manufacturing activities in medium-sized and small urban areas in those regions. In contrast, manufacturing activities are sparser in the west and south of France, although certain smallurban areas may have local concentrations of manufacturing jobs (agri-food industry, home appliances, etc.).

THE ORGANISATION OF FREIGHT FLOWS BETWEEN THE LEVELS OF HIERARCHY

The hierarchical and/or horizontal interrelations between urban areas according to their sizeclass are explored in this part. We analyze if the jobs and the flows exhibit similar location patterns. The location pattern of economic activities should theoretically be reproduced in the pattern of freight flows by urban areas forming networks of either a horizontal or hierarchical kind.

Flows are globally correlated with jobs

The volumes of goods exchanged between urban areas in France are rather correlated with the number of jobs in those urban areas, with some exceptions (figure 3a). Flows are slightly underrepresented in Paris and the urban areas having a population of more than 400,000. They contribute less to shipments (33%) and tons (28%) and more to jobs (40%). By way of a corollary, this first finding confirms the importance of urban areas at the bottom of the urban hierarchy and of rural areas in structuring the geography of freight flows. In particular, the findings emphasize the structural role of medium-sized urban areas, in terms of both shipments and tonnage, and the rural areas, in tonnage but not in shipments. It also should be added that in these two levels (medium-sized urban areas and rural areas) inbound and outbound shipments are extremely unbalanced (figure 3b). The relationship between flows and jobs vary depending on the direction of flows: inbound and outbound (table II). Only urban areas with a population of 100,000 to 400,000 display a positive balance both on shipments and tonnage. The emission indices, defined as the ratio between the proportion of outbound flows observed and the proportion of jobs, show that small urban areas, Paris, and even more rural areas, generate few shipments (index below 100). Conversely, when weight of goods is used as a measure, rural areas and very small and medium-sized urban areas generate an enormous outbound tonnage (index above 100). An analysis based on the reception indices, defined as the ratio between the proportion of inbound flows and the proportion of jobs, shows that both inbound and outbound shipments and tonnage are massively underrepresented in Paris. And finally, the data show an overrepresentation of tonnage entering rural areas and small urban areas.

These initial findings confirm the importance of the small urban areas in the French productive system (appendix C). It becomes evident that freight flows are not exclusively polarized by the biggest urban areas. The system is not most dominated by Paris and the regional centres, but activities take place at all levels of urban hierarchy, with significant connections to secondary UAs and rural areas.

The hypothesis of the hierarchy now needs to be explored through the origindestination matrix.

A system dominated by vertical flows

Our analysis of the shipments reveals that one in two shipments originate from a higher ranked urban center to a lower ranked urban center and one in three from a lower to a higher ranked urban entity (table III). Given this background, the most intense flows in shipments and tonnage originate from medium-sized urban areas and reach rural areas (downward flows) (figures 4a and 4b). Interurban exchanges between medium-sized urban areas (horizontal flows) and also from these toward large urban areas (upward flows) structure the formation of urban networks. By contrast, rural areas and small and very small urban areas feature only a few exchanges with same-ranked entities, but more with other levels in the hierarchy. The matrix also highlights the extent of the tonnage carried from rural areas to small , medium-sized, and large urban areas. The last finding relates to the relationship between the size of urban areas and flow distance, a hierarchical indicator of the range of interaction between urban areas. The results show that catchment areas of urban centers are proportional to their population size (figure 4c) and this applies only for inbound flows (both shipments and tons). The median distance of inbound shipments varies between 77 km (for rural areas) and 340 km (for large urban areas). Outbound flows follow a different pattern: catchment areas correlate less with the size of the urban area. The median distance of outbound shipments varies between 130 km for medium-sized towns and 311 km for Paris. This overall analysis provides empirical evidence of hierarchical organization of freight flows between urban areas. The hierarchical pattern of flows confirms our main hypothesis. The findings do not throw light on the causes, but only on the consequences in the spatial organization of freight flows. A more detailed approach to flows by type of activity can contribute to a better understanding of the causes of this configuration.

Upward flows dominate in the manufacturing system

Most manufacturing flows are upward in character (figure 5b). The vast majority of flows reach urban centers with a population of more than 100,000: 67% of shipments and 48% of tonnage. This finding leads to the observation that numerous manufacturing flows are from medium-sized to large urban areas and to Paris (figure 5a). Similarly, manufacturing flows originating from rural areas firstly bound to medium-sized towns and secondly to Paris demonstrate the importance of upward manufacturing flows. However, these observations do not discount the existence of horizontal flows between medium-sized towns, and a few downward flows, in particular from medium-sized towns toward rural areas. The shipments generated by manufacturing activities are usually carried over long distances as evident by the fact that 50% of these shipments have their destination beyond 308 km.

Their scope varies proportionally with the size of the urban areas (figure 5c) but only for inbound flows (both shipments and tons). This can be explained by the overall geographic organization of the manufacturing system. Manufacturing activities in small towns and rural areas are often tributary of local inputs of raw materials (i.e., agricultural products). The bulk of the raw materials are often carried over short distances. Conversely, intermediate goods and finished products, mainly meant for larger urban areas, are conveyed over longer distances. Outbound distances are more or less the same for all levels of urban areas (between 265 and 340 km), except Paris (418 km). This can be explained by the fact that manufacturing outputs are all carried over long distances, and the town size is not a factor. Globally, the national catchment areas observed above are the outcome of a strong regional specialization of manufacturing. In contrast with manufacturing, wholesale trade shows a downward hierarchical pattern (figure 6b). More than six in ten shipments are dispatched to a destination town smaller than the originating urban area. Most shipments originate from towns with a population of more than 100,000, in particular medium-sized towns. These send 12% of shipments and 22% of tonnage to rural areas (figure 6a). This means that wholesale trade flows are highly structured by large urban areas. The primary destination in wholesale trade is the rural area, which on its own attracts 30% of shipments and 33% of tonnage, but also, to a lesser degree, the large and medium-sized towns.

In comparison with the national scope of manufacturing catchment areas, wholesale trade areas are rather local in nature (figure 6c). This type of trade activity is organized as most complex of services, mostly localized at the higher levels of urban hierarchy. Wholesale trade activities play an important role in redistributing freight flows, as they facilitate the link between buyers and sellers at the local level [START_REF] Polèse | Economie urbaine et régionale. Introduction à la géographie économique[END_REF]. Therefore, wholesale trade flows tend to occur over relatively short distances: half of the shipments is conveyed over a distance of less than 119 km. Catchment areas are particularly small at the lower levels of urban hierarchy: 50% of their shipments travel less than 70 km. Outbound catchment areas of wholesale trade are proportional to the size of urban areas and reveal the central place structure: wholesale trade in large urban areas tends to be more scarce and complex than in small urban areas. The exceptionally long distances of outbound flows from very small urban areas (299 km) is partly explained by the specific concentration of niche products of wholesale trade at these places (i.e., drinks, forestry products) whose scope is rather national.

CONCLUSION

This paper has provided a novel analysis of the organization of freight flows between French urban areas using original survey as the basis. This research has provided empirical evidence to confirm theoretical assumptions on production systems. The conclusions of this study may be broadly be grouped into the three following topics: (1) the hierarchical nature of interurban freight flows; (2) the interlocking subsystems in wholesale trade; (3) the regional specialization in manufacturing production systems.

Catchment areas of urban areas vary directly with their population size. This relationship has been verified both for shipments and tonnages. Vertical linkages are predominant: more than one in two shipments reach a lower ranked urban center and more than one in three is destined for a higher ranked urban center. Wholesale trade broadly reflects the traditional spatial organization of a market servicing activity, with interlocking areas of influence. Its flows are highly structured by the largest urban area, which redistributes goods to centers at other levels in the urban and rural hierarchy. Catchment areas of wholesale trade are proportional to the size of the urban areas and reveal the central place structure: wholesale trade in large urban areas tends to be more scarce and complex than in small towns. Obviously, not all the subsectors of wholesale trade are equally organized and niches exist (i.e. agricultural products, drinks, mail-order sales), but they are marginal compared to the main wholesale activities (i.e. consumer goods, capital goods, food).

On the one hand, manufacturing is a supply chain servicing activity. In most of sectors, production units are concentrated in just a few local regions. Automotive or industrial equipment manufacturing, for example, is located in the northern part of the country. But fresh-food processing industry is mainly located in north-west France. On the other hand, manufacturing outputs are ubiquitously distributed. This regional specialization of manufacturing leads to a superposition and entanglement of catchment areas that are large overall: 50% of shipments are carried beyond 308 km. Their size is almost the same on every level of urban hierarchy, except Paris. The manufacturing activities in the capital (i.e. pharmaceutical industry, printing) seem to be slightly more national-oriented than those in the rest of the territory. The sourcing distance (inbound flows) varies proportionally with the size of urban areas, both for shipments and tonnages. Manufacturing activities located in rural areas and little towns often act as a tributary of local inputs of raw materials (i.e., agricultural products), which are generally carried over short distances. Manufacturing activities located in medium and large urban areas do not feature local inputs of materials, and sourcing distances therefore tend to be longer. The downward-oriented flows of wholesale trade can be explained as a function of interface between global and regional sourcing entering a national economy through its gateways. This distribution hierarchy reflects the national urban system since the largest markets get priority in the distribution system. Moreover, it should be highlighted that many of the outputs of manufacturing are inputs for wholesale trade. The majority of manufacturing flows involve parts and semi-finished goods that are not distributed to the market but to other manufacturing units, or to large purchasers who then coordinate the distribution of these goods. The exception could be certain fresh food products (i.e. dairy), which, in their final form (ready for consumption), have a market-based distribution structure, similar to wholesale trade.

The year of observation considered for our analysis is 2004. Since then, the relocation of European manufacturing to developing countries has probably contributed to a shift in freight flows from manufacturing to wholesale trade and longer distances. The reorganization of French and European distribution centres (Hesse, 2006, Raimbault and[START_REF] Raimbault | Quelles places pour l'économie des biens matériels dans les espaces métropolitains? L'exemple des territoires logistiques du Bassin parisien[END_REF] and the development of e-commerce [START_REF] Weltevreden | Internet strategies and performance of Dutch retailers[END_REF] could have modified the pattern of wholesale trade flows. At the time of writing this paper, it was still too early to fully assess the consequences of the financial crisis of 2008 on the hierarchy of freight flows. Reconfigurations in road transport market already have led to a decrease of freight volumes and a transformation of distribution networks. The resulting cargo consolidation could mean that larger urban areas and their evolved transport systems are placed in a better position than small and medium-sized urban centers. It is however not entirely clear at this point to what extent these changes will affect the hierarchy of freight flows and might lead to a paradigm shift.

  Figure 1 -Cumulative percentages of jobs in wholesale trade and in manufacturing within urban areas

Figure 2 -

 2 Figure 2 -Presence of wholesale trade activities in urban areas. Source INSEE, SIRENE (2004)

Figure 3 -

 3 Figure 3 -(a) Share of each class size in jobs, shipments and tons. (b) Number of inbound and outbound shipments by size class. Source: ECHO, IFSTTAR (2004), SIRENE, INSEE (2004)

Figure 4 .

 4 Figure 4. -Diagram of freight flows between urban areas, aggregated by size class. Source: ECHO, IFSTTAR(2004)

Figure 5 -

 5 Figure 5 -Diagram of manufacturing flows between urban areas, aggregated by size class. Source: ECHO, IFSTTAR (2004)

Table III -

 III Organisation of freight flows between UAs

Source:

ECHO, IFSTTAR (2004)

ACKNOWLEDGEMENTS

This research has benefitted from financial support of the French Ministry of Transport in the framework of the research project ECHO TMV: "Contribution of the 2004 shipper survey to city freight issues", coordinated by Michèle Guilbault (University Paris Est, IFSTTAR, SPLOTT). The authors would like to thank the reviewers for their comments that helped in the improvement of the manuscript.


A Boudelier
email: aude.boudelier@ensam.eu

M Ritou

S Garnier

B Furet

Investigation of CFRP machining with diamond abrasive cutters

Keywords: Machining, diamond abrasive cutter, CFRP, laminate, trimming, force Usinage, fraise à concrétion diamantée, CFRP, laminé, détourage, effort

ABSTRACT. Diamond abrasive cutters are more and more used for industrial applications of CFRP laminate machining, due to their resistance to abrasion and low cost. The objective of the approach is to improve productivity during trimming operations, by choosing adapted tools and cutting parameters. The objective of this article is to determine to what extent feedrate and spindle speed can be increased. To do so, specific cutting energy (Esp) and cutting forces are studied. Designs of Experiments and ANOVA are performed in order to analyze the influence of tool (grit size, level of nickel and diameter) and process (feed per revolution and cutting speed) parameters. It shows that high cutting speed is favourable to the cut due to thermal effects. Conversely, the study of specific cutting energy reveals that the feed increase is limited by diamond grit size and level of nickel due to the saturation of the tool intergrit space. RESUME. Les fraises à concrétions diamantées sont de plus en plus utilisées industriellement pour le détourage de composites, CFRP laminés notamment, en raison de leur résistance à l'abrasion et de leur faible coût. L'objectif des travaux est d'améliorer la productivité en optimisant le choix des paramètres opératoires. Il s'agira donc déterminer dans quelle mesure l'avance et la vitesse de rotation de la broche peuvent être accrues. Pour cela, l'énergie spécifique de coupe (Esp) et les efforts de coupe sont étudiés. Des plans d'expériences et ANOVA ont été effectués afin d'analyser l'influence des paramètres de l'outil (granulométrie, niveau de sertissage et diamètre) et du procédé (avance et vitesse de coupe). Il est montré que des vitesses de coupe élevées sont favorables à la coupe, grâce aux effets thermiques. Par contre, l'étude de l'énergie spécifique de coupe a révélé que l'avance est limitée par la granulométrie et le niveau de sertissage, à cause d'une saturation du volume libre inter-granulaire de l'outil.

Extended abstract:

Diamond abrasive cutters are more and more used for industrial applications of CFRP laminate machining, due to their resistance to abrasion and low cost. The objective of the approach is to improve productivity during trimming operations, by choosing adapted tools and cutting parameters. The objective of this article is to determine to what extent feedrate and spindle speed can be increased. To do so, specific cutting energy and cutting forces are studied. Design of Experiments and ANOVA are performed in order to analyze the influence of tool (grit size, level of nickel and diameter) and process (feed per revolution and cutting speed) parameters.

It shows that high cutting speed is favourable to the cut due to thermal effects. Indeed, complementary measures with thermal camera have revealed an increase of cutting temperature with spindle speed. Besides, Kinemat test have shown that the mechanical properties of carbon-epoxy laminate decrease with temperature. They drop after the glass transition temperature, but it is not reached during the cut at high spindle speed. Thus, the maximum spindle speed should be used.

The study of specific cutting energy has revealed that the increase of feed is limited by a saturation of the tool intergrit space with CFRP chips. In order to avoid the phenomenon, feed values should be lower than a given threshold. It limits productivity. The threshold is higher with larger diamond grit size and lower level of nickel.

It was also found that, under identical feed and cutting speed, the influence of tool diameter on specific cutting energy and force is negligible. In order to analyse it, tools were scanned, the tool numerical model rebuilt and the process simulated. It revealed that, in spite of the random grit distribution around the tool, the average chip thickness removed by grits on a given level of the tool is similar whatever the diameter, which is not intuitive. It explains why specific cutting energy and force are not affected by tool diameter. Besides, the same analysis explains why the influence of grit size on specific cutting energy and force is negligible, which is not intuitive too.

Introduction

Manufacturing processes of composite materials leads to finishing operations, like drilling and trimming, so as to eliminate excess of material from polymerized parts. It is necessary in order to achieve dimensional tolerances and surface quality requirements. However, the machining of composite laminates is difficult because of their mechanical and thermal properties: heterogeneity, anisotropy and low thermal conductivity [START_REF] Teti | Machining of Composite Materials[END_REF]. Moreover, their high abrasiveness, which is mentioned by [START_REF] Latha | Analysis of Thrust Force in Drilling Glass Fiber-Reinforced Plastic Composites Using Fuzzy Logic[END_REF] for drilling and [START_REF] Furet | Milling and drilling of composite materials for the aeronautics:feature aeronautics[END_REF] for milling, causes excessive tool wear. [START_REF] Davim | Damage and dimensional precision on milling carbon fiber-reinforced plastics using design experiments[END_REF] studied the milling of CFRP with carbide tools and obtained good surface roughness. But they have a short tool life, especially in CFRP (Carbon Fibre Reinforced Polymer) due to its abrasiveness [START_REF] Teti | Machining of Composite Materials[END_REF]. During their study on orthogonal cutting, [START_REF] Wang | Orthogonal Cutting Characteristics of Graphite/Epoxy Composite Materials[END_REF] proposed PCD (Poly Crystalline Diamond) endmill as an alternative. Higher feedrate can be used and higher product quality is obtained. However, the costs are significant and they are very brittle, as highlighted by [START_REF] Sheikh-Ahmad | Machining of Polymer Composites[END_REF]. That is why new tools, such as diamond abrasive cutters and discs, have been specifically developed for CFRP trimming operations. This tool technology, which is constituted of diamond grits, improves tool life and productivity as well as reduces costs. For example, a PCD tool can trim 10 meters of CFRP before being worn, whereas a diamond tool can machine more than 300 meters. Many works have been carried out with metal-bonded diamond tool. However, they mainly concern finishing operations using diamond grinding wheels in metal [START_REF] Teicher | Performance of Diamond and CBN Single-Layered Grinding Wheels in Grinding Titanium[END_REF], metal matrix composite (Anad et al., 2009) or ceramic matrix composite applications [START_REF] Li | Wear of diamond grinding wheels and material removal rate of silicon nitrides under different machining conditions[END_REF] [START_REF] Tawakoli | Intermittent grinding of ceramic matrix composites (CMCs) utilizing a developed segmented wheel[END_REF]. There is a lack of research concerning the performance of diamond abrasive cutters during trimming operations. Only (Colligan et al., 1999) performed experiments with similar geometry of diamond abrasive cutters in composite material. They essentially characterized quality of trimmed surfaces, which is correlated to the tool grit size.

The paper presents an investigation of CFRP machining with diamond abrasive cutters. The objective is to determine to what extent feedrate and cutting speed can be increased, in order to optimize productivity. For this reason, specific cutting energy (Esp) and cutting forces are analyzed in order to identify possible limiting phenomena. The influence of five parameters is studied: feed per revolution, cutting speed, diamond grit size, level of nickel and tool diameter. Experiments have been performed and analysed by ANOVA. Limiting phenomena are researched and lead to practical recommendations for the optimization of productivity, through the optimal choice of process parameters.

Experimental procedure

Set-up

A 9.1 mm thick laminate of T800-M21 (Hexcel) was used to carry out the experiments. The laminate was composed of 35 plies of unidirectional graphite fibre fabric (0.26 mm thick). The matrix was a thermosetting epoxy resin M21. Lay-up sequence was (0/-45/90/90/45/90/90/45/0/-45/90/90/ 90/45/90/-45/90/-45/90)2s.

Trimming tests were carried out on a three-axis Huron KX30 milling machine, equipped with a 28000 RPM -40 kW Kessler spindle. External and internal waterbased coolant was used. The depth of cut corresponded to the part thickness and the width of cut to the tool diameter, as usual in rough trimming. Feedrate direction corresponded to the 0° external ply. Figure 1 presents the experimental set-up.

During cutting tests, the spindle power consumption was measured with a DigitalWay device. The specific cutting energy Esp (W/cm3/min) was deduced from the average power values, by dividing by the material removal rate (product of width of cut, depth of cut and feedrate) once the power corresponding to idle rotation subtracted. Note that it is homogenous to a pressure but those are the usual name and unit. Cutting forces were also measured with a Kistler dynamometer table. Contrary to endmills, diamond abrasive cutters lead to constant cutting forces during cuts. So, for each run, average values of feed force Ff and normal force Fn were evaluated. Then, the cutting forces resultant F was obtained and analysed.

Diamond abrasive cutters

The diamond abrasive cutters used during the experiments were composed of natural diamond grits, fixed with a nickel bond on a cylindrical body by electro deposition. Several parameters characterize the tools. Grit size is the most important Ff Fn Feedrate Dynamometer 9.1 mm thick CFRP laminate one. Different grit sizes G are proposed by manufacturers, from very small ones used in grinding applications, to large ones used in the present cutting application. However, limits results from the tool manufacturing process, depending on tool diameter ∅. Indeed, deposing large grits on a small diameter is difficult. Another parameter describing diamond cutter is the level of nickel, noted Ln, which is defined as the ratio nickel height to grit size (expressed in %). The larger the level of nickel is, the deeper the grits are in the bond.

Control factors

The aim of the study is to determine relevant process parameters for CFRP trimming operations with diamond abrasive cutter. Factors that might limit productivity must be identified. Two categories of parameters were investigated: tool parameters and cutting conditions.

Cutting conditions were studied through the feed per revolution and the cutting speed. Several diamond abrasive cutters were used. Four diamond abrasive grit sizes were studied: 427, 602, 852 and 1182 µm. Tools diameter influence was also considered through three levels: 12, 16 and 25 mm. Moreover, two different levels of nickel were tested: bond matrix covered 50% of the diamond grits, excepted for tool 9 with 65% (Table 1).

An approach with experimental design has been carried out to analyze the influence of tool and process parameters on the cut. Different Designs of Experiments (DoE) were constructed in order to reduce the number of cutting tests. Moreover, technical constrains resulting from the tool manufacturing process and from dangerous sets of cutting conditions were take into account. Consequently, the tests were divided into three designs of experiments that are presented in Table 2. In order to determine the effects and interactions significances of the parameters, analyses of variance (ANOVA) were carried out for the whole DoEs. A 95% confidence level was applied to all dependent variables. ANOVA tables can be found in annex 1 and the results are presented and discussed in the following section.

Results and discussion

Influence of cutting speed

The effect of cutting speed on specific cutting energy and force is low, as illustrated in Figure 2. The thermal effects in the CFRP laminate can explain the low decrease. Indeed, complementary tests with thermal camera indicated that the local temperature of trimmed surface increases with cutting speed (Figures 3a and3b). Besides, tests were performed on a Kinemat device in order to observe the mechanical properties evolution during a temperature increase. The torque necessary to impose a given angular deformation on a strip specimen of the CFRP laminate is measured during the temperature increase (blue curve on Figure 3c). It was observed that, before reaching the glass transition temperature (identified at Tg = 240°C) where they collapsed, mechanical properties slowly decrease of 15% between 40 and 210°C. Thus, chip removal becomes easier at higher temperature. Therefore, the low decrease of specific cutting energy and forces during trimming (Figure 2) can be explained by the CFRP thermal behaviour. However, during our cutting tests, Tg was not reached because no severe decrease of specific cutting energy was observed. Consequently, the material integrity was not affected. It can be concluded from the experiments that the highest cutting speed, i.e. maximum spindle speed, is recommended, since it improves productivity.

Influence of grit size and feed per revolution

Firstly, it can be noticed on Figure 4b that the cutting force levels are very close, whatever the tool grit size; when identical feeds are considered. It can be explained by the fact that the chip thickness removed by a given grit is almost the same whatever the grit size. It was proven by tool scanning and process simulation with the real tool geometry, for each tool with a different grit size. Computations are explained in section 3.4. Figure 4a presents the evolutions of specific cutting energy in relation to feed and grit size. It can be noticed that three domains appear. Particular phenomena are revealed at low and high feed by the increases of specific cutting energy. They are explained in the following sections. Between them, a central domain leads to adequate cutting conditions for the diamond abrasive cutter. A low decrease can be noticed on this domain that suggests the use of high feeds, while avoiding the high feed phenomenon. Levels of feed force Ff and normal force Fn are interesting (Figure 4b). Indeed, during classical metal machining with endmill, Fn tends to be higher than Ff. On the Ff Fn contrary, during machining using diamond abrasive cutters, normal forces are 40% less than feed force. It is due to higher negative rake angles on grits.

Cutting phenomenon at low feed

The presence of a limiting phenomenon at low feed per revolution can be clearly identified in Figure 4a. Indeed, the specific cutting energy significantly increases when feed per revolution is smaller than a given threshold; its value depends on grit size. When grit size is larger, the threshold value is higher. Figure 4a shows that 602 µm and 852 µm grit sizes reached this critical threshold. Lower feed per revolution should have been used to observe a similar phenomenon in the other tools.

When the feedrate is low, the chip thickness is small. Consequently, specific cutting energy that is necessary to remove material rises. [START_REF] Mondelin | Characterisation of friction properties between a laminated carbon fibres reinforced polymer and a monocrystalline diamond under dry or lubricated conditions[END_REF] have also noted this phenomenon during scratching tests on the same material, due to higher proportion of friction between the grit cutting face and the workpiece.

Cutting limit at high feed

The presence of a second limiting phenomenon can be observed in Figures 4a and4b concerning 427 µm and 852 µm grit sizes. When feed per revolution reaches a critical threshold, respectively 0.16 mm/rev and 0.36 mm/rev for grit size of 427 µm and 852 µm, specific cutting energy quickly increases. The tools then saturate, depending on their grit size. In the case of the tools with 602 µm and 1182 µm grit sizes, the critical threshold was not reached due to the use of insufficient feeds.

The loading of the diamond abrasive cutter can explain this rise of specific cutting energy. [START_REF] Ghosh | Modelling of specific energy requirement during high-efficiency deep grinding[END_REF] documented the same phenomenon for metal grinding using wheels. During the machining with diamond abrasive cutters, chips are accumulated in the intergrit space, until the grits exits from material with tool rotation. The chips are composed of small CFRP aggregates. If the feed per revolution is too high, the chips do not have enough space to lodge between grits before being evacuated. The cutting mechanism is deteriorated and specific cutting energy increases along with forces. If the feed per revolution then decreases, the chip flow decreases and can be evacuated normally.

Figure 4a also reveals that the chip removal limit is reached sooner with a small grit size. Indeed, when grit size is smaller, the intergrit space is lower due to higher grit density. Thus, the feed critical threshold is lower for a smaller grit size. To avoid tool saturation, the feed per revolution must be chosen in relation to grit size and especially the intergrit space. Considering our experimental results, the maximum feed per revolution can be set at about 50% to 60% of grit size. So, tool grit size is an important parameter for optimizing productivity.

Influence of level of nickel and feed per revolution

When low feed per revolution is used, specific cutting energy and forces have similar levels, whatever the level of nickel (Figure 5). However, saturation is reached earlier with a higher level of nickel at a high feed, as shown by the deviations of forces and specific energy values at 0.5 mm feed. In fact, when the level of nickel is greater, the intergrit space is smaller. Therefore, a diamond abrasive cutter with a higher level of nickel is saturated before a cutter with a lower level of nickel. Thus, a low level of nickel is recommended in order to improve productivity. Nevertheless, it must be large enough to hold the grits in spite of cutting forces. This requires a compromise between the mechanical strength of the tool and its productivity. The limits concerning the tool manufacturing process must also be taken into account. It results that an average value of 50% is suitable.

Influence of tool diameter and feed per revolution

The results presented in Figure 6 should be considered with identical cutting speeds. Indeed, the effect of cutting speed presented in section 3.1 must be removed to avoid misinterpretations. Then, the influence of tool diameter can hence be studied. Low deviations can be observed in Figure 6a. The larger the diameter is, the higher the specific cutting energy is. In Figure 6b, the cutting force levels are very close whatever the tool diameter, under identical feedrate. It can be explained by the chip thicknesses removed by grits. In order to discuss this hypothesis, a specific device has been developed for tool scanning. It leads to the real tool geometry (Figure 7a). Then, the tool is discretized into horizontal slices and the cutting process is simulated in relation to the feed per revolution. Grits that participate to the cut are identified and their associated chip thickness hc is evaluated (Figure 7b). In this way, the mean chip thickness can be calculated. Figure 7c presents the results for different tool diameters. Counterintuitively, it shows that the mean chip thickness varies few in relation to tool diameters. Consequently, it explains why specific cutting energy and cutting force values are similar. Finally, it results from the low effect of tool diameter that small diameters are recommended in order to reduce width of cut and spindle power. Limits exist due the tool strength and to the tool manufacturing process. Indeed, it is difficult to set large grits on a small diameter. Thus, there is a minimum tool diameter on which a given grit size can be fixed correctly.

Conclusion

The paper investigates the CFRP machining with diamond abrasive cutters. The aim is to maximize productivity, through the increase of feedrate and cutting speed.

The effects and interactions of tool grit size, level of nickel, tool diameter, feed per revolution and cutting speed were studied by analysing the cutting forces and the specific cutting energy (issued from spindle power).

Limiting cutting phenomena were revealed, at low and high feeds. The latter is of major interest. Saturation of the diamond abrasive cutter occurs when too high feedrate is used, beyond a given threshold. An aggregate of CFRP chips saturates the tool intergrit space. This threshold is a limit to productivity. The use of large grit size and low level of nickel increases the value of the threshold. Indeed, intergrit space is more important and tool saturation occurs at higher feedrate. Besides, it was found that tool diameter and cutting speed have low effects on cutting force and specific energy. Thus, small diameter should be favoured and the highest cutting speed is recommended. The latter improves the cut due to thermal effects; but the material integrity is respected, since the glass transition temperature Tg is not reached during the cut.

Annex A:

a -DoE1

Figure 1 .

 1 Figure 1. Experimental set-up.

Figure 2 .Figure 3 .

 23 Figure 2. Effect of cutting speed on specific cutting energy (a) and forces (b).

Figure 4 .

 4 Figure 4. Influence of feed per revolution and grits size on (a) specific cutting energy and (b) forces.

Figure 5 .

 5 Figure 5. Influence of level of nickel on (a) specific cutting energy and (b) Forces.

Figure 6 .

 6 Figure 6. Influence of tool diameter on (a) specific cutting energy and (b) forces, in relation to feed per revolution and cutting speed.

Figure 7 .

 7 Figure 7. Simulation of cutting process (b) from the scanned tool geometry (a) and analysis of the mean chip thickness in relation to feedrate and tool diameter (c).

Table 1 .

 1 Table 1 presents the nine tools that were used during the experiments. Presentation of the diamond abrasive cutters.

	N°	Ø (mm)	Grits size (µm)	Level of nickel (%)
	1	16	427	50
	2	16	602	50
	3	16	852	50
	4	16	852	50
	5	16	1182	50
	6	25	852	50
	7	12	852	50
	8	16	852	50
	9	16	852	65

Table 2 .

 2 Experimental parameters.

	N° DoE	Symbols	Machining parameters	Units	Level 1	Level 2	Level 3	Level 4
	1	f1	Feed per revolution	mm/rev	0.1	0.23	0.36	0.5
		ø1	Diameter	mm	12	16
		V1	Cutting speed	m/min	400	600	800	1000
	2	f2	Feed per revolution	mm/rev	0.03	0.1	0.16	0.23
		G2	Abrasive grits size	µm	427	602
		V2	Cutting speed	m/min	1000	1400
	3	f3	Feed per revolution	mm/rev	0.1	0.23	0.36	0.5
		G3	Abrasive grits size	µm	852	1182
		V3	Cutting speed	m/min	1000	1400

Journal of Composite and Advanced Materials. Volume 23 -n° 3/2013

Journal of Composite and Advanced Materials. Volume 23 -n° 3/2013

Journal of Composite and Advanced Materials. Volume 23 -n° 3/2013

Acknowledgments

Authors thank Synervia for its contribution, Asahi Diamond and AOB for the development of specific diamond abrasive cutters. This work was carried out within the context of the working group Manufacturing'21 which gathers 16 French research laboratories. The topics approached are: modelling of the manufacturing process, virtual machining, and emergence of new manufacturing methods.


Fen Zhou
email: fen.zhou@univ-avignon.fr

Jiayi Liu

Gwendal Simon

Raouf Boutaba
email: rboutaba@uwaterloo.ca

D Cheriton

Joint Optimization for the Delivery of Multiple Video Channels in Telco-CDN

Keywords: Delivery Networks (CDN), Video Delivery, Joint Optimization, Heuristic Algorithms

A Telco-CDN can be regarded as an intra-domain overlay network with tight resources and critical deployment constraints. This paper addresses two problems in this context:

(1) the construction of the overlays used to deliver the video channels from the entrypoints of the Telco-CDN to the appropriate edge servers; and (2) the allocation of the required resources to these overlays. Our ultimate goal is to maximize the number of delivered channels while preserving network resources. Two classes of heuristic algorithms, namely two-step optimization and joint-optimization, are proposed to solve these problems. The conducted evaluations confirm the efficiency of the jointoptimization approach.

I. INTRODUCTION

It has become clear over the past couple of years that Internet Service Providers (ISP) have to deploy a Content Delivery Network (CDN) within their network infrastructure in order to cope with the sharp increase of video traffic. The recent OpenConnect [START_REF]Netflix Open Connect Content Delivery Network[END_REF] proposal from Netflix illustrates this major shift: content providers now develop peering agreements with ISPs, and rely on co-controlled delivery platforms to serve end-users. As a matter of fact, the management of video streams in Telco-CDNs has become a critical topic for both network operators and content providers.

Telco-CDNs differ from traditional CDNs on several aspects. First, Telco-CDNs can be fully controlled, since they own the network and the entire "last mile" from edge servers to end users. This enables to engineer Telco-CDNs through centralized optimization techniques so that the Quality of Service (QoS) can be guaranteed. Second, a Telco-CDN matches the topology of an underlying network. Consider the case of a French network operator (see Fig. 1). The "entrypoints" for the content providers are the Internet Exchange Points (IXP) where peering occurs (here the rectangular nodes). As far as we know, edge servers in Telco-CDN are deployed near the routers that connect the ISP backbone core network to the metropolitan access networks of the different regions (the circular nodes). Thus each edge server is in charge of a regional area. However, the congestion of the core network is a serious concern for network operators, so content delivery within the Telco-CDN -between entrypoints and edge servers -is an essential operational and management concern. A key challenge for Telco-CDNs is the management of the traffic generated by live video channels from Over-The-Top (OTT) video services. OTT content providers include usergenerated video platforms like justin.tv or ustream, and also second-screen video services affiliated with traditional TV broadcasters. Traffic related to these services is exploding. Moreover, the adoption of rate-adaptive streaming technologies (e.g. DASH) negatively affects the CDN infrastructure because the bit-rate of a video channel corresponds to the accumulated rate of all the video representations, which is frequently greater than 20 Mbps [START_REF] Adhikari | Unreeling netflix: Understanding and improving multi-CDN movie delivery[END_REF].

As it has been shown in many previous works [START_REF] Adler | Algorithms for optimizing the bandwidth cost of content delivery[END_REF]- [START_REF] Thomos | Network coding of rateless video in streaming overlays[END_REF], the delivery of a live channel stream over a CDN can benefit from constructing an overlay. Edge servers contribute to the delivery of flows within the CDN using spare upload capacities. Several techniques have been developed for the construction of an overlay for one live channel over CDNs. In particular, multi-tree overlays that leverage rateless codes (e.g., Raptor codes [START_REF] Shokrollahi | Raptor codes[END_REF]) enable video stream delivery with optimal bandwidth utilization [START_REF] Thomos | Network coding of rateless video in streaming overlays[END_REF][START_REF] Wu | rstream: Resilient and optimal peer-to-peer streaming with rateless codes[END_REF][START_REF] Zhou | Minimizing Server Throughput for Low-Delay Live Streaming in Content Delivery Networks[END_REF]. This solution however performs well for one channel while the traffic that a CDN should carry for a platform like justin.tv consists of a large number of simultaneous channels. Typically, agreements between justin.tv and CDN stipulate the delivery of around fifty channels -the so-called "featured" channels.

In this paper, we study the problem of delivering multiple channels over a Telco-CDN. Our goal is to maximize the number of channels that are delivered to the edge servers, given that the Telco-CDN is constrained by the capacity of the edge servers. This optimization problem involves two distinct subproblems: the construction of one overlay per channel, and the allocation of resources among the competing overlays. To tackle this problem, we envision two approaches:

• Two-Step optimization-First, we construct all overlays, then we allocate the bandwidth among the different overlays so that the most important channels are delivered, until resource exhaustion. • Joint optimization-We jointly construct the overlays and reserve the required resources on the fly. This approach leads to better solutions. The contribution of this paper is two-fold. First, it provides a step into the study of joint optimization problems for the provisioning of multiple overlays. Joint optimization approach achieve better performance at the cost of more intensive computations. Our study provides a comprehensive evaluation of this trade-off. Second, this paper introduces some key management needs for scarce resources in Telco-CDNs.

II. RELATED WORK

Optimization problems related to the construction of tree overlays have been widely studied in the context of IP multicast [START_REF] Takahashi | An approximate solution for the steiner problem in graphs[END_REF]- [START_REF] Oliveira | Optimization Problems in Multicast Tree Construction[END_REF]. Researchers have identified two main ways to build a multicast tree. The first one consists in building a Steiner tree using the heuristic algorithm given in [START_REF] Kou | A fast algorithm for steiner trees[END_REF]. The second one, namely Minimum Path heuristic algorithm [START_REF] Takahashi | An approximate solution for the steiner problem in graphs[END_REF], tries to construct a cost-optimal tree. In this paper, we use a more contemporary video delivery technique based on rateless codes [START_REF] Shokrollahi | Raptor codes[END_REF], where each delivery is ensured by multiple trees.

The use of rateless coding in content delivery overlays was introduced in [START_REF] Wu | rstream: Resilient and optimal peer-to-peer streaming with rateless codes[END_REF]. Its key advantages include: (i) rateless codes have very low computational cost; (ii) they minimize delivery redundancy when a server receives data concurrently from multiple other servers; and (iii) they are adaptive to varying channel conditions since the encoder can generate on the fly as many encoded symbols as needed. Following this seminal work, several performance improvements were proposed in the literature. End-to-end delivery delay is reduced by the method described in [START_REF] Grangetto | Rateless codes network coding for simple and efficient p2p video streaming[END_REF]. Shorter start-up delay and more stable service are among the objectives addressed in [START_REF] Oh | An effective mesh-pull-based p2p video streaming system using fountain codes with variable symbol sizes[END_REF]. Previous works consider the delivery in only one overlay. The objective of this paper is different since it aims at constructing several rateless coding based overlays while addressing the critical problem of bandwidth reservation for these overlays. Our approach does not require any specific overlay construction method, hence any of the existing overlay tree construction algorithms can be used in conjunction with our approach.

III. SYSTEM MODEL

The Telco-CDN network is modeled as a connected symmetric digraph G(V, E). See an example in Fig. 1. The set V (|V | = n) contains the edge servers (here the access points to the regional areas) and a set of entrypoints S ⊆ V , which are located near the peering points (here the three main French peering IXPs). A content provider usually delivers its most popular channels to a given ISP through only one peering point. But a Telco-CDN serves several content providers, so the set of channels I comes from several entrypoints. Each entrypoint s is associated with the set of channels I(s) ⊆ I that it actually receives. The sets I(s) for all s ∈ S form a partition of I. Each channel i ∈ I is associated with two key parameters. First, the targets are the set of edge servers that must receive the channel i. This subset of edge servers is denoted V i ⊆ V \ S. Second, the importance of channel i, denoted by f i , sets the priority to the delivery of channels. The channel importance is generally related to the popularity of the content in the area. The monitoring of the CDN and the algorithms that allow to set both parameters are out of the scope of this paper. For major services, the content provider provides these parameters to the CDN provider.

We leverage previous works on multi-tree (forest) overlay networks based on rateless codes [START_REF] Thomos | Network coding of rateless video in streaming overlays[END_REF][START_REF] Zhou | Minimizing Server Throughput for Low-Delay Live Streaming in Content Delivery Networks[END_REF]. Each edge server v reserves some upload capacity c v to assist the entrypoints. To simplify, we assume there exists a unit of stream, and we express upload capacities as the number of units that the server can transmit over a period of time. The system introduced in [START_REF] Zhou | Minimizing Server Throughput for Low-Delay Live Streaming in Content Delivery Networks[END_REF] suggests to build, for each channel i, a forest overlay F i where each overlay tree supports one unit of encoded video stream. An edge server can re-build the stream if it is spanned in at least K trees.

Studied Optimization Problem

The objective is twofold: to deliver the maximum number of channels (with regard to their importance) and to reduce the traffic load on the CDN infrastructure, i.e., to reduce the number of edge servers that are involved in the delivery of a channel if they are not a target for this channel. The former objective prevails over the latter. Therefore we formulate the optimization problem as first to deliver the maximum number of channels, then to find the delivery scheme that imposes the least traffic load on the network. Let R i be a binary variable equal to one if the channel i is delivered to all edge servers in V i , and zero otherwise. Our first objective is to maximize i∈I f i × R i , and our second objective is to minimize the number of overlay links that are used to deliver the channels to the edge servers. In our rateless code based multiple-channel video streaming system, three main constraints are considered:

• Edge servers capacity constraint. The contribution of edge servers to stream delivery should not overcome their capacities. Let deg + T (v) be the out degree of node v in a tree T . Clearly the sum of its out-degree in the trees of all the overlays it is involved in cannot be greater than its capacity:

i∈I T ∈Fi deg + T (v) ≤ c v , ∀v ∈ V (1)
• Video content constraint related to rateless codes. Each edge server subscribing to channel i should be spanned in at least K trees in the forest F i dedicated to channel i, so that the edge server is able to receive K units of stream and decode the video. Let F i (v) be the set of trees in which the edge server v is included in F i . We have

∀i ∈ I, ∀v ∈ V i , |F i (v)| ≥ K (2)
• Hop-count constraint, which may be used to bound the delay and transmission reliability from the entrypoint to each subscribing edge server. For each tree T ∈ F i , the number of hop-counts from s to any node of T should be smaller than a given threshold D h . Let SP T (v) be the shortest path (list of arcs) from s to v in T , we have

∀i ∈ I, ∀T ∈ F i , ∀v ∈ T, e∈SP T (v) 1 ≤ D h (3)
IV. JOINT-OPTIMIZATION AND TWO-STEP OPTIMIZATION HEURISTIC ALGORITHMS

We propose two classes of heuristic algorithms for solving the video delivery of multiple channels in practical Telco-CDNs, i.e., two-step optimization and joint-optimization. Both heuristics are greedy algorithms, with one main loop. At each step, we select one channel, then we compute the forest overlay for this channel, and, if it is possible to support the overlay using the residual capacities of edge servers, then we reserve the needed resources for this overlay. We highlight the main differences below.

A. Two-Step Optimization Approach

In the two-step optimization approach, we first construct all overlays, then we allocate the bandwidth among the different overlays so that the most important channels are delivered, until resource exhaustion. Following this idea, the SOP-heu algorithm is proposed, where all overlays are computed before the resources are allocated. Pseudocode is given in Algorithm 1. Here we emphasize: (i) in line 1, all the overlays are pre-computed; and (ii) in line 3, the channels are selected iteratively according to a utility score.

Algorithm 1: Heuristic Main Loop for SOP-heu

Input : I, {(f i , V i ) : ∀i ∈ I}, G, {c v : ∀v ∈ V } Output: F i for all i ∈ I 1 precompute F i for all i ∈ I; 2 while not all channels have been processed do 3 i ← the remaining channel with max. utility; 4 if F i not null then 5 update capacities for every edge server in F i

The simplest implementation of the utility score, denoted U i , ∀i ∈ I, is to set U (i) = f i , i.e., the channels are processed according to their importance. This method is named SOP1-heu. It is however well-known from knapsack and bin packing literature that better performance can be obtained using utility scores that take into account both the gain (here f i ) and the penalty cost that this overlay produces on the infrastructure. This approach is denoted by SOP2-heu. In our implementation, we utilize the following parameters to set the penalty cost: (i) minimum remaining nodal bandwidth: we try to prevent edge servers to be exhausted, with the risk of network disconnection, and (ii) saving on critical edge servers: we analyse the channels that have not been processed yet, and we estimate the edge servers that are the most demanded.

1) Advantages: The most costly channels are not processed first if they are not very important. This strategy is expected to allow the distribution of more channels. Moreover, in case of churn of video channels, only the bandwidth allocation part should be re-computed. 2) Drawbacks: Algorithm 1 uses pre-computed forest overlays, therefore it may be unable to utilize the last remaining resources at the end of the loop.

B. Joint-Optimization Approach

Different form the previous approach, the joint-optimization approach proposes to jointly construct the overlays and reserve the required resources on the fly. This approach generally leads to better solutions. The JOP-heu heuristic algorithm adopts this idea. Its pseudocode is given in Algorithm 2. We emphasize the following main aspects: (i) in line 2, the channel to process is selected according to the channel importance; and (ii) in line 3, the overlay computation takes into account the remaining capacities of edge servers.

Algorithm 2: Heuristic Main Loop for JOP-heu

Input :

I, {(f i , V i ) : ∀i ∈ I}, G, {c v : ∀v ∈ V } Output:
F i for all i ∈ I 1 while not all channels have been processed do 2 i ← the most important remaining channel; 3 compute F i with the remaining capacities; 4 if F i not null then 5 update capacities for every edge server in F i 1) Advantages: Since the forest overlays are computed with the remaining capacity, this algorithm is able to construct overlays even when most capacities have been exhausted. It should result in no waste of resources. 2) Drawbacks: Algorithm 2 is oblivious to the amount of capacities that are utilized by the channels. That is, an important but very costly channel can be processed before some channels that are just slightly less important, but far cheaper in terms of resources. Moreover, if a new channel has to be delivered, or if a channel should not be delivered anymore, the algorithm should be executed from scratch.

C. Overlay Construction

The construction of multi-tree overlays under capacity constraint has been addressed in several previous works, including [START_REF] Zhou | Minimizing Server Throughput for Low-Delay Live Streaming in Content Delivery Networks[END_REF]. Here, we propose to use a tree construction algorithm for general graphs that aims at minimizing the used capacity by linking every edge server iteratively according to their distance to the entrypoint. For a channel i, which should be rooted at an entrypoint s, the idea of this greedy algorithm is as follows. We first determine the edge server in V i that is the closest to s in terms of number of intermediate edge servers. If several edge servers are tied, we pick the one with the largest capacity.

Then, we iteratively pick the non-spanned edge server that is the closest to the set of spanned edge servers with spare resources. We always choose the one with maximum capacity if there is a tie. The spanning process continues until all edge servers in V i are spanned K times in the resultant forest F i .

V. EVALUATION

Extensive simulations are conducted to evaluate the performance of the proposed solutions in this paper: JOP-heu, SOP1-heu and SOP2-heu. The French CDN network (Fig. 1) is used as the network topology. The following three metrics are used in our comparisons: 1) profit ratio, i.e., i∈I Ri×fi i∈I fi , which indicates the satisfaction of the service provider since it measures if channels are well delivered, according to their importance 2) number of delivered video channels, i.e., i∈I R i 3) ratio of used capacity, i.e., Cap v∈V cv

Here, we study the performance of the proposed heuristic algorithms: JOP-heu, SOP1-heu and SOP2-heu. Node bandwidth follows a lognormal distribution with an average of 96 Mbps. The channel importance follows the Zipf(0.5, 105) distribution. The number of subscribers |V i | for a channel i ranges from 3 to 9. Thus, there are some configurations where the network is over-provisioned (e.g. when |I| ∈ {30, 45}), and some others where not all channels can be delivered.

In Figs. 2(a)-2(c), the video bit-rate is 2,048 kbps, and we evaluate the performance of our algorithms with respect to the number of channels from 30 to 105. It is found that the proposed three heuristic algorithms serve well the most important channels, so the overall profit is almost the same for every algorithm in the over-provisioned network configuration. In the under-provisioned scenario, i.e., when the number of channels is bigger than 45, all algorithms obtain an achievable profit ratio no less than 87%. The joint optimization JOP-heu is always able to obtain up to 12% higher profit ratio and deliver 20 more video channels than the two-step heuristic algorithms. Thus, it clearly results in high network bandwidth usage, i.e., 9% higher. Moreover, the simple importance-first heuristic SOP1-heu performs better than SOP2-heu in term of achievable profit ratio, while the latter one tends to accept more video channels with smaller bandwidth requirement. This may be explained by the fact that a video channel with smaller importance requires less bandwidth due to the Zipf distribution of importance value. The SOP1-heu packs the most important videos better than SOP2-heu, meaning that the more sophisticated utility score of SOP2-heu is counterproductive. In Figs. 2(d)-2(f), the number of channels is fixed to |I| = 105 and we study the performance of our algorithms when the video bit rate varies from 512 kbps to 2560 kbps. We can find that algorithm JOP-heu is always superior to the others. As the video bit rate increases, the achievable profit ratio degrades slightly while the number of delivered videos diminishes quickly. This is due to the lack of bandwidth in the video entrypoints or the edge servers around the videos entrypoints for accommodating high quality videos. It also should be noted that the network bandwidth usage is up to 80%, which is not high. This is because, we employ a mesh topology (c.f. Fig. 1), where there are only three entrypoints. Since an entrypoint node does not have a link to all the edge servers, the bandwidth of an edge server far away from the entrypoint node may be wasted when the neighbors of the entrypoint exhaust their bandwidth. In summary, JOP-heu performs best among the proposed heuristic algorithms. When the resources are more constrained, it serves one third of the channels more. Such gain in performance is enough to justify the implementation of JOP-heu in resources-constrained Telco-CDNs.

VI. CONCLUSION

This paper addressed the problem of overlay construction and bandwidth allocation for delivering video channels from the entrypoints of the Telco-CDN to edge servers. The pursued goal is to maximize the total profit of delivered channels while preserving network resources. To this end, two optimization methods have been compared: two-step optimization and joint optimization. We analyzed the relevance of implementing the joint optimization approach, which is theoretically more efficient. Our work provided insights to network operators for making informed resource provisioning decisions in the support of a Telco-CDN.

Fig. 1 .

 1 Fig. 1. Topology of a French Telco-CDN

Fig. 2 .

 2 Fig. 2. Simulation Results in the French Telco-CDN (Fig. 1)