Matthieu Boutier

Juliusz Chroboczek

Source-specific routing

Source-specific routing (not to be confused with source routing) is a routing technique where routing decisions depend on both the source and the destination address of a packet. Source-specific routing solves some difficult problems related to multihoming, notably in edge networks, and is therefore a useful addition to the multihoming toolbox. In this paper, we describe the semantics of source-specific packet forwarding, and describe the design and implementation of a source-specific extension to the Babel routing protocol as well as its implementation -to our knowledge, the first complete implementation of a sourcespecific dynamic routing protocol -, including a disambiguation algorithm that makes our implementation work over widely available networking APIs. We further discuss interoperability between ordinary next-hop and source-specific dynamic routing protocols. Our implementation has seen a moderate amount of deployment, notably as a testbed for the IETF Homenet working group.

I. INTRODUCTION

The routing paradigm deployed on the Internet is next-hop routing. In next-hop routing, per-packet forwarding decisions are performed by examining a packet's destination address only, and mapping it to a next-hop router. Next-hop routing is a simple, well understood paradigm that works satisfactorily in a large number of cases.

The use of next-hop routing restricts the flexibility of the routing system in two ways. First, since a router only controls the next hop, a route A • B • C • • • Z can only be selected by the router A if its suffix B • C • • • Z has already been selected by a neighbouring router B, which makes some forms of optimisation difficult or impossible. Other routing paradigms, such as circuit switching, label switching and source routing, do not have this limitation. (Source routing, in particular, has been proposed multiple times as a suitable routing paradigm for the Internet [START_REF] Saltzer | Source routing for campus-wide internet transport[END_REF], but has been discouraged due to claimed security reasons [START_REF] Abley | Deprecation of Type 0 Routing Headers in IPv6[END_REF]).

Second, the only decision criterion used by a router is the destination address: two packets with the same destination are always routed in the same manner. Yet, there are other data in the IP header that can reasonably be used for making a routing decision -the TOS octet, the IPv6 flow-id, and, of course, the source address.

We call source-specific routing the modest extension of classical next-hop routing where the forwarding decision is allowed to take into account the source of a packet in addition to its destination. Source-specific routing gives a modest amount of control over routing to the sending host, which can choose among different routes by picking different source addresses. The higher layers (transport or application) are therefore able to choose a route using standard networking APIs (collecting the host's local addresses and binding a socket to a specific address). Unlike source routing, however, sourcespecific routing remains a hop-by-hop mechanism, and therefore leaves local forwarding decisions firmly in the control of the routers.

Two things are needed in order to make source-specific routing practical: a forwarding mechanism that can discriminate on both source and destination addresses, and a dynamic routing protocol that is able to distribute source-specific routes. In this paper, we describe our experiences with the design and implementation of a source-specific extension to the Babel routing protocol [START_REF] Chroboczek | The Babel Routing Protocol[END_REF], including a disambiguation algorithm that allows implementing source-specific routing over existing forwarding mechanisms.

II. APPLICATIONS

The main application of source-specific routing is the implementation of multihoming.

A. Classical multihoming

A multihomed network is one that is connected to the Internet through two or more physical links. This is usually done in order to improve a network's fault tolerance, but can also be done in order to improve throughput or reduce cost.

Classically, multihoming is performed by assigning Provider-Independent addresses to the multihomed network and announcing them globally (in the Default-Free Zone (DFZ)) over the routing protocol. The dynamic nature of the routing protocol automatically provides for fault-tolerance; improvements in throughput and reductions in cost can be achieved by careful engineering of the routing protocol.

While classical multihoming works reasonably well in the network core, it does not apply to the edge. In order to perform classical multihoming, a network needs to be allocated a "Provider-Independent" prefix that is reannounced by some or all of a network's peers. This setup is usually impossible to achieve for home and small business networks.

Note that it is not in general possible to implement classical multihoming using a single "Provider-Dependent" prefix. If a network is connected to two providers A and B, a packet with a source address in an address range allocated to A will usually not be accepted by B, which will treat it as a packet with a spoofed source address and discard it [START_REF] Ferguson | Network Ingress Filtering: Defeating Denial of Service Attacks which employ IP Source Address Spoofing[END_REF]. What is more, A's prefix will not be reannounced by B, and hence destinations in A's prefix will not be reachable over the link to B.

There is some concern that classical multihoming, even when restricted to the large networks of the core, is causing uncontrolled growth of the "default-free routing table". Since we have only experimented with source-specific routing in edge networks, we hold no opinion on the usefulness of our techniques in the network core, and in particular on the desirability of adding it to the BGP external routing protocol.

B. Multihoming with multiple source addresses

Since announcing the same Provider-Dependent (PD) prefix to multiple ISPs is not always possible, it is a natural proposition to announce multiple PD prefixes, one per provider. In this approach, every host is assigned multiple addresses, one per provider, and extra mechanisms are needed (i) to choose a suitable source and destination address for each packet, and (ii) to properly route each outgoing packet according to both its source and its destination. In a sense, using multiple addresses splits the difficult problem of multihoming into two simpler problems that are handled at different layers of the network stack.

1) Choosing addresses: The choice of source and destination addresses is typically left to the application layer. All destination addresses are stored within the DNS (or explicitly carried by the application protocol), and the sending host tries them all, either in turn [START_REF] Draves | Default Address Selection for Internet Protocol version 6 (IPv6)[END_REF] or in parallel [START_REF] Wing | Happy Eyeballs: Success with Dual-Stack Hosts[END_REF]; similarly, all possible source addresses are tried in turn. Once a flow is established, it is no longer possible to change the source and destination addresses -from the user's point of view, all TCP connections are broken whenever a link outage forces a change of address. Address selection can be implemented in the operating system's kernel and libraries, or by the application itself, which is notably done by most modern web browsers.

A different approach is to use a transport layer that has built-in support for multiple addresses and for dynamically renegotiating the set of source and destination addresses. One such transport layer is MPTCP [START_REF] Raiciu | How Hard Can It Be? Designing and Implementing a Deployable Multipath TCP[END_REF]; we describe our experience with MPTCP in Section VII-B.

2) Source-specific routing: As mentioned above, a provider will discard packets with a source address that is in a different provider's prefix. In a network that is connected to multiple providers, each outgoing packet must therefore be routed through the link corresponding to its source address.

When the outgoing links are all connected to a single router, it is feasible to set up traffic engineering rules to ensure that this happens. There can be good reasons, however, why it is desirable to connect each provider to a different router (Figure 1): avoiding a single point of failure, load balancing, or simply that the various links use different link technologies that are not available in a single piece of hardware. In a home networking environment, the edge routers might be provided by the different service providers, with no possibility to consolidate their functionality in a single device.

With multiple edge routers, it is necessary that the routing protocol itself be able to route according to source addresses. We say that a routing protocol performs source-specific routing when it is able to take both source and destination addresses into account in its routing decisions.

ISP 1 ISP 2

Fig. 1. A network connected to two providers

C. Other applications

In addition to multihoming with multiple addresses, we are aware of two problematic networking problems that sourcespecific routing solves cleanly and elegantly.

1) Overlay networks: Tunnels and VPNs are commonly used to establish a network-layer topology that is different from the physical topology, notably for security reasons. In many tunnel or VPN deployments, the end network uses its native default route, and only routes some set of prefixes through the tunnel or VPN.

In some deployments, however, the default route points at the tunnel. If this is done naively, the network stack attempts to route the encapsulated packets through the tunnel itself, which causes the tunnel to break. Many workarounds are possible, the simplest being to point a host route towards the tunnel endpoint through the native interface.

Source-specific routing provides a clean solution to that problem. The native default route is kept unchanged, while a source-specific default route is installed through the tunnel. The source-specific route being more specific than the native default route, packets from the user network are routed through the tunnel, while the encapsulated packets sourced at the edge router follow the native, non-specific route.

2) Controlled anycast: Anycast is a technique by which a single destination address is used to represent multiple network endpoints. A packet destined to an anycast address is routed to whichever endpoint is nearest to the source according to the routing protocol's metric. Anycast is useful for load balancing -for example, the DNS root servers are each multiple physical servers, represented by a single anycast address.

For most applications of anycast, all of the endpoints are equivalent and it does not matter which endpoint is accessed by a given client. Some applications, however, require that a given user population access a well-defined endpoint -for example, in a Content Distribution Network (CDN), a provider might not want to serve nodes that are not its customers. Ensuring that this is the case by tweaking the routing protocol's metric (or "prepending" in BGP parlance) is fragile and error-prone.

Source-specific routing provides an elegant solution to this problem. With source-specific routing, each instance of the distributed server is announced using a source-specific route, and will therefore only receive packets from a given network prefix.

III. RELATED WORK

