Lionel Molinier
email: lionel.molinier@ginkgo-networks.com

Mathieu Ligocki
email: mathieu.ligocki@ginkgo-neworks.com

Emna Ghedira Molinier

Guy Pujolle
email: guy.pujolle@lip6.fr

Emna Ghedira
email: emna.ghedira@ginkgo-networks.com

Dominique Gaïti
email: dominique.gaiti@utt.fr

Piloting the spanning tree protocol in home networks using a multi-agent system

Keywords: Home Network, WiFi, HomePlug AV, Agent, QoS, Knowledge Plane, Ontology, Throughput estimation

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

The spread of broadband accesses and of digital TVs at home is boosting the emergence of so called Home Networks. Currently, Home Networks are only composed of a broadband gateway, a set-top box and the domestic PC. We expect in a close future IPTV, VoIP WiFi phones, PDA, mobile phones, sensors and even domestic appliances (refrigerator, security devices) to be connected as well.

Contrary to classical networks, the Home Network is not monitored nor configured by an administrator. The end-user is supposed to be a neophyte, without any network skills. This implies strong constraints and the network needs to implement self-* functionalities, mainly:

self-configuration: a new device should be easy to connect; -self-healing: link disruption or device failures must be transparent for the end-user, if possible; -self-optimizing: the network must reconfigure itself to tackle potential resource shortage.

Those functionalities lead us to autonomic networks techniques, and mainly distributed ones.

In this paper we present a Home Network architecture, widely accepted, in section 1 with a basic routing solutions. However, to improve and implement self-* he have used Distributed Artificial Intelligence as explained in 2. In 3 we are presenting in details our solution and you are testing it in 4 to complete the work presented in [START_REF] Molinier | Piloting the spanning tree protocol in home networks using a multi-agent system[END_REF][START_REF] Nguengang | Intelligent routing scheme in home networks[END_REF]. The multi-agent system involved in those solutions is mostly the same which permits us, in 5, to compare them and also classical ones. Finally, we are concluding this paper by pointing out some work that remain to be achieved in section 6.

Home Network definition

Major initiatives are working on the Home Network for several years now, in order to identify this emerging network, the use-case, the technologies to be involved and so on. The Home Network cannot be treated separately from its broadband access to the Internet.

Home Network overview

The Broadband Forum is one of the oldest workgroup that mainly focuses on the broadband access. However, since the last years, the Home Network evolution has been taken into account in terms of management. Therefore, the TR-069 [START_REF] Lupton | Cpe wan management protocol -amendment 2[END_REF] jointly with the TR-098 [START_REF] Lupton | Internet gateway device data model for tr-069 -amendment 2[END_REF] describe and complete and powerful management architecture that tackles both the Home Gateway and others in-home devices. For instance the TR-104 [START_REF] Bernstein | Dslhome provisioning parameters for voip cpe[END_REF] describe a data model for a VoIP end device. However, the Home Network architecture remains out of the scope of the Broadband Forum.

However, this last point is covered by the Home Gateway Initiative (HGI) which is working on defining a wide set of use cases, and on enumerating technical solutions that could be used in a future Home Network. The purpose of this initiative is to mutualize development effort. The main idea is to enable a user to connect all its devices smoothly. For instance, an user must be able to watch a movie stored on the living room DVR directly on its bedroom TV.

Regarding the application, the DLNA [START_REF]Dlna overview and vision whitepaper[END_REF] (Digital Living Network Alliance) is focusing on the software part of the upcoming use. Devices, DLNA compliant, are able to communicate and exchange content, like in the previously mentioned use case. It is an extension of the UPnP architecture, where the service discovery and management is implemented. Moreover, it defines how audio or video stream should be transported on the network, for instance in terms of codecs.

Architecture

The Home Network architecture is a tricky point to succeed in providing a good user experience in the network. Indeed, even if the software is working well, the network has to carry flows with a good QoS, to be as simple as possible to set-up, and to run standalone, without any network administrator. Moreover this networks must be as cheap as possible since ISP will have to deploy billions.

Today's architecture and evolution

The nowadays architecture is represented figure 1. The Home Gateway is concentrating all services and adapts Obviously, this architecture can only be a transition to a full IP Home Networks. Indeed, in a near future, PSTN phones are to be replaced with IP phones, as for TVs and IP TVs which can be connected to the Home Gateway, using IP. Moreover, the number of devices is expected to rise significantly so that the star topology will no longer be sufficient. Each appliance is intended to be connected to the Home Network, which can be the fridge, the security system, lamps, locks, . . . The Home Network will have to evolve to distributed topologies (mesh or partial mesh), and will have to handle multiple technologies. We are expecting the simultaneous use of WiFi, HomePlug AV, ZigBee, Ethernet, Bluetooth, and any other upcoming technology.

At the same time, the huge bandwidth increase of the broadband access enable users to enjoy 100 Mb/s or even more till the gateway. However, the WiFi alone cannot support such bandwidth, with a wide coverage. Even with the upcoming 802.11n, a single AP cannot cover properly a complete home. A simple and usual way to increase the overall bandwidth of a WiFi network is to add relays and decrease the range of each cell 1 . The following architecture is taking into account this point.

Mesh-hybrid architecture

As discussed in [START_REF] Shihab | Wireless mesh networks for in-home iptv distribution. Network[END_REF], a full mesh architecture is not suitable if the hops number is larger than 2 or 3. We are proposing a 2 layer architecture, introducing new net-work devices, called bridges, which have several functionalities, mainly:

to realize a transparent bridge between technologies (HomePlug AV and WiFi for instance) -to extend a wireless network (WiFi for instance)

The first level is a full-mesh backbone of those bridging devices. They can connect to each other using Ethernet, PLC, MoCA, or any wireless technology. Connection diversity introduces several path to reach any other bridge. A smart routing scheme can be used to ensure a proper QoS. Those devices can be seen as wireless extenders.

The second level is for end devices, that can connect directly to any bridge. The connection can be either wireless, or wired. The figure 2 presents a typical instantiation of the architecture. This previous architecture minimizes the modification of end-devices as their are connecting in a standard slave/master architecture (station connected to a WiFi access point). The backbone provides enough diversity to balance load over network resources, and over technologies.

However, the routing between backbone nodes is quite challenging because most of technologies (WiFi and PLC, for instance) are perturbation sensitive, and we have to ensure a perfect QoS to carry HDTV flows, or VoIP flows.

Technologies involved

A Home Network must remain as cheap as possible, so technologies involved are using shared media. The two key technologies that have been identified so far are WiFi and HomePlug AV. Both are electromagnetic perturbation sensitive and are using the CSMA/CA. Those two points are tricky in terms of QoS.

WiFi

The WiFi is a very well known technology, and well documented in the literature. There were some physical layer models as in [START_REF] Dao | Throughput performance of saturated 802[END_REF][START_REF] Dao | A new markov model for nonsaturated 802[END_REF], some, like [START_REF] Xiong | Saturated throughput analysis of ieee 802.11e using two-dimensional markov chain model[END_REF] are even considering the 802.11e QoS-extension. These methods are widely used in simulated environments. However, to the best of our knowledge, there is no experimentally useful studies to estimate the saturated throughput online with passive methods. In this paper, we introduce a method based on realistic parameters, measured from a publicly available WiFi chipsets (see 4.2).

HomePlug AV

The problem is the same for the HomePlug AV as for the WiFi. The literature about saturated throughput estimation is however less important since the technology is more recent. Nonetheless, we have to mention [START_REF] Chung | Performance analysis of homeplug 1.0 mac with csma/ca. Selected Areas in Communications[END_REF] which develop a model to tackle the CSMA/CA problem with multiple stations on the same medium. However this is not directly useable in our real testbed, that's why we propose, in this paper (see 3.3.3), a method to estimate the saturated throughput. This can be achieved using physical layer statistics that be can retrieved using the open-source Faifa library [1].

Routing concerns

In the section 1.2.2 we have presented a mesh-hybrid architecture and, in 1.3, the shared and perturbation sensitive transmission technology are tricky for the routing scheme. The following is focusing on the routing problematic and the tradeoff between a layer 2 routing or a classical layer 3 one.

Routing problematic

Providing a routing protocol into such networks is not something difficult. There is a lot of routing protocols in the ad-hoc networks literature. The two main are AODV [START_REF] Perkins | Ad hoc ondemand distance vector (aodv) routing. RFC 3561 (Experimental)[END_REF] or OLSR [START_REF] Clausen | Optimized link state routing protocol (olsr). RFC 3626 (Experimental)[END_REF]. Both are providing connectivity but without any QoS concerns. Some QOS extensions has been proposed, and recently the Hybrid Wireless Mesh Protocol (HWMP) has been standardized in the 802.11s. It introduces the Air Metric in order to introduce QoS in the routing protocol. Unfortunately, this protocol is only for WiFi ad-hoc networks, and does not encompass our problematic.

Moreover, in the Home Network we have to ensure a good Quality of Experience for the end user, so the HWMP approach is not sufficient anyway. Indeed, the network should not only select the best path available, but must spread out the load over different link so that each flow can enjoy the appropriate QoS.

Layer 2 vs. layer 3

The choice between the layer 2 or the layer 3 is not straight forward. The following paragraphs are discussing this choice.

