B Storer

C Pignataro

Ed Category

: Standards

Track M Dos

Santos Cisco

Systems B Stevant

Ed L Toutain

J Tremblay

Network Working Group

This document describes the framework of the Softwire "Hub and Spoke" solution with the Layer Two Tunneling Protocol version 2 (L2TPv2). The implementation details specified in this document should be followed to achieve interoperability among different vendor implementations.

Introduction

The Softwires Working Group has selected Layer Two Tunneling Protocol version 2 (L2TPv2) as the phase 1 protocol to be deployed in the Softwire "Hub and Spoke" solution space. This document describes the framework for the L2TPv2 "Hub and Spoke" solution, and the implementation details specified in this document should be followed to achieve interoperability among different vendor implementations.

In the "Hub and Spoke" solution space, a Softwire is established to provide the home network with IPv4 connectivity across an IPv6-only access network, or IPv6 connectivity across an IPv4-only access network. When L2TPv2 is used in the Softwire context, the voluntary tunneling model applies. The Softwire Initiator (SI) at the home network takes the role of the L2TP Access Concentrator (LAC) client (initiating both the L2TP tunnel/session and the PPP link) while the Softwire Concentrator (SC) at the ISP takes the role of the L2TP Network Server (LNS). The terms voluntary tunneling and compulsory tunneling are defined in Section 1.1 of [START_REF] Patel | Securing L2TP using IPsec[END_REF]. Since the L2TPv2 compulsory tunneling model does not apply to Softwires, it SHOULD NOT be requested or honored. This document identifies all the voluntary tunneling related L2TPv2 attributes that apply to Softwires and specifies the handling mechanism for such attributes in order to avoid ambiguities in implementations. This document also identifies the set of L2TPv2 attributes specific to the compulsory tunneling model that does not apply to Softwires and specifies the mechanism to ignore or nullify their effect within the Softwire context.

The SI and SC MUST follow the L2TPv2 operations described in [RFC2661] when performing Softwire establishment, teardown, and Operations, Administration, and Management (OAM). With L2TPv2, a Softwire consists of an L2TPv2 Control Connection (also referred to as Control Channel), a single L2TPv2 Session, and the PPP link negotiated over the Session. To establish the Softwire, the SI first initiates an L2TPv2 Control Channel to the SC, which accepts the request and terminates the Control Channel. L2TPv2 supports an optional mutual Control Channel authentication that allows both SI and SC to validate each other's identity at the initial phase of hand-shaking before proceeding with Control Channel establishment. After the L2TPv2 Control Channel is established between the SI and SC, the SI initiates an L2TPv2 Session to the SC. Then the PPP/IP link is negotiated over the L2TPv2 Session between the SI and SC. After the PPP/IP link is established, it acts as the Softwire between the SI and SC for tunneling IP traffic of one Address Family (AF) across the access network of another Address Family. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. L2TPv2 supports an optional in-band keepalive mechanism that injects HELLO control messages after a specified period of time has elapsed since the last data or control message was received on a tunnel (see Section 5.5 of [RFC2661]). If the HELLO control message is not reliably delivered, then the Control Channel and its Session will be torn down. In the Softwire context, the L2TPv2 keepalive is used to monitor the connectivity status between the SI and SC and/or as a refresh mechanism for any NAT/NAPT translation entry along the access link.

LCP ECHO offers a similar mechanism to monitor the connectivity status, as described in [RFC1661]. other possible protocols involved to complete the solution. This section examines the four scenarios for both IPv6-over-IPv4 (Section 3.1) and IPv4-over-IPv6 (Section 3.2) encapsulations.

3.1. IPv6-over-IPv4 Softwires with L2TPv2

The following sub-sections cover IPv6 connectivity (SPH) across an IPv4-only access network (STH) using a Softwire. -----------------||-----------------||---------- ----------------- ---------------- -----------------||-----------------||--------------------- Interface-Identifier to the router CPE or perform uniqueness validation for the two interface identifiers at the two PPP ends [START_REF] Varada | IP Version 6 over PPP[END_REF]. After IPv6-over-PPP is up, IPv6 Stateless Address Autoconfiguration / Neighbor Discovery runs over the IPv6-over-PPP link, and the LNS can inform the router CPE of a prefix to use for stateless address autoconfiguration through a Router Advertisement (RA). DHCPv6 can be used to perform IPv6 Prefix Delegation (e.g., delegating a prefix to be used within the home network [START_REF] Troan | IPv6 Prefix Options for Dynamic Host Configuration Protocol (DHCP) version 6[END_REF]) and convey other non-address configuration options (such as DNS [START_REF] Droms | DNS Configuration options for Dynamic Host Configuration Protocol for IPv6 (DHCPv6)[END_REF]) to the router CPE.

| I SC SI N +-----+ +----------+ T | | | v4/v6 | E <==[ IPv6 ]....|v4/v6|....[IPv4-only]....| host CPE | R [network] | | [ network ] | | N | LNS | |LAC Client| E +-----+ +----------+ T _ _ _ _ _ _ _ _ _ ()_ _ _ _ _ _ _ _ _() <--IPv6 traffic PPP o L2TPv2 o UDP o IPv4 (SPH) Softwire <-
| I SC SI N +-----+ +----------+ T | | | v4/v6 | +-----+ E <==[ IPv6 ]....|v4/v6|....[IPv4-only]....| CPE |----|v4/v6| R [network] | | [ network ] | | | host| N | LNS | |LAC Client| +-----+ E +-----+ +----------+ T _ _ _ _ _ _ _ _ _ ()_ _ _ _ _ _ _ _ _() <--------IPv6 traffic PPP o L2TPv2 o UDP o IPv4 (SPH) Softwire <------------------> IPV6CP: capable of /64 Intf-Id assignment or uniqueness check |------------------>/64 prefix RA |------------------>/48 prefix, DHCPv6 DNS, etc. |------->/64 prefix RA |-------> DNS, etc. DHCPv4/v6

Host behind CPE as Softwire Initiator

The CPE is IPv4-only. The Softwire Initiator (SI) is a dual-stack host (behind the IPv4-only CPE), which acts as an IPv6 host CPE. The IPv4 traffic SHOULD NOT traverse the Softwire. See Figure 3. -----------------||----------------------------||---------- ----------------------------->DNS, etc. DHCPv6 Interface-Identifier to the host or perform uniqueness validation for the two interface identifiers at the two PPP ends [START_REF] Varada | IP Version 6 over PPP[END_REF]. After IPv6-over-PPP is up, IPv6 Stateless Address Autoconfiguration / Neighbor Discovery runs over the IPv6-over-PPP link, and the LNS can inform the host of a prefix to use for stateless address autoconfiguration through a Router Advertisement (RA) while other non-address configuration options (such as DNS [START_REF] Droms | DNS Configuration options for Dynamic Host Configuration Protocol for IPv6 (DHCPv6)[END_REF]) can be conveyed to the host via DHCPv6.

IPv6 or dual-stack IPv4-only dual-stack |-

| I SC SI N +-----+ +----------+ T | | +-------+ | v4/v6 | E <==[ IPv6 ]....|v4/v6|....[IPv4-only]....|v4-only|--| host | R [network] | | [ network ] | CPE | | | N | LNS | +-------+ |LAC Client| E +-----+ +----------+ T _ _ _ _ _ _ _ _ _ _ _ _ _ _ ()_ _ _ _ _ _ _ _ _ _ _ _ _ _() <--IPv6 PPP o L2TPv2 o UDP o IPv4 traffic Softwire (SPH) <------------------------------> IPV6CP: capable of /64 Intf-Id assignment or uniqueness check |------------------------------>/64 prefix RA |-

Router behind CPE as Softwire Initiator

The CPE is IPv4-only. -----------------||-------------------------||------------- In this scenario, after the L2TPv2 Control Channel and Session establishment and PPP LCP negotiation (and optionally PPP Authentication) are successful, IPV6CP negotiates IPv6-over-PPP, which also provides the capability for the ISP to assign the 64-bit Interface-Identifier to the v4/v6 router or perform uniqueness validation for the two interface identifiers at the two PPP ends [START_REF] Varada | IP Version 6 over PPP[END_REF] (RA). DHCPv6 can be used to perform IPv6 Prefix Delegation (e.g., delegating a prefix to be used within the home network [START_REF] Troan | IPv6 Prefix Options for Dynamic Host Configuration Protocol (DHCP) version 6[END_REF]) and convey other non-address configuration options (such as DNS [START_REF] Droms | DNS Configuration options for Dynamic Host Configuration Protocol for IPv6 (DHCPv6)[END_REF]) to the v4/v6 router.

