Andrzej Kabat

Lida Sadeghioon

Annie Gravey

Hazar Sayed Darwish

A Multi-Class MAC for time-slotted WDM Optical Packet Ring

In this paper we present an approach for supporting best effort traffic on an ECOFRAME ring network which has been dimensioned primarily for Guaranteed Traffic. This approach is reservation based, and is combined within the ECOFRAME MAC with the opportunistic access method used for Guaranteed traffic. The reservation method is intended to both protect the Guaranteed traffic and allocate fair shares of the excess resources to the competing Best Effort traffic flows. We analyze the performance of the proposed approach on 2 simple scenarios, i.e. a "concentration" scenario where all stations send the same amount of traffic to a Hub on the ring, and an "any-to-any" scenario where each station sends the same amount of traffic to each other station on the ring. The maximum amount of BE traffic that can be supported without degrading the QoS offered to Guaranteed traffic is derived using simple queueing models. The simple scenarios are then simulated, with the modified MAC, and compared to the theoretical results. The obtained simulation results show that Guaranteed traffic is very well protected, and that spare resources are indeed fairly shared. However, the reservation approach fails to meet the maximum utilization in the any-to-any scenario due to the fact that it forbids spatial reuse for BE traffic.

I. INTRODUCTION

With emerging new applications, metropolitan area networks are used for aggregating and distributing of various client traffic types with different requests for services. WDM optical packet rings have been proposed to bring fine granularity along with reconfigurable flexibility for next generation Metro networks.

The present paper continues our work from [START_REF] Uscumlic | Impact of peer-to-peer traffic on the efficiency of optical packet rings[END_REF], [START_REF] Uscumlic | Traffic grooming in WDM optical packet rings[END_REF], [START_REF] Uscumlic | The impact of network design on packet scheduling in slotted WDM packet rings[END_REF] and [START_REF] Sadeghioon | A label based MAC for OPS multi-rings[END_REF]. The performance of a single-wavelength, unidirectional optical packet ring is studied in [START_REF] Uscumlic | Impact of peer-to-peer traffic on the efficiency of optical packet rings[END_REF]. The impact of WDM on the performance of optical packet rings is studied in [START_REF] Uscumlic | Traffic grooming in WDM optical packet rings[END_REF] while different design methods of the optical packet ring together with the impact of schedulers on the dimensioning process is studied in [START_REF] Uscumlic | The impact of network design on packet scheduling in slotted WDM packet rings[END_REF]. A MAC for ECOFRAME WDM multi-ring optical packet networks that supports only Guaranteed (G) traffic is presented in [START_REF] Sadeghioon | A label based MAC for OPS multi-rings[END_REF].

In our previous works, only G traffic is considered: the network is dimensioned to support all G traffic with no loss and controlled delay. The present work considers both G traffic as before, but also Best Effort (BE) traffic, and addresses methods for supporting BE traffic on top of G traffic, while still respecting committed QoS for G traffic.

We do not consider here the creation of optical packets from electronic packets, and we assume that each optical packet is Andrzej Kabat, Lida Sadeghioon, and Annie Gravey are with Institut Telecom, Telecom Bretagne, France, firstname.lastname@telecom-bretagne.eu Hazar Sayed Darwish is with Higher Institute for Sciences and Technology, Damascus, Syria, hazarsd@gmail.com classified as G or BE traffic. Algorithms for creating optical packets in ECOFRAME have been proposed in [START_REF] Eido | Packet Filling Optimization in Multiservice Slotted Optical Packet Switching MAN Networks[END_REF] and [6].

We assume here that once a packet is inserted on the ring, whether it is G or BE traffic, it is transparently carried to its destination. In particular, resources used by a BE packet in transit cannot be preempted by a G packet. This means that packet loss cannot occur on the ring. On the other hand, buffers used in each station for inserting and extracting packets can possibly get congested, leading to increased transit delays and possibly to packet loss if the buffers are too small.

After analyzing the possible causes of QoS degradations due to BE traffic, we propose a distributed reservation protocol that is used for supporting BE traffic. We show that the reservation protocol impacts on the fairness of BE support.