Multihoming is a difficult problem, and, unsurprisingly, there are many techniques available to implement it, none of which are fully general. In addition to classical network-layer multihoming, already mentioned above, there are a number of lower-layer techniques, the use of which is usually completely transparent to the network layer; we are aware of Multi-Link PPP, of Ethernet link aggregation (port trunking), of the use of MPLS to provide multiple paths across a rich link layer, as well as of proprietary techniques used by vendors of cable modems. Since these techniques work at the link layer, they are usually restricted to multihoming with a single provider.

All of these techniques are compatible, in the sense that they can be used at the same time. We imagine a home network where source-specific routing is used to access two providers, each of which is classically multihomed, over links that consist of multiple physical links combined at the link layer.

Source-specific packet forwarding itself is not a new idea [START_REF] Baker | Ingress Filtering for Multihomed Networks[END_REF], and implementing it manually on a single router using traffic engineering interfaces is a well-documented technique [START_REF] Hubert | Linux Advanced Routing and Traffic Control[END_REF]. Implementing source-specific routing within the routing protocol has been proposed by Bagnulo et al. [START_REF] Bagnulo | The Case for Source Address Dependent Routing in Multihoming. Quality of Service in the Emerging Networking Panorama[END_REF], but the techniques used differ significantly from ours. First, the authors only deal with the non-overlapping case -where the different possible sources are disjoint -, which avoids the need for the disambiguation algorithm which is one of our main concerns. Second, they use a more general facility of an existing routing protocol (BGP Communities) rather than explicitly implementing source-specific routing. We find our more direct approach to be more intuitive, and expect it to be more reliable, since it doesn't require out-of-band agreement on the meaning of the labels carried by the routing protocol.

More generally, there are other applications of routing based on more information from the packet header than just the destination address. The traffic-engineering community has been experimenting with routing based on the TOS octet of the IPv4 header for many years, and the ability to do that is part of the OSPFv2 protocol. TOS-based routing is somewhat analoguous to source-specific routing, and many of the issues raised are similar; both can be seen as particular cases of "multi-dimensional routing".

Equal Cost Multipath (ECMP) is somewhat different. A router performing ECMP has multiple routes to the same destination, and chooses among them according to the value of a hash of the packet header. While ECMP does route on multiple header fields, the choice of fields used to choose a route in ECMP is a purely local matter, and does not need to be carried by the routing protocol.

IV. SOURCE-SPECIFIC ROUTING

A. Next-hop routing tables

Ordinary next-hop routing consists in mapping a destination address to a next-hop. Obviously, it is not practical to maintain a mapping for each possible destination address, so the mapping table must be compressed in some manner. The standard compressed data structure is the routing table (or Forwarding Information Base, FIB), which ranges over prefixes, ranges of addresses the size of which is a power of two. The routing table can be constructed manually, but is usually populated by a routing protocol.

Since prefixes can overlap, the routing table is an ambiguous data structure: a packet's destination address can match multiple routing entries. This ambiguity is resolved by the socalled longest-prefix rule: when multiple routing table entries match a given destination address, the most specific matching entry is the one that is used.

More precisely, a prefix is a pair P = p/plen, where p is the first address in the prefix and plen is the prefix length. An address a is in P when the first plen bits of a match the first plen bits of p. We say that a prefix P = p/plen is more specific than a prefix P = p /plen , written P ≤ P , when the set of addresses in P is included in the set of addresses in P . Clearly, P ≤ P if and only if plen ≥ plen , and the first plen bits of p and p match.

The specificity ordering defined above has an important property: given two prefixes P and P , they are either disjoint (P ∩ P = ∅), or one is more specific than the other (P ≤ P or P ≤ P ).

A routing table is a set of pairs (P, nh), where P is a prefix and nh, the next hop, is a pair of an interface and a (linklocal) address; we further require that all the prefixes in a routing table be distinct. Because of the particular structure of prefixes, given an address a, either the set of prefixes in the routing table containing a is empty, or it is a chain (a totally ordered set); hence, there exists a most specific prefix P in the routing table containing a. The longest-prefix rule specifies that the next hop chosen for routing a packet with destination a is the one corresponding to this most specific prefix, if any.

B. Source-specific routing tables

Source-specific routing is an extension to next-hop routing where both the destination and the source of a packet can be used to perform a routing decision. Source-specific routers use a source-specific routing table, which is a set of triples (d, s, nh), where d is a destination prefix, s a source prefix, and nh is a next hop (note the ordering -destination comes first). Such an entry matches a packet with destination address a d and source address a s if a d is in d and a s is in s. The specificity ordering generalises easily to pairs: a pair of prefixes (d, s) is more specific than a pair (d , s ) when all pairs of addresses (a d , a s ) which are in (d, s) are also in

(d , s ); clearly, (d, s) ≤ (d , s ) when d ≤ d and s ≤ s .
Unfortunately, the set of destination-source pairs of prefixes equipped with the specificity ordering does not have the same structure as the set of single prefixes: given a pair of addresses (a d , a s ), the set of pairs of prefixes containing (a d , a s ) might not be a chain. Consider the pairs (2001:db8:1::/48, ::/0) and (::/0, 2001:db8:2::/48). Clearly, these two pairs are not disjoint (the pair of addresses (2001:db8:1::1, 2001:db8:2::1) is matched by both), but neither is one more specific than the other -the pair (2001:db8:1::1, 2001:db8:3::1) is matched by the first but not the second, and, symmetrically, the pair (2001:db8:4::1, 2001:db8:2::1) is matched by just the second.

From a practical point of view, this means that a sourcespecific routing table can contain multiple most-specific entries, and thus fail to unambiguously specify a forwarding behaviour.

We say that a source-specific routing table is ambiguous when it contains multiple non-disjoint most-specific entries. Two entries r 1 and r 2 that are neither disjoint nor ordered are said to be conflicting, written r 1 # r 2 . If r 1 = (d 1 , s 1 ) and r 2 = (d 2 , s 2 ), then this is equivalent to saying that either d 1 < d 2 and s 1 > s 2 or d 1 > d 2 and s 1 < s 2 . We call the conflict zone of r 1 and r 2 the set of (a d , a s ) that are matched by both r 1 and r 2 .

C. Forwarding behaviour

In the presence of an ambiguous routing table, there exist packets that are matched by distinct most-specific entries. An arbitrary choice must be made in order to decide how to route such a packet.

Let us first remark that all routers in a single routing domain must make a consistent choice -having different routers follow different policies within conflict zones may lead to persistent routing loops. Consider the topology in Figure 2, with two source-specific routes indexed by the pairs (d 1 , s 1 ) and (d 2 , s 2 ) respectively, where packets matching (d 1 , s 1 ) are sent towards the left of the diagram, and packets matching (d 2 , s 2 ) are sent towards the right. If the two pairs are in conflict, and router A chooses (d 2 , s 2 ) while B chooses (d 1 , s 1 ), then a packet matching both pairs will loop between A and B indefinitely.

A (d 1 , s 1 ) (d 2 , s 2 ) B (d 1 , s 1 ) (d 2 , s 2 )

Fig. 2. A routing loop due to incoherent orderings

It is therefore necessary to choose a disambiguation rule that is uniform across the routing domain. There are two natural choices: discriminating on the destination first, and comparing sources if destinations are equal, or discriminating on source first. More precisely, the destination-first ordering is defined by:

(d, s) (d , s ) if d < d or d = d and s ≤ s ,
while the source-first ordering is defined by

(d, s) s (d , s ) if s < s or s = s and d ≤ d .
These orderings are isomorphic -hence, there is no theoretical argument that allows us to choose between them. An engineering choice must be made, based on usefulness alone.

The current consensus, both within the IETF Homenet group and outside it, appears to be that the destinationfirst ordering is the more useful of the two. Consider the (fairly realistic) topology in Figure 3, where an edge router A announces a source-specific route towards the Internet, and a stub network N announces a (non-specific) route to itself. A packet matching both routes must follow the route towards N , since it is obviously the only route that can reach the destination, which implies that A must use the destination-first ordering. On the other hand, we know of no such compelling examples of the usefulness of the source-first ordering.

Internet A (::/0, s)

(N, ::/0) N Fig. 3. A stub network behind a source-specific router

In the following sections, we describe our experience with source-specific routing using the destination-first ordering. However, nothing in this article depends on the particular ordering being used, and our techniques would apply just as well to any structure that is a refinement of the specificity ordering and that is totally ordered on route entries containing a given address.

V. IMPLEMENTING SOURCE-SPECIFIC ROUTING

In the previous sections, we have described source-specific routing and shown how all routers in a routing domain must make the same choices with respect to ambiguous routing tables, and have argued in favour of the destination-first semantics. Whichever particular choice is made by an implementation of a routing protocol, however, must be implementable in terms of the primitives made available by the lower layers (the operating system kernel and the hardware).