| I SC SI N +-----+ +----------+ T | | +-------+ | v4/v6 | E <==[ IPv6 ]....|v4/v6|..[IPv4-only]..|v4-only|---| router | R [network] | | [ network ] | CPE | | | | N | LNS | +-------+ | |LAC Client| E +-----+ | +----------+ T | ---------+-----+ |v4/v6| | host| _ _ _ _ _ _ _ _ _ _ _ _ _ +-----+ ()_ _ _ _ _ _ _ _ _ _ _ _ _() <--IPv6 PPP o L2TPv2 o UDP o IPv4 traffic Softwire (SPH) <---------------------------> IPV6CP: capable of /64 Intf-Id assignment or uniqueness check |--------------------------->/64 prefix RA |--------------------------->/48 prefix, DHCPv6 DNS, etc. |----> /64 RA prefix |----> DNS, DHCPv6 etc.

IPv4-over-IPv6 Softwires with L2TPv2

The following sub-sections cover IPv4 connectivity (SPH) across an IPv6-only access network (STH) using a Softwire.

Host CPE as Softwire Initiator

The Softwire Initiator (SI) is the host CPE (directly connected to a modem), which is dual-stack. There is no other gateway device. The IPv6 traffic SHOULD NOT traverse the Softwire. See Figure 5. -----------------||-----------------||---------- ----------------- -----------------||-----------------||------------------- -----------------||----------------------------||---------- -----------------||-------------------------||------------

IPv4 or dual-stack IPv6-only dual-stack |-

| I SC SI N +-----+ +----------+ T | | | v4/v6 | E <==[ IPv4 ]....|v4/v6|....[IPv6-only]....| host CPE | R [network] | | [ network ] | | N | LNS | |LAC Client| E +-----+ +----------+ T _ _ _ _ _ _ _ _ _ ()_ _ _ _ _ _ _ _ _() <--IPv4 traffic PPP o L2TPv2 o UDP o IPv6 (SPH) Softwire <-
| I SC SI N +-----+ +----------+ T | | | v4/v6 | +-----+ E <==[ IPv4 ]....|v4/v6|....[IPv6-only]....| CPE |--|v4/v6| R [network] | | [ network ] | | | host| N | LNS | |LAC Client| +-----+ E +-----+ +----------+ T _ _ _ _ _ _ _ _ _ ()_ _ _ _ _ _ _ _ _() <---------IPv4 traffic PPP o L2TPv2 o UDP o IPv6 (SPH) Softwire <------------------> IPCP: capable of global IP assignment and DNS, etc. |------------------> DHCPv4: prefix, mask, PD private/ |------>
| I SC SI N +-----+ +----------+ T | | +-------+ | v4/v6 | E <==[ IPv4 ]....|v4/v6|....[IPv6-only]....|v6-only|--| host | R [network] | | [ network ] | CPE | | | N | LNS | +-------+ |LAC Client| E +-----+ +----------+ T _ _ _ _ _ _ _ _ _ _ _ _ _ _ ()_ _ _ _ _ _ _ _ _ _ _ _ _ _() <--IPv4 PPP o L2TPv2 o UDP o IPv6 traffic Softwire (SPH) <------------------------------
| I SC SI N +-----+ +----------+ T | | +-------+ | v4/v6 | E <==[ IPv4 ]....|v4/v6|..[IPv6-only]..|v6-only|---| router | R [network] | | [ network ] | CPE | | | | N | LNS | +-------+ | |LAC Client| E +-----+ | +----------+ T | --------+-----+ |v4/v6| | host| _ _ _ _ _ _ _ _ _ _ _ _ _ +-----+ ()_ _ _ _ _ _ _ _ _ _ _ _ _() <---IPv4 PPP o L2TPv2 o UDP o IPv4 traffic Softwire (SPH)
<---------------------------> IPCP: assigns global IP address and DNS, etc. --------------------------

|-

Softwire Establishment

A Softwire is established in three distinct steps, potentially preceded by an optional IPsec-related step 0 (see Figure 9). First, an L2TPv2 tunnel with a single session is established from the SI to the SC. Second, a PPP session is established over the L2TPv2 session and the SI obtains an address. Third, the SI optionally gets other information through DHCP such as a delegated prefix and DNS servers. -------------PPP------------- ).

SC SI | | |<-------------IKEv1------------->| Step 0 | | IPsec SA establishment | | (optional) | | |<-------------L2TPv2------------>| Step 1 | | L2TPv2 Tunnel establishment | | |<-

L2TPv2 Tunnel Setup

L2TPv2 [RFC2661] was originally designed to provide private network access to end users connected to a public network. In the L2TPv2 incoming call model, the end user makes a connection to an L2TP Access Concentrator (LAC). The LAC then initiates an L2TPv2 tunnel to an L2TP Network Server (LNS). The LNS then transfers end-user traffic between the L2TPv2 tunnel and the private network.

In the Softwire "Hub and Spoke" model, the Softwire Initiator (SI) assumes the role of the LAC Client and the Softwire Concentrator (SC) assumes the role of the LNS.

In the Softwire model, an L2TPv2 packet MUST be carried over UDP. The underlying version of the IP protocol may be IPv4 or IPv6, depending on the Softwire scenario.

In the following sections, the term "Tunnel" follows the definition from Section 1.2 of [RFC2661], namely: "The Tunnel consists of a Control Connection and zero or more L2TP Sessions".

Tunnel Establishment

Figure 11 describes the messages exchanged and Attribute Value Pairs (AVPs) used to establish a tunnel between an SI (LAC) and an SC (LNS). The messages and AVPs described here are only a subset of those defined in [RFC2661]. This is because Softwires use only a subset of the L2TPv2 functionality. The subset of L2TP Control Connection Management AVPs that is applicable to Softwires is grouped into Required AVPs and Optional AVPs on a per-control-message basis (see Figure 11). For each control message, Required AVPs include all the "MUST be present" AVPs from [RFC2661] for that control message, and Optional AVPs include the "MAY be present" AVPs from [RFC2661] that are used in the Softwire context on that control message. Note that in the Softwire environment, the SI always initiates the tunnel. L2TPv2 AVPs SHOULD NOT be hidden. --------SCCRQ--------- In L2TPv2, generally, the tunnel between an LAC and LNS may carry the data of multiple users. Each of these users is represented by an L2TPv2 session within the tunnel. In the Softwire environment, the tunnel carries the information of a single user. Consequently, there is only one L2TPv2 session per tunnel. Figure 12 describes the messages exchanged and the AVPs used to establish a session between an SI (LAC) and an SC (LNS). The messages and AVPs described here are only a subset of those defined in [RFC2661]. This is because Softwires use only a subset of the L2TPv2 functionality. The subset of L2TP Call Management (i.e., Session Management) AVPs that is applicable to Softwires is grouped into Required AVPs and Optional AVPs on a per-control-message basis (see Figure 12). For each -------ICRQ--------- Framing Capabilities AVP Both the synchronous (S) and asynchronous (A) bits SHOULD be set to 1. This AVP SHOULD be ignored by the receiver.

Framing Type AVP

The synchronous bit SHOULD be set to 1 and the asynchronous bit to 0. This AVP SHOULD be ignored by the receiver.