Fairness for BE traffic is a well studied topic, and in particular a well known, but quite complicated, distributed fairness algorithm is proposed by the Resilient Packet Ring protocol [7]. However, ECOFRAME differs from RPR in the sense that optical packets are not converted into electronic packets in transit stations; the RPR methods cannot then be applied to ECOFRAME. A simple distributed method of reservation of time slots in non-WDM optical packet rings, called SWING, is proposed in [START_REF] Bonald | Swing: Traffic capacity of a simple WDM ring network[END_REF], while a centralized approach of reservation of the free time slots is studied in [START_REF] Cadéré | Virtual circuit allocation with QoS guarantees in the ECOFRAME optical ring[END_REF]. Our approach differs from these works by first explicitly considering both G traffic (quantified by a known traffic matrix) and BE traffic, and second by considering a WDM ring where each station can send and receive on several wavelengths in order to benefit from statistical multiplexing. This paper is organized as follows : Section II explains the ECOFRAME principles; theoretical stability conditions for the ECOFRAME ring for G and BE traffic are described in Section III; Section IV details the Access protocol for BE traffic and in Section V performance results are presented; a last section conclude the paper .

II. ECOFRAME ARCHITECTURE

The ECOFRAME ring is a unidirectional WDM optical packet ring. All operations are synchronized and occur at discrete time instants [START_REF] Chiaroni | Demonstration of the Interconnection of Two Optical Packet Rings with a Hybrid Optoelectronic Packet Router[END_REF]. The interval between successive instants is fixed and is called "time slot". There are up to 40 data channel wavelengths and one out of band control channel carried by a separate wavelength. All data channels support the same rate, which is considered as rate unit in the present paper.

We assume here that each station is equipped with a tunable transmitter and as many fixed WDM receivers as there are data channels.

Each station can thus transmit traffic on all data channels, but at most one packet per slot, which effectively limits a station's ingress rate to 1.

A station can receive traffic on each data channels. Although each station can receive several packets per slot, there may be a limit on the egress rate from each station.

The status of the data channel slots are carried in the same slot of the control channel; control packets are used to operate the MAC and carry, either explicitly or implicitly, all relevant control information such as slot occupancy on each data channel, traffic type of the packet carried in a slot (if any), destination address and reservation status, plus any other necessary traffic control, fault management or performance monitoring information [START_REF] Sadeghioon | A label based MAC for OPS multi-rings[END_REF].

Traffic travels transparently in the optical domain between its source and its destination which means that there is no Optical/Electronic/Optical (OEO) conversion in transit stations. This characteristic both limits power consumption in stations and minimizes latency. This means that no packets are lost in the optical domain (neglecting physical layer impairments). On the other hand, insertion delay is impacted by this policy since the transit traffic always has priority over packets to be inserted, even if the packet in transit is BE whereas the packet to be inserted is G. According to this policy, and under the assumption that sufficient buffers are available in the electronic domain, the QoS delivered to packets by the ECOFRAME network is expressed in terms of delay (e.g. insertion delay, extraction delay, end-to-end latency, etc).

III. ECOFRAME STABILITY CONDITIONS

We assume here that planning the ECOFRAME network is done according to a traffic matrix obtained e.g. thanks to the set of negotiated Service level agreements (SLA). We thus assume that the network operator knows (an upper bound for) the amount of G traffic to be supported on the ring. This upper bound is usually a busy hour estimate, which implies that the network is usually over-provisioned for G traffic by the network providers in order to operate within safe margins both for delivering the contracted SLAs and for future expansions.

Let the G traffic matrix be A = [a ij ], where a ij represents the traffic flow between stations i and j for a ring with N s stations and N w data channels. Different design methods for ECOFRAME ring with G traffic only are derived in [START_REF] Uscumlic | The impact of network design on packet scheduling in slotted WDM packet rings[END_REF].

For a given network characterized by N s , N w and A, deriving stability conditions for BE traffic consists in identifying the maximum amount of BE traffic that can be supported on the ring, while maintaining the QoS delivered to the G traffic within specific bounds.

The 3 conditions sets to be considered are the following :

1) The load carried by each link is limited by N s ;

2) The insertion delay for G traffic is controlled ; for example, an upper quantile could be specified for this insertion delay; 3) The extraction delay (i.e. the time it takes for a station to extract the optical packet on the link, and to send it on its egress link) is controlled; for example, an upper quantile could be specified for this extraction delay.

