text:
# 1 Introduction

## 1 Introduction

In heavy ion reactions particle production at high transverse momentum is expected to result from parton scatterings with large momentum transfer. In n+n reactions these hard scatterings dominate particle production above $`p_T2`$ GeV/$`c`$ . Hard scattering in heavy ion collisions will occur in the early stage of the reaction, well before a quark-gluon plasma is expected to form. Thus, fast partons produced in hard scatterings interact with the extended medium that is subsequently produced in a heavy ion reaction. The interaction of partons with hot and dense nuclear matter leads to an energy loss of the partons. This parton energy loss is considered as a potential signature of a quark-gluon plasma formation since the energy loss in a medium of deconfined quarks and gluons is expected to be higher than in hadronic matter .

An observable consequence of parton energy loss is the suppression of hadron production at large transverse momenta relative to a baseline expectation in the absence of energy loss. The construction of this baseline necessarily relies on model assumption. For the description of hard scattering processes the nucleons of the two colliding nuclei can be approximated as incoherent superpositions of partons. In this picture the particle yields in a heavy ion reaction are expected to scale with the number $`N_{coll}`$ of inelastic nucleon-nucleon collisions, since the cross-section for hard processes is small. Thus, the results on neutral pion production are presented in terms of the following ratio of invariant yields $`Ed^3N/dp^3`$:

$$R_{AA}=\frac{E\frac{d^3N}{dp^3}(p_T)|_{AA}/N_{coll}}{E\frac{d^3N}{dp^3}(p_T)|_{nn}}$$
(1)
This ratio is usually denoted as the nuclear modification factor. In the absence of nuclear modifications to hard scattering $`R_{AA}`$ will be unity.

Calculations based on perturbative QCD are a second possibility for the construction of a baseline expectation. These calculations usually also phenomenologically model the multiple initial scatterings of the partons in a A+A reaction. By just comparing the hadron yield in A+A reaction with the scaled n+n reference, as in equation 1, the effect of multiple parton scattering is not taken into account. Multiple parton scattering can explain the enhancement of high-$`p_T`$ hadron production in p+A reactions relative to a $`N_{coll}`$-scaled n+n reference. This anomalous enhancement is usually referred to as the Cronin-effect. In order to fix the strength of initial parton scattering in the modeling of A+A reactions data for p+A reactions at the same energy are very important.

## 2 Neutral Pion Spectra at SPS and RHIC

The WA98 experiment at the CERN SPS and the PHENIX experiment at RHIC reconstruct neutral pions on a statistical basis via their decay into two photons. The photon detector LEDA of the WA98 experiment consists of 10.080 lead glass modules and covers the pseudorapidity interval $`2.3<\eta <3.0`$. After the last WA98 data taking in 1996 the WA98 lead glass detector was brought from CERN to the Brookhaven National Laboratory and is now part of the PHENIX experiment. PHENIX consists of two separate electromagnetic calorimeters: the lead glass detector (PbGl) and a lead-scintillator (PbSc) sampling calorimeter. Both detectors cover the pseudorapidity interval $`0.35<\eta <0.35`$. The PbGl and PbSc data were analyzed separately. Figure 1 shows the agreement of the final $`\pi ^0`$ spectra .

The number $`N_{coll}`$ of inelastic binary nucleon-nucleon collisions in WA98 and in PHENIX is determined within a Glauber model framework . The Glauber-model is based on a purely geometric picture of a nucleus-nucleus collision: Nucleons travel on straight-line trajectories and a collision between two nucleons takes place if their distance in the plane transverse to the beam axis is smaller than a certain value given by the inelastic nucleon-nucleon cross section. The inelastic nucleon-nucleon cross section increases from $`\sigma _{nn}30`$ mb at CERN SPS energies ($`\sqrt{s}=17.3`$ GeV) to $`\sigma _{nn}40`$ mb at the RHIC energy of $`\sqrt{s}=130`$ GeV.

The neutral pion yields in central Pb+Pb collisions at $`\sqrt{s_{nn}}=17.3`$ GeV and in central Au+Au collisions at $`\sqrt{s_{nn}}=130`$ GeV are shown in Figure 1 . The yields are normalized to $`N_{coll}^{WA98}=651\pm 65`$ and $`N_{coll}^{PHENIX}=905\pm 96`$, respectively. The measured $`\pi ^0`$ spectra are compared to results for nucleon-nucleon reactions. The n+n references is a parameterization that is based on an interpolation of existing data to the respective center-of-mass energy . One observes that the $`\pi ^0`$ spectrum in n+n reactions at the RHIC energy is significantly flatter than the corresponding spectrum at the CERN SPS energy. The curvature of the $`\pi ^0`$ spectrum in A+A reactions, however, changes only moderately when going from SPS to RHIC.

Figure 2 shows the ratio $`R_{AA}`$ as defined in equation 1. The PHENIX PbGl and PbSc results were averaged for this plot. A striking difference between the results for the SPS and RHIC energy can be seen. The ratio $`R_{AA}`$ for $`\sqrt{s_{nn}}=17.3`$ GeV is qualitatively in line with expectations from the Cronin effect: $`R_{AA}`$ increases with $`p_T`$ and the neutral pion yield increases stronger than $`N_{coll}`$ above $`p_T2`$ GeV/$`c`$. At $`\sqrt{s_{nn}}=130`$ GeV, however, $`R_{AA}`$ is basically flat. Moreover, $`R_{AA}`$ is significantly below unity over the entire $`p_T`$ range. Thus, high-$`p_T`$ neutral pion production at RHIC energies is suppressed compared to the $`N_{coll}`$-scaled n+n reference.

One can now replace the n+n reference by the $`N_{coll}`$-normalized $`\pi ^0`$ spectrum measured in peripheral A+A collisions. This is depicted in Figure 3. The number of binary nucleon-nucleon collisions for the peripheral samples are $`N_{coll}^{WA98}=30\pm 5`$ and $`N_{coll}^{PHENIX}=20\pm 6`$. Figure 3 indicates that the $`N_{coll}`$ normalized peripheral $`\pi ^0`$ spectrum at RHIC is very similar to the respective n+n spectrum. In contrast, the comparison of the SPS results in Figure 2 and Figure 3 shows that the shape of the $`\pi ^0`$ spectrum changes significantly when going from n+n to peripheral Pb+Pb collisions with $`N_{coll}30`$.

## 3 Comparison to pQCD calculations

A pQCD calculation from Wang described in  is compared to the central $`\pi ^0`$ spectrum for Pb+Pb collisions at $`\sqrt{s_{nn}}=17.3`$ GeV/$`c`$ in Figure 4a. In the range around $`m_Tm_02.5`$ GeV/$`c^2`$ the pQCD calculation overpredicts the experimental data by around 30%. In a recent publication also Lévai et al. compare their pQCD calculations to WA98 data . In agreement with Wang’s calculation they find that their pQCD calculation predicts more neutral pions at high $`p_T`$ than actually measured. Thus, one can conclude that a possible parton energy loss effect (”jet quenching”) is not ruled out at SPS energies.

Figure 4b shows a comparison of the PHENIX neutral pion spectrum in central Au+Au collisions with a pQCD calculation from Wang . The standard pQCD calculation without parton energy loss effects clearly fails to describe the data points. By introducing a parton energy loss parameter a reasonably description of the data can be reached. In  it is argued that when the expansion of the fireball is appropriately taken into account the energy loss of $`dE/dX=0.25`$ GeV/fm in an expanding system effectively corresponds to a much higher energy loss in a static system. This implies that the energy loss in the initial fireball produced in a A+A collision at RHIC is significantly higher than in cold nuclear matter.


format: text

text:
# Not Color Blind: Using Multi-Band Photometry to Classify Supernovae

## 1 Introduction