( AVPs that are relevant to Softwires were covered in Sections 5.1.1, 5.1.1.1, and 5.1.1.2. Softwire implementations SHOULD NOT send AVPs that are not relevant to Softwires. However, they SHOULD ignore them when they are received. This will simplify the creation of Softwire applications that build upon existing L2TPv2 implementations.

Tunnel Maintenance

Periodically, the SI/SC MUST transmit a message to the peer to detect tunnel or peer failure and maintain NAT/NAPT contexts. The L2TPv2 HELLO message provides a simple, low-overhead method of doing this.

The default values specified in [RFC2661] for L2TPv2 HELLO messages could result in a dead-end detection time of 83 seconds. Although these retransmission timers and counters SHOULD be configurable (see Section 5.8 of [RFC2661]), these values may not be adapted for all situations, where a quicker dead-end detection is required, or where NAT/NAPT context needs to be refreshed more frequently. In such cases, the SI/SC MAY use, in combination with L2TPv2 HELLO, LCP ECHO messages (Echo-Request and Echo-Reply codes) described in [RFC1661]. When used, LCP ECHO messages SHOULD have a re-emission timer lower than the value for L2TPv2 HELLO messages. The default value recommended in Section 6.5 of [RFC2661] for the HELLO message retransmission interval is 60 seconds. When used, a set of suggested values (included here only for guidance) for the LCP ECHO message request interval is a default of 30 seconds, a minimum of 10 seconds, and a maximum of the lesser of the configured L2TPv2 HELLO retransmission interval and 60 seconds.

Tunnel Teardown

Either the SI or SC can tear down the session and tunnel. This is done as specified in Section 5.7 of [RFC2661], by sending a StopCCN control message. There is no action specific to Softwires in this case.

Additional L2TPv2 Considerations

In the Softwire "Hub and Spoke" framework, L2TPv2 is layered on top of UDP, as part of an IP-in-IP tunnel; Section 8.1 of [RFC2661] describes L2TP over UDP/IP. Therefore, the UDP guidelines specified in [START_REF] Eggert | Unicast UDP Usage Guidelines for Application Designers[END_REF] apply, as they pertain to the UDP tunneling scenarios carrying IP-based traffic. Section 3.1.3 of [START_REF] Eggert | Unicast UDP Usage Guidelines for Application Designers[END_REF] specifies that for this case, specific congestion control mechanisms for the tunnel are not necessary. Additionally, Section 3.2 of [START_REF] Eggert | Unicast UDP Usage Guidelines for Application Designers[END_REF] provides message size guidelines for the encapsulating (outer) datagrams, including the recommendation to implement Path MTU Discovery (PMTUD).

PPP Connection

This section describes the PPP negotiations between the SI and SC in the Softwire context.

MTU

The MTU of the PPP link presented to the SPH SHOULD be the link MTU minus the size of the IP, UDP, L2TPv2, and PPP headers together. On an IPv4 link with an MTU equal to 1500 bytes, this could typically mean a PPP MTU of 1460 bytes. When the link is managed by IPsec, this MTU SHOULD be lowered to take into account the ESP encapsulation (see [SW-SEC]). The value for the MTU may also vary according to the size of the L2TP header, as defined by the leading bits of the L2TP message header (see [RFC2661]). Additionally, see [START_REF] Malis | Pseudowire Emulation Edgeto-Edge (PWE3) Fragmentation and Reassembly[END_REF] for a detailed discussion of fragmentation issues.

LCP

Once the L2TPv2 session is established, the SI and SC initiate the PPP connection by negotiating LCP as described in [RFC1661]. The Address-and-Control-Field-Compression configuration option (ACFC)

[RFC1661] MAY be rejected. In the IPv6-over-IPv4 scenarios (see Section 3.1), after the optional authentication phase, the Softwire Initiator MUST negotiate IPV6CP as defined in [START_REF] Varada | IP Version 6 over PPP[END_REF]. IPV6CP provides a way to negotiate a unique 64-bit Interface-Identifier to be used for the address autoconfiguration at the local end of the link.

IPv4CP

In the IPv4-over-IPv6 scenarios (see Section 3.2), a Softwire Initiator MUST negotiate IPCP [RFC1332]. The SI uses IPCP to obtain an IPv4 address from the SC. IPCP MAY also be used to obtain DNS information as described in [RFC1877].

Global IPv6 Address Assignment to Endpoints

In several scenarios defined in Section ) MUST be performed on the Softwire in both cases.

DHCP

The Softwire Initiator MAY use DHCP to get additional information such as delegated prefix and DNS servers.

DHCPv6

In the scenarios in Section 3.1, if the SI supports DHCPv6, it SHOULD send a Solicit message to verify if more information is available.

If an SI establishing an IPv6 Softwire acts as a router (i.e., in the scenarios in Sections 3.1.2 and 3.1.4) it MUST include the Identity Association for Prefix Delegation (IA_PD) option [START_REF] Troan | IPv6 Prefix Options for Dynamic Host Configuration Protocol (DHCP) version 6[END_REF] in the DHCPv6 Solicit message [START_REF] Droms | Dynamic Host Configuration Protocol for IPv6 (DHCPv6)[END_REF] in order to request an IPv6 prefix.

When delegating an IPv6 prefix to the SI by returning a DHCPv6 Advertise message with the IA_PD and IP_PD Prefix options [START_REF] Troan | IPv6 Prefix Options for Dynamic Host Configuration Protocol (DHCP) version 6[END_REF], the SC SHOULD inject a route for this prefix in the IPv6 routing table in order to forward the traffic to the relevant Softwire.

Configuration of DNS MUST be done as specified in [START_REF] Droms | DNS Configuration options for Dynamic Host Configuration Protocol for IPv6 (DHCPv6)[END_REF] and transmitted according to [START_REF] Droms | Dynamic Host Configuration Protocol for IPv6 (DHCPv6)[END_REF] and [START_REF] Droms | Stateless Dynamic Host Configuration Protocol (DHCP) Service for IPv6[END_REF]. In general, all DHCPv6 options MUST be transmitted according to [START_REF] Droms | Dynamic Host Configuration Protocol for IPv6 (DHCPv6)[END_REF] and [START_REF] Droms | Stateless Dynamic Host Configuration Protocol (DHCP) Service for IPv6[END_REF].

DHCPv4

An If the SI was previously assigned a prefix from that same SC, it SHOULD include the Subnet-Information suboption with the prefix it was previously assigned. The 'c' and 's' bits of the suboption SHOULD be set to '0'.

In the scenarios in Section 3.2, when delegating an IPv4 prefix to the SI, the SC SHOULD inject a route for this prefix in the IPv4 routing table in order to forward the traffic to the relevant Softwire.

Considerations about the Address Provisioning Model

This section describes how a Softwire Concentrator may manage delegated addresses for Softwire endpoints and for subnets behind the Softwire Initiator. One common practice is to aggregate endpoints' addresses and delegated prefixes into one prefix routed to the SC. The main benefit is to ease the routing scheme by isolating on the SC succeeding route injections (when delegating new prefixes for SI). As this practice had been used, the inclusion of the Framed-IP-Netmask attribute along with the Framed-IP-Address attribute tells the Softwire Concentrator to delegate an IPv4 prefix to the Softwire Initiator (e.g., in the IPv4-over-IPv6 scenarios where the Softwire Initiator is a router, see Sections 3.2.2 and 3.2.4), as the SC should forward packets destined to any IPv4 address in the prefix to the SI.

Considerations for Maintenance and Statistics

Existing protocol mechanics for conveying adjunct or accessory information for logging purposes, including L2TPv2 and RADIUS methods, can include informational text that the behavior is according to the Softwire "Hub and Spoke" framework (following the implementation details specified in this document).

  > IPV6CP: capable of /64 Intf-Id assignment or uniqueness check |------------------>/64 prefix RA |-

Figure 2 :

 2 Figure 2: Router CPE as Softwire Initiator

Figure 3 :

 3 Figure 3: Host behind CPE as Softwire Initiator

Figure 4 :

 4 Figure 4: Router behind CPE as Softwire Initiator

Figure 9 :

 9 Figure 9: Steps for the Establishment of a Softwire

Figure 10 :

 10 Figure 10: Detailed Steps in the Establishment of a Softwire

Figure 12 :

 12 Figure 12: Session Establishment

  During the life of the Softwire, both SI and SC send L2TPv2 keepalive HELLO messages to monitor the health of the Softwire and the peer L2TP Control Connection Endpoint (LCCE), and to potentially refresh the NAT/NAPT (Network Address Translation / Network Address Port Translation) entry at the CPE or at the other end of the access link. Optionally, Link Control Protocol (LCP) ECHO messages can be used as keepalives for the same purposes. In the event of keepalive timeout or administrative shutdown of the Softwire, either the SI or the SC MAY tear down the Softwire by tearing down the L2TPv2 Control Channel and Session as specified in[RFC2661].

	RFC 5571	Softwire H & S Framework with L2TPv2	June 2009
	1.1. Abbreviations
	AF	Address Family, IPv4 or IPv6.
	CPE	Customer Premises Equipment.
	LCCE	L2TP Control Connection Endpoint, an L2TP node that exists at
		either end of an L2TP Control Connection. (See [RFC3931].)
	SI	Softwire Initiator, the node initiating the Softwire within
		the customer network. (See [RFC4925].)
	SPH	Softwire Payload Header, the IP headers being carried within a
		Softwire. (See [RFC4925].)
	STH	Softwire Transport Header, the outermost IP header of a
		Softwire. (See [RFC4925].)
	SW	Softwire, a shared-state "tunnel" created between the SC and
		SI. (See [RFC4925].)
	1.2. Requirements Language
	Storer, et al.	Standards Track	[Page 4]