Simple queueing models have been derived in [START_REF] Uscumlic | Traffic grooming in WDM optical packet rings[END_REF] in order to assess both insertion delay and extraction delay in an ECOFRAME ring. Inserted traffic flows are modeled as Bernoulli processes, which may seem as overly simplifying since Bernoulli processes are memoryless, and thus not bursty. H owever, consider that ECOFRAME is assumed to support the aggregated traffic from a large number of individual application flows. Indeed, ECOFRAME is designed to operate metropolitan area networks. It is well known that such aggregated traffics are rather smooth [START_REF] Cao | Internet traffic tends toward Poisson and independent as the load increase[END_REF].

We also show in [START_REF] Uscumlic | Traffic grooming in WDM optical packet rings[END_REF] that extraction delays can easily be upper bounded, as long as the egress rate is limited to a given percentage of the capacity of the egress link. We shall therefore concentrate on the second set of stability condition, and show that this set forbids saturating the links in the ring.

In the present section, we derive stability conditions for simple traffic scenarios.

A. Concentration Scenario

In the "concentration scenario" we assume that there is a specific station (a Hub) which receives traffic from N s other stations. The capacity of the egress link from the Hub is equal to N w .

If there is no G traffic (A = 0), there is a single constraint which consists in avoiding saturation on the most saturated link (i.e. the link to the HUB):

b iHub ≤ N w N s . (1)
In the general case for symmetric G traffic, let a iHub be the amount of traffic sent by one station to the hub.

The stability conditions now read :

a iHub + b iHub ≤ N w N s , (2)
which avoids the congestion of the most saturated link.

a iHub ≤ β[1 -((N s -1)(a iHub + b iHub )/N w ) Nw ], (3)
which ensures that G traffic to be inserted in the last station before the hub is still delivered an acceptable QoS in terms of insertion delay. Expression (3) is obtained by modeling the insertion queue in station N s (the last station before the hub) with a Geo/Geo/1 queue where the ingress rate is a iHub and the service time is geometric with parameter

[1 -((N s -1)(a iHub + b iHub )/N w ) Nw ].
Indeed, the total rate of transit traffic in competition with the G traffic to be inserted in station

N s is [(N s -1)(a iHub + b iHub )].
This rate is balanced on N w data channels and the slots on all data channels are considered to be independent. Therefore, the probability that a G packet can be inserted in a given time slot is

[1 -((N s -1)(a iHub + b iHub )/N w ) Nw ].
β is a parameter (e.g. 0.9) chosen to limit an upper quantile of the waiting time in the above Geo/Geo/1 queue.

For the concentration case, the maximum amount of acceptable BE traffic is thus given by :

b iHub ≤ N w N s -a iHub (4) b iHub ≤ N w (1 -a iHub /β) 1/Nw )/(N s -1) -a iHub .( 5
)
Depending on the value for a iHub , either condition (4) or condition ( 5) is the most constraining, which indeed means that protecting G traffic may forbid using all spare resources on the ring.

B. Any-to-any Scenario

In the "any-to-any" scenario, each station sends the same amount of traffic to each other station. The egress link from each station is of capacity 1. Let a a2a be the amount of G traffic sent by one station to any other station; the amount of G traffic entering (and exiting) each station is thus (N s -1)a a2a .

Since the system is completely symmetric, the (single) link saturation condition reads:

(N s -1)(a a2a + b a2a ) ≤ 2N w /N s . (6)
Each ingress queue is modeled by a Geo/Geo/1 queue with parameters a a2a and [1 -

((N s -2)(N s -1)(a a2a + b a2a )/2N W ) Nw ].
The upper quantile of the insertion time is then limited by the following constraint:

(N s -1)a a2a ≤ β[1-((N s -2)(N s -1)(a a2a +b a2a )/2N W ) Nw ].
(7) As in the concentration case, it is straightforward to derive from these two conditions an upper bound for b a2a . In this scenario also, depending on the value for a a2a , it may be possible, or not, to fully use spare resources.

IV. BE TRAFFIC ACCESS METHOD