In this section, we describe the two techniques that we have used to implement a source-specific extension to the Babel routing protocol [START_REF] Boutier | Source-Specific Routing in Babel[END_REF]. We first describe the technique that we use when running over a lower layer that natively implements destination-first source-specific routing (Section V-A). We then describe our so-called "disambiguation" algorithm (Section V-B) which we use to implement destination-first sourcespecific routing over any source-specific facility provided by the lower layers, as long as it is compatible with the specificity ordering -a very mild hypothesis that is satisfied by a number of widely available implementations.

A. Native source-specific FIB

Ideally, we would like the lower layers of the system (the OS kernel, the line cards, etc.) to implement destination-first source-specific routing tables out of the box. Such native support for source-specific routing is preferable to the algorithm described below, since no additional routes will need to be installed. In practice, while many systems have a facility for source-specific traffic engineering, this lower-layer support often has a behaviour different from the one that we require.

The Linux kernel, when compiled with the relevant options ("ipv6-subtrees"), supports source-specific FIBs natively, albeit for IPv6 only. Unfortunately, this support is only functional since Linux 3.11 (source-specific routes were treated as unreachable in earlier versions), and only for IPv6 (for IPv4, the "source" datum is silently ignored). We know of no other TCP/IP stacks with native support for destination-first sourcespecific routing -other techniques must be used on most systems.

B. Disambiguation of a routing table

All versions of Linux, some versions of FreeBSD, and a number of other networking stacks implement a facility to manipulate multiple routing tables and to select a particular one depending on the source address of a packet. Since the table is selected before the destination address is examined, these API implement the source-first behaviour, which is not what we aim to implement.

In this section, we describe a disambiguation algorithm that can be used to maintain a routing table that is free of ambiguities, and will therefore yield the same behaviour as long as the underlying forwarding mechanism implements a behaviour that is compatible with the specificity ordering (Section IV-B). All the forwarding mechanisms known to us satisfy this very mild hypothesis.

Recall that a routing table is ambiguous if there exists a packet that is matched by at least one entry in the table and such that there is no most-specific entry among the matching entries. A necessary and sufficient property for a routing table to be non-ambiguous is that every conflict zone is equal to the union of more specific route entries.

The algorithm that we propose maintains, for each conflict, exactly one route entry that covers exactly the conflict zone. While a more parsimonious solution would be possible in some cases, it would greatly complicate the algorithm.

a) Weak completeness: We say that a routing table is weakly complete if each conflict zone is covered by more specific entries. More formally, T is weakly complete if

∀r 1 , r 2 ∈ T, r 1 ∩ r 2 = {r ∈ T | r ≤ r 1 ∩ r 2 }.

Theorem 1. A routing table is non-ambiguous if and only if it is weakly complete.

Proof: Let U y x = {r ∈ T | r ≤ x ∩ y}. We need to show that T is non-ambiguous iff ∀r 1 , r 2 ∈ T, r 1 ∩ r 2 = U r2 r1 . (⇐) Suppose T is weakly complete, and consider two route entries x, y ∈ T in conflict. By weak completeness, U y x = x ∩ y, so for all addresses a ∈ x ∩ y, there exists a route r ∈ U y

x such that a ∈ U y x . Since r ∈ x ∩ y, we have r < x and r < y, and r is more specific than x ∩ y. Since this is true for all conflicts, the table is not ambiguous.

(⇒) Suppose T is non-ambiguous and not weakly complete. Then there exist two entries x, y ∈ T in conflict such that x ∩ y = U y

x . Consider an address a ∈ x ∩ y U y x , and an entry r ∈ T matching a. Clearly, r

x ∩ y, and so either r # x or r # y, or r > x and r > y. In all cases, r is not more specific than both x and y, so there is no minimum for the set of entries matching a. This contradicts the hypothesis, so if T is not ambiguous, it is weakly complete.

Disambiguation with weak completeness is not convenient, since it may require adding multiple route entries to solve a single conflict, and the disambiguation routes added may generate additional conflicts. Suppose for example that the FIB first contains two entries r 1 > r 2 , and we add r 3 > r 2 which conflicts with r 1 (see figure below). Since r 2 < r 3 , there is no conflict within r 2 , but we need disambiguation routes d 1 and d 2 . The FIB is now weakly complete.

Suppose now that we add r 4 < r 3 in conflict both with r 1 and the disambiguation route d 2 . We install a new disambiguation entry d 3 . Note also that since r 4 < r 3 , we need to use the next-hop of r 4 for the former region covered by d 1 : we need to change the currently installed disambiguation route entry.

r 1 r 2 → r 1 r 2 r 3 d 1 d 2 → r 1 r 2 r 3 r 4 d 1 d 3
Some of this complexity can be avoided by requiring a stronger notion of completeness.

b) Completeness: A routing table is (strongly) complete if each conflict zone is covered by one route entry. More formally, T is complete if ∀r 1 , r 2 ∈ T, r 1 ∩ r 2 ∈ T . This obviously implies weak-completeness, and therefore a complete routing table is not ambiguous. Our algorithm maintains the completeness of the routing table.

Theorem 2. Adding routes to achieve completeness does not lead to another conflict.

Proof: Suppose that r 1 = (d 1 , s 1 ) and r 2 = (d 2 , s 2 ) are two route entries in conflict, where d 1 < d 2 and s 1 > s 2 . Consider the disambiguation entry r sol = (d 1 , s 2 ) which disambiguates this conflict. Suppose now that r sol is in conflict with another route entry r 3 = (d 3 , s 3 ). We have either d 1 < d 3 and s 1 > s 2 > s 3 , in which case r 3 # r 1 ; or d 2 > d 1 > d 3 and s 2 < s 3 , in which case r 3 # r 2 . In either case, the conflict existed beforehand, and must therefore already have been resolved.

Take the previous example again. When adding r 3 , we add one route entry to cover the area d 1 (r 1 ∩ r 3 ). Since r 2 is more specific, the new route entry does not affect the routing decision for addresses in r 2 . When adding r 4 , it is in conflict with both r 1 and the disambiguation route d 1 , but for the same conflict zone r 4 ∩r 1 . The disambiguation route inserted is thus not an additional conflict.

r 1 r 2 → r 1 r 2 r 3 d 1 → r 1 r 2 r 3 d 1 r 4 d 2 c
) Preliminaries: We write min(r 1 , r 2 ) for the minimum according to . We define two auxiliary functions. The function min conflict(zone, r) (Algorithm 1) returns, if it exists, the minimum route entry in conflict with r for the conflict zone zone. The function conflict solution(zone) (Algorithm 2) returns, if it exists, the minimum route entry participating in a conflict for the zone zone. We write nh(r) for the next hop of a route r.

We use three primitives for manipulating the routing table. Let r = (d, s, nh) be a route entry, and nh a nexthop. Then install(r, nh ) adds the route entry (d, s, nh ), uninstall(r, nh ) removes the route entry (d, s, nh ), and switch(r, nh , nh ) changes the FIB's route entry (d, s, nh ) to (d, s, nh ). Calling switch(r, nh , nh ) is equivalent to calling uninstall(r, nh ) followed by install(r, nh ).

d) Relevant conflicts: Consider a route entry r, and a set E of routing entries in conflict with r for the same conflict zone; all of these conflicts will have the same resolution. Moreover, if the resolution was caused by a route in E, then that was necessarily the more specific of the entries in E. Note that the minimum exists because elements of E have either the same destination, or the same source, and match at least one address in r.

Given a route entry r, we define the equivalence ∼ r by r 1 ∼ r r 2 ⇔ r 1 ∩ r = r 2 ∩ r, i.e. two route entries are equivalent for ∼ r if they have the same intersection with r. If two equivalent route entries are in conflict with r, this means that they have the same conflict zone.

Quotienting a set of routing entries in conflict with r by this equivalence, and taking the minimum of each of the class of equivalence gives us exactly the routes that we care about.

e) Adding a route entry (Algorithm 3): Installing a new route entry in the FIB may make it ambiguous. For this reason, we must install the most specific routing entries first. In particular, we must install disambiguation entries (lines 2 to 9) before the route itself (lines 10 to 14).