LNS

L2TP Network Server, a node that acts as one side of an L2TP tunnel (Control Connection) endpoint. The LNS is the logical termination point of a PPP session that is being tunneled from the remote system by the peer LCCE. (See

[RFC2661]

.) SC Softwire Concentrator, the node terminating the Softwire in the service provider network. (See

[START_REF] Li | Softwire Problem Statement[END_REF]

.)

  The Softwire Initiator (SI) is a dual-stack device (behind the IPv4-only CPE) acting as an IPv6 CPE router inside the home network. The IPv4 traffic SHOULD NOT traverse the Softwire.

	RFC 5571	Softwire H & S Framework with L2TPv2	June 2009
	IPv6 or dual-stack	IPv4-only	dual-stack
	|-
	See Figure 4.
	Storer, et al.		Standards Track	[Page 12]

  . After IPv6-over-PPP is up, IPv6 Stateless Address Autoconfiguration / Neighbor Discovery runs over the IPv6-over-PPP link, and the LNS can inform the v4/v6 router of a prefix to use for stateless address autoconfiguration through a Router Advertisement

	RFC 5571	Softwire H & S Framework with L2TPv2	June 2009
	Storer, et al.	Standards Track	[Page 13]

  Required AVPs include all the "MUST be present" AVPs from[RFC2661] for that control message, and Optional AVPs include the "MAY be present" AVPs from[RFC2661] that are used in the Softwire context on that control message. Note that in the Softwire environment, the SI always initiates the session. An L2TPv2 session setup for a Softwire uses only the incoming call model.

	RFC 5571	Softwire H & S Framework with L2TPv2	June 2009
	control message, No outgoing
	or analog calls (sessions) are permitted. L2TPv2 AVPs SHOULD NOT be
	hidden.
		SC	SI
		|<-
	Storer, et al.	Standards Track		[Page 23]

  AVPs that, while allowed for a given message, are irrelevant to Softwires. They can be irrelevant to Softwires because they do not apply to the Softwire establishment flow (e.g., they are only used in the Outgoing Call establishment message exchange, while Softwires only use the Incoming Call message flow), or because they are Optional AVPs that are not used. L2TPv2

	RFC 5571	Softwire H & S Framework with L2TPv2	June 2009
	Challenge AVP and Challenge Response AVP
	These AVPs are not required, but are necessary to implement tunnel
	authentication. Since tunnel authentication happens at the
	beginning of L2TPv2 tunnel creation, it can be helpful in
	preventing denial-of-service (DoS) attacks. See Section 5.1.1 of
	[RFC2661].
	The usage of these AVPs in L2TP messages is OPTIONAL, but SHOULD
	be implemented in the SC.
	Receive Window Size AVP, Firmware Revision AVP, and Vendor Name AVP
	As defined in [RFC2661].
	5.1.1.3. AVPs Not Relevant for Softwires
	L2TPv2 specifies numerous
	Tx) Connect Speed AVP
	(Tx) Connect Speed is a required AVP but is not meaningful in the
	Softwire context. Its value SHOULD be set to 0 and ignored by the
	receiver.
	Message Type AVP, Protocol Version AVP, Assigned Tunnel ID AVP, Call
	Serial Number AVP, and Assigned Session ID AVP
	As defined in [RFC2661].
	5.1.1.2. AVPs Optional for Softwires
	This section prescribes specific values for AVPs that are Optional
	(not required by [RFC2661]) but used in the Softwire context. It
	combines all the Optional AVPs from all the control messages in
	Section 5.1.1, and provides Softwire-specific use guidance.
	Storer, et al.	Standards Track	[Page 25]

  Request suboption MUST be configured with the 'h' bit set to '1', as the SI is expected to perform the DHCP server function. The 'i' bit of the Subnet-Request suboption SHOULD be set to '0' the first time a prefix is requested and to '1' on subsequent requests, if a prefix has been allocated. The Prefix length suboption SHOULD be 0 by default. If the SI is configured to support only specific prefix lengths, it SHOULD specify the longest (smallest) prefix length it supports.

	RFC 5571	Softwire H & S Framework with L2TPv2	June 2009
	One Subnet-
	SI establishing an IPv4 Softwire MAY send a DHCP request
	containing the Subnet Allocation option [SUBNET-ALL]. This practice
	is not common, but it may be used to connect IPv4 subnets using
	Softwires, as defined in Sections 3.2.2 and 3.2.4.
	Storer, et al.	Standards Track	[Page 29]

Table 2

 2 The address and prefix are expected to change when reconnecting to a different Softwire Concentrator. However, an organization providing a Softwire service may provide the same address and prefix across different Softwire Concentrators at the cost of a more fragmented routing table. The routing fragmentation issue may be limited if the prefixes are aggregated in a location topologically close to the SC. This would be the case, for example, if several SCs are put in parallel for load-balancing purpose.8. Considerations about RADIUS IntegrationThe Softwire Concentrator is expected to act as a client to a AAA server, for example, a RADIUS server. During the PPP authentication phase, the RADIUS server may return additional information in the form of attributes in the Access-Accept message.The Softwire Concentrator may include the Tunnel-Type and Tunnel-Medium-Type attributes[RFC2868] in the Access-Request messages to provide a hint of the type of Softwire being configured. Address attribute[RFC2865] is present, the Softwire Concentrator must provide that address to the Softwire Initiator during IPCP address negotiation. That is, when the Softwire Initiator requests an IP address from the Softwire Concentrator, the address provided should be the Framed-IP-Address.If the attribute Delegated-IPv6-Prefix[START_REF] Salowey | RADIUS Delegated-IPv6-Prefix Attribute[END_REF] is present in the RADIUS Access-Accept message, it must be used by the Softwire Concentrator for the delegation of the IPv6 prefix. Since the prefix delegation is performed by DHCPv6 and the attribute is linked to a username, the SC must associate the DHCP Unique Identifier (DUID) of a DHCPv6 request to the tunnel it came from and its user.Interaction between RADIUS, PPP, and DHCPv6 server may follow the mechanism proposed in [RELAY-RAD]. In this case, during the Softwire authentication phase, PPP collects the RADIUS attributes for the user such as Delegated-IPv6-Prefix. A specific DHCPv6 relay is assigned to the Softwire. The DHCPv6 relay fills in these attributes in the Relay agent RADIUS Attribute Option (RRAO) DHCPv6 option, before forwarding the DHCPv6 requests to the DHCPv6 server.8.2.2. IPv4 PrefixesRADIUS does not define an attribute for the delegated IPv4 Prefix. Attributes indicating an IPv4 prefix and its length (for instance the combination of the Framed-IP-Address and Framed-IP-Netmask attributes[RFC2865]) may be used by the Softwire Concentrator to delegate an IPv4 prefix to the Softwire Initiator. The Softwire Concentrator must add a corresponding route with the Softwire Initiator as nexthop.

	: Scenarios for IPv4

  RADIUS Accounting for L2TP and PPP are documented (see Section 4.3).When deploying Softwire solutions, operators may experience difficulties to differentiate the address family of the traffic reported in accounting information from RADIUS. This problem and some potential solutions are described in [SW-ACCT].9.2. MIBsMIB support for L2TPv2 and PPP are documented (see Section 4.4). Also, see[START_REF] Routhier | Management Information Base for the Internet Protocol (IP)[END_REF].10. Security ConsiderationsOne design goal of the "Hub and Spoke" problem is to very strongly consider the reuse of already deployed protocols (see[START_REF] Li | Softwire Problem Statement[END_REF]). Another design goal is a solution with very high scaling properties. L2TPv2[RFC2661] is the phase 1 protocol used in the Softwire "Hub and Spoke" solution space, and the L2TPv2 security considerations apply to this document (see Section 9 of[RFC2661]). The L2TPv2 Softwire solution adds the following considerations: o L2TP Tunnel Authentication (see Sections 5.1.1 and 9.1 of [RFC2661]) provides authentication at tunnel setup. It may be used to limit DoS attacks by authenticating the tunnel before L2TP and PPP resources are allocated. o In a Softwire environment, L2TPv2 AVPs do not transport sensitive data, and thus the L2TPv2 AVP hiding mechanism is not used (see Section 5.1.1). o PPP CHAP [RFC1994] provides basic user authentication. Other authentication protocols may additionally be supported (see Section 5.2.3). L2TPv2 can also be secured with IPsec to provide privacy, integrity, and replay protection. Currently, there are two different solutions for security L2TPv2 with IPsec: o Securing L2TPv2 using IPsec "version 2" (IKEv1) is specified in [RFC3193], [RFC3947], and [RFC3948]. When L2TPv2 is used in the Softwire context, the voluntary tunneling model applies. [RFC3193] describes the interaction between IPsec and L2TPv2, and

	RFC 5571	Softwire H & S Framework with L2TPv2	June 2009
	9.1. RADIUS Accounting
	Storer, et al. Storer, et al.	Standards Track Standards Track	[Page 34] [Page 35]

 --------DHCPREQUEST------

