Cyril Gavoille
email: gavoille@labri.fr

Christian Glacet
email: glacet@labri.fr

Nicolas Hanusse
email: hanusse@labri.fr

David Ilcinkas
email: ilcinkas@labri.fr

Brief Announcement: Routing the Internet with Very Few Entries *

Keywords: compact routing, routing scheme, power-law graphs

This paper investigates compact routing schemes that are very efficient with respect to the memory used to store routing tables in internet-like graphs. We propose a new compact name-independent routing scheme whose theoretically proven average memory per node is upper-bounded by n γ , with constant γ < 1/2, while the maximum memory of any node is bounded by √ n and the maximum stretch of any route is bounded by 5. These bounds are given for the Random Power Low Graphs (RPLG) and hold with high probability. Moreover, we experimentally show that our scheme is very efficient in terms of stretch and memory in internet-like graphs (CAIDA and other maps). We complete this study by comparing our analytic and experimental results to several compact routing schemes. In particular, we show that the average memory requirements is better by at least one order of magnitude than previous schemes for CAIDA maps on 16K nodes.

INTRODUCTION

To achieve the routing task, a routing protocol typically uses routing tables stored at each node in order to find a path in the network. These tables are computed beforehand by what is usually called a routing scheme. One of the main goals in the context of routing is to reduce the storage of the routing information at each node (to allow quick routing decisions, fast updates, and scalability), while maintaining routes along paths as short as possible.

A routing scheme that guarantees a sub-linear1 routing table size at each node is qualified to be compact. There is a trade-off between the route efficiency (measured in terms of stretch) and the memory requirements (measured by the size or the number of entries in the routing tables). An extra desirable property of a routing scheme is to use arbitrary routing addresses (say based on processor IDs or MAC addresses) and thus independent of any topological information. Such routing schemes are called name-independent, in contrast with labeled routing schemes for which nodes are labeled by poly-logarithmic size addresses that do depend on the graph and can be freely designed to help routing decisions. In practical use, a labeled routing scheme has to use a location service that maps local information to labels, which could be a bottle-neck in regards to routing scalability, mobility and multi-homing.

Trade-offs between stretch and memory for routing in arbitrary graphs are well known, and optimal nameindependent algorithms exist (see for example [START_REF] Abraham | Compact name-independent routing with minimum stretch[END_REF]). Nevertheless for some types of routing, like routing in the AS-internet graph, optimizations can be done and trade-offs are still barely known. Indeed, this network, like many others, exhibits several structural properties that can help a lot for routing.

Routing in internet-like graphs has already received some attention in the literature. In particular [START_REF] Chen | A compact routing scheme and approximate distance oracle for power-law graphs[END_REF] and [START_REF] Tang | HDLBR: A name-independent compact routing scheme for power-law networks[END_REF] respectively studied labeled and nameindependent compact routing scheme for internet-like graphs. They both proved that the average number of entries in the routing tables for Random Power Low Graphs (RPLG, see Fig. 1) can be significantly lower than for arbitrary graphs, and they both confirmed experimentally their analytic results on large CAIDA and "BC" maps2 .

RESULTS

Our contributions are the following. First we present a new stretch-5 name-independent routing scheme, that guar-Figure 1: The largest connected component of a graph sampled from RPLG(n, τ ) for n = 300 and power-law exponent τ = 2.9. This component has 216 nodes (whose size is depicted proportional to their degree), 280 edges, and maximum degree 19.

antees, in internet-like graphs, to produce compact routing tables of very small average size at every node.

Theorem 1. For any n-node graph sampled from RPLG(n, τ ) with power-low exponent τ ∈ (2, 3), within its largest connected component, the name-independent routing scheme CLUSTER has w.h.p.3 the following properties:

1. the maximal size of the routing tables is O(

√ n ); 2. the average size of the routing tables is 4 Õ(n γ ) with γ = 1 2 • τ -2 τ -1 for τ ≤ 2.5, and γ = (τ -2) 2 τ -1
otherwise; 3. the stretch factor is at most 5; 4. every routing decision takes constant time; and 5. headers have poly-logarithmic size.

Actually, Properties 3,4,5 hold for every connected graph.