Layer 3 experimentation In previous works [START_REF] Nguengang | Intelligent routing scheme in home networks[END_REF] we have implemented the Home Network architecture using a layer 3 protocol. Our choice was AODV [START_REF] Perkins | Ad hoc ondemand distance vector (aodv) routing. RFC 3561 (Experimental)[END_REF] because of its link to ad-hoc networks. The reactive behavior of AODV fitted well in a wireless network with some mobile devices, and with fluctuating resources.

However, this first try has pointed out some lacks of the layer 3 approach:

-The address scheme is difficult to maintain in a full plug-and-play environment. Each network must be coherent, unique and must provide enough addresses for end-devices. Moreover, the DHCP does not work natively on routed networks. -Many usual LAN applications such as file sharing are using IP broadcasts, which cannot work with several subnets, which is a natural consequence of routed networks. -With the proposed architecture, each network should have at least 2 or 3 MAP. Telcos which are to bundle those bridges with their gateways will try to reduce as its minimum the production cost because of the huge number of units. Unfortunately, a layer 3 implementation in bridges implies a faster CPU to decapsulate frames into packets and to encapsulate them back2 .

Layer 2 choice Based on those considerations, we have then examined the layer 2 approach. The proposed architecture is offering diversity, that the layer 2 is not able to use properly. Indeed, diversity means loops in the 802.3 standard. The STP (Spanning Tree Protocol) is running between switches (further called bridges) so that looping links are disabled. This limitation will be discussed further in 3.1. Apart from this, the ethernet bridging functionality with the STP tackles layer 3 limitations. Indeed, the transfer plane of nodes are much simpler, so that the CPU speed can be reduced.

An other important point is the full independence between Ethernet and IP layers. Indeed, you can change the MAC layer, without impacting the IP one. This separation does not exists in upper layers3 .

Agent-based solution

As previously mentioned the complexity of the network architecture in 1.2 and of technologies used cannot be mastered with a classical protocol4 . Indeed, we have to interface different technologies (with built-in lacks) while guaranteeing QoS. Depending the applicative flow nature, those QoS requirements may differ.

Knowledge plane

Introduced by [START_REF] Clark | A knowledge plane for the internet[END_REF], the knowledge plane can handle this complexity with a reasonable computation overhead. This plane was defined as [. . . ] a distributed and decentralized construct within the network that gathers, aggregates, and manages information about network behavior and operation.

The knowledge plane enables the network to implement the self-* capabilities. Those requirements can be satisfied by a multi-agent system, which provides a decentralized approach to solve problems in complex environments [START_REF] Wooldridge | An Introduction to Multi-Agent Systems[END_REF]. The followings sections are introducing the agent (see 2.2). In 2.2.2, we are presenting the agent in a society. We are finishing with section 2.3 and 2.4 in which we are describing the platform developed by our company, Ginkgo Networks.

Agent overview

Definitions

According to J. Ferber in [START_REF] Ferber | Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence[END_REF], the agent definition is:

An agent can be a physical or virtual entity that can act, perceive its environment However, in our solution, we are using intelligent agents which can be defined as:

[an intelligent agent can] communicate with others, is autonomous and has skills to achieve its goals and tendencies. It is in a multi-agent system (MAS) that contains an environment, objects and agents (the agents being the only ones to act), relations between all the entities, a set of operations that can be performed by the entities and the changes of the universe in time and due to these actions.

The figure 3 is presenting a simplified structure of an intelligent agent in the J. Ferber view.

Environment Agent

Receptor Effector Intelligence Fig. 3 Simplified structure of intelligent agent Furthermore, M. Wooldridge in [START_REF] Wooldridge | Intelligent agents: Theory and practice[END_REF] defines them more precisely and emphasizes some characteristics.

Perhaps the most general way in which the term agent is used is to denote a hardware or (more usually) software-based computer system that enjoys the following properties: -autonomy: agents operate without the direct intervention of humans or others, and have some kind of control over their actions and internal state; -social ability: agents interact with other agents (and possibly humans) via some kind of agentcommunication language; -reactivity: agents perceive their environment, (which may be the physical world, a user via a graphical user interface, a collection of other agents, the internet, or perhaps all of these combined), and respond in a timely fashion to changes that occur in it; -pro-activeness: agents do not simply act in response to their environment, they are able to exhibit goal-directed behavior by taking the initiative.

Agents society

As mentioned in the previous definition, we can exhibit the collectivity notion through Multi-Agent Systems. First, we will present the multi-agent environment, the way the agent is perceived, and finally the communication and the interaction between agents. A multi-agent environment is open5 , decentralized and composed of a set of intelligent agents which are autonomous and distributed. It has to provide protocols for the inter-agent communication and interaction.

Within this environment, an agent is considered as an active object with probing and knowledge representation capabilities. Then, the reasoning ability process them to infer actions.

Interaction, no matter its nature, between agents within a MAS is goal-oriented (either local or global). The coordination is defined as a MAS property executing a specific activity in a common environment. In other words this eases sharing among agents.

Regarding the communication, it enables a better coordination of actions and behaviors to improve the system consistency. The inter-agent communication is based on three levels of understanding:

syntactic: communication symbol structuring semantic: symbol meanings pragmatic: symbol interpretation The inter-agent communication understanding is linked to the semantic (to be understand by other) and to the interpretation (to understand others). Therefore the language used for this communication is derived from the human natural language, with a common and structured vocabulary, called ontology.

After the individual and collective agent overview of the previous section, we will focus now on the Ginkgo MAS.

Ginkgo MAS

An intelligent agent, as defined in section 2.2.1, is embedded on each network device as shown on figure 4. As previously explained, the Ginkgo agent, as an environment entity, has a knowledge representation, a perception of its environment which are both stored in a situated view, which is defined in [START_REF] Bullot | A situatedness-based knowledge plane for autonomic networking[END_REF].

It is mandatory to have a common vocabulary, both for the inter-agent communication and for the knowledge representation. Therefore an ontology has been developed. The figure 5 is representing a subpart of the ontology using Unified Modeling Language (UML). The inter-agent communication in the Ginkgo MAS is done via the situated view exchange. In other words, there is no speeching act 6 , but only knowledge exchange. In a MAS, each agent has a partial view of its environment, the Ginkgo MAS has been designed so that an agent can only exchange his situated view with its directly connected neighbors (1-hop neighbors), as shown on figure 6. link disruption: agents must change the path as soon as a link failure is detected; -link quality degradation: agents must monitor the link quality, which means the available bandwidth 7 . If a noticeable degradation occurs, agents should change the path.

STP by-pass

To enable agents piloting the STP, mentioned in 1.4.2, several hooks have been implemented. Indeed, the STP is known to be quite slow to converge after a topology change. In Home Networks context, agents must preempt the normal operation to restore as quickly as possible the applicative flow. This requires a by-pass of the during its convergence phase.

In the STP operation, depending its state, a port can forward frames, or block all traffic (except STP PDUs). In our implementation, agents are able to force traffic to pass through blocked ports. This may introduce loops in the network, but internal agents operation prevents this.

In other words, we simply allow agents to modify the forwarding tables of the switch, preventing the STP to override those modifications till its full convergence.

7 This is an approximation to consider the QoS as a matter of bandwidth, but in most cases, the delay can be converted into extra bandwidth. This works if the delay is considered to be caused only by the serialization problem on the link.

Building alternatives routes

The figure 8 is describing the agent operation in this precise context of building alternatives routes. Each element of the figure is explained in the following.

Local forwarding database

For wireless technologies, the modulation is selected on the fly for each peer. The link performance is defined for the couple (Access Point, Station). To monitor performance, agents have to know to which peer the flow is sent. In other words, they need to know the next hop. This notion does not exists in classical ethernet networks, so agents have to build it back. This can be easily done by comparing the local neighbor list with direct neighbor ones.

Remote forwarding databases

The reactivity is critical for real-time flows. To minimize this time, agents are preparing solutions to any potential problem that may occur. This means, that each agent is looking for an alternate solution for each network access failure 8 .

Actually, each agent is populating the knowledge plane with its own forwarding database where network access identifiers are swapped by the neighbor list reachable with the access in order to identify link without any confusion. Given its neighbor forwarding databases, each agent can compute alternatives.

Link monitoring

Agents have to monitor the link status and performance in realtime, since they have to change as fast as possible the route. These constraints prevent us from using any active measurement methods. Everything must be done locally, in the hosting equipment. Moreover, the computation cost must be taken into account. In a first step of our work, we have elaborated methods as simple as possible 9 to have references for any further works. This section discusses quickly the link status of each interface, and then the maximum available bandwidth estimation on WiFi, and finally on HomePlug AV links.

Link status

Each agent embedded on a MAP must be conscious of network interfaces and must monitor them. Indeed, agent are polling regularly the hardware for information.

WiFi bandwidth estimation

The algorithm used to estimate the WiFi bandwidth is at this step of our work very simple. In digital communication on noisy channel, the physical layer has to optimize the tradeoff between transmission bit rate and noise resilience on the channel. Some algorithms exist to approach this optimality, such Atsushi Onoe [2] algorithm or SampleRate described in [START_REF] Bicket | Bit-rate selection in wireless networks[END_REF]. We are using this last one in our experiments 10 .

