Giacomo Bernardi

Damon Fenacci

Mahesh K Marina

Dimitrios P Pezaros

BSense: A Flexible and Open-Source Broadband Mapping Framework

Keywords: Broadband mapping, performance measurement, broadband quality index, broadband access technologies

We present, BSense, a flexible broadband mapping system for broadband coverage and quality assessment of broadband connections in a given geographic region. For coverage related analysis, it relies on data that is either obtained from ISPs or generated based on technology models and information about infrastructure sites. Broadband quality assessment in BSense is via host-based measurements using our multiplatform and technology-adaptive software client which periodically runs as a background process on users' computers. The host-based software measurement approach employed in BSense is not only cost-effective but is also flexible and reduces measurement bias. BSense also incorporates a flexible broadband quality index for summarizing the collective effect of various underlying attributes such as download/upload speeds and latency. BSense system has been implemented based on open-source software components. The usefulness of the BSense system is demonstrated using two real world case studies, one on identifying notspots in Scotland and the other on broadband quality assessment in a rural part of Scotland through pilot deployment.

Introduction

Broadband mapping is the process of assessing broadband coverage, quality and market for a given geographical region (e.g., country, province, city). Broadband coverage assessment is aimed at identifying "notspots", i.e., locations not serviced by any broadband access technology. For areas that are covered, assessing broadband quality in those areas is more interesting. Quality is measured using a set of performance metrics such as download/upload speeds, latency, jitter and packet loss rate. Several technology-specific and network provisioning factors affect quality in practice (e.g., line length, number of concurrent users, contention ratio, backhaul capacity). Choice and cost associated with broadband subscription are additional aspects that are of interest for broadband mapping, especially to consumers and regulators. In order to determine the amount of choice that a consumer has, one needs to find out various access technologies and Internet Service Providers (ISPs) available at the consumer's location. Greater choice usually also implies lower cost (per Mbps) for the consumer. Moreover, choice and cost both tend to depend on the coverage and quality aspects -poor broadband coverage or quality in a region correlates well with lack of choice and/or higher costs for consumers in that region. Note that all these four aspects -coverage, quality, choice and cost -vary with time though timescales of change may differ widely between them.

