text:
# References

Observability of neutron events above the Greisen-Zatsepin-Kuzmin cut-off due to violation of Lorentz invariance

Nayantara Gupta 111Email address: nayan@imsc.res.in

Institute of Mathematical Sciences,
C.I.T Campus, Taramani, Chennai 600113
INDIA.

## Abstract

The clustering of ultra high energy cosmic ray events suggests that they have originated from compact sources. One of the possible physical mechanisms by which ultra high energy nuclei reach the Earth from far away astrophysical sources (quasars or BL Lac objects) evading the Greisen-Zatsepin-Kuzmin (GZK) cut-off is by violation of Lorentz invariance. Assuming that there is violation of Lorentz invariance, we calculate the expected number of neutron events from some of the EGRET sources (including $`\gamma `$-ray loud BL Lac objects) which can be correlated in direction with ultra high energy cosmic ray events observed by AGASA above energy $`4\times 10^{19}`$eV. We present in this paper what AGASA should see in future if violation of Lorentz invariance is responsible for the propagation of ultra high energy cosmic rays having energies above the GZK cut-off when there is a correlation of EGRET sources with the ultra high energy cosmic ray events.

PACS numbers:11.30.Cp, 98.54.-h, 96.40.-z

Observational data on ultra high energy cosmic ray events have been recorded by different experiments like Fly’s Eye , Akeno Giant Air Shower Array (AGASA) , Yakutsk experiment , Haverah Park , Volcano Ranch experiment  and Sydney University Giant Air-shower Recorder (SUGAR) . The composition of the ultra high energy cosmic rays (UHECR) has been studied in . Data from Fly’s Eye experiment  suggest that the chemical composition is dominated by heavy nuclei up to ankle $`(10^{18.5})`$eV and thereafter by lighter component like protons. The AGASA data  suggest a mixed composition of both protons and heavier nuclei. The present experiments do not give us enough information about the chemical composition of primary UHECR. This topic has been addressed in . If the UHECR are nuclei, then what could be their origin and how they propagate in the extragalactic magnetic field are at present exciting fields of study. References  discuss different suggestions on these issues.

The Greisen-Zatsepin-Kuzmin(GZK) cut-off  will prevent nucleons of energy greater than $`4\times 10^{19}`$eV from travelling more than about 50 Mpc, but most of the suitable astrophysical acceleration sites are located at greater distances. AGASA experiment  has recorded about 8 events above $`10^{20}`$eV, whereas data recorded by HiRes fluorescence detector  seem to be in agreement with the GZK-cutoff . Since currently the experimental data are not convincing enough for accepting the presence of the GZK cut-off, theoretical suggestions for observability of cosmic rays above the GZK cut-off remain of interest to us. The Physics involving the formation and annhilation of topological defects (TDs) has been studied as a possible explanation of observing UHECR. However TD annhilation has unique observational consequences such as, copious production of particles like neutrinos and $`\gamma `$-rays . The experimental signatures of the Z-burst scenario has been discussed in . Gamma ray bursts have also been identified as a possible explanation of observing UHECR above the GZK cut-off .

If the highest energy cosmic rays have a neutral component then that will come to the Earth from the direction of its source. Elbert and Sommers  identified radio-loud quasar 3C147 as an ideal source within $`10^{}`$ of the highest energy event observed by Fly’s Eye experiment  at energy $`3.2\times 10^{20}`$eV. Later another quasar PG0117 + 213 was identified by Biermann  within the error cone of the second highest energy event observed by AGASA . In the last few years a lot of work has been done by different groups  in correlating UHECR events with radio quasars and BL Lac objects. It was pointed out by Dubovsky et al.  that the statistics of clustering of ultra high energy cosmic ray events suggests their correlation with compact sources. In  the authors have pointed out that there is no significant correlation between quasars or BL Lac objects and ultra high energy cosmic ray events. They have used data from Haverah Park  and Volcano Ranch experiments  for their statistical analysise. However, the authors of  have shown that there is a significant correlation between compact sources and observed ultra high energy cosmic ray events using the data from AGASA  and Yakutsk  experiments. The probability of positional coincidence between BL Lac objects and UHECR events to occur by chance in a random distribution is of the order of $`10^4`$. The still unknown data from HiRes experiment  and the accumulating data from AUGER experiment  will enable us to carry out statistical analysis with a bigger set of data in the near future.

Since, as of now it is not clear whether the UHECR events are statistically uncorrelated with compact sources at high redshifts, the physical mechanisms by which neutral component of UHECR may come to the Earth evading the GZK cut-off from high redshifts are still exciting fields of study for us. In the Z-burst scenario  or in models of hypothetical “immune messengers”  neutral particles can come to the Earth from the direction of the source evading the GZK cut-off. It has been suggested by Coleman and Glashow  that if there is violation of Lorentz invariance (VLI) then protons and neutrons of energies above the GZK cut-off will reach the Earth without interacting with the cosmic microwave background. In the present work we show that one can test whether VLI is responsible for the observability of the UHECR events above the GZK cut-off using the data from AGASA experiment and certainly with the data from AUGER  experiment in future. We have predicted what AGASA should see in future if VLI is the underlying physical mechanism for propagation of cosmic rays with energies above the GZK cut-off from compact sources at high redshifts.

We consider the ultra high energy cosmic ray events observed by AGASA above the GZK cut-off. Among this set of events we find that some of them can be correlated in direction with EGRET sources from the third EGRET catalog . In  the authors have suggested that the sources of UHECR are high energy peaked BL Lac objects. Our set of correlated EGRET sources also include $`\gamma `$-ray loud BL Lac objects. If the radiation energy density is sufficiently high in a source, photo-pion production leads to the generation of a sufficient number of neutrons which can escape from the system. If there is VLI the neutrons having an energy above a certain energy will not decay. The energy above which the neutrons become stable depends on the degree of VLI. In  the authors have obtained a limit on the energy above which neutrons become stable, using observational data from the Yakutsk experiment . These neutrons can travel through the cosmic microwave background with energy above the GZK cut-off when there is VLI and in that case we expect to detect them from the direction of the compact source. For clusters of UHECR events we consider sources within $`4^{}`$ of the events and for a single event we correlate with a source within $`2.5^{}`$. In our correlated data set we have eight EGRET sources, among which three (3EG J0433+2908, 3EG J1052+5718 and 3EG J1424+3734) are confirmed BL Lac objects from the Véron 2001 catalog . Among the remaining five, 3EG J1744-0310 is a quasar . The four unidentified EGRET sources i.e. 3EG J1824+3441, 3EG J1903+0550, 3EG J0429+0337 and 3EG J0215+1123 may be BL Lac objects that have not yet been confirmed. Two of these four unidentified EGRET sources are also present in Table 3 of .

TABLE I. The EGRET sources correlated with UHECR events above $`4\times 10^{19}`$ eV in AGASA data

| 3EG J | EGRET ID | Type of | $`l_s`$ | $`b_s`$ | $`z`$ | $`l`$ | $`b`$ | $`E`$ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  |  | Object | (deg) | (deg) |  | (deg) | (deg) | $`10^{19}eV`$ |
| (1) | (2) | (3) | (4) | (5) | (6) | (7) | (8) | (9) |
| 0433+2908 | AGN | BL Lac | 170.5 | -12.6 | $`>0.3`$ | 170.4 | -11.2 | 5.47 |
|  |  | 2EG J0432+2910 |  |  |  |  |  |  |
|  |  |  |  |  |  | 171.1 | -10.8 | 4.89 |
| 1052+5718 | Possible AGN | BL Lac | 149.6 | 54.42 | 0.144 | 147.5 | 56.2 | 5.35 |
|  |  | RGB J1058+564 |  |  |  |  |  |  |
|  |  |  |  |  |  | 145.5 | 55.1 | 7.76 |
| 1424+3734 |  | BL Lac | 63.95 | 66.92 | 0.564 | 68.5 | 69.1 | 4.97 |
|  |  | TEX 1428+370 |  |  |  |  |  |  |
| 1744-0310 | AGN | Quasar | 22.19 | 13.42 | 1.054 | 22.8 | 15.7 | 4.27 |
| 0215+1123 |  |  | 153.75 | -46.37 |  | 152.9 | -43.9 | 4.2 |
| 0429+0337 |  |  | 191.4 | -29.08 |  | 191.3 | -26.5 | 6.19 |
| 1824+3441 |  |  | 62.49 | 20.14 |  | 63.5 | 19.4 | 9.79 |
| 1903+0550 |  |  | 39.52 | -0.05 |  | 39.9 | -2.1 | 7.53 |

In the first row of TABLE I we note that the redshift of the EGRET source 3EG J0433+2908 is more than 0.3 . The fourth and fifth columns of TABLE I give longitudes and latitudes of the sources in Galactic coordinates and the seventh and eighth columns display longitudes and latitudes of the UHECR events in Galactic coordinates.

We consider the sources of TABLE I whose redshifts are known and calculate the number of neutron events from them expected to be detected by AGASA in 30 years. We calculate the expected number of neutron events from the source 3EG J0433+2908 assuming its redshift to be 0.3. In future we will come to know the redshifts of the other EGRET sources and then it will also be possible to calculate the expected number of neutron events from them. There are both theoretical  and observational  reasons to believe that when proton acceleration is being limited by energy losses, the luminosity of the object in very high energy cosmic rays $`L_{CR}`$ is approximately equal to its luminosity in gamma rays. The cosmic ray luminosity $`L_{CR}`$ in the energy range $`1\times 10^{19}`$eV$`<E<4\times 10^{20}`$eV can be assumed to be emitted equally in each decade of energy $`E`$. In that case, in each decade of energy we expect the power emitted in UHECR in the energy range of $`1\times 10^{19}`$eV to $`4\times 10^{20}`$eV to be approximately $`L_{CR}/10`$. Let ‘$`A`$’ be the area of AGASA detector which is $`10^{12}cm^2`$ . Here we mention that the exposure of the AGASA detector is energy independent in the energy range in which we are interested. One can see the plot of exposure against energy of the UHECRs for AGASA detector in . The expected number of neutron events in a time interval $`dt_o`$ in AGASA within the source energy interval of $`E_1`$ and $`E_2`$ can be expressed as