MAC operation for G traffic is explained in [START_REF] Sadeghioon | A label based MAC for OPS multi-rings[END_REF]. In ECOFRAME, G traffic is transmitted in an opportunistic manner, i.e. G packets can be sent at any free time slot by any station in the network as the network is dimensioned for a known amount of G traffic.

However the amount of BE traffic offered by the stations is potentially unknown, which precludes the use of the same opportunistic access mode. We thus propose an approach to insert BE traffic while ensuring the following properties:

• The QoS of the G traffic should still be within the design limits;

• No station should be able to starve the others (i.e. some fairness should be enforced). The main MAC operation specifications in ECOFRAME network to support BE traffic are listed below:

• A transit packet has always the priority over the packet to be inserted at any priority level;

• In a given station, G packets always has the priority to be transmitted over BE packets;

• BE packet can only be transmitted using the reservation made for the BE flow characterized by the same source and destination.

• A reservation on a time slot can be erased by a any other station for the benefit of putting a new reservation if the previous reservation has a lower "relative priority" than the new reservation (the notion of "relative priority", which is central to our reservation based scheme, is explained later in this section). Sending a reservation and inserting BE packets are both based on computing the relative priority for each BE flow at every station. The relative priority is only calculated for BE flows, and does not apply to G traffic.

Consider BE flows as f k , let b k be the load per flow and d k be the exact fair share of the rest of the flow. Defining α as a positive variable, each flow is defined as followed:

x k = (α + b k )/(α + d k ). ( 8
)
x k is always larger than b k then it is possible to classify the BE flows according to their respective eligibility and select the flow that has the higher relative priority. The fair rate for b k can be calculated according to the G traffic matrix used to dimension the network. Additionally it is possible to implement dynamic policy calculation of G traffic matrix based on the actual G traffic inserted by each station. Where a D ij is the G flow sent by station i and received by j, and respectively a M ij is the observed flow rate during measurements then a E ij is the calculated fair shared flow.

a E ij = min(a D ij , A M ij ) (9)
The above equation actually allows us to measure how much G traffic the ring can support according to negotiated SLAs. Moreover the network can be updated to recalculate the fair share resources available to offer to BE traffic. Knowing how to calculate the fair share , traffic exchange process within each station follow these steps:

1) Receive any G packets on one or more channels and release corresponding slots; 2) Insert a G packet if possible; 3) Insert a BE packet if possible; 4) Check all reservations carried in the time slot and insert a single new reservation if it is both necessary, and possible.

Step 1 is straightforward. In step 2, a G packet is transmitted even if the slot is reserved as was previously discussed. While the G packet is inserted, the station can optimize the data channel to insert its packet.

Step 3 only occurs if there is no G packet to transmit (a station can only send 1 packet per slot time). Also, a BE packet can be inserted only on a slot that carries a reservation for its own flow (same source and same destination). If there is a reservation but there is no BE packet to insert, the reservation is just erased by the station.

Step 4 is central in protecting G traffic, and enforcing fairness. It first protects the QoS offered to the G traffic to insert in this station by estimating the future amount of transit traffic, by continuously monitoring reservations. If the amount of future transit traffic is considered excessive, a reservation is dropped. Secondly, G traffic to be received at the station is also protected by estimating the future amount of traffic to receive in the station. If this amount is considered to be excessive, a reservation is dropped. If the station has BE traffic to insert, and one slot is unreserved after these operations, the station can insert a single reservation corresponding to its flow which has the highest relative priority. Otherwise, if no slot is unreserved, the relative priorities of all reservations are compared and the station can overwrite an existing reservation if it has a flow with a higher relative priority.

V. PERFORMANCE RESULTS

To evaluate the performance of the proposed reservation mechanisms, we have implemented them in our NS2 based ECOFRAME simulator, which has been augmented to support a reservation based insertion process for BE traffic while using a purely opportunistic insertion process for G traffic.

In the experiments reported below, we consider both the concentration scenario and the any-to-any scenario. The ring is constructed with six stations and three data channels. The G traffic arrival process is Bernoulli. We assume greedy BE sources, which means that each station always has a BE packet to transmit.

