Juan Antonio Cordero

Matthias Philipp

Emmanuel Baccelli
email: baccelli@inria.fr

Compound Wired/Wireless Internetworking with OSPF

Keywords: OSPF, MANET, MPR, Routing, Internetwork, Compound, Testbed, Experiment OSPF, MANET, MPR, Routage, Internetwork, Hybride, Banc d'essai, Expérience

As wireless ad hoc networks become more deployed, there is a growing interest for compound internetworks, that is, internetworks that contain both fixed and ad hoc networks. Routing is one of the main challenges that arise in such compound internetworks. Although specialized routing protocols exist for wired and for ad-hoc networks, and several such specialized protocols could be used together in a compound internetwork, it has been shown that the use of a single routing solution in the whole internetwork brings several advantages. The IETF has standardized extensions of the Open Shortest Path First (OSPF) protocol for ad hoc operation.

While previous performance evaluations of these extensions have focused on the wireless part of the internetwork and have been mostly performed by way of simulation tools, this paper studies practical issues of the use of a single protocol, extended OSPF, providing paths through a compound internetwork. In first term, it examines the behavior of OSPF in a real networking testbed. This testbed consists of an internetwork composed of 6 computers that form a static topology, i.e., computers do not move during network lifetime. In second term, the overall behavior of extended OSPF, both considering standard OSPF and its MANET extension, is examined. Despite the limitations of the testbed, these experiments provide both a proof-of-concept and complementary results compared to prior work in the domain, which was mostly based on simulations, and focused on wireless ad hoc network scenarios only.

Compound Wired/Wireless Internetworking with OSPF

Résumé : À mesure que les réseaux ad hoc sans fil deviennent de plus en plus déployés, il y a un intérêt croissant pour des internetworks (réseaux des réseaux) hybrides, c'est-à-dire, internetworks qui contiennent la fois des réseaux ad hoc et des réseaux fixes. En ce domain-là, le routage devient l'un des principaux défis qui se posent. Bien qu'il existe des protocoles de routage spécifiques pour réseaux filières et des réseaux ad hoc, et plusieurs de ces protocoles pourraient être utilisés ensemble dans un internetwork hybride, il a été montré que l'utilisation d'une seule solution de routage dans un internetwork hybride a plusieurs avantages. L'IETF a standardisé trois extensions du protocole Open Shortest Path First (OSPF) ayant pour but le routage dans des réseaux ad hoc et à mobilité (MANETs).

Les évaluations du rendement de ces extensions développées jusqu'à présent se sont concentrées sur la partie sans fil (ad hoc) de l'internetwork et ont été principalement effectuées à travers de simulations. Ce rapport étudie des questions pratiques liées a l'usage d'un seul protocol de routage, en l'occurrence OSPF, sur un internetwork hybride. D'abord, la performance de OSPF est analysée avec des experiénces sur un banc d'essai de réseaux (testbed ). Ce testbed consiste en un internetwork hybride de 6 ordinateurs qui forment une topologie statique, c.-à.-d. où les ordinateurs ne bougent pas durant la vie du réseau. Deuxièmement, le comportement global du protocole OSPF étendu, à la fois sa version standard et son extension pour MANETs, est examiné. Malgré les limites du testbed, ces expériences fournissent à la fois une preuve de concept et des résultats qui confirment et complétent des travaux antérieurs dans le domaine, basés sur l'analyse du protocol sur MANETs à travers des simulations.

Introduction

Since the Internet Engineering Task Force (IETF) defined in 1997 the concept of Mobile Ad hoc Networks (MANETs), several research efforts have focused on enabling communication in wireless multi-hop networks in which topology is spontaneous and dynamic. As a result of such efforts, different routing protocols have been designed for MANET operation, the most prominent to date being the OLSR [START_REF] Clausen | RFC 3626, Optimized Link State Routing Protocol (OLSR)[END_REF] and AODV [START_REF] Perkins | RFC 3561, Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF]. This paper studies the case of Autonomous Systems (AS) containing both ad hoc and fixed networks -such an AS is hereafter denominated compound AS. An approach for routing in a compound AS consists in splitting the AS into several routing domains, and then using a routing protocol for each domain: MANET-specific protocols in ad hoc networks, other existing protocols for fixed networks. An alternative approach consists of using a single routing protocol for the whole AS -ad hoc and fixed networks considered together. The former approach requires the presence in the AS of routers with specific hardware and software capabilities, denominated gateways, in order to provide connectivity between different routing domains. The latter approach, explored in this paper, reduces the cost of network maintenance and operation as no such gateways are needed, as explained in [START_REF] Cordero | Wired/Wireless Compound Networking[END_REF]. This is, however, at the expense of increasing the complexity of the employed routing protocol, which in this case needs to handle the diverse characteristics of MANETs and fixed networks with the same core mechanisms.

To date [START_REF] Halabi | Internet Routing Architectures, 2nd Edition[END_REF], two major protocols are used in the Internet for IGP routing: the Open Shortest Path First protocol (OSPF, specified in RFCs 2328 [START_REF] Moy | RFC 2328, OSPF Version 2, IETF[END_REF] and 5340 [START_REF] Coltun | RFC 5340, OSPF for IPv6[END_REF]) and the Intermediate-System-to-Intermediate-System protocol (IS-IS, RFC 1142 [START_REF] Oran | RFC 1142, OSI IS-IS Intra-domain Routing Protocol[END_REF]). This paper explores the use of OSPF for routing in compound ASes, by way of evaluating its performance in a testbed consisting in a small compound internetwork.

Related Work