$$\frac{dN_o^n}{dt_o}=\frac{A}{4\pi d^2}_{E_1}^{E_2}\frac{dN_s^n}{dE_sdt_s}𝑑E_s$$
(1)
where $`d`$ is the luminosity distance of the source from the Earth. $`N_s^n`$ and $`N_o^n`$ are respectively the number of neutrons emitted at the source and observed by the detector. $`E_s`$, $`E_o`$ are the source energy and observed energy of the neutrons respectively. If the redshift of the source is $`z`$ then $`E_o=E_s/(1+z)`$. Similary the correction to be applied to observed time $`t_o`$ due to redshift of the source is $`t_o=t_s(1+z)`$, where $`t_s`$ is the time at which the neutron is emitted from the source.

We have assumed there is VLI and that the lower limit of the above integration is such that neutrons are stable above this energy.

We define $`F_\gamma ^{ob}`$ as the energy received in gamma rays per second per $`cm^2`$ on the surface of the Earth from an EGRET source and this quantity can be calculated from . $`ϵ_n`$ is the efficiency of neutron production in the source. When the photon density in a source is sufficiently high then the efficiency of neutron and proton production become comparable near the end of the UHECR spectrum . Hence it is not unreasonable to assume $`ϵ_n=1/2`$ in our calculation. If we assume the luminosity of the source in gamma rays of energy more than $`100`$MeV $`L_\gamma `$ to be a fraction $`x`$ times the luminosity of the source in UHECR $`L_{CR}`$, then eqn.(1) can be written as

$$\frac{dN_o^n}{dt_o}=Aϵ_nx\frac{F_\gamma ^{ob}}{10}_{E_1}^{E_2}\frac{dE_s}{E_s^2}$$
(2)
An almost similar procedure has been followed in ref. in calculating number of neutron events from Centaurus A but without the assumption of VLI. Using eqn.(2) we calculate the expected number of neutron events between observed energy intervals of $`1\times 10^{20}`$eV and $`2\times 10^{20}`$eV in AGASA from the sources of TABLE I whose redshifts are known. The second column of TABLE II displays the photon flux in $`10^8`$ photon $`cm^2sec^1`$ above $`100`$ MeV energy for the EGRET sources in the first column . The third column shows the photon spectral indices from  of the EGRET sources displayed in the first column. The fourth and fifth columns present the expected number of neutron events in a time interval of $`30`$ years in AGASA for case (1) $`ϵ_n=1/2`$, $`x=1`$ and for case(2) $`ϵ_n=1/2`$, $`x=1/2`$ respectively.

TABLE II. The number of neutron events between energy $`1\times 10^{20}`$eV and $`2\times 10^{20}`$eV expected in AGASA in 30 years from some of the EGRET sources of TABLE I.

| 3EG J | Photon flux | Photon Spectral | Number of Neutron | Number of Neutron |
| --- | --- | --- | --- | --- |
|  | above 100 MeV | Index | Events in case (1) | Events in case (2) |
| 0433+2908 | 22.0 | 1.9 | 8.4 | 4.2 |
| 1052+5718 | 6.5 | 2.51 | 2.2 | 1.1 |
| 1424+3734 | 16.3 | 3.25 | 3.5 | 1.7 |
| 1744-0310 | 21.9 | 2.42 | 4.29 | 2.1 |

In the last 10 years data from AGASA there is no event above $`10^{20}`$eV energy from the direction of the sources of first column of TABLE II. If VLI is the underlying mechanism for UHECR propagation then we can expect to see UHECR events above $`10^{20}`$eV from the direction of the sources presented in TABLE II in future. If we increase the area of the detector or the time of data collection then of course we would detect more neutron events than that presented in TABLE II. The number of neutron events will increase linearly with increasing area or time of data collection by the detector. Since the area of AUGER is $`30`$ times larger than AGASA, we can expect such neutron events in a much shorter interval of time in AUGER.

Conclusion
In this paper we have presented how the UHECR data above the GZK cut-off can tell us whether VLI is the underlying mechanism for the propagation of these cosmic rays from quasars or BL Lac objects at high redshifts.


format: text

text:
# Computation of Hyperbolic Structures in Knot Theory

## 1 Introduction

Knot and link complements enjoy a geometry of crystalline beauty, rigid enough that simple cut-and-paste techniques meet geometrical as well as topological needs, yet surprisingly complex in their inexhaustible variety. The cut-and-paste approach makes computer exploration of their geometry easy: link complements become finite unions of tetrahedra, handled in a purely combinatorial way, with no need for the messy machinery of differential geometry.

The present article begins with the geometry of 2-dimensional link complements in Section 2 to provide an overview of all the main ideas. Section 3 explains an efficient algorithm for triangulating 3-dimensional link complements, Section 4 shows how to compute the hyperbolic structure, and finally Section 5 shows how the hyperbolic structure deforms to yield hyperbolic structures on closed manifolds obtained by Dehn filling.

Readers may consult other chapters in this volume for richer discussions of hyperbolic knots and links  and Dehn fillings . Hyperbolic structures have found applications in knot tabulation  and more generally provide a fast and effective way to test hyperbolic knots and links for equivalence  and to compute their symmetry groups  and other invariants . The computer program SnapPea  implements these applications based on the foundation described in the present article. The SnapPea source code contains detailed explanations of all algorithms used.

Even though the exposition in the present article is original, most of the mathematics was born in the work of Bill Thurston. Thurston’s informal 1979 notes (see also ) contained the theory of hyperbolic knots and links, hyperbolic Dehn filling, and in particular his simple and elegant system (explained here in Sections 4 and 5) for finding hyperbolic structures in terms of complex edge angles.

## 2 Two-dimensional preview

Before tackling 3-dimensional knots and links, let us review the the 2-dimensional ones. Their topology and geometry is far simpler, yet the insights they provide will serve us well in the 3-dimensional case.

Just as a 3-dimensional link is a collection of 1-spheres (circles) in a 3-sphere, a 2-dimensional link is a collection of 0-spheres (pairs of points) in a 2-sphere. The classification of 2-dimensional links is easy: two links are equivalent if and only if they have the same number of components (Figure 1).

Each link complement admits a constant curvature geometry. The 0-component link complement, which is simply an unpunctured 2-sphere, already has spherical geometry. At first glance the remaining $`n`$-component link complements, which are punctured 2-spheres, also seem to have spherical geometry, but these geometric structures are disallowed because they are incomplete. Many formal definitions of completeness appear in the literature, but intuitively a surface is incomplete if a traveller starting at some point on the surface can reach an “edge” (either a ragged edge or a boundary) within a finite distance. Conversely a surface is complete if a traveller starting at any point on the surface can travel any finite distance in any direction without hitting an edge. In the case of a punctured 2-sphere, a traveller easily reaches a puncture, so the surface is incomplete.

To construct a complete geometric structure on the 1-component link complement, pull the link itself (the pair of points) to infinity, dragging the link complement along with it (Figure 2, second frame). The link complement becomes an infinite cylinder, which has locally Euclidean geometry (constant zero curvature) and is complete.

Following the same technique, take the 2-component link and pull the link itself (two pairs of points) to infinity. Intuitively the stretched out link complement looks hyperbolic (Figure 2, third frame). To make this rigorous, cut the link complement into four ideal triangles (Figure 3, left) and then define the hyperbolic structure on the link complement to be the union of four hyperbolic ideal triangles with edges identified (“glued”) in the appropriate way (Figure 3, right).

More generally, for every $`n>1`$ the $`n`$-component link complement splits into a union of ideal triangles which then defines a hyperbolic structure on the link complement. The hyperbolic structure is never unique, but a simple Euler number argument shows that the number of ideal triangles must be exactly $`4(n1)`$. An ideal triangle has area $`\pi `$, so the total area of the $`n`$-component link complement is $`4\pi (n1)`$ no matter what hyperbolic structure is chosen.

Assuming we identify the ideal triangles’ edges midpoint-to-midpoint (the midpoint of an edge being the edge’s intersection with an orthogonal line of mirror symmetry), the hyperbolic structure is complete, and is therefore called a complete hyperbolic structure. The parts stretching off to infinity are called cusps.

On the one hand, ideal triangles are rigid (Figure 4 left). On the other hand, the gluing between two ideal triangles is flexible: each edge is infinitely long so the neighboring triangles may slide past one another (Figure 4 right). These 2-dimensional facts are exactly the opposite of the situation in 3 dimensions, where ideal tetrahedra are flexible but the gluings between them are rigid. Nevertheless, deforming the hyperbolic structure produces analogous results in both 2 and 3 dimensions, and so examining the 2-dimensional case in this Section will provide insight into the analogous 3-dimensional results in Section 5.

To deform a hyperbolic structure, start with one of the cusps. Slice the cusp open (Figure 5). Gluing opposite edges of the sliced-open cusp straight across (Figure 5 top) would restore the cusp to its original condition, but gluing opposite edges with a shift (Figure 5 bottom) yields a different result. If you physically construct a paper model111The paper model is of course only an approximation. The real cusp is intrinsically hyperbolic while your paper model is intrinsically flat. Nevertheless the paper model suffices for the demonstration at hand. Remember that the width of your paper strip must shrink exponentially fast as you move along it lengthwise. of the sliced-open cusp and wrap it around so that each point on one edge glues to a point on the opposite edge that’s shifted by, say, 4 cm, you obtain a cylinder (Figure 6). Your paper strip, if infinitely long, would wrap around the cylinder infinitely many times, approaching but never reaching a limiting circle.