Secondly we experimentally compare our scheme to AGMNT [START_REF] Abraham | Compact name-independent routing with minimum stretch[END_REF], DCR [START_REF] Gavoille | On the communication complexity of distributed name-independent routing schemes[END_REF], HDLBR [START_REF] Tang | HDLBR: A name-independent compact routing scheme for power-law networks[END_REF], and TZ + [START_REF] Chen | A compact routing scheme and approximate distance oracle for power-law graphs[END_REF]. In particular, Table 1 shows that our scheme, CLUSTER, improves significantly the routing table sizes on a CAIDA map (sampled from the AS network [Cai]) and on a BC graph, even though TZ + (a specialized variant of Thorup-Zwick routing scheme) is a labeled routing scheme. Moreover, TZ + scheme makes the assumption that τ is known whereas our scheme does not need this parameter. We have provided a fully distributed implementation for the schemes DCR, HDLBR, CLUSTER, and proved that each one generates all the routing tables in Õ(n 3/2 ) messages. No distributed implementation within o(n 2 ) messages is known for AGMNT.

OUR SCHEME

Preliminaries.

Similarly to TZ + and HDLBR, our algorithm is based on a set of landmark nodes positioned in the "center" of the graph. In our case, the k landmarks are composed of the highest degree node 1 plus its k -1 neighbors of highest degree, where k -1 = min{ √ n , deg( 1)}. Moreover, every landmark node i, i ∈ {1, . . . , k}, is provided with a distinct color c( i) ∈ {1, . . . , k}. Landmark nodes also share a balanced (w.h.p.) hash function h, as in [START_REF] Abraham | Compact name-independent routing with minimum stretch[END_REF], mapping in constant time all node identifiers to the color set {1, . . . , k}.

Routing tables.

Any landmark node i stores one entry per node v whose hash value is equal to the color of i, namely c( i). This entry corresponds to the path from i to v in some fixed shortest-path spanning tree T rooted at 1. Each path of T can be compressed into a poly-logarithmic size entry, e.g. by using the classical labeled compact routing scheme for trees from [START_REF] Fraigniaud | Routing in trees. 28th ICALP[END_REF]. This adds one entry to every node. Every landmark also stores one entry for each color c. This entry corresponds to the next-hop from i to the landmark with color c along a shortest path in the subgraph induced by the landmarks, a diameter two subgraph. As the hash function is balanced, the number of entries for landmark routing tables is at most k + n/k + O(1).

For every non-landmark node u, we define its vicinity ball Bu as the set of all nodes that are strictly closer to u than u, where u is a landmark closest to u. For every node v in Bu ∪ N (u) ∪ { u}, node u stores the next-hop on a shortest path to v, where N (u) denotes the neighbors of u. Thus, the number of entries for the routing table of u is at most |Bu| + deg(u) + O(1). However, for each node u with no landmark neighbors, N (u) ⊆ Bu.

Routing from u to v.

If u has an entry for v, then u can route directly to v. Otherwise u forwards the packet to u, its closest landmark. At this point, u computes the hash value h(v) of node v and forwards the packet to the landmark h of color h(v). Finally, the information stored in the entry corresponding to v in the routing table of h is used to route the packet to its final destination v via the tree T .

SKETCH OF THE PROOF

The proof of our main theorem is based on topological observations done on RPLG(n, τ ) graphs [START_REF] Chung | The Average Distance in a Random Graph with Given Expected Degrees[END_REF]. Those graphs are defined as follows. With each node vi, i ∈ {1, . . . , n}, we assign a weight wi = (n/i) 1/(τ -1) . There is an edge between node vi and vj with probability min{1, wiwj/σ}, where σ = i wi.

Memory size analysis.

The first step is to show that, w.h.p., k = √ n , i.e., the highest degree node 1 is larger than √ n. This implies that landmark routing tables have at most 2 √ n entries, and contributes to at most k • 2 √ n = 2n to the total number of entries. The degree of every non-landmark u is also lower than √ n. So, the maximum number of entries in a routing table is dominated by maxu |Bu| + √ n. And, the average number of entries is bounded by 1 n u |Bu| + O(1) since the average degree is O(σ/n) = O(1), the main component has Ω(n) nodes, and the landmark routing tables contribute to only 2n/Ω(n) = O(1) entries on the average.