Interest in broadband mapping has been growing recently in tune with increase in consumer awareness and recognition by governments on the importance of high-speed Internet access for all citizens. Different countries have launched national broadband mapping programs (e.g., [1][START_REF]UK Fixed Broadband Map[END_REF][START_REF]Broadband Map for Germany[END_REF][START_REF]UK Fixed Broadband Speeds[END_REF]) to quantify the existing state of broadband delivery and to track the progress towards achieving targets set forth in national broadband plans, especially in view of the on-going debate on the role of public funding and regulation in enabling fast and universal broadband access. Beyond these government-initiated efforts, other broadband mapping examples include [START_REF]Ookla Speedtest[END_REF][START_REF] Grenouille | [END_REF]. Despite these various efforts, we identify the lack of an open and flexible broadband mapping framework, key to effective and consistent mapping exercises. Open specification of assessment methodology and metrics is important for audit, whereas the use of open-source software results in lower cost implementations which in turn enable broadband mapping efforts in developing regions. Flexibility is also important to accommodate the wide range of broadband access technologies and to factor in latest advances and best practice in terms of measurement techniques. Moreover, these efforts take one of two different approaches we refer to as model based (e.g., [START_REF] Grubesic | Spatial Data Constraints: Implications for Measuring Broadband[END_REF][START_REF]Assessment of the Theoretical Limits of Copper in the Last Mile[END_REF][START_REF]Ofcom. 3G Coverage Maps[END_REF]) and measurement based (e.g., [START_REF] Samknows | [END_REF][START_REF] Sundaresan | Broadband Internet Performance: A View From the Gateway[END_REF][START_REF]Ookla Speedtest[END_REF][START_REF]Network Diagnostic Tool (NDT[END_REF][START_REF] Grenouille | [END_REF]13,[START_REF] Dischinger | Characterizing Residential Broadband Networks[END_REF]) even though neither is enough -model based approaches fail to capture the discrepancy between expected and actual broadband quality experienced by consumers, whereas measurement based approaches are clearly not useful for identifying notspots. We further discuss these different broadband mapping approaches in §2.

In this paper, we present an open and flexible broadband mapping framework called BSense (Fig. 1(a)) along with its implementation based on open-source software components ( §3).

-BSense incorporates both model based and measurement based approaches keeping in mind the observation that each is useful for a different purpose.

For coverage related analysis, it relies on data that is either obtained from ISPs or generated based on technology models and information about infrastructure sites. Broadband quality assessment in BSense is based on hostbased continuous measurement stream obtained using our multi-platform and technology-adaptive software client, which periodically runs as a background process on users' computers. As elaborated in §2, the measurement paradigm employed in BSense results in a lower-cost and flexible alternative to [START_REF] Samknows | [END_REF][START_REF] Sundaresan | Broadband Internet Performance: A View From the Gateway[END_REF], and reduces measurement bias compared to [START_REF]Ookla Speedtest[END_REF][START_REF]Network Diagnostic Tool (NDT[END_REF][START_REF] Dischinger | Characterizing Residential Broadband Networks[END_REF]. -Unique to BSense is a flexible broadband quality index for summarizing the collective effect of various underlying attributes such as download/upload speeds and latency. Specifically, we propose to separately model user preference concerning various performance attributes through a specific instan- tiation from a flexible family of utility functions and then combine them to produce an overall index by leveraging the general framework of multiattribute utility theory [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF]. To demonstrate the usefulness of the BSense system, we use two real world case studies -one on identifying notspots in Scotland and the other on broadband quality assessment in a rural part of Scotland through pilot deployment involving 60 real users over a three month period ( §4). Also, evaluation of our measurement methodology shows that it compares favorably to the hardware based measurement approach [START_REF] Samknows | [END_REF] as well as with a recently proposed sophisticated measurement technique [START_REF] Kanuparthy | ShaperProbe: End-to-end Detection of ISP Traffic Shaping using Active Methods[END_REF]; see [START_REF] Bernardi | BSense: A Flexible and Open-Source Broadband Mapping Framework[END_REF] for these results. We should, however, clarify that our focus is not on measurement techniques. Though we use D-ITG [START_REF] Botta | Multi-Protocol and Multi-Platform Traffic Generation and Measurement[END_REF], an open-source measurement technique we have access to, in our current BSense implementation, our design is flexible enough to allow the use of other measurement techniques such as [START_REF] Kanuparthy | ShaperProbe: End-to-end Detection of ISP Traffic Shaping using Active Methods[END_REF][START_REF] Kreibich | Netalyzr: Illuminating The Edge Network[END_REF]. We regard the BSense framework, its realization using open-source components and the two real-world case studies demonstrating its utility as our key contributions in this paper.

BSense Agent

GeoExt + Openlayers

D-ITG

Related Work

Broadband mapping approaches can be broadly classified into two categories: (1) model based and (2) measurement based. With the model based approach, broadband coverage and speeds are estimated based on theoretical or empirically derived models of access technologies, knowledge of network infrastructure (e.g., locations of phone exchanges, mobile network base stations) and configurations (e.g., contention ratio, radio parameters). For ADSL, see [START_REF] Grubesic | Spatial Data Constraints: Implications for Measuring Broadband[END_REF][START_REF]Assessment of the Theoretical Limits of Copper in the Last Mile[END_REF] for examples of such models and their use in estimating broadband coverage. Similar approaches can be followed to estimate 3G mobile broadband coverage [START_REF]Ofcom. 3G Coverage Maps[END_REF]. Such data is inherently optimistic as it does not consider various practical impediments (e.g., line quality, contention). Nevertheless, it is useful for coverage analysis in the absence of any measurement data. Note that this is the approach followed in [1-3] using the data obtained from ISPs.

Measurement based approaches involve actual measurement of broadband connections, a necessity for assessing broadband quality in a region. None of the existing measurement approaches we are aware of rely on measurement data from ISPs. Measurement based approaches can be further divided into hardware-based and software-based approaches.

The hardware-based measurement approach (also called gateway-based approach) involves deploying a customized hardware box that directly connects to home broadband router for a representative sample of users, and using the gathered statistics across all such boxes to estimate statistics for the whole population. It is pioneered by SamKnows [START_REF] Samknows | [END_REF] for UK Ofcom and US FCC sponsored broadband speed studies, and is also considered recently in the academic community [START_REF] Sundaresan | Broadband Internet Performance: A View From the Gateway[END_REF]. This approach can be expensive than an equivalent software based measurement approach. Moreover, it is also limited in terms of flexibility -unviable for mobile/wireless broadband quality assessment and for analysis at a fine-grained geographic granularity (e.g., city) when planned at national level.

Software-based measurement approaches broadly come in three varieties:

-Web based: Using web-based speed tests such as [START_REF]Ookla Speedtest[END_REF][START_REF]Network Diagnostic Tool (NDT[END_REF] can only gather sporadic and geographically non-uniform measurement data and also suffer from measurement biases (e.g., users taking speed tests may have poor broadband connections or may not belong to a representative sample). -Host daemon based: This approach relies on a measurement agent running in the background on user computers and can overcome the limitations of the web-based approach. However, existing systems following this approach [13, 6] lack openness and flexibility expected from a broadband mapping system. -Consumer and ISP independent: Dischinger et al. [START_REF] Dischinger | Characterizing Residential Broadband Networks[END_REF] present an interesting approach that does not require cooperation from either the consumers or the ISPs. This approach relies instead on certain specific but standard functionality from routers (e.g., responding with TCP RST packets upon receiving unsolicited ACKs). Such functionality may be disabled due to security concerns. If a particular ISP does not support this functionality on all its broadband routers, then that ISP is effectively ignored by this approach, introducing a measurement bias and thus undesirable from a broadband mapping perspective.

BSense uses a model based approach as well as a host daemon based software measurement approach, each for a different use case.

BSense Broadband Mapping Framework

As shown in Fig. 1(a), BSense framework views broadband mapping as a cooperative exercise involving various stakeholders -consumers, ISPs, policy makers and regulators. In [START_REF] Bernardi | BSense: A Flexible and Open-Source Broadband Mapping Framework[END_REF], we elaborate on the incentives that can be provided to different stakeholders to continually contribute to the exercise. BSense brings together different types of data. Estimated broadband data from ISPs is fed into the BSense database via webservice API calls. Broadband users (consumers) are the key source of continuous measurement data for the mapping system. This is enabled by a lightweight software agent termed BSense Agent that runs in the background on a user computer and periodically communicates with BSense Test Servers to measure technical attributes of user's broadband characteristics such as download speed, upload speed and latency. Digital geographic data from country-specific sources and demographic data from population census are additionally used as layers underneath estimated or measured broadband statistics to generate broadband coverage or quality maps, respectively.

Design and Implementation

Fig. 1(b) depicts the BSense software architecture, which is described in the rest of this section.

BSense Server

The BSense server side includes a web server for hosting a public website that users can access for registering and downloading the BSense agent software and subsequently to retrieve their broadband connection statistics. The web server also supports a set of web service API calls over SOAP for interaction between the BSense system and various stakeholders. The current API consists of the following calls: BroadbandTestRecord, AddPackage, EditPackage, DeletePackage, AddEstimatedData, EditEstimatedData, DeleteEstimatedData and LookUpMappingData. The purpose of these calls is evident from their names; for further elaboration, see [START_REF] Bernardi | BSense: A Flexible and Open-Source Broadband Mapping Framework[END_REF]. These API calls are handled by a server side component that enforces security and access control, validating the input and checking whether an API call is made by a party with the required permissions.

In addition to SOAP based web services, BSense provides external access via the Open Geospatial Consortium's standard WMS (Web Map Service) and WFS (Web Feature Service) to obtain raster and vector geo-referenced images, respectively, of a geographical area of interest; most open-source and commercial GIS software products can directly use WMS and WFS services. BSense also provides an in-built web application based on WMS, developed using open-source GeoExt (http://www.geoext.org/) and OpenLayers (http://openlayers.org/) frameworks, to further ease access to broadband maps and their visualization.

Coming to data management, our implementation uses the open source Post-greSQL (http://www.postgresql.org/) database management system augmented with the PostGIS (http://postgis.refractions.net/) extensions to handle spatial data. See [START_REF] Bernardi | BSense: A Flexible and Open-Source Broadband Mapping Framework[END_REF] for further details (database schema, etc.). Access to the BSense database via WMS and WFS is enabled by the well known open-source GeoServer (http://www.geoserver.org), a Java software that allows users to view and edit geospatial data. Besides broadband mapping data, BSense allows the storage of additional geospatial layers with geographic and demographic data that are useful when generating maps.

BSense Agent Each broadband user participating in the BSense based mapping exercise runs a software agent (BSense Agent) that facilitates continuous and cost-effective measurement of the user's broadband connection. As such, the agent is a key element of the BSense framework for gleaning the quality of broadband provisioning in a given region. Given the diversity of operating system (OS) platforms used by consumers in the real world, the agent should function on different commonly used platforms to avoid measurement bias. The BSense agent was designed explicitly keeping in mind this requirement for multi-platform support. Specifically, it has been developed using Qt (http://qt.nokia.com), an open-source and cross-platform application/UI framework; Qt is available for Windows, Linux and Mac OS X.

We first give a high-level overview of the measurement process. A participating broadband user would download the agent from a public website like the one we developed (http://broadbandforall.net) and install it on the user's home computer. The agent runs in the background and periodically wakes up to perform a measurement test of the user's broadband connection 3 . Each measurement test consists of the following sequence of steps (Fig. 2(a)):

1. The agent queries BSense server to get the details of the measurement test to be performed. 2. BSense server replies with an "experiment definition" (elaborated below) as well as details for a test server to be used (e.g., IP address, port number). 3. BSense server also simultaneously notifies the test server about the impending measurement test from the user's agent. 4. The agent interprets and follows the experiment definition received, generating the traffic flow requested and/or receiving the incoming traffic to/from the specified test server. 5. Upon test completion, the agent summarizes the traffic traces from the test and uploads it to the BSense server. Since the effectiveness of the mapping framework improves with a larger number of participating users, the mapping system should be scalable and robust to server failures. In the case of BSense server, this can be achieved through the use of a server farm (the current approach) or by installing the BSense server on a cloud-based hosting. The use of multiple test servers as in our current design also contributes towards scalability and fault tolerance. As regards to the location of test servers, we advocate their deployment at neutral Internet exchange points (IXPs) (e.g., the ones listed at http://www.euro-ix.net/) to avoid introducing bias against users of some ISPs. In the current implementation, however, test servers are co-located with the BSense server farm.

BSense agent could in principle use any multi-platform network performance measurement tool. In our implementation, we choose a widely used traffic generator called D-ITG [START_REF] Botta | Multi-Protocol and Multi-Platform Traffic Generation and Measurement[END_REF] with BSense Agent acting as a wrapper application. While D-ITG can be seen just as a placeholder in the current implementation, it also has several attractive features that have influenced our choice such as the following: open source; can be made to work on different platforms and behind most common types of NATs with minimal effort; and provides a high degree of flexibility when it comes to traffic generation.

We now briefly describe the experiment specified to the agent every time it is about to do a measurement test. An experiment is defined as a set of traffic session specifications with each session potentially consisting of multiple concurrent or partially overlapping flows. Specifically, each experiment in our context is a sequence of three traffic sessions: initial ping-like UDP session with short packets to measure latency, jitter and packet loss rate, followed by an upstream traffic session and then a downstream traffic session. See [START_REF] Bernardi | BSense: A Flexible and Open-Source Broadband Mapping Framework[END_REF] for detailed parameter settings. Note that in a host-based software measurement approach like ours, it is possible to have in-home wireless network use and other active use of the broadband connection from other devices within the home concurrently with broadband connection measurement traffic. However, the problem of cross-traffic on the network path is unavoidable with end-to-end performance measurement even with hardware-based measurement approach. We believe it is best dealt with via statistical filtering.

Broadband Quality Index

As noted at the outset, coverage and quality are the two key aspects of interest for broadband mapping. While broadband coverage in a particular location can be quantified as a binary variable, the same is not true for broadband quality as the latter is dependent on several underlying technical attributes such as download speed, upload speed and round-trip latency. Due to the lack of standard ways to summarize the collective impact of those several attributes, the focus is often solely on download speeds even though it is widely recognized that upload speeds and latency also have to be considered at the very least.

Defining an index is a common approach to deal with problems of the above nature. Only work we are aware of that tries to address the issue of developing a broadband quality index is surprisingly a sociological study [START_REF] Vicente | Assessing the Broadband Gap: From the Penetration Divide to the Quality Divide[END_REF] relying on expert surveys to determine the relative importance of various technical attributes. More importantly, the work in [START_REF] Vicente | Assessing the Broadband Gap: From the Penetration Divide to the Quality Divide[END_REF] only provides a very specific approach to defining the broadband quality index while we are interested in defining a more flexible and general framework.

Our main idea in addressing this issue is to model each attribute impacting broadband quality as a utility function and then draw upon the multi-attribute utility theory (MAUT) [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF] to define the broadband quality index (BQI) as a composite function of utility function values for the individual attributes.

In our model, denote F = [f 1 , ..., f n ] for the set of network attributes (features) to be included in the BQI, covering important attributes characterizing a broadband connection. For the sake of concreteness, we focus on three key performance attributes in this paper: download speed (d, in Mbps), upload speed (u, in Mbps) and round-trip latency (l, in milliseconds).

We first aim to identify a suitable family of realistic single-attribute utility (SAU) functions for modeling user preferences about individual attributes, and then consider their composition into a multi-attribute function. For the attributes under consideration (i.e., download speed, upload speed and latency), we observe that sigmoid functions, whose graphs are "S-shaped" curves (see Fig. 2(b)), better reflect user satisfaction. This is because improvement in utility from improving any of these attributes beyond a point is marginal. Equally, when these attributes are below a certain threshold (for speeds) and above a certain threshold (for latency), the change in utility is again marginal. In between these extremes, the improvement in utility with improvement for any of these attributes is noticeable and substantial.

Thus, we define a set of utility functions u f (f ), each defined on a given attribute f ∈ F as:

u f (f ) = e a+bf -e a 1 + e a+bf (1)
where parameters a and b determine the nature of each utility function curve.

A pragmatic approach to specify a utility function for each attribute would be to have the BSense administrator pick two strategic values of each attribute f and provide their corresponding utility u values:

(f o , u o ) and (f * , u * ) s. t. u o = u f (f o ) < u * = u f (f * ) (2)
These two points can be carefully picked so that they represent the utility of low-end and high-end broadband connections (e.g., with u o = 0.2 and u * = 0.8 or u o = 0.1 and u * = 0.9). Intuitively, the lower knee in the curve represent the value of the attribute which is deemed as insufficient, and the upper knee describes the attribute value which is good enough for the service. As a consequence, "poor" broadband connections that are only able to offer attribute values (e.g., download speeds) below the lower point offer only marginal utility to the users. Similarly, the incremental utility above the upper threshold is only marginal. The low and high values can, for example, be based on current policies and regulations (e.g., the "Universal Service Obligation" to set the bottom bar that ISPs have to provide and the policy maker must enforce) or current state-of-the-art (e.g., the fastest commercially available service to set the top bar).

The parameters a and b for each of our SAU functions can then be derived from their two specified corresponding 'knobs' by solving the following pair of equations obtained by substituting values from (2) in equation (1).

To provide a quality index for each broadband connection, we first need to generate a summary statistic from all the measurements that have been gathered by BSense for that connection. In the current implementation, we use the median values of download speed, upload speed and latency. These values along with their respective a and b parameter values as input to equation (1) determine the utilities of the broadband connection in question with respect to each of those three attributes.

Multi-attribute utility theory assists us in combining the various SAU functions in a single equation, whose form depends upon the particular independence conditions fulfilled by the different SAU functions. For simplicity, we assume mutual additive independence in this paper. Then the resulting multi-attribute utility function can be represented as:

u(f ) = ∑ f ∈F k f u f s.t. ∑ f ∈F k f = 1 and k f > 0, ∀f ∈ F (3)
A further simplifying assumption would be to have all scaling constants (weights) k f to be equal. This is reasonable given that our main purpose is to demonstrate the value of multi-attribute utility theory and utility functions in providing a flexible framework for defining broadband quality index.

Case Studies

Broadband Coverage Analysis for Scotland

In this case study we show the benefit of BSense for understanding broadband coverage, using Scotland as the setting. Such studies would rely upon estimated coverage and speed data from ISPs whenever available. For this study, we mimicked the way ISPs would contribute to the BSense mapping system by trawling through the public websites of different ISPs to determine whether an ISP covers a particular postcode and if so, the estimated download speeds from the ISP's viewpoint, for each of the 152,000 postcodes in Scotland. This information is then fed into the BSense estimated database via the web service API calls. Fig. 3 shows the broadband coverage in Scotland for different access technologies based on the estimated data from ISPs collected as described above. For the 3G mobile broadband case, we show data for only one network operator for clarity but the coverage for other mobile network operators is similar. From these maps, we observe that ADSL is the dominant access technology with cable and mobile confined mainly to population centers in the central belt and north east. Now focusing on ADSL alone, we estimate the notspots in Scotland with respect to a threshold download speed. Specifically, a postcode area is considered to be a notspot if ADSL service with estimated download speed above the specified threshold cannot be supported within that area. This may be because residences in the postcode area are too far away from their nearest phone ex-

Broadband Quality Measurement: A Pilot Study

In this case study, we assess the broadband quality in a rural part of Scotland. Specifically, we focus on the area around the Isle of Skye located in the northwest of Scotland. We also consider the neighboring archipelago of the 'Small Isles' and the mainland rural areas of Glenelg and Knoydart peninsulas. This region is quite diverse in terms of demographics, terrain and broadband service provisioning, making it a well suited region for our broadband performance measurement study. It has a population of around 10 thousand people spread across a handful of small towns, several small villages and scores of isolated dwellers in the farming lands. Several different access technologies used for broadband provisioning. In total, 15 phone exchanges are located in the area. Although every resident has access to a landline, broadband connection types vary. A few phone exchanges are enabled for ADSL2/ADSL2+, which is available only from the telecom incumbent (BT). Other exchanges offer ADSL (8Mbps download speed) service, and a few are enabled only for "Exchange Activate" (512Kbps) ADSL service. There are no FTTH deployments in the area, and cable and 3G coverage are non-existent. Due to a recent broadband reach initiative from the Scottish government, some of the users in rural and remote areas in previously notspot areas in Scotland, including those in our study area, now connect via subsidized yet relatively expensive satellite connections. In addition, residents in a small part of this area connect via Tegola, an experimental/community long distance WiFi network we have deployed four years ago [START_REF] Bernardi | Tegola Tiered Mesh Network Testbed in Rural Scotland[END_REF].

Through publicity of our pilot broadband quality assessment initiative via email, local press and word of mouth, we managed to find 60 volunteers in the area who were willing to install and run our BSense agent software. Half of these users are connected to the Internet via ADSL lines to different exchanges and differing line lengths, whereas 18 users connected via our Tegola network; remaining volunteers used satellite connections. Over a 3-month period, we measured the broadband connections of each of the volunteer users, keeping track of median values of download/upload speeds and latency measurements for each user. We collected around 40,000 measurements in total. To study the broadband quality index across users and access technologies, we used the following parameter settings for the individual utility functions (see Section 3.2), all reasonable given the type of broadband connections in the study area:

-Download speeds. Low-end: 2Mbps with a utility of 0.1. High-end: 24Mbps with a utility of 0.9. -Upload speeds. Low-end: 1Mbps with a utility of 0.1. High-end: 5Mbps with a utility of 0.9. -Latency speeds. Low-end: 200ms with a utility of 0.1. High-end: 20ms with a utility of 0.9.

Fig. 5(a) shows the results. The top graphs show the utility function values for each of the three performance attributes. Each data point in the plots corresponds to a user with the color of the data points indicating the access technology used. Clearly and as expected, satellite users have poor utility values and are clustered together at the worst extreme. Wireless users on the Tegola network, on the other hand, not only experience high speeds exceeding 20Mbps but also are subject to greater variability in speeds because of the shared nature of access. ADSL users also exhibit greater variability in speeds like wireless users but because of different reasons -due to differences in broadband capabilities of the associated phone exchanges and differences in line lengths; most ADSL users fall in between satellite users and wireless users in this area. The bottom graph shows the combined effect of the three attributes. For ease of interpretation, we scale up each user's index value to a percentage value between 0% and 100%. Results for different access technologies shown as CDFs follow directly from the top graphs given our choice for the multi-attribute utility function (an equal weighted sum of individual attribute utilities). When index values for different users are geographically rendered on a map, however, the result is quite revealing (see Fig. 5(b)). Here coloring is done at the ward level -all users belong to a ward (an area with about 50 residents and 20 households) are aggregated together. We observe that remote parts of Knoydart and the Small Isles (colored

Conclusions

In this paper, we have developed a flexible framework for broadband mapping called BSense that incorporates both model based broadband coverage data and broadband performance measurement data from users. BSense framework also incorporates a flexible specification of broadband quality index based on utility functions and multi-attribute utility theory. We implemented BSense using open-source tools and use it demonstrate the value of BSense approach for broadband coverage and quality assessment with two real-world case studies.

Our future work will focus on enhanced measurement techniques that are robust to various sources of variability. We would like to also enhance the broadband quality index by considering additional attributes, variability of each attribute and relationships among various attributes. Finally, we would like to extend BSense for mobile broadband mapping.

Fig. 1 :

 1 Fig. 1: (a) BSense broadband mapping framework illustrated. (b) BSense software architecture.

Fig. 2 :

 2 Fig. 2: (a) The sequence of steps making up a measurement test initiated by an instance of the BSense agent. (b) The sigmoid utility function can be seen as a transfer function between a given attribute f and the perceived utility associated with specific values of f . In fact, the function shown is a modified sigmoid function given in equation (1) to realize zero utility when the value of f is zero.

Fig. 3 :

 3 Fig. 3: BSense generated broadband map for various access technologies and ISPs based on their estimated data: (a) ADSL -BT Wholesale; (b) Cable -Virgin and Smallworld; (c) 3G mobile broadband -Orange. In each of these maps, postcode areas with the corresponding service are colored with darker colors indicating faster expected speeds or better mobile coverage.

Fig. 4 :

 4 Fig. 4: BSense generated map of notspots in Scotland that lack an ADSL broadband service supporting download speed greater than the indicated threshold. Notspot postcode areas are shaded in red.

Fig. 5 :

 5 Fig. 5: (a) Pilot study results. Top graphs showing the utilities for different attributes, different users and different access technologies. Bottom graph summarizes the broadband quality index values for users of different access technologies as CDFs. (b) Map generated using the results from the pilot study aggregating users belonging to a ward together and colors representing different ranges for broadband quality index values.

The time interval between measurements (i.e., measurement frequency) is a customizable parameter whose setting is a tradeoff between gathering fine-grained measurement samples over time and measurement overhead. The value is set to 15 minutes in the current implementation.


Meng Shen
email: shenmeng@csnet1.cs.tsinghua.edu.cn

Hongying Liu
email: liuhongying@buaa.edu.cn

Ke Xu
email: ke.xu@csnet1.cs.tsinghua.edu.cn

Ning Wang
email: n.wang@surrey.ac.uk

Yifeng Zhong
email: zhongyifeng@csnet1.cs.tsinghua.edu.cn

Routing On Demand: Toward the Energy-Aware Traffic Engineering with OSPF

Keywords: Traffic Engineering, OSPF, Energy Saving, Routing

Energy consumption has already become a major challenge to the current Internet. Most researches aim at lowering energy consumption under certain fixed performance constraints. Since trade-offs exist between network performance and energy saving, Internet Service Providers (ISPs) may desire to achieve different Traffic Engineering (TE) goals corresponding to changeable requirements. The major contributions of this paper are twofold: 1) we present an OSPF-based routing mechanism, Routing On Demand (ROD), that considers both performance and energy saving, and 2) we theoretically prove that a set of link weights always exists for each trade-off variant of the TE objective, under which solutions (i.e., routes) derived from ROD can be converted into shortest paths and realized through OSPF. Extensive evaluation results show that ROD can achieve various trade-offs between energy saving and performance in terms of Maximum Link Utilization, while maintaining better packet delay than that of the energy-agnostic TE.

Introduction

Since plenty of bandwidth-intensive applications (e.g., video-on-demand and cloud computing) have come into service, the amount of data being carried on the Internet has dramatically grown [START_REF] Vasić | Energy-Aware Traffic Engineering[END_REF]. Traditionally, Internet Service Providers (ISPs) leverage Traffic Engineering (TE) to ensure acceptable network performance. Open Shortest Path First (OSPF) [START_REF] Moy | RFC 2328 OSPF Version 2[END_REF] is a commonly used intra-domain routing protocol that can be applied in TE through configuring appropriate link weights. In our previous work [START_REF] Xu | One More Weight is Enough: Toward the Optimal Traffic Engineering with OSPF[END_REF], we made a change on the traffic splitting scheme in OSPF and proposed an OSPF-based approach to achieve optimal TE.

As bandwidth requirements increase, ISPs need to deploy more and faster network equipments (e.g., routers) to handle these demands, resulting in the growth of energy consumption. Therefore, TE should take both energy efficiency and network performance into consideration rather than merely focusing on the latter. The common idea of the state-of-the-art energy-aware TE approaches [START_REF] Zhang | GreenTE: Power-Aware Traffic Engineering[END_REF] [START_REF] Vasić | Energy-Aware Traffic Engineering[END_REF] is to reduce energy consumption under certain performance constraints. However, we argue that trade-offs exist between energy saving and network performance. Intuitively, an ISP can achieve higher network energy efficiency at the cost of sacrificing partial performance without influencing user experience. Thus, there is a set of solutions rather than a unique solution to solve the energy-aware TE problem, where ISPs can make a flexible adjustment among these solutions.

The main challenge to achieve this goal exists that the conventional TE problem is already difficult due to the elastic nature of network traffic. Therefore, considering energy saving and network performance together will make the problem even harder. This problem should be carefully studied to ensure the network free from frequent oscillations and extra long delays.

This paper presents Routing On Demand (ROD), an OSPF-based routing mechanism that can achieve energy-aware traffic engineering solutions. ROD is formulated based on the Multiple Commodity Flows (MCF) constrains with a weighted objective considering both energy consumption and network performance in terms of Maximum Link Utilization (MLU). In ROD, a specific trade-off requirement can be derived from adjusting a green factor in the objective function, where corresponding solutions (i.e., routes) can be converted into shortest paths with respect to a set of link weights. Then we develop algorithms to achieve these link weights, as well as flow splitting ratios based on minor extensions to the Equal-Cost Multiple Paths (ECMPs) function in OSPF that has been proposed in [START_REF] Xu | One More Weight is Enough: Toward the Optimal Traffic Engineering with OSPF[END_REF], which can be directly configured through OSPF protocol without introducing additional load to the network. The compatibility with existing network protocols eases the deployment of ROD mechanism.

Using real and synthetic network topologies, we evaluate the effectiveness of the ROD mechanism in multiple metrics, including trade-offs between energy saving and performance, link utilization and packet delay. Results show that, through adjusting the green factor, ROD can achieve diverse trade-offs between energy saving and MLU without bias on topology types. Moreover, a promising result for Abilene lies in that a 1% growth of MLU threshold will roughly lead to a 15% decrease in energy consumption. Similar results also hold for other topologies.

The rest of the paper is organized as follows. Section 2 gives an overview of our basic idea. In Section 3, we present the ROD model and the proof of the existence of optimal link weights. The implementation issues are discussed in Section 4, which is followed by the evaluation of ROD mechanism in Section 5.

We summarize the related work in Section 6 and then conclude the paper in Section 7.

Overview of the Basic Idea

In this section, we illustrate through case studying that trade-offs exist between energy saving and network performance. As shown in Figure 1, each link has a capacity of 5 units. Traffic demands consist of 2 Original-Destination (OD) pairs, namely A→B and A→E, with a bandwidth requirement of 2 and 4 units respectively. For simplicity, we assume that each unused link can be put into sleep mode [START_REF] Gupta | Greening of the Internet[END_REF] without any power consumption, while each loaded link consumes the same amount of power. Given traffic demands and network topology, we need to configure the OSPF link weights under which the optimal routes for these demands according to certain constrains and objectives are exactly the OSPF shortest paths.

Through the following three cases with the OSPF link weights beside links, we illustrate the existence of trade-offs between energy saving and network performance in terms of Maximum Link Utilization (MLU) based on OSPF.

Case 1: Minimizing MLU. The most widely used objective function of the conventional TE is simply to minimize MLU [START_REF] Applegate | Making Intra-domain Routing Robust to Changing and Uncertain Traffic Demands: Understanding Fundamental Tradeoffs[END_REF], which aims at reducing the risk of network congestion. The optimal routes are shown in Figure 1 (a), where each path is marked with the same line type and its traffic load. In this case, the optimal routes altogether leverage 7 links with a 2-unit load on each link. Thus the MLU is 40%.

Case 2: Minimizing energy consumption without MLU constraint. Based on the energy assumption, this goal is equivalent to minimize the number of loaded links. The optimal routes are presented in Figure 1 (b), where altogether 4 links are involved and the MLU is 80%. Comparing to Case 1, energy consumption of the entire network is reduced approximately by (7 -4)/7 = 42.9%.

Case 3: Minimizing energy consumption with certain MLU upper bound. TE with only energy consideration might increase the risk of network congestion on heavy loaded links when facing traffic bursts. Therefore, an ISP may desire to minimize energy consumption while keeping MLU within certain safety threshold, say 60%. The optimal routes are shown in Figure 1 (c), where the energy saving rate compared with Case 1 is about 14.3% and the MLU is exactly 60%.

We notice that the traffic is not equally split over two ECMPs serving the same OD pair A→E in Case 3. This can be realized by modifying hardware components, which will be discussed in Section 4.

ROD Model

In this section, we first present the Routing On Demand (ROD) model to formulate energy-aware TE problem, which extracts the trade-off between energy saving and network performance. Then we prove that the optimal link weights always exist under each considered TE objective function.

Network Model

We consider a directed network G = (N , E), where N is the set of nodes (i.e., routers) and E is the set of edges (i.e., links). We assume that all links are directional and each link (i, j) ∈ E is attached with its own capacity c ij which is the maximum amount of traffic it can take. Let M denote the set of sourcedestination pairs. For each m ∈ M, a traffic demand of (s m , t m ) is d m , which represents the average intensity of traffic volume entering the network at node s m and leaving from node t m . Hereafter we use notations N, E and M to denote the cardinalities of sets N , E and M, respectively.

A customary way to treat the TE problem is to formulate it based on MCF constraints. We denote the destination node set with D = {t ∈ N : ∃ m ∈ M s.t. t m = t}. The traffic volume of commodity flow t along edge (i, j) is denoted by f t ij . The MCF constraints can be formulated as

f ij = t∈D f t ij ≤ c ij , ∀(i, j) ∈ E (1a) i:(s,i)∈E f t si - j:(j,s)∈E f t js = d t s , ∀t ∈ D, s ∈ N (1b) f t ij ≥ 0, ∀t ∈ D, (i, j) ∈ E, (1c)
where d t s ≥ 0 in (1b) is the expected traffic entering the network at node s and destined to node t. For s = t, set d t s = d m if there exists m ∈ M such that s m = s and t m = t, or set d t s = 0 otherwise. For s = t, according to the previous definition of commodity, we set d t t =m:tm=t d m . Constraint sets (1a) and (1b) represent the capacity and flow conservation constraints, respectively. We say a traffic distribution

f = (f ij , (i, j) ∈ E) is feasible if there exists (f t , t ∈ D) such that (f, f t , t ∈ D) satisfies the MCF constraints.
Remark: Here, to formulate the problem in a more compact way, we regard all traffic flows to the same destination as a commodity, i.e., we use the constraints (1b) associated with those traffic flows with their sum for s = t, so that we can obtain a formulation with less constraints and variables. It can be easily checked that this formulation is equivalent to the one where each traffic flow is treated as a separate commodity.

Minimizing MLU. If f is feasible, the total load and the utilization of link (i, j) ∈ E are f ij and f ij /c ij , respectively. The conventional TE problem prefers to minimize MLU to balance traffic distribution over all links, i.e., minimize max

(i,j)∈E f ij c ij (2a) subject to (1a) -(1c). ( 2b
)
Minimizing Energy Consumption. If we only consider minimizing energy consumption of the entire network, then the TE problem turns into optimizing traffic distribution under the same MCF constraints in (2) to use as few links as possible, i.e., to minimize f 0 , where f 0 represents the number of non-zero elements of f.

The above formulation, which seeks the vector whose support has the smallest cardinality, is commonly referred to as cardinality minimization and known to be NP-hard. Since the computation time for medium and large-scale networks is a great concern, the cardinality minimization problem is thus usually heuristically solved by minimizing the 1 norm [START_REF] Candès | Decoding by Linear Programming[END_REF]. Then the TE problem of minimizing energy consumption with the relaxed objective function is

minimize (i,j)∈E f ij subject to (1a) -(1c). (3)
Routing On Demand. We introduce a green factor θ to combine the above two models together and propose an integrated ROD model as follows minimize θ max

(i,j)∈E fij cij + (i,j)∈E f ij subject to (1a) -(1c). (4)

Universal Existence of Optimal Link Weights

We associate the network with an operator, and assume that if the load held by link (i, j) is f ij , then the cost is φ(f). We also assume that the cost φ(f) is an continuous convex function of f (f ≥ 0). Without loss of generality, we can apply φ(f) to represent various objective functions of previous models. The goal of TE thus turns into minimizing φ(f) over MCF constraints.

For simplicity of presentation, we write the MCF constrains in matrix form. Then the general TE problem is given as TE(φ, G, c, D)

minimize φ(f) (5a) subject to f - t∈D f t = 0 (5b) f ≤ c (5c) Af t = d t , f t ≥ 0, ∀t ∈ D, (5d)
where A, an N × E node-arc incidence matrix for network G, is introduced to represent the multi-commodity flow constraints (1b). The column corresponding to link (i, j) has a +1 entries in row i and a -1 entries in row j.

The partial Lagrangian of TE(φ, G, c, D) is

L(f, f t , t ∈ D; w) = φ(f) - (i,j)∈E w ij f ij + t∈D w T f t
From the general theory of constrained convex optimization [START_REF] Bertsekas | Nonlinear Programming[END_REF], it follows that (f, f t , t ∈ D) solves Problem (5) if and only if there exists a Lagrangian multiplier vector w such that (f,

f t , t ∈ D) solves φ(f) -(i,j)∈E w ij f ij + t∈D w T f t subject to f ≤ c; Af t = d t , f t ≥ 0, ∀t ∈ D. (6)
Problem ( 6) is a separable optimization, since there is no coupling between variable f and f t for all t ∈ D. Then Problem (5) can be solved through the following distributed method, i.e., (f, f t , t ∈ D) solves problem (5) if and only if there exists the Lagrangian multiplier vector w such that f solves the capacity planning problem ISP(w, φ, c), i.e.,

minimize φ(f) -(i,j)∈E w ij f ij subject to f ≤ c (7)
and for each t ∈ D, f t solves the minimum cost flow problem MCF(w,

d t ) minimize w T f t subject to Af t = d t ; f t ≥ 0. ( 8
)
Here we give some engineering interpretations to the separated Problems ( 7) and ( 8) for all t ∈ D. First, the ISP's problem [START_REF] Zhang | GreenTE: Power-Aware Traffic Engineering[END_REF] can be interpreted as a capacity planning problem where ISP determines the possible virtual link capacity with each link cost w ij , the total cost φ(f) generated for flow distribution f ij , and the maximal permission capacity for each link c ij and the objective as the net cost. Then the flows of the t-th class with the same destination t finds a solution that minimizes the total cost under the given link cost w ij without considering the link capacity.

An promising property of the optimal routes is that they can be converted into shortest paths, i.e., the routes for the t-th class flow is the shortest path under the link weights w ij . Let ν t denote the optimal solution of the dual of Problem [START_REF] Gupta | Greening of the Internet[END_REF]. By applying the complimentary slackness theorem, we have

ν t i -ν t j = w ij , if f t ij > 0 (9a) ≤ w ij , if f t ij = 0. ( 9b
)
Let p : i 0 i 1 • • • i n be a possible path of OD pair (s, t), where i 0 = s and i n = t. For example, if

y p = min k=1,2,••• ,n f t i k-1 i k > 0, we have (i,j)∈p w ij = ν t s -ν t t ≤
(i,j)∈ p w ij for any other path p that connects the same source-destination pair (s, t) under conditions (9a) and (9b).

Hereafter we refer to these as the optimal link weights and the optimal link loads, which are denoted by w * and f * , respectively. The similar results have been shown by Wang et al. [START_REF] Wang | Internet Traffic Engineering Without Full Mesh Overlaying[END_REF]. The major difference existing in our approach is that we present a close form of the link weights which are explicitly determined by the objective and the optimal traffic distribution. The main results are shown by Theorem 1 and that in Section 3.3.

Let p be a subgradient of a convex function

f at x ∈ domf if f (y) ≥ f (x) + p T (y -x), ∀y ∈ domf.
Subdifferential of f at x ∈ domf is the set of all subgradients of f at x and is denoted by ∂f (x). If f is convex and differentiable at x, then ∂f (x) = {∇f (x)}.

Theorem 1. There exists one subgradient p of φ at f * such that

w * ij = p ij if f * ij < c ij and w * ij ≥ p ij if f * ij = c ij .
The proof of Theorem 1 can be conducted based on the convex analysis theory with the ISP's problem [START_REF] Zhang | GreenTE: Power-Aware Traffic Engineering[END_REF] and the calculation rule of subdifferential, which is omitted here due to space limitation.

Optimal Link Weights for Various Cost Functions

In this subsection, we will illustrate that the optimal link weights can be achieved for those cost functions in Section 3.1.

Lemma 1. Let f (x) = max{f 1 (x), • • • , f m (x)}. Define I(x) = {i : f i (x) = f (x)},
and the active functions is at x. Then it holds that ∂f (x) = conv ∪ i∈I(x) ∂f i (x) , For minimizing MLU, i.e., (2), we have

φ(f) = max (i,j)∈E fij cij . Let I(f * ) = {(i, j) ∈ E : f * ij /c ij = max (i,j)∈E f ij /c ij }, i.e.
, the set of the link with MLU. By Lemma 1, we have p ∈ ∂φ(f * ) if and only if p ij = a ij /c ij for (i, j) ∈ I(f * ) and a ij ≥ 0, (i,j)∈I(f * ) a ij = 1, and p ij = 0 otherwise.

The results show that the routing minimizing MLU is the shortest path routing for each source-destination pair, where the link weights for the nonbottleneck links are all zeros, and only the link weights of the bottleneck links are possibly positive and scale with the inverse of their link capacities.

For minimizing energy consumption, by Theorem 1, routes derived from Model (3) are the shortest paths, where link weights are 1s for unsaturated links (i.e., f * ij < c ij ) and greater than 1 for the rest links. Furthermore, any path without including saturated links must be the lowest hop-count path.

For Routing On Demand, in (4), assume the green factor such that the optimal link load f * ij < c ij for all (i, j) ∈ E, i.e., all links are unsaturated. By Theorem 1, the routes minimizing Problem (4) are the shortest paths, where the link weight is θa ij /c ij + 1 for (i, j) ∈ I(f * ) and a ij ≥ 0, (i,j)∈I(f * ) a ij = 1, and is 1 otherwise. Furthermore, the path of a source-destination pair must be the shortest hop-count path if it does not cross bottleneck links.

Implementation Issues

In this section, we will briefly discuss the implementation issues of ROD mechanism based on the theoretical formulation in Section 3. Similar to the conventional traffic engineering, ROD relies on a centralized controller that is responsible for centrally computing link weights and periodically configuring all routers.

Collecting and Disseminating Information for ROD

The input information for ROD (e.g., network topology and traffic matrix) can be collected from routers. In OSPF, each router will periodically flood its Link State Advertisements (LSAs) that contain all link state information. In particular, the Traffic Engineering Link State Advertisement (TE-LSA) defined in RFC3630 [START_REF] Katz | RFC 3630: Traffic Engineering (TE) Extensions to OSPF Version 2[END_REF] records link load information. Thus, the latest topology and traffic matrix could be computed based on this information.

Algorithm 1 Computing the optimal link weights

Given optimal tolerance and initial weight w(0) (such as wij(0) = 1), k = 0; for the given weight w(k) do Solve ISP(w, φ, c) in ( 7) to achieve the traffic load fij(k) for link (i, j); Solve MCF(w, d t ) in ( 8) to achieve the routing variable f t (k) for destination t; Each link (i, j) ∈ E updates its link weight

wij(k + 1) = wij(k) -γ k ( t∈D f t ij (k) -fij(k)) + ; k ← k + 1; Until gap(w(k), f (k), f(k)) < . end for
The optimal link weights can be computed through Algorithm 1, which is derived from the dual decomposition of TE(φ, G, c, D) defined in [START_REF] Xu | One More Weight is Enough: Toward the Optimal Traffic Engineering with OSPF[END_REF]. Given the link weight w in each iteration, the ISP's problem in [START_REF] Zhang | GreenTE: Power-Aware Traffic Engineering[END_REF] and the MCF problem in (8) will be solved to get their own optimal traffic distribution. Then the dual gap gap(w(k),

f (k), f(k)) = (i,j)∈E w ij (k)( t∈D f t ij (k) -f ij (k))
is applied as an optimality measure. Here γ k is the step size and (z) + = max(0, z).

If the dual gap is smaller than tolerance , the iteration will terminate with optimal link weights w * and traffic distribution f * . These link weights can be directly configured in routes as OSPF link weights. Algorithm 1 is converged because we apply the classic sub-gradient projection method [START_REF] Bertsekas | Nonlinear Programming[END_REF] to the dual of TE(φ, G, c, D) in [START_REF] Xu | One More Weight is Enough: Toward the Optimal Traffic Engineering with OSPF[END_REF]. Since the traffic matrix changes over time, the frequency of periodically computation and configuration may have an impact on network overhead and ROD performance. This is a major issue for our further investigation.

Data Forwarding under ROD

The packet under ROD mechanism is forwarded hop-by-hop along the destinationbased shortest paths, which is the same as in OSPF. The shortest paths are constructed from the optimal link weights derived from Algorithm 1. In case that there are multiple equal-cost shortest paths between the same OD pairs, the flow splitting ratios over these paths can be computed from Algorithm 2. Taking the optimal traffic distribution f * derived from Algorithm 1 as input information, Algorithm 2 first topologically sorts all nodes that are involved in data forwarding to a certain destination t, and then calculates the traffic splitting ratio τ (s, p, t) for each candidate next-hop denoted by p. The computational complexity of Algorithm 2 is O(N * (N + E)).

We mentioned the unequal traffic splitting ratios over ECMPs in Section 2. In hardware level, such traffic splitting scheme is usually realized through a hashbased mechanism [START_REF] Cao | Performance of Hashing-Based Schemes for Internet Load Balancing[END_REF]. Therefore, we can configure the hash table with different weights corresponding to the desired traffic splitting ratios.

Algorithm 2 Achieving the splitting ratios

Input the optimal traffic distribution f * for each t ∈ D do Define an empty node set V and an empty link set L V ← V ∪ {t} for each link (i, j) ∈ E do if i / ∈ V and f t * ij > 0 then V ← V ∪ {i} and L ← L ∪ {(i, j)} end if end for Do topological sorting on V to get the sorted node set V for each node s ∈ V (s = t) do τ (s, p, t) = f * t sp / (s,p)∈L f * t sp V ← V \{s} end for end for

Evaluation

In this section, we evaluate ROD with real and synthetic networks to show its effectiveness on achieving trade-offs between energy saving and performance. (a) Abilene Network

Experimental Setup

We resort to ns2 simulator [21] to explore the effectiveness of ROD on smalland large-scale topologies. For comparison, hereafter we refer to mechanisms minimizing MLU and energy consumption as MMLU and MEC, respectively. Topologies. The topologies used are summarized in Table 1. The router-level topology of Abilene is available at [START_REF] Zhang | s Abilene TM[END_REF]. For simplicity, we consider the two routers at Atlanta as a single node, the entire network thus has 11 nodes altogether. The Cernet2 is the worldwide largest pure IPv6 research network, which has 44 links with 10 Gbps for 8 core links and 2.5 Gbps for the rest. The Random topology is generated by GT-ITM [START_REF] Gt-Itm | [END_REF], whose capacity is set to 1 Gbps for each link. Traffic Matrices. For Abilene, we select a subclass of the online available matrices [START_REF] Zhang | s Abilene TM[END_REF], which are measured on March 1st, 2004. The traffic matrix for Cernet2 is generated by the gravity model [START_REF] Roughan | Experience in Measuring Backbone Traffic Variability: Models, Metrics, Measurements and Meaning[END_REF] based on aggregated link load collected from January 10th to 16th, 2010. We generate a sparse traffic matrix for Random through gravity model to achieve a light traffic load scheme. Energy Saving Assumptions. Since line-cards are considered to account for more than 40% of a router's total budget [START_REF]Power Management for the Cisco 12000 Series Router[END_REF], we thus focus on line-cards for energy saving, whose consumption in our evaluation is summarized in TABLE 2. We assume that unloaded line-cards can be automatically put into sleep mode and the time required to enter or wake up from sleep mode is negligible [START_REF] Nedevschi | Reducing Network Energy Consumption via Sleeping and Rate-Adaptation[END_REF].

Performance versus Energy Saving

In this subsection, we explore trade-offs that exist between performance and energy saving potential in ROD. MLU is usually a major concern for ISPs in 0:00 6:00 12:00 18:00 24:00 0 TE and thus employed here as an indicator of network performance. For energy saving indicator, we compute the amount of power consumption of line-cards in each simulation.

For each topology, we vary the green factor θ to investigate trade-offs between MLU and power consumption, which are plotted in Figure 2. The x-axis represents power consumption of the entire network and the y-axis represents the MLU. For ease of illustration, we use MEC as a benchmark and normalize the value of energy consumption of ROD. We first asterisk discrete points for a set of selected values of θ and then fit these points to achieve smooth curves.

The result for Abilene in Fig. 2(a) reveals that power consumption varies consistently with θ, whereas MLU decreases as θ increases. We also notice that, if the MLU threshold of Abilene network is relaxed a bit (e.g., from 16.8% to 17.5%), the power consumption will considerably lower down (e.g., from 1.25 to 1.05). Similar results also hold for Cernet2 and Random.

From the three sub-figures, we also notice two stages, 1) keeping θ increasing when it is larger than 10 can slightly bring down MLU but dramatically raises up the energy consumption, which we refer to as power-sensitive stage; 2) continuing to turn θ down when it is smaller than 0.1 will make a small contribution to energy saving at the cost of a sharp increase of MLU, which we regard as performance-sensitive stage. As both power-and performance-sensitive stages are undesirable for ISPs, we choose three typical values of θ between these two stages for the following evaluation, namely 0.1, 1 and 10.