Several extensions of OSPF for MANET operation have recently been proposed and analyzed. Early studies and proposals such as [START_REF] Henderson | A Wireless Interface Type for OSPF[END_REF] [20] paved the way to IETF standardizing several OSPF protocol extensions for operation over ad hoc networks [START_REF] Baccelli | RFC 5449, OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF] [5] [START_REF] Ogier | RFC 5614, Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding[END_REF]. Various studies have evaluated and compared the performance of these extensions in mobile ad hoc scenarios [START_REF] Baccelli | Multi-Point Relaying Techniques with OSPF on Ad Hoc Networks[END_REF][START_REF] Henderson | Evaluation of OSPF MANET Extensions[END_REF][START_REF] Baccelli | OSPF over Multi-Hop Ad Hc Wireless Communications[END_REF], mostly via simulations. Further improvements of these extensions have been proposed in [START_REF] Cordero | MPR+SP -Towards a Unified MPR-based MANET Extension for OSPF[END_REF][START_REF] Baccelli | Optimization of Critical Data Synchronization via Link Overlay RNG in Mobile Ad Hoc Networks[END_REF], still comparatively evaluated via simulations in MANET only scenarios. In contrast, this paper evaluates OSPF on a real testbed, consisting in both ad hoc networks and fixed wired networks.

Paper Outline

In the experiments described thereafter, all router interfaces run OSPF -interfaces attached to the wired network use the OSPF point-to-point interface specified in [START_REF] Coltun | RFC 5340, OSPF for IPv6[END_REF][START_REF] Moy | RFC 2328, OSPF Version 2, IETF[END_REF], while wireless interfaces use the MANET interface type of the OSPF protocol extension specified in [START_REF] Baccelli | RFC 5449, OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF]. Analysis of the behavior of extended OSPF on such a testbed confirms results obtained in simulation-based studies. In particular, this paper concentrates on the effect of wireless links on INRIA data path quality, on managing their coexistence with wired links in the same internetwork, as well as the impact of wireless links on overall OSPF control traffic.

Section 2 introduces the basics of OSPF and its extension for MANET operation, both used in the testbed. Section 3 describes the main characteristics of the testbed, the internetwork topology and the configuration of the participating network interfaces. Section 4 presents the performed experiments and the most significant results. Finally, section 5 concludes the paper.

2 The OSPF Protocol and its MANET Extension OSPF [START_REF] Coltun | RFC 5340, OSPF for IPv6[END_REF][START_REF] Moy | RFC 2328, OSPF Version 2, IETF[END_REF] is a link-state routing protocol for IP networks. This implies that each router maintains a local instance of the Link-State Database (LSDB), representing the full network topology -with the objective of the protocol being that each router should have the same information in its local instance of LSDB and, thus, the exact same view of the network topology. Paths to every possible destination are derived from the Shortest Path Tree (SPT) that every router computes, by way of Dijkstra's algorithm [START_REF] Dijkstra | A Note on Two Problems in Connection with Graphs[END_REF]. OSPF supports network partitioning in several areas, in a way such that topology information maintained by different routers (the LSDB from which they maintain local instances) is the same if they belong to the same area. Throughout this document, however, a single area is configured in the internetwork. Routers acquire local topology information and advertise their own presence by periodically exchanging Hello messages with all their 1-hop neighbors (i.e. neighbor sensing). With such signaling, each router becomes aware of its immediate network topology, i.e. its 2-hop neighborhood. This also allows verification of bidirectional connectivity with 1-hop neighbors (then called bidirectional neighbors). The set of symmetric 1-hop neighbors of a router x are denoted by N (x), whereas the set of symmetric 2-hop neighbor are denoted by N 2 (x).

Each router also explicitly synchronizes its local instance of LSDB with a subset of its bidirectional neighbors. Links between a router and its synchronized neighbors are called adjacencies, and are required to form a network-wide connected backbone, connecting all routers in the network, in order to ensure paths can be computed correctly.

Finally, routers also acquire remote topology information by way of receiving Link State Advertisements (LSA). Each such LSA lists mainly the current adjacencies of the router which generated the LSA. LSAs are disseminated through the entire network in reliable fashion (explicit acknowledgements and retransmissions) via the backbone formed by adjacencies; this operation is called LSA Flooding. Thus, any router which has formed adjacencies must advertise this periodically by way of originating an LSA and performing LSA flooding.

Remote topology information is then used for the construction of the Shortest Path Tree: each router computes the shortest paths over the network graph described in the set of received LSAs it, by way of Dijkstra's algorithm.

According to this structure, OSPF distinguishes several types of links: a subset of bidirectional links become adjacent, among which a new subset is selected to be part of the SPT. While data traffic is routed on the SPT, control traffic is sent over adjacent links.

Packet Types

Routers in OSPF use five types of messages and packets to exchange topology information over the networks, some of them have been already mentioned in this section: Hello packets are used for neighbor sensing, Database Description (DBDesc) packets are exchanged for LSDB synchronization and Link State Advertisements (LSAs) are used for topology reliable flooding and update. After the exchange of DBDesc packets, a router in process of LSDB synchronization may request to its synchronizing neighbor the retransmission of particular LSAs -these requests are sent by way of Link State Request (LSReq) packets. Several LSAs may be sent in a single Link State Update packet (LSU). Several LSA acknowledgements may also be grouped in a single Link State Acknowledgment (LSAck) packet.

Interface Types for Wired Links

Rules for flooding and adjacency handling vary for the different interface types supported by OSPF. In broadcast and non-broadcast multiple access (NBMA) interfaces, the flooding procedure is mainly managed by Designated Routers (DRs). A Designated Router is elected from among routers whose interfaces are connected to the same link. Such a DR forms adjacencies with all the routers connected to the same link, and it becomes responsible for flooding of LSAs, originated by routers on that link. In point-to-point and point-tomultipoint interfaces, all links are synchronized and all interfaces participate in LSA flooding.

MANET Interface Type

The MANET interface type is defined in the extension of OSPF for operation over MANETs. Three different extensions have been standardized by the IETF [START_REF] Roy | RFC 5820, Extensions to OSPF to Support Mobile Ad Hoc Networking[END_REF][START_REF] Ogier | RFC 5614, Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding[END_REF][START_REF] Baccelli | RFC 5449, OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF], each of which specifies mechanisms to optimize topology description, flooding and LSDB synchronization in wireless ad hoc environments.

The experiments carried out used RFC 5449 [START_REF] Baccelli | RFC 5449, OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF]. Wireless interfaces following this specification select a set of Multi-Point Relays (MPRs) among its bidirectional neighbors [START_REF] Clausen | RFC 3626, Optimized Link State Routing Protocol (OLSR)[END_REF][START_REF] Jacquet | Performance of Multipoint Relaying in Ad Hoc Mobile Routing Protocols[END_REF]. The set of MPRs selected by the wireless interface of a router must ensure that every packet received from the router reach all 2-hop neighbors of the selecting interface in 2 hops (MPR coverage criterion). A link between a router and one of its MPRs is denominated MPR link.