Next we show that the sum of the weights, called the volume, of the set of nodes inside the cluster is polynomial, depends on τ ∈ (2, 3), but is always much larger than √ n. Then, we use one lemma from [START_REF] Chung | The Average Distance in a Random Graph with Given Expected Degrees[END_REF] [START_REF] Tang | HDLBR: A name-independent compact routing scheme for power-law networks[END_REF] that the route length for HDLBR is at most 2d + 2δ(τ ) where d is the source-destination distance and δ(τ ) the inter-landmark distance. We note that, w.h.p., δ(2.1) > 1, and from this observation one can derive that the maximum stretch is at least 6. We ran our own (distributed) version of HDLBR since results for AS and BC maps were not available. TZ + is not a name-independent routing scheme, and we have not implemented it. Thus, we have some unknown experimental values for this algorithm.

or intersect. This implies that the volume of every vicinity ball is upper bounded by a small polynomial. The last part consists in exhibiting a strong relationship between the volume and the number of nodes in the vicinity balls. We use the facts, shown in [START_REF] Chen | A compact routing scheme and approximate distance oracle for power-law graphs[END_REF], that the volume of a set of nodes is likely to be equal to the sum of their degrees, and that two balls of radius r and r + 1 do not differ too much in terms of their number of nodes.

Stretch analysis.

From the routing algorithm from u to v taken from the main connected component of G, we derive that the route length is either the distance d = dG(u, v) if v ∈ Bu, or bounded by dG(u, u)+dG( u, h )+dT ( h , v) otherwise. (Recall that the route goes first from u to u along a shortest path in G, then to h using the landmark subgraph, and then to v using T .) If w denotes the closest ancestor of v in T in the cluster, then the length of the route from h to v can be bounded by dT ( h , v) ≤ dT ( h , w) + dT (w, v) ≤ dG( v , v) + 2 by definition of v and T . Since dG( u, h ) ≤ 2, the route length is at most dG(u, u) + dG(v, v ) + 4. Note also that dG(v, v ) ≤ dG(v, u) + dG(u, u) = d + dG(u, u) since otherwise u would be a closer landmark for v than v . Assuming that v / ∈ Bu (otherwise the stretch is 1), it turns out also that dG(u, u) ≤ d. Overall, combining these inequalities, the route length is at most 3d + 4. However, if u is a landmark, the route length is at most dG

(u, u) + dG(v, v ) + 4 ≤ dG(u, u) + [d + dG(u, u)] + 4 = d + 4 since in this case u = u.
To summarize, either u is a landmark and the stretch is at most (d + 4)/d = 1 + 4/d ≤ 5, or u is not a landmark and the stretch is at most (3d + 4)/d = 3 + 4/d. This is at most 5 if d ≥ 2. On the other hand, if d = 1 then the stretch is only 1 since each non-landmark node u has the entries for N (u). Thus, the stretch factor of our scheme is at most 5 for all connected graphs.

Optimization.

For our experimentations, we proceed to several optimizations for the CLUSTER scheme. In particular, for every nonlandmark node u, we remove every entry for w ∈ Bu such that the shortest-path routing from u to w can actually be achieved by routing from u to its landmark u. In other words, we can clean Bu by removing every node w such that dG(u, w) = 1 + dG(u , w) where u is the next-hop to reach u from u. Another optimization addresses the landmark routing tables. For a landmark i, the set of entries to each node v with h(v) = c( i) is partionned into: 1) the entries for nodes at distance at most r = log n/ log log n from i; and 2) the remaining entries (for further nodes). For these latter entries we store a routing label of log 2 n/ log log n = r log n bits used for the routing in T as described in [START_REF] Fraigniaud | Routing in trees. 28th ICALP[END_REF]. And, for the former entries we use a different routing label, still of r log n bits, composed of the first r next-hops on a shortest path from i to v. Overall, this improves the average route length without extra cost on the number of entries or their size.

Table 1 :

 1 which states that (w.h.p.) two sets of nodes with high volumes are adjacent According to[START_REF] Vázquez | Internet topology at the router and autonomous system level[END_REF] the AS power-law exponent τ can be estimated to 2.1. The main component of the BC graph has 7873 nodes, whereas the AS graph is connected. It is proved in

	Name-indep. AGMNT DCR HDLBR CLUSTER	RPLG(n, τ ) for τ = 2.1 Stretchmax Memavg Memmax 3 Õ( √ n ) Õ( √ n ) 7 Õ( √ n ) Õ( √ n ) ≥6 O( √ n ) Ω(n 1/2+ε ) 5 Õ(n 1/22 ) O( √ n )	AS graph (n = 16 301) Stretchavg Memavg Memmax Stretchavg Memavg Memmax BC graph (n = 10K, τ = 2.1) ?? 465 1 261 1.56 396 1 143 1.74 465 1 261 1.63 396 1 143 1.52 106 2 324 1.24 404 1 877 1.59 4.05 415 1.75 6.47 228
	Labeled
	TZ +	5	O(n 1/12 )	O(n 1/12 )	??	??	??	1.30	55.2	??