Globally, for each 0-sphere in an $`n`$-component link, pick a geodesic edge connecting the two cusps belonging to that 0-sphere. Cut, shift and reglue along each such edge (Figure 7 left). Locally the result at each cusp looks like Figure 6. Globally the result looks like Figure 7 right. That is, the result is a surface of genus $`n`$ with $`n`$ circles missing (namely the limiting circles of the former cusps). With foresight we may arrange for the geodesic edges (along which we cut, shifted and reglued) to be edges of the triangulation. That is, our original cusped surface was the union of $`4(n1)`$ hyperbolic ideal triangles, and we cut, shifted and reglued along edges of that ideal triangulation. Thus the result (Figure 7 right) is also the union of $`4(n1)`$ hyperbolic ideal triangles and therefore enjoys a hyperbolic structure, albeit an incomplete one. The missing circles are geodesics. Adding those $`n`$ missing geodesic circles yields a complete hyperbolic structure on the closed surface of genus $`n`$.

In two dimensions most link complements admit a complete hyperbolic structure. Deforming a complete hyperbolic structure yields a hyperbolic structure (with missing geodesics) for a closed surface. Both these results generalize readily to three dimensions.

## 3 Triangulation of knot and link complements

Just as every 2-dimensional link complement splits into ideal triangles (Figure 3), every 3-dimensional link complement splits into ideal tetrahedra. For now we will work with “topological ideal tetrahedra” — that is, we will visualize them as ideal tetrahedra but won’t worry about the exact hyperbolic geometry they carry. The latter will be the subject of Section 4.

The goal in triangulating a link complement is to produce a triangulation that quickly simplifies down to as few tetrahedra as possible. Minimizing the number of tetrahedra saves space and computational time, but more importantly it vastly improves the chances that all tetrahedra will be “positively oriented”, a condition needed to rigorously guarantee that the subsequent hyperbolic structure is correct. The triangulation algorithm used in the computer program SnapPea has proven more effective than several alternatives the author tested, so that is the algorithm presented here.

Technical Note (which the reader may ignore): SnapPea’s algorithm requires a connected link projection. If a given link projection consists of more than one component, SnapPea does Type II Reidemeister moves to make the projection connected. In the same spirit, to each obviously unknotted component SnapPea does a Type I Reidemeister move to add a nugatory crossing. Link projections requiring these moves never have hyperbolic complements; the moves are needed only for non-hyperbolic knots and links.

The link complement will have one cusp for each component of the link. For visual convenience we chop off the cusps. That is, rather than triangulating the complement of the link using ideal tetrahedra, we’ll triangulate the complement of a tubular neighborhood of the link using truncated ideal tetrahedra. Once such a truncated ideal triangulation is found, the extension to true ideal tetrahedra is easy and obvious.

Imagine the tubular neighborhood of the link lying near the equatorial 2-sphere of the 3-sphere $`S^3`$. To keep the construction simple and natural, the triangulation must adhere closely to the link projection itself. To accomplish this, let us triangulate it in $`S^2\times I`$ rather than in $`S^3`$ (Figure 8). The two missing solid balls — one lying to either side of $`S^2\times I`$ in $`S^3`$ — will be added back later.

To triangulate the link complement in $`S^2\times I`$, cut straight down through it just as you would cut cookie dough with a cookie cutter. Figure 9 shows the pattern of the cuts: cut along the centerline of each link component and also along the dual graph. The resulting pieces are all identical. Figure 10 (first panel) shows one piece. It’s not yet a truncated tetrahedron. It has four truncated vertices, two of which border the tubular neighborhood of the knot and two of which border the upper and lower surfaces of $`S^2\times I`$, along with six ordinary faces, four of which are combinatorial hexagons and two of which are combinatorial squares.

Now deform each combinatorial square to become a tall narrow rectangle (Figure 10 second panel) that finally collapses to a vertical line segment (third panel). The resulting solid (last panel) has four truncated vertices (all are triangles) and four ordinary faces (all are hexagons), and is in fact combinatorially a truncated tetrahedron!

Collapsing all square faces to vertical lines does not change the topology of the manifold. If some link component had only overcrossings or only undercrossings, then collapsing the squares would indeed change the manifold’s topology because we’d be collapsing an embedded cylinder, but the preceding Technical Note excludes this possibility. Collapsing an embedded square or a series of embedded squares is safe.

A simple indexing system describes the triangulation in a format amenable to computer use. Label the four truncated vertices of each tetrahedron with the integers $`\{0,1,2,3\}`$ and label each face with the index of its opposite vertex. To specify how a face of one tetrahedron glues to a face of another, simply specify the permutation of the vertex index set $`\{0,1,2,3\}`$ induced by reflecting the vertices of the original tetrahedron across the face in question onto the vertices of the neighboring tetrahedron.

In general the vertex indices may be assigned arbitrarily, but in the case of a triangulated link complement we make the convention that vertex 0 is the truncated vertex at the south pole of $`S^3`$ (on the bottom of the polyhedron in Figure 10 left), vertex 1 is the truncated vertex at the north pole of $`S^3`$ (on the top of the polyhedron in Figure 10 left), and vertices 2 and 3 are the truncated vertices touching the link ( the left and right hemi-cylindrical truncated vertices, respectively, in Figure 10 left). With this convention the symmetry of the decomposition guarantees that all gluing permutations are the same throughout the triangulation, namely $`01230132`$.

We now have a nicely triangulated manifold, but we constructed it in $`S^2\times I`$ rather than $`S^3`$, so in $`S^3`$ it’s the complement of the link plus two solid balls. To remedy this problem, drill out a tube connecting the thickened link to the solid ball at the north pole (thus “cancelling” that solid ball) and a second tube connecting the thickened link to the solid ball at the south pole. The easiest way to drill out a tube is to splice into the triangulation a triangular pillow that already contains a pre-drilled tube (Figure 11). That is, let $`F`$ be any 2-cell of the triangulation incident to both the northern spherical boundary of $`S^2\times I`$ and one of the torus boundary components of the link complement. If we cut along $`F`$, insert an ordinary (un-drilled) triangular pillow, and reglue, then the topology of the manifold does not change. But if we instead insert a triangular pillow with a pre-drilled tube (Figure 11) then the boundary component at one end of the tube gets joined to the boundary component at the other end of the tube. In the present case this joins the spherical boundary component at the north pole (resp. south pole) to the torus boundary of the link, thereby neutralizing the former.

A triangular pillow with a pre-drilled tube can be constructed from two truncated (or ideal) tetrahedra. Face 0 of the first tetrahedron glues to face 0 of the second tetrahedron via the gluing $`01230213`$. Face 3 of the first tetrahedron glues to face 3 of the second tetrahedron via the gluing $`01231023`$. Faces 1 and 2 of the second tetrahedron glue to each other via the gluing $`01230213`$. Faces 1 and 2 of the first tetrahedron remain unglued and provide the two external boundary faces of the pillow.

Once the two triangular pillows are installed we have a valid triangulation of the link complement. The triangulation contains $`4n+4`$ tetrahedra, but the number of tetrahedra decreases substantially when the triangulation is simplified. Two elementary operations serve to simplify the triangulation: the first operation replaces three tetrahedra surrounding a common edge with two tetrahedra sharing a common face, while the second operation cancels two ”flattened” tetrahedra that share two adjacent faces. For an explanation of an effective high-level algorithm governing the application of the two elementary operations, please see the file simplify\_triangulation.c in the SnapPea source code . Note that the high-level algorithm sometimes requires the inverse of the first operation, which temporarily increases the number of tetrahedra – by replacing two tetrahedra sharing a face with three tetrahedra surrounding an edge – but ultimately leads to simplifications.

## 4 The complete hyperbolic structure

If the link complement admits a hyperbolic structure , then the “topological ideal tetrahedra” of the previous section may be replaced with honest hyperbolic ideal tetrahedra.

In principle this is easy: just imagine the topological ideal triangulation sitting in the hyperbolic manifold in some wiggly way, and pull all its 1-dimensional edges taut, so that the edges become geodesics running from infinity in one cusp, though the fat part of the manifold, and back to infinity either in the same cusp or in a different cusp. Each 2-dimensional face is now defined by its three geodesic edges, and each 3-dimensional ideal tetrahedron is defined by its faces.222If the triangulation is inefficient, with more than a minimal number of tetrahedra, then there is some danger that one or more of the tetrahedra will become negatively oriented — in effect the triangulation folds over on itself and then double back at those places, leaving some points in the manifold covered three times, twice by ordinary positively oriented tetrahedra and once by a negatively oriented tetrahedron. But we needn’t worry about this problem here.

In practice we solve for the shapes of the honest hyperbolic ideal tetrahedra analytically. The shape of an ideal tetrahedron is determined by its dihedral angles. By symmetry (Figure 12) opposite dihedral angles are equal, so three of the angles determine the opposite three. Furthermore, if we examine a horospherical cross section of a cusp (Figure 13), we may replace the real dihedral angle with a complex dihedral angle (Figure 14). The three complex dihedral angles depend on each other: any one of them determines the other two (Figure 15). Thus a single complex dihedral angle completely parameterizes the shape of an ideal tetrahedron.

The real dihedral angles surrounding a single edge in a hyperbolic ideal triangulation sum to $`2\pi `$. Analogously, the complex dihedral angles surrounding an edge multiply to $`1`$. Figure 16 illustrates how the complex angles provide more information than the real angles do. In practice one replaces the product $`z_i=1`$ with its more powerful logarithmic form $`\mathrm{log}z_i=2\pi i`$ to insure that the arguments sum to $`2\pi `$ rather than, say, to $`4\pi `$ or $`0`$. Geometrically this ensures that the sequence of tetrahedra wraps exactly once around the edge.

Our goal, in geometrical terms, is to take the topological ideal triangulation of a knot or link complement produced in Section 3 and realize each topological ideal tetrahedron as an honest hyperbolic ideal tetrahedron in such as way that they fit together correctly around their common edges. Algebraically, this means we must find complex dihedral angles $`z`$ for the tetrahedra such that the edge equations $`\mathrm{log}z_i=2\pi i`$ are satisfied. But we are not quite ready to solve those equations. Even though a simple Euler characteristic argument guarantees that the number of equations equals the number of variables, the equations are not independent. Rather the solution space contains one complex degree of freedom for each cusp (i.e. for each component of the original link). For now we will resolve this ambiguity by insisting that each cusp be complete, i.e. that its cross section be effectively a parallelogram (Figure 17 left) rather than some other quadrilateral (Figure 17 right). Section 5 will explore the more general case in detail.