LSA flooding is then performed through MPRs, meaning that an LSA transmitted (originated or forwarded) by an interface is retransmitted by the MPRs of such interface. Links between interfaces and their MPRs are synchronized and thus become adjacent. Moreover, each interface describes in its LSAs the set of MPRs and MPR selectors. As the set of adjacencies based on MPR selection may not provide a connected subgraph, links from one additional router in the network (denominated synch router) are also declared adjacent to ensure adjacency set connection [START_REF] Cordero | MPR-based Pruning Techniques for Shortest Path Tree Computation[END_REF]. The Shortest Path Tree is then constructed over the set of adjacencies.

INRIA 3 Testbed Description

This section describes the characteristics of the employed networking testbed. Section 3.1 presents the distribution of computers in the testbed and the network topology that they form. Section 3.2 details the implications of such topology in OSPF routing.

Interfaces Configuration and Network Topology

The testbed is composed of 6 fixed computers (routers/hosts) attached to two interconnected networks: a wired network and a wireless network. Table 1: Network interfaces of testbed computers.

Physical Topology

The internetwork connecting these computers was deployed in the Computer Science Lab (Laboratoire d'Informatique, LIX) of École Polytechnique, in Paris (France). Three scenarios -I, II and III-were configured over the resulting internetwork. These scenarios permit to test the communication between computers wless3 and server, for different situations. The physical distribution of computers at LIX is displayed in Figure 1.

Logical Internetwork Topology

Each scenario corresponds to a specific internetwork topology. Figure 2 indicates the internetwork topology graphs for scenarios I, II and III. In the wired network, computers communicate through the IEEE 802.3 (Ethernet) standard protocol, server is connected with hybrid1 by way of interface eth0 and with hybrid2 by way of interface eth1, as shown in Figure 2. In the wireless network, interfaces communicate through the IEEE 802.11b WLAN standard protocol, and all wireless routers (hybrid1, hybrid2, wless1, wless2 and wless3) use their wireless interface wlan0. The topology that results from wireless reachability among computers hybrid1, hybrid2, wless1, wless2 and wless3 is modified by means of MAC filtering in order to disable links h 1 ←→ h 2 , w 1,3 ←→ w 2 , w 1,3 ←→ h 2 and w 2 ←→ h 1 , as well as h 1 ←→ w 1 for scenario III.

OSPF Routing Configuration

All interfaces use the extended OSPFv3 routing protocol, wired and wireless interfaces using different interface types. Wired interfaces are configured as point-to-point interfaces, as they are specified in RFCs 2328 [START_REF] Moy | RFC 2328, OSPF Version 2, IETF[END_REF] and 5340 [START_REF] Coltun | RFC 5340, OSPF for IPv6[END_REF]. Wireless interfaces are configured as MANET interfaces, as specified in the MPR-OSPF MANET extension for OSPF (RFC 5449 [START_REF] Baccelli | RFC 5449, OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF]).

OSPF Adjacencies and MPRs

According to the specification of OSPF and MPR-OSPF extension, all links in any of the considered topologies for scenarios I, II and III are adjacent. Within the wired network, every point-to-point link is an adjacency. In the wireless It can be observed that all links are MPR links, and therefore all are adjacent. In this topology, the presence of a synch router (see section 2.3) is thus redundant.

OSPF Flooding

Flooding in the wired network is performed through adjacent links -that means, S ←→ h 1 and S ←→ h 2 . In the wireless network, flooding is performed:

❼ through the MPR links (from a wireless router towards its MPR), and ❼ through all links connecting an interface to a hybrid router (hybrid1 and hybrid2).

Experiments and Results

For each scenario (I, II and III), communication between wless3 and server is tested by way of two experiments. Displayed results show the averaged measures over tens of samples (see Appendices A.3 and A.4 for further details on configuration of the experiments):

❼ Transmission of ICMPv6 1 requests (pings) from wless3 to server. The measure of time between the transmission of an ICMP request and its reply corresponds to the Round Trip Time (RTT) of the ping through the evaluated path.

❼ Transmission of a constant bit rate data UDP flow from wless3 to server.

Comparison between packets sent and packets received permits to test the quality of the traversed paths and the wireless links that compose them in each scenario. Characteristics of these UDP flows are summarized in Table 3. 1 Internet Control Messaging Protocol for IPv6, RFC 4443 [START_REF] Conta | RFC 4443, Internet Control Message Protocol (ICMPv6) for the Internet Protocol Version 6 (IPv6) Specification, IETF[END_REF].

RR n➦ 7642

The three considered scenarios are complemented by another scenario in which information is transmitted and measured through the wired link h 1 ←→ S. Results on this scenario are added for completeness and reference. Section 4.1 presents the results obtained in both experiments, for each scenario, in terms of quality of wireless links. Section 4.2 examines the amount and structure of control traffic used in OSPF for enabling routing of packets within the internetwork. nication between routers wless3 and server as the number of wireless links between them increases. As expected, the wired link h 1 ←→ S has an almostideal behavior: 100% PDR and no significant delay. The negative impact of wireless links in the path from source to destination is close-to-linear with the number of traversed wireless links, as shown in Figure 3.a: more than 30% of transmitted packets are lost in the first wireless link, and such percentage increases about a 15% per additional wireless link included in the path. Figure 3.b shows that such degradation is also evident in terms of round trip time (RTT).

Wireless Multi-hop Communication

INRIA

Replies to ICMP requests are immediately delivered through a wired link, but the average and the variation of delays grow with the number of wireless links involved -is in the order of tens of miliseconds for 2 and 3 wireless links.

While the impact on communication due to the use of wireless links depends on the specific topology and the network technology that is used, two conclusions can be drawn from these experimental results. As each additional wireless hop in the route of data packets in the network implies a significant degradation of the quality of communication, routing in wireless networks should preserve the principle of shortest (wireless) paths, meaning that the number of wireless links traversed by data packets should be minimized. This confirms the conclusions of simulation-based studies such as [START_REF] Baccelli | OSPF over Multi-Hop Ad Hc Wireless Communications[END_REF] which highlights the importance of not sacrificing path optimality for less control traffic.

