MAPPING -- Measuring And Practically Predicting INternet Growth

Measuring and predicting growth in Internet addressing, routing complexity and energy usage

Overview

Over the past decade the Internet has moved from a well-hyped 'new thing' in the 1990s to become a central part of most first-world societies. Our increasing connectedness is enabling new modes of inter-personal, world-wide communication for individuals, businesses and governments. Yet the Internet faces a number of significant challenges.

The Internet's current “IP version 4” (IPv4) has almost exhausted the supply of addresses with which to route packets to new destinations [Hain05, Huston08], yet migration to an improved “IP version 6” (IPv6) addressing scheme is slow and poorly understood [Perset08]. Exhaustion of publicly routed IPv4 address space in the next few years is expected trigger a new marketplace for trading small and large blocks of existing IPv4 address space [Beck10], as companies (and entire countries) strive to remain connected while continuing to add internet-enabled devices. However, current models are inadequate for predicting the likely value and costs of this new market.

There is also growing demand for internet-related electrical energy world-wide – both in core infrastructure (service provider routers, switches and wired and wireless links) and end-user devices (such as PCs, laptops, home broadband gateways, 802.11-enabled access points, internet-enabled PDAs and cellular/mobile phones). However, current estimates of this end-user energy consumption are based on unwieldy manual surveys.

Lack of address utilisation models

The community lacks plausible models for the current use of (and future growth in demand for) internet addresses by devices attached around the Internet's “edge”. The use of IP addresses is neither homogeneous nor centrally controlled. The Internet Assigned Numbers Authority (IANA) periodically delegates large blocks of contiguous IP addresses (identified by address prefixes) to five geographically-arranged Regional Internet Registries (RIRs), who further subdivide and delegate to Internet Service Providers (ISPs) in each region. ISPs then allocate addresses (singly or in contiguous blocks) to their own customers. Although the RIRs know which address prefixes are allocated, we have no way to tell how many internet addresses are actually used at any point in time, or which are used intermittently. Some address prefixes are used sparsely, others are almost full [RFC3194].

IPv4 address space consists of allocated space (provided by RIRs to ISPs), routed space (address prefixes actually advertised as reachable by the inter-domain routing system), and occupied space (IP addresses actually being utilised). Allocated and routed space can be ascertained from RIR records and current inter-domain routing activity respectively. However, to say an address is occupied requires a measurement; for example it may

• respond to IP layer management query packets (“pings”);
• respond to a web request (SYN to port 80), either as a server would, or with an error;
• be observed participating in two-way packet exchange. (A one-way exchange is not sufficient evidence, as the source address may be “forged”.)

Public and independently verifiable tracking of estimated IP address utilisation levels will significantly improve society's ability to learn lessons applicable to the roll-out of IPv6 address allocation policies, guide regulators in understanding the future market in usable IPv4 address prefixes, and predict patterns of energy consumption around the Internet's edges. IANA and the RIRs provide public information on their overall prefix allocations. However, to date individual ISPs have had little regulatory requirement to collect or reveal the details of their actual address space utilisation (distinct from their address space allocations), and equally limited economic interest in doing so.

Selective probing and monitoring to estimate current utilisation

It is possible, but impractical, to establish utilisation by enumerating and actively probing all possible IPv4 addresses in allocated or routed space. For example, probing half the 2^32 IPv4 address space (roughly 2x10^9 addresses) at 500 probes per second would take around 50 days. However, this sampling period precludes building a picture of how individual IP addresses are used on a daily basis. In addition, probes may not be answered due to firewalls, temporary end-host outages or transient packet loss somewhere along the way.

Initial work by Heidmann et al has shown promising results by sampling only subsets of allocated IPv4 address space [Heid08]. Our goal is to develop and deploy improved techniques for intelligently sampling subsets of the IPv4 address space in a way that captures the essential utilisation patterns in hours or days rather than months. Frequent repetition of such sampling enables us to build large- and small-scale pictures of how utilisation changes over time.

Estimating the actual number of hosts