In Figure 3 (a), we show how the green factor θ affects the energy saving potential of Abilene on March 1st, 2004. For each time interval, the power saving ratio is computed with the total power consumption of MMLU as a benchmark. The average energy saving ratio of ROD with θ = 0.1 is about 15%, which is very close to that of MEC and higher than the other two cases with larger θ. The curve with θ = 1 experiences severe oscillation since it can be easily affected by the changes in traffic matrix when equally considering minimizing MLU and power consumption.

Link Utilization

In this subsection, we evaluate the impact of ROD on link utilization that is denoted by f in Section 3. Using the Abilene traffic matrices collected for 24 hours, we first explore changes of MLU under each routing mechanism. We present the CDF of MLU of Abilene for a whole day in Figure 3 (b). Since the traffic is light, MLU is always under 40% for all cases. The curves for MMLU and MEC mechanisms act as a lower and higher bound, respectively. The three variations of ROD mechanism with different θ have slight difference in terms of MLU over temporal scale.

In Figure 4, we explore the utilization of all links for a single traffic matrix, where the x-axis represents the link indices. For Abilene, the traffic of MMLU is more evenly distributed over all links, since nearly 64.3% of the total 28 links achieve the largest utilization. However, MEC goes to the opposite side and concentrates the traffic on fewer links, leaving the minority of the links with much higher utilization. The curves under ROD mechanism with θ = 10 is similar to that of MMLU, whereas the one with θ = 0.1 is close to MEC, leaving the curve with θ = 1 taking the middle place. The cases for Cernet2 and Random are similar, therefore, we do not present Random result due to space limitation.