In summary, to the set of edge equations we add a set of cusp equations ensuring that each cusp is complete. We then solve the equations using Newton’s method and obtain the solution.

In practice the situation is somewhat delicate. When applied blindly, Newton’s method usually fails. That is, if one begins with, say, regular ideal tetrahedra (all complex dihedral angles $`z`$ equal to the sixth root of unity $`\frac{1}{2}+\frac{\sqrt{3}}{2}i`$) and applies the standard Newton’s method, often the shapes of the tetrahedra will diverge to infinity or other nonsense values. To avoid this, one must take two precautions. First, one re-selects the coordinate system at each iteration of Newton’s method in order to minimize exposure to singularities and keep the entries in the derivative matrix small. Second, one trusts the direction of the gradient in Newton’s method but distrusts its magnitude. Let us consider each of these two precautions in detail.

Choice of coordinates. Complex dihedral angles of $`z`$ = 0, 1, or $`\mathrm{}`$ correspond to degenerate tetrahedra. Near those values, bad things happen. The two main problems are that (1) some of the entries in the derivative matrix (used in Newton’s method) approach infinity, and (2) incrementing the solution can move it too close to a singularity, resulting in wild swings in the real dihedral angles. Switching the coordinates from the complex dihedral angle $`z`$ to its logarithm $`\mathrm{log}z`$ helps a bit. Rather than having two singularities (at $`z=0`$ and $`z=1`$) embedded in the parameter space, you have only one. The singularity that used to be at $`z=1`$ is now at $`\mathrm{log}z=0`$, but the singularity that used to be at $`z=0`$ has been happily pushed out to infinity.

This strategy can be further improved by choosing the (logarithmic) coordinate system based on the current shape of the tetrahedron. The coordinate system is chosen so that the current shape of the tetrahedron stays as far away as possible from the one remaining singularity in the parameter space. Specifically, let the three complex dihedral angles be

$$z_0=z,z_1=\frac{1}{1z},z_2=1\frac{1}{z}$$
(1)
(note that those expressions are taken directly from the formulas in the caption of Figure 15) and divide the complex plane into three regions

| Region A: | $`|z1|>1`$ | and | $`\mathrm{R}ez<1/2`$ |
| --- | --- | --- | --- |
| Region B: | $`|z|>1`$ | and | $`\mathrm{R}ez>1/2`$ |
| Region C: | $`|z1|<1`$ | and | $`|z|<1`$ |

Viewed on the Riemann sphere, the singularities at $`0`$, $`1`$ and $`\mathrm{}`$ are equally spaced points on the equator, and the Regions A, B and C are separated by meridians spaced $`2\pi /3`$ apart. Points lying on the separating meridians may be arbitrarily assigned to either neighboring region.

When $`z`$ lies in Region A (resp. Region B, Region C), let $`\mathrm{log}z_0`$ (resp. $`\mathrm{log}z_1`$, $`\mathrm{log}z_2`$) parameterize the shape of the tetrahedron.

Proposition. If one chooses coordinates as in the preceding sentence, then the entries in the derivative matrix remain bounded.

Proof. Each entry in the derivative matrix used in Newton’s method is a fixed linear combination of the derivatives of $`\mathrm{log}z_0`$, $`\mathrm{log}z_1`$ and $`\mathrm{log}z_2`$ for several tetrahedra, so it suffices to show that each such derivative has modulus less than or equal to one. First compute

$$\frac{d(\mathrm{log}z_0)}{dz}=\frac{1}{z},\frac{d(\mathrm{log}z_1)}{dz}=\frac{1}{1z},\frac{d(\mathrm{log}z_2)}{dz}=\frac{1}{z(z1)}$$
(2)
and then take ratios of the above to obtain

$$\begin{array}{ccc}\frac{d(\mathrm{log}z_0)}{d(\mathrm{log}z_0)}=1\hfill & \frac{d(\mathrm{log}z_0)}{d(\mathrm{log}z_1)}=\frac{1z}{z}\hfill & \frac{d(\mathrm{log}z_0)}{d(\mathrm{log}z_2)}=z1\hfill \\ \frac{d(\mathrm{log}z_1)}{d(\mathrm{log}z_0)}=\frac{z}{1z}\hfill & \frac{d(\mathrm{log}z_1)}{d(\mathrm{log}z_1)}=1\hfill & \frac{d(\mathrm{log}z_1)}{d(\mathrm{log}z_2)}=z\hfill \\ \frac{d(\mathrm{log}z_2)}{d(\mathrm{log}z_0)}=\frac{1}{z1}\hfill & \frac{d(\mathrm{log}z_2)}{d(\mathrm{log}z_1)}=\frac{1}{z}\hfill & \frac{d(\mathrm{log}z_2)}{d(\mathrm{log}z_2)}=1.\hfill \end{array}$$
(3)
If $`z`$ lies in Region A and we have chosen $`\mathrm{log}z_0`$ coordinates as required, then the derivatives in the first column of (3) have modulus less than or equal to 1. This is obvious for the first entry in the column. For the third entry it’s an immediate consequence of the condition $`|z1|>1`$. For the second entry, note that

$$|\mathrm{I}mz|=|\mathrm{I}m(1z)|$$

and

$$|\mathrm{R}ez|<|\mathrm{R}e(1z)|\mathrm{i}ff\mathrm{R}ez<1/2$$

so $`|z|<|1z|`$.

Similar arguments show that when $`z`$ lies in Region B (resp. Region C) the derivatives in the second column (resp. third column) have modulus less than or equal to 1. Q.E.D.

Theoretical Note #1: The computed dihedral angles, given by the imaginary parts of $`\mathrm{log}z_0`$, $`\mathrm{log}z_1`$ and $`\mathrm{log}z_2`$, are not a priori limited to the range $`(0,\pi )`$. However, only when they fall in the range $`(0,\pi )`$ does the computed solution have a direct geometrical interpretation as a union of ideal tetrahedra comprising a cusped hyperbolic 3-manifold. When some or all of the angles fall outside the range $`(0,\pi )`$ the situation is more complicated: in most cases the hyperbolic structure still exists and has the computed volume but in rare cases spurious non-geometric solutions occur.

Theoretical Note #2: I briefly entertained the idea of finding a single coordinate system that avoids all three singularities. Unfortunately Picard’s Little Theorem shows that this is not possible for an analytic function. It might be possible for a nonanalytic function — perhaps a simple function of $`z`$ and $`\overline{z}`$ — but I haven’t pursued this idea and in any case such a function wouldn’t be conformal.

Avoiding singularities. When applying Newton’s method to find a hyperbolic structure, one trusts the direction of the gradient but distrusts its magnitude. More precisely, one insists that neither the real part nor the imaginary part of the parameter $`\mathrm{log}z`$ change by more than $`1/2`$ for any tetrahedron. This restricts the change to a limited zone (Figure 18) and in particular keeps the parameter well away from the one singularity that remains in the parameter space (at $`z=1`$ or $`\mathrm{log}z=0`$). If Newton’s method calls for a change exceeding those limits, then we rescale the proposed change (for all the tetrahedra, not just the offending one) so that the largest change in any $`\mathrm{R}e(\mathrm{log}z)`$ or $`\mathrm{I}m(\mathrm{log}z)`$ is $`1/2`$.

## 5 Hyperbolic Dehn filling

Section 2 showed how to construct a hyperbolic structure on the complement of a $`k`$-component link of 0-spheres on a 2-sphere ($`k2`$) and then went on to show how deforming the hyperbolic structure (Figures 5 and 6) yields a hyperbolic structure on a closed surface of genus $`k`$ with two closed geodesics missing (Figure 7). That was 2-dimensional hyperbolic Dehn filling. Three-dimensional hyperbolic Dehn filling is similar: deforming the complete hyperbolic structure on a $`k`$-component link complement (Section 4) will yield a hyperbolic structure on a closed manifold with $`k`$ closed geodesics missing. In spite of the strong analogy between 2-dimensional and 3-dimensional hyperbolic Dehn filling, there are nevertheless a few differences. In the 2-dimensional case the ideal triangles were rigid while the gluings between them were flexible, whereas in the 3-dimensional case the shapes of the tetrahedra themselves are flexible while the gluings between them are rigid. More interestingly, in the 2-dimensional case different deformations all gave the same topological 2-manifold (namely the closed surface of genus $`k`$, once the $`k`$ missing geodesics are filled in), whereas in the 3-dimensional case different deformations give topologically distinct 3-manifolds (filling in the missing geodesics realizes a Dehn filling on the link complement, with the Dehn filling coefficients depending on the deformation — more on this below).

The cut-open 2-dimensional cusps of Figure 5 become, in three dimensions, solid structures resembling the Eiffel tower (Figure 19). If the cusp cross section is effectively a parallelogram (Figure 17 left) the sides of the Eiffel tower match straight across (Figure 19 left) in the sense that people travelling across one face of the tower will re-enter the opposite face on the same level at which they left. This condition ensures that the hyperbolic structure is complete. If, on the other hand, the cusp cross section is not a parallelogram (Figure 17 right), then the sides of the Eiffel tower match with a vertical offset (Figure 19 right). For example, travellers leaving the tower at point $`B`$ on one level will re-enter at point $`B^{}`$ on a lower level. Note that the width $`w`$ of the upper quadrilateral’s long side equals the width $`w^{}`$ of the lower quadrilateral’s short side.