Moreover, in the context of compound internetworks with both wired and wireless links, it is obvious that 'optimal' does not necessarily mean 'the least number of hops', as implicitly used in previous work such as [START_REF] Baccelli | Multi-Point Relaying Techniques with OSPF on Ad Hoc Networks[END_REF][START_REF] Henderson | Evaluation of OSPF MANET Extensions[END_REF][START_REF] Cordero | MPR+SP -Towards a Unified MPR-based MANET Extension for OSPF[END_REF][START_REF] Baccelli | Optimization of Critical Data Synchronization via Link Overlay RNG in Mobile Ad Hoc Networks[END_REF]. Indeed, in compound internetworks, it is better for a path to use wired links than wireless links, whenever possible, even if it means more hops in the end. This observation confirms that metrics used should indeed be able to track link quality, and that OSPF sepcifications such as [START_REF] Baccelli | RFC 5449, OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF] [5] [START_REF] Ogier | RFC 5614, Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding[END_REF] should be completed with a standard way to do that in MANETs.

OSPF Control Traffic Pattern

RR n➦ 7642

Figures 4, 5, 6 and 7 display the evolution of OSPF control traffic transmitted by wireless interfaces wless3:wlan0 and hybrid1:wlan0, on one side, and wired interfaces hybrid1:eth0 and server:eth0, on the other. The five packet formats used in OSPF (Hello, LSUpdate, LSRequest, LSAck and DBDesc, see section 2.1) can be distinguished in these figures. Measures were taken with the topology of scenario I, each point corresponding to the number of packets or bytes sent within an interval of 5 seconds. The traffic load of the internetwork was composed of a CBR UDP data traffic flow from wless3 towards server (see Table 3 for details), and OSPF control traffic. The figures show the structure of such control traffic, both in terms of number of packets and number of bytes, during the first 335 seconds of network operation, i.e., after routers' startup. All interfaces are configured with the same OSPF parameters, in order to facilitate the comparison between control traffic patterns of each of them. See Appendix A.4 for further details. For the same number of neighbors, Hellos from hybrid1:eth0 have 40 bytes while those from hybrid1:wlan0 have 75.34 bytes. This is due to the INRIA fact that Hello packet format in RFC 5449 [START_REF] Baccelli | RFC 5449, OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF] includes additional information about link costs, adjacencies and MPR selection, which is added to the format specified in OSPF [START_REF] Moy | RFC 2328, OSPF Version 2, IETF[END_REF] and OSPFv3 [START_REF] Coltun | RFC 5340, OSPF for IPv6[END_REF]. The existence of ongoing LSDB synchronization processes during the monitored time interval can be noticed in the OSPF control traffic structure by way of the presence of Database Description (DBDesc) packets. The fact that such packets are only present, for wired interfaces, in the first part of the monitored interval (from t = 0sec to t = 10sec, as shown in Figures 4 and6) indicates that links become synchronized only when the routers are switched on. In contrast, DBDesc are transmitted in the whole monitored interval for wireless interfaces. This is consistent with the fact that wired links are mostly stable and therefore there is no need to repeat synchronization process after the first LSDB exchange. Wireless links, in contrast, are more prone to packet losses and link failures, and need thus to be synchronized several times during the network lifetime, even in the absence of router mobility. The same phenomenon can be observed with LSRequest packets, which can only be sent during the last phase of the LSDB synchronization process, when the synchronizing neighbors have completed the exchange of DBDesc packets. These observations are also consistent with simulation-based studies such as [START_REF] Baccelli | OSPF over Multi-Hop Ad Hc Wireless Communications[END_REF] which have studied the impact of link quality on OSPF control traffic. LSUpdate packets contain one or more Link State Advertisements (LSAs). Such LSAs can be either originated by the sending interface, either originated by another interface and flooded (forwarded) by the sending interface. Transmission of LSUpdate packets follows a common pattern in all the interfaces in the internetwork. Thus pattern consists of periodic peaks followed by time intervals (valleys) in which the number and size of LSUpdate transmissions is lower and roughly constant.

LSDB Synchronization

The time interval between two consecutive peaks corresponds to the value of parameter LSRef resh, set to 60sec for all interfaces. This is the time interval at which an interface floods its topology description (periodically) if there are no topology changes in the meanwhile.

Despite the common pattern in the LSUpdate traffic, several differences can be observed between wired and wireless interfaces. This section concentrates on three particular aspects: peak width, height of valleys between consecutive peaks and transient state (after routers are switched on). for hybrid1:eth0) is followed by a steady period in which the minimum LSUpdate rate is slightly higher (about 30Bps = 150B 5sec for hybrid1:eth0). These different behaviors can be explained by the different roles that flooding has over wired and wireless links. Due to their stability, packets sent over wired links are mostly forwarded packets -that is, they come from other interfaces than those involved in the links. In the first instants in which there is no flooding over the network because adjacencies have not been formed in the network and flooding links have not yet been identified, the overall traffic traversing such wired links is temporarily low. The opposite is observed in wireless links. ❼ Peak width. Peaks are narrower in wired interfaces (∼ 10sec for server:eth1, ∼ 15sec for hybrid1:eth0) than in wireless interfaces (∼ 25sec for hybrid1:wlan0, ∼ 30sec for wless3:wlan0). For interfaces attached to wireless links, there is a high probability that a topology change causes a new topology update before the LSRef resh interval -therefore, intervals between consecutive transmission of interfaces' topology descriptions are shorter than LSRef resh and the width of the peak increases. In stable wired links, in contrast, intervals between consecutive transmissions are closer to the LSRef resh parameter and, therefore, LSUpdate transmission events are less spread in time.