In a word, this algorithm tries each modulation regularly to compute performance metric. In average, it generally uses to best modulation. The tricky point is to test appropriate modulations while not noticeably degrading overall performances. Our estimation is based on those statistics, mainly the average frame transmission time tx time and the time elapse since the last frame send last tx. Those statistics are given for 3 frame sizes, defining the ensemble S = {250 B, 1.600 B, 3.000 B}. We are introducing a weight function w to average the frame size:

w : s → 1 s∈S 1 1+last tx(s) 1 1 + last tx(s)
Finally, the resulting formula is given bellow in the formula 1.

wif i bw max = s∈S w(s) s tx time(s) (1)
In practice, the algorithm is working with 2 steps: first, a geometric averaging of the formula 1 is computed to smooth high frequency variation. Secondly, given the first order derivate, the next value is extrapolated. This algorithm is very simple and must be consider a lower bound of the estimation efficiency. As discussed in 6.2, a more powerful algorithm is in development.

HomePlug AV bandwidth estimation

As for the WiFi, the HomePlug AV physical layer as to adapt to the channel conditions by adjusting the modulation. However, despite the WiFi, there are 1152 frequencies available for the communication (see [START_REF] Hazen | The technology behind homeplug av powerline communications[END_REF] for more information). The resulting modulation table is called the Tone Map, from which we can compute the channel capacity, called cap c .

The HomePlug AV chip is also maintaining statistics on successfully transmitted frames11 and unsuccessfully ones. We are calling p suc the proportion of successfully transmitted frames.

Since there is a high binary error rate on power lines, the HomePlug AV is using a powerful FEC 12 system based on Turbo Codes. This adds overhead in blocks, so that the payload bandwidth is reduced by a factor p F EC . As explained in [START_REF] Guerrieri | Performance of the turbo coded homeplug av system over power-line channels[END_REF], the factor value is p F EC = 1 2 .

Finally, the bandwidth can be computed by the formula 2:

hpav bw max = p suc .p F EC .cap c (2)
In practice, we are smoothing this value so that high frequency variation are filtered out. One more time, this is the simplest way to estimate the bandwidth, that is sufficient in simple environment. A better estimation is under development, as discussed in 6.2.

experimental set-up

To experiment previous concepts, we have decided to setup a real testbed instead of using a simulator because many potential problems can be caused by implementation shortcuts. We have simplified the architecture to only 3 PC running GNU/Linux, in order to isolate problems quickly. The figure 9 is illustrating the testbed. We focus on Ethernet (for the link disruption scenario) and on WiFi or HomePlug AV (for link quality degradation scenario).

Bridge implementation

The GNU/Linux kernel is implementing the ANSI/IEEE 802.1d [3] standard. We have patched the STP to allow our agent by-passing ports states as described in 3.1.

WiFi infrastructure

The classical infrastructure mode of WiFi cannot be used in conjunction with ethernet bridging. Indeed, the 802.11 standard is using the MAC address to identify wifi station (association, modulation selection, . . . ), so that they cannot forward foreign MAC addresses. The WDS introduces a 4 addresses header in 802.11 frames to enable frame forwarding.

We have used this system in conjunction with Atheros [4] based WiFi cards. The Madwifi [2] module for GNU/Linux is supporting the WDS, and has been patched for performance monitoring.

HomePlug AV infrastructure

For our HomePlug AV network, we have used Develo dLAN 200 ethernet adapters [5]. There are running with Intellon [6] chipset, like mostly any other adapters. Thanks the Faifa [1] library we were able to retrieve layer 1 statistics in our system. For instance, we have access to the current Tone Map used to reach a given destination.

As a first step in our experimentation we have not studied the effect of concurrent HomePlug AV stations. The PLC network in figure 9 is a real power line, with only our 2 adapters connected. This prevent us from consider the CSMA/CA effect on the QoS.

Results

Given the network architecture presented in 4, we have realized two sets of experimentations. The first one was performed to check agents ability on detecting and recovering from a link disruption. The second one to measure agents reactivity when faced to a WiFi perturbation, then faced to a HomePlug AV one.

Ethernet wire unplugging

Another part of our experimentation was about wire failures. Indeed, when an agent detects a link down it should find an alternative access. Based on the previous scenario, the flow is going from the Video streaming server to the Video client through the Bridge. The link between the Video server and the Bridge is then unplugged. In this experimentation, the tricky point is the ability to act on the network device remaining transparent for applicative flows. There is a huge difference between the layer 3 approach. Indeed, the IP stack does not allow modification of interface state without a long disruption. This point is blocking because it prevents agent from acting properly. Fortunately, the separation between the layer 2 and the layer 3 is good enough to allow agent to operate.

We have measured, with the layer 2 approach an average disruption of 540 ms (see table 1). This delay is mainly cause by slow software. Indeed, up to now, agents are developed in Java to ease the development and tests 13 . An optimized software design can reduce it to less than 50 ms. In the setup, a flow is going from the Video streaming server to the Video client by the WDS link. An agent is running on each node, so that they can fill their situated view to compute alternatives. As shown on figure 10, we then generate a perturbation on the WDS link frequency, so that MAC layer performances collapse. As a consequence, the agent situated on the Video server notices the problem and solves it.

Figure 11 is showing that agents are reacting to the perturbation in less than 3 seconds. Even if this is not satisfying for real time flows, this time can easily be reduced as discussed below. Anyway, this detection time is tricky to minimize applicative perturbations. No matter we are using the layer 2 approach or the layer 3, the reactivity time is mostly the same.

However in our testbed, the generated perturbation is the worst case that may occur in real field because resources are collapsing in few milliseconds as shown on figure 12. When the agent detects the perturbation, the applicative flow is already degraded. A real perturbation should be smoother, in most cases.

HomePlug AV perturbation

Figure 13 illustrate the perturbation scenario for the HomePlug AV. Results are mostly the same as for WiFi, since in both case, the overall performance relies on the perturbation detection. However, figure 14 is showing the performance of our bandwidth estimation in the test architecture. The section 6.2 will describe work that remains to be done to take into account the CSMA/CA effect. 13 Our agent framework can be executed indifferently on an own-made simulator or on GNU/Linux. This causes an important overhead in abstraction layer that considerably slows agents execution. In previous sections, we have presented the third step of our work. The first one was to simulate the knowledge plane on an own-made simulator to validate agents operations. As a second step we have setup a real testbed using a layer 3 routing protocol. Then in this third step, we have used the same testbed with a layer 2 approach. However a lot of work remains to be done.

Architecture extension

The architecture used for these experimentations is not yet complete, and one or two more PC will be added soon. This will enable more complex scenario, where agents will have to cooperate more intensively.

QoS measurements

The passive QoS measurements both for WiFi or Home-Plug AV is still under study to improve the confidence in the estimator in one hand, and in the other hand to handle the CSMA/CA effect. Some AI techniques like kNN or neuronal networks are tested. At the same time the agent framework is used to simulate the CSMA/CA behavior.

Another way of development is to introduce a prediction module with the bandwidth temporal serie so that the agent can change the path faster, and ideally before the perturbation became damaging for the user experience.

Knowledge plane

Another way of investigation will be to improve the knowledge plane. Indeed, we are using a very simple technique which relies on forwarding tables exchange. However, this requires a stable network in which forwarding tables can be considered as stable (at 10 seconds scale).

In highly variable environment, such method may lead to inconsistency which are unrecoverable by layer 2 mechanism. Methods using the ant-routing principle, presented in [START_REF] Caro | Antnet: A mobile agents approach to adaptive routing[END_REF][START_REF] Dhillon | Performance analysis of the antnet algorithm[END_REF], can be used successfully since the network diameter is small.

Handover management

For the WiFi, the WDS allows horizontal handovers but it has been eluded. Next work will be to integrate an algorithm to optimize the handover decision based on several criteria, such as the number of stations connected, the required bandwidth. . . The paper [START_REF] Abid | Practical handover optimization solution using autonomic agent-based piloting system[END_REF] presents the handover work on the same SMA platform that can be integrated with this work.

Service differentiation

In the presented architecture, we are working with only one flow (IPTV). In the real field Home Network, there will be more flows, such as Data, VoIP, Game, IPTV, . . . We are working on isolating flows on separated ethernet VLAN, so that the agent system can route services independently. Moreover, a DiffServ -like architecture is implemented in each forwarding device. This enables also the SMA to tune the QoS parameters, so that an agent can reduce bandwidth allocated for the data, in order to preserve the VoIP quality.

Conclusion

The results presented in section 5 are confirming that the layer 2 approach is more effective than the layer 3 (see 1.4.2). The independence between the Ethernet layer and the IP one enables agents (and any piloting system) to work without impacting the end user experience.

The work on this layer is harder, but agents crosslayer capabilities helps us to transpose upper layer notions without modifying the transfer plane of network nodes. This transfer plane remains cheap and efficient.

Home Networks are using perturbation sensitive technologies due to their low deployment costs. However, users are requiring high quality of service as this network is the backbone of tomorrow homes. Dealing with this antagonism is not as simple as elaborating a new protocol. It as been experimented in 5 that a multiagent system is able to master such complex environments.

The first real experimentations are quite satisfying as they can solve partially many problems. The real field is still far, but we think that progressing step by step, adding new components at each step may lead to a complete working system fitting all requirements.