Let r be the route to install, and C the set of route entries in conflict with r, for which there is no natural solution, i.e. C = {r ∈ T | r # r and r ∩ r ∈ T } (line 3). We only consider the relevant conflicts upon this set (line 4):

C = {min(E) | E ∈ C/ ∼ r }.
For each route entry r 1 ∈ C (considering the most specific first), we first search (line 5), if it exists, the minimum route entry r 2 such that r 2 # r 1 and r 2 ∩ r 1 = r ∩ r 1 . If r 2 does not exist, then there was no conflict for this zone before, and we must add ((r 1 ∩ r), nh) to the FIB (line 7). Otherwise, a routing entry has been installed for this conflict, and we must decide if the new route entry r is or not the new candidate, which is true if it is more desirable ( ) than both r 2 and r 1 (line 8). If it is the case, then the previous next-hop installed was the one of r 2 : we replace ((r 1 ∩ r), nh 2 ) by ((r 1 ∩ r), nh) (line 9).

Finally, we must search if there exists two route entries in conflict for the zone of r (line 10). In that case, a disambiguation route entry has been installed, so r must replace it (line 12). Otherwise, r can be added normally (line 14). We end the procedure by adding r to our local RIB (line 15).

1 Function add route(r) This time, we must first remove the less specific route first to keep the routing table unambiguous. Again, we write r for the route to be removed. First, remove r from the RIB (line 2). As for the addition, r may be solving a conflict, in which case we cannot just remove it, but must first search for the entry covering that conflict (line 3), and if it exists replace r's next-hop (line 7). Otherwise, we just remove r from the FIB (line 5).

2 for all r 1 ∈ T 3 s.t. r # r 1 and r ∩ r 1 ∈ T 4 and r 1 = min conflict(r ∩ r 1 , r) 5 r 2 ← min conflict(r ∩ r 1 , r 1 ) 6 if r 2 = ⊥ 7 install(r ∩ r 1 , nh(min(r, r 1 ))) 8 else if r ≺ r 2 and r ≺ r 1 9 switch(r ∩ r 1 , nh(r 2 ), nh(r))
We consider C as previously defined (lines 9 and 10). For each route entry r 1 ∈ C (considering the less specific first), we first search, as we did for the adding process, for the minimum route entry r 2 such that r 2 # r 1 and r 2 ∩ r 1 = r ∩ r 1 (line 11). If r 2 does not exist, we remove ((r 1 ∩ r), nh) from the FIB (line 13). Otherwise, for the same reasons above, if r is more desirable than both r 1 and r 2 , then we replace in the FIB the next-hop of r assigned for r ∩ r 1 by the one of r 2 (line 15).

12 if r 2 = ⊥ 13 uninstall(r ∩ r 1 , nh(min(r, r 1 ))) 14 else if r ≺ r 2 and r ≺ r 1 15 switch(r ∩ r 1 , nh(r), nh(r 2 ))
Algorithm 4: Route deletion g) Changing a route entry (Algorithm 5): This is the simplest case, since disambiguation routes must be maintained, and changed only if the route that we want to change has been selected for disambiguation. The order in which we change the route entries does not matter. Let r the route entry to change by r new . Here, we choose to first replace r by r new (line 2).

We consider C as previously defined (lines 3 and 4). For each route entry r 1 ∈ C , we search for the minimum route entry r 2 such that r 2 # r 1 and r 2 ∩ r 1 = r ∩ r 1 . If both r ≺ r 1 and r 2 is r (line 6), then we replace the next-hop nh of the corresponding disambiguation route entry by the new one nh new (line 7).

C. External changes to the routing table

In the description above, we have asssumed that only our algorithm ever needs to manipulate the routing table. In practice, however, the routing table is also manipulated by other agents -other routing protocols or human operators. In principle, the same algorithm should be applied to externally changed routes; however, this is not implemented yet.

VI. SOURCE-SPECIFIC BELLMAN-FORD

The distributed Bellman-Ford algorithm is the foundation of a number of more or less widely deployed routing protocols, such as the venerable RIP, EIGRP, Babel and, arguably, BGP. In order to experiment with source-specific routing, we have implemented a source-specific variant of the Babel routing protocol [START_REF] Chroboczek | The Babel Routing Protocol[END_REF]; the exact details of the packet format of our extension are described in [START_REF] Boutier | Source-Specific Routing in Babel[END_REF]. Our implementation has seen a moderate amount of deployment, most notably as a testbed for the IETF Homenet working group [START_REF] Chown | IPv6 Home Networking Architecture Principles[END_REF].

Ordinary (next-hop) distributed Bellman-Ford maintains a routing table which associates, to each known destination prefix, a next-hop router and a metric; each prefix and metric pair is advertised to neighbours in periodic update messages. In source-specific Bellman-Ford, the routing table is indexed by pairs of a destination prefix and a source prefix, and (source-specific) updates advertise a triple of a destination prefix, a source prefix, and a metric.

The source-specific extension to Babel adds a new kind of source-specific update message in addition to the original, non-specific update. Since Babel's loop-avoidance mechanism relies on two kinds of request messages, it also adds two new kinds of source-specific requests. All of these are encoded as new kinds of messages rather than extensions to existing messages, which causes them to be silently ignored by unextended Babel routers, and ensures that our extension interoperates with the original Babel protocol.

A. Bootstrapping

In distributed Bellman-Ford, a prefix is reannounced after it has been learnt from a neighbour. This process is bootstrapped by announcing prefixes learned from a different source (typically a different routing protocol or a static route); in Babel, this is known as redistribution.

Just like ordinary routes, source-specific routes are originated by performing redistribution. In case a source-specific route is already present, our implementation is able to redistribute it; more generally, the filtering language allows attaching a source prefix to a non-specific route at redistribution time. While careless use of this facility may cause persistent routing loops to occur, this is expected with careless redistribution.

B. Interoperability

The Babel protocol has seen a moderate amount of deployment in production networks, and is usually deployed within cheap routers that can be difficult to update with a source-specific version of the protocol. We have therefore paid particular attention to the issue of interoperability between routers running the source-specific and unextended protocols.

The extended version of the protocol uses both non-specific and specific update messages. In principle, a non-specific route could be announced in two manners: by using a non-specific update carrying the destination prefix d , or by using a sourcespecific update carrying the pair (d , ::/0). As we want nonspecific routes to be propagated between source-specific and non-specific routers, source-specific routers interpret a nonspecific update as a source-specific update with a source prefix of ::/0, and, conversely, source-specific routers never send source-specific updates of the form (d , ::/0), preferring the non-specific form instead.

A more difficult issue is how a non-specific router should interpret a source-specific update. There are two possibilities: the source can be discarded and the update treated as nonspecific, or the entire update can be discarded. The first of these possibilities can cause persistent routing loops.

Consider two nodes A and B, with A source-specific announcing a route to (d , s) (Figure 4). Suppose that B ignores the source information when it receives the update, and reannounces it as d . This is reannounced to A, which treats it as (d , ::/0). Packets destined to d but not sourced in s will be forwarded by A to B, and by B to A, causing a persistent routing loop. On the other hand, if non-source-specific nodes reject source-specific updates, but source-specific nodes accept nonspecific updates, then source-specific nodes can communicate entries of the form (d , ::/0) and are completely compatible with non-source-specific nodes. In this case, Bellman-Ford will eventually converge to a loop-free configuration.

In general, discarding of source-specific routes by nonspecific routers will cause routing blackholes. Intuitively, unless there are enough non-specific routes in the network, non-specific routers will suffer starvation, and discard packets for destinations that are only announced by source-specific routers. A simple yet sufficient condition for avoiding blackholes is to build a connected source-specific backbone that includes all of the edge routers, and announce a (non-specific) default route towards the backbone.

VII. EXPERIMENTAL RESULTS

We have implemented both schemes described in Sections V-A and V-B within babeld, a Linux implementation of the Babel routing protocol. This has allowed us to perform a number of experiments which we describe in this section.

Our experimental network consists of a mesh network consisting of a dozen OpenWRT routers and a single server running Debian Linux. Two of the mesh routers have a wired connection to the Internet, and are connected to the server through VPNs (over IPv4). All of the routers run our modified version of the Babel protocol.

IPv4 connectivity for the mesh is provided by the Debian server, which acts as a NAT box. The IPv6 connectivity is more interesting: there are two IPv6 prefixes, one of which is a native prefix provided by our employer's network, the other one being routed through the VPN. The network therefore has two source-specific default IPv6 routes. Table 11 contains routes for locally originated packets, sourced in 192.168.4.0/24. The only "real" route in this table is the default route, which prevents the VPN from attempting to "enter itself". The other routes are disambiguation routes, automatically generated by the algorithm described in Section V-B. These entries are copies of those present in the main routing table, and prevent locally generated packets destined to local subnets from leaving through the native default route.

A. Routing table for VPN connectivity

B. Multipath TCP

Multipath TCP [START_REF] Raiciu | How Hard Can It Be? Designing and Implementing a Deployable Multipath TCP[END_REF] is an extension to TCP which multiplexes a single application-layer flow over multiple network layer sub-flows, and attempts to use as many distinct routes as possible, and to either carry traffic over the most efficient one or to perform load balancing. An obvious application is a mobile node (a telephone) with permanent connectivity to a cellular network and intermittent WiFi connectivity: MPTCP is able to use the cellular link when WiFi is not available, and switch to WiFi when available without dropping already established connections.

Multipath TCP and source-specific routing turn out to be a surprisingly good match. MPTCP is able to use all of the addresses of the local host, and to dynamically probe the reliability and performance of packets sourced from each.