The QoS metric for G traffic is the sojourn time in the ingress which includes both the waiting time till a G packet arrives at the head of the queue, and its the insertion time on the ring. The QoS metric for BE traffic is the insertion time (since there is no actual queue for greedy traffic).

We first assess the performance of the reservation based scheme for the concentration scenario. Using relations (2) and (3) for b iHub = 0 and β = 0.9, we observe that the system with only G traffic is unstable for a iHub > 0.55. Therefore, relevant areas in Fig. 1 and Fig. 2 are on the left hand side, for a load offered per station (a iHub ) smaller than 0.55.

Fig. 1 shows how the egress traffic from the hub varies versus offered G traffic per station comparing the system without and with BE traffic. It clearly shows that the reservation scheme succeeds indeed in using most of the spare resources to support BE traffic.

It is also necessary to check on the one hand that supporting BE traffic does not degrade the QoS offered to G traffic, and on the other hand that the reservation scheme fairly shares the spare resources between stations. This is assessed in Fig. 2 which represents the throughput per station, for both G and BE traffic in the cases without and with BE traffic.

We first see on Fig. 2, that for the flow of traffic from station 5 to the Hub (station 3), G traffic is insensitive to BE traffic. We do not report what happens for the G traffic sent by the other stations, but the result is similar. These experiments clearly show that G traffic is protected by the reservation scheme. Let us now address the fairness issue for BE traffic. Fig. 2 shows the achieved BE throughputs for stations 5 and station 1. Since station 5 inserts its traffic before station 1 in the concentration scenario, it is to be expected that station 5 receives more opportunities for inserting its BE traffic unless the reservation scheme does enforce fairness. We can indeed see that station 5 is slightly favoured compared to station 1 in terms of BE traffic throughput, but fairness, although not perfectly enforced, is quite correct. Indeed, with greedy sources, the upstream stations could indeed starve the downstream stations unless the reservation scheme counterbalanced the topology advantage. Fig. 2 also shows how supported BE traffic decreases as G traffic increases. Let us now assess the performance of the reservation scheme for the "any-to-any" scenario. Using relations (6) and ( 7) for b a2a = 0 and β = 0.9, we observe that the system with only G traffic is unstable for (N s -1)a a2a > 0.77. Therefore, relevant areas in Fig. 3 and Fig. 4 are on the left hand side, for a load offered per station ((N s -1)a a2a ) smaller than 0.77. Fig. 3 shows the achieved throughput in any station for both G and BE traffic, without and with BE traffic. As in the "concentration" case, we see that the G traffic throughput is not affected by the support of BE traffic thanks to the reservation scheme. We can also check that spare resources are only partially used since in the area of interest (for the load offered per station smaller than 0.77), the total throughput varies between 0.51 and 0.85. This is not as efficient as in the previous case. Actually, the inefficiency especially at low G load is due to the fact that the reservation scheme precludes spatial reuse for BE traffic. This is why, at minimal G load, the reservation scheme only allows to use half of the ring capacity. This behavior does not affect the "concentration" case which cannot take advantage of spatial reuse.

We assess the performance offered to both G and BE traffic in Fig. 4 which shows the sojourn time for G traffic and the insertion time for BE traffic. As predicted by our analytical model, we observe that the system becomes unstable when (N s -1)a a2a is close to 0.8. We also see that the sojourn time for G traffic is indeed impacted by BE traffic by comparing the mean waiting times for the cases without and with BE traffic. However, we see that the sojourn time degradation is very limited. We can also see that the insertion time for BE traffic is significantly larger than the sojourn time for G traffic. This was to be expected since the opportunistic insertion process is obviously more efficient and less constraining than the reservation based scheme used by BE traffic.

The results for any to any scenario under conditions described in Section III are shown in Fig. 3 and4.In this scenario all station behave similar and completely symmetrical, thus the flow to one station is presented in the cases of and G+ BE flows. As it is depicted in Fig. 3 the links are never completely saturated and only in the sum flow of G+ BE the link utilization saturation rate is faster. The waiting times experienced by customers in the any to any scenario before and after inserting Be traffic are shown in Fig. 4. Noticing the very little variation in the average waiting time for the two G and G+BE curves confirms that the proposed reservation method method maintains the QoS for G flows while BE traffic insertion .