Fig. 1

 1 Fig. 1 Nowadays Home Network architecture

Fig. 2

 2 Fig. 2 Home Network architecture

Fig. 4

 4 Fig. 5 Extract of the ontology developed

6Fig. 6

 6 Fig. 6 Agents situated view concept

Fig. 7

 7 Fig. 7 Agent operation

Fig. 8

 8 Fig. 8 Agent operation

Fig. 9

 9 Fig. 9 Testbed network

Fig. 10

 10 Fig. 10 WiFi perturbation scenario

  Fig. 12 WiFi perturbation profile

Fig. 11

 11 Fig. 11 Rate and loss factor during a perturbation.

Table 1

 1 Recovery time after a link failure

		Recovery time
	Layer 3 with Agents	5.4 s
	OSPF only	11 s
	Layer 2 with Agents	680 ms
	STP only	21 s
	RSTP only	≈ 1 s
	Values given in table 1 have been measured using a
	network packet generator [7] with a periodical packet
	generation. Both OSPF and STP implementation are
	running with default configuration values.

The overhead is situated in the transfer plane of the node, which impacts each packet. The agent presented in section 2 is working in background, in the knowledge plane (which is a user-space application), so that it is scheduled with a lower priority.

If you change the IP address, you have to restart all your applicative sockets.

The STP is clearly insufficient for this job, but even AODV or OLSR have also shortcomings. To the best of our knowledge, there is no efficient protocol to deal with that.

An agent can join or leave the community at anytime, without distributing activities

Actually, it computes a list of alternate solutions, so simultaneous failures could be handled as well.

The strongest approximation is the CSMA/CA effect on shared mediums.

There is no strict limitation in using SampleRate, since most of the rate selection algorithm are using the same principle.

In HomePlug AV, we prefer talking of blocks

FEC: Forward Error Correction

Acknowledgment

The authors would like to thank the Ginkgo Networks developer team that helps them in implementing this solution, and one of our closest CELTIC/AutHoNe partner, Orange Labs for their guidelines and expertise on such networks.


Mariano Tepper

Pablo Musé

Andrés Almansa

Marta Mejail

Automatically finding clusters in Normalized Cuts

Keywords: clustering, Normalized Cuts, a contrario detection

Normalized Cuts is a state-of-the-art spectral method for clustering. By applying spectral techniques, the data becomes easier to cluster and then k-means is classically used. Unfortunately the number of clusters must be manually set and it is very sensitive to initialization. Moreover, k-means tends to split large clusters, to merge small clusters, and to favor convex-shaped clusters. In this work we present a new clustering method which is parameterless, independent from the original data dimensionality and from the shape of the clusters. It only takes into account inter-point distances and it has no random steps. The combination of the proposed method with normalized cuts proved successful in our experiments.

Introduction

Clustering is an unsupervised learning method in which a set of observations is assigned into subsets (called clusters) so that observations within the same cluster are similar in some sense. Clustering is an interesting problem for many domains, such as image and signal analysis, bioinformatics or medical sciences.

It has been applied for image segmentation [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF][START_REF] Comaniciu | Mean shift: a robust approach toward feature space analysis[END_REF][START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF], object class and shape * corresponding author Email addresses: mtepper@dc.uba.ar (Mariano Tepper), pmuse@fing.edu.uy (Pablo Musé), andres.almansa@telecom-paristech.fr (Andrés Almansa), marta@dc.uba.ar (Marta Mejail) that do not rely on any assumptions about the chosen metric. It imposes graphs as the only suitable underlying structure for clustering.

2.

No random steps. Results must remain equal for all runs of the detection process. In particular, random initializations are forbidden.

3. Independence from the exploration strategy. The order in which points are analyzed must not affect the outcome of the algorithm.

The ultimate goal of our work is to propose a clustering method which follows Zahn's principles. In recent years, a theory for the quantitative analysis of gestalts, called Computational Gestalt [START_REF] Desolneux | Edge detection by helmholtz principle[END_REF], was developed and since then many refinements followed. By studying Zahn's principles in the light of the Computational Gestalt theory, we introduce a perceptually driven clustering method. It only takes into account inter-point distances and it has no random steps. As a consequence, it is independent from the original data dimensionality and from the shape of the clusters. Although the proposed approach is a general clustering method, in this work we combine it with normalized cuts. This work is structured as follows. In Section 2 we review spectral graph theory and in Section 3 we present a new parameterless clustering method. In Section 4 we show results and then provide final remarks in Section 5.

Spectral Graph Methods

Formally, we want to find clusters in a feature set X = {x i ∈ R H } i=1...N where H is the dimension of the feature space. In the following the terms point and feature have the same meaning and we will use one or the other depending on the context.

Here we briefly recall spectral graph concepts used for clustering. For further details, see the extended overview of the spectral graph theory by Chung [START_REF] Chung | Spectral Graph Theory[END_REF].

Let G = (V, E) be an undirected graph with a vertex set V = {v i } i=1...N , where N is the cardinal of V , and an edge set E ⊆ V × V . We consider graphs to be non-reflexive, i.e. ∀ v ∈ V, (v, v) / ∈ E. We also define an edge weighting function ω : E → R such that ∀ e ∈ E, ω(e) > 0.

j W ij . The Laplacian of G is defined to be the matrix

L = D -1/2 (D -W )D -1/2 = I -D -1/2 W D -1/2 . (1)
L is symmetric positive semidefinite [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF] and its eigenvalues lie in the interval [0, 2]. Von Luxburg [START_REF] Luxburg | Consistency of spectral clustering[END_REF] analyzed the advantages of this form of the Laplacian.

Ng et al. [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF] and Fowlkes et al. [START_REF] Fowlkes | Spectral grouping using the nyström method[END_REF] studied the utility of employing multiple eigenvectors of L to embed each feature into an M -dimensional space (M ≪ N ).

To build the embedding, we compute the N × N matrices A and Λ such that D -1/2 W D -1/2 A = AΛ and the values λ i = Λ ii are sorted in ascending order.

The columns of A are the eigenvectors of L and 1λ i are its eigenvalues. The M -dimensional embedding is the result of keeping the first M columns of A forming the matrix A M . The normalized form of A M is defined as

A M def = D -1/2 A M . (2)
The resulting spectral clustering procedure is as follows:

1. build G o from V = X using ω((v i , v j )) = d(x i , x j ) where d is an application specific kernel distance, 2. compute the embedding A M from G o , 3. apply a clustering algorithm to the rows of A M , as they form tight clusters.

Each feature is finally assigned to the cluster to which its corresponding row belongs. This procedure provides a relaxation of minimizing the Normalized Cut of the original graph [START_REF] Shi | Normalized cuts and image segmentation[END_REF], given by

NCut(C 1 , C 2 ) def = f(C 1 , C 2 ) f(C 1 , V ) + f(C 1 , C 2 ) f(C 2 , V ) (3)
where

C 1 , C 2 ∈ V , C 1 ∩ C 2 = ∅ and f(C, C ′ ) = u∈C,v∈C ′ ω((u, v)).
Ng et al. [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF] and Fowlkes et al. [START_REF] Fowlkes | Spectral grouping using the nyström method[END_REF] use k-means for the final clustering stage.

It is well known that k-means presents two drawbacks: (1) it is very sensitive to the initialization and (2) the number of clusters has to be manually specified.

The former is usually addressed by performing several random initializations and then choosing the optimal partition with respect to Ncut, see Figure 1. The latter is an open question as choosing k is a difficult model-selection problem.

Popular approaches to circumvent this issue are Akaike's Information Criterion (AIC), Bayesian Information Criterion (BIC) [START_REF] Burnham | Model selection and multimodel inference: a practical information-theoretic approach[END_REF] or Minimum Description Length (MDL) [START_REF] Barron | The minimum description length principle in coding and modeling[END_REF]. While these methods rely on firm theoretical background, results usually differ from a human made choice. Nadler and Galun [START_REF] Nadler | Fundamental limitations of spectral clustering[END_REF] showed that spectral methods may not reveal clusters of different sizes and scales. This assertion holds when clusters are intertwined or sufficiently near each other. However in practice, when clusters (even of different sizes and scales) are well separated, spectral methods perform well.

Ozertem et al. [START_REF] Ozertem | Mean shift spectral clustering[END_REF] propose to use the Mean Shift algorithm to build the adjacency matrix. Mean Shift [START_REF] Comaniciu | Mean shift: a robust approach toward feature space analysis[END_REF] detects clusters by computing what Comaniciu and Meer call attraction basins. Vertices that lie on different attraction basins are removed from the graph. The matrix is built by using the groups found with Mean Shift, instead of directly using a kernel distance, for determining locality.

A Contrario Clustering

In this section we present a method that overcomes the issues presented in the previous section. It is not dependent of random initializations and clusters are detected without manually specifying its number. The presented method is general, in the sense that it can be applied to any feature set X equipped with a suitable distance d.

We start by presenting a method in which ours is inspired. Then we introduce theoretical definitions in Section 3.1. The automatic choice of detection thresholds is discussed in Section 3.2. Sections 3.3 and 3.4 address the simplification and revision, respectively, of the obtained clusters.