Henceforth we will restrict our attention to the case that the offset in one direction is a rational multiple of the offset in the transverse direction (Figure 20). Cutting along a consistent set of cross sections (like those illustrated in Figure 20) splits the cusp into an infinite set of bricks, all of equal height. Ignore for a moment the bricks’ freshly cut top and bottom faces, and instead glue them together along their side faces. The result will be a solid cylinder (Figure 21) with infinitely many progressively narrower bricks spiraling in towards the center. The vertical geodesic at the exact center is missing, and indeed plays the role in three dimensions of the missing geodesics in Figure 7. Restoring the gluings on the bricks’ top and bottom faces converts the cylinder into a solid torus, still with its central geodesic missing. Typically the cylinder’s bottom glues to its top with some nonzero twist.

Filling in the missing geodesic at the center of the solid torus (Figure 21) realizes a Dehn filling on the link complement. To read off the Dehn filling coefficients, simply note how a meridian of the solid torus wraps around the cusp. In the example shown (see Figure 22 for a top view) any topological meridian will wrap $`5`$ times around the quadrilateral’s “long direction” and $`2`$ times around its “short direction”. Typically the “long direction” is chosen to be a longitude of the original knot or link while the “short direction” is chosen to be a meridian of the original link, making this a $`(2,5)`$ Dehn surgery.

In practice, of course, we don’t randomly deform the hyperbolic structure and then wait to see what Dehn filling coefficients emerge. Instead, we choose the Dehn filling coefficients $`(p,q)`$ in advance and ask what deformation of the hyperbolic structure will accommodate them. Recall from Figure 17 that a product of complex dihedral angles gives the rotational/dilational factor taking one side of the quadrilateral to the other. In Section 4 we insisted that that product be $`1`$; more precisely we replaced the naive product equation $`z_i=1`$ with the more powerful logarithmic equation $`\mathrm{log}z_i=0`$ to guard against stray multiples of $`2\pi i`$. Here we apply the same technique, but focusing on the arbitrary quadrilateral (Figure 17 right) instead of the parallelogram (Figure 17 left). We now get one expression $`\mathrm{log}z_i`$ for the rotation/dilation in the meridional (“short”) direction and a different expression $`\mathrm{log}z_i^{}`$ for the rotation/dilation in the longitudinal (“long”) direction. Tracing all the way around the loop in Figure 22 returns us to our starting point with a $`2\pi `$ rotation. The loop consists of $`p`$ meridians and $`q`$ longitudes, so the analytic condition is

$$p\mathrm{log}z_i+q\mathrm{log}z_i^{}=2\pi i.$$
(4)
In Section 4 we had supplemented the edge equations with the cusp equations to solve for the hyperbolic structure on the cusped manifold. We now instead supplement the edge equations with the Dehn filling equations (4) to solve for the hyperbolic structure on the Dehn filled manifold.

Acknowledgement. I thank Adam Weeks Marano for help with the illustrations.


text:
# Active Internet Traffic Filtering: Real-time Response to Denial-of-Service Attacks

## I Introduction

Denial of Service (DoS) attacks are recognized as one of the most challenging threats to Internet security. Any organization or enterprise that is dependent on the Internet can be subject to a DoS attack, causing its service to be severely disrupted, if not fail completely. The attacker typically uses a worm to create an “army” of zombies, which she orchestrates to flood the victim’s site with malicious traffic. This malicious traffic exhausts the victim’s resources, thereby seriously affecting the victim’s ability to respond to normal traffic.

A network layer solution is required because the end-user or end-organization has no way to protect its tail circuit from being congested by an attack, causing the disruption sought by the attacker. For example, if an enterprise has a $`10`$ Mbps connection to the Internet, an attacker can command its zombies to send traffic far exceeding this $`10`$ Mbps rate to this enterprise, completely congesting the downstream link to the enterprise and causing normal traffic to be dropped.

Network operators use conventional router filtering capabilities to respond to DoS attacks. Typically, an operator of a site under attack identifies the nature of the packets being used in the attack by some packet collection facility, installs a filter in its firewall/edge router to block these packets and then requests its ISP to install comparable filters in its routers to remove this traffic from the tail circuit to the site. Each ISP can further communicate with its peering ISPs to block this unwanted traffic as well, if it so desires.

Currently, this propagation of filters is manual: the operator on each site determines the necessary filters and adds them to each router configuration. In several attacks, the operators of different networks have been forced to communicate by telephone given that the network connection, and thus email, was inoperable because of the attack.

As DoS attacks become increasingly sophisticated, manual filter propagation becomes unacceptably slow or even infeasible. For example, an attack can switch from one protocol to another, move between source networks as well as oscillate between on and off far faster than any human can respond. In general, network operators are confronting an “arms race” in which any defense, such as manually installed filters, is viewed as a challenge by the community of attacker-types to defeat. Exploiting a weakness such as human speeds of filter configuration is an obvious direction for an attacker to pursue.

The concept of automatic filter propagation has already been introduced in \[MBF+01\]: a router is configured with a filter to drop (or rate-limit) certain traffic; if it continues to drop a significant amount of this traffic, it requests that the upstream router take over and block the traffic. However, the crucial issues associated with automatic filter propagation are still unaddressed.

The real problem is how to efficiently manage the bounded number of filters available to a network operator to provide this filtering support. An attacker can change protocols, source addresses, port numbers, etc. requiring a very large number of filters. However, a sophisticated hardware router has a fixed maximum number of wire-speed filters that can block traffic with no degradation in router performance. The maximum is determined by hardware table sizes and is typically limited to several thousand. A software router is typically less constrained by table space, but incurs a processing overhead for each additional filter. This usually limits the practical number of filters to even less than a hardware router. Moreover, there is a processing cost at each router for installing each new filter, removing the old filters and sending and receiving filter propagation protocol messages.

Given the restricted amount of filtering resources available to each router, hop-by-hop filter propagation towards the attacker’s site clearly does not scale: Internet backbone routers would quickly become the “filtering bottleneck” having to satisfy filtering requests coming from all the corners of the Internet. Fortunately, traceback \[SWKA00\] \[SPS+01\] makes it possible to identify a router close to the attacker and send it a filtering request directly. However, any filter propagation mechanism other than hop-by-hop raises a serious security issue: Once a router starts accepting filtering requests from unknown sources, how can it trust that these requests are not forged by malicious nodes seeking to disrupt normal communication between other nodes?

In this paper we propose a new filter propagation protocol called AITF (Active Internet Traffic Filtering): The victim sends a filtering request to its network gateway. The victim’s gateway temporarily blocks the undesired traffic, while it propagates the request to the attacker’s gateway. As we will see, the protocol both motivates and assists the attacker’s gateway to block the attack. Moreover, a router receiving a filtering request satisfies it only if it determines that the requestor is on the same path with the specified undesired traffic. Thus, the filter cannot affect any nodes in the Internet other than those already operating at the mercy of the requestor.

The novel aspect of AITF is that it enables each participating service provider to guarantee to its clients a *specific, significant amount of protection against DoS attacks*, while it requires only a *bounded credible amount of resources*. At the same time it is *secure* i.e., it cannot be abused by a malicious node to harm (e.g. block legitimate traffic to) other nodes. Finally, it *scales with Internet size* i.e., it keeps its efficiency in the face of continued Internet growth.

## II Active Internet Traffic Filtering (AITF)

### II-A Terminology

A *flow label* is a set of values that captures the common characteristics of a traffic flow – e.g., “all packets with IP source address $`S`$ and IP destination address $`D`$”.

A *filtering request* is a request to block a flow of packets – all packets matching a specific wildcarded flow label – for the next $`T`$ time units.

A *filtering contract* between networks $`A`$ and $`B`$ specifies:

1. The filtering request rate $`R_1`$ at which $`A`$ accepts filtering requests to block certain traffic to $`B`$.
2. The filtering request rate $`R_2`$ at which $`A`$ can send filtering requests to get $`B`$ to block certain traffic from coming into $`A`$.

An *AITF network* is an Autonomous Domain which has a filtering contract with each of its end-hosts and each neighbor Autonomous Domain directly connected to it. An *AITF node* is either an end-host or a border router 111A *border router* is a router that has interfaces in more than one AITF networks. in an AITF network.

Finally, we define the following terms with respect to an undesired flow: The *attack path* is the set of AITF nodes the undesired flow goes through. The *attacker* is the origin of the undesired flow. The *victim* is the target of the undesired flow. The *attacker’s gateway* is the AITF node closest to the attacker along the attack path. Similarly, the *victim’s gateway* is the AITF node closest to the victim along the attack path.

### II-B Overview

The AITF protocol enables a service provider to protect a client against $`N`$ undesired flows, by using only $`nN`$ filters and a DRAM cache of size $`O(N)`$. The motivation is that each router can afford gigabytes of DRAM but only a limited number of filters.

In an AITF world, each Autonomous Domain (AD) is an AITF network i.e., it has filtering contracts with all its end-hosts and peering ADs. These contracts limit the rates by which the AD can send/receive filtering requests to/from its end-hosts and peering ADs. The limited rates allow the receiving router to police the requests to the specified rates and indiscriminately drop requests when the rate is in excess of the agreed rate. Thus, the router can limit the CPU cycles used to process filtering requests as well as the number of filters it requires.

An AITF filtering request is initially sent from the victim to the victim’s gateway; the victim’s gateway propagates it to the attacker’s gateway; finally, the attacker’s gateway propagates it to the attacker. Both the victim’s gateway and the attacker’s gateway install filters to block the undesired flow. The victim’s gateway installs a filter only temporarily, to immediately protect the victim, while it waits for the attacker’s gateway to take responsibility. The attacker’s gateway is expected to install a filter and block the undesired flow for $`T`$ time units.

If the undesired flow stops within some grace period, the victim’s gateway interprets this as a hint that the attacker’s gateway has taken over and removes its temporary filter. This leaves the door open to “on-off” undesired flows 222When the attacker’s gateway does not cooperate, the attacker can start an undesired flow, stop long enough to trick the victim’s gateway into removing its temporary filter, then start again and so on.. In order to detect and block such “on-off” flows, the victim’s gateway needs to remember each filtering request for at least $`T`$ time units. Thus, the victim’s gateway, installs a filter for $`T_{tmp}T`$ time units, but keeps a “shadow” of the filter in DRAM for $`T`$ time units 333 Keeping each filter for $`T`$ time units is very expensive – doing so would defeat the whole purpose of pushing filtering to the attacker’s gateway..