We have performed two tests that both consist in downloading a 110 MB file over MPTCP from the MPTCP website. In the first test (Figure 6), a desktop computer is directly connected to the source-specifically routed wired network, and is configured with two IPv4 addresses. The Linux tc subsystem is used to limit each of the addresses to 100 kB/s traffic; MPTCP is able to reliably download at 200 kB/s.

In the second test (Figure 7), a laptop's WiFi interface is configured with three addresses (one IPv4 and two IPv6). MPTCP multiplexes the traffic across the three routes, and balances their throughput dynamically.

VIII. CONCLUSION AND FURTHER WORK

Source-specific routing is a modest extension to next-hop routing that keeps the forwarding decisions firmly within control of the routers while allowing end hosts a moderate and clearly defined amount of control over the choice of routes. Since source-specific routing can cause ambiguous routing tables, we have defined the behaviour that we believe source-specific routers should have, and shown how combining different behaviours in the same network can cause persistent routing loops. Similar care must be taken when combining non-specific with source-specific routers in the same network. We have proposed two ways to implement source-specific routing, and obtained experimental results that show that sourcespecific routing can be usefully exploited by the transport layer protocol MPTCP. Our implementation is of production quality, and has seen a modest amount of deployment, notably as a testbed for the ideas of the IETF Homenet working group.

While we enjoy working with distance-vector protocols, much of the networking community appears to have converged on using the OSPF protocol for internal routing. OSPF is a rich and complex protocol, and while many of our techniques should apply without difficulty to it, actually implementing a full source-specific variant of OSPF without sacrificing any of its flexibility remains a challenging endeavour.

It was a pleasant surprise to discover that unmodified MPTCP can use source-specific routes without any manual configuration. However, we claim that source-specific routing can also be exploited at the application layer, and we are currently working on an extension to the Mosh [START_REF] Winstein | Mosh: An Interactive Remote Shell for Mobile Clients[END_REF] UDPbased remote shell that is able to dynamically balance over multiple source-specific routes.

Finally, we have only considered the applicability of sourcespecific routing to edge networks, which tend to carry only a moderate number of distinct routes. However, there is nothing in principle that would prevent source-specific routing from being applicable to BGP and to core networks, where it could perhaps be used for some forms of multihoming and traffic engineering without the routing table growth due to classical multihoming. Extending our results to core networks, with their large routing tables, will require careful analysis of the complexity of our techniques, and a carefully optimised implementation.

1 2 min ← ⊥ 3 for all r 1 ∈ T 4 s 2 min ← ⊥ 3 for all r 1

 234231 Function min conflict(zone, r) .t. r # r 1 and r ∩ r 1 = zone 5 min ← min(r 1 , min) 6 return min Algorithm 1: search for mininum conflicting route 1 Function conflict solution(zone) , r 2 ∈ T 4 s.t. r 1 # r 2 and r 1 ∩ r 2 = zone and r 1 ≺ r 2 5 min ← min(r 1 , min) 6 return min Algorithm 2: Search for conflict solution

10 r 1 ←

 101 conflict solution(r) , nh(r 1 ), nh(r)) 15 T ← T ∪ {r} Algorithm 3: Route addition f) Removing a route entry (Algorithm 4):

1 2 T ← T {r} 3 r 1 ← 4 if r 1 = ⊥ 5 uninstall 8 for all r 1 ∈ T 9 s 11 r 2 ←

 23141589112 Function delete route(r) conflict solution(r) , nh(r), nh(r 1 )) .t. r # r 1 and r ∩ r 1 ∈ T 10 and r 1 = min conflict(r ∩ r 1 , r) min conflict(r ∩ r 1 , r 1 )

1

  Function change route(r, r new ) 2 switch(r, nh(r), nh(r new )) 3 for all r 1 ∈ T 4 s.t. r # r 1 and r ∩ r 1 ∈ T 5 and r 1 = min conflict(r ∩ r 1 , r) 6 and r ≺ r 1 and r = min conflict(r ∩ r 1 , r 1 ) 7 switch(r ∩ r 1 , nh(r), nh(r new )) Algorithm 5: Route modification

Fig. 4 .

 4 Fig. 4. Non-specific routers cannot accept specific routes

Figure 5

 5 Figure5shows an excerpt of the routing tables of one of the two wired routers. The modified babeld daemon has

3 Fig. 6 .Fig. 7 .

 367 Fig. 6. Download using MPTCP and traffic control

  Fig. 5. IPv4 routingtable on a router using a VPN allocated a non-default routing table, table 11, and inserted routes (marked as proto 42) into both the default main table and table 11. The former contains non-specific routes: the default route and the /20 subnet announced by our local DHCP server, and host routes to individual mesh nodes. The encapsulated VPN packets are routed through the default route.

	# ip rule show
	0: from all lookup local
	101: from 192.168.4.0/24 lookup 11
	32766: from all lookup main
	32767: from all lookup default
	# ip route show
	default via 172.23.47.254 dev eth1 proto static
	172.23.32.0/20 dev eth1 proto kernel src 172.23.36.138
	192.168.4.20 via 192.168.4.20 dev tun-ariane proto 42 onlink
	192.168.4.30 via 192.168.4.30 dev wlan1 proto 42 onlink
	[...]
	# ip route show table 11
	default via 192.168.4.20 dev tun-ariane proto 42 onlink
	192.168.4.20 via 192.168.4.20 dev tun-ariane proto 42 onlink
	192.168.4.30 via 192.168.4.30 dev wlan1 proto 42 onlink
	[...]

ACKNOWLEDGEMENTS

We are grateful to Benoît Valiron for his help with the presentation of the disambiguation algorithm.

CODE AVAILABILITY

The source-specific version of Babel is available from https://github.com/jech/babeld.


Guido Gioioso
email: [gioioso@dii.unisi.it

Mostafa Mohammadi
email: mohammadi@dii.unisi.it

Antonio Franchi
email: afranchi@laas.fr

Domenico Prattichizzo
email: prattichizzo]@dii.unisi.it

A Force-based Bilateral Teleoperation Framework for Aerial Robots in Contact with the Environment

come

I. INTRODUCTION

Most of the applications designed for aerial robots, also known as Unmanned Aerial vehicles (UAVs), concern inspection and surveillance of places inaccessible by humans or grounded vehicles. The possibility of letting aerial robot interact with the environment opens an additional wide set of potential applications for aerial robots like, e.g., maintenance, construction, cooperative grasping and transportation.

The problem of modeling and control of an aerial robot interacting with objects and surfaces in the surroundings has been faced in some very recent projects [START_REF] Airobots | EU Collab[END_REF], [START_REF] Arcas | EU Collab[END_REF]. In [START_REF] Fumagalli | Modeling and control of a flying robot for contact inspection[END_REF] a delta-shaped structure has been mounted on a quadrotor to apply forces on the environment using a passivity-based controller. One-dimensional manipulation of a cart performed by one or two quadrotors, equipped with rigid and passive tools, has been studied in [START_REF] Srikanth | Controlled manipulation with multiple quadrotors[END_REF]. A hybrid force/motion control for a quadrotor with a rigid tool attached on it applying forces on external environment has been presented in [START_REF] Nguyen | Hybrid force/motion control and internal dynamics of quadrotors for tool operation[END_REF]. A standard near-hovering controller has been used instead in [START_REF] Gioioso | Turning a near-hovering controlled quadrotor into a 3D force effector[END_REF] to let a quadrotor UAV apply a desired 3D force on a surface by means of a rigidly attached passive tool.

Most of the UAVs' real applications, requiring or not the physical interaction of the robots with the surrounding objects, take place in unstructured, uncertain and unknown environments. This could make the fully-autonomous control of the UAVs practically unreliable. The human intervention thus becomes advisable to handle uncertainty issues.

Moreover, providing the human operators with an intuitive and natural interface to control the vehicle would open the possibility of tele-operating UAVs also to users with no particular piloting skills. Several possible bilateral teleoperation schemes using haptic feedback to steer single or multiple UAVs have been proposed in the last decade. In [START_REF] Mahony | A new framework for force feedback teleoperation of robotic vehicles based on optical flow[END_REF] an impedance controller is presented that allows quadrotor teleoperation with haptic feedback to the pilot that was able to steer the vehicle, avoiding collisions with obstacles in the environment. In [START_REF] Schill | Admittance mode framework for haptic teleoperation of hovering vehicles with unlimited workspace[END_REF] an admittance control mode, dual to the impedance mode, has been developed. In [START_REF] Rifa | Haptic-based bilateral teleoperation of underactuated unmanned aerial vehicles[END_REF], impedance control was used for velocity control while a force feedback was computed using the distance from obstacles.