W.r.t. the number of nodes in the graph.

The latter maps are the benchmark graphs used in the study of[START_REF] Brady | Compact routing on power law graphs with additive stretch[END_REF]. They are based on Power Low Random Graphs (a.k.a. PLRG) a model for internet-like graphs whose analytic study is less convenient than the RPLG model.

I.e., with probabilty at least 1 -1/n.

The notation Õ(f (n)) stands for O(f (n) • polylogf (n)).

* Supported by the ANR project DISPLEXITY (ANR-11-BS02-014).


Valerio Basile
email: v.basile@rug.nl

WordNet as an Ontology for Generation

In this paper we propose WordNet as an alternative to ontologies for the purpose of natural language generation. In particular, the synset-based structure of WordNet proves useful for the lexicalization of concepts, by providing ready lists of lemmas for each concept to generate.

Introduction

While RDF/OWL ontologies are a popular format to encode domain and general knowledge, there are alternatives. It is debatable, for instance, whether one should consider WordNet [START_REF] Miller | WordNet: A lexical database for English[END_REF] a computational ontology in the proper sense. This paper tries to answer to this question, by providing an overview of WordNet, an argument for its employment as a knowledge base for generation, and a practical example involving lexical choice.

WordNet has been used both as a standalone knowledge base and as a mean to augment existing RDF/OWL ontologies [START_REF] Lin | A survey of exploiting wordnet in ontology matching[END_REF]. Despite its wide application in other fields, such as, for instance, word sense disambiguation, WordNet has been rarely been applied to NLG. A notable exception is the work by Jing (1998) who proposes WordNet-based methods to address specific NLG tasks, in particular lexicalization and paraphrasing. The author shows that the open-domain nature of WordNet makes it a robust knowledge base to support generation in open-domain scenarios, but also that it can also used in combination with other knowledge bases, i.e., to adapt to a particular domain.

WordNet

The book detailing the WordNet project is titled "WordNet: an Electronic Lexical Database", thus as a starting point the resource can be defined as a structured database of words in a format readable by electronic calculators. For each word in the database, WordNet provides a list of senses and their definition in plain English. The senses, besides having a inner identifier, are represented as synsets, i.e., sets of synonym words. Words in general belong to multiple synsets, as they have more than one sense, so the relation between words and synsets in WordNet is a many-to-many one. The synsets are grouped into four categories based on part of speech: noun, verb, adjective or adverb.

WordNet is more than only an electronic dictionary though. As the "net" in the name suggests, WordNet not only contains words and their definitions, but also a whole set of relations defined among the word senses. In particular, the hyponymy relation between noun synsets induces a taxonomical structure of concepts.

Figure 1 shows a screenshot of the WordNet 3.1 search Web interface1 used to search for the word box. Clicking on the inherited hypernym link under the first sense of the word, the full hypernym chain is shown, all the way up to the root node entity.

WordNet as an Ontology

