Thomas Heide

Clausen -Ulrich Herberg

Thomas Heide Clausen

Ulrich Herberg

AUTOCONF -Stating the Problem

Keywords: mobile network, ad hoc network, network architecture, address configuration, routing, IP networks, MANET réseaux mobiles, réseaux ad-hoc, architecture de réseau, configuration d'adresses, protocole de routage, réseaux IP, MANET

This memorandum outlines the goals for and constraints on an IP address and prefix autoconfiguration mechanism for mobile ad hoc networks.

Introduction

A Mobile Ad hoc NETwork (MANET) is, essentially, a collection of mobile nodes, communicating among themselves over wireless links and thereby forming a dynamic, arbitrary and often multi-hop graph. The core tenants of MANETs are their autonomy (ad-hoc-ness), i.e. that they can be deployed with no a priori configuration, and their ability to cope with a high degree of network topology dynamism (the term mobile is indicative of this, although a dynamic network topology may be due to factors other than mobility).

MANETs are largely made possible due to the emergence of commodity wireless radio interfaces, and protocols maintaining connectivity in a highly dynamic, multi-hop wireless network have been developed and standardised by the IETF and by others in form of routing protocols such as [START_REF] Clausen | RFC3626: Optimized Link State Routing Protocol (OLSR)[END_REF].

Such MANET routing protocols operate with the assumption that MANET routers (MRs) already have IP addresses and, if applicable, prefixes assigned1 -however no dedicated mechanisms for assigning IP addresses or distributing prefixes to MRs have been standardised by the IETF. It is worth noting that academic literature has presented numerous such mechanisms, however that these may not necessarily have been developed with an explicit requirement of seamless integration with the Internet architecture and other IETF-related protocols.

Memorandum Outline

The remainder of this memorandum is organised as follows: section 2 outlines the notion of IP addresses and prefixes, as is currently employed in the Internet, with the purpose of retaining the basic notions and properties of addresses and prefixes. Section 3 briefly recapitulates the architecture of MANETs as seen by the IETF and described in [START_REF] Chakeres | Mobile Ad hoc Network Architecture[END_REF] and [START_REF] Clausen | A MANET Architectural Model[END_REF]. Specific effort is made to include those architectural issues which are pertinent to understanding the requirements and constraints that an IP autoconfiguration mechanism for MANETs must satisfy, as well as to define a terminology used in later sections.

Two common terms are used when describing MANET deployments: "connected MANETs" and "disconnected MANETs", with the latter also sometimes referred to as "stand-alone MANETs". These terms are wrong, misleading, unfortunate and unhelpful since they do not provide an useful classification of MANETs -in fact, these terms do not provide any classification of MANETs. Section 4 explains why in detail, and proposes an alternative taxonomy -which, contrary to "connected MANETs" and "disconnected MANETs", accurately classifies MANET deployment scenarios with respect to autoconfiguration issues.

Section 5 explicitly, and with reference to section 2 and section 3, tries to answer the simple question of "what are the entities that are to be configured in a MANET, and what does it mean to configure those?". In other words, which of interface(s), router(s) are to get which of addresses and prefixes. In a sense, this section is stating the problem that is to be solved.

In the Internet today, mechanism for automatically configuring network interfaces with IP addresses already exists. Similarly, mechanism for automatically delegating a prefix from a given router to another given router exists. Section 6 briefly summarises those, as well as outlines the assumptions that these mechanisms are designed to work under. While these mechanisms can be said to "solve the problem" stated in section 5 for the Internet, the assumptions under which they do "solve the problem" are closely related to the classic model of an IP link.

MANET interfaces and the logical structure of a MANET differs in part from the classic model of an IP link, as described in section 3. Verbatim application of the mechanisms for automatically configuring network interfaces with IP addresses described in section 6 may therefore not be possible, or may not satisfy the goals stated in section 5 -and this is described in section 7 in some detail.

Section 8 recapitulates the key points brought forward in these discussions, and thus concludes this memorandum.

INRIA

2 What is an IP Address?

Before elaborating on the specific issues regarding IP autoconfiguration of MANETs, as well as on existing IP autoconfiguration mechanisms, it is important to retain the basic notions of addresses -and their complements, prefixes. This section will therefore briefly describe the nature of addresses -which includes introducing the terms "address assignment" and "prefix delegation". The discussions in this section are intended to provide an overview and motivation for the IP addressing architecture in the Internet, and not to be an exhaustive architectural discussion of the IP addressing architecture.

The Basics

In the most basic form, an IP address can be considered simply as follows:

• an IP address is a unique identifier of a network interface.

I.e., an IP address allows, uniquely, to address IP datagrams to one network interface among the many network interfaces present in the Internet2 .

According to this, the important property of an IP address is its network-wide uniqueness -and absent any other constraints, in order to uniquely identify any network interface on the Internet, this would be a sufficient property to ensure.

Networks

The Internet is big -very big -so a large number of IP addresses are required in order to ensure that each network interface can have a unique IP address. IPv4 offers 2 32 unique addresses, and IPv6 offers 2 128 unique addresses. If, as indicated in section 2.1 no other constraints than uniqueness were imposed, this would imply that each router in the Internet would have to maintain a routing table explicitly containing 2 32 or 2 128 entries -and, in order to construct its routing table, would have to exchange this much information with other routers. In order to reduce the amount of state information that each router would have to maintain (the size of the routing table) and exchange, constraints other than uniqueness are imposed on IP addresses as assigned throughout the Internet.

The basic idea in reducing the state that routers are to maintain and exchange is simple: assign IP addresses in an organised fashion, as indicated in the example in figure 1. Thus, all network interfaces with IP addresses from within a given interval would be attached to the same router -and the routers would each have to maintain and exchange state for each interval, rather than for each explicit IP address. With 2 32 or 2 128 IP addresses, if the Internet was constructed uniquely as in the simple example in figure 1 illustrates, it would imply either a large number of routers, each with a still large number of network interfaces attached -or a small number of routers, each with even more network interfaces attached. A large number of routers still entails a large amount of state for each router to maintain and exchange -and a small number of routers each with a very large amount of network interfaces attached would concentrate traffic with ensuring capacity and reliability issues. Thus, and with respect to IP addresses, each of the clouds from figure 1 may itself contain routers, as illustrated in figure 2.

IP addresses within a cloud in figure 2 are assigned in the same organised fashion as in the example in figure 1, although now hierarchical: all addresses from within the interval [a-p] are in the cloud "under" router R 0 ; all the addresses from within the interval [a-c] are also "under" router R 1 etc.

The term used for giving a router an address interval and allowing that IP addresses from within that interval are attached to only that router is called delegation. Thus, an IP address assigned to a network interface indicates where in the hierarchy this network interface is located. This implies two things, which are important to retain:

• a router is delegated an IP address interval from someone, who has authority to do so -i.e. from a router has had (at least) that IP address interval delegated itself;

• two properties apply to IP addresses:

an IP address is a unique identifier of a network interface (as in section 2.1); an IP address implies a precise topological location in the addressing hierachy.

The last item is of special importance, since it implies that an address is not just an identifier, but that there's a semantics associated to an address -and that this semantics is important for the organisation of the Internet.

INRIA

Prefixes -the Internet Term for Intervals

Syntactically, an IP address is a simple sequence of bits -32 bits for IPv4 and 128 bits for IPv6. In order to achieve an easy way of designating "IP address intervals" and "sub intervals" of such an IP address interval, prefixes are used. Structurally, a prefix is the n leftmost bits of an IP address, which are common to all IP addresses from within that interval, and n is said to be the prefix length. The general notation for a prefix in IPv6 is p::/n, implying that p is the prefix, the length of this prefix is n, and the :: indicating that everything following the prefix (i.e. the bits other than the n leftmost bits of the address) is a sequence of zeros 3 .

Thus, and with reference to figure 3, if the router R has the prefix p::/32 assigned, subordinate routers R 1 , R 2 and R 3 can be delegated sub-intervals by simply delegating these the prefixes p:1::/64, p:2::/64 and p:3::/64 respectively.

It shall be noted that:

• the prefixes thus delegated to these three routers are non-overlapping -i.e. the address ranges from which the routers R 1 , R 2 and R 3 may respectively assign addresses are also non-overlapping; • prefixes delegated to the routers R 1 , R 2 and R 3 overlap with the prefix delegated to R 0 , and thus the precise topological location of the routers R 1 , R 2 and R 3 is subordinate to R 0 .

Commonly, and for the remainder of this memorandum, prefixes will simply be written as p:: or p:1::, i.e. the prefix length will be omitted when written. The prefix length is in this case simply assumed equivalent to the length of the leftmost and explicitly written bits, i.e. that which appears to the left of the ::.

Delegation and Assignment