In [START_REF] Lee | Semi-autonomous haptic teleoperation control architecture of multiple unmanned aerial vehicles[END_REF] a multi-layer architecture was developed to steer a formation of UAVs while perceiving the state of all (or some) of the robots along with the presence of obstacles in the environment. A decentralized passivity-based approach was used in [START_REF] Franchi | Bilateral teleoperation of groups of mobile robots with time-varying topology[END_REF] in order to cope with the presence of possible destabilizing time-varying topologies. A reactive planning approach to bilaterally teleoperate a UAV is presented in [START_REF] Masone | Semi-autonomous trajectory generation for mobile robots with integral haptic shared control[END_REF] where the human modifies the future path and receives a integral haptic feedback related to the path flyability.

To the best of our knowledge the problem of teleoperating UAVs able to establish contact and apply forces on objects in the surroundings has not been yet deeply investigated. Our main contribution is to propose a novel teleoperation framework based on the controller presented in [START_REF] Gioioso | Turning a near-hovering controlled quadrotor into a 3D force effector[END_REF], suitable for both contact-free tasks and arbitrary 3D force exertion on the environment using a rigidly attached tool. The user is provided with a force feedback proportional to the force applied by the vehicle at the contact point (Fig. 1). An automatic slowing-down policy is introduced to ensure a smooth transition between free motion and physical interaction.

The rest of this paper is organized as follows. In Sec. II the models of the master and the slave systems involved in the teleoperation are described. The adopted near-hovering controller is presented in Sec. III along with the main results obtained in [START_REF] Gioioso | Turning a near-hovering controlled quadrotor into a 3D force effector[END_REF]. In Sec. IV the teleoperation architecture is described. The proposed framework has been validated in simulations whose results are described in Sec. V, while in Sec. VI conclusions and possible future developments of the work are outlined.

II. SYSTEM MODEL

The proposed teleoperation scheme consists of a fully actuated haptic joystick (master), an underactuated aerial robot (slave), and a communication link between them. In the present paper communication time-delays will not be taken into account. The models considered for master and slave systems are described in the following.

A. Master Model

The dynamics of a gravity/inertial compensated haptic interface can be simply described by:

M m q = f h + f c (1)
where q ∈ IR 3 is the position of the haptic device end effector, M m ∈ IR 3×3 is a diagonal matrix, f h ∈ IR 3 is the human force on the haptic probe, and f c ∈ IR 3 is the control force.

B. Slave Model

In this section we present the standard dynamical model of an underactuated aerial robot, of which the quadrotor is the most popular example. Let us consider a reference world frame W : {O W , w 1 , w 2 , w 3 } and a robot body frame B :

{O B , , b 1 , b 2 , b 3 }.
The origin of this second frame is placed at the center of mass of the UAV and coincides with the geometric center of the four propellers. The position of O B in W and the corresponding linear velocity will be indicated with p = (p 1 , p 2 , p 3 ) T ∈ IR 3 and with v = (v 1 , v 2 , v 3 ) T ∈ IR 3 respectively. Let us denote by m ∈ IR the mass of the vehicle and by J ∈ IR 3×3 its inertia matrix with respect to the body frame. The matrix R ∈ IR 3×3 represents the rotation matrix from the body frame to the inertial world frame and ω ∈ IR 3 is the angular velocity vector representing the rotation of B with respect to W , expressed in B. The orientation of the vehicle is denoted by η := (φ , θ , ψ) T ∈ IR 3 , being φ , θ , ψ respectively the roll, pitch and yaw angles (RPY). The matrix R ∈ IR 3×3 can be thus written as R(η) = R z (ψ)R y (θ )R x (φ ), where R x , R y , R z are the elementary rotation matrices about the three coordinate axis. The total thrust acting on the -b 3 direction, denoted by λ ∈ IR + , and the total moment expressed in B, denoted by τ = (τ 1 , τ 2 , τ 3 ) T , are assumed to be the control inputs of this system.

The aerial robot is equipped with a tool used to establish contact with the environment. Its tip position in B is expressed by: d = (d x , d y , d z ) T ∈ IR 3 . The position y ∈ IR 3 of the tool-tip in the world frame is:

y = p + Rd. (2)
The force exerted by the environment on the tool-tip, expressed in the world frame, will be denoted by f e ∈ IR 3 . According to the hard finger contact model [START_REF] Prattichizzo | Grasping[END_REF], we assume a negligible interaction moment at the contact point. Given these assumptions, the equations of motion of the slave robot can be written as:

ṗ = v (3) mv = -λ Rẑ + mgẑ + f e (4) η = T(η)ω (5) J ω = -ω × Jω + τ + d × R T f e , (6)
where ẑ = (0, 0, 1) T and T(η) ∈ IR 3×3 is a matrix that transforms ω to the RPY rates η. Another common assumption will be adopted in the rest of the paper: the aerial robot is never in a singular configuration (i.e., -π 2 < φ < π 2 and π 2 < θ < π 2 ). In the singular configuration, in fact, the total thrust cannot be used to balance the gravity force and this represents a useless case for the purposes of this work.

III. NEAR-HOVERING CONTROLLER ADAPTED FOR PHYSICAL INTERACTION

The aerial robot in exam is an underactuated system with its six configuration parameters, (p, η) and four control inputs (λ , τ). Despite its underactuation it is able to apply arbitrary 3D forces on the environment, as shown in [START_REF] Gioioso | Turning a near-hovering controlled quadrotor into a 3D force effector[END_REF]. In fact, in [START_REF] Gioioso | Turning a near-hovering controlled quadrotor into a 3D force effector[END_REF] a mathematical derivation has been presented which allows to adopt a widely used near-hovering controller not only during contact-free flight but also to apply desired contact forces on the surrounding environment. In this section the structure of the mentioned controller, will be recalled along with the main results obtained in [START_REF] Gioioso | Turning a near-hovering controlled quadrotor into a 3D force effector[END_REF], which represent the core of the proposed framework.

A fast inner-loop PID controller is aimed a letting the robot track a desired attitude 3 , relying on the fact that the rotational dynamics is fully actuated. Differentiating ( 5) and substituting (6), we get

η d = (φ d , θ d , ψ d ) T ∈ IR
η = T(η)J -1 (-ω × Jω + τ + d × R T f e ) + Ṫ(η)ω.
We can thus define the attitude controller as:

τ = JT -1 (η)K A η e (7)
where:

K T A =            0 0 k φ DA 0 0 k φ PA 0 0 k φ IA 0 k θ DA 0 0 k θ PA 0 0 k θ IA 0 k ψ DA 0 0 k ψ PA 0 0 k ψ IA 0 0            , η e =          - φ φ d -φ (φ d -φ ) dt - θ θ d -θ (θ d -θ ) dt - ψ sin(ψ d -ψ) sin(ψ d -ψ) dt          (8)
leading to the closed-loop dynamics:

η + K A η e = TJ -1 (-ω × Jω + d × R T f e ) + Ṫω.
Local exponential stability has been shown for (η e , ηe ) under suitable conditions of the initial state and suitable gains.

The expression ( 7) can be simplified considering that in the near-hovering conditions assumed for the contact-free flight T -1 (η) can be approximated by a 3 × 3 identity matrix and J can be assumed to be diagonal, as common practice, and hidden in the gain matrix K A . The expression of τ can be thus written as:

τ = K A η e . (9)
These approximations have been proven to work very well in reality under near-hovering conditions [START_REF] Franchi | Bilateral teleoperation of groups of mobile robots with time-varying topology[END_REF], [START_REF] Lee | Semi-autonomous haptic teleoperation control architecture of multiple unmanned aerial vehicles[END_REF].

An outer loop controller is then designed to track a desired vertical dynamics as:

λ = - m cos φ cos θ (-g -b z P v 3 + k z PP e 3 ) (10)
f h f c f s f e q + g e f d ( , ⌧ ) Kf K h K e

Master device

Mapping N-H controller where b z P and k z PP are positive scalar gains and e 3 is an additional control input. In order to act on the horizontal dynamics, the desired roll φ d and pitch θ d are set such that [START_REF] Franchi | Bilateral teleoperation of groups of mobile robots with time-varying topology[END_REF] where e 1 , e 2 are two additional control inputs, and s • and c • denote sin(•) and cos(•) respectively. The reader is referred to [START_REF] Lee | Semi-autonomous haptic teleoperation control architecture of multiple unmanned aerial vehicles[END_REF] for a detailed analytical derivation of [START_REF] Franchi | Bilateral teleoperation of groups of mobile robots with time-varying topology[END_REF]. Let us gather the three additional control inputs in the vector e = (e 1 , e 2 , e 3 ) T ∈ IR 3 .

sin φ d sin θ d = m λ -s ψ c ψ -c ψ /c φ -s ψ /c φ -b P v 1 + k PP e 1 -b P v 2 + k PP e 2
The presented controller has been used in literature to steer aerial robots in contact-free motion by choosing e = p d -p in order to regulate p to a desired position p d ∈ IR 3 (see [START_REF] Lee | Semi-autonomous haptic teleoperation control architecture of multiple unmanned aerial vehicles[END_REF] for further details).