The study of supernovae (SNe) has greatly advanced in the last few years. Intensive and highly automated monitoring of nearby galaxies (e.g., Li et al. 1996; Treffers et al. 1997; Filippenko et al. 2001; Dimai 2001; Qiu & Hu 2001), wide-field, moderately deep surveys (e.g., Reiss et al. 1998; Gal-Yam & Maoz 1999, 2002; Hardin et al. 2000; Schaefer 2000), and cosmology-oriented, deep, high-redshift SN search projects (Perlmutter et al. 1997; Schmidt et al. 1998) now combine to yield hundreds of new SN discoveries each year. Ambitious programs that are currently planned or underway \[e.g., the Nearby Supernova Factory – Aldering et al. 2001; the Supernova/Acceleration Probe (SNAP) – Perlmutter et al. 2000; automated SN detections in Sloan Digital Sky Survey (SDSS) data – Vanden Berk et al. 2001; Miknaitis et al. 2001b; see also $`\mathrm{\S }4`$\] promise to increase these numbers by at least an order of magnitude.

SNe are heterogeneous events, empirically classified into many subtypes, with the main classification criteria based on spectral properties. Briefly, SNe of type II show hydrogen lines in their spectra while SNe of type I do not. Each of these types is further divided into subtypes, the commonly used ones including Ia, Ib, and Ic, as well as II-P, II-L, IIn, and IIb. See Filippenko (1997) for a thorough review and $`\mathrm{\S }2`$ for more details. It is widely accepted that SNe Ia are produced from the thermonuclear disruption of a white dwarf at or near the Chandrasekhar limit, while all other types of SNe (Ib, Ic, and II) result from the core collapse of massive stars.

While understanding SNe, their properties, and their underlying physics is of great interest, SNe are also useful tools in the study of various other important problems. SNe Ia are excellent distance indicators, and their Hubble diagram has been used to determine the local value of the Hubble constant (e.g., Parodi et al. 2000, and references therein). The extension of the Hubble diagram to higher redshifts ($`z1`$) probes the geometry and matter-energy content of the Universe (e.g., Goobar & Perlmutter 1995). Two independent groups using large samples of high-$`z`$ SNe Ia presented a strong case for a current acceleration of the Universe (Riess et al. 1998; Perlmutter et al. 1999; see Filippenko 2001 for a summary), consistent with a nonzero cosmological constant, $`\mathrm{\Lambda }`$. Subsequent work (Riess et al. 2001) based on a single SN Ia at $`z1.7`$ possibly shows the transition from matter-dominated deceleration to $`\mathrm{\Lambda }`$-dominated acceleration at $`z1`$. SNe II-P can also be used as primary distance estimators through the expanding photosphere method (EPM; Kirshner & Kwan 1974; Schmidt, Kirshner, & Eastman 1992; Schmidt et al. 1994), as was most recently demonstrated by Hamuy et al. (2001) and Leonard et al. (2002a,b). Leonard et al. (2002a; see also Höflich et al. 2001) suggest that distances good to $`30`$% ($`1\sigma `$) may be possible for SNe II-P by simply measuring the mean plateau visual magnitude, obviating the need for a complete EPM analysis unless a more accurate distance is desired. Hamuy & Pinto (2002) refine this technique, showing that a measurement of the plateau magnitude and the ejecta expansion velocity potentially yields a considerably smaller uncertainty in the derived distance.

SN rates as a function of redshift probe the star-formation history of the Universe, the physical mechanisms leading to SNe Ia, and the cosmological parameters (Jorgensen et al. 1997; Sadat et al. 1998; Ruiz-Lapuente & Canal 1998; Madau, Della Valle, & Panagia 1998; Yungelson & Livio 2000). SN rates are also important for understanding the chemical enrichment and energetics of the interstellar medium (e.g., Matteucci & Greggio 1986) and the intracluster medium (e.g., Brighenti & Mathews 1998, 2001; Lowenstein 2000; Gal-Yam, Maoz, & Sharon 2002).