In the scope of the Computational Gestalt programme [START_REF] Desolneux | From Gestalt Theory to Image Analysis[END_REF], Cao et al. proposed a cluster detection method [START_REF] Cao | A unified framework for detecting groups and application to shape recognition[END_REF]. The main idea is to measure the statistical significance of a set of points as being a cluster. Let us recall its basic definition.

For k ≤ N ∈ N and p ∈ [0, 1], let us denote by

B(N, k; p) def = N j≥k N j p j (1 -p) N -j (4)
the tail of the binomial law. See Desolneux et al.for a thorough study of the binomial tail and its use in the detection of geometric structures [START_REF] Desolneux | From Gestalt Theory to Image Analysis[END_REF].

Let R be a set of H-dimensional hyper-rectangles parallel to the coordinates axes and centered at the origin.

Definition 1. Let C ⊂ X be a subset of k points out of the N data points. We call number of false alarms (NFA) of C,

NFA(C) def = |R| • N • min xi∈C R∈R C⊂R+xi B(N -1, k -1, π i ) ( 5
)
where R + x i is the rectangle R translated to x i and

π i = Pr(x ∈ x i + R) is its probability. We say that C is an ε-meaningful group if NFA(C) < ε.
The term |R|•N is the number of tests and the remaining part of Equation 5represents a Probability of False Alarms (PFA). B(N -1, k -1, π i ) corresponds to the probability that at least k -1 out of the N -1 remaining points fall into

x i +R. The detection algorithm consists in exploring the group of points given by a dendrogram, identifying ε-meaningful groups as clusters and then performing an additional pruning, based on the inclusion properties of the dendrogram. A similar technique will be described in Section 3.3.

Notice that the above detection rule does not conform to Zahn's first argument. Indeed, inter-points distances are not directly taken into account and hyper-rectangles are used instead.

Another drawback of this approach is that a set R of hyper-rectangles parallel to the axes must be properly chosen. This choice is application specific since R is intrinsically related to cluster size/scale. For example, an exponential choice for the discretization of the rectangle space is made by Cao et al. [START_REF] Cao | A unified framework for detecting groups and application to shape recognition[END_REF] introducing a bias for small rectangles (since they are more densely sampled).

Each cluster must be fitted by an axis-aligned hyper-rectangle R ∈ R, meaning that clusters with arbitrary shapes are not detected. Even hyper-rectangular but diagonal clusters may be missed or oversegmented.

The probability law π i for each hyper-rectangle R ∈ R, assuming no specific structure in the data, must be known a priori or estimated. The complexity of computation of the probability of an hyper-rectangle then depends on the dimension H and suffers from the "curse of dimensionality".

Graph-based A Contrario Clustering

We now propose a new method to find clusters in graphs that is independent from their shape and from the dimension H. We first build a weighted undirected graph G = (V, E) where v i ∈ V is identified with a feature x i ∈ X in a metric space (X, d) and the weighting function ω is defined in terms of the corresponding distance function, namely ω((v i , v j )) = d(x i , x j ).

Although the method may be applied to any metric space, in this work we will use the rows of A M as the input features X = {x i } i=1...N , by identifying x i with the i-th row of A M and by defining d as the usual Euclidean distance in R M . Notice that this distance comes from the embedding described in Section 2 and may represent a more complex semidistance in the original feature space.

A subgraph G ′ of G is a connected graph G ′ = (V ′ , E ′ ) in which V ′ ⊆ V and E ′ ⊆ V ′ × V ′ .
Definition 2. We define the non-compactness of a subgraph G ′ as

c(G ′ ) def = Ω(E ′ ) Ω(E)
where

Ω(E) = e∈E ω(e). ( 6
)
We say

G ′ is p-compact if c(G ′ ) = p.
Non-compactness is an estimation of the local vertex density, which plays the role of the relative volume π i of the hyper-rectangles in Definition 1. It can be interpreted in the spirit of non-parametric density estimation. Parzen methods [START_REF] Fukunaga | Introduction to Statistical Pattern Recognition[END_REF] locally estimate density at a given point by computing the distances to its neighbors

p(x) ≈ 1 N h N i=1 Q ||x -x i || h , ( 7
)
where Q is a smoothing kernel. Choosing a kernel Q that evaluates to one in G ′ and to zero elsewhere, and picking x ∈ X, yields

p(x) ≈ 1 N h 2 K i=1 ω((v, v i )), (8)
where v ∈ V is the vertex associated to feature x. Finally

Pr(v ∈ V ′ ) ≈ 1 N h 2 K j=1 K i=1 ω((v j , v i )). (9)
By normalizing Pr(v ∈ V ′ ), c(G ′ ) is obtained.

In our approach, non-compactness plays an important role in cluster detection. Informally, a cluster is a subgraph with two properties: (1) its vertices are sufficiently near each other with respect to the remaining vertices, i.e. small non-compactness, and (2) the number of its vertices is sufficiently large.

A detection scheme must propose a balance between the density of the cluster and its size. A small set must be very dense to be perceptually noticeable while larger sets are more clearly perceived even if they are less dense. A set of points will be more striking, and more compact, as it gets farther away from the rest of the points.

The non-compactness of a subgraph models how tight its vertices are but is not sufficient to characterize clusters. This can be seen in Figure 2 where

G ′ 1 = (V ′ 1 , E ′ 1 ) and G ′ 2 = (V ′ 2 , E ′ 2 ) are two different subgraphs such that Ω(E ′ 1 ) = Ω(E ′
2 ). Suppose they are respectively embedded in two graphs

G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) such that Ω(E 1 ) = Ω(E 2 ), then G ′
1 would have the same non-compactness as G ′ 2 while having more nodes.

8 2 Figure 2: Two different subgraphs G ′ 1 = (V ′ 1 , E ′ 1 ) and G ′ 2 = (V ′ 2 , E ′ 2 ) such that Ω(E ′ 1 ) = Ω(E ′ 2 ) = 4 + 2 √ 2.
Suppose they are respectively embedded in two graphs

G 1 = (V 1 , E 1 )
and Assume we were to model the problem described above as a classical hypothesis test:

G 2 = (V 2 , E 2 ) such that Ω(E 1 ) = Ω(E 2 ), G ′ 1 would
H 1 : the observed features have a particular distribution F ∈ F, i.e. the data is clustered.

H 0 : the observed features are distributed more randomly, e.g. uniformly.

Modeling H 1 means to model F. Modeling F, even if it was feasible, would require an a priori characterization of what a cluster is. Due to the reasons that have just been exposed, we are not interested in defining such a model. We prefer instead to follow the classical claims of the Computational Gestalt School [START_REF] Desolneux | From Gestalt Theory to Image Analysis[END_REF];

our detection algorithm will be driven by the Helmholtz principle: no perception in white noise. We will only concentrate on modeling H 0 and consider that low probabilities of occurrence under H 0 are indeed causal instead of casual.

Testing randomness to detect clusters is not a new concept. To cite a few, Hoffman, Jain et al. [START_REF] Hoffman | A test of randomness based on the minimal spanning tree[END_REF][START_REF] Jain | Uniformity testing using minimal spanning tree[END_REF] perform such kind of tests. The works by Cao et al. [START_REF] Cao | A unified framework for detecting groups and application to shape recognition[END_REF] and by Desolneux et al. [START_REF] Desolneux | From Gestalt Theory to Image Analysis[END_REF] also follow this line of research.

We are interested in a general clustering method but, in accordance to our model, in applications where the cluster shapes and the number of clusters are known a priori, the full hypothesis test could be performed, using similar but more simple a contrario techniques.

Given a subgraph G ′ and its non-compactness, we consider its number of vertices k as a realization of a random variable K. We can then model the probability that a p-compact subgraph G ′ has at least k vertices due to a realization of randomness. We denote this probability by Pr(G ′ | H 0 ).

Definition 3. Let G ′ be a p-compact subgraph of G, we define the probability of false alarms (PFA) of G ′ as

PFA(G ′ ) def = Pr(G ′ | H 0 ) = B(|V |, |V ′ |; p), (10)
where | • | denotes the cardinality of a set.

The probability of false alarms quantifies the unlikeliness of occurrence of

a p-compact subgraph G ′ of G with at least |V ′ | nodes among |V | under H 0 .
In other terms the unlikeliness of occurrence of a configuration of at least |V ′ | features among |V | with density p.

There have been previous attempts to automatically detect the number of clusters in Normalized Cuts (or spectral clustering), e.g. by Zelnik-Manor and Perona [START_REF] Zelnik-Manor | Self-tuning spectral clustering[END_REF]. Their work has similar goals but starts from different requirements: they indeed make use of the characteristics of the eigenspace. Moreover, since their method is based on selecting the minimum of an alignment cost function, it is not able to detect non-clustered data as such. Our method is specifically designed for this task.

Learning detection thresholds

To detect unlikely dense subgraphs, a threshold is necessary on the PFA. In the classical a contrario framework, a new quantity is introduced: the Number of False Alarms (NFA), i.e. the product of the PFA by the number of tests (see Definition 1). The NFA has a more intuitive meaning than the PFA, since it is an upper bound on the expectation of the number of false detections [START_REF] Desolneux | From Gestalt Theory to Image Analysis[END_REF]. The threshold is then easily set on the NFA.

To use the NFA one has to be able to compute (or at least analytically estimate) the number of tests being performed. In our setting, this is not possible, since it is equivalent to computing the number of subgraphs for a graph, which is an astronomical quantity (e.g. approximately 10 300 for N = 1000).