What has been shown in [START_REF] Gioioso | Turning a near-hovering controlled quadrotor into a 3D force effector[END_REF] is that, during the contact phase, a mapping exists between the control input e = (e 1 , e 2 , e 3 ) T ∈ IR 3 and the contact force f e at steady state. The analytical expression of this mapping depends on the presence of integral terms in the attitude controller. If nonzero integral gains are considered for roll and pitch regulation in the inner loop (i.e.,t k IA > 0, k θ IA > 0, k ψ IA any), the mapping assumes the simplest form and can be written as:

e 1 = - f e 1 mk PP e 2 = - f e 2 mk PP e 3 = - f e 3 k PP . (12)
For the more complex expressions of the mapping obtained in the other cases (when k φ IA and k θ IA are equal to zero) the reader is referred to [START_REF] Gioioso | Turning a near-hovering controlled quadrotor into a 3D force effector[END_REF].

The mapping between e and f e has been used in [START_REF] Gioioso | Turning a near-hovering controlled quadrotor into a 3D force effector[END_REF] to let an autonomous UAV apply a desired steady-state contact force f d ∈ IR 3 on the environment (equal to -f e ). Given the desired force f d , the error e was then computed (still considering the simple case of non-zero integral terms for the inner-loop) as:

e 1 = f d 1 mk PP e 2 = f d 2 mk PP e 3 = f d 3 k PP ( 13
)
and given to the outer-loop controller to result in the desired contact force. Remark 1: It is worth noting that the presented framework allows an underactuated aerial robot to apply an arbitrary 3D force on the environment, relying on its four actuators, as shown in [START_REF] Gioioso | Turning a near-hovering controlled quadrotor into a 3D force effector[END_REF]. The underactuation of the robot appears in the fact that the position and the orientation cannot be freely chosen when applying the arbitrary 3D force

The aim of the present paper is to exploit this result to build a teleoperation framework in which a human operator can manually regulate f d by changing the position of the haptic probe and is provided with a force feedback computed on the basis of the contact force that arises from the environment interaction.

d s v 0 v 1 S 0 S 1 S 1 ḋs l 0 : ḋs = m 0 d s + v 0 l 1 : ḋs = m 1 d s + v 1

IV. TELEOPERATION FRAMEWORK

The proposed teleoperation framework is schematically represented by the block diagram in Fig. 2 and described in the following. In this work we assume that the yaw is automatically regulated by the robot and set such that the projection of the tool on the x-y plane of W is normal to the target surface and the tool is pointing to it.

A. User Command

The human operator applies a force f h on the haptic device changing its position q. The desired force f d is computed as:

f d = K f q + f s (14)
where K f ∈ IR 3×3 is a diagonal matrix with positive entries, chosen to produce a desired mapping between the workspace of the haptic device and the range of possible forces applicable by the robot on the environment. The term f s ∈ IR 3 in ( 14) constitutes a potential force whose role is to automatically slow down the vehicle when it is approaching the part of the environment on which the user wants to apply a force. At the beginning of the interaction phase, in fact, the speed of the vehicle has to be sufficiently small, in order to avoid undesirable high impact forces that might damage both the robot and the environment. The vector f s is thus designed as:

f s = b n (d s , ḋs ) n -b t (d s )ẏ t , (15)
where n ∈ IR 3 is the unitary vector normal to the target surface, ẏt ∈ IR 3 is the velocity of the tooltip projected on the surface plane and b n (d s , ḋs ) ∈ IR and b t (d s ) ∈ IR are positive scalar functions defined in the following.

The scalar b n (d s , ḋs ) is a function of the distance d s ∈ IR between the tooltip and the target surface and its derivative ḋs ∈ IR. Let l 0 and l ∞ be two straight lines on the half plane represented in Fig. 3 which are described by the equations:

l 0 : ḋs = m 0 d s + v 0 l ∞ : ḋs = m ∞ d s + v ∞ , (16)
where m ∞ < m 0 < 0 and v ∞ < v 0 < 0 are negative scalar parameters, properly chosen. Denote with p = ( ds , ds ) the actual state of the tooltip on that half plane, and define the two points p0 and p∞ as the intersections of the vertical lines passing through p with l 0 and l ∞ , respectively. Now consider a function α(d s , ḋs ) ∈ IR defined as:

α(d s , ḋs ) = p -p∞ p0 -p∞ , (17)
which represents the vertical distance of the point p from the line l ∞ , normalized in such a way that it is equal to one when p lies on l 0 . The function b n is finally defined as follows:

b n (α) = 1 cos 2 ( π 2 α-π 2 ) -cos( π 2 α -π 2 ) if 0 < α ≤ 1 0 otherwise . ( 18
)
Function b n is nonzero only in the zone denoted by S 1 in Fig. 3. In the zones S 0 and S ∞ it is equal to zero and thus in those regions f s does not act in the direction n normal to the target surface.

The function b t (d s ) serves as a damping factor that acts on the projection of the tooltip velocity on the plane tangential to the target surface. Its value is defined as

b t (d s ) = b max (1 -d s d ) if 0 ≤ d s ≤ d 0 otherwise ( 19
)
where b max is the maximum damping value when d s = 0 (i.e., when the contact phase starts) and d is the value of the distance d s at which the damping action starts.

Remark 2: Note that the term f s defined by ( 15), (17) (18) and ( 19) only acts on f d during the approaching phase while it is zero during the contact. This allows to apply the user-commanded force on the surface without interference. Furthermore f s is zero during the detaching phase (i.e., when ḋs > 0) and the possible traveling phases used to move between several contact points. The mapping recalled in Section III is then used to transform f d in the control input e which is the input for the near-hovering controller that computes the corresponding control inputs (λ , τ) for the UAV. If the robot is in contact with the environment, the controller presented in Section III, fed with the input e, will produce, at steady state, a contact force f d at the tooltip. Conversely, if no contact occurs, the same control input e will produce a motion of the vehicle in the direction of f d . The user can thus intuitively control the motion of the robot in the environment and also its interaction with it.

B. Force Feedback

The control force for the master device f is computed as:

f c = -K h sat(q, q max ) -B h q + K e f e (20)
where K h ∈ IR 3×3 , B h ∈ IR 3×3 and K e ∈ IR 3×3 are diagonal matrices with positive entries, q max ∈ IR is a positive scalar, and the function sat(x, y) ∈ IR 3 × IR 3 is defined as:

sat(q, q max ) = q if |q| ≤ q max q |q| q max otherwise . ( 21
)
The role of the first term in the rhs of (20) is to ensure the haptic probe stabilization at (q = [0, 0, 0]) in absence of external forces. This term also gives to the user the feeling of the distance from zero-commanded force. The second term is a damping factor that prevents the system from oscillatory behaviors. The third term is used to compensate the gravitational force. Finally K e f e represents the force feedback provided to the user that gives the perception of the contact force applied by the robot on the environment.

In order to implement this kind of feedback we assume to have a measure of the external force f e that occurs at the contact point during the interaction. This measure can be obtained by means of a force sensor placed at the tooltip or implementing an observer for the external force. A possible choice for the observer is represented by the algorithm presented in [START_REF] Yüksel | A nonlinear force observer for quadrotors and application to physical interactive tasks[END_REF]. Note that the matrices of gains K h , B h , the scalars q max and qmax and K e in (20) should be designed s.t. the stabilization terms -K h sat(q, q max ) and B h q become negligible w.r.t. K e f e during the interaction phase (i.e. when f e = 0), according to the performed task.

In this paper we do not provide a formal proof of the stability of the teleoperation system, which is left as a future development of this work. However we want to briefly discuss some stability-related facts about the system in exam. The stability of the slave system (3)-( 6) under the control law ( 9)-( 11) has been proven in [START_REF] Lee | Semi-autonomous haptic teleoperation control architecture of multiple unmanned aerial vehicles[END_REF]. Moreover in [START_REF] Gioioso | Turning a near-hovering controlled quadrotor into a 3D force effector[END_REF] the stability of the equilibrium points of the system in contact with the environment has been proven by means of numerical analysis using the indirect Lyapunov method. The structure of the teleoperation framework proposed in this work has some affinity with the scheme presented in [START_REF] Rifa | Haptic-based bilateral teleoperation of underactuated unmanned aerial vehicles[END_REF], even though there physical interaction was not allowed. In that paper the stability of the teleoperation system, subject to bounded forces applied by the human operator on the master and bounded external forces acting on the slave, was proven. In that case the external forces acting on the slave were preventing the vehicle from colliding with obstacles in the environment. Nevertheless, the proof shown in [START_REF] Rifa | Haptic-based bilateral teleoperation of underactuated unmanned aerial vehicles[END_REF] gives us grounded hopes on the existence of a formal proof for our teleoperation framework in which the external forces acting on the slave arise from its interaction with the environment. Furthermore a stable behavior of the proposed force-based teleoperation scheme was practically observed during the human-in-the-loop simulations described in the following section.