RFC 5571

Softwire H & S Framework with L2TPv2

June 2009

IPv4

A Softwire Concentrator may provide either globally routable or private IPv4 addresses. When using IPv4 private addresses [RFC1918] on the endpoints, it is not recommended to delegate an IPv4 private prefix to the SI, as it can lead to a nested-NAT situation.

The endpoints of the PPP link use host addresses (i.e., /32), negotiated using IPCP. This table describes the possible combination of IPv6 address scope for endpoints and delegated prefixes. -----------------+-----------------------+------------------------ -----------------+-----------------------+------------------------


Achour Mostefaoui

Stéphane Weiss

A Probabilistic Causal Message Ordering Mechanism

Causal broadcast is a classical communication primitive that has been studied for more then three decades and several implementations have been proposed. The implementation of such a primitive has a non negligible cost either in terms of extra information messages have to carry or in time delays needed for the delivery of messages. It has been proved that messages need to carry a control information the size of which is linear with the size of the system. This problem has gained more interest due to new application domains such that collaborative applications are widely used and are becoming massive and social semantic web and linked-data the implementation of which needs causal ordering of messages.This paper proposes a probabilistic but efficient causal broadcast mechanism for large systems with changing membership that uses few integer timestamps.

Introduction

Nowadays, we are facing an increasing number of collaborative applications. The nature of these applications is diverse as they appear as web 2.0 applications such as blogs, wikis or even social networks, as well as applications for mobile devices such as foursquare, yelp, latitude. Moreover, semantic web (web 3.0) and now social semantic web and linked-data (web 4.0) such as DBpedia are gaining more and more interest. The common point to these applications is that they gather the outcome of numerous users in order to provide a service for their users. The more users participate, the more content is created, attracting more users. This virtuous circle tends to create very large scale systems. However, while the content is created by users for users, for many applications, the underlying architecture remains centralized, leading to scalability issues as well as privacy and censorship threats. Stating this observation, several work envision decentralized architectures. The idea behind this concept, is to put the users as nodes of the network, allowing direct communication between users.

Currently, the development of such applications is restricted by several scientific problems. Among them, the problem of data replication has been investigated for many years, and have provided several approaches such as appropriate replicated data structures [START_REF] Oster | Data consistency for p2p collaborative editing[END_REF][START_REF] Shapiro | Conflict-free replicated data types[END_REF] and programming languages [START_REF] Alvaro | Consistency analysis in bloom: a CALM and collected approach[END_REF]. Hence replicated data can be enriched, updated and queried. However, the implementation of these operations has an underlying requirement: causally ordered communication (causal order for short) [START_REF] Sun | Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems[END_REF][START_REF] Terry | Session guarantees for weakly consistent replicated data[END_REF]. Informally a causal communication primitive imposes some restrictions on the delivery order of sent messages. It can be seen as an extension of the FIFO channel property to a whole communication network. Hence, a causal broadcast communication service imposes that a message is delivered to a some process only if all the messages that have been delivered in its past have been already delivered.

Unfortunately, causal communication has a cost that can be high either in time (message exchanges) or in space (the size of control information carried by messages). This cost becomes unacceptable when we consider a very large scale network of nodes with churn. Moreover, if the set of participating users changes over time, one needs to offer a join/leave decentralized procedure that is theoretically impossible to implement in asynchronous systems [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF].

Interestingly, in a real setting, depending on the system we consider, the probability to deliver in a non causal order two messages the sending of which are causally related may be quite low. For example, if the time between the generation of two messages on each peer is bigger than the transit time of a message, most of messages will be received in the causal order without any explicit control or synchronization. This observation is in favor of a probabilistic mechanism.

In this paper, we propose a probabilistic causal broadcast that provides a causal communication with high probability at a low cost for very large systems while allowing continuous joins and leaves. Of course it may happen, in few situations, that causal ordering is not respected. The proposed solution is then evaluated from a theoretical point of view and by simulation.

Related Work

The first causal broadcast mechanism was introduced in the ISIS system [START_REF] Birman | Reliable communication in the presence of failures[END_REF]. The simplest way to implement causal communication consists in piggybacking on each messsage a process want to send the whole set of messages it has delivered prior to this sending. Of course, this is very costly and there is a need to some kind of garbage collector. Otherwise, prior work mainly use either a logical structure (central node, tree, ring, etc.) or are based on the use of timestamps. A timestamp is an integer value that counts events (possibly not all events). A vector clock is a vector of such counters. The first solution based on vector clocks for a broadcast primitive has been proposed is [START_REF] Schiper | A new algorithm to implement causal ordering[END_REF] (a solution based on a matrix of counters has been proposed in [START_REF] Raynal | The causal ordering abstraction and a simple way to implement it[END_REF] for point-to-point communication). Vector clocks introduced simultaneously by [START_REF] Fidge | Logical time in distributed computing systems[END_REF][START_REF] Mattern | Virtual time and global states of distributed systems[END_REF] have been proved to be the smallest data structure that can capture exactly causality [START_REF] Charron-Bost | Concerning the size of logical clocks in distributed systems[END_REF]. Moreover, vector clocks require to know the exact number of sites involved in the application. As an example, the churn (intempestive join and leave of processes) and the high (and unknown) number of processes make the use of vector clocks unrealistic.

Torres-Rojas and Ahamad presented an approach based on plausible clocks [START_REF] Francisco | Plausible clocks: constant size logical clocks for distributed systems[END_REF]. Its aim is to trade the quality of the detected causality (number of false positives and false negative) among events (messages sending events) against timestamp size. When using a vector clock of size 1, a plausible clock boils down to Lamport's clocks [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] then as the timestamp size increases, a more and more accurate causal relation is encoded. Finally, when considering a timestamp size equal to the total number of processes, plausible clocks meet vector clocks. In a vector clock, the entry j of the vector managed by a given process p i counts the number of messages broadcast by process p j , to the knowledge of p i . Indeed due to asynchronism, the different processes do not have the same view of the state of the system at a given time instant. The approach of Torres-Rojas and Ahamad consists in associating several processes to the same entry of each vector clock.

The approach presented in this paper is an extension to the one of Torres-Rojas, namely each entry is associated to several processes and moreover, to each process are associated several entries of the vector clock. To summarize, let us consider the triplet (a, b, c). Where a is the size of the system (number of processes), b the size of the vector and c the number of entries associated with each process. A Lamport clock is (n, 1, 1) where n is the total number of users in the system, a vector clock is (n, n, 1), a plausible clock is (n, r, 1) and the proposed approach is (n, r, k) (r and k being two constants n ≥ r ≥ k).

System Model

When we consider the application level, the different users, nodes, processses or whatever we call them share common information by mean of replication to be able to tolerate chrashes and unexpected leaves (each process manages a local copy of part of the whole set of data). The differents processes interact by mean of operations (insert / delete / update a piece of data, make a query, etc.). The frequency and the distribution of operations through time and space depend on the application. At the underlying level, an operation will entail a change in the local state of a process and possibly the sending of messages to inform the other processes as the system is message-passing (no shared memory).

At the abstraction level considered in this paper, a distributed computation is a large set Π of n processes/users (N and Π are not necessarily known to the different processes of the system). We note p i or p j any processes in Π. We assume that processes gen-erate messages at arbitrary rates. Messages are sent to all processes using a reliable broadcast mechanism (broadcast sending primitive). Any process p i ∈ Π generates three kinds of events. An event e could be a local event, a send event or a delivery event. A local event induces no interaction with other processes and thus will be omitted in the rest of the paper.

Events produced by a distributed computation are ordered by Lamport's happened-before relation [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF].

Definition 1 (Happened-before Relation [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF]) We say that event e 1 happened before event e 2 denoted by e 1 → e 2 if:

• e 1 occurred before e 2 on the same process, or

• e 1 is the send event of some message m and e 2 is the delivery event of the same message by some process, or

• there exists an event e 3 such that e 1 → e 3 and e 3 → e 2 (transitive closure).