VI. CONCLUSION AND DISCUSSION

We have presented here preliminary results regarding a multiservice MAC for a WDM optical packet ring. A previous work [START_REF] Sadeghioon | A label based MAC for OPS multi-rings[END_REF] proposed using a very simple opportunistic access mode for Guaranteed (G) traffic, and the present work advocates using a reservation based scheme in order to also support Best Effort (BE) traffic.

Actually, this proposal may appear paradoxical : it is quite common, in a multi-service framework, to explicitly reserve resources for G traffic while using opportunistic modes to send BE traffic.

However, the present proposal makes a lot of sense. Indeed, opportunistic access methods are to be preferred, whenever applicable, since they minimize latency in general; such a method can indeed be applied to G traffic, as long as the network is properly dimensioned for the amount of G traffic to be supported.

As ECOFRAME is intended to operate as an optical MAN, it is quite realistic to assume that the network operator has indeed dimensioned its network according to a realistic traffic matrix, and only attempts to transmit G traffic that conforms to the traffic matrix.

On the other hand, the network operator could wish to take advantage of spare resources in order to operate beyond the planned traffic matrix, while still protecting the G traffic. This is why we have attempted to add BE support to our original MAC.

We have also chosen to avoid packet discard in the optical domain, i.e. to ensure that each packet that was successfully inserted in the optical support would always be delivered, except possibly in case of physical layer failures. This is a strong design option, which can be defended with several arguments:

• A MAN is first and foremost a transport network; transport network are classically designed as "no loss" networks, i.e. highly dependable networks;

• An optical packet carries typically 100 Kbits, that is the aggregate traffic of at least a dozen or more sources; loosing a single optical packet may indeed affect a many applicative flows;

• It it usually more efficient to avoid congestion by delaying packets than to apply drop based end-to-end congestion control (i.e. delaying packets increases the round trip time for TCP controlled flows and thus naturally limits its instantaneous rate, while avoiding retransmissions). This design option however precludes the use of opportunistic access for BE traffic, since G traffic delivered QoS could be negatively affected by BE packets in transit. Some kind of controlled access has to be implemented for BE traffic. Packet by packet reservation is one such method, that has already been proposed for example in [START_REF] Bonald | Swing: Traffic capacity of a simple WDM ring network[END_REF] which however only supports BE traffic and does not enforce egress rate limitations. This is why we had to design a new reservation scheme for extending our MAC to multi service support.

Other approaches such as [START_REF] Cadéré | Virtual circuit allocation with QoS guarantees in the ECOFRAME optical ring[END_REF] rely on a centralized computation of "fair shares". This approach allows spatial reuse, but is more sensitive to failures than our purely distributed reservation scheme.

Future studies shall compare the present approach both to drop-based congestion control approaches and to centralized fairness and congestion control approaches.

The preliminary results regarding the proposed reservation based access scheme for BE traffic have shown that this scheme can efficiently use spare resources in scenarios where spatial reuse is not required (typically a concentration scenario), but is less efficient whenever spatial reuse improves the performance. This is a potential drawback, although most operational scenarios are currently based on concentration/distribution architectures for Metro networks.

The performance in terms of Fairness of the distributed reservation based scheme has been shown to be correct, even in the concentration scenario where the topological location of a station has a potentially large impact on access performance. We currently try to improve this fairness principle, while also studying other asymmetrical scenarios.

Fig. 1 .

 1 Fig. 1. Concentration scenario. Hub Throughput versus offered G traffic per station. Ns = 5, Nw = 3.

Fig. 2 .

 2 Fig. 2. Concentration scenario. Achieved ingress throughput versus offered G traffic per station. Ns = 5, Nw = 3.

Fig. 3 .

 3 Fig. 3. Any-to-any scenario. Achieved ingress throughput versus offered G traffic per station. Ns = 6, Nw = 3.

Fig. 4 .

 4 Fig. 4. Any-to-any scenario. Mean insertion times versus offered G traffic per station. Ns = 6, Nw = 3.

ACKNOWLEDGMENT

The work described in this paper was carried out with the support of the French "Agence Nationale de la Recherche" in the framework of the ECOFRAME project (grant number 2006 TCOM-002-06).


Pedro Quaresma