V. HUMAN-IN-THE-LOOP SIMULATIONS

To evaluate the efficiency of the proposed bilateral teleoperation scheme, a set of human-in-the loop simulations has been performed, in which the human operator teleoperates a quadrotor aerial robot in a virtual environment. The experimental setup is shown in Fig. 4. The operator sends the commands using an Omega.3 (Force Dimension) haptic device to a simulated quadrotor. The dynamic model of the quadrotor and the proposed controller are simulated using Matlab and Simulink. The interaction between the robot and the environment is also computed in Simulink. In particular the presence of a force sensor at the end of the tool is emulated by computing the interaction forces between the tooltip and the environment using the god-object model. The visualization of robot and environment has been implemented using the open source game engine Blender. Control loop and data communication runs with a rate of 1000 Hz. Position and orientation of the simulated vehicle and other objects are computed in Simulink at 1000 Hz and sent to Blender with a rate of 25 Hz. Two cameras (one fixed and one onboard) give the visual feedback to the operator. The inertial parameters of the simulated quadrotor are: m = 1kg, J = diag(0.13, 0.13, 0.22)kgm 2 . Two different scenarios have been designed to validate the approach in which the operator was asked to perform different tasks. A detailed description of the two tasks is given in Secs.V-A and V-B. The results obtained during the simulations performed in the first and in the second scenario are summarized in the plots shown in Fig. 7 and8, respectively. In the plots the following correspondence between colors and cartesian axis has been established: blue → x, green → y, red → z. For the plots regarding angles the adopted convention is: blue → roll, green → pitch, red → yaw. In Figures 7a and8a the dashed lines show the force commanded by the user K f q, while the continuous lines represent the desired force f d . Figures 7b and8b show the force commanded by the user (dashed lines) and the force exerted by the robot on the environment f e (continuous lines). In Figures 7c and8c the continuous lines represent f e while the dashed lines are used to plot the control force f c . The error e is shown in Figures 7d and8d. Figures 7e and8e show the desired (dashed lines) and actual (continuous lines) attitude of the vehicle. In Figures 7f and8f the control inputs λ (black line) and τ (colored lines) can be observed. The plots have been divided by vertical dashed black lines into phases denoted by P1, P2 and P3. The phases denoted by P1 represent free motion phases in which the slowing-down policy does not act on f d (i.e., f s = 0). The ones denoted by P2 represent the phases of the task in which the slowing-down policy acts on f d (i.e. f s = 0). Finally, the contact phases are denoted by P3. The three different phases can be also interpreted, considering Fig. 3, as it follows. The phases denoted by P1 can be interpreted as the ones in which (d s , ḋs ) ∈ S 0 . The phases denoted by P2 as the ones in

A. First Scenario -Pressing buttons on a wall

In the first scenario a human operator was asked to drive the quadrotor to push three buttons on a wall. The positions of the buttons were randomly chosen. In order to fulfill the task, the UAV had to apply a force on the three buttons greater than a certain threshold (5N). This experiment has been designed to show the applicability of the proposed framework for both contact-free flight and interaction phases. Two screenshots of the simulation are given in Fig. 5a.

The results of this experiment are plotted in Fig. 7. Figure 6 shows the 3D trajectory of the UAV during the test. The first phase is a free motion phase in which the user controls the motion of the robot and aligns the tool position with the first button to be pressed on the wall. The approaching phase then starts, denoted by P2. The action of f s on f d is shown in Fig. 7a: the difference between f d and the force commanded by the user increases while the robot gets closer to the button. The third phase, denoted by P3, is the first contact phase in which the robot presses the first button on the wall. In Fig. 7b the contact force f e is indeed different from zero in this phase, and it tracks the desired force f d . At the beginning of this phase, a positive peak of force on the z axis can be observed. This transient force is due to the underactuation of the considered robotic platform. In order to apply the pushing force on the button, in fact, the UAV has to tilt with a negative pitch (shown in Fig. 7e). This results in an undesired force read by the sensor during the transient phase which is not considered by the mapping recalled in Section III which only takes into account steady-state forces. Let us consider the Fig. 7c for what concerns the force feedback. It can be seen how f c follows the external force f e despite of an offset due to the presence of the stabilization term -K h q in (20). In these simulations the value of the stabilization term cannot be considered negligible w.r.t. to the contact force. Nevertheless it was found to be appropriate for the considered conditions and led to a comfortable teleoperation system. The value of the force feedback is considerably higher in the contact phase denoted by P3 w.r.t. to the one recorded during the previous phases. During the rest of the experiment the same sequence of phases is replicated twice. Reasonable values of thrust and torques have been computed by the controller during the simulation (see Fig. 7f), in correspondence of the (bounded) values of the input e shown in Fig. 7c.

B. Second Scenario -Pushing a cart toward a wall

The second virtual environment consists of a cart machine moving on rails (see Fig. 5b). The user was asked to push the cart machine toward a wall placed at the end of the rails and stop the movement when the contact with it was reached. The inertia and the friction of the cart on the rails prevent it to move freely. The human operator applies a certain amount of force on it, by teleoperating the UAV, to reach the wall. The aim of the experiment is to show the ability of the system to apply forces on moving objects and to show the effectiveness of the proposed force feedback strategy in rendering forces of the environment to the human operator.

Let us consider the Fig. 8. In the first phase (denoted by P1) of the simulation, the UAV is teleoperated by the user in order to approach the cart that has to be pushed on the rails. The distance between the tool and the target surface of the cart starts decreasing until (d s , ḋs ) ∈ S 1 and the second phase (denoted by P2) starts. In this second phase, due to the action of the slowing-down control action, the distance between the dashed and the continuous blue lines of Fig. 8a starts to be greater then zero and it increases until the contact is reached. When the contact phase (denoted by P3) starts, a peak of force on the z axis is read by the sensor and shown in Fig. 8b and8c. This peak can be explained with the same arguments used in Section V-A to explain the peaks recorded during the simulation performed in the first scenario. After the transient phase, also in this test, the force f e tracks the desired force f d (see Fig. 8b). At the end of the contact phase a peak of force in the x direction is observable in Fig. 8b. This important haptic cue happens when the cart touches the wall. This peak is also felt by the user (as shown in 8c). During the experiment the UAV has a stable behavior (as shown in Fig. 8e) and the control inputs of the nearhovering controller, in correspondence to the error e shown in Fig. 8d, reach reasonable values (see Fig. 8f) w.r.t. a typical quadrotor platform of that size and weight. The positions of both the UAV and the cart in the three different phases of the simulation can be observed in Fig. 9. It can be seen from this plot that the cart moves under the action of the UAV and subject to the friction force until it reaches the wall.

VI. CONCLUSIONS AND FUTURE WORK

In this paper a novel teleoperation framework for aerial robots able to establish contact with the surrounding environment has been presented. The framework is based on the mathematical derivation previously presented in [START_REF] Gioioso | Turning a near-hovering controlled quadrotor into a 3D force effector[END_REF], in which the problem of an autonomous aerial robot applying an arbitrary 3D force on the environment was addressed. The proposed teleoperation architecture allows a human operator to intuitively drive the vehicle during the free motion and also to apply a desired force on a surface of the environment by means of a passive tool rigidly attached on the robot. The approach has been validated in extensive human-in-the-loop simulations aimed at showing its effectiveness. The validation of the framework in a real experimental setup is the future development of this work. Work is ongoing to formally prove the stability of the proposed teleoperation loop.

Fig. 1 :

 1 Fig. 1: Schematic representation of the proposed teleoperation framework.

Fig. 2 :

 2 Fig. 2: Block diagram of the proposed teleoperation framework.

Fig. 3 :

 3 Fig.3: Graphical representation of the adopted slowing-down policy.

Fig. 4 :

 4 Fig. 4: A picture of the experimental setup. The human operator teleoperates the UAV using the haptic device and relies on a fixed camera (left) and an onboard camera (right) to see the virtual environment.

Fig. 5 :

 5 Fig. 5: Screenshots of the first (a) and second (b) scenarios designed for the human-in-the-loop simulations.

Fig. 6 :

 6 Fig. 6: 3D position of the robot during the simulation performed in the first scenario.

Fig. 7 :

 7 Results of the simulation performed in the first scenario.

Fig. 8 :

 8 Results of the simulation performed in the second scenario.

Fig. 9 :

 9 Fig. 9: Position of the UAV (a) and position of the cart (b) recorded during the simulation performed in the second scenario.

Preprint version, final version at http://ieeexplore.ieee.org/ 2

Preprint version, final version at http://ieeexplore.ieee.org/ 3

Preprint version, final version at http://ieeexplore.ieee.org/ 4

Preprint version, final version at http://ieeexplore.ieee.org/ 5

Preprint version, final version at http://ieeexplore.ieee.org/