The attacker’s gateway expects the attacker to stop the undesired flow within a grace period. Otherwise, it holds the right to disconnect from her. This fact encourages the attacker to stop the undesired flow. Similarly, the victim’s gateway expects the attacker’s gateway to block the undesired flow within a grace period. Otherwise, the mechanism *escalates*: The victim’s gateway now plays the role of the victim (i.e., it sends a filtering request to its own gateway) and the attacker’s gateway plays the role of the attacker (i.e., it is asked to stop the undesired flow or risk disconnection). The escalation process should become clear with the example in II-D.

Thus, the mechanism proceeds in *rounds*. At each round, only four nodes are involved. In the first round, the mechanism tries to push filtering of undesired traffic back to the AITF node closest to the attacker. If that fails, it tries the second closest AITF node to the attacker and so on.

### II-C Basic protocol

The AITF protocol involves only one type of message: a *filtering request*. A filtering request contains a *flow label* and a *type* field. The latter specifies whether this request is addressed to the victim’s gateway, the attacker’s gateway or the attacker.

The only nodes in an AITF network that speak the AITF protocol are end-hosts and border routers. Internal routers do not participate.

AITF node $`X`$ sends a filtering request to AITF node $`Y`$, when $`X`$ wants a certain traffic flow coming through $`Y`$ to be blocked for $`T`$ time units.

When AITF node $`Y`$ receives a filtering request, it checks which end-host or peering network the request is received from/through. If that end-host or peering network has exceeded its allowed rate, the request is dropped. If not, $`Y`$ looks at the specified undesired flow label and takes certain actions:

* If $`Y`$ is the victim’s gateway:

1. It installs a *temporary* filter to block the undesired flow for $`T_{tmp}T`$ time units.
    2. It logs the filtering request in DRAM for $`T`$ time units.
    3. It propagates the filtering request to the attacker’s gateway. If the attacker’s gateway does not block the flow within $`T_{tmp}`$ time units, $`Y`$ propagates the filtering request to its own gateway.
* If $`Y`$ is the attacker’s gateway:

1. It installs a filter to block the undesired flow for $`T`$ time units.
    2. It propagates the filtering request to the attacker. If the attacker does not stop the flow within a grace period, $`Y`$ disconnects from her.
* If $`Y`$ itself is the attacker, it stops the flow (to avoid disconnection).

We should note that the behavior described above is that of a non-compromised, non-malicious node. Neither the attacker not even the attacker’s gateway are expected to always conform to this behavior. AITF operation does not rely on their cooperation.

### II-D Example

In Figure 1 $`G\mathrm{\_}host`$ – which stands for “good host” – is an end-host residing in enterprise network $`G\mathrm{\_}net`$, which is connected to local ISP $`G\mathrm{\_}isp`$ through router $`G\mathrm{\_}gw1`$. $`G\mathrm{\_}isp`$ runs a regional network that connects through its backbone router $`G\mathrm{\_}gw2`$ to a wide-area ISP $`G\mathrm{\_}wan`$. Similarly, $`B\mathrm{\_}host`$ – which stands for “bad host” – is an end-host residing in enterprise network $`B\mathrm{\_}net`$ etc.

$`B\mathrm{\_}host`$ starts sending an undesired flow to $`G\mathrm{\_}host`$. $`G\mathrm{\_}host`$ sends a filtering request to $`G\mathrm{\_}gw1`$ against $`B\mathrm{\_}host`$. Upon reception of $`G\mathrm{\_}host`$’s request, $`G\mathrm{\_}gw1`$ temporarily blocks the undesired flow but also propagates the request to $`B\mathrm{\_}gw1`$.

On the other side, upon reception of $`G\mathrm{\_}gw1`$’s request, $`B\mathrm{\_}gw1`$ immediately blocks the undesired flow, but also propagates the filtering request to $`B\mathrm{\_}host`$. $`B\mathrm{\_}host`$ either stops the undesired flow or risks being disconnected. Thus, if $`B\mathrm{\_}gw1`$ cooperates, by the end of the first round, filtering of the undesired flow has been successfully pushed to the AITF node closest to the attacker ($`B\mathrm{\_}gw1`$).

Of course, $`B\mathrm{\_}gw1`$ may decide not to cooperate and ignore the filtering request. Then, the mechanism escalates: $`G\mathrm{\_}gw1`$ propagates the filtering request to $`G\mathrm{\_}gw2`$. $`G\mathrm{\_}gw2`$ temporarily blocks all undesired traffic, but also propagates the filtering request to $`B\mathrm{\_}gw2`$ and so on. Thus, if $`B\mathrm{\_}gw2`$ cooperates, by the end of the second round, filtering of the undesired flow has been successfully pushed to the second closest to the attacker AITF node ($`B\mathrm{\_}gw2`$).

In the worst-case scenario, even $`B\mathrm{\_}gw3`$ refuses to cooperate. As a result, $`G\mathrm{\_}gw3`$ disconnects from $`B\mathrm{\_}gw3`$.

### II-E Verifying a filtering request

In a network architecture where source address spoofing is allowed, compromised node $`M`$ can maliciously request the blocking of traffic from $`A`$ to $`V`$ thereby disrupting their communication. To avoid this, we add a simple extension to the basic protocol.

The extension introduces two more messages: A *verification query* and a *verification reply*. Both types include a *flow label* and a *nonce* (i.e., a random number).

When router $`Y`$ receives a filtering request, which asks for the blocking of a traffic flow from attacker $`A`$ to victim $`V`$, $`Y`$ verifies that the request is real before taking any action to satisfy it. If $`Y`$ is the victim’s gateway, this verification is trivial with appropriate ingress filtering. If $`Y`$ is the attacker’s gateway, verification is accomplished through the following “3-way handshake”:

1. Router $`Y`$ receives a filtering request, asking for the blocking of a traffic flow from attacker $`A`$ to victim $`V`$.
2. $`Y`$ sends a verification query to $`V`$, asking “Do you really not want this traffic flow?”
3. $`V`$ responds to $`Y`$ with a verification reply. The reply must include the same flow label and nonce included in the query.

If the nonce on $`V`$’s reply is the same with the nonce on $`Y`$’s query, $`Y`$ accepts the request as real and proceeds to satisfy it. The “3-way handshake” is further discussed in III-B.

### II-F Assumptions

AITF operation assumes that the victim’s gateway can determine

* Who is the attacker’s gateway (in order to propagate the request).
* Who is the next AITF node on the attack path (in order to escalate, if necessary).

These assumptions are met, if an efficient traceback technique as those described in \[SWKA00\] \[SPS+01\] is available.

Also AITF assumes that off-path traffic monitoring is not possible i.e., if node $`M`$ is not located on the path from node $`A`$ to node $`V`$, then $`M`$ cannot monitor traffic sent on that path (this assumption is necessary for the “3-way handshake”).

## III Discussion

### III-A Why it works

The basic idea of AITF is to push filtering of undesired traffic to the network closest to the attacker. That is, hold a service provider responsible for providing connectivity to a misbehaving client and have it do the dirty job. The question is, why would the attacker’s service provider accept (or at least be encouraged) to do that?

If the attacker’s service provider does not cooperate, it risks being disconnected by its own service provider. This makes sense for both of them: If $`B\mathrm{\_}net`$ in Figure 1 refuses to block its misbehaving client, the filtering burden falls on $`B\mathrm{\_}isp`$. Thus, it makes sense for $`B\mathrm{\_}isp`$ to consider $`B\mathrm{\_}net`$ a bad client and disconnect from it. On the other hand, this offers an incentive to $`B\mathrm{\_}net`$ to cooperate and block the undesired flow. Otherwise, it will be disconnected by $`B\mathrm{\_}isp`$, which will result in all of its clients being dissatisfied.

Moreover, AITF offers an economic incentive to providers to protect their network from the inside by employing appropriate ingress filtering. If a provider pro-actively prevents spoofed flows from exiting its network, it lowers the probability of an attack being launched from its own network, thus reducing the number of expected filtering requests it will later have to satisfy to avoid disconnection.

In short, AITF creates a cost vs quality trade-off for service providers: Either they pay the cost to block the undesired flows generated by their few bad clients, or they run the risk of dissatisfying their legitimate clients, which are the vast majority. Thus, the quality of a provider’s service is now related to its capability to filter its own misbehaving clients.

### III-B Why it is secure

The greatest challenge with automatic filtering mechanisms is that compromised node $`M`$ may maliciously request the blocking of traffic from $`A`$ to $`V`$, thereby disrupting their communication. AITF prevents this through the “3-way handshake” described in II-E.

The “3-way handshake” does not exactly verify the authenticity of a filtering request. It only enables $`A`$’s gateway to verify that a request to block traffic from $`A`$ to $`V`$ has been sent by a node located on the path from $`A`$ to $`V`$. A compromised router located on this path can naturally forge and snoop handshake messages to disrupt $`A`$-$`V`$ communication. However, such a compromised router can disrupt $`A`$-$`V`$ communication anyway, by simply dropping the corresponding packets. 444We assumed that off-path traffic monitoring is impossible. Thus, an off-path malicious node cannot snoop handshake messages.

In short, AITF cannot be abused by a compromised node to cause interruption of a legitimate traffic flow, unless that compromised node is responsible for routing the flow, in which case it can interrupt the flow anyway.

### III-C Why it scales

AITF scales with Internet size, because it pushes filtering of undesired traffic to the leaves of the Internet, where filtering capacity follows Internet growth.