Let us note send(m) the sent event of a message m and del(m) the associated delivery event. Note that del(m) = rec(m) the receive event. The receive event corresponds to the arrival of a message to the underlying communication level of some process. The application level of this ame process is not aware of the arrival of such message and thus has no access to its content. The delivery of a message corresponds to the arrival of the message at the application level leading to the use of its content. Moreover, when considering two messages m 1 and m 2 , we say that

m 1 → m 2 if send(m 1 ) → send(m 2 ).
A distributed computation respects causal order if for any pair of messages (m 1 , m 2 ) the following holds.

• send(m 1 ) → send(m 2 ) ⇒ del(m 1 ) → del(m 2 )
To ensure the aforementioned property an arrived message m, event rec(m), at a destination process p i can be possibly delayed until all the messages sent or delivered by the sending process p j before the sending of m have been already delivered by the receiving process p i .

Probabilistic Causal Broadcast

Several works in the literature propose to reduce the communication cost to increase scalability by proposing probabilistic solutions. One example is the probabilistic broadcast [START_REF] Eugster | Lightweight probabilistic broadcast[END_REF]. We can define a probabilistic broadcast as following:

Definition 2 (Probabilistic Broadcast) A probabilistic broadcast is a mechanism that ensures, with a high probability, the deliverance of sent messages to all participants.

Unlike traditional broadcast that ensures that each message is delivered exactly once to all recipients, a probabilistic broadcast offers only a very high probability that all recipients will receive the message. In addition, this message can be received several times, requiring a mechanism to discard duplicated messages. On the contrary, probabilistic broadcast have a greater scalability.

In this paper, we introduce two definitions: the probabilistic causal ordering mechanism and the probabilistic causal broadcast.

Existing mechanisms such as vector clocks are often used to provide a perfect causal ordering mechanism. We believe that their cost is not compatible with large systems, and propose to use a probabilistic causal ordering mechanism. We define it as follows: Definition 3 (Probabilistic Causal Ordering) A probabilistic causal ordering mechanism is a mechanism that ensures a causal delivery with high probability.

A Probabilistic Causal Ordering Mechanism

In this section, we start by describing the data structures used by our causal ordering mechanism. Then, we describe the algorithms that allow this probabilstic causal delivery.

Data structure

The main idea of the proposed solution is to associate with each process p i a vector of integer values V i of size R < N (N being the total number of processes in the system). This vector acts as a logical clock that allows to timestamp a subset of the events generated by this process. This timestamping allows to test whether an event occured before another one. Mainly, the proposed protocol associates a logical date with each send event and this date is attached to the message and is called its timestamp. When a message is received, the receiving process compares its local logical clock with the timestamp carried by the received message. This allows it to know whether there exist messages sent causally before it and that

have not yet been delivered. As soon as a message can be delivered it is given to the upper layer application and the local clock is updated to take into account that this message has been delivered. We denote V i [j] with 0 ≤ j < R the j-th entry of the vector clock of the process p i . A vector clock assigns exactly one entry to each process. With a plausible clock, each process is assigned only one entry, but one entry is assigned to several processes. Finally, our approachproposes to assign several entries to each process, each entry being assigned to several processes. We denote f (p i ) the set of the entries assigned to p i .

Probabilistic causal ordering delivery mechanism

The proposed probabilistic causal ordering delivery mechanism is an adaptation of the classical and wellknown causal delivery mechanism [START_REF] Birman | Reliable communication in the presence of failures[END_REF]. When a process p i wants to broadcast a message m, it executes Algorithm 1 given below.

First, process p i increments all its assigned set of entries f (p i ) in its local vector. Then, a copy of this local vector is attached to the message to be sent. m.V denotes the vector timestamp attached to message m. Finally, m is broadcast to all processes.

Input: m: message to broadcast ∀x ∈ f (p i ), V i [x] = V i [x] + 1; m.V = V i ; Broadcast(m);
Algorithm 1: Broadcasting a message m by p i When a message m broadcast by a process p j is received by a process p i , this process executes Algorithm 2 given below.

Input: m: message received by p i from p j waitUntil((∀x

∈ f (p j ), V i [x] ≥ m.V [x] -1) ∧ ∀k / ∈ f (p j ), V i [k] ≥ m.V [k]); ∀x ∈ f (p j ), V i [x] = V i [x] + 1; deliver(m);
Algorithm 2: Upon reception of message m by p i A message m received by a process p i from a process p j is queued until it is considered as causally ready, namely all the messages m sent causally before it (m → m) have been already delivered by process p i to the application level. Note that:

On the one side, the f (p j ) entries are at least as high as the local vector of process p j before it generates that message:

∀x ∈ f (p j ), V i [x] ≥ m.V [x] -1.
This means that all the messages sent by process p j but message m are already known at process p i .

On the other side, the other entries of the vector are at least as high as the local vector of process p j before it generates that message:

∀k / ∈ f (p j ), V i [k] ≥ m.V [k].
This means that at least all the messages that have been delivered to process p j before it broadcast message m are known at process p i before p i delivers m to its application level.

When the delivery test of a message m holds, process p i increments the entries of its local vector that belong to the set f (p j ) of entries of its local vector before delivering the message to the application. Hence p i has recorded the information "m has been delivered to the p i " in its local vector.

Figure 4.1.2 shows how the proposed mechanism works. Assume that three processes p i , p j and p k are in the same initial state, meaning they have generated no messages yet, and all values in their vector are set to 0. Also, we consider here that each process has a vector of R = 4 entries and each process is assigned K = 2 entries. We assume that f

(p i ) = {0, 1}, f (p j ) = {1, 2} and f (p k ) = {3, 4}.
On that state, p i generates a first message called m. If we assume that f (p i ) = {0, 1}, then after applying the algorithm 1 at p i , its vector becomes [1, 1, 0, 0]. Notice that it is this vector ([1, 1, 0, 0]) that is attached to m. This message is sent to all other processes, here we represent only p j and p k . We assume that p j receives m first: Algorithm 2 is applied and, When p k receives m , the vector p k is [0, 0, 0, 0] while the vector attached to m is [1, 2, 1, 0]. The delivery of m is delayed because its delivery condition (see Algorithm 2) is not satisfied (

V k [1] < (m.V [1]-1) and V k [0] < m.V [0]).
The reception of m turns p k 's vector into [1, 1, 0, 0] which fulfills the condition for delivering m . This protocol cannot be perfect as it uses control information the size of which is smaller than a vector clock of size N that has been proved to be minimal for ensuring causal delivery of messages. Indeed, it is possible that if process p k receives some set of messages before receiving m , the vector of p k could have been updated in such a way that p k believes that m is causally ready. This scenario is illustrated by Figure 4.1.2. In addition to the previous processes, we now consider p 1 and p 2 whose assigned entries are respectively f (p 1 ) = {0, 3} and f (p 2 ) = {1, 3}. pi pj p1 p2 pk 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 This error comes from the fact that all entries of p i are matched by the combination of the entries of p 1 and p 2 : f (p i ) ⊆ (f (p 1 ) ∪ f (p 2 )). It is interesting to notice that, as each set of entries is assigned to at most one process, the error occurs only if we have at least two concurrent messages, here m 1 and m 2 . If only one concurrent message is received, the protocol delivers the message in causal order.

m m m1 m2 m2
1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 m m1 1 2 1 0 1 1 0 2 m 1 2 1 2 m 2 3 1 2
In addition, it is easy to see that the proposed protocol never delays the delivery of an arrived message m at some process p i if all the messages m that have been sent causally before m (i.e. m → m ) have been already delivered by process p i . Indeed, between two consecutive sendings of messages, on the same process, the increment is one for some entries and when a message is delivered the corresponding entries are at least incremented by 1 then if the first one is delivered, the second cannot be blocked as the corresponding entries are augmented by at least 1. The same happens for messages sent by different processes as in this case the sender of the second message has necessarily delivered the first message to establish the causal dependency between the two messages.

Generation and distribution of the sets of keys

The example given above gives the intuition why the generation of the sets of keys (entries in the vector clock) is the core of the approach, and how it heavily affects the accuracy of the resulting protocol. In this section, we present our approach to assign sets of keys to processes.

Perfect distribution of keys

We assume the existence of a mapping function f used to assign to each process a set of K entries of the vector such that, the function f returns exactly K distinct values between 0 and R-1 (R being the total number of entries, i.e. the size of the vector clock). Moreover, the values are equally distributed among processes. In other words, for all subsets of s values assigned to x processes, there exists no other subset of s values assigned to more than x + 1 processes, or less than x -1 processes, for 1 ≤ s ≤ K.