Prefix delegation is, thus, the way in which a router acquires an IP address interval, which is topologically correct with respect to its location in the addressing hierarchy. From within this IP address interval, the router may -as detailed in section 2.3 -either delegate parts to subordinate routers, or assign addresses to network interfaces attached to it, as illustrated in figure 4. The important distinction in this is, that a delegation of a prefix does not provide any network interface with a unique identity but rather allocates part of the IP address interval for exclusive use by a subordinate router -whereas address assignment implies that a network interface is configured with a specific unique and topologically correct IP address.

Summary

In this section, basic notions of IP addresses and prefixes, as is currently employed in the Internet, have been outlined. An IP address can be assigned to a network interface as a unique identifier in the network. In addition, it is also a precise topological location in the addressing hierarchy. Prefixes are intervals of addresses that can be delegated to routers for the purpose of either redelegating parts to subordinate routers, or assigning addresses from the interval to network interfaces attached to them.

3 The MANET Architecture [START_REF] Chakeres | Mobile Ad hoc Network Architecture[END_REF] and [START_REF] Clausen | A MANET Architectural Model[END_REF] describe, in detail, an architectural view of MANETs, as when seen as part of the Internet and thus integrated in the Internet architecture. In this section, the basic concepts relevant to a discussion on IP autoconfiguration for MANETs will be briefly reiterated. In particular, the notion of a "link" as well as the morphology of a MANET router (MR) is important for the discussion in this memorandum and are, therefore, presented in section 3.2 and section 3.3, respectively. In these sections, reference will be made to what can be called the Classic IP Link Model, which is therefore introduced in section 3.1.

The Classic IP Link Model

A core notion in the Internet is that of a link. A link, illustrated in figure 5, is assumed to have the following properties:

• IP datagrams are not forwarded at the network layer when communicating between network interfaces which are on the same link; hence • TTL/hop-limit in IP datagrams are not decremented when communicating between network interfaces on the same link;

• IP datagrams with a TTL/hop-limit of 1 are (modulo data loss) delivered to all network interfaces on the same link and;

• link-local multicasts and broadcasts are received by all network interfaces on the same link -without forwarding. When assigning an IP address to a network interface, this network interface is also configured with a prefix, such that the following constraint is respected:

• all network interfaces configured with addresses from within the same prefix p::, and with the same prefix p:: assigned to the interfaces, can communicate directly with one another.

INRIA

It follows from the above that the notion of "IP link" is tied with the notion of an "IP Subnet" (IPv4) or a prefix (IPv6), in that all network interfaces which are configured with the same subnet address or prefix are considered to be on the same IP link and thus that for communication between nodes within the same subnet, no forwarding is required and no decrement of TTL/hop-limit is performed.

Network interfaces within the same prefix or, for IPv4, within the same subnet, are within the classic IP link model assumed to also be attached to the same classic IP link as described above. For completeness, it should be mentioned that the inverse is not necessarily true: in some network configurations, interfaces connected to the same classic IP link may be configured within different prefixes or subnets.

The Missing Link

MANET interfaces are a specific class of network interfaces in that they exhibit what is commonly denoted as semi-broadcast characteristics. With reference to [START_REF] Clausen | A MANET Architectural Model[END_REF], this roughly implies that otherwise neighbouring nodes may experience distinctly different local connectivity. As indicated in figure 6, the MANET interface of N2 is able to directly communicate with the MANET interface of N1 and N3 (i.e., no forwarding, TTL/hop-limit is not decremented, a transmission from the MANET interface N2 is received by the MANET interfaces of both N1 and N3, including link-local multicasts and broadcasts). Considering the properties listed for an IP link in section 3.1, this might imply that the MANET interfaces of N1, N2 and N3 would be connected to the same link. However the semi-broadcast nature of MANET interfaces implies that this is not so: transmissions from N1 will not reach N3 without forwarding -which entails that TTL/hop-limit is decremented, and that link-local multicast and broadcast from the MANET interface of N1 will not reach the MANET interface of N3.

The semi-broadcast nature of MANET interfaces implies that:

• any two MANET interfaces can not be assumed to be connected to the same link; thus

• the IP address / prefix configuration of MANET interfaces must be such that their configuration (as per the constraint in section 3.1) does not indicate that they can be assumed to be connected to the same link.

The Morphology of a MANET Router

A MANET router is a router having, at least, one MANET interface -i.e. an interface exhibiting semi-broadcast characteristics as indicated in section 3.2 -and otherwise retaining the usual characteristics of a router. In particular, a MANET router:

• may have a prefix delegated to it;

• may delegate (part of) that prefix to other subordinate routers;

• may have networks attached to it, in particular these networks may be of any type, (including, but not limited to, other MANETs), thus respecting usual routing and addressing hierarchies.

'M' for Mobility -'A' for Ad hoc

As indicated in section 1, MANETs are characterised by being mobile -i.e. that the network topology, in particular the set of participating MANET Routers as well the ability for two MANET routers to communicate among themselves may change over time. In particular, this entails that a formerly single MANET may separate into two independent MANET, and that two formerly independent MANETs may merge into one single larger MANET. Additionally, the 'A', for ad hoc, implies that the network may emerge spontaneously and, potentially, without any pre-determined infrastructure elements (or without any such elements altogether) such as a router providing access to an outside network such as the Internet. This implies that a MANET may appear either in isolation, where the uniqueness property of IP addresses is the sole priority, configuration-wise -or in a situation where it may be integrated/attached to an outside network where, in addition to the uniqueness property, IP addresses / prefixes should correspond to the topologic location of the MANET within the addressing hierarchy. This latter point is somewhat analogous to other IP networks, in which a collection of hosts may connect with each other in a private network without connection to outside networks and wish to acquire IP addresses where the uniqueness property of IP addresses / prefixes is the sole priority (link-local addresses) -as well as be part of a network where in addition to the uniqueness property, IP addresses / prefixes should correspond to the topologic location of the network interfaces within the addressing hierarchy (global addresses). As will be detailed in section 6, these two are both supported in the Internet via IPv6 Stateless Autoconfiguration -and, an analogy to MANETs exist, as indicated in this section.

INRIA

Summary

A MANET router is a router which has at least one MANET interface, i.e. a network interface exhibiting semi-broadcast characteristics, but which otherwise retains the usual characteristics of a router. Thus, the singular issue with respect to MANET routers is, that the constraints regarding IP address and prefix configuration of network interfaces must be respected, also on the MANET interface(s) -which in particular entails that:

• any two MANET interfaces can not be assumed to be connected to the same link; thus

• the IP address / prefix configuration of MANET interfaces must be such that their configuration (as per the constraint in section 3.1) does not indicate that they can be assumed to be connected to the same link.

4 Connected vs. Disconnected MANETs ???

Occasionally, the terms "connected MANET" and "disconnected MANET" (or, for the latter also "stand-alone MANET") are employed when describing different deployments scenarios (for example in [START_REF] Boot | Analysis of MANET and NEMO[END_REF][START_REF] Mase | Prefix Distribution Framework for Connected MANETs[END_REF][START_REF] Ruffino | Connectivity Scenarios for MANET[END_REF][START_REF] Clausen | RFC3626: Optimized Link State Routing Protocol (OLSR)[END_REF][START_REF] Shenoy | Bandwidth Reservation and QoS in Internet MANETs[END_REF]). These terms are both unfortunate and wrong -and their use should be discouraged and discontinued. This section will show why they're wrong in section 4.1, why they're unfortunate in section 4.2 -and propose an alternative and correct way of describing different MANET deployment scenarios in section 4.3.

On why these terms are wrong

In order to correctly analyse why the terms "connected MANET", "disconnected MANET" and "stand-alone MANET" are wrong, consider first the scenario depicted in figure 7. This MANET contains four MANET routers (MRs), each of which having (of course) one MANET interface and one additional network interface towards a classic IP link. MR1 has, on this classic IP link, a (non-MANET) router, R, which has another network interface towards another classic IP link. There are no components (other than, perhaps, hosts) in this network, other than those depicted in figure 7. The obvious question to ask, then, if this MANET in figure 7 is a "connected" MANET or if it is a "disconnected MANET"?

Graph Theory?

Being "connected" may refer to a property of a graph, recalling that a connected graph is an undirected graph that has a path between every pair of vertices.

A MANET is intended -even expected -to possess this property, which the MANET in figure 7 certainly does posses.

• Thus, if the intended semantics of a "connected MANET" is with reference to graph theory, then the MANET in figure 7 indisputably is a "connected MANET".

Outside Networks?

The common use of the term "connected MANET", however, seems intended to carry a semantics that go beyond that of graph theory. Assuming that MANETs are supposed to be composed of a connected graph of MANET routers, a MANET being "connected" may be in reference to the existence of links from MANET routers over non-MANET interfaces to other networks. Considering the scenario in figure 7, this MANET indisputably is connected to another network over a non-MANET interface -the easiest example hereof is the existence of a connection from the MANET via MR1 to R. Considering an even simpler MANET, such as the one depicted in figure 8 where a single MANET router, MR 1 , has a single MANET interface and a single network interface towards a classic IP link, the MANET can be said to be composed of the single MANET interfacewhich, indeed is connected to another network, indicated by the grey oval, via MR 1 .