In most cases, AITF pushes filtering of undesired traffic to the provider(s) of the attacker(s). Thus, the amount of filtering requests a provider is asked to satisfy grows proportionally to the number of the provider’s (misbehaving) clients. However, intuitively, a provider’s filtering capacity also grows proportionally to the number of its clients. 555In the AITF model, the filtering contract becomes part of a provider’s services. Thus, a part of each client’s service fee is invested in provisioning the provider’s routers with extra filters. In short, a provider’s filtering capacity follows the provider’s filtering workload.

If the attacker’s provider is itself compromised, AITF naturally fails to push filtering to it. Instead, filtering is performed by another network, closer to the Internet core. If this situation occurred often, then the scalability argument stated above would be false. Fortunately, compromised routers are a very small percentage of the Internet infrastructure. 666It is difficult to compromise a router, because of the limited number of potentially exploitable services it offers. Moreover, service providers have an immense economic incentive to keep their routers uncompromised. Thus, AITF fails to push filtering to the attacker’s provider with a very small probability.

## IV Performance Analysis

In this section we provide simple formulas that describe AITF performance. For lack of space and given that our formulas are very simple and intuitive, we defer any details to \[AC03\].

### IV-A The victim’s perspective

#### IV-A1 Effective bandwidth of an undesired flow

AITF significantly reduces the *effective bandwidth* of an undesired flow – i.e., the bandwidth of the undesired flow actually experienced by the victim. Specifically, it can be shown that AITF reduces the effective bandwidth of an undesired flow by a factor of

$$r\frac{n(T_d+T_r)}{T}$$

where $`n`$ is the number of non-cooperating 777 By *non-cooperating* node we mean an AITF node, which does not take its responsibility to filter an undesired flow for $`T`$ time units.  AITF nodes on the attack path, $`T_d`$ is attack detection time and $`T_r`$ is the one-way delay from the victim to its gateway. $`T`$ is the timeout associated with all filtering requests i.e. each filtering request asks for the blocking of a flow for $`T`$ time units. For example, if the only non-cooperating node on the attack path is the attacker, and if the one-way delay from the victim to its gateway is $`T_r=50`$ msec, for $`T=1`$ min, an AITF node can reduce the effective bandwidth of an undesired flow by a factor $`r0.00083`$. 888 $`T_d`$ may be significant the first time the undesired flow is detected. Here, we ignore that initial overhead. Detecting a reappearing undesired flow could be as fast as matching a received packet header to a logged undesired flow label i.e., insignificant compared to the one-way delay to the victim’s gateway.

Here we only demonstrate this result for $`n=1`$ i.e., when the only non-cooperating node on the attack path is the attacker: At time $`0`$ the attacker starts the undesired flow; at time $`T_d`$ the victim detects it and sends a filtering request; at time $`T_d+T_r`$ the victim’s gateway temporarily blocks the flow and the victim stops receiving it; the flow is eventually blocked by the attacker’s gateway and released after time $`T`$. Thus, if the original bandwidth of the undesired flow is $`B`$, its effective bandwidth is $`B_eB\frac{T_d+T_r}{T}`$.

When $`n1`$ i.e., when $`1`$ or more AITF routers close to the attacker are non-cooperating, the attacker can play “on-off” games: Pretend to stop the undesired flow to trick the victim’s gateway into removing its filter, then resume the flow etc. The victim’s gateway detects and blocks such attackers by using its DRAM cache.

#### IV-A2 Number of undesired flows

An AITF node is guaranteed protection against a specific number of undesired flows, which depends on its contract with its service provider. Specifically, it can be shown that if a client is allowed to send $`R_1`$ filtering requests per time unit to the provider, then the client is protected 999 When we say that the client is “protected” against an undesired flow, we mean that the client can significantly reduce the effective bandwidth of the flow, as described in the previous subsection. against

$$N_v=R_1T$$

simultaneous undesired flows. For example, for $`R_1=100`$ filtering requests per second and $`T=1`$ min, the client is protected against $`N_v=6,000`$ simultaneous undesired flows.

### IV-B Filtering close to the victim

AITF enables a service provider to protect a client against $`N_v`$ undesired flows by using only $`n_vN_v`$ filters. Specifically, it can be shown that if a client is allowed to send $`R_1`$ filtering requests per time unit to the provider, the provider needs $`n_v`$ filters and a DRAM cache that can fit $`m_v`$ filtering requests in order to satisfy all the requests, where

$$n_v=R_1T_{tmp},m_v=R_1T$$

$`T_{tmp}`$ is the amount of time that elapses from the moment the victim’s gateway installs a temporary filter until it removes it. The purpose of the temporary filter is to block the undesired flow until the attacker’s gateway takes over. Therefore, $`T_{tmp}`$ should be large enough to allow the traceback from the victim’s gateway to the attacker’s gateway plus the 3-way handshake. For example, suppose we use an architecture like \[CG00\], where traceback is automatically provided inside each packet. Then traceback time is $`0`$. If the 3-way handshake between the two gateways takes $`600`$ msec, for $`R_1=100`$ filtering requests per second and $`T=1`$ min, the service provider needs $`n_v=60`$ filters to protect a client against $`N_v=6,000`$ undesired flows.

### IV-C Filtering close to the attacker

AITF requires a bounded amount of resources from the attacker’s service provider. Specifically, if a service provider is allowed to send $`R_2`$ filtering requests per time unit to a client, then the provider needs

$$n_a=R_2T$$

filters in order to ensure that the client satisfies all the requests. Given these resources, the provider can filter $`N_a=n_a=R_2T`$ simultaneous undesired flows generated by the client. For example, for $`R_2=1`$ filtering request per second and $`T=1`$ min, the provider needs $`n_a=60`$ filters for the client. This filtering request rate allows the provider to filter up to $`N_a=60`$ simultaneous undesired flows generated by the client.

### IV-D The attacker’s perspective

We have defined an attacker as the source of an undesired flow. By this definition, an attacker is not necessarily a malicious/compromised node; it is simply a node being asked to stop sending a certain flow. A legitimate AITF node must be provisioned to stop sending undesired flows when requested, in order to avoid disconnection.

AITF requires a bounded amount of resources from the attacker as well. Specifically, if a service provider is allowed to send $`R_2`$ filtering requests per time unit to a client, the client needs

$$n_a=R_2T$$

filters (as many as the provider) in order to satisfy all the requests. For example, for $`R_2=1`$ filtering request per second and $`T=1`$ min, the client needs $`n_a=60`$ filters.

## V Related Work

In \[MBF+01\] Mahajan et al. propose mechanisms for detecting and controlling high bandwidth traffic aggregates. One part of their work discusses how a node determines whether it is congested and how it identifies the aggregate(s) responsible for the congestion. In contrast, we start from the point where the node has identified the undesired flow(s). In that sense, their work and our work are complementary. Another part of their work discusses how much to rate-limit an annoying aggregate due to a DoS attack or a flash crowd. In contrast, our mechanism focuses on DoS attack traffic and attempts to limit it to rate $`0`$. 101010 We believe that DoS attacks should be addressed separately from flash crowds: Flash crowd aggregates are created by legitimate traffic. Therefore, it makes sense to rate-limit them instead of completely blocking them. On the contrary, DoS attack traffic aims at disrupting the victim’s operation. Therefore, it makes sense to block it. Blocking a traffic flow is simpler and cheaper than rate-limiting it. Moreover, DoS attack traffic is generated by malicious/compromised nodes. Therefore, it demands a more intelligent defense mechanism.

The part of their work most related to ours proposes a cooperative pushback mechanism: A congested node attempts to rate-limit an aggregate by dropping a portion of its packets. If the drop rate remains high for several seconds, the node considers that it has failed to rate-limit the aggregate and asks its adjacent upstream routers to do it. If the recipient routers also fail to rate-limit the aggregate, they recursively propagate pushback further upstream.

A pushback request is propagated hop by hop by the victim towards the attacker. In contrast, the propagation of an AITF filtering request involves only $`4`$ nodes: the victim, the victim’s gateway, the attacker’s gateway and the attacker – we claim that this allows AITF to scale with Internet size. A pushback request does not force the recipient router to rate-limit the problematic aggregate; it relies on its good will to cooperate. In contrast, AITF forces the attacker to discontinue the undesired flow and the attacker’s service provider to filter the attacker or else risk disconnection – we claim that this makes AITF deployable.

In \[PL01\] Park and Lee propose DPF (Distributed Packet Filtering), a distributed ingress-filtering mechanism for pro-actively blocking spoofed flows. In contrast, AITF aims at blocking *all* undesired – including spoofed – flows as close as possible to their sources. Thus, it cannot be replaced by DPF. On the other hand, DPF blocks most spoofed flows *before* they reach their destination i.e., DPF is proactive, whereas AITF is reactive. In that sense, DPF and AITF are complementary.

In \[KMR02\] Keromytis et al. propose SOS (Secure Overlay Services), an architecture for pro-actively protecting against DoS attacks the communication between a pre-determined location and a specific set of users who have authorized access to communicate with that location. In contrast, AITF addresses the more general problem of protecting against DoS attacks any location accessible to all Internet users.

Finally, \[SWKA00\] and \[SPS+01\] propose traceback solutions i.e., mechanisms that enable a victim to reconstruct the path followed by attack packets in the face of source address spoofing. As already mentioned, an efficient traceback mechanism is necessary to AITF operation.

## VI Conclusions

We presented AITF, an automatic filter propagation mechanism, according to which each Autonomous Domain (AD) has a filtering contract with each of its end-hosts and neighbor ADs. A filtering contract with a neighbor provides a guaranteed, significant level of protection against DoS attacks coming through that neighbor in exchange for a reasonable, bounded amount of router resources.

Specifically:

* Given a filtering contract between a client and a service provider, which allows the client to send $`R_1`$ filtering requests per time unit to the provider, the provider can protect the client against a large number of undesired flows $`N_v=R_1T`$, by significantly limiting the effective bandwidth of each undesired flow. The provider achieves this by using only a modest number of filters $`n_v=R_1T_{tmp}N_v`$.
* Given a filtering contract between a client and a service provider, which allows the provider to send $`R_2`$ filtering requests per time unit to the client, both the client and the provider need a bounded number of filters $`n_a=R_2T`$ to honor their contract.