Packet Delay

In this subsection, we evaluate the propagation delay under ROD. Figure 5 shows CDF of packet delay in different routing mechanisms for Abilene and Cernet2 topologies. For Abilene, MMLU exhibits the higher bound of packet delay, whereas MEC acts as the lower bound. The reason lies in that MMLU may result in undesirable overlong paths in terms of hop counts in order to avoid the highly utilized links. For this reason, the reciprocal of green factor in ROD could be considered as a penalty on the unnecessarily long paths. Therefore, the variation of ROD with a smaller θ should have a lower packet delay, which is confirmed through the curves in Figure 5(a). Due to space limitation, we omit the discussion on Cernet2 and the similar results to Random topology.

Related Work

Gupta et al. [START_REF] Gupta | Greening of the Internet[END_REF] firstly propose an energy saving approach by shifting network interfaces or devices (e.g., routers) into sleep mode during idle periods. Nedevschi et al. [START_REF] Nedevschi | Reducing Network Energy Consumption via Sleeping and Rate-Adaptation[END_REF] investigate two approaches via sleep and rate adaption. The former approach enables line-cards to sleep between packet bursts while the latter can adjust devices to operate at low frequency when traffic load is light. Vasić et al. [START_REF] Vasić | Energy-Aware Traffic Engineering[END_REF] consider the above two approaches and present EATe to reduce energy consumption at the expense of increasing massage overhead of routers. In contrast, ROD mechanism is compatible with the current OSPF protocol and thus do not introduce unnecessary message cost.