An alternative solution, proposed by Burrus [START_REF] Burrus | Image segmentation by a contrario simulation[END_REF], consists in estimating the threshold directly on the PFA by Monte Carlo simulations, following the actual search heuristics instead of trying to bound the total number of tests in a full search. Furthermore, this solution allows to estimate not only a global threshold but partial thresholds, by splitting the detected subgraphs into different categories, each with a dedicated threshold. In this work we follow this approach.

Let G be the set of all subgraphs of a graph G and let J K : G → {1, 2, . . . , K} be a hash function used to divide G into K categories. We define the exploration strategy S ⊆ G as a set of subgraphs to be analyzed during detection and learning. In Section 3.3 we analyze exploration strategies in depth. As an example we define the basic universal strategy S U = G.

We already stated that our detection algorithm is ruled by the principle of no perception in white noise. It is therefore clear that subgraphs in S with a PFA that is likely to occur in white noise have to be discarded. A direct approach would be to generate several random graphs, compute the PFA of their subgraphs and select a threshold such that all of them are discarded (up to a certain confidence level).

Given a hash function J K and an exploration strategy S, Algorithm 1 performs exactly that same procedure to compute a set of thresholds δ(ε) = {δ k (ε)} k=1...K . Thresholds are first initialized. For each category k, we run Q simulations. For each simulation q = {1 . . . Q}, the number

d q of subgraphs G ′ such that J K (G ′ ) = k and PFA(G ′ ) < δ k (ε) is counted. Then the empirical mean m k and deviation s k of d = {d q } q=1...Q are computed.
An upper bound u of the expectation µ k of m k is computed by performing a Student's t-test. We are looking to approximate ε/K by u and δ k (ε) is adjusted accordingly. We refer to Burrus [START_REF] Burrus | Image segmentation by a contrario simulation[END_REF] for further details. initialize δ k (ε)

3: repeat 4:
for all q ∈ {1 . . . Q} do 5:

build a graph G q by sampling N vertices from the distribution of H 0 .

6:

apply S to G q .

7:

d q ← #{G ′ ∈ S, PFA(G ′ ) < δ k (ε) ∧ J K (G ′ ) = k} 8:
end for

9:

Compute the empirical mean m k and deviation s k of d = {d q } q=1...Q

10:

Compute a confidence interval on the expectation µ k of d using the

property P (µ k ≤ m k ) = F Q-1 m k -µ k s k √ Q -1 where F n (x)
is the distribution function of a Student law with n degrees of freedom.

11:

For a chosen confidence level, if the estimated upper bound of µ k is greater than ε/K, increase δ k (ε) otherwise decrease δ k (ε).

12:

until convergence of δ k (ε)

13: end for Definition 4. We say that a subgraph G ′ is an ε-meaningful cluster if

PFA(G ′ ) < δ J K (G ′ ) (ε) ( 11
)
for a properly computed set of thresholds δ(ε). We define the number of false

alarms (NFA) of G ′ as NFA(G ′ ) def = ε δ J K (G ′ ) (ε) PFA(G ′ ) (12)
Notice that subgraphs consisting of a single node must certainly not be detected. From Definition 3 they cannot be detected, i.e. B(|V |, 1; 0) = 1. As we look for rare events, subgraphs with probability of occurrence in noise equal to 1 are never detected.

Lemma 1. The expected number of ε-meaningful clusters in a random graph G is lower than ε.

Proof. By construction of δ k (ε), the number of meaningful subgraphs G ′ in a random graph G is lower than ε/K. By linearity of expectation, if there are less than ε/K errors in average for each category, then there are globally less than ε errors in average. (in negative logarithmic scale). Thresholds evolve smoothly with size, consequently they can be safely interpolated for intermediates sizes. Larger subgraphs are rarer and thresholds are therefore less restrictive than for smaller subgraphs.

G ′ = (V ′ E ′ ) is simply J K (G ′ ) = ⌊(|V ′ | + 1) • K/N ⌋. Medium-

Eliminating redundancy

While each meaningful cluster is relevant by itself, the whole set of meaningful clusters exhibits, in general, high redundancy [START_REF] Cao | A unified framework for detecting groups and application to shape recognition[END_REF]. Indeed, a very meaningful

for all ε-meaningful clusters G 1 , G 2 do if G 2 ⊂ G 1 ∨ G 1 ⊂ G 2 then eliminate arg max (NFA(G 1 ), NFA(G 2 ))
end if end for that indeed produces the desired result but is computationally intractable.

Moreover, for a given graph, exploring the whole set of its subgraphs to compute each PFA is already intractable. An exploration algorithm is therefore needed.

Hierarchical clustering methods are well suited for this task.

Definition 5. A hierarchy T of a graph G = (V, E) is a set such that ∀ T ∈ T ∃ v ∈ V, T = {v}, or ∃ T 1 , T 2 ∈ T , T = T 1 ∪ T 2 . ( 13
)
Depending on the direction they build the hierarchy, these clustering methods can be agglomerative (bottom-up) or divisive (top-down). The former are usually computationally simpler.

Any hierarchical algorithm [START_REF] Jain | Data clustering: 50 years beyond k-means[END_REF] can be used. In this work we focus on the agglomerative algorithm called minimal spanning tree. Zahn's work [START_REF] Zahn | Graph-theoretical methods for detecting and describing gestalt clusters[END_REF] concentrates on stating the good properties of minimal spanning trees to detect perceptual clusters. The construction of the minimal spanning tree starts by considering each single point as a cluster and iteratively merges the pair of clusters containing the closest nearest-neighbor points. It can be found using Kruskal's method (Figure 4). We will restrict ourselves to explore the node sets contained in a hierarchy and to compute PFAs on the subgraphs induced by them. Finally we apply the pruning rule profiting from the inclusion properties of the tree structure.

Definition 6 (Exploration strategy). Given a graph G = (V, E), we denote by

G C = (C, E ′ ) the subgraph such that ∀ (c a , c b ) ∈ E, c a ∈ C ∧ c b ∈ C ⇒ (c a , c b ) ∈ E ′ , ( 14
)
and we say that G C is induced by C. For a given hierarchy T we define the exploration strategy as S T = {G T } T ∈T .

Definition 7 (Maximal ε-meaningful cluster). For a learned set of thresholds δ(ε), we say that G T ∈ S T is a maximal ε-meaningful cluster if

1. G T is an ε-meaningful cluster, see Definition 4,
2. all meaningful descendants are less meaningful,

∀ T ′ ∈ T , T ′ ⊂ T, NFA(G T ′ ) > NFA(G T ),
3. all meaningful ancestors are less meaningful,

∀ T ′ ∈ T , T ⊂ T ′ , NFA(G T ′ ) ≥ NFA(G T ).
The proposed clustering algorithm simply consists on detecting maximal εmeaningful clusters. Definition 7 is closely related to the maximality rule by Cao et al. [START_REF] Cao | A unified framework for detecting groups and application to shape recognition[END_REF] but is simpler and it might be regarded as an implementation of the exclusion principle [START_REF] Desolneux | From Gestalt Theory to Image Analysis[END_REF]. In our experiments, we found no need to include a measure of meaningfulness for a pair of subgraphs.

According to Definition 6 the subgraph G C is the largest subgraph in G not containing more vertices than C. Why not use instead the partial trees provided by the hierarchy as in Figure 4? Because in the father (represented in white) inter-cluster edges (dashed line) are underrepresented with respect to intra-cluster edges (solid lines).

To explain this situation, let G = (V, E) be a hypothetical base graph. Let A be the blue node set and B the red node set respectively and let them induce subgraphs G A = (A, E A ) and G B = (B, E B ). Let us denote the father of both

G A and G B by G A∪B = (A ∪ B, E A ∪ E B ∪ E AB ) where E AB = {(v A , v B ) ∈ E, v A ∈ A ∧ v B ∈ B}. Then, c(G A∪B ) = Ω(E A ) + Ω(E B ) + Ω(E AB ) Ω(E) . ( 15
)
Let us compare PFA(G A∪B ) with PFA(G A ). The non-compactness c(G A∪B ) grows by Ω(E B )+Ω(E AB )

Ω(E)

with respect to c(G A ). Since B is tight, Ω(E B ) is small and the growth is mainly determined by Ω(E AB ). Meanwhile, providing the cardinality of such groups as important information.

E A ∪ E B ∪

Revising elongated clusters

Non-elongated clusters are preferred by our detection algorithm. Elongated clusters are separated in several non-elongated maximal meaningful clusters as in Figure 5(a). Detecting non-elongated clusters is equivalent to detecting clusters with the same intrinsic dimension as the embedding. Since in the embedding (see Section 2) some clusters are indeed elongated, a revision is needed.

For a given graph

G = (V, E), let G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) be two subgraphs of G. We define L(G 1 , G 2 ) def = min max e∈E1 ω(e), max e∈E2 ω(e) . ( 16
)
This equation is very similar to the one proposed by Felzenszwalb [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] to detect clusters in a hierarchical structure except there is no extra scale parameter. Let G T = (V T , E T ) be a maximal ε-meaningful cluster, G F = (V F , E F ) its father and G S = (V S , E S ) its sibling in T . Let us define