We argued that AITF successfully deals with the biggest challenge to automatic filtering mechanisms: source address spoofing. Namely, we argued that it is not possible for any malicious/compromised node to abuse AITF in order to interrupt a legitimate traffic flow, unless the compromised node is responsible for routing that flow, in which case it can interrupt the flow anyway.

Finally, we argued that AITF scales with Internet size, because it pushes filtering of undesired traffic to the service providers of the attackers, unless the service providers are themselves compromised. Fortunately, compromised routers are a very small percentage of Internet infrastructure. Thus, in the vast majority of cases, AITF pushes filtering of undesired traffic to the leaves of the Internet, where filtering capacity follows Internet growth.


text:
# LOFAR, a new low frequency radio telescope

## 1 LOFAR, the telescope

The mission of LOFAR is to survey the Universe at frequencies in the range 10 - 240 MHz (corresponding to wavelengths of $`1.530`$ m). Until now this portion of the spectrum has been virtually neglected. This is mainly because at these low radio frequencies the natural image quality is set by “radio seeing”, i.e. severe image blurring due to the ionosphere. Recent work with the VLA at 74 MHz nicely illustrates the problem of “radio seeing”, with the apparent position of objects being shifted by more than an arcminute on timescales of tens of minutes (Cohen, Röttgering, Kassim et al. 2003). Recently Cotton and Condon (2002) developed an algorithm to correct for these diffraction effects. The basic idea is that on short regular timescales the wandering of positions of a number of bright sources within the primary beam is measured. This timescale is chosen as a compromise between being long enough so that a sufficient number of sources are visible, and short enough so that changes in the ionosphere can be smoothly tracked. For observations at 74 MHz, typically for 5-10 sources, shifts are measured on timescales of 1-2 minutes. A Zernike polynomial is then fitted to the source shifts and the resulting fit is used to correct for the ionospheric phase fluctuation.

LOFAR’s design is such that a similar scheme will work even under the severe ionospheric conditions present at these low frequencies. Each of the LOFAR stations will form a baseline with the very sensitive central core, which comprises 25 % of the collecting area. The sensitivity of each of those baselines is such that, within the coherence time of the ionosphere and within the primary beam of each station, enough sources are visible to perform the needed calibration.

LOFAR will have 2 antenna systems, one for the 10-90 MHz range, and one for the 110-240 MHz range. These antennas will be placed in soccer-field sized stations yielding, for each station, effective aperture sizes that will range from 50 m to 150 m, depending on frequency. The signals from each antenna are digitised and fed into the station beamformer. The beamformer can produce up to eight coherent “station-beams” within the primary power pattern of the antenna element in use. In total of the order of 100 stations will make up the array. These stations will be distributed over an area with a diameter of about 400 km. For a sketch of a possible layout if LOFAR is built in the Netherlands, see Figure 1.

An overview of the resulting resolutions and sensitivities is given in Table 1. There is an interesting trade-off between sensitivity and number of beams. If observations are carried out with 8 different beams, then the maximum bandwidth available for each beam is 4 MHz. It is also possible to observe with only one beam and use the full 32 MHz bandwidth, thus obtaining greater instantaneous sensitivity.

## 2 Science case

The science case for LOFAR is broad; there are important application of LOFAR not only for astrophysics, but also for studies of the Earth’s ionosphere and the physical properties of the solar wind. Here we will briefly sketch the general astrophysical science case and subsequently those applications that are most relevant for this workshop.

As a direct result of the calibration scheme that measures phase fluctuation of the ionosphere, LOFAR will map its dynamic structure and variability over a wide range of scale sizes. Emission of a longwavelength radar directed at the sun would be scattered back by Solar Coronal mass ejections (CMEs). The Doppler shifts introduced by different parts of an outward moving CME will result in a characteristic frequency and time dependent signature. This not only enables studies of the CMEs, but would also lead to accurate predictions for occurrences of geomagnetic storms.

An interesting application of LOFAR is its use as a detector for high-energy cosmic rays (HECRs). The existence of HECRs at energies between 1015 – 1020.5 eV is an outstanding challenge for particle astrophysics. Both the sites and processes for accelerating these particles are unknown. A primary CR induces a particle cascade in the atmosphere which emits coherent radio emission in the terrestrial magnetosphere (Falcke and Gorham 2003). From the arrival times and intensities of the radio pulse at various antennas of LOFAR, the poorly understood development of the electromagnetic part of the cascade can be studied. Furthermore, the direction of the primary particle can then be determined to an accuracy of 1 degree, potentially revealing the origin of the cosmic rays.

LOFARs large instantaneous beam allows for the first time a sensitive unbiased survey for radio transients on a variety of time scales, ranging from a few tenths of seconds to many days. Rapid follow up with LOFAR at high resolution will give the accurate positions required for optical and X-ray identifications. There are numerous classes of sources that are variable or expected to be variable at low frequencies and these include radio supernovae, Gamma-ray burst afterglows, Galactic black-hole/neutron-stars, exo-planets and radio flare stars.

One of the most exciting goals of LOFAR will be to chart the end of the Dark Ages when the first stars and AGNs started to ionise the neutral baryonic gas pervading the Universe. LOFAR will study at which redshift range the bulk of the HI became ionised. Through studies of the spatial distribution of both the heated and still cold IGM, it will be possible to determine which objects or processes are responsible for re-ionising the Universe.

### Radioloud AGN

One of the main goals of LOFAR will be to survey the whole accessible sky at a number of the lower frequencies (e.g. 15, 30, 75 MHz) down to the confusion limit. These surveys will be complimented by surveys at higher frequencies (e.g. 120 and 200 MHz) with the aim of (i) obtaining good positional information, essential for optical identification and (ii) determining the higher frequency part of the radio spectrum.

Due to the low observing frequencies, LOFAR surveys will yield large numbers of radio galaxies with very steep radio spectra. Using the empirical correlation between radio spectral steepness and distance, (e.g. de Breuck et al. 2000), LOFAR surveys will be used to efficiently pick out very distant ($`z>5`$) radio galaxies. As discussed in many contributions to this workshop, study of these distant radio galaxies at other wavelengths will provide information about the formation of massive galaxies, AGN and proto-clusters.

It is possible that some of these radio galaxies are located at an epoch before reionisation has completely occurred. This would open up the possibility of studying the epoch of reionisation through observations of the absorbing neutral gas against these very distant radio galaxies (Carilli et al. 2002)

### Starforming galaxies

With its unprecedented sensitivity to non-thermal radio emission from star formation, LOFAR will detect large numbers of star-forming galaxies at an epoch at which the bulk of galaxy formation is believed to occur. Observing at 200 MHz, LOFAR should be able to detect the nearby star-forming galaxies, such as M82 and the “ultra-luminous infrared galaxy” Arp 220 (z=0.018), out to redshifts of respectively $`z=1.1`$ and out to $`z=3.3`$ (e.g. Garrett 2002). Since the ratio of radio flux to sub-mm flux is a sensitive redshift indicator (Carilli and Yun 1999), LOFAR surveys, in combination with data from new far-IR and millimeter facilities such as SIRTF, ALMA, and JWST, will therefore provide distances and thus allow for a complete census of the cosmic star-formation history, unhindered by the effects of dust obscuration.

### Cluster radio halos

Due to their large extent, low surface brightness, and steep-spectra, diffuse cluster sources are difficult to detect with conventional facilities, such as Westerbork and the VLA. However, their properties are well matched to LOFAR’s observational capabilities. The number of cluster halos that could potentially be detected with LOFAR has been estimated using a simple model (Enßlin and Röttgering 2002). This model takes into account the locally observed fraction of cluster radio halos, the observed relation between radio and X- ray luminosity, and a Press-Schecter description of the merging rate of massive clusters as a function of redshift. A LOFAR survey at 120 MHz covering half the sky to a 5-sigma flux limit of 0.1 mJy (1 hour per pointing) is feasible on the timescale of one year and could detect of the order of 1000 halos at the 10 sigma level, of which 25 % are expected to be at redshifts larger than $`z0.3`$.

The XMM X-ray telescope, the Planck satellite and the Sloan Digital Sky Survey should catalogue as many as 500,000 new clusters (Barthelmann and White 2002). LOFAR has sufficient sensitivity to detect existing radio halos in all such clusters. This will be very relevant for (i) understanding the dynamics of the cluster gas, (ii) determining the origin of their magnetic field content, and (iii) constraining physical models for the origin of these sources.

## 3 The Project

ASTRON (Dwingeloo, the Netherlands), M.I.T. (Cambridge, USA) and Naval Research Lab (Washington, USA) are responsible for the design, construction, operation and software of the LOFAR telescopes. The agreed timescale is ambitious and has the aim of full operations in 2008. Important milestones towards this goal are (i) a first test station with 100 antennas in 2003, (ii) the LOFAR core operational in 2005, and (iii) operations of the central core plus first outer stations in 2006.

A site characterisation committee is presently obtaining data needed to assess the suitability of LOFAR siting in the Netherlands, south-west Australia and the southern USA (Texas and New Mexico). A decision on the location for LOFAR is expected to be made in 2003.

The international project is supervised by an International Steering Committee (ISC), consisting of directors of the participating institutes. An Engineering Consortium (EC) is responsible for the design and implementation of the instrument. The Science Consortium Board (SCB) is responsible for developing the science case for LOFAR in close collaboration with the community and gives scientific input to the EC.

The Science Consortium Board very much welcomes suggestions for improving or optimising the design of the instrument for general or very specific applications. For further information, visit: www.LOFAR.org

Acknowledgements I would like to thank the following of people for many interesting discussions and fruitful collaborations: Ger de Bruyn, Aaron Cohen, Bill Cotton, Rob Fender, Michiel van Haarlem, Melanie Johnston-Hollitt, Namir Kassim, Jan Kuijpers, George Miley, Jan Noordam and Marco de Vos.