Zhang et al. [START_REF] Zhang | GreenTE: Power-Aware Traffic Engineering[END_REF] have recently proposed an MPLS-based intra-domain traffic engineering mechanism, GreenTE, to maximize the number of links that can be put into sleep mode under given performance constrains. However, GreenTE requires excessive management control to achieve its goal because MPLS tunnels should be frequently set up and adjusted according to the elastic traffic. Panarello et al. [START_REF] Panarello | Energy Saving and Network Performance: a Trade-off Approach[END_REF] put forward a trade-off approach for performance and energy saving in access network. However, since devices in backbone networks consume the large majority of energy [START_REF] Tucker | Energy Consumption in IP Networks[END_REF], we thus focus on exploring trade-off that exists in backbone networks.

Conclusion

This paper presents Routing On Demand (ROD), which is an OSPF-based routing mechanism that can achieve trade-off solutions to energy-aware TE problem. We theoretically prove that a set of link weights always exists for each tradeoff in energy-aware TE objective, under which solutions (i.e., routes) derived from ROD can be converted into shortest paths and realized through OSPF. Evaluation results show that ROD can achieve different trade-offs between energy saving and performance in terms of Maximum Link Utilization (MLU) while maintaining better packet delay than that of energy-ignore TE. The compatibility of ROD with OSPF eases its deployment. Our future work includes investigating the overhead to realize ROD mechanism as well as the impact of link failures and traffic bursts.

Figure 1 .

 1 Figure 1. Optimal Routing in Various Cases

Figure 2 .

 2 Figure 2. Trade-offs between MLU and Energy Consumption for Different Topologies

Figure 3 .

 3 Figure 3. Simulation Results for Abilene on March 1st, 2004

Figure 4 .

 4 Figure 4. Sorted Link Utilization for Different Topologies

Figure 5 .

 5 Figure 5. CDF of Packet Delay for Different Topologies

Table 1 .

 1 Topologies for evaluation

	Network Category Nodes Links Flows
	Abilene Backbone 11	28	110
	Cernet2 Backbone 20	44	380
	Random Random 50	230	50

Table 2 .

 2 Power consumption of line-cards

	Line-card	Rate/Mbps Energy/W
	1-Port OC3	155.52	60
	8-Port OC3	1244.16	100
	1-Port OC48	2488.32	140
	1-Port OC192 9953.28	174

This work is supported by New Generation Broadband Wireless Mobile Communication Network of the National Science and Technology Major Projects (2012ZX03005001), NSFC Project (61170292, 60970104), 973 Project of China (2009CB320501), Program for New Century Excellent Talents in University and EVANS Project (PIRSES-GA-2010-269323).