An ontology is "an explicit specification of a conceptualization" (Gruber, 1993), a collection of facts about some domain of defined entities 2 . Ontologies vary on different dimensions, including their size, complexity, domain, and specificity. Some ontologies have complex logical formulas among their rules, while others are more shallow collections of classes. Rules in an ontology are ifthen-like statements describing the logical infer-S: (n) box (a (usually rectangular) container; may have a lid) "he rummaged through a box of spare parts" direct hyponym / full hyponym part meronym direct hypernym / inherited hypernym / sister term S: (n) container (any object that can be used to hold things (especially a large metal boxlike object of standardized dimensions that can be loaded from one form of transport to another)) S: (n) instrumentality, instrumentation (an artifact (or system of artifacts) that is instrumental in accomplishing some end) S: (n) artifact, artefact (a man made object taken as a whole) S: (n) whole, unit (an assemblage of parts that is regarded as a single entity) "how big is that part compared to the whole?"; "the team is a unit" S: (n) object, physical object (a tangible and visible entity; an entity that can cast a shadow) "it was full of rackets, balls and other objects" S: (n) physical entity (an entity that has physical existence) S: (n) entity (that which is perceived or known or inferred to have its own distinct existence (living or nonliving)) derivationally related form S: (n) box, loge (private area in a theater or grandstand where a small group can watch the performance) "the royal box was empty" S: (n) box, boxful (the quantity contained in a box) "he gave her a box of chocolates" S: (n) corner, box (a predicament from which a skillful or graceful escape is impossible) "his lying got him into a tight corner" S: (n) box (a rectangular drawing) "the flowchart contained many boxes" S: (n) box, boxwood (evergreen shrubs or small trees) S: (n) box (any one of several designated areas on a ball field where the batter or catcher or coaches are positioned) "the umpire warned the batter to stay in the batter's box" S: (n) box, box seat (the driver's seat on a coach) "an armed guard sat in the box with the driver" S: (n) box (separate partitioned area in a public place for a few people) "the sentry stayed in his box to avoid the cold" S: (n) box (a blow with the hand (usually on the ear)) "I gave him a good box on the ear" ences that can be drawn from assertions.

WordNet was created with the initial goal of proving psycholinguistic models about the mental organization of concepts. Nevertheless, the electronic lexical database has grown more and more popular among NLP scholars dealing with the meaning of words and their relations, and also among ontology experts. As a matter of fact, many employ WordNet as an ontology by treating the hypernymy relation between synsets as subsumption between concepts, or in some cases as an instantiation relation between named entities (cities, countries, people, ...) and their hyponyms in WordNet. Gangemi et al. (2003b) went as far as defining a "complete formal specification of the conceptualizations expressed by means of Wordnet's synsets" in the OntoWordNet project.

We argue that WordNet constitutes a solid choice as knowledge base for generation. The main argument is that some unique features of WordNet facilitate the NLG process as designed in the Unboxer pipeline, in particular the fact that concepts are represented in WordNet as sets of words, ready to be picked up for the generation of surface forms. WordNet can be seen as a lightweight ontology about words, senses, and a series of relations among them, while still being more ontology-like than, say, a machine-readable dictionary or a thesaurus. This last point is debatable, as technically WordNet is a lexical resource, and additional work is necessary to transform it into a formal ontology specified in some logic formalism (Gangemi et al., 2003a). Nevertheless, for the purpose of designing an NLG system, the difference of definitions is not crucial.

Lexical Choice from WordNet Synsets

In recent work, we described a novel method for lexicalization that incorporates WordNet as linguistic knowledge base to provide natural sounding generations. The Ksel algorithm [START_REF] Basile | A lesk-inspired unsupervised algorithm for lexical choice from wordnet synsets[END_REF] exploits the network structure of WordNet in order to reduce the problem of the lexicalization of concepts to that of lexical choice from synsets.

The algorithm works by computing a similarity score between each candidate lemma and the set of synsets in the abstract meaning representation that is provided as input to the NLG system. This similarity score is actually an aggregate measure of the semantic similarities between the synsets containing the candidate lemmas and the synsets in the input structure. For example, consider an abstract meaning representation with three concepts encoded as WordNet synsets:

• c 1 = {stimulant, stimulant drug, excitant} "a drug that temporarily quickens some vital process"

• c 2 = {tonic, restorative} "a medicine that strengthens and invigorates"

• c 3 = {doctor, doc, physician, MD, Dr., medico} "a licensed medical practitioner"

• c 4 = {food, nutrient} "any substance that can be metabolized by an animal to give energy and build tissue"

The ksel algorithm will select nutrient over food as the realization of c 4 because the word nutrient is semantically closer to the synsets c 1 , c 2 and c 3 , based on measures of similarity computed on the WordNet structure (e.g., path distance).

Conclusion

In this paper we argued in favor of the use of WordNet as a lexical resource to support natural language generation. Despite it not being a fullfledged ontology, the structure of WordNet has interesting features that facilitate tasks such as lexical choice in the context of generation.

Figure 1 :

 1 Figure 1: The result of the search for box in the Wordnet 3.1 search Web interface.

http://wordnetweb.princeton.edu/perl/ webwn

A more extensive definition of ontology in the field of computer science is given in the Encyclopedia of Database Systems(Liu and Özsu, 2009).