❼ Height of valleys. Besides the peaks caused by transmission of its own topology description, either periodic or as a reaction to a topology change, two other events may lead an interface to transmit Link State Advertisements (LSAs): (i) forwarding of LSAs originated by other interfaces in the internetwork, and (ii) retransmission of LSAs not acknowledged by their intended destinations. Both additional events explain the presence of valleys with significant traffic rate, i.e., a non-zero minimum level of LSUpdate transmissions in the monitored interfaces. In wired (reliable) links such as server:eth1 and hybrid1:eth0, such transmissions are caused by flooding, and involve about 25Bps (127B per interval of 5sec). Wireless interfaces such as wless3:wlan0 have a minimum LSUpdate transmission rate of about 16Bps (80B per interval of 5sec) caused by LSA retransmissions and flooding.

Conclusion

Results from the experiments carried out on the testbed confirm the effect of the presence of wireless links in an OSPF network, confirming prior simulationbased studies concerning control traffic composition. Analysis of OSPF control traffic over the wireless network reveals that even with a very small number of neighbors per wireless interface and static routers, link synchronization processes may involve a continuous and substantial amount of traffic. Reduction of the number of synchronized links is, therefore, essential when using OSPF over ad hoc networks.

Degradation of data communication due to wireless links implies that suboptimal data paths should be avoided in routing on ad hoc networks, as the quality of resulting communication decreases substantially with each additional wireless hop. For internetworks combining wired and wireless networks, wired links should be preferred to wireless links when possible. A standard way to track link quality in compound internetworks is thus necessary in order to complete current OSPF specifications for operation on MANETs. The presented results also point out the importance of leveraging every possible wired connection in the compound AS, which advocates for the use of a single routing protocol in the AS. By using a single protocol, indeed, wired links would be natively included in path computation, without requiring the use of mandatory gateways between different routing domains, which may lead to suboptimal paths (and additional hardware, software and maintenance costs for these gateways).

INRIA

Figure 1 :

 1 Figure 1: Computers position over the plan of LIX. Positions of computers do not change, except for the case of wless3, which has a different position for scenario I and for scenarios II and III, as shown in Figure 1.

Figure 2 :

 2 Figure 2: Considered topologies for scenarios I, II and III.

Figures 3 .Figure 3 :

 33 Figures 3.a and 3.b display the results of the performed experiments, in particular the delay for ICMP requests (pings) and the packet delivery ratio of CBR UDP data flows.

Figure 4 :

 4 Figure 4: Control traffic overhead at server:eth1.

Figure 5 :

 5 Figure 5: Control traffic overhead at wless3:wlan0.

Figure 6 :

 6 Figure 6: Control traffic overhead at hybrid1:eth1.

Figure 7 :

 7 Figure 7: Control traffic overhead at hybrid1:wlan0.