Input: set id , K, R Output: {a 1 , . . . , a k } k ← K -1 ; r ← R -1 ; t ← C r k ; sav ← t; for i = 0 → K -1 do while set id ≥ t do a i ← a i + 1 ; r ← r -1 ; sav ← t ; t ← C r k ; end t ← sav ; if i < K -1 then a i+1 ← a i ; end k ← k -1 ; end Algorithm 3: Generating the set of entries from set id for K > 1
Distributed key assignment algorithms Finding the best solution is a difficult problem. Moreover, such an algorithm would not support dynamicity. Indeed, the addition or the removal of one process would lead to re-assign all new entries to all or part of the processes. Therefore, to select the K values, we propose to use a random algorithm.

Each process generates randomly a value called set id chosen between 1 and C R K . Then, the corre-sponding set of values is obtained using the function f defined below: This algorithm ensures that no peer has twice the same entry. Moreover, if we can ensure that all peers have different identities, all the generated sets are distinct, and the intersection between all the sets is at most K -1.

Detecting Delivery Errors

Most of the applications that require causal ordering of messages assume that no message is wrongly delivered. The proposed approach that aims to scale, may deliver a message before a message that causally precedes it. This would lead to inconsistencies, however, we make the assumption that a recovery procedure does exist (e.g., anti-antropy). This procedure may be costly, and we must determine when it is required.

A simple solution could be to run it at an arbitrarily chosen period of time. However, this period impacts the system performance: on the one hand, if it is underestimated, we will waste time by running unnecessary costly recovery procedure. On the other hand, the over estimation of this period will cause heavy changes on the application and will hurt the usability of the system and the recovery from this inconsistent global state.

We propose a mechanism (Algorithm 4) that allows to detect possible delivery errors if run when receiving a message, prior to the deliver function Input: m: message received from p j Output: error: true if an error has occurred error ← true;

if (∃x ∈ f (p j ), V i [x] = m.V [x] -1) then error ← false;
endif Algorithm 4: Before delivering m from p j to the application Before delivering a message m from a process p j , we check if all its entries are already higher than their corresponding value in the message, meaning that concurrent messages have covered all its entries. In that case, the receiving process p i wrongly believes that it has already received this message, and may have delivered other messages m such that m → m .

If the procedure returns false, we are sure that all is fine: no such message m does exist. However, if it returns true then either there may be a causal order violation or not. In other words, this does not mean that m will not be delivered before some message m such that m → m.

Interestingly, the detection gives an alert within the propagation time of the message from p j . As a result, errors are detected quickly after they occur. Unfortunately, this mechanism greatly over-estimate the number of errors (causal order violations). In the following section, we propose two mechanisms to limit the number of false detections.

Improving the protocol

As explained above, we can have an alert within the propagation time of the late message. As a consequence, we propose the following protocol where we assume that each process keeps a list L of the last received messages.

Input: m: message received from process p j , L: list of previously delivered messages Output: error: true if an error may have occurred error ← false;

if (∀x ∈ f (p j ), V i [x] > m.V i [x]) ∧ (∃m i ∈ L.∀x ∈ f (p j ), m i .V [x] ≥ m.V [x]
) then error = true; endif Algorithm 5: Before delivering m from a process p j to the application Algorithm 5 is similar Algorithm 4 but it checks in the list of previously delivered messages. The main idea is to check if a message previously delivered depends on the same values for the keys f (p j ) set by the message m. If the size of L is infinite, this mechanism may over-estimate the number of error, but will never under-estimate it. The list L should contain all messages received for a time O(T propagation ) where T propagation depends on that actual communication network and keeps the value of the estimate transmission delay.

It is interesting to notice that such a list may already be available. Indeed, broadcast mechanisms based on gossip protocols, which duplicate a message to ensure that it reaches all peers or based on an unreliable communication protocol like UDP, keep a short list of the moste recently received messages to circumvent message loss and multiple deliveries of a same message.

5 Theoretical analysis

Correctness

Lemma 1 A well-formed message is eventually delivered.

Proof 1 We prove the liveness by induction.

H0: Any message generated on the initial state will be eventually delivered.

In the initial state, all entries of the local vector are 0. Therefore, the vector of a message m i 0 generated by p i on the initial state contains zeros for all entries except the all f (p i ) entries which are 1.

∀x / ∈ f (p i ), m i 0 .V [x] = 0 ∧ ∀x ∈ f (p i ), m i 0 .V [x] = 1 A vector cannot
have values below 0, hence we can prove that any message generated on the initial state can be delivered on any process p j .

∀x, j V j [x] ≥ 0 ⇒ (∀i, j (∀x / ∈ f (p i )) V j [x] ≥ m i 0 .V [x]∧ ∀x ∈ f (p i ) V j [x] ≥ (m i 0 .V [x] -1))
H1: We assume a set S of messages that are eventually delivered on all processes. A message m generated on any process p i after the delivery of S will be eventually delivered on all processes.

The delivery of all messages in S implies that the local vector p i is defined by ∀x, V i [x] = {j|x∈f (j)} n j where n j is the number of messages generated by p j in the set S. Notice that the order of delivery have no impact on the obtained vector.

We make the assumption that S is eventually delivered on all processes, hence it is obvious that eventually all processes will have a local vector which entries are greater or equal to V i before the generation of m. A direct consequence of this observation is that m will be eventually delivered:

∀x, j (V j [x] ≥ V i [x]) ⇒ ∀i, j, (∀x / ∈ f (p i )) V j [x] ≥ m i .V [x]∧ ∀x ∈ f (p i ) (V j [x] ≥ (m i .V [x] -1))
We prove that any message generated after a set of eventually delivered messages is also eventually delivered (see H1). As any message generated on the initial state is eventually delivered (see H0), we conclude that any message is eventually delivered.

Corollary 1 A message causally ready is never delayed.

Complexity Analysis

In this section, we evaluate the complexity of our algorithms. The first algorithm is in charge of the creation of a message to be sent. The K entries assigned to a process that wants to send a message are incremented. Then, the R entries of the vector are attached to the message to be sent. Thus, Algorithm 1 has a complexity of O(R). Similarly, the Algorithm 2 that evaluates the delivery condition of an arrived message has to go through the R entries of the vector leading to a complexity of O(R).

The third algorithm assigns K entries to a site from its unique identifier. The first loop in the algorithm is done at most K times. The embedded loop will be done at most R times independently from the first loop, meaning that the R entries in the loop are split over the K entries of the for loop. The algorithm needs to compute R + 1 combinations denoted as C r k each of them having a complexity of O(K). As a consequence, the overall complexity of the third algorithm is O(RK).

Error Analysis

In this section, we evaluate the error rate of our probabilistic causal ordering mechanism depending on the estimation of the system load and the different parameters of our approach (N, R and K).

Let us first say that the higher R the better is the resulting protocol (better in the sense less messages that violate causal ordering). At the extreme, if R = 1 we have a linear clock similar to Lamport's clock. At the other extreme, R = N we get the perfect and optimal (no causal order violation and delivery at the earliest) solution to causal ordering. Concerning K, it is easy to see that the situation is less clear. Indeed, if K is too small; at the extreme K = 1 we get the plausible clocks of Torres and Ahamad, and we are sure that if two process are assigned the same entry they will interfere at each message sending. At the other extreme K = R the protocol boils down to the use of a Lamport's clock merging all processes within one single entry. Hence the intuition of the proposed approach is that there is some value of K to determine that lies between 1 and R that is optimal. The aim of this theoretical analysis and the simulations presented in the coming sections is to determine the best value for K and to evaluate the impact of K on the error rate.

First, we need to compute the probability that a message m is delivered before a message m that precedes it causally (m → m). As explained in Section 4.1.2 if such messages m and m are received by some process p i with m received first, then m can be delivered before m with a probability that we note P nc the probability that a message m bypasses a message m sent causally before it. Depending on the system we consider, this probability may be quite low. Therefore, we have to consider this probability to dimension precisely the size of the vector and the number of entries each process chooses. A necessary condition, though not sufficient, to wrongly delivered a message is that this message is received after a preceding message, and the entries of the delayed messages have been all matched by concurrent messages. Let us note P error the probability that all the K entries of the missing message are covered by a set of concurrent messages (see the example given in Section 4.1.2). Consequently, the probability P of wrongly delivering a message is bounded by the probability that a delayed message has its entry matched concurrently P ≤ P nc * P error .

The probability that a message is replaced by a set combination of previous messages is computed following the same scheme as the false positive error of a bloom filter [START_REF] Burton | Space/time trade-offs in hash coding with allowable errors[END_REF].