Yannis Haralambous
email: yannis.haralambous@telecom-bretagne.eu

Geometry Construction Recognition by the Use of Semantic Graphs

Given the large number of dynamic geometry systems (DGS), geometry automated theorem provers (GATP) and repositories of geometric information (constructions and/or conjectures), we face the need of a query mechanism for formal descriptions of geometric constructions. The DGS and GATP describe the geometric constructions using formal languages where the elements and the relations between them are described formally and not in terms of a given geometric model. Given a formal language we need to be able to look for similar construction, sub-constructions or even different construction sharing a common property, e.g., a set of constructions about right angled triangles. Our approach is to transform the geometric construction into a semantic graph representation of the construction, in a given ontology. Graph pattern recognition algorithms can then be used to search for the similarities we need and the results brought back to the geometric setting.

Introduction

Dynamic geometry systems (DGS) [START_REF]Wikipedia. List of interactive geometry software[END_REF] distinguish themselves from drawing programs in two major ways, the first is their knowledge of geometry. Indeed, from a initial set of objects drawn freely in the Cartesian plane (or maybe, on another model of geometry), one can specify/construct a given geometric figure using relations between the objects, e.g., the intersection of two non-parallel lines, a line perpendicular to a given line and containing a given point, etc. That is, one uses a DGS by constructing a geometric figure with geometric objects and geometric relations between them, not placing points on specific cartesian coordinates. Another major feature of a DGS is its capability to introduce dynamics to a given geometric construction. Given the fact that one specifies/constructs a geometric figure using a set of basic elements, e.g. points, lines, circles and relations between then, the DGS allow its user to move one of the basic (free) elements form its initial placement to another placement in the Cartesian plane, the relations will be kept, so a movement in a single point can entail the movement of almost all the other elements in the construction, i.e., when moving a basic object, we will move that object and all the other elements that are related to it, always preserving the geometric properties of the construction.

Most (if not all) DGS possess a formal language for the specification of geometric constructions. In some systems this formal language is explicit, in others it is hidden from the user by the graphical interface. The intergeo project designed a common format, called I2G, for this formal language which is already accepted by many DGSs [START_REF]Intergeo implementation table[END_REF][START_REF] Santiago | I2G Common File Format Final Version[END_REF].

Geometry automated theorem provers (GATP), being formal systems, need a formal language to describe geometric conjectures. GATPs are nowadays mature tools capable of proving hundreds of geometric conjectures [START_REF] Janičić | System description: GCLCprover + GeoThms[END_REF]. There are two major lines of research: the synthetic proof style and the algebraic proof style. The algebraic proof style begins by reducing the geometric properties to algebraic properties expressed in terms of Cartesian coordinates, proving the theorem by pure algebraic methods, so they do not belong to the realm of the geometric reasoning. The synthetic proof style GATP uses geometric reasoning, and its formal language is an extension of the formal language used by the DGS. The I2GATP project goal is to define a common language, an extension of the I2G language, to the DGS/GATP tools [START_REF] Quaresma | An XML-format for conjectures in geometry, (work-in-progress)[END_REF].

The design of common languages, and the emergence of Web repositories of geometric knowledge is an attempt to make widely available the already vast data set of geometric knowledge. The intergeo project [START_REF] Kortenkamp | Using the Intergeo platform for teaching and research[END_REF],

the GeoThms [START_REF] Quaresma | GeoThms -a Web System for euclidean constructive geometry[END_REF] and the TGTP [START_REF] Quaresma | Thousands of Geometric problems for geometric Theorem Provers (TGTP)[END_REF] systems already meet some of these goals having provided a large data set of geometric information widely available. In these systems the question of querying the geometric construction is not solved, that is, it is not possible to query the data set for a construction similar to some other construction, or to query for all constructions having some common geometric properties.

The goal of our research is to develop a search mechanism for geometric constructions (done by a DGS or a GATP) using the formal specification of the construction. Our approach is to transform the geometric construction into a semantic graph representation of its elements and relations, in a given ontology. The resulting semantic graphs can then be used, using graph pattern recognition algorithms, to detect matching constructions, and the results can be presented to the user once converted back to their geometric representation.

State of the Art