❼

  Transient state. Immediately after switching on, wireless interfaces transmit a high number of packets -mostly, LSUpdate packets sent in response to LSRequest packets received during the first LSDB synchronization processes in all wireless links (Figures 7.a and 5.a, between t = 0sec and t = 50sec). This amount of transmissions involves traffic rates above INRIA 220Bps (1.1kB per interval of 5sec), then decreases and stabilizes in a slightly lower level (maximum peak of 130Bps). The opposite behavior is found in wired interfaces (Figures 4.a and 6.a), in which the initial transient period of low LSUpdate traffic rate (about 26Bps = 130B 5sec

  Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Paper Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 The OSPF Protocol and its MANET Extension 2.1 Packet Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Interface Types for Wired Links . . . . . . . . . . . . . . . . . . . 2.3 MANET Interface Type . . . . . . . . . . . . . . . . . . . . . . . Interfaces Configuration and Network Topology . . . . . . . . . . 3.1.1 Physical Topology . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Logical Internetwork Topology . . . . . . . . . . . . . . . 3.2 OSPF Routing Configuration . . . . . . . . . . . . . . . . . . . .

	1 Introduction
	1.1 3 Testbed Description
	3.1

3.2.1 OSPF Adjacencies and MPRs . . . . . . . . . . . . . . . . 3.2.2 OSPF Flooding . . . . . . . . . . . . . . . . . . . . . . . . 4 Experiments and Results 4.1 Wireless Multi-hop Communication . . . . . . . . . . . . . . . . . 4.2 OSPF Control Traffic Pattern . . . . . . . . . . . . . . . . . . . . 4.2.1 Hello Packets . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 LSDB Synchronization . . . . . . . . . . . . . . . . . . . . 4.2.3 Link State Updates, Requests and Acknowledgements . . 5 Conclusion A APPENDIX A.1 Testbed Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Testbed Software . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Setup for PDR and RTT Measures . . . . . . . . . . . . . . . . . A.4 Setup for Control Traffic Measures . . . . . . . . . . . . . . . . . A.5 OSPF Parameters . . . . . . . . . . . . . . . . . . . . . . . . . .

  Table 1 indicates the network interfaces of each computer. For more details about computers' hardware, see Appendix A.1.

	Computer	Abbr. Wired ifs. Wireless ifs.
	server	S	eth0, eth1	-
	hybrid1	h1	eth0	wlan0
	hybrid2	h2	eth0	wlan0
	wless1	w1	-	wlan0
	wless2	w2	-	wlan0
	wless3	w3	-	wlan0

  INRIAnetwork, wireless links are adjacent if they are MPR links. The list of MPRs of every wireless interface, for each scenario, is displayed in Table2.

	Interface	I	II	III
	hybrid1:wlan0	w1 w1	-
	hybrid2:wlan0	w2 w2 w2
	wless1:wlan0	-	w2 w2
	wless2:wlan0	w3 w1 w1
	wless3:wlan0	w2 w1 w1

Table 2 :

 2 MPRs selected by each wireless interface, for each scenario.

Table 3 :

 3 Characteristics of transmitted UDP flows.

RR n➦ 7642

A.2 Testbed Software

Software used in all computers was as follows:

❼ Operating System: Ubuntu v.10.04 with kernel 2.6.32.

❼ Routing Protocol Implementation: ospf6d daemon of Quagga/Zebra routing suite v.0.99.15.

-Wired interfaces: Point-to-point.

-Wireless interfaces: MANET, as specified in RFC 5449 [START_REF] Baccelli | RFC 5449, OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks[END_REF].

A.3 Setup for PDR and RTT Measures

❼ Routers were switched on between t = 0sec and t = 2sec.

❼ PDR results averaged over 84 iterations.

❼ ospf6d daemon NOT restarted in each iteration.

❼ UDP flows, started 60sec after ospf6d daemon switch-on:

A.4 Setup for Control Traffic Measures

❼ Routers were switched on between t = 0sec and t = 2sec.

❼ Results averaged over 84 iterations.

❼ ospf6d daemon restarted in each iteration.

❼ UDP flows: see Table 4.

A.5 OSPF Parameters

RR n➦ 7642


Jalal M Fadili
email: jalal.fadili@greyc.ensicaen.fr

François Lecellier
email: francois.lecellier@univ-poitiers.fr

Stéphanie Jehan-Besson

Multiscale transforms for region-based texture segmentation

HAL is

INTRODUCTION

Texture segmentation remains a difficult and challenging task, and an intense research field. Indeed, the main bottleneck to segment a texture image is to find an appropriate set of generic computable descriptors to characterize a given texture and discriminate distinct textures between them. Representing and characterizing textures remains an important open problem, mainly because there is no consensus on how to define a texture model, despite several attempts including random models in spatial or transform domains, low-dimensional manifold models, or sparsity-oriented models; see [START_REF] Peyré | Sparse modeling of textures[END_REF] for an review. There is also number of papers devoted to the segmentation of textured images; a comprehensive overview can be found e.g. in [START_REF] Lecellier | Les contours actifs basés région avec a priori de bruit, de texture et de forme : Application à l'échocardiographie[END_REF]. Some of them attacked the problem of segmenting or classifying textures using the wavelet machinery as texture descriptors [START_REF] Unser | Texture classification and segmentation using wavelet frames[END_REF][START_REF] Do | Wavelet-based texture retrieval using generalized gaussian density and kullback-leibler distance[END_REF][START_REF] Aujol | Wavelet-based level set evolution for classification of textured images[END_REF][START_REF] Corpetti | An active contour method based onwavelet for texture boundaries[END_REF]. In this paper, we tackle the texture segmentation This work was accomplished when the second and third authors were hosted in the first institution.

problem under the umbrella of transform domain models such as, but not limited to, wavelets, and variational region-based active contours (RBAC). More precisely, we propose a general texture segmentation framework that discriminates textures by measuring a divergence between the non-parametric density estimates of the PDFs of their respective transform coefficients. The framework is adapted to both supervised and unsupervised segmentation of textured images. In the supervised case (Section 3.1.1), we consider the minimization of the divergence between the coefficients PDF of a reference exemplar texture, and that of the texture to segment. In the unsupervised case (Section 3.1.2), we maximize this divergence between the coefficients PDFs. Region-based active contours and shape derivatives In variational image segmentation, the general energy functional to be optimized is composed of region and contour terms. For the sake of simplicity, we will focus in the sequel on the 2D case.

Let Ω I , an open bounded subset of R 2 , be the domain of the image. Image segmentation can then be cast as obtaining a disjoint minimal partition of

Ω I in K ≥ 2 regions min {Ω k } K k=1 ∪ K k=1 Ω k ∪∂Ω=ΩI F (Ω 1 , • • • , Ω K , ∂Ω) = K k=1 Ω k F k (x; Ω k ) dx + ∂Ω F b (x) ds(x) , (1)
where F k is the region descriptor attached to the open bounded and regular domain/region Ω k , ∂Ω is the boundary of the regions, and s(x) is the curvilinear abscissa. Each descriptor F k can be thought of as a homogeneity criterion, where homogeneity is to be understood in a broad sense. The contour integral term corresponds to a local information, and can be used as a regularization on ∂Ω. Typically, this term can be the length of the contour (as a curve) in 2D in which case F b (x) = λ, a positive constant that plays the role of a regularization parameter.

Once the optimization problem has been formulated, it remains now to solve it with respect to the domains {Ω k } k=1,••• ,K , by deriving a geometrical evolution PDE that would drive the contour to a stationary point of the minimized energy functional, which may happen to be a local minimum of interest. However, the set of domains in R d does not have the structure of a vector space, and classical descent algorithms do not qual-ify straightforwardly for this problem. Throughout this work, to exhibit such a PDE, we will focus on shape derivative tools.

To cut a long story short, shape derivative tools consist in considering that the domain evolves in a velocity field V, and the derivative of a domain functional F r (Ω) := Ω F (x; Ω) dx is computed in the direction V. This is summarized in the following result.

Theorem 1 ([4, 6])

The Eulerian derivative of the domain functional F r (Ω) in the direction V is given by

< F ′ r (Ω), V >= Ω F ′ (x; Ω, V) dx - ∂Ω F (x; Ω) V, N da(x),
where N is the inward unitary normal to ∂Ω, da(x) the area element, and F ′ (x; Ω, V) is the domain derivative of F (x; Ω) in the direction V:

F ′ (x; Ω, V) = lim τ →0 F (x; Ω(τ )) -F (x; Ω) τ .
With this derivative at hand, the evolution PDE of the active contour Γ (τ ) is given by

∂Γ ∂τ = speed(x; Ω) • N , Γ (τ = 0) = Γ 0 , (2)
if one is able to re-express the Eulerian derivative of F r (Ω) as

< F ′ r (Ω), V >= - ∂Ω speed(x; Ω) V, N da(x) . (3)

TEXTURE DESCRIPTORS

Sparsity in fixed or learned dictionaries has been successfully used for texture synthesis and also for texture segmentation and classification. For these tasks, most fixed dictionaries can be viewed as a cascade of filter banks. These filter banks are built in order to discriminate between the textures depending on their frequency response. However, many of these methods are designed to a particular choice of the transform. On the other hand, this choice will obviously not be adapted for a variety of textures. For instance, it has been known for some time now that some transforms can entail reasonably sparse expansions of certain textures; e.g. locally oscillatory textures in bases such as local discrete cosines [START_REF] Starck | Redundant multiscale transforms and their application for morphological component analysis[END_REF], brushlets [START_REF] Meyer | Brushlets: a tool for directional image analysis and image compression[END_REF], Gabor [START_REF] Mallat | A Wavelet tour of signal processing[END_REF], wave-atoms [START_REF] Ying | Wave atoms and sparsity of oscillatory patterns[END_REF]. Gabor and dyadic traditional wavelets are widely used in the image processing community for texture analysis. Their use may be motivated by physiological evidence where simple cells of the primary visual cortex exhibit Gabor-like responses. But little is known on the decay, hence the approximation behavior, of wavelet coefficients of textures in general. In fact, sparsely representing realistic models of textures remains an open problem.

Our goal here is to segment textures in images without confining ourselves to a specific representation to characterize them, nor necessarily relying on the sparsity of the transform coefficients (see Section 3.1.1). Thus, our framework is flexible enough to handle virtually any transform which is able to discriminate the targeted textures. For good success of the segmentation, such a transform should satisfy three major requirements: (i) to be multiscale; (ii) translation invariant; and (iii) to enjoy directional selectivity. Note that multiscale and translation invariance are reminiscent of the axioms of random generative models popular in statistical modeling of natural images.

We denote by α γ = f, ϕ γ the coefficients of a texture f in a dictionary of atoms {ϕ γ }, where γ = (j, θ j , x), j ≥ 0 is the scale, θ j ∈ [0, 2π[ the subband/orientation parameter at scale j, and x = (x 1 , x 2 ) the position. For instance, for the TI-wavelet transform, γ is: j ∈ {0, . . . , J -1} and θ j ∈ {0, π/4, π/2} for all j. For wave-atoms: j ∈ {0, . . . , ⌈ J-1 2 ⌉ + 1} and θ j is implicit in j such that ν j,m = ±πm2 j ∼ 2 2j , where ν j,m is the central frequency of the wave-atom, m = (m 1 , m 2 ), (m 1 , m 2 ) is a pair of integers such that max i=1,2 m i ∼ 2 j . This relation between the central frequency and the support size of the waveatom is behind a parabolic scaling law which entails that waveatoms provide optimally sparse representation of locally warped oscillatory patterns [START_REF] Ying | Wave atoms and sparsity of oscillatory patterns[END_REF].

PDF-BASED TEXTURE SEGMENTATION

Hitherto, we have advocated the use of transform coefficients as discriminative descriptors to reveal the differences between different textures depending on their spectral and geometrical contents. Once the transform has been identified, it remains now to compare these texture descriptors (coefficients), and we here propose to use a divergence between their respective PDFs. Under stationarity hypothesis in each subband (j, θ j ), the proposed domain functional to be optimized reads:

F j,θj (Ω) = X D pdf 1 j,θj (α; Ω) , pdf 2 j,θj (α; Ω) dα , (4)
where D : R + × R + → R + is some metric comparing two PDFs pdf 1 j,θj and pdf 2 j,θj . Typical choices of D including the Hellinger distance, the χ 2 -score, or the Kullback-Leibler divergence (KLD) or its symmetrized version (which is in fact a distance), etc. Summing (4) over scales and subbands, segmenting a texture amounts to optimizing the following domain functional:

F (Ω) = j,θj F j,θj (Ω) . (5)

Supervised segmentation

Supervised segmentation means that an exemplar texture is available to serve as a reference and for which the coefficients PDF at all subbands are known a priori. Given a new candidate image containing a similar texture, the goal is to segment it. In the notation of (4), one of the PDFs (e.g. pdf 2 j,θj ) would be that of the exemplar pdf ref j,θj , which obviously does not depend on Ω.

Parametric approach

The path undertaken here strongly relies on the sparsity of the texture representation coefficients at all scales and subbands in the domain of the chosen transform. If such a hypothesis holds true, then a good candidate sparsity-promoting prior PDF would be the generalized Gaussian distribution (GGD) family. With the symmetrized KLD, (5) becomes:

F (Ω) = j,θj σ ref j,θj σ j,θj (Ω) p j,θ j (Ω) Γ 1+p j,θ j (Ω) p ref j,θ j Γ 1 p ref j,θ j + σ j,θj (Ω) σ ref j,θj p ref j,θ j Γ 1+p ref j,θ j p j,θ j (Ω) Γ 1 p j,θ j (Ω) - 1 p j,θj (Ω) - 1 p ref j,θj , (6)
where p j,θj (Ω) and σ j,θj (Ω) are the shape and scale parameters of GGD distribution at each scale and subband, Γ(z) is the Gamma function. These parameters are estimated in each region during the contour evolution, hence their dependence on the domain Ω. Using a moment estimators yields:

p MO j,θj (Ω) = h -1    M (1) j,θj (Ω) 2 M (2) j,θj (Ω)    , (7)
σ MO j,θj (Ω) = M (1) j,θj (Ω)Γ 1 p MO j,θ j (Ω) Γ 2 p MO j,θ j (Ω) , (8)
where

h(p) = Γ 2 ( 2 p ) Γ( 1 p )Γ( 3 p )
, and

M (i) j,θj (Ω) := 1 |Ω| Ω α j,θj ,x i dx
is the absolute empirical moment of order i. Beyond existence and uniqueness issues of these estimators1 , their implicit form makes the derivation of the evolution PDE through the Eulerian derivative of F (Ω) (see Theorem 1) cumbersome. Furthermore, such an approach is strongly sensitive to the sparsity/compressibility assumption which may be violated for some textures. To mitigate these limitations, we now move to the much more versatile non-parametric approach.

Non-parametric approach

Kernel density estimators Given a collection of observed coefficient samples, supposed to be independent and identically distributed, this approach will first estimate the underlying PDF using the well-known kernel density estimator. Let K ς a positive kernel of unit mass and bandwidth ς. The kernel density estimator of pdf 1 j,θj in ( 4) is defined as

pdf 1 j,θj (α; Ω) = 1 |Ω| Ω K ς α j,θj ,x -α dx . (9)
Typical choices of K ς are the Gaussian kernel (Parzen) and the Epanechnikov kernel. The choice of ς is even more crucial and results from a traditional bias-variance tradeoff. If the PDF is uniformly bounded and C s+1 , it is wellknown that the rate of the quadratic risk of the kernel estimator scales as O |Ω| -2s/(2s+1)

with the optimal choice ς opt ≍ |Ω| -1/(2s+1) . Typically, for s = 2, the quadratic risk is O(|Ω| -4/5 ) which is much better that the histogram optimal risk O(|Ω| -2/3 ). Evolution speed Suppose the goal is to segment two textures in an image, where we have an exemplar for each. In the language of RBAC, and from (4), this segmentation task boils down to a two region partition problem by minimizing the following functional with respect to the inside and outside regions Ω in and Ω out :

G(Ωin, Ωout) = X j,θ j " |Ωin| Z X D " pdf in j,θ j (α; Ωin) , pdf ref,in j,θ j (α) " dα | {z } F j,θ j (Ω in ) + |Ωout| Z X D " pdf out j,θ j (α; Ωout) , pdf ref,out j,θ j (α)
" dα

| {z } F j,θ j (Ω out )
" .

(1 where pdf in j,θj and pdf out j,θj are the kernel density estimates as given by [START_REF] Meyer | Brushlets: a tool for directional image analysis and image compression[END_REF]. Using shape derivative tools, as in [START_REF] Aubert | Image segmentation using active conturs : Calculus of variations or shape gradients[END_REF], the following result can be established, see [START_REF] Lecellier | Les contours actifs basés région avec a priori de bruit, de texture et de forme : Application à l'échocardiographie[END_REF] for the proof.

Theorem 2

The PDE evolution of the active contour Γ (τ ) corresponding to [START_REF] Peyré | Sparse modeling of textures[END_REF] is:

∂Γ ∂τ = X j,θ j " F j,θ j (Ωin) -F j,θ j (Ωout) + C j,θ j (Ωout) -C j,θ j (Ωin) + ``V j,θ j (•; Ωin) -V j,θ j (•; Ωout) ´ * Kς ´(α j,θ j ,x ) " N , ( 11
)
where V j,θ j (α; Ωi) = ∂1D " pdf i j,θ j (α; Ωi), pdf ref,i j,θ j (α)

" , C j,θ j (Ωi) = R X V j,θ j (α; Ωi) pdf i j,θ j (α; Ωi) dα , ∂ 1 D(., .) is the partial derivative of D(., .) with respect to its first argument, and N is the unit normal to the contour.

Explicit expressions of C j,θj and V j,θj for specific choices of D including the KLD and the Hellinger distance are given in [START_REF] Lecellier | Les contours actifs basés région avec a priori de bruit, de texture et de forme : Application à l'échocardiographie[END_REF]. They are omitted here for obvious space limitations.

Unsupervised segmentation and region competition

When no exemplar textures are available, it appears natural to make the regions compete. This leads to a maximization problem of the form:

G(Ωin, Ωout) = X j,θ j Z X D "
pdf in j,θ j (α; Ωin) , pdf out j,θ j (α; Ωout) " dα, [START_REF] Unser | Texture classification and segmentation using wavelet frames[END_REF] where pdf in j,θj (α; Ω in ) and pdf out j,θj (α; Ω out ) are the kernel density estimates as given by [START_REF] Meyer | Brushlets: a tool for directional image analysis and image compression[END_REF]. In plain words, maximizing this functional will seek the partition in which the coefficients PDFs in the inside and outside regions are the most distinct. 12) is given by the following result, see the proof in [START_REF] Lecellier | Les contours actifs basés région avec a priori de bruit, de texture et de forme : Application à l'échocardiographie[END_REF].

Theorem 3

The PDE evolution of the active contour Γ (τ ) to maximize [START_REF] Unser | Texture classification and segmentation using wavelet frames[END_REF] is:

∂Γ ∂τ = X j,θ j " 1 |Ωin| `-`Vj,θ j (•; Ωin) * Kς ´(α j,θ j ,x ) + C j,θ j (Ωin) + 1 |Ωout| ``V j,θ j (•; Ωout) * Kς ´(α j,θ j ,x ) -C j,θ j (Ωout) ´"N , (13)
V j,θ j (α; Ωin) = ∂1D " pdf in j,θ j (α, Ωin), pdf out j,θ j (α, Ωout)

" , V j,θ j (α; Ωout) = ∂2D " pdf in j,θ j (α, Ωin), pdf out j,θ j (α, Ωout) " , C j,θ j (Ωin) = Z X V j,θ j (α; Ωin) pdf in j,θ j (α; Ωin) dα, C j,θ j (Ωout) = Z X V j,θ j (α; Ωout) pdf out j,θ j (α; Ωout) dα .

EXPERIMENTAL RESULTS AND DISCUSSION

Fig. 1 displays some examples of non-parametric texture segmentation with two transforms (separable wavelets and waveatoms) and the supervised and unsupervised approaches. The minimized functional was [START_REF] Aubert | Image segmentation using active conturs : Calculus of variations or shape gradients[END_REF]. Beside the speeds provided by Theorem 2 and 3, the active contour evolution speed included an additional curvature term corresponding to the regularization in [START_REF] Aubert | Image segmentation using active conturs : Calculus of variations or shape gradients[END_REF]. In all the experiments, D was the KLD and K ς is the Gaussian kernel with a bandwith chosen according to the above discussion. The synthetic images were generated by randomly combining textures from the Brodatz database. The evolution PDE was implicitly implemented with the level-sets method.

Overall, the results are very good. In general, wave-atoms were able to segment more complex textures than separable wavelets owing to their directional selectivity. As expected, wavelets are well adapted whenever the texture is an oscillatory pattern mainly oriented vertically, horizontally or diagonally. With such textures, unsupervised segmentation (texture competition) can be successfully applied to an image with even more than two textures, or one texture and one cartoon part as soon as the oriented texture can be clearly distinguished from the other parts of the image. This is clearly confirmed by the results on real images.

  (a) Synthetic images: Supervised (wave-atoms). (b) Synthetic images: Supervised (wavelets). (c) Synthetic images: Unsupervised (wave-atoms). (d) Synthetic images: Unsupervised (wavelets).(e) Real images: Unsupervised (wavelets and waveatoms).

Fig. 1 .

 1 Fig. 1. Non parametric texture segmentation examples with different transforms. (a)-(d): synthetic images from the Brodatz database. (e): natural images

It can be shown that p MO exists if and only if M[START_REF] Aubert | Image segmentation using active conturs : Calculus of variations or shape gradients[END_REF]

M (2) <

3/4, in which case the solution to (7) is also unique.