G T ∪S def = (V F , E T ∪ E S ∪ E T S ) (17)
where

E T S = {e ∈ E F , ω(e) ≤ L(G T , G S )}.
Long edges connecting the extremes of the G F are eliminated from G T ∪S by using a local connection between G T and G S . The effect of this local connection rule is shown in Figure 6.

If PFA(G T ∪S ) < PFA(G T ), G F is replaced in S T by G T ∪S and maximality in S T is recomputed. This procedure is repeated until convergence. Note that convergence is guaranteed since changes are propagated up in the tree, stopping at the root in the worst case. This heuristic is able to correct for oversplitting of elongated clusters present in the embedding, as seen in Figure 5(b). if G T is maximal ε-meaningful then replace G F by G T ∪S in S T

17:

end if 18: until no more replacements are performed

Experimental Results

As every spectral clustering technique, there are two main values to be tuned: the scale of the kernel distance and parameter M (see Equation 2and Algorithm 2). The former was fixed by manually choosing the scale that yields the best results with k-means. Anyhow, once the scale fixed, all compared methods analyze the transformed feature space (i.e. the embedding) an should provide results independently of that choice. The parameter M can be interpreted as an estimation of the number of groups [START_REF] Ng | On spectral clustering: Analysis and an algorithm[END_REF]. For example, when using k-means, M is set usually set equal to k. In the case of meaningful clusters, the value of M was determined empirically and can be seen as an overestimation of the largest possible number of groups.

The proposed approach is successful at finding perceptually clear 2D clusters even when clusters have arbitrary shapes (Figure 7). By only fixing the parameters needed to compute the embedding, i.e. its dimension M and the variance of the Gaussian kernel used for the distance, the clustering is successful. No extra parameter is needed as fixing ε = 1 is sufficient for stable detections. Maximal ε-meaningful clusters perform correctly with no parameter tuning (i.e.

the number of clusters is automatically found by the algorithm), see Figure 8(c).