The term "Geometric Pattern Matching" refers to the recognition of shapes in a given set of points and it is a important area of research with applications in computer image processing, manufacturing, robotics, VLSI design, military intelligence, etc. with many articles written under many different approaches, but that it is not the goal we pursue. By geometry construction recognition we mean the search for pattern not on a given model of geometry but in the formal specification of the construction, or, equivalently, in its semantic graph representation, for a given ontology. As far as we known this is an area still to be explore, we are making the first steps in that direction.

Geometric Constructions and their Semantic Graph Representations

The DGS and most of the GATP are based in a constructive geometry [START_REF] Von | The axioms of constructive geometry[END_REF]. A construction is specified stating an initial set of points, the free points, implicitly universally quantified over a field of characteristic different from two, and from these initial elements, using a set of constructive rules the geometric construction is built [START_REF] Janičić | Geometry constructions language[END_REF][START_REF] Janičić | The Area Method: a recapitulation[END_REF]. For rendering the DGS will attach to the free points some Cartesian coordinates, but these coordinates will be ignored by the GATP. Let us consider a (very) small example (see Fig. 1).

A C′ P B′ A′ B C Figure 1: Geometric construction.
Points A, B and C are the free objects of this construction, starting with them we define new elements A ′ , B ′ and C ′ as being the middles of the opposite line segments, and P as the intersection of AA ′ , BB ′ , CC ′ and hence the barycenter of the triangle. The GeoThms and the TGTP systems share a database with more them 180 constructions like this one, specified in a constructive geometry language, the geometric queries are a much needed feature for those systems.

To represent this construction we need to chose an ontology. Most ontologies will contain the concept of "point," but, depending on the theorem to prove, one may add concepts for "line," "line segment," "angle," "length," etc. Typical relations are "belongs to," "is parallel to," etc. In our case, since points A ′ , B ′ and C ′ are defined as being middles of line segments, we need the relation "is middle of," which is a superrelation of "belongs to," in the partial hierarchical order of the ontology.

In Fig. 2 one can see the semantic graph of construction 1 in the ontology using points (represented by ) and line segments (repr. by △) as concepts, and relations "belongs to" (→) and "is middle of" (dashed →). Fig. 2 represents construction 1 entirely, in the given ontology. We could also represent the same construction in an ontology with relation "has same length" instead of "is middle of;" in that case we would use "has same length" arrows between nodes AC ′ and BC ′ in both directions, instead of the "is middle of" arrow between C ′ and AB.

Changing ontologies will cause a transformation of semantic graphs, and this is an operation that can be done mechanically.

Querying Geometric Constructions

Every user query can be transformed in a pair consisting of a (minimal) ontology and a (small) semantic graph. For example, the query find a construction containing a triangle would result into the ontology {"point" ( ), "line segment" (△), "belongs to" (→)} and the semantic graph

G = ¨r r r
By representing all constructions in this ontology (which, in the case of Fig. 2, would require to replace the relation "is middle of" by the weaker relation "belongs to"), we only need to seek for the presence of G as a semantic subgraph of the representation of each construction.

Here is another example: to find all constructions containing an intersection of three line segments (or three lines, in a slightly different ontology), one would need to seek the presence of the following subgraph:

G ′ = r r r 4

Conclusions and Future Work

Having already defined a semantic graph representation counterpart for the GC geometric constructions and a way of extracting information from it we need to define a query language that can be used in the Intergeo, GeoThms and TGTP (and others) systems, i.e., we need a user interface enabling users to make queries about geometric constructions and/or properties. The support for the geometric languages (I2G and I2GATP) and the trimming of the search mechanism to be used on the large set of geometric construction is also important. After a query has been submitted to the engine, it will need to find the (minimal) ontology needed, and, if necessary, convert constructions into it. Then it will detect semantic subgraphs and either display them to the user, or display the corresponding parts of the geometric constructions, or simply reply with a boolean value for constructions matching the query.

An interesting research direction to pursue in the future, is also to investigate how inference used in proofs by GATPs, interacts with the semantic representation.

Figure 2 :

 2 Figure 2: Semantic graph of construction 1. (Labels have been placed only to allow the reader to establish a connection with the original geometric figure -they are not part of the semantic graph per se.)