A crucial challenge remains the estimation of how many hosts are represented by a given public IP address. A single physical host may have multiple IP addresses – perhaps for redundant connectivity (multi-homing) or to support multiple virtual hosts each with their own IP addresses. Conversely, routers at the boundaries of home and enterprise networks may hide multiple hosts behind single IP address using Network Address Translation (NAT). Indeed, one response to the depletion of available IPv4 address space may be a period of significantly increased NAT deployment. Such information is rarely documented anywhere outside of organisation that owns the physical hosts and NAT-enabled routers. We will synthesise new techniques for estimating the degree to which public IP addresses are actually NAT’d addresses, and how many hosts may be hiding behind them.

Our project will not attempt to estimate the number of hosts never connected to the Internet.

Energy estimation

We will improve current lower bounds on estimates of total energy consumption relating to Internet-attached residential and office computing equipment. Current studies, such as [BA07], are typically based on sales of PCs or numbers of broadband subscriptions (ADSL or cable). Studies such as [Ketal01] combined these with manual surveys and audits of the number of hours per day devices are used, such as [DOE99, Wetal06]. These figures vary significantly from country to country, and vary with time as new services such as VoIP and VoD become common. Since such surveys are major undertakings, they are not performed frequently; [BA07] used data from the 10-year old (1997) study [DOE99]. Energy use of office equipment has been studied in an Australian context by [LHH09], again by means of sales data and surveys. A further limitation of manual surveys, which will be overcome by this project, is that modern computers have many low power modes.  A user may be able to report the number of hours per day for which a computer is powered on, but will not know the fraction of time that the machine is in a lower power state.

Our project will improve such energy use estimates by providing a tighter lower bound on the number of power-consuming devices turned on and active at a given time, and enable other organisations to use our new probing techniques at low overhead cost to themselves.

References

[BA07]	P. Bertoldi, B. Atanasiu, Electricity Consumption and Efficiency Trends in the Enlarged European Union, Technical report, Institute for Environment and Sustainability, European Commission Report EUR 22753 EN, 2007.
[Beck10]	M. Beckman, Beware the black market rising for IP addresses, InfoWorld, May 3rd 2010.
[DOE97]	US DOE. 1999, Residential Energy Consumption Survey (RECS): Household Energy Consumption and Expenditures 1997, DOE/EIA-0632(97), November, 1999.
[Hain05]	T. Hain, A Pragmatic Report on IPv4 Address Space Consumption, Internet Protocol Journal, Volume 8, Number 3, 2005.
[Heid08]	J. Heidemann, Y. Pradkin, R. Govindan, C. Papadopoulos, G. Bartlett, J. Bannister, Census and Survey of the Visible Internet (extended), Technical Report ISI-TR-2008-649, USC/Information Sciences Institute, February, 2008.
[Huston08]	G. Huston, The Changing Foundation of the Internet: Confronting IPv4 Address Exhaustion, Internet Protocol Journal, September 2008.
[Ketal01]	K. Kawamoto, J. G. Koomey, B. Nordman, R. E. Brown, M. A. Piette, M. Ting, A. K. Meier, Electricity used by office equipment and network equipment in the US, Energy, Volume 27, Issue 3, Page 255, 2001.
[LHH09]	M. Lane, A. Howard, S. Howard, The Energy Inefficiency of Office Computing and Potential Emerging Technology Solutions.  Issues in Informing Science and Information Technology, Volume 6, pp. 795-808, 2009.
[Perset08]	K. Perset, Internet Address Space: Economic Considerations in the Management of IPv4 and in the Deployment of IPv6, Directorate for Science Technology and Industry, OECD Ministerial Meeting on the Future of the Internet Economy, Seoul, Korea, 17-18 June 2008.
[RFC3194]	A. Durand, C. Huitema, The Host-Density Ratio for Address Assignment Efficiency: An Update on the H Ratio, RFC3194, Internet Engineering Task Force, November 2001.
[Wetal06]	C. A. Webber, J. A. Roberson, M. C. McWhinney, R. E. Brown, M. J. Pinckard, J. F. Busch, After-hours Power Status of Office Equipment in the USA, Energy, 31, pp. 2823-2838, 2006.