• Thus, if the intended semantics of a "connected MANET" is with reference to the existence links connecting the MANET to other networks, then the MANET in figure 7 indisputably is a "connected MANET". Moreover, a single MANET router with a single MANET interface and a single interface connected to a classic IP link is indisputably a connected MANET -and, indeed, so is every possible MANET.

The Internet?

It may be that the intention of the term "connected MANET" is to indicate if a MANET is connected to "The Internet", with the term "disconnected MANET" being used otherwise.

There are a number of problems inherent in this usage, since:

• "The Internet" as such does not exist as an unique and identifiable entity, but is rather a concept of "a network of networks" [START_REF] Kurose | Computer Networking: a Top-Down Approach Featuring the Internet Package[END_REF]. Thus, what does it mean to be connected to the Internet? That one can access a particularly common www search-engine? Are "Internets" (other than the one where this particularly common www search-engine exists) then not "Internets"? If not, then what, other than arbitrary existence of a given service, distinguishes the "real" and the "other" Internets.

• Even if an unique "Internet" could be identified and defined, this would not suffice, since:

a router is a router is a router, thus a router which connects to another router which is part of this "Internet" does not become "connected to" the Internetbut becomes "part of" the internet. A MANET router connecting via a network interface to a classic IP link and thereby to another router which is "part of" the "Internet" therefore also becomes "part of" this "Internet".

specifically, routers in the "Internet" are not segregated into classes of "Internet routers" and "Internet routers, connected to the Internet";

as such, routers do not signal if they are indeed "Internet routers" or notimplying that the scenario in figure 7 would be indistinguishable from the scenario where the outside network was this "Internet".

• Thus, if the intended semantics of a "connected MANET" is with reference to the existence of links connecting the MANET to the "Internet", then if a given MANET is a "connected MANET" or not is indeterminable.

On why these terms are Unfortunate

The use of the terms "connected MANET" and "disconnected MANET" indicates a desire for classifying MANETs into two categories, with networks of either category having a clearly defined and easily identifiable set of properties, distinct from networks of the other category.

The fact that since a single MANET router with a single MANET interface and a single network interface connected to a classic IP link, as well as more complex MANETs can be said to be a "connected MANET", as per both section 4.1.1 and section 4.1.2, indicates, that all MANETs are, indeed, in the "connected MANET" category. Or, in other words, the clearly defined and easily identifiable set of properties that would set a "connected MANET" INRIA and a "disconnected MANET" apart are not to be found in neither graph theory nor in the existence of links from the MANET to outside networks.

Since, as per section 4.1.3, if a MANET, or more generally "any router" is "connected to the Internet" or not, is indeterminable, using this as a classifying metric is unfortunate for the same reasons: it does not provide a well-defined set of criteria for determining if a MANET is a "connected MANET" or not.

All of the above illustrates that these proposed classifications and terms are unfortunate, or perhaps unnecessary, since the terms "connected MANET", "disconnected MANET" and "stand-alone MANET" do not clearly specify scenarios in which distinct problems are present and therefore where distinct considerations are required.

A Better Taxonomy

While the terms "connected MANET" and "disconnected MANET", as described in section 4.1 and section 4.2 are wrong and unfortunate and therefore should be discouraged and discontinued, they have been proposed for a reason -a reason which is valid enough, but which needs to be clearly described and, consequently, a valid taxonomy needs be defined.

In order to understand the issue, it is important to recapitulate the properties of an IP address, as described in section 2 and repeated below:

• an IP address is a unique identifier of a network interface (as in section 2.1);

• an IP address implies a precise topological location in the addressing hierachy.

Of particular importance for the discussion in the following is the second of these two properties. Considering the two scenarios in figure 9 for illustrating the importance this makes.

Autonomous MANETs

In figure 9a, the MANET exists, with a number of connections to other networks. The particularity of this scenario is, that none of these networks imposes an addressing hierarchy on the MANET. To make reference to the tree-like figures in section 2, the MANET is the "root" of the tree, with routers in the other networks being subordinate to the MANET. As such, these non-MANET routers should have prefixes delegated to them from the MANET, such that these prefixes reflect the non-MANET routers topological location below their upper MANET routers.

• in the network illustrated in figure 9a, the MANET is not subordinate to any "upper router" which imposes an addressing hierarchy -and, in particular, the MANET is the "root" of the addressing hierarchy.

MANET MR 1 R MR 4 MR 3 MR 2 R R R A
MANET prefix q::/32 MANET prefix q:2:/64 MANET prefix q:1:/64 MANET prefix q:4:/64 MANET prefix q:3:/64

N MANET MR 1 R MR 4 MR 3 MR 2 R R R

B

Topologically correct prefix p::/32 with respect to network N Figure 9: Autonomous and Subordinate: On the left side, the MANET is the "root" of the addressing hierarchy. On the right side, the MANET is imposed an addressing hierarchy by a superordinate router.

Subordinate MANETs

In figure 9b, the MANET exists, with a number of connections to other networks. The particularity of this scenario is, that one of these networks, the one indicated with a boldface "A", imposes an addressing hierarchy on the MANET. To make reference to the tree-like figures in section 2, the MANET is an "internal node" of the tree, with the router R A in the network A. Thus, to ensure that the second property of IP Addresses (that they be correct with respect to a topological location in the addressing hierarchy imposed by the network A), IP addresses within the MANET must be assigned from within a prefix delegated to R A -possibly by R A delegating part of its prefix for use within the MANET.

As with the "Autonomous MANETS", described above, non-MANET routers in other networks, subordinate to the MANET, should have prefixes delegated to them from the MANET, such that these prefixes reflect the non-MANET routers topological location below their upper MANET routers.

• in the network illustrated in figure 9b, the MANET is subordinate to any "upper router" which imposes an addressing hierarchy -and, in particular, addresses within the MANET must respect this addressing hierarchy.