The probability that one entry is incremented is 1/R. So the probability that it is not incremented is: 1 -1/R and that it is not set by X messages is (1 -1/R) k * X . Then the probability that one entry is incremented by X messages is 1

-(1 -1/R) k * X .
Finally the probability of an error delivery is (

1-(1- 1/R) k * X ) k .
We need to find the value K that minimizes the probability of an error. We can easily show that (1 -

(1 -1/R) k * X ) K is minimal when K min = ln(2) * R X .

Experiments

In this section, we detail the model used to run our simulation. In the first part, we show that the estimation of the optimal value of K is sound. Then, in a second part, the experiments are run using this optimal value. We, therefore, show the behavior of the mechanism based on the size of the vector. In a third part, we show the accuracy of the estimation of the probability of an error occurrence.

Methodology: In order to evaluate our proposal, we have developed a simple event-based simulator. Each process generates messages according to a Poisson distribution of parameter λ. Each message has its own propagation time d described as a random value which follows a Gaussian distribution N (µ, σ 2 ) law. Each process receives a message whose propagation time is according to a N (d, σ 2 m ). In the average, each node generates a message each second The message propagation time d follows a normal distribution law N (100, 20) and the skew between a message reception on all nodes follows also a normal distribution law N (d, 20).

Detecting delivery errors

One of the challenges to evaluate the proposed approach is to measure the error rate. When a message is said to be "causally ready" by our mechanism, we need to verify that it is really causally ready, therefore, in our simulator we also need to implement a perfect causal broadcast. This additional mechanism should have the lowest cost possible as it limits the simulator scalability. To detect an error, we must know all the messages the sending of which happenedbefore a given message. A simple solution would be to attached a set of messages to each sent message. Obviously, this would limit drastically the scalability of the simulator. Therefore, we use a mechanism based on vector clocks. Unfortunately, a vector clock cannot capture wrongly delivered messages. Indeed, when a non-causally ready message arrives, the causal ordering mechanism delays it, while in our case, it may be delivered to the application.

To deal with this case, we update the local vector clock by taking the maximum of the local vectors and the wrongly delivered messages. Therefore, missing messages will be dropped by the perfect causal delivery mechanism. Detecting precisely if the missing messages are causally ready is costly, instead we propose two metrics. The first one, min , simply assumes that all missing messages are delivered in a causal order, while the second one max assume that all of them are delivered in a non-causal order. Finally, we have two bounds on the error rate: the lower bound min and the upper bound max .

Choosing the optimal number of keys

The first step in validating our approach is to verify that we choose the best value for the parameter K. Therefore, we ran several experiments by changing only the value of K and then compare the value that minimizes it with the theoretical optimal value.

Figure 3 shows the error rate for respectively 500, 1000, 1500 and 2000 peers. In this experiment, the average number of messages received by a process is constant (200 messages/second) and, the number of exchanged messages is more than a hundred million.

As our simulation considers an average message propagation time of 100ms, the average number of messages that are received concurrently is 20. We use 100-entry vectors, hence, the optimal number of keys is theoretically ln(2) * 100/20 ≈ 3.5 and the experimental results show that the value for K that minimizes the error rate for this configuration is 4.

Impact of the different parameters

In this section, we assume these system parameters:

• Number of nodes: N = 1000

• Each node generates a message every 5 seconds in the average (λ = 5000) • The vector has 100 entries (R = 100)

• Each node has 4 entries (K = 4) As a real system may behave differently from the estimation, we are now interested in the impact on the error rate when we vary only one parameter. Impact of λ on the error rate The error rate depends on the number of processes that send messages. Therefore, to determine the optimal size of the vector, and the number of keys, we need to estimate the number of "active" processes during an average message propagation time. Figure 4 shows the variation of the error rate according to different values of the average delay between two messages generated by each process. Impact of N on the error rate Figure 5 shows the impact of the number of nodes. The error rate increases quickly as soon as the number of nodes is higher than the estimation (N = 1000). As a result, 1000 should be considered as the maximum number of nodes in this case (λ, R, K, N ).

Figure 6 shows the impact of the number of nodes In this experiment, the estimated number of nodes is 1000. We can see that the error rate remains constant when the number of nodes increases. Also it increases when the number of nodes decreases. This can be explained by the constant message rate, when the number of nodes decreases, the message rate of each node increases.

The previous experiments show that indeed, it is not λ, N by themselves that direct impact the error rate but the "concurrency". We mean by concurrency the mean number of messages that are broadcast during the transit time of some message (latency of the network).

Conclusion

In this paper we presented a new approach that allows to heavily reduce the cost of causal broadcast communication primitive. This reduction of the cost leads to a small rate of errors. The errors being the cases when a message is delivered while there are causally related messages that need to be delivered that are not yet delivered.

We have shown that the approach is theoretically sound. The main parameter K optimizes the protocol and may vary from 1 and R the two extreme already existing cases. The second contribution of the paper is an alert mechanism that allows to check the bad cases. In case there is no alert, we are sure there is no error.

Figure 1 :

 1 Figure1: Example of message delivery p j 's vector is updated to [1, 1, 0, 0]. Then p j generates a new message m . Assuming that f (p j ) = {1, 2}, the generation of m leads to update p j 's vector to the value [1, 2, 1, 0] which is piggybacked with the message m . As m is generated after m, m is causally dependent of m (m → m ). Although message m is broadcast and will eventually reach p i , we only represent its reception by process p k for the sake of simplicity.When p k receives m , the vector p k is [0, 0, 0, 0] while the vector attached to m is [1, 2, 1, 0]. The delivery of m is delayed because its delivery condition (see Algorithm 2) is not satisfied (V k [1] < (m.V [1]-1) and V k [0] < m.V [0]).The reception of m turns p k 's vector into [1, 1, 0, 0] which fulfills the condition for delivering m . This protocol cannot be perfect as it uses control information the size of which is smaller than a vector clock of size N that has been proved to be minimal for ensuring causal delivery of messages. Indeed, it is possible that if process p k receives some set of messages before receiving m , the vector of p k could have been updated in such a way that p k believes that m is causally ready. This scenario is illustrated by Figure4.1.2. In addition to the previous processes, we now consider p 1 and p 2 whose assigned entries are respectively f (p 1 ) = {0, 3} and f (p 2 ) = {1, 3}.

Figure 2 :

 2 Figure 2: Example of possible delivery error Processes p 1 and p 2 generate m 1 and m 2 , which are received by p k before m .The reception of m 2 and m 1 updates the vector of p k to the value[START_REF] Alvaro | Consistency analysis in bloom: a CALM and collected approach[END_REF][START_REF] Alvaro | Consistency analysis in bloom: a CALM and collected approach[END_REF] 0,[START_REF] Birman | Reliable communication in the presence of failures[END_REF]. When m arrives, p k evaluates to true the delivery condition of Algorithm 2 and delivers m while m has not been received yet. This error comes from the fact that all entries of p i are matched by the combination of the entries of p 1 and p 2 : f (p i ) ⊆ (f (p 1 ) ∪ f (p 2 )). It is interesting to notice that, as each set of entries is assigned to at most one process, the error occurs only if we have at least two concurrent messages, here m 1 and m 2 . If only one concurrent message is received, the protocol delivers the message in causal order.In addition, it is easy to see that the proposed protocol never delays the delivery of an arrived message m at some process p i if all the messages m that have been sent causally before m (i.e. m → m ) have been already delivered by process p i . Indeed, between two consecutive sendings of messages, on the same process, the increment is one for some entries and when a message is delivered the corresponding entries are at least incremented by 1 then if the first one is delivered, the second cannot be blocked as the corresponding entries are augmented by at least 1. The same happens for messages sent by different processes as in this case the sender of the second message has

Figure 3 :

 3 Figure 3: Number of errors for different value of K (Theoretical best value is 3.5)Impact of λ on the error rate The error rate depends on the number of processes that send messages. Therefore, to determine the optimal size of the vector, and the number of keys, we need to estimate the number of "active" processes during an average message propagation time. Figure4shows the variation of the error rate according to different values of the average delay between two messages generated by each process.

Figure 4 :

 4 Figure 4: Error rate for different values of λ The Figure shows that the error rate is stable around the estimate value (λ = 5000), but it increases quickly when λ is lower than 3000.

Figure 5 :

 5 Figure 5: Error rate for different values of N

Figure 6 :

 6 Figure 6: Error rate for different values of N , but with a constant number of received messages