Once discovered, the study of a particular SN, and its use as a tool for any of the applications above, is almost always based on spectroscopic verification and classification. The information extracted from SN spectra usually includes (but is not limited to) the SN type, redshift, and age (relative to the dates of explosion or peak brightness). Spectroscopic followup may not always be possible or practical. SNe, especially at high redshift, may be too faint for spectroscopy, even with the largest, 10-m-class telescopes currently available. Spectroscopy is also not practical if large numbers (hundreds or thousands) of SNe are detected within a relatively short time, as is expected to happen in the case of the SDSS southern strip (Miknaitis et al. 2001b; see also $`\mathrm{\S }4`$). Finally, spectroscopy is impossible for SNe discovered in archival data (Gal-Yam & Maoz 2000; Riess et al. 2001; Gal-Yam et al. 2002), which have long faded by the time they are found. The discovery of SNe in archival data is expected to become frequent as high-quality astronomical databases become larger and more accessible, especially with the development of projects such as ASTROVIRTEL (http://www.stecf.org/astrovirtel) and the National Virtual Observatory (Brunner, Djorgovski, & Szalay 2001).

The goal of the present work is to facilitate the scientific exploitation of SNe for which no spectroscopic observations exist. The obvious alternative for spectroscopy is multi-color broadband photometry. The potential utility of such an approach is demonstrated, in principle, by the use of the “photometric redshift” method to infer the redshift and type of galaxies and quasars that are too faint or too numerous to observe spectroscopically (e.g., Weymann et al. 1999; Richards et al. 2001). Applying a similar method to SNe is not straightforward since, unlike galaxies, the spectra of SNe vary strongly with type, redshift, and time. While photometric approaches to the study of faint SNe have been discussed before (Dahlén & Fransson 1999; Sullivan et al. 2000; Riess et al. 2001), no general treatment has been presented thus far.

In a recent paper, Dahlén & Goobar (2002, hereafter DG2002) tackle the issue of SN classification for the case of deep, cosmology-oriented, high-$`z`$ SN searches. Their treatment relies heavily on the particular observational setup used by these programs — i.e., the comparison of images obtained $`3`$–4 weeks apart, designed to detect SNe before, or at, peak brightness. As these authors show, this setup is strongly biased toward the discovery of SNe Ia. The main theme of DG2002 is the selection of the high-$`z`$ SNe Ia from an observed sample, using photometry of the host galaxies and the SNe themselves. For the particular observational setup they consider, DG2002 also wish to minimize the contamination of the sample by non-Ia SNe. To do this, they use the models of Dahlén & Fransson (1999) and demonstrate their ability to reject most non-Ia SNe based on their colors and lower brightness. However, the models used for the population of non-Ia SNe are based on many parameters and assumptions, such as the ultraviolet (UV) spectra, peak brightness, light curves, and relative fractions of non-Ia SNe, that are not precisely known even in the local universe, let alone at high redshift. While DG2002 seek only to identify high-$`z`$ SNe Ia detected by a particular observational setup, we present general methods that apply to all the major SN subtypes and can be used for a wide range of SN surveys, including searches that are similar to those described by DG2002.

Classification of SNe using broadband colors is such a complex problem that, as we show below, a full solution (i.e., deriving SN type, redshift, and age from a few broadband colors) is probably impossible. However we will argue here that the problem may be simplified. Type, redshift, and age need not all be determined simultaneously. Most SNe are associated with host galaxies that are readily detectable. One can therefore infer the redshift of the SN from that of the host, derived either from spectroscopy (that may be obtained long after the SN has faded) or using a photometric redshift. In fact, for SNe that are detected in well-studied parts of the sky, the redshift information often already exists. Gal-Yam et al. (2002) recently demonstrated this with SNe they discovered in archival Hubble Space Telescope (HST) images of well-studied galaxy-cluster fields. Five of the six apparent SNe they found (and all of those clearly associated with a host) had redshift information in the literature. For the majority of SNe, the redshift can thus be obtained from observations of the host, and treated as a known parameter.

In the absence of a spectrum, the SN age may sometimes be revealed by measuring the photometric light curve of the event. Admittedly, such followup may still pose a problem for faint or very numerous events, and is generally not possible for archival SNe (see Riess et al. 2001 for an exception). However, for many of the scientific uses of SNe (e.g., the derivation of SN rates), the age of each event is immaterial.

Determination of the type of a SN is crucial for most of the applications discussed above. The SN type can be securely determined only from observations of the active SN itself. While some information can be gleaned from the host (e.g., elliptical galaxies are known to contain only SNe Ia), this information is limited and such reasoning may not hold at high redshifts. We therefore concentrate our efforts on using multi-color broadband photometry to classify SNe.

## 2 Method

Since we want to constrain the type of a SN with an arbitrary (but known) redshift, it is not simple to utilize broadband photometry; K-corrections for SNe of all types, and at all ages, are currently unknown. Instead, we have compiled a large spectral database of nearby, well-observed SNe. These spectra are used to calculate synthetic broadband colors for various SN types through a given filter set at a given redshift. The temporal coverage of our compilation allows us to draw paths in color space which show the time evolution of each SN type. Inspecting the resulting diagrams, one can then look for regions which are either populated by a single type of SN, or that are avoided by various SN types. The observed photometric colors of a candidate SN with a known redshift can then be plotted on the relevant diagrams, and constraints on its type and age may be drawn. As we show in $`\mathrm{\S }3`$, the type of a SN can sometimes be uniquely determined. When this is not the case, the type may still be deduced by supplementing the color information with other available data on the SN, such as constraints on its brightness, and information (even if very limited) on its variability (e.g., whether its flux is rising or declining).

### 2.1 Supernova Subtypes

Our SN classification method is based on colors, determined by the spectral energy distribution (SED) of each event. By definition, such a method can differentiate only between SN subtypes with unique spectral characteristics. Hypothetically, two SNe with very different photometric properties (e.g., light curves, peak magnitudes), but having similar SEDs at all ages, would not be distinguished by our method. The SN classification scheme we adopt needs, therefore, to rely only on spectral properties. Fortunately, the common classification of SNe (see Filippenko 1997 for a review) is mostly based on their spectra, with one notable exception which we discuss below.

It is customary to divide the SN population into two main subgroups: type II SNe, which show prominent hydrogen lines in their spectra, and type I SNe, which do not (Minkowski 1941). Type I SNe are further divided into type Ia whose spectra are characterized by a deep absorption trough around $`6150`$ Å, attributed to blueshifted Si II $`\lambda \lambda `$6347, 6371 lines, type Ib that show prominent He I lines, and type Ic that lack both Si II and He I (e.g., Matheson et al. 2001, and references therein).

Type II SNe are divided (e.g., Barbon, Ciatti, & Rosino 1979; Doggett & Branch 1985) into two subclasses according to their light-curve shape: SNe II-P show a pronounced plateau during the first $`100`$ d of their evolution, and SNe II-L decline in a linear fashion in a magnitude vs. time plot, similar to SNe I. Further studies (e.g., Filippenko 1997) show that SNe II-P have characteristic spectra, with the H$`\alpha `$ line showing a P-Cygni profile. On the other hand, SNe II-L have not been well characterized spectroscopically, and the best spectroscopically studied events (SNe 1979C and 1980K) are considered to be photometrically peculiar (“overluminous”; Miller & Branch 1990) relative to other SNe II-L. During the 1990s, the focus in studies of SNe II shifted from photometry to spectroscopy. Two new subtypes have emerged. SNe IIn show narrow H$`\alpha `$ emission (e.g., Schlegel 1990; Filippenko 1997, and references therein), and SNe IIb are transition objects that first appear as relatively normal SNe II, but evolve to resemble SNe Ib (Filippenko 1988; Filippenko, Matheson, & Ho 1993; Matheson et al. 2001, and references therein). For our study, only SN subtypes with well-defined spectral properties are meaningful. We therefore consider henceforth only SNe II-P, IIn, and IIb as subtypes of the SN II population. SNe IIn and IIb are probably a large fraction of the SN population that was previously classified as type II-L based only on their light-curve shape (approximately half of the SN II population, e.g., Cappellaro et al. 1997). Reviewing the latest spectral databases available to us, we estimate that most of the SNe II discovered by current surveys belong to the spectroscopically defined subtypes II-P, IIn, and IIb (see below).

SNe are a veritable zoo, with many peculiar and even unique events, from luminous hypernovae (e.g., SN 1998bw — Galama et al. 1998; Patat et al. 2001; SN 1997cy — Germany et al. 2000; Turatto et al. 2000; SN 1997ef — Iwamoto et al. 2000; Matheson et al. 2001) to faint SN 1987A-like events (e.g., Arnett et al. 1989, and references therein), and SN “impostors” (e.g., Filippenko et al. 1995a; Van Dyk et al. 2000, and references therein). Currently, we limit our discussion to SN types that are not extremely rare, and are well-defined and well-characterized spectroscopically. Assuming that the SNe reported in the IAU Circulars are representative of the SN population that is discovered by current programs, we estimate that, collectively, the well-defined subtypes we consider (Ia, Ib, Ic, II-P, IIn, and IIb) constitute at least 83%, and probably more, of the entire population.

For instance, we consider all the SNe that were discovered during the year 2000 and whose type was either reported in IAU Circulars, or alternatively could be constrained by data available to us. Among 110 such events, there were 54 type Ia, 5 type Ib, 5 type Ic, 8 type IIn, one type IIb, two peculiar SNe Ia, one peculiar SN Ib, and 34 events which were reported just as “type II.” Using available spectra or data reported in the IAU Circulars, we learn that of the latter 34 events, 18 show a P-Cygni profile in H$`\alpha `$, typical of SNe II-P, 13 events may or may not belong to the II-P, IIn, or IIb subtypes, and 3 events are definitely not II-P, IIn, or IIb events. Hence 91 events (83%) belong to our spectroscopically defined SN sample (types Ia, Ib, Ic, II-P, IIn, and IIb), 13 events (12%) may or may not be of these types, and just 6 events (5%) are known to be of types not included in our database. It is therefore likely that analysis based on our database will be relevant to the large majority of SNe discovered by current programs. This is probably also true for future programs that will use similar search methods. We are aware that a large population of intrinsically faint SNe (e.g., SN 1987A-like) may be underrepresented in current SN statistics. Analysis of future surveys that will be sensitive to such events may require their inclusion in the spectral database.

### 2.2 Spectral Database

The core of our classification algorithm is the spectral database: a compilation of optical spectra of nearby SNe. Most of the these spectra were obtained with the Shane 3-m reflector at Lick Observatory. The typical resolution is better than $`15`$ Å (full width at half maximum), and the majority of the data used cover the range 3200–10000 Å. Some spectra with narrower coverage (approximately 4000–8000 Å) are also used. All spectra were either obtained at the parallactic angle (Filippenko 1982), or calibrated by simultaneous photometry, to ensure that spectral shape distortions due to wavelength-dependent atmospheric refraction are not significant. Telluric lines were removed, generally through division by the spectrum of a featureless star. According to the Galactic coordinates of the observed SN, the spectra were corrected for Galactic reddening, using the maps of Schlegel, Finkbeiner, & Davis (1998) and the extinction curve of Cardelli, Clayton, & Mathis (1989).

The working edition of the database was constructed in the following manner. For each of the well-defined SN subtypes mentioned above, we have selected a prototype. The main criterion was the availability of spectra with wide wavelength coverage and multiple epochs. In addition, a few complementary spectra of other events were included in order to verify consistency and fill gaps in the temporal evolution, when needed. Table 1 lists the SNe whose spectra constitute our database, with the prototypical event for each subtype listed first.

We have specifically avoided events that were known to either suffer considerable extinction, or to be otherwise peculiar. For SNe Ia, peculiar (overluminous, SN 1991T-like, or underluminous, SN 1991bg-like) events are rather well characterized, and may be quite common, at least in low-redshift environments (Li et al. 2001a). Our main database includes only spectra of normal SNe Ia, but we examine the effects of peculiar SNe Ia in $`\mathrm{\S }3.4`$ below.

All spectra were de-redshifted according to the host-galaxy redshift taken from the NED database. After redshifting the spectra again to a chosen redshift (see below), the telluric features were re-applied before deriving synthetic colors.

### 2.3 Color-Color Diagrams

Using our spectral database, we calculate the synthetic colors of SNe at a chosen redshift through the Johnson-Cousins $`UBVRI`$ (Johnson 1965; Cousins 1976; see Moro & Munari 2000 for details), Bessell $`JHK`$ (Bessell & Brett 1988), and SDSS $`ugriz`$ (Fukugita et al. 1996; Stoughton et al. 2002) filter systems. If a filter’s bandpass is not fully covered by a SN spectrum, the flux in the missing spectral region is extrapolated linearly using the median value of the spectrum. Each calculated magnitude that includes such an extrapolation is assigned an error equal to the amount of flux in the extrapolated part of the spectrum, thus providing a conservative error estimate. The resulting synthetic photometry is then displayed on color-color diagrams. Note that in all the plots we present, the ordinate and abscissa are composed of colors consisting of adjacent bands (e.g., $`UB`$ vs. $`BV`$, $`BV`$ vs. $`VR`$ etc.). Since most of the spectra in our database have a wide wavelength range, error bars will hence generally appear only on one axis.

In the following section we present such diagrams, discuss their use in the classification of SNe discovered by various programs, and derive a few general rules. Note that the choice of colors that gives the best SN type differentiation, apart from the obvious dependence on the filter system used, also depends on redshift. For optimal results, for each SN (having a known redshift and some observed colors) one needs to search for color-color diagrams that give the maximum information content. Obvious space limitations allow us to present below just a few representative examples of such plots. Similar plots for arbitrary values of $`z`$ may be obtained from our website (http://wise-obs.tau.ac.il/$$dovip/typing).

## 3 Results

### 3.1 Comparison with Available Photometry

In Figure 1, we compare our data on SNe Ia to template colors of normal SNe Ia compiled by Leibundgut (1988). One can see that our calculated colors follow the expected path in color space, with a small scatter ($`0.2`$ mag), consistent with the previously measured dispersion in SNe Ia colors (e.g., Tripp 1998; Phillips et al. 1999, and references therein). Since our spectral database includes spectra of SN 1994D, which was somewhat bluer at early times than average SNe Ia (Richmond et al. 1995), our treatment covers an even wider variety in the colors of early SNe Ia. From this plot, we can estimate the expected width of color-color paths for normal SNe Ia to be $`0.2`$–0.3 mag.

Note that SNe Ia follow a complex curve in color space, with a distinct turn-around point $`30`$ d after peak brightness. The underlying spectral evolution is nontrivial. Like most SNe, the continuum slope of early SNe Ia is very blue, and becomes redder as the SN grows older. This process is dominant during the first weeks of SN Ia evolution, but is later countered by the emergence of strong emission lines in the blue part of the spectrum (restframe 4000–5500 Å). The line-dominated spectrum results in unique colors for late-time ($`t>100`$ d) SNe Ia (e.g., Figure 3, below).

In Figure 2 our results for SNe II-P are plotted against the observed photometry of the recent, well-observed SN 1999em. It can be clearly seen that the results agree perfectly up to around 70 d past maximum brightness, where a bifurcation appears in our calculated color path. Our spectral data for SNe II-P is based on three different events (SNe 1992H, 1999em, and 2001X). The three points that have considerably lower $`UB`$ values (at 110, 127, and 165 d) have all been calculated from the spectra of SN 2001X, which up to that age was consistent with the other SNe II-P used. This demonstrates the well-known variety of late-type spectra of SNe II (Filippenko 1997). In subsequent plots, we retain both branches of “old” SNe II-P (with the one derived from spectra of SN 2001X marked, when significantly different, in a darker shade), and treat the color space bounded by them as a possible location for such SNe.

Contrary to SNe Ia, the color path of SNe II-P is quite smooth. The underlying spectral evolution is driven mostly by the change in the continuum slope, from very blue at early ages, growing redder with time (e.g., Filippenko 1997). Late-time ($`t>100`$ d) spectra become increasingly dominated by strong and broad emission lines, especially H$`\alpha `$, that give SNe II-P their distinct late-time colors (see, e.g., Fig. 3, below).

### 3.2 Zero-Redshift Diagrams

In Figure 3 (top panel), we show the color paths of all types of SNe at zero redshift in $`UB`$ vs. $`BV`$. One sees that many SNe before maximum light are blue, with $`BV<0.3`$ mag. While most young SNe II have $`UB0.6`$ mag, young SNe Ia have bluer $`BV`$ colors ($`0.1`$ mag) but redder $`UB`$ colors, around $`UB=0.4`$ mag. It is also evident that old ($`>100`$ d) SNe Ia have unique colors ($`BV<0.4`$ mag, $`UB>0.5`$ mag), as do some of the SNe II-P (ages 19–100 d) which have the reddest colors of all SNe. The arrow shows the reddening effect corresponding to $`A_V=1`$ mag of extinction, assuming the Galactic reddening curve of Cardelli et al. (1989). One can see that the unique colors of young ($`t<12`$ d) and very old ($`t>100`$ d) SNe Ia cannot be masked even by significant reddening in their host. Furthermore, we note that high extinction values are rare for SNe Ia. For example, only 3 among 49 SNe Ia ($`6\%`$) studied by the CfA and Calán/Tololo programs, and presented in Riess et al. (1999), have $`A_V>1`$ mag. Conversely, because reddening works only in one direction, some candidates with appropriate observed colors can be uniquely determined to be SNe Ia.

However, the center of the diagram is populated by SNe of all types. For example, a zero-redshift SN, of unknown type, with colors of $`UB=0.2`$ mag, $`BV=0.5`$ mag, would be impossible to classify based on these colors only. But the middle panel of Figure 3 shows that if one examines an additional color, such as $`VR`$, this degeneracy can be partly lifted. For the same $`BV=0.5`$ mag, there is a spread in $`VR`$ that can shed some light on the SN type. A value of $`VR0`$ mag would favor a type Ia classification, while a positive value would suggest one of the core-collapse types. Addition of an $`RI`$ measurement (Fig. 3, bottom panel) would narrow the options even further, since in this color, at this redshift, different types have distinct values, from the bluest SNe Ia to the reddest types (Ib, Ic, and II-P). Looking at the reddening vectors in the middle and bottom panels of Figure 3, we again note that only heavy extinction ($`A_V>1`$ mag) can move SNe Ia into color regions populated by core-collapse SNe.

Before we proceed, we briefly comment on the effects of host-galaxy contamination. Since our approach assumes the redshift of a given SN is a known parameter, and this is commonly available through the observation of the host galaxy, some data on the galaxy should exist. It should therefore generally be possible to subtract the galaxy’s light from the SN photometry. To study the effect of non-subtraction of host-galaxy light, or imperfect subtraction, we parameterize the amount of the contaminating galactic flux, at a given epoch, by the ratio $`C=F_{galaxy}/F_{SN},`$ where $`F_{galaxy}`$ and $`F_{SN}`$ are the mean flux of the host galaxy and SN spectra, respectively, calculated over the wavelength range of the spectrum of the SN. We consider contamination as negligible, when it is not likely to make one type of SN look like another. First, we find that for all types of SNe and hosts, when $`C<0.1`$ the effect of contamination is indeed negligible. For young SNe Ia, the worst-case scenario would be the contamination by a red elliptical host that could make them look like redder core-collapse SNe. When observed in restframe blue colors (e.g., $`UBV`$), this effect becomes significant only when $`C1`$, but if red bands (e.g., $`VRI`$) are used, contaminated SNe Ia attain colors similar to those of the core-collapse population already at $`C=0.5`$. The opposite effect (i.e., of bluer host galaxies on red core-collapse SNe) is much weaker, so contamination by spiral hosts is unlikely to mix core-collapse SNe with young SNe Ia. Only heavy contamination ($`C>1`$) by a very blue, star-forming host galaxy can make a red SN II-P appear similar to a bluer SN Ia on a $`UBV`$ color-color diagram. In redder bands (e.g., $`VRI`$), even this extreme case causes negligible shifts in color. We conclude that if the host galaxy light has been subtracted, at least roughly, from the measured SN photometry, residual contamination has no significant implication. A large contribution from an underlying host (e.g., with a flux similar to that of the SN itself) that has not been removed may mask blue SNe Ia as core-collapse events, but is unlikely to make red core-collapse events appear as SNe Ia. In the discussion below, we therefore neglect contamination of the SN photometry by light from the underlying host galaxy.

### 3.3 High-Redshift Diagrams

With increasing redshift, the available spectral information shifts to longer-wavelength filters. The top panel of Figure 4 demonstrates how well SNe Ia can be differentiated from other types at $`z=0.1`$ on a $`VR`$ vs. $`RI`$ diagram. On the $`RI`$ axis the only SNe with negative values are SNe Ia. They are also the only type with $`VR`$ color greater than 0.6 mag while $`RI`$ is smaller than 0.3 mag. During most of the temporal evolution of SNe Ia, their distinction from other types is practically unaffected by host galaxy dust reddening, as can be seen from the vector plotted (the reddening is calculated in the SN rest frame).

The middle panel of Figure 4 shows a similar diagram computed at $`z=0.5`$. Classification is obviously more difficult. Still, SNe II-P (including “SN 2001X-like,” see $`\mathrm{\S }3.1`$) at ages above 100 d have $`RI`$ values higher than SNe of other types (at all ages). Close to peak flux, SNe Ia have $`VR`$ colors of a few tenths of a magnitude bluer than other types, and again, this distinction is not sensitive to reddening. Even where all types seem to mingle, at $`RI0.7`$ mag and $`VR1.1`$ mag, SNe Ia and II-P have $`VR`$ values that are 0.2 mag higher than other types. Should one of these types be rendered unlikely by other data, such as a SN that is too bright to be a SN II-P, the classification can become unique or nearly so. For example, SNe II-P can be unambiguously identified by their light curves; no other SN type has a roughly constant $`VRI`$ brightness over such a long period. In principle, two $`V`$-band (restframe) observations separated by, say, 30 d can unambiguously identify a SN II-P.

At redshifts higher than 0.6, the $`V`$ band samples the restframe UV, not covered by our spectral database. Thus, only one color ($`RI`$) remains in the Johnson-Cousins system. The SDSS filter system has 3 filters ($`r`$, $`i`$, and $`z`$) in the approximate range covered by the $`R`$ and $`I`$ filters, but extending farther into the red by $`1000`$ Å. Using this system, we can extend our analysis to higher redshifts. This is demonstrated in the bottom panel of Figure 4 for SNe at $`z=0.75`$. Again, late-time SNe II-P are significantly redder than other types ($`ri>1.5`$ mag and $`iz>1`$ mag), while early-time SNe Ia are significantly bluer ($`ri<1`$ mag and $`iz<0.2`$ mag), and remain so even in the presence of significant reddening by dust. At later times (over two months), SNe Ia escape from the vicinity of other types and reach $`ri`$ values above 1.2 mag. SNe IIn at this redshift appear to be isolated from other types.

As we move even farther up the redshift scale the use of infrared (IR) filters is required. Between $`z=0.8`$ and $`1.3`$, classification would require a combination of optical and IR photometry. Figure 5 (top panel) shows that at $`z=1`$, SNe Ia have distinct blue colors ($`IJ<2`$ mag and $`JH<0.1`$ mag) at almost all ages, SNe II-P develop very red $`IJ`$ colors ($`>2.8`$ mag) two months after peak, while SNe Ib and Ic are the only ones that have $`JH`$ colors that are redder than $`0.7`$ mag. As before, these distinctions are hardly affected by extinction. Between $`z=1.3`$ and 2.5 our spectra shift into the region covered by the Bessell $`JHK`$ filters. In the bottom panel of Figure 5 ($`z=1.5`$), one can see that SNe Ia have generally lower $`JH`$ colors ($`<0.5`$ mag), except between ages of one to two months, shared perhaps by very early type IIn, II-P, and Ic events. SNe Ib and Ic are the only objects to have both $`JH`$ and $`HK`$ above unity.

The use of synthetic colors, calculated from spectra of local SNe, to classify high-$`z`$ events, assumes that SN spectra do not evolve strongly with redshift. The similarity, to a first approximation, between the spectra of distant SNe Ia and their local counterparts has been demonstrated (Riess et al. 1998; Coil et al. 2000). However, for all other types of SNe, high-quality spectra of distant ($`z>0.1`$) events are largely unavailable. Since we use synthetic broadband colors, only significant evolution in either the spectral slope or strong emission or absorption features will influence our classification method. Nevertheless, this is a caveat that must be addressed once spectra of distant core-collapse SNe become available.

### 3.4 Peculiar Type Ia SNe

We now examine the colors of peculiar SNe Ia and their implication for our classification method. Following the same approach used earlier, we have compiled spectra of the most extreme varieties of peculiar SNe Ia: overluminous (SN 1991T-like; e.g., Filippenko et al. 1992a) and underluminous (SN 1991bg-like; e.g., Filippenko et al. 1992b) objects, as well as spectra of SN 2000cx, a unique SN Ia that may be considered a subtype of its own (Li et al. 2001b). Table 2 provides observational details for these objects.

Inspecting Figure 6 (top panel), which shows the $`UB`$ vs. $`BV`$ colors of the various SN Ia subtypes at zero redshift, we see that, although the paths of peculiar SNe Ia in color space are different from those of “normal” SNe Ia, they populate the same general region. On the other hand, in the middle panel of Figure 6, showing $`VR`$ vs. $`RI`$ colors at zero redshift, one can see that underluminous SNe Ia have significantly larger $`RI`$ values (by 0.2–0.6 mag) than those of all other SNe Ia, and are therefore liable to mix with the redder core-collapse population. This is illustrated in the bottom panel of the same figure, where indeed, underluminous SNe Ia at early ages (prior to $`60`$ d) cannot be distinguished from core-collapse SNe. Later in their evolution, these events acquire unique colors ($`VR<0.2`$ mag, $`RI>0.3`$ mag) that are different from all other types of SNe.

As SN 1991T-like and SN 2000cx-like events are almost always bluer than “normal” SNe Ia, they are generally easier to distinguish from core-collapse SNe, and pose no special problem in our analysis. SNe Ia of the underluminous, redder, SN 1991bg-like variety are hard to distinguish from core-collapse SNe at early ages, and may be lost in color-based classification. This problem is quite limited at low redshift, where underluminous SNe Ia are rare ($`16`$% of the SN Ia population; Li et al. 2001a), and may be totally negligible at higher redshifts where, empirically, SN 1991bg-like events have not been found at all (Li et al. 2001a).

### 3.5 Applications

#### 3.5.1 Distinguishing Between Type Ia and Ic SNe at High Redshift

High-redshift SN search programs that focus on finding SNe Ia for use as distance indicators encounter the problem of sample contamination by other SN types, especially a luminous variety of SNe Ic (Riess et al. 1998; Clocchiatti et al. 2000). The problem is two-fold. First, unwanted non-Ia SNe take up precious telescope resources for followup spectroscopy. Second, when only low signal-to-noise ratio spectra of faint, high-$`z`$ events are available, luminous SNe Ic may masquerade as SNe Ia. The latter problem is acute at high $`z`$, since at these redshifts the SN Ia hallmark (the Si II $`\lambda 6355`$ trough) is shifted out of the optical range, and SNe Ic spectra lack the telltale H or He lines that distinguish SNe II and SNe Ib, respectively. Spectra with high signal-to-noise ratios can provide definitive classifications (Coil et al. 2000), but these are time-consuming to obtain.

¿From Figure 7, one sees that color information may help, at least partially, to alleviate this problem. We confirm and quantify the well known “rule of thumb” (e.g., Riess et al. 2001): SNe Ic are red compared to SNe Ia at a similar redshift. One can see that, for SNe at ages that are relevant for high-$`z`$ search programs, designed to discover SNe near peak brightness, SNe Ia are typically 0.5 mag bluer in $`ri`$ than SNe Ic, well above the typical effects of reddening. While it is true that rising (pre-maximum) SNe Ic have colors similar to those of older ($`2`$ weeks past maximum) SNe Ia, even the most basic variability information (e.g., whether the object is rising or declining) breaks this degeneracy. Figure 7 also illustrates the fact that most of the information at this redshift can be obtained from the $`ri`$ color alone, and the inclusion of $`z`$-band information does not appear to be cost-effective.

#### 3.5.2 Classifying One of the First SDSS SNe

SN 2001fg was the third SN reported from SDSS data. This event was discovered on 15 October 2001 UT by Vanden Berk et al. (2001) with $`g=19.20`$, $`r=17.87`$, and $`i=18.17`$ mag. Inspecting the color-color diagram calculated for the appropriate redshift ($`z=0.0311`$, see below), one can see (Fig. 8) that the type and approximate age of the SN candidate can be deduced. The diagram clearly indicates this is a SN Ia, around one month old. Followup spectra by Filippenko & Chornock (2001) using the Keck II 10-m telescope reveal that the object is indeed a SN Ia, at $`z=0.0311`$. The spectrum is similar to those of SNe Ia about two months past maximum brightness. This age, at the time of the spectral observation (18 November UT), implies an age around one month past maximum brightness at discovery, confirming our diagnosis. A fully “blind” application would have, of course, required an independent photometric or spectroscopic redshift for the SN host galaxy.

## 4 Future Prospects and Conclusions

The method presented here can become significantly more powerful when more observational data become available. Faint, high-$`z`$ SNe are usually observed at optical wavelengths (i.e., $`V`$, $`R`$, or $`I`$ bands). In order to use these bands for classification, knowledge of the restframe UV spectrum is required. Currently, UV spectra are available for only a handful of objects, while methods like those discussed here require multi-epoch coverage of several objects for each SN subtype.

Further characteristics of the various SN types, most notably the absolute peak magnitudes and their scatter for every SN type, the typical light curves, and the relative rates of the different types, would also be useful. With such data in hand, one could use the limiting magnitude of a survey to calculate, for each SN type, at what epochs it is bright enough to be observed, thus removing some degeneracy in the classification. A further enhancement could be introduced to deal with the regions in color space that are populated by several different SN types. Using the typical light curves and known peak magnitudes for all types, and the relative rates, one could calculate the amount of time a SN of a certain type spends within a region and deduce the likelihood that an observed event belongs to a particular type. As already mentioned in $`\mathrm{\S }1`$, work along these lines has been presented by DG2002, who replace missing observational data with rough estimates or models.

SNe are generally discovered by their variability. However, the tools developed in this paper may enable one to detect SNe by their colors alone. Indeed, such methods have recently been discussed for the detection of another kind of transient phenomenon — gamma-ray burst afterglows (Rhoads 2001). Multi-color wide-field surveys (e.g., Becker et al. 2001; Jannuzi et al. 2001; SDSS — York et al. 2000) that are either planned or already underway may be used to discover large numbers of SNe using similar methods. To illustrate this point, we plot in Figure 9 the locations of SNe of all types at $`z=0.2`$, together with a polygon within which fall the vast majority of stars, asteroids, cataclysmic variables, Cepheids, and quasars, as discussed by Krisciunas, Margon, & Szkody (1998). Except for late-time SNe Ic, all SNe have lower $`iz`$ values and higher $`ri`$ values than these objects. Similar results are obtained for the SN population at $`z=`$ 0–0.3, the redshifts of SNe probed by the SDSS. This demonstrates the feasibility of color selection of SNe, a method which may emerge as an invaluable resource when applied to upcoming, large data sets.

An exciting application of the methods presented in this paper would be the study of SNe discovered in the SDSS southern strip. During the months of September to November, when the primary target of the SDSS, the north Galactic pole, is not visible, the SDSS telescope observes parts of the sky near the south Galactic pole. The so called “south equatorial strip” is a patch of sky that will be imaged repeatedly during the 5-year planned operations of the survey. According to the SDSS website (http://www.sdss.org/documents/5yearbaseline.pdf), this 270 square degree area will be imaged $`19`$ times during the 5-year period, or about 4 times each fall, on average. Assuming that this sampling enables the discovery of all SNe that occur during the $`3`$ months this strip is imaged each year, for five years, the total surveyed area is $`270\times 3\times 5`$ deg<sup>2</sup>-months, or 337.5 deg<sup>2</sup>-years. Pain et al. (1996) have measured a SN Ia rate of 34 per year per square degree in the magnitude range $`21.3R22.3`$, and the limiting magnitude of the SDSS images in this band is given as $`r=22.5`$ mag. We would then expect some 2300 SNe Ia each year or a total of over 11,000 SNe Ia in this strip. The numbers of SNe of all types (not just Ia) will undoubtedly be even larger. Miknaitis et al. (2001b) report that a systematic search for SNe in these data is underway, and the first SNe have already been reported (Miknaitis et al. 2001a; Rest, Miceli, & Covarrubias 2001; Miknaitis & Krisciunas 2001).

This huge expected dataset, which may contain an order of magnitude more events than all previously known SNe, all with five-band photometry and possibly some variability information, offers an unprecedented resource for SN studies. As an example, SN rates, based on thousands of events, can be computed as a function of SN type, host-galaxy morphology, and redshift. However, it is clear that obtaining spectra for thousands of faint SNe each fall is not feasible. Photometric classification could therefore be a valuable option. The SDSS supplies five-band information, along with ready-made tools for the derivation of photometric redshifts for all host galaxies, and spectral identification for part of the brighter ones. This makes our approach of using the SN photometry for classification, assuming that the redshift is known, even more appropriate. Since no followup is required, such an analysis need not be done in real time — in principle, it may even be carried out long after the project is complete, and all the data are publicly available.

In summary, we have presented a method for the classification of SNe, using multi-color broadband photometry. We have shown that the type of a SN may be uniquely determined in some cases. Even when this is not the case, constraints on the type may still be drawn. In particular, SNe Ia may be distinguished from core-collapse SNe during long periods in their evolution, for most of the redshifts and filter combinations studied. Finally, we have demonstrated the application of our method to a recently discovered SN from the SDSS, and we have shown how this technique may become a valuable tool for the analysis of the large SN samples expected to emerge from this and other programs that are already active or will begin soon. This work proves that spectroscopic followup is not always a prerequisite for SNe to be a valuable scientific resource, and lays the foundations for the exploitation of large SN samples for which such followup may not be possible.

We thank the many people in A.V.F.’s group at the University of California, Berkeley (especially A. J. Barth, R. Chornock, L. C. Ho, and J. C. Shields) who, over the years, helped obtain and calibrate the spectra that constitute much of the dataset used in this study. We are grateful to A. Fassia, M. Hamuy, and Y. Qiu for supplying us with digital copies of their spectra of SN 1998S, 1999ee, and 1996cb, respectively. B. Leibundgut generously provided help with SN light curves, and we thank D. Branch, E. O. Ofek, G. Richards, and O. Shemmer for useful suggestions. We acknowledge the assistance of the staffs of various observatories (especially Lick) where the data were taken. This research has made use of the NASA/IPAC Extragalactic Database (NED), which is operated by the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administration. D. M. acknowledges support by the Israel Science Foundation — the Jack Adler Foundation for Space Research, Grant 63/01-1. A.V.F. is grateful for the financial support of NSF grants AST–9417213 and AST–9987438, as well as of the Guggenheim Foundation.


text:
# Hypernets – Good (G)news for Gnutella

## 1 Introduction

The Gnutella network is a class of open source virtual networks known as *Peer-to-Peer* or P2P networks. Compared to the more ubiquitous client-server distributed architectures, every P2P node (or *servant*) can act as both a client and a server. Many client-server applications such as, commercial databases, have multiple clients (users) accessing a centralized server (see  Chap. 8). Conversely, P2P network applications are usually completely decentralized.

Finding applications that can make efficient use of P2P is the current gating factor for their widespread adoption. So far, P2P networks have been employed for such applications as the Napster (www.napster.com) music file-sharing service, and the SETI@Home project (setiathome.ssl .berkeley.edu), although those implementations rely on a significant centralized server component.

###### Remark 1 (Update 2012).

One of the best known working examples of a P2P-style computing system is www.skype.com, which allows millions of people to use their PCs like a free telephone by forming its own gargantuan network that supports the Voice Over Internet Protocol (VOIP).

Other well-known P2P architectures include Napster, Freenet, Limewire, Kazaa, and BitTorrent. Moreover, many of these P2P architectures have progressed from file-sharing protocols to a viable means for distributing applications such as games, movies, and even software itself. For example, moving a 1.5 GB binary blob to countless servers is a non-trivial technical challenge. After exploring several solutions, Facebook.com came up with the idea of using BitTorrent for that purpose.

The initial release of Gnutella in 2000 led to the perception that the intrinsic architecture may not be capable of scaling to meet the sharing demands of millions of anticipated 111 In 2001, the size of the Napster network was 160,000 simultaneous users, down from a peak of 1.6 million reported by Webnoize in February, 2001  users. Similar concerns about scalability have arisen in the context of hypergrowth traffic impinging on popular e-commerce Web sites . Based on measurements of popular queries,  proposed that Gnutella scaling problems could be ameliorated through the implementation of appropriate caching strategies. Measurements by  indicated that there were more readers than writers involved in file sharing. They suggested that such a “free ride” could lead to higher than expected load on the P2P network thereby degrading its performance as well as increasing its vulnerability to fragmentation.

A mathematical analysis by  (one of the original developers of Napster) presented a detailed numerical argument demonstrating that the Gnutella network could not scale to the capacity of the competitor 222At the height of the media attention, Napster’s legal problems drove some 50,000 users per day over to Gnutella such that peers connected by 56 Kbps phone lines caused the P2P network to fragment into disconnected “islands” of about 200 peers. Napster network. Essentially, that model showed that the Gnutella network is severely bandwidth limited long before the P2P population reaches a million peers. In each of these previous studies, the conclusions have overlooked the intrinsic bandwidth limits of the underlying topology  in the Gnutella network: a Cayley tree . (See section 2 for the definition)

Trees are known to have lower aggregate bandwidth than higher dimensional topologies e.g., hypercubes and hypertori. Studies of interconnection topologies in the literature have tended to focus on hardware implementations (see e.g., ,  and ) which are generally limited by the cost of the chips and wires to a few thousand nodes . P2P networks, on the other hand, are intended to support hundreds of thousands to millions of simultaneous peers and since they are implemented in software, hyper-topologies are relatively unfettered 333As the SETI@Home project has demonstrated, 2.8 million desktops (and 10 PetaFLOPS) can be harnessed for free. by the economics hardware.

In this paper, we analyze the scalability of several alternative topologies and compare their throughput up to 2-3 million peers. The virtual hypercube and the virtual hypertorus offer near-linear scalable bandwidth subject to the number of peer TCP/IP connections that can be simultaneously kept open. We adopt the abbreviation *hypernet* for these alternative topologies. The assumptions about the distribution of peer activity are similar to those employed by . This is appropriate since our purpose is to rank the relative performance of these hypernets rather than to predict their absolute performance.

## 2 Tree Topologies

In the subsequent discussion, the P2P network is treated as a graph i.e., a set nodes or vertices connected by a set of edges or links. The nodes correspond to network peers and the links to the links to network connections.

Because the tree structure of the Gnutella network has been such a hidden determinant underlying the conclusions drawn in previous scalability studies, we commence our performance comparisons by distinguishing clearly among the relevant tree topologies. Topologically, all trees are planar and thus have d = 2 spatial dimensionality.

### 2.1 Binary Tree

The binary tree is familiar in the computing context by virtue of its ubiquity as a parsing and storage data structure . There is a unique root node which is connected only to two sibling nodes and each of those siblings is connected to another pair of sibling nodes and so on. At each level (h) in the tree, there are $`2^h`$ nodes. Therefore, the number of nodes grows as a binary exponential. Because of its relatively sparse nodal density, the binary tree is rarely employed as a bona fide interconnection network.

### 2.2 Rooted Tree

A rooted tree is simply the generalization of a binary tree in which each node (other than the root) has a vertex of degree v. The total number of nodes is the sum of a geometric series:

$$N_{bin}(h)=\frac{v^h1}{v1}$$
(1)
### 2.3 Cayley Tree

A Cayley tree  has no root. Recalling the binary tree, what was the root of the parent binary tree now has a link to an another binary sub-tree of height one less than the parent. All nodes thus become tri-valent with v = 3 at every level. More generally, for a v-valent tree, the total number of nodes is given by:

$$N_{cay}(h)=1+v(v1)^{h1}$$
(2)
and therefore is denser than ( 1).

This is the central formula used in the scalability analysis of . The network he analyzed is thus a Cayley tree with vertex degree (v) corresponding to the number of open network connections per servant.  analyzed valences in the range $`v=4\mathrm{}8`$; the former value being the default setting in the original Gnutella release, and the latter more closely resembling the number of peers claimed for the contemporaneous Napster network.

## 3 Hypernet Topologies

An alternative to bandwidth-limited trees is a topology with higher dimensionality. We examine the performance attributes of two hypernets in particular: the binary hypercube and the hypertorus, each in d-dimensions.

### 3.1 Hypercube

In a boolean or binary hypercube each node forms the vertex of a d-dimensional cube . The number of nodes is simply $`2^d`$ and the degree of each vertex (v) is equal to the dimensionality (d) of the network. Hence, each node can be enumerated or addressed using a base-2 (binary) d-digit number.

Moreover, since neighboring nodes differ in address by only 1 digit, sending a message on the hypercube becomes a simple matter of shifting successive bits as the binary address passes each node between source and destination.

In d = 3 dimensions the hypercube is simply a cube. Each vertex has degree v = 3, so there are $`2^3=8`$ nodes. A 4-dimensional hypercube, can be visualized as spatially translating a 3-cube such that the locus of its 4 vertices trace out the additional connections.

### 3.2 HyperTorus

A d-dimensional hypertorus  is a d-dimensional grid with each nodes connected to a ring of nodes in each of the d orthogonal dimensions. The hypertorus reduces to the binary hypercube when there are only 2 nodes in each ring.

The simplest visualization is, once again, in 3-dimensions. A 2-dimensional grid is first wrapped about one axis such the edges join to form a tube. The tube is wrapped about the orthogonal axis to form a ring such that the open ends of the tube become joined. The result is a 3-torus, otherwise known as a donut.

All of these topologies fall into a class known as single stage networks and are relatively easy to implement in software. The more exotic topologies, such as cube-connected cycles, butterflies and other multistage  networks are not considered here because they are likely to be more difficult to implement.

## 4 Performance Metrics

### 4.1 Network Diameter ($`\delta `$)

The notion of a network diameter is analogous to the diameter for a circle. There, it is the maximum chordal length between two points on the circumference. For a network, it is the maximum number of communication links that must be traversed to send a message to any node along the shortest path. It represents a lower bound on the latency to propagate messages throughout the entire network.

In 1997 the Web was estimated to comprise more than half a million sites . By 2001, it was estimated  to have grown to 3.1 million publicly accessible sites.

The diameter of the Web has been estimated  to be about 20 hops. If the Web is modelled as a Cayley tree, its height would be half the diameter i.e., $`h=\delta /2=10`$ hops. A vertex degree of 5 (connections per node) would contain just under half a million nodes while a vertex degree of 6 would contain nearly 3 million (2,929,687) nodes.

### 4.2 Total Nodes (N)

The total number of peer nodes in the P2P network. For a binary tree:

$$N(h)=\underset{k=1}{\overset{h}{}}2^{k1}$$
(3)
For a d-dimensional binary hypercube the number of nodes is $`2^d`$.

### 4.3 Path Length

The path length is the maximal distance between a leaf node and the root. For a tree, it is half the diameter. The path length corresponds the peer horizon used by  in his analysis. A better measure of network latency is the average number of hops (H), which we shall define shortly.

### 4.4 Internal Path Length (P)

The internal path length is the total number of paths between all nodes. For a binary tree of depth h, the total number of paths is:

$$P(h)=\underset{k=1}{\overset{h}{}}kN(k)$$
(4)
### 4.5 Average Number of Hops (H)

Since the network diameter is a maximal distance, it tends to overestimate message latency. A better measure is the average number of hops between source and destination. This quantity is found by dividing the internal path length in (4) by the total number of nodes in (3)

$$H=\frac{P}{N}$$
(5)
It corresponds to the average number of network hops traversed by a P2P query.

### 4.6 Number of Network Links (L)

This is a measure of the number of physical network links.

As shown in Table 2, L scales with the number of physical nodes (N) for the topologies we consider.

### 4.7 Network Demand ($`D_{link}`$)

The transit frequency across a link $`f_{link}`$ is a measure of the average query size per link. Under the assumption of uniform message routing, it can be defined as:

$$f_{link}=\frac{H}{L}$$
(6)
If the latency across a link is denoted by $`S_{link}`$, then the total service demand  is:

$$D_{link}=f_{link}S_{link}$$
(7)
For simplicity, and without loss of generality, we normalize the network demand to unit periods ($`S_{link}=1`$).

### 4.8 Peer Demand ($`D_{peer}`$)

Similarly, for node latency $`S_{peer}`$. Under the assumption of uniform message routing:

$$f_{peers}=\frac{1}{N}$$
(8)
and the total peer service demand is:

$$D_{peers}=\frac{S_{peer}}{N}$$
(9)
Again, we normalize the peer demand to unit periods ($`S_{peer}=1`$) in the subsequent discussion.

### 4.9 Bandwidth (X)

It follows from Little’s law, $`U=XD`$ (See e.g.,  p. 44) that when any node in the network reaches saturation ($`U=1`$) the maximum in the system throughput is determined by:

$$X_{max}=\frac{1}{Max[D_{peers},D_{link1},D_{link2},\mathrm{}]}$$
(10)
The node with the longest service demand $`D_{max}`$ is the system bottleneck. The service demand at the bottleneck therefore determines the maximum system throughput.

With these metrics defined, we are in a position to compare the asymptotic performance of each of the topologies described in sections 2 and 3.

## 5 Relative Bandwidth

Since we are interested in network scalability up to a few million peers, it is sufficient to base the comparison on the asymptotic network throughput defined in ( 10). In particular, we will rank the above hypernets according to their relative maximal bandwidth,

$$X_{relative}=X_{max}(N)/N$$
(11)
where N is the number of peers in the horizon (Table 3 at the end of this section). $`X_{relative}=1.0`$ corresponds to linear scalability since $`X_{max}=N`$ in (11).

In several respects our approach is similar to that taken by  for their LogP model of assessing parallel hardware performance. In both approaches, the respective network topology enters into the performance model via the network demand defined in ( 7 and 9).

### 5.1 Cayley Trees

First, we consider the relative performance of tree topologies. Fig. 1 shows the normalized bandwidths of a 4-th degree rooted tree, a 4-valent Cayley tree and an 8-valent Cayley tree.

The 4-valent Cayley tree represents the default peer connectivity in the original release of Gnutella. Similarly, the 8-valent Cayley tree corresponds to Ritter’s comparison with Napster scalability. The curves in Fig. 1 terminate at different peer populations because the population is an integral multiple which is dramatically affected by the vertex degree and the height of the tree.

We see immediately that the 8-valent Cayley tree has the greatest bandwidth up through 2 million peers. The 4-valent Cayley tree has the lowest bandwidth; even lower than the rooted tree. This follows from the fact that at its root the 4-tree has the same connectivity as the 4-Cayley tree but all its descendents have vertices of 5 degrees. Even for the 8-Cayley, at 2 million peers the bandwidth is less than one quarter of linear scalability.

### 5.2 Cubes and Trees

We next consider the relative performance of high degree trees and hypercubes. In particular, Fig. 2 shows the normalized bandwidths for an 8-Cayley (the best throughput of the trees considered in Fig. 1), a 20-Cayley, and a binary hypercube. The d-dimensional hypercube clearly exhibits superior scalability.

### 5.3 Cubes and Tori

Of these high-order topologies, the binary hypercube offers linearly scalable bandwidth beyond one million active peers (Fig. 3). The 10-dimensional hypertorus has comparable scalability up to one million peers but degrades beyond that point.

The 3-dimensional hypertorus is also shown for comparison since that topology has been used in large-scale hardware implementations up to several hundred nodes per cluster (e.g., the Tandem Himalya).

### 5.4 Ranked Performance

The main results of our analysis are summarized in Table 3 which shows each of the topologies ranked by their relative bandwidth as defined in (11).

The 20-dimensional hypercube outranks all other contenders on the basis of query throughput. For an horizon containing 2 million peers, each servant must maintain 20 open connections, on average. This is well within the capacity limits of most TCP/IP implementations .

The 10-dimensional hypertorus is comparable to the 20-hypercube in bandwidth up to an horizon of 1 million peers but falls off by almost 10% at 2 million peers. The 10-torus is also arguably a more difficult topology to implement.

The 20-valent Cayley tree is included since the number of connections per peer is the same as that for the 20-cube and the 10-torus. An horizon of 6 hops was used for comparison because the peer population is only 144,801 nodes at 5 hops. Similarly for 8-Cayley, a 9 hop horizon would contain 7.7 million peers. These large increments are a direct consequence of the high vertex degree per node.

The 4-Cayley (modeling early Gnutella) and 8-Cayley (modeling the Napster population) show relatively poor scalability at 1 million peers. Even doubling the number of connections per peer produces slightly better than 50% improvement in throughput. This confirms the conclusions reached in  and, moreover, supports our proposal to consider hypernet topologies.

## 6 Conclusions

Previous studies of Gnutella scalability have tended to overlook the intrinsic bandwidth limits of the underlying tree topology. The most thorough and accurate of these studies is that presented in . Unfortunately, his analysis could be accused of straining at a gnat. As a viable candidate for massively scalable bandwidth, our analysis demonstrates that trees are dead.

Conversely, by going to higher dimensional virtual networks (and the hypercube in particular) near linear scalability can be achieved for populations on the order of several million peers each with only 20 open connections. According to section 4, this level of scalability would already match the number of nodes present in the entire Web.

The dominant constraint for hardware implementations of high-dimensional networks is the cost of the physical wires on the interconnect backplane. Since the hypernets discussed here would be implemented in software, no such constraints would prevent reaching the desired level of scalability. In this sense, we see hypernets as offering good (g)news for Gnutella scalability.