On the topic of subordinate MANETs, such may be multi-homed, i.e. be subordinate to two or more routers, each of which impose their own topological location in an addressing hierarchy. This situation is no different than that of any other multi-homing situation, in that the MANET may acquire a prefix from either or both of these, and assign addresses from either or both of these -so long as it is ensured that traffic from the MANET which INRIA is generated with a given source IP address is transited through the appropriate router (i.e. the one from whose' prefix that source IP address is acquired).

Summary

This section takes exception to the usage of the terms "connected" and "disconnected" MANETs, arguing that these are both wrong, unfortunate and unhelpful -in particular since it is not possible to uniquely classify MANETs into either "connected" or "disconnected", and since they therefore do not assist in understanding if different considerations apply for different MANET deployments.

With reference to an understanding of address hierarchies, it is understood that there exists two distinct deployment scenarios for MANETs -with the distinction being if the MANET is subjected to an address hierarchy, imposed from an outside network to which it is connected, or not. The particularities of these two scenarios are discussed.

The MANETs is proposed, classifying MANETs which are NOT subordinate to another network in an addressing hierarchy. The term Subordinate MANETs is proposed, classifying MANETs for which another network (or set of networks) impose an addressing hierarchy onto the MANETs.

The distinction of "Autonomous MANETs" and "Subordinate MANETs" allows, uniquely, to classify MANETs into two disjoint classes.

AUTOCONF -The Goals

With the general considerations on IP addresses and prefixes in section 2, and the taxonomy in section 4.3 identifying two distinct MANET deployments, the goals that a MANET AUTOCONF solution should satisfy can be summarised into a simple set of goals:

• provide each MANET router with a unique prefix;

• respecting addressing hierarchies and the Internet addressing architecture;

• contain any MANET-specific behaviours to the MANET interfaces of MANET routers. This section will detail these goals a bit further, starting with general architectural considerations in section 5.1, followed by specific considerations for Autonomous MANETs and Subordinate MANETs, in section 5.2 and section 5.3, respectively. Each of these sections will specify the precise goal for an AUTOCONF solution for each of these two MANET classes.

Section 5.4 will reflect on the architectural consequences of this approach, specifically with respect to that which applies to the MANET interfaces.

Architectural Considerations

The overall goal of AUTOCONF -AUTOmatic CONFiguration for MANETs -is to ensure that network interfaces can be uniquely identified, respecting the addressing architecture in section 2 and the constraint outlined in section 3.1. In other words, that network interfaces are automatically configured, respecting the Internet and the IP architecture.

In a MANET router, this entails that the MANET interface is to be configured with an IP address and prefix, as detailed in [START_REF] Chakeres | Mobile Ad hoc Network Architecture[END_REF] and [START_REF] Clausen | A MANET Architectural Model[END_REF] -and that network interfaces attached to a given MANET router, as well as routers subordinate to a given MANET router are to be, respectively, assigned IP addresses and delegated prefixes from within a unique prefix over which that MANET router is authoritative. This implies that:

• each MANET router must acquire a unique prefix, over which it is authoritative. Under which constraints this prefix is to be acquired will be detailed in subsequent sections. With each MANET router having acquired such a unique prefix, the following considerations apply:

• a MANET router behaves, with respect to subordinate routers and networks, identical to any other router, in particular in respecting the addressing hierarchies;

• given that the MANET router has acquired a unique prefix, the MANET interface can be configured with an address from within this prefix and a prefix length of /128 (for IPV6) or /32 (for IPv4) -or use the MANET interface as an unnumbered interface [START_REF] Baker | RFC1812: Requirements for IP Version 4 Routers[END_REF].

INRIA

Acquiring a Prefix in an Autonomous MANET

The particularity of an Autonomous MANET is the absence of an externally imposed addressing hierarchy -and thereby the absence of an entity which can provide unique and topologically correct prefixes to MANET routers.

In order for each MANET router to acquire a unique prefix, an AUTOCONF solution must therefore be developed that:

• allows MANET routers to, from within a well-known prefix similar to the well-known Link Local Prefix, and in a distributed fashion, each acquire a prefix which unique within this MANET;

• addresses and prefixes from within this well-known prefix are characterised by:

being unique only within one MANET.

Acquiring a Prefix in a Subordinate MANET

The particularity of a Subordinate MANET is the presence of one or more externally imposed addressing hierarchies -and thereby the presence of one or more entities which can provide unique and topologically correct prefixes to MANET routers. In a Subordinate MANET, the solution detailed for Autonomous MANETs may be applied in order to acquire MANET-wide unique and local prefixes for each MANET router. In addition, an AUTOCONF solution must be developed that:

• allows MANET routers to request delegation of a prefix from one or more or all of the externally imposed addressing hierarchies -a prefix or prefixes which will be correct with respect to the MANETs topological location within that/these addressing hierarchies.

Consequences

Recalling the tree-like addressing hierarchies from section 2, the set of MANET routers in a MANET appear as a single "internal node" in the tree. This means that:

• "downwards" in the tree, i.e. to connected networks and subordinate routers, the addressing hierarchy is respected with respect to each MANET router;

• "upwards" in the tree, if the MANET is a Subordinate MANET, the MANET routers will respect the addressing hierarchy with respect to the external entity(ies) from which prefixes have been acquired;

• "horizontally" within the MANET, and due to the potentially dynamic topology of the MANET, no permanent relationship -and, in particular, no hierarchy -is ensured between MANET routers. Negative consequences hereof are prevented by configuring the MANET interfaces such that their configurations do not allow assumptions that they all be connected to the same "link", as detailed in section 3. This particularity is exposed ONLY horizontally between MANET routers, and is neither propagated upwards or downwards in the tree.

Summary

In this section, the goals of MANET autoconfiguration based on the architectural considerations and the difference between Autonomous and Subordinate MANETs have been classified. Each MANET router must be provided with a unique prefix. If the MANET is a Subordinate MANET, prefixes have to be topologically correct with respect to the imposed addressing hierarchies. In addition, only the MANET interface of a router has to be exposed to MANET-specific autoconfiguration requirements; classical IP networks attached to a non-MANET interface are not affected.

INRIA 6 Automatic Configuration in the Internet

Other than assigning IP addresses and prefixes to network interfaces in a static manner, there are several mechanisms of automatic configuration. Multiple solutions have been standardised by the IETF and are wide-spread in implementations. In this section, an overview of the most common autoconfiguration mechanisms is presented. Among them are DHCP (presented in section 6.1), and Stateless Autoconfiguration (refer to section 6.2). These mechanisms rely on certain assumptions of the Internet, some of them being mentioned in section 6.3.

Dynamic Host Configuration Protocol (DHCP)

DHCP ( [START_REF] Droms | RFC2131: Dynamic Host Configuration Protocol[END_REF] for IPv4, [START_REF] Droms | RFC3315: Dynamic Host Configuration Protocol for IPv6 (DHCPv6)[END_REF] for IPv6) enables automatic allocation of an IP address to a host by a DHCP server. A host requiring an IP address contacts a DHCP server and requests a new address. The DHCP server will dynamically4 assign an address from a certain interval of addresses, and allocate a so called "lease" of that address to the client. The client can then use the address for a certain time. If it wants to keep the address for a longer time, it has to prolong the lease. If the DHCP server is not in the same subnet as the DHCP client, it is possible to use a DHCP relay agent which can forward the messages to a different IP network.

For automatically delegating IPv6 prefixes to routers, there exists an option in a DHCP message called DHCP-PD (as specified in [START_REF] Troan | RFC3633: IPv6 Prefix Options for Dynamic Host Configuration Protocol (DHCP) version 6[END_REF]). A router may demand a prefix from another router by sending a DHCP request including the DHCP-PD option. The DHCP server may then delegate a subordinate prefix of its own prefix to the client. The prefix delegation option may also be relayed through a DHCP relay agent.

Stateless Autoconfiguration (SLAAC) / Neighbour Discovery Protocol (NDP)

Stateless Autoconfiguration (SLAAC) (as specified in [START_REF] Thomson | RFC4862: IPv6 Stateless Address Autoconfiguration[END_REF]) is another way of assigning IP addresses to hosts which has been introduced with IPv6 (and cannot be applied in IPv4). In contrast to DHCP, a host requiring an address does not need to contact any kind of server. Instead, the protocol is completely distributed.

A host first selects a tentative IPv6 address by attaching its host identifier (in most cases its MAC address) to the well-known link-local prefix. It then has to verify that no other host in the same subnet has the same address by broadcasting NDP messages [START_REF] Narten | RFC4861: Neighbor Discovery for IP version 6 (IPv6)[END_REF] to the link. If the address is not unique, the autoconfiguration process will be aborted. Upon a successful address uniqueness test, a host may request a prefix from any router on the link by an exchange of NDP messages. It will again attach its host identifier to that router prefix and possibly repeat the address uniqueness test.

IP architecture assumptions

The two mechanisms presented in the sections 6.1 and 6.2, are based on certain assumptions which hold in the Internet. Most importantly, these assumptions are:

1. Messages (e.g. DHCP Request, NDP) are link-locally broadcasted with a TTL of 1, and may thus never be forwarded by a router.

2. The local topology is relatively stable.

3. Routers acquiring a prefix from a delegating router are in a subordinate topology with respect to that router.

An example for assumption 1 are NDP messages. They have a hop limit of 255, and whenever a node receives an NDP message with a decremented hop limit, it will reject the message, and the uniqueness test will fail. Thus, NDP messages may never be forwarded by a router.

Assumption 2 means that in classical IP networks, links will not break down very frequently, and the topology of the LAN will not change in an ad-hoc manner. This assumption is for example important for DHCP where all clients are required to reach the DHCP server to acquire or prolong their lease. If the link is broken, the allocated address will be invalidated after the lease has expired.

Assumption 3 applies for instance for DHCP-PD. The requesting router is topologically subordinate to the delegating router, as depicted in figure 2.

Summary

In this section, the currently most-used autoconfiguration mechanisms DHCP and SLAAC/NDP have been described in their basic functionality. They do solve the autoconfiguration "problem" in the Internet, relying on certain assumptions which hold in the Internet. Important assumptions among them are that link-locally broadcasted messages will never pass any router, that the local topology is relatively stable, and that routers acquiring a prefix from a delegating router are in a subordinate topology with respect to that router.

INRIA 7 Internet vs MANETs

As presented in section 6, there are several well-working standards for autoconfiguring IP addresses and prefixes in the Internet. These are all based on certain assumptions that are valid in the architecture of the Internet, some of them having been presented in section 6.3. However, as shown in section 3, MANETs have some different architectural properties in comparison to classical IP networks. These special properties avoid the verbatim usage of the presented autoconfiguration mechanisms, which will be demonstrated in this section.

Different link-model of MANETs

One reason why the autoconfiguration methods presented in section 6 cannot directly work on MANETs is the different link model of MANETs in comparison to the classic IP link model (refer to section 3.1 and 3.2 for a more detailed description of the link model in the MANET architectural model). In the classic IP link model, a link-locally broadcasted packet will never be forwarded by a router. However, to assure that MANET router prefixes are non-overlapping within a certain scope, uniqueness of router prefixes must be assured over several hops. This invalidates the usage of NDP for the prefix uniqueness test, as the NS and NA messages would have to be forwarded by routers.

Routers vs. Hosts

Several proposals for MANET autoconfiguration in literature suggest to simply use NDP messages to configure MANET nodes. However, this contradicts the MANET architecture as proposed in section 3 where MANET nodes are described as routers and possibly attached nodes. RFC 4862 [START_REF] Thomson | RFC4862: IPv6 Stateless Address Autoconfiguration[END_REF] specifically states: "The autoconfiguration process specified in this document applies only to hosts and not routers". The reason for this is that one main goal of autoconfiguration is to allocate prefixes to MANET routers (refer to section 5) and not IP addresses to hosts. It has to be assured that these prefixes are non-overlapping so that hosts attached to that router can then be autoconfigured using classical autoconfiguration mechanisms as presented in section 6.

Mobility in MANETs

One main difference of MANETs in comparison to classical wired networks is the mobility of the nodes and thus a dynamic network topology (refer to section 1). Routes between MANET nodes may change very frequently and may also break down. When using DHCP for prefix delegation, it is important that all clients reach the DHCP server which is not guaranteed in a MANET. For example, the node running a DHCP server can be cut off the MANET, and thus no new node would ever get a prefix, and as soon as the leases of prefixes expire, participating nodes in the MANET will lose their prefixes. In addition, neither DHCP servers nor NDP can handle merging and partitioning of MANETs as described in section 1.

Relationship between MANET routers

As seen in the example in section 6.3, in the Internet, routers acquiring a prefix from a delegating router are compulsorily in a subordinate topology with respect to that router. This is not always true in a MANET. While MANET routers may allocate a subprefix from a superordinate router, they are not forced to. This case is depicted in figure 10, where two routers in a MANET with a prefix p:1:: and p:2::, respectively, are on the same hierarchical level rather than in a subordinated topology. This is the reason why delegating prefixes using DHCP-PD will not directly work because p:2:: is not subordinate prefix of p:1:: and can thus not be delegated by MR 1 .

Summary

MANETs have some different architectural properties in comparison to classical IP networks. Verbatim application of classical autoconfiguration mechanisms is not possible due to different underlying assumptions. First, MANET nodes have a different link-model as classical IP links thus inhibiting verbatim application of these mechanisms in MANETs. In addition, NDP cannot be applied in MANETs as it only applies to configure hosts, not routers. Mobility in MANETs avoids the usage of DHCP, as the network topology may frequently change and the connection to the DHCP server might not be constantly available. At last, MANET routers are in contrast to classical routers not compulsorily in a subordinate topology with respect to some other router. Hence, they can be in the same hierarchical level thus requiring some other mechanism as DHCP-PD.

INRIA 8 Recapitulation

This memorandum has described goals for and constraints on IP address and prefix autoconfiguration mechanisms for mobile ad hoc networks, which are necessary for a seamless integration of MANETs with the classical IP architecture.

In doing so, it has been illustrated that the unfortunately commonly used terms "connected MANET", "disconnected MANET", and "stand-alone MANET" are unsuitable -in particular since these terms do (i) not allow classification of MANETs with different properties and (ii) do not allow this since the terms are not descriptive of relevant properties in MANETs. Indeed, it has been argued that any and all MANETs can be classified as being "connected MANETs", rendering the terminology and the classification that the terminology aims at providing useless.

Considering the Internet addressing architecture, a taxonomy has been proposed which, contrary to the terms indicated above, allows to classify MANETs into two categories, describing properties relevant for each category with respect to autoconfiguration of MANETs. This taxonomy aids in simplifying both the description of the goals of autoconfiguration in MANETs, as well as the architectural considerations that apply for how IP addresses and prefixes are assigned and delegated to interfaces and routers.

While the goals for autoconfiguration in MANETs are not that different from those for autoconfiguration in other network types, the characteristics of the MANET interfaces, the requirement that each MANET router shall acquire a prefix and the possible deployment of MANETs as Autonomous MANETs render verbatim application of existing autoconfiguration mechanisms impossible: the fundamental assumptions behind such existing mechanisms are distinctly different from those of MANETs -core examples hereof have been described in this memorandum.

Figure 1 :

 1 Figure 1: Flat topology of routers: each router having an address interval, with all network interfaces configured with addresses from within that interval being directly connected to that router.

Figure 2 :

 2 Figure 2: Hierarchical topology of routers: router R 0 delegates a subinterval [a...c] from its interval [a...p] to the subordinate router R 1

  A classic example of a prefix and a prefix length from IPv4 would be 130.225.194/24, where 130.225.194 is the prefix and 24 subsequently is the prefix length -indicating an IP address interval of [130.225.194.0-130.225.194.255].

Figure 3 :

 3 Figure 3: Prefix delegation: router R 0 has delegated non-overlapping subprefixes p:1::/64, p:2::/64 and p:3:/64 of its prefix p::/32 to its subordinate routers.

Figure 4 :

 4 Figure 4: Prefix Delegation and Address Assignment: a router assigning IP addresses from part of its prefix to network interfaces directly attached, and delegating another part of its prefix to a subordinate router.

Figure 5 :

 5 Figure 5: Classic IP Link Model: hosts (H) connected to the same link have assigned IP addresses from a common prefix, possibly assigned by a router (R).

Figure 6 :

 6 Figure 6: MANET: nodes (N) with MANET interfaces. The light grey area indicates the coverage area of each MANET interface.

Figure 7 :

 7 Figure 7: A MANET: four MANET routers (MRs), with MR 1 connected via a classical IP link to a non-MANET router R. Is this a "connected MANET"?

MR 1 Figure 8 :

 18 Figure 8: A Minimal "connected" MANET: the mobile router MR 1 has a single MANET interface and a single network interface towards a classic IP link.

Figure 10 :

 10 Figure 10: MANET routers: which are on the same hierarchical level thus having nonoverlapping prefixes.

At this point, the term "assigned" is used for both prefixes and addresses being "given" to a given MR. A distinction will be made in section

RR n°6376

A note may be in order to point out that an IP address is not on its own considered a unique identifier of an"end-point of communication", since that requires to not only identify the network interface of a networked entity, but also the process running on that entity that should receive a given IP datagram. In the Internet, an IP address AND a process identifier (a port number or a protocol number) serves as the unique identification of an "end-point of communication". Incidentally, port numbers and protocol numbers are, therefore, often also termed "code points".RR n°6376

Although not relevant for the present discussion in this memorandum, note that :: in general in IPv6 indicates any number of consecutive four-digit groups (in hexadecimal) whose value is zero. Thus, p::1 would be a valid way of representing an IPv6 address where the first bits are p, followed by one or more four-digit groups of zeros, followed by 1 RR n°6376

RR n°6376

INRIA

For details of manual and automatic allocation refer to[START_REF] Droms | RFC2131: Dynamic Host Configuration Protocol[END_REF],[START_REF] Droms | RFC3315: Dynamic Host Configuration Protocol for IPv6 (DHCPv6)[END_REF] RR n°6376

Acknowledgements

The architectural view presented in this memorandum is the result of exhaustive discussions within the IETF, in particular with the participants in the MANET and AUTOCONF working groups. Special thanks to Jari Arkko (Ericsson, Finland) and Dave Thaler (Microsoft, USA) for sharing their insights and for reviewing various pieces of this memorandum, and Francois Morain (Ecole Polytechnique, France), for providing clarifying questions to parts of this memorandum.

INRIA


Pablo Alvarez

Simon Rouzé

Matthieu Chabanas

Miguel Castro

Yohan Payan

Jean-Louis Dillenseger

Modeling lung deflation during video-assisted thoracoscopy surgery for the localization of small nodules

come

Introduction

Lung cancer remains as the worldwide leading cause of cancer death [START_REF] Dillenseger | Global Cancer Statistics[END_REF]. The disease is normally identified at late stages, where the 5-year survival rate lies between 6% and 18% [START_REF] Siegel | Cancer Statistics[END_REF]. However, survival opportunities might significantly increase if diagnosis and treatement are performed at early stages [START_REF] Henschke | Early Lung Cancer Action Project: overall design and findings from baseline screening[END_REF]. In this regard, screening programs have used low-dose CT to raise detections of early stage lung cancers [START_REF] Henschke | Early Lung Cancer Action Project: overall design and findings from baseline screening[END_REF]. In such scenarios, surgical resection through thoracotomy or videoassisted thoracoscopy (VATS) are the choice of treatment, the latter being a less invasive method with better and faster patient recovery [START_REF] Mckenna | New approaches to the minimally invasive treatment of lung cancer[END_REF]. One of the principal issues during a VATS resection comes from the localization of small, subsolid nodules [START_REF] Gould | Evaluation of Individuals With Pulmonary Nodules: When Is It Lung Cancer?[END_REF]. In practice, such difficulty is addressed by physically tagging the lesions (e.g., dyes, wires, coils) through an auxiliary, preoperative CT-guided procedure [START_REF] Zaman | In patients undergoing video-assisted thoracoscopic surgery excision, what is the best way to locate a subcentimetre solitary pulmonary nodule in order to achieve successful excision?[END_REF]. However, in addition to the associated risks (e.g. bleeding, pneumothorax), these methods are not fully reliable and result in further costs and organizational burdens. Intraoperative cone-beam CT (CBCT) has been previously used for guiding a variety of medical interventions (e.g. head and neck surgery, orthodontics). In addition, thanks to its low dose radiation and fast acquisition time, CBCT imaging might potentially guide the localization of small and subsolid nodules during a VATS procedure [START_REF] Uneri | Deformable registration of the inflated and deflated lung in cone-beam CT-guided thoracic surgery: Initial investigation of a combined model-and image-driven approach[END_REF][START_REF] Rouzé | Small pulmonary nodule localization with cone beam computed tomography during video-assisted thoracic surgery: a feasibility study[END_REF]. This approach will not only eliminate the hazardous preoperative interventions, but it will also allow a safer, more deterministic method for the localization of challenging nodules. However, during the VATS intervention, the surgeon purposely creates a pneumothorax that makes him space for the comfortable manipulation of the lung. This results in a total collapse of the lung into a deflated state, which invalidates any measurement formerly calculated via preoperative CT. This work introduces a biomechanical model of the lung that simulates its deflation process during a VATS intervention. The model can be used to predict the geometrical alterations of different lung structures, and more interestingly, the re-positioning of nodules within the parenchyma due to lung deflation. To the best of our knowledge, no previous attempt exists for the mechanical modeling of lung deflation for the localization of small, subsolid nodules during a VATS intervention.

Materials and Methods

The biomechanical model of lung deflation will be built upon a Finite Element Method (FEM) formulation. The main lung structures of concern for such model are the lobes and the initial levels of the airway tree. For the segmentation of the lobes, we have used a modified version of the Chest Imaging Platform, an open source plugin for the 3D Slicer software. In the case of the airway tree, a combination of Frangi et al. [START_REF] Frangi | Multiscale vessel enhancement filtering[END_REF] vesselness measure and a 3D region growing algorithm has been corresponding author: pablo.alvarez@etudiant.univ-rennes1.fr used. These two segmentations are then used to obtain a patient-specific mesh of tetrahedral Finite Elements for the inflated lung, i.e. the lung in its preoperative state. Although the mechanical behavior of the lung is extremely complex (e.g. very flexible tissue, very large deformations, influence of residual air, plasticity), in this preliminary work we have assumed linear-elasticity in the constitutive equation. Material properties for each Finite Element are estimated by merging information extracted from the preoperative image and information from previous works on the behaviour of lung tissue [START_REF] Ilegbusi | Modeling Airflow Using Subject-Specific 4DCT-Based Deformable Volumetric Lung Models[END_REF][START_REF] Naini | Measurement of Lung Hyperelastic Properties Using Inverse Finite Element Approach[END_REF]. Segmentations from the intraoperative CBCT are used to constraint the model using Lagrangian Multipliers. This FEM formulation is solved by using a co-rotational approach, whose efficiency allows us to comply with clinical requirements of time. Finally, the obtained deformation field is applied to preoperative nodule information to obtain the updated, intraoperative position of the nodule. The validation of our proposed approach will be performed using retrospective data of 4 patients that underwent a VATS intervention. This study will allow us to identify the influence of different factors (e.g. gravity, elasticity, boundary conditions) to take into account for an accurate modeling of the lung deflation. We intend to continue our research by using a more reliable constitutive equation. Our final goal in the long term is to develop an application for intraoperative modeldriven localization of lung nodules.


Konstantin Avrachenkov

Tejas Bodas

On the equivalence between multiclass processor sharing and random order scheduling policies

Consider a single server system serving a multiclass population. Some popular scheduling policies for such system are the discriminatory processor sharing (DPS), discriminatory random order service (DROS), generalized processor sharing (GPS) and weighted fair queueing (WFQ). In this paper, we propose two classes of policies, namely MPS (multiclass processor sharing) and MROS (multiclass random order service), that generalize the four policies mentioned above. For the special case when the multiclass population arrive according to Poisson processes and have independent and exponential service requirement with parameter µ, we show that the tail of the sojourn time distribution for a class i customer in a system with the MPS policy is a constant multiple of the tail of the waiting time distribution of a class i customer in a system with the MROS policy. This result implies that for a class i customer, the tail of the sojourn time distribution in a system with the DPS (GPS) scheduling policy is a constant multiple of the tail of the waiting time distribution in a system with the DROS (respectively WFQ) policy.

INTRODUCTION

Consider a single server system with multiclass customers. Some commonly used scheduling policies in such multiclass system are DPS, DROS, GPS and WFQ. A quick overview of these policies is as follows. Policies like GPS and DPS are variants of the processor sharing policy where the server can serve multiple customers from the system simultaneously. In case of GPS, a separate queue is maintained for each customer class and the total service capacity of the server is shared among customers of the different classes in proportion to predefined weights p i. The GPS scheduling policy is often considered as a generalization of the head-of-line processor sharing policy (HOLPS) as described in [START_REF] Aalto | Beyond Processor Sharing[END_REF][START_REF] Demers | Analysis and Simulation of a Fair Queueing Algorithm[END_REF][START_REF] Kumar | Communication Networking: An Analytical Approach[END_REF]. (Refer [START_REF] Fayolle | Two Coupled Processors: The reduction to a Riemann-Hilbert Problem[END_REF][START_REF] Morrison | Head of the line processor sharing for many symmetric queues with finite capacity[END_REF] for details about HOLPS). As a generalization of HOLPS, GPS maintains a FIFO scheduling policy within the queue of each class and only the head-of-line customers of different classes are allowed to share the processor. The share of the server for a head-of-line Class i customer is proportional to the weight p i and is independent of the number of other customers in the queue. The service rate received by the customer is precisely given by p i N j=1 p j φ j where φj = 1 if the queue has at least one class j customer and

Copyright is held by author/owner(s). φj = 0 otherwise. Refer Parekh and Gallager [START_REF] Parekh | A generalized processor sharing approach to flow control in integrated services networks: The single-node case[END_REF], Zhang et al. [START_REF] Zhang | Statistical analysis of generalized processor sharing scheduling discipline[END_REF] for an early analysis of the model.

In case of DPS, the total service capacity is shared among all the customers present in the system and not just among the head-of-line customers of different classes. The share of the server for a customer of a class is not only in proportion to the class weight, but also depends on the number of multiclass customers present in the queue. In particular, a Class i customer in the system is served at a rate of

p i N j=1 p j n j
where nj denotes the number of Class j customers in the system. The DPS system was first introduced by Kleinrock [START_REF] Kleinrock | Time-shared systems: a theoretical treatment[END_REF] and subsequently analyzed by several authors [START_REF] Avrachenkov | Discriminatory processor sharing revisited[END_REF][START_REF] Fayolle | Sharing a processor among many job classes[END_REF][START_REF] Haviv | Waiting times in queues with relative priorities[END_REF][START_REF] Haviv | Equilibrium strategies for processor sharing and random queues with relative priorities[END_REF][START_REF] Kim | Sojourn time distribution in M/M/1 queue with discriminatory processor sharing[END_REF]. See [START_REF] Altman | A survey on discriminatory processor sharing[END_REF] for a survey of various results on DPS.

The DROS and WFQ scheduling policies are also characterized by an associated weight for each customer class. However these policies are not a variant of the processor sharing policies and hence their respective server can only serve one customer at a time. The DROS and WFQ policies differ in their exact rule for choosing the next customer. In the DROS policy, the probability of choosing a customer for service depends on the weights and the number of customers of the different classes in the queue. A Class i customer is thus chosen with a probability of

p i N j=1 p j n j
where nj denotes the number of Class j customers waiting in the system for service. DROS policy is also know as relative priority policy and was first introduced by Haviv and wan der Wal [START_REF] Haviv | Equilibrium strategies for processor sharing and random queues with relative priorities[END_REF]. For more analysis of this policy we refer to [START_REF] Haviv | Waiting times in queues with relative priorities[END_REF][START_REF] Kim | Analysis of M/G/1 queue with discriminatory random order service policy[END_REF]. In the WFQ policy, a separate queue for each class is maintained and the next customer is chosen randomly from among the head-ofline customers of different classes. As in case of the GPS scheduling policy, a FIFO scheduling policy is used within each queue for a class. WFQ can be seen as a packetised version of GPS and the probability of choosing a head-ofline Class i customer for service is given by p i N j=1 p j φ j where φ j is as defined earlier. Refer Demers [START_REF] Demers | Analysis and Simulation of a Fair Queueing Algorithm[END_REF] for the detailed analysis of the WFQ policy.

It is interesting to note that for a Class i customer, the service rate received in DPS and the probability of being chosen next for service in case of DROS is given by

p i N j=1 p j n j
. Similarly, the service rate received in GPS and the probability of being chosen next for service in case of WFQ is

p i N j=1 p j φ j .
This similarity in the scheduling rules motivates us to compare the tail of the waiting time and sojourn time distributions of the multiclass customers with these scheduling policies. Assuming identically distributed service requirements for all customers, we will show that the tail of the waiting time distribution of a Class i customer in a system with DROS (WFQ) scheduling policy is ρ times the tail of the sojourn time distribution of any Class i customer with DPS (resp. GPS) scheduling policy. This is a generalization of [START_REF] Borst | The equivalence between processor sharing and service in random order[END_REF], where the equivalence has been established between single-class processor sharing and random order service discipline.

Organization: In the next section, we introduce a generalized notion of multiclass processor sharing (MPS) and random order service (MROS) policies. The DPS, GPS, DROS and WFQ policies will turn out to be special cases of MPS and MROS. In Section 3, we show that the tail of the sojourn time distribution of a Class i customer with MPS scheduling is equivalent to the tail of the waiting time distribution of a Class i customer with MROS policy. As a special case, this proves the mentioned equivalences among the four multiclass scheduling policies.

Notation: We use N to denote the total number of customer classes in the system. Let λ i denote the arrival rate for a Class i customer, i = 1 . . . N. Let N i=1 λi = Λ, ρi = λ i µ and ρ = N i=1 ρi. Further, let pi denote a weight parameter associated with a Class i customer.

Assumptions:

We assume that the service requirement of each customer is independent and exponentially distributed with rate µ. Thus the service requirements are independent of their class. We also assume that customers from different classes arrive according to independent Poisson processes. For the purpose of stability, we assume that Λ < µ.

GENERALIZED MULTICLASS SCHEDUL-ING POLICIES

In this section, we will describe two multiclass scheduling policies that are a generalization of policies such as DPS, DROS, GPS and WFQ. The two policies are based on the processor sharing and random order service mechanism and will be labeled as MPS and MROS respectively.

The MPS scheduling policy is a multiclass processor sharing policy where the server can serve multiple customers simultaneously. A separate queue for each customer class is maintained and a FIFO scheduling policy is used within each queue of a class. The MPS scheduling policy is parameterized by a vector ᾱ = (α 1, . . . , αN ) that characterizes the maximum permisible number of customers of each class that can be served simultaneously with other customers. We shall henceforth use the notation MPS( ᾱ) when we talk about an MPS policy with parameter ᾱ. Let n i denote the instantaneous number of Class i customers in the queue and n := (n 1, . . . , nN ) denotes the corresponding state in the MPS system. Let β i(n) denote the number of Class i customers under service when the state of the MPS system is n. Then, clearly β i(n) = min (ni, αi). In other words, if n i ≤ αi, then all the Class i customers present in the queue are being served simultaneously for i = 1, . . . , N. However if n i > αi, then only the first αi customers of Class i in its queue are served simultaneously. It should be noted that due to the FIFO policy within each queue of a class, only the first β i(n) customers in the queue are served at any time. To lighten some of the notation, we shall drop the dependence on n and use only β i when the context is clear. For an MPS( ᾱ) scheduling policy in state n, the service rate received by a particular Class i customer which is in service is given by

p i N j=1 p j β j
. When αi = ∞, for i = 1 to N, the corresponding scheduling policy will be denoted by MPS( ∞). In this case, β i = min (ni, ∞) = ni and therefore MPS( ∞) corresponds to the DPS scheduling policy. Similarly if ē = (1, . . . , 1), then MPS(ē) corresponds to the GPS scheduling policy where only the head-of-line customers of each class can be served.

In a similar manner, we can define the MROS( ᾱ) scheduling policy where ᾱ = (α 1, . . . , αN ) denotes the vector of multiclass customers from which the subsequent customer is chosen for service. As in case of the MPS policy, note that a separate FIFO queue for each customer class is also maintained for the MROS system. At any given time, the first β i = min (ni, αi) customers are candidates for being chosen for service while the remaining n i -βi customers have to wait for their turn. Note that the state n for an MROS( ᾱ) scheduling policy denotes the vector of waiting multiclass customers present in the system. In the MROS( ᾱ) system, a Class i customer within the first β i customers in its queue will be chosen next for service with probability

p i N j=1 p j β j .
As in case of the MPS scheduling, MROS( ∞) corresponds to the DROS policy whereas MROS(ē) corresponds to the WFQ policy.

Remark 1. A policy closely related to the MPS discipline is the limited processor sharing (LPS) policy. LPS is a single class processor sharing policy parametrized by an integer c where c denotes the maximum number of customers that can be served simultaneously. Here c = ∞ corresponds to the processor sharing policy while c = 1 corresponds to FCFS policy. LPS can also be viewed as a special case of the MPS policy when there is a single service class for the arriving customers. See [START_REF] Halfin | Expected response times in a non-symmetric time sharing queue with a limited number of service positions[END_REF][START_REF] Zhang | Diffusion limits of limited processor sharing queues[END_REF] more more details about the LPS-c policy.

Having introduced the generalized multiclass scheduling policies, we shall now establish an equivalence relation between the tail of the sojourn time distribution of a Class i customer in MPS system with the tail of the waiting time distribution of a Class i customer in MROS system.

COMPARING THE SOJOURN AND WAIT-ING TIME DISTRIBUTIONS IN MPS AND MROS

The analysis in this section is inspired from that in [START_REF] Borst | The equivalence between processor sharing and service in random order[END_REF] where a similar result is established for the case of a single class of population. For a given state of n = (n 1, . . . , nN ), define n := N i=1 ni. Let random variable S i (ᾱ, n) denote the conditional sojourn time experienced by an arriving Class i customer that sees the MP S(ᾱ) system in state n. The corresponding unconditional random variable will be denoted by S i (ᾱ). We shall occasionally use the notation MP S(ᾱ, n) to denote the MPS( ᾱ) system with n customers. Along similar lines, let the random variable W i (ᾱ, n) denote waiting time (time until chosen for service) experienced by an arriving Class i customer that sees the MROS( ᾱ) system in state n, i.e., it sees a vector of n waiting customers in the system. This system will be often denoted as M ROS(ᾱ, n) and the unconditional random variable will be denoted by W i (ᾱ). Let P and P ′ denote the probability distribution of the random variables S i (ᾱ, n) and W i (ᾱ, n) respectively.

(The dependence of these distributions on n have been suppressed for notational convenience.) We now state the main result of this paper. Theorem 1. ρP (S i (ᾱ) > t) = P (W i (ᾱ) > t) for i = 1, . . . , N.

Proof. As in [START_REF] Borst | The equivalence between processor sharing and service in random order[END_REF], our aim is to first provide a coupling Ŝi (ᾱ, n), Ŵi (ᾱ, n) with the corresponding law denoted by P such that

• Ŝi (ᾱ, n) D = S i (ᾱ, n) and Ŵi (ᾱ, n) D = W i (ᾱ, n) • P Ŝi (ᾱ, n) = Ŵi (ᾱ, n) = 1
The second requirement will help us to show that the two distributions P and P ′ are equal. This follows from the coupling inequality (see [START_REF] Lindvall | Lectures on the coupling method[END_REF] for more on coupling inequalities)

P -P ′ ≤ 2 P Ŝi (ᾱ, n) ̸ = Ŵi (ᾱ, n) . ( 1
)
Such a coupling is precisely obtained as follows.

Consider two tagged Class i customers X and Y that arrive to a MP S(ᾱ, n) and a M ROS(ᾱ, n) system respectively. This means that at the arrival instant of customer X in the MP S(ᾱ, n) system, there are n i Class i customers already present in the system. Similarly, at the arrival instant of customer Y in M ROS(ᾱ, n), there are n i customers of Class i that are waiting for service in the queue. Recall that β = (β 1, . . . , βN ) where βi in the MPS system denotes the number of Class i customers that are receiving service. In the MROS system, β i denotes those (waiting) Class i customers from which the next customer could be chosen. Note that since N i=1 ni = n, with the arrival of customer X, the MP S(ᾱ, n) system has n + 1 customers. Similarly, with the arrival of customer Y, the M ROS(ᾱ, n) system has n + 2 customers of which one customer is in service and the remaining n + 1 customers (including customer Y) are waiting for service. We will now specify the rule for forming the required coupling. Since the customers can be distinguished by their class index and also the position in their respective queues, we couple the n+1 customers in MP S(ᾱ, n) with the n+1 waiting customers in the M ROS(ᾱ, n) system based on their class and queue position. The coupling must be such that the coupled customers belong to the same class and invariably have the same queue position in their respective queues. It goes without saying that the tagged customers X and Y are also coupled. As in [START_REF] Borst | The equivalence between processor sharing and service in random order[END_REF], we also couple the subsequent arriving customers and let D 1, D2 . . . denote i.i.d random variables with an exponential distribution of rate µ. These random variables correspond to service times of a customer in service in M ROS(ᾱ). At the service completion epoch, pick a pair of coupled customers randomly. This random picking is with a distribution such that the chosen pair is of Class i with probability

p i N j=1 p j β j
. When the randomly chosen pair is of Class i, a class i customer departs from the MPS system while such a customer is taken for service in the MROS system. This process is repeated till the tagged pair (X, Y ) leaves the system. Clearly, this joint probability space is so constructed that the random variables Ŝi (ᾱ, n) = Ŵi (ᾱ, n) P-a.s. From Eq. ( 1), this implies that

S i (ᾱ, n) D = W i (ᾱ, n). (2)
Now let random vectors N MP S (resp. N M ROS

1

) denote the vector of multiclass customers present in the system in steady state (resp. waiting in the system in steady state in MROS). The subscript 1 in N M ROS 1 is used to indicate a busy server. Since the arrival process is Poisson, the unconditional probabilities are given by the following

P (S i (ᾱ) > t) = n P (N MP S = n)P (S i (ᾱ, n) > t). (3)
Similarly, we have 2), the statement of the theorem follows and this would complete the proof. In the following lemma, we shall prove that indeed P (N M ROS

P (W i (ᾱ) > t) = n P (N M ROS 1 = n)P (W i (ᾱ, n) > t). (4) Now if P (N M ROS 1 = n) = ρP (N MP S = n) is true, then from Eq. (
1 = n) = ρP (N MP S = n). Lemma 1. P (N M ROS 1 = n) = ρP (N MP S = n) for n such that |n| ≥ 0.
Proof. We first simplify the notations as follows. Let π(n) := P (N MP S = n) and π(1, n) := P (N M ROS 1 = n). Let π(0, 0) denote the probability that the MROS system has no customers and is idle. The statement of the lemma now requires us to prove that π(1, n) = ρπ(n). To prove this result, consider the balance equation for the MPS system where π shall denote the stationary invariant distribution for the system. The assumption Λ < µ implies that the underlying Markov process is ergodic and hence the stationary distribution π is unique. For n such that |n| ≥ 0, the global balance equations for the MPS( ᾱ) system are

(Λ + N i=1 βi(n)pi N j=1 pjβj(n) µ {|n|>0} )π(n) = N i=1 λi {n i >0} π(n -ei) + N i=1 βi(n + ei)pi
Additionally, the idle system should satisfy Λπ(0, 0) = µπ(1, 0) [START_REF] Kleinrock | Time-shared systems: a theoretical treatment[END_REF] where π(0, 0) = 1ρ is the probability that the system is empty. Now again, the assumption Λ < µ implies that the underlying Markov process is ergodic and hence the stationary distribution π is also unique. Therefore to prove the lemma, it is sufficient to check if the global balance equations for the MROS system given by Eq. ( 6) are satisfied when π(1, n) = ρπ(n). Now from Eq. ( 6) and assuming that π(1, n) = ρπ(n), we have

(Λ + µ {|n|>0} )π(1, n) - N i=1 λi {n i >0} π(1, n -ei) - N i=1 βi(n + ei)pi N j=1 pjβj(n + ei) µπ(1, n + ei) = (Λ + µ {|n|>0} )ρπ(n) - N i=1 λi {n i >0} ρπ(n -ei) - N i=1 βi(n + ei)pi N j=1 pjβj(n + ei) µρπ(n + ei) = 0.
The last equality follows from Eq. ( 5) after dividing throughout by ρ. Similarly, Λπ(0, 0)µπ(1, 0) = Λπ(0, 0)µρπ( 0) = µ (ρπ(0, 0)ρπ( 0))

= µ (ρπ(0, 0) -ρ(1 -ρ)) = 0. (8)
Here the third equality is from the fact that π( 0) = (1-ρ) is the probability that the MPS( ᾱ) system is empty. Clearly, substituting π(1, n) = ρπ(n), satisfies the balance equations for the MROS system. Since π is the unique invariant distribution, the statement of the lemma follows.

We now have the following corollary that establishes the desired equivalence between DPS (GPS) and DROS (resp. WFQ) scheduling policies. Note that the result is true only for the case when all customers have identically distributed service requirements. The equivalence result is not true in general when the customer classes differ in their service requirements.

Corollary 1.

• ρP (S i ( ∞) > t) = P (W i ( ∞) > t)
where S i ( ∞) denotes the sojourn time of a Class i customer in DPS system and W i ( ∞) denotes the waiting time of a Class i customer in DROS system.

• ρP (S i (ē) > t) = P (W i (ē) > t) where S i (ē) denotes the sojourn time of a Class i customer in GPS system and W i (ē) denotes the waiting time of a Class i customer in WFQ system.

DISCUSSION

In this paper, we have proposed two multiclass policies, namely MPS and MROS, that generalize some important multiclass policies from the literature. Our policies are parameterized by a vector ᾱ that can be used to control performance metrics like the mean delay or mean waiting time per class. Restricting to the special case where the multiclass customers arrive according to a Poisson process and have indepndent and exponential service requirements, we show that the tail of the sojourn time distribution for a class i customer in a system with the MPS policy is a constant multiple of the tail of the waiting time distribution of a class i customer in a system with the MROS policy. As special cases, we have thus proved the above equivalence between DPS (GPS) and DROS (resp. WFQ) scheduling policies.

It is worth mentioning that Borst et al [START_REF] Borst | The equivalence between processor sharing and service in random order[END_REF] have shown the sojourn time equivalence between ROS and processor sharing for a more general case when the arrival process is a general renewal process. While our analysis for MPS and MROS assumes a Poisson arrival process, it would be of interest to investigate if our equivalence result is true when the arrival process is a general renewal process. This is part of future work.

N

  j=1 pjβj(n + ei) µπ(n + ei). can be written as(Λ + µ {|n|>0} )π(n) = N i=1 λi {n i >0} π(nei) (5) + N i=1 βi(n + ei)pi N j=1 pjβj(n + ei) µπ(n + ei).Similarly, the global balance equations for the MROS( ᾱ) system are as follows for n such that |n| ≥ 0. (Λ + µ {|n|>0} )π(1, n) = N i=1 λi {n i >0} π(1, nei) + N i=1 βi(n + ei)pi N j=1 pjβj(n + ei) µπ(1, n + ei).

Acknowledgements

Both authors would like to thank Dr. Rudesindo Queija from CWI, Amsterdam for several discussions on this work. Research for the second author is partially supported by the French Agence Nationale de la Recherche (ANR) through the project ANR-15-CE25-0004 (ANR JCJC RACON). The authors would also like to acknowledge the support of CE-FIPRA, an Indo-French centre for promotion of advanced research, specifically grant FC/DST-Inria-2016-01/448.


Yohan Payan

Technological innovations and biomechanics: Development and optimization in pressure ulcer prevention

published or not. The documents may come

Technological innovations and biomechanics: Development and optimization in pressure ulcer prevention

Introduction:

While in interactions with external supports such as shoes, seats or mattresses, human soft tissue can be submitted to large stresses and strains that may affect tissue integrity, especially for people suffering from sensory loss and/or peripheral vascular disease. Basic science has recently made substantial progress as concerns the etiology of deep tissues injuries (DTI). Mechanical compression, ischemia, lymphatic blockage and reperfusion are indeed potential factors triggering DTI (Oomens 2015). Among these factors, the most dangerous one is probably direct mechanical compression that results in high deformations of the subcutaneous tissue layers and that can damage soft tissue in a very short period of time (some minutes).

Methods:

We are today fairly confident in the fact that an efficient pressure ulcer prevention medical device should include, at least, four components:

(1) a compliant support (shoe, seat, mattress) that optimizes the way pressure forces apply onto skin surface and that limits any stress concentration;

(2) an on-line embedded quantitative measurement of the pressure at the support/skin interface;

(3) an on-line estimation of the internal soft tissue deformations;

(4) the estimation of the risk for DTI and if necessary, an alarm sent to the person.

Results:

This invited talk will focus on the solutions and bottlenecks towards an on-line estimation of the risks for DTI. If some new technologies and products can now propose embedded pressure mat to measure the pressure at the support/skin interfaces, a relevant biomarker for estimating tissue internal strain is unfortunately still lacking. The solution is the design of a subject-specific biomechanical model of the bony prominence / soft tissue / support interactions computing in real time tissue internal strains. The associated reminding bottlenecks will be discussed: How to generate, in a clinical routine, a subject-specific biomechanical model taking into account the specific anatomy of the subject, in terms of tissue layers (skin, fat, muscles) or shapes of the bony surfaces? How to get such anatomical information without the use of a complex and costly MRI or CT exam? How to run in real time the non-linear biomechanical Finite Element models required to compute internal strains? How to define a subject-specific threshold in terms of maximal strains values?

Conclusions:

This talk will illustrate the bottleneck questions raised above with some results obtained by our group using biomechanical models of the foot and buttock soft tissues.