( k-means incorrectly merges some clusters (zone A) and incorrectly splits others (zone B).

The next experiment aims at comparing our results with Mean Shift [START_REF] Comaniciu | Mean shift: a robust approach toward feature space analysis[END_REF][START_REF] Fukunaga | The estimation of the gradient of a density function, with applications in pattern recognition[END_REF].

Mean Shift performs a non-parametric density estimation (using sliding windows) and finds its local maxima. Clusters are determined by what Comaniciu and Meer call "basins of attraction" [START_REF] Comaniciu | Mean shift: a robust approach toward feature space analysis[END_REF]: points are assigned to a local maximum following an ascendent path along the density gradient1 .

Figure 9 presents an experiment were Mean Shift is used to cluster the dataset in Figure 8(a). Different density estimations were performed, by varying the kernel size. Clearly, results are suboptimal. The main disadvantage we see in the density estimation step is that a global kernel size must be chosen. Such a strategy is unable to cope with clusters of different densities and spatial sizes.

Choosing a small kernel causes to correctly detect dense clusters at the price of oversplitting less denser ones. On the contrary, a large kernel corrects the oversplitting of less denser clusters but introduces undersplitting for the denser ones. Our method also uses non-parametric density estimation, but the scale is not fixed in advance. As shown by the Parzen windows interpretation of the non-compactness, the "kernels" we use are determined by the candidate sets given by the hierarchy and thus multiscale density estimation if performed. In Figure 10 we show segmentation results on synthetic images. A precision should be made regarding this experiment as well as all segmentation experiments in this paper: our goal here is not to present a new segmentation method, but just to illustrate the performance of proposed clustering technique by means of segmentation examples. For this reason, we simply consider that the vectors to be clustered are the set of single color image pixels or 3 × 3 color image patches, depending on the experiment. Notice that there is no term imposing image spatial connectivity of clusters.

If the random initialization procedure picks an appropriate seed, Normalized

Cuts with k-means may perform reasonably well when setting the correct k (Figure 10). Still, sometimes the resulting clusters can be degraded by noise, as in the top figure on the second column. When k is not well chosen (k = 3 in our example) results are poor, as on the third column. Results on the fourth column show that our method is successful without any further parameter tuning. correct. In all cases except for the one on the first row, the number of clusters k had to be overestimated with respect to the number of visually perceived regions. In some cases, some regions are overconnected (see the blue region on the first row and the red region on second row) a fact that could not be corrected by slightly increasing k.

Results on the third column were obtained with Zelnik-Manor and Perona' method (ZMP) [START_REF] Zelnik-Manor | Self-tuning spectral clustering[END_REF] 2 . In this case the features are individual color pixels, since we did not find better results by using patches. In one case, on the fifth row, the method oversegments the image, while in the others the image is undersegmented. In these cases, boundaries between regions seem somewhat away from perceived regions.

The proposed algorithm, whose results are depicted on the fourth column, performs well in all cases, being able to correctly separate perceptually evident clusters. Contrarily to the other two methods, small clusters are not arbitrarily merged to the closest larger cluster but remain undetected. In simpler terms, some patches are detected as not belonging to any cluster: they are considered as noise. In accordance to this claim and since we are clustering patches (without any kind of rotation invariance) the ones that lie on the boundaries between objects are not classified. This is a desirable feature since boundary patches are of different nature from non-boundary patches.

Figure 12 presents more segmentation results on images from the COIL-100 database. The same remarks from the previous examples hold. In general, our method correctly finds the clusters and outperforms ZMP, although in some cases relatively big areas remain detected as unclustered patches.

The Berkeley Segmentation Dataset [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF] is often used to perform segmentation experiments. Nowadays, to our knowledge, an exhaustive review of the clustering methods reported in the literature shows that there exists no clustering approach that is able to correctly and automatically segment all images in such a varied and complex dataset. Hence, we selected a subset of this database that we consider that should be easier to segment. For the sake of completeness, experiments on this subset are also included.

For the final set of experiments we compare our method with the algorithm by Cour et al. [START_REF] Cour | Spectral segmentation with multiscale graph decomposition[END_REF]. They use the Normalized Cut framework, but using a multiscale decomposition3 . The final embedding for clustering is constructed by using the information on the different scales and applying inter-scale constraints to ensure overall consistency. The final clustering step is performed by using the discretization algorithm by Yu and Shi [START_REF] Yu | Multiclass spectral clustering[END_REF], which seeks the discrete solution closest to the continuous optimum by rotating the normalized eigenvectors. In their algorithm the number of clusters is an input parameter and must be equal to the dimensionality of the embedding; this choice does not necessarily lead to optimal results. Moreover, as pointed out by Zelnik-Manor and Perona, this iterative method can easily get stuck in local minima and thus does not reliably find the optimal alignment [START_REF] Zelnik-Manor | Self-tuning spectral clustering[END_REF]. This claim was confirmed in our experiments.

In Figures 13,[START_REF] Zahn | Graph-theoretical methods for detecting and describing gestalt clusters[END_REF] It is important to note that we do not propose a specifically designed method to solve the final assignment problem in Normalized Cuts, but a general clustering algorithm. In this work, we use this algorithm to cluster sets of point within the Normalized Cuts framework.

In Figures 13 and14, the spectral embedding is constructed with M = 3. This is based on two reasons. First, choosing three regions seems to be a reasonable choice in both experiments. Second, visual inspection of point clouds is easier (otherwise, dimensionality reduction techniques should be applied and results would actually depend also on the performance of these techniques).

By looking directly at the embeddings in Figures 13 and14, it is straightforward to see that the clusters detected by YS and by ZMP differ from the results that one should have expected. The proposed method yields detections which seem to be more adequate to the point clouds structure. In Figure 13 we perceive that the segmentation obtained with the elongated clusters revision step (Section 3.4) is globally better than the one which omits this step. The opposite situation occurs in Figure 14, where disabling the revision allows to detect the balcony. As a side effect, the sky is split in three regions, which roughly correspond to different brightness resulting from the degradé of the sky.

In Figure 15, the embeddings are constructed with M = 10. In some cases, YS and ZMP perform better while in others the proposed method produces more satisfactory results. All methods oversplit or undersplit clusters in different cases. In general, we think there is no clear winner for these relatively complex scenes. However, both in ZMP and in the proposed approach, contrarily to YS, the number of clusters is not chosen in advance. Moreover, in contrast to ZMP, our method is general in the sense that it was not specifically designed for Normalized Cuts and can be used in other scenarios.

Final Remarks

The proposed method satisfies Zahn's requirements for a perceptual clustering technique. On the one hand, the algorithm does not involve any random choice since it is completely deterministic. On the other hand, once distances have been computed, the method is independent from the dimension of the points (in this case, the dimension of the embedding). Its running time is not affected by an increase in dimensionality: it does not suffer from the "curse of dimensionality". In addition using a more complicated, time consuming distance function is transparent to our method.

The number of clusters is automatically determined, eliminating a classical parameter that is usually hard to choose. It is replaced by ε which has a more intuitive meaning: it controls the average number of false detections. Tuning its value is not necessary since setting ε = 1 is sufficient in practice.

Detection thresholds are easily computed from ε by performing Monte Carlo simulations. These thresholds are well adapted to accept/reject non-clustered data. Experimental results support this claim. Indeed, our method correctly finds the number of clusters and the detected clusters are perceptually significant. Moreover, detections are highly stable since clusters have NFAs well below the estimated thresholds.

Results show that the technique is shape independent. Although our base algorithm has a bias towards non-elongated clusters, a simple heuristic rule is able to correct that situation and yield correct results for a wide range of shapes.

Finally, the exploration rule in Section 3.3 allows for a reasonable computational complexity of O(N 2 • log N ), detailed in Appendix A. When N is large, although the total complexity is a low-degree polynom, handling a fully connected graph is costful, no matter how simple the computed operations are.

Figure 1 :

 1 Figure 1: Example of image segmentation from 3×3 color patches, obtained using Normalized Cuts and k-means with k = 4. In each example k-means was executed 5 times and the segmentation that minimizes the Normalized Cut is chosen. Due to the clusters difference in density and in cardinality, the method yields unstable results.

  have the same non-compactness as G ′ 2 while having more nodes. Suppose we wanted to statistically model all possible instances of clustered data. First, we would need a model for each possible cluster shape (e.g. Gaussian). Each individual model would have its own parameter set. Next, since we seek for a general model, it must support data distributed in multiple clusters with different shapes. In other terms, we need to integrate the individual models into a mixture. For example, k-means is aimed to detect mixtures of k Gaussian distributions.These different mixtures can be seen as a parametric family F of distributions. This family is parametric on the number of clusters and on the parameters of the distribution modeling each cluster. Such a family has colossal cardinality and parameter set. Even if we restrict ourselves to a mixture of k Gaussian clusters for H dimensional data, the problem is hard enough. Since there are H(H + 1)/2 + H parameters for each Gaussian (determined by an H × H covariance matrix and H × 1 mean vector), the number of parameters is k(H(H + 1)/2 + H) for each k. A family of such mixtures, parametric on k, is already untestable in practice.

Algorithm 1

 1 Compute δ(ε) for N vertices using exploration strategy S by Q Monte Carlo simulations.1: for all k ∈ {1 . . . K} do 2:

Figure 3

 3 Figure 3 depicts the profile of the learned set of thresholds δ(ε) for the exploration strategy explained in Section 3.3 and different graph sizes. There are N vertices, K = 10 categories and the hash function for a graph G ′ = (V ′ E ′ )

  small and compact subgraphs are more frequent than large and compact subgraphs causing that thresholds for the first categories are more restrictive than thresholds for the last ones. Note that the evolution of the set of thresholds δ(ε) with size is smooth, allowing the computation of intermediate sets of thresholds by interpolation.The role of the hash function is to correct a bias that might be introduced by the exploration strategy. If the sizes of the clusters one seeks to detect are well enough sampled by the exploration strategy, choosing K = 1 should suffice.

Figure 3 :

 3 Figure 3: Learned set of thresholds δ(ε) for ε = 1 for sizes ranging from N = 100 to N = 300

Figure 4 :

 4 Figure 4: Part of a minimal spanning tree. The blue node set and the red node set are linked by the dashed edge, creating a new node in the minimal spanning tree.

Figure 5 :

 5 Figure 5: Maximal meaningful clusters (a) before and (b) after revising elongated clusters. In (a) 10 clusters are found while in (b) only 3 remain.

Figure 6 :Algorithm 2 2 : 4 : 5 : M = ∅ 6 :

 622456 Figure 6: Effect of locally connecting clusters. The subgraphs G T (in blue) and G S (in red) are siblings in T . For clarity, only inter-cluster edges are depicted. Left, their father G F in T . Right, the locally connected graph G T ∪S .

13 :

 13 find its sibling G S , its father G F in S T and compute G T ∪S14:if PFA(G T ∪S ) < PFA(G T ) then 15: replace G T (and possibly G S ) by G T ∪S in M 16:

Figure 7 (

 7 Figure 7(e) presents an interesting case since some maximal clusters are not meaningful (represented in cyan, black and orange). The scene is composed of a mixture of three Gaussians. Peripheral points, i.e. located in low density areas, are harder to merge. Note that spectral methods are unable to deal with highly intertwined clusters as features are mapped to a single manifold in the Euclidean embedding.

Figure 7 :

 7 Figure 7: 2D points clustering examples. In (a), (b), (c) and (d) all groups are meaningful. In (e) maximal clusters are shown: only red, green and blue groups are meaningful while cyan, black and orange are not and are finally discarded by our algorithm.

Figure 8

 8 Figure 8 depicts a comparison between results using k-means and our algorithm. Both start from the same embedding. We consider that there are 15 clusters in Figure 8(a). For k-means the correct number of clusters was set. The combination of groups with very high density and groups with low density causes the random initialization in k-means to fail, see Figure 8(b). It creates under-split clusters, e.g. rectangle A, and over-split clusters, e.g. rectangle B.

Figure 8 :

 8 Figure 8: (a) Original scene. Starting from the same embedding, result with (b) k-means, where we manually set the correct number of clusters, and (c) maximal meaningful clusters.

Figure 9 :

 9 Figure 9: Results with Mean Shift for the point set from Figure 8(a). The local maxima of the estimated density are signaled by x's. Even when varying the kernel size, results are clearly suboptimal.

Figure 10 :

 10 Figure 10: Comparison of image segmentations. On the first column,original images with 5 and 4 regions respectively. On the second column, segmentations obtained with k-means by correctly setting k to 5 and 4 respectively. On the third column, segmentations obtained with k-means by setting k = 3. On the fourth column, segmentations obtained with our method.

Figure 11

 11 Figure 11 presents more image segmentation results. Results on the second column are among the best we could obtain with k-means, by carefully choosing k by hand (we set k to 3, 6, 6, 6 and 11 respectively). In general, results are

  and 15 we use Cour's algorithm to construct the embeddings and then compare the clustering results obtained with different methods: (a) Yu and Shi' algorithm (YS) [32]; (b) Zelnik-Manor and Perona' algorithm (ZMP), restricted to the final assignment of points to clusters [27]; (c) maximal meaningful clusters, revising elongated clusters (MMC+R); (d) maximal meaningful clusters, without revising elongated clusters (MMC-R), i.e. by omitting lines 11 to 18 on Algorithm 2.

Figure 11 :Figure 12 :Figure 13 :Figure 14 :Figure 15 :

 1112131415 Figure 11: Comparison of image segmentations from 3 × 3 color patches. Results with kmeans were obtained by tuning k by hand. In all examples, for maximal meaningful clusters non-detected areas are depicted in black.

  E AB grows by |E B | + |E AB | with respect to E A . If |E AB | is small (in our case 1),the growth in size is mainly determined by |E B |. The same reasoning can be applied to PFA(G A∪B ) and PFA(G B ). In summary, Ω(E AB ) has to be very large to compensate for the relatively large growth in size. If it is not the case, the father will be more meaningful than its two children. Only very separated clusters will be detected separately. To correct this situation, inter-cluster edges have to be better sampled. A reasonable choice is using the subgraphs induced by A and B.

Comaniciu and Meer

[START_REF] Comaniciu | Mean shift: a robust approach toward feature space analysis[END_REF]

state that "arbitrarily structured feature spaces can be analyzed only by nonparametric methods since these methods do not have embedded assumptions". They classify nonparametric clustering methods into two classes: hierarchical clustering and density estimation. Regarding the first class, they regard the detection of clusters in a hierarchy as being a non-trivial task. The proposed approach, maximal ε-meaningful clusters, merges these two main trends. It detects clusters in a hierarchy by using density estimation. The hierarchy provides candidate groups in a natural manner thus, from one side, allowing a reduced effort in the density estimation step and, from the other side,

www.mathworks.com/matlabcentral/fileexchange/10161-mean-shift-clustering

http://webee.technion.ac.il/ ~lihi/Demos/SelfTuningClustering.html

www.seas.upenn.edu/ ~timothee/software/ncut_multiscale/ncut_multiscale.html

The implementation in its current state can not handle graphs with more than twenty thousands nodes. The computation time of maximal meaningful clusters for a graph of such size takes between one and three minutes.

Acknowledgments

We thank the reviewers for their comments and suggestions, which significantly contributed to improve the quality of the publication. We acknowledge financial support by CNES (R&T Echantillonnage Irregulier DCT/SI/MO-2010.001.4673), FREEDOM (ANR07-JCJC-0048-01), Callisto (ANR-09-CORD-003), ECOS Sud U06E01, ARFITEC (07 MATRH) and the Uruguayan Agency for Research and Innovation (ANII) under grant PR-POS-2008-003.

Appendix A. Temporal complexity

Kruskal's algorithm for computing the minimal spanning tree has a complexity of O(|E| • log |E|), as the edge set E in G must be sorted. There are faster algorithms such as Prim's but optimal computation of the minimum spanning tree is not the goal of this work. Kruskal's algorithm is sped-up by using a union-find algorithm on a disjoint-sets data structure [START_REF] Tarjan | Worst-case analysis of set union algorithms[END_REF]. After sorting edges, union-find allows to build the minimal spanning tree T in quasi-linear time.

More precisely, its worst-case complexity is O(|E| • α(|E|)) where α is the extremely slow-growing inverse Ackermann function. In practice α(M ) < 4.

Computing the set of edges of each node in T can be done in O(|E| • log |E|).

The computation of the binomial tail is done by using the incomplete beta function which is constant in time [START_REF] Press | Numerical Recipes in C[END_REF].