Matthieu Coudron

Stefano Secci

An Implementation of Multipath TCP in ns3

Keywords: MPTCP, Network Simulator, Implementation Evaluation 2016 MSC: 20-70, 20-80

The Multipath Transport Control Protocol (MPTCP) is undergoing a rapid deployment after a recent and quick standardization. MPTCP allows a network node to use multiple network interfaces and IP paths concurrently, which can lead to several advantages for the user in terms of performance and reliability. In this paper, we describe an MPTCP implementation in the Network Simulator 3 (ns3), comparing it with both the Linux implementation and previous ns3 implementations. We show that it is compatible with the Linux implementation and that it has a desirable similar behavior in traffic handling. Our goal is to allow researchers develop and evaluate new features of MPTCP using our simulator in a much faster way than they would with a kernel implementation, hence boosting MPTCP research.

Introduction

Nowadays modern mobile devices are usually equipped with several network interfaces: it may be WiFi and Ethernet for laptops, or WiFi and cellular for smartphones. In this context, a user may want to leverage these different interfaces into using concurrently several paths to achieve the following goals:

1. Seamless mobility: with legacy TCP, losing an IP address means losing active TCP sessions, which in a mobility scenario translates into a communication delay necessary to setup a new connection. With multipath transport, one device can establish several connections in advance and (re)transmit data on alternate paths when there is a partial or total failure on one path (see [START_REF] Croitoru | Towards wifi mobility without fast handover[END_REF]). Bandwidth aggregation: The ability to aggregate the bandwidth of several links is also very appealing and appears as the most anticipated feature. 2. Higher confidentiality: if a flow of data is split over several paths, it may become harder for an attacker to reconstitute the whole connection flow.

3. Lower response time: sending duplicated packets on several paths can increase the probability for the data to follow uncongested paths.

More elaborate features can emerge from combining some of these techniques. For instance, a smartphone user may enable both LTE and WiFi interfaces to benefit from the mobility advantage, and at the same time to limit the cellular throughput to save some battery or money. Or one may choose to trade some of the aggregation benefit in exchange for higher confidentiality.

Yet a multipath protocol needs to address several problems to reach the previous goals and deliver better than singlepath performance. Multipath communications lead to an increased occurrence of out-of-order packet deliveries, which may generate worse performance than single path protocols [START_REF] Ferlin | Multi-path transport over heterogeneous wireless networks: Does it really pay off?[END_REF], besides questioning the fair usage of the network. Information such as the Round Trip Time (RTT) or the packet sequence number are critical to mitigate these problems, and are already available at the transport layer. While the application layer could provide a similar or even better service, having a standard multipath transport protocol allows to spread such a knowledge and should ease multipath communications deployment.

MPTCP is such a multipath transport protocol that attempts to address these issues in a backward compatible way. As any new Internet protocol, MPTCP has to face an ossified Internet whose many middleboxes are typically configured to block any unknown protocol extension or any new protocol. MPTCP must also address the fairness issue, i.e., it should not get too much more bandwidth compared to legacy users, otherwise the protocol could be blocked by Internet providers. At the same time MPTCP ambitions to be as least as good as TCP in terms of throughput, which can prove challenging in some environments.

In the following, in Section 2 we describe MPTCP, presenting its main components, and describing its state machine. In Section 3 we motivate our effort, detailing our implementation characteristics, and describing our design methodology and comparing it with existing implementations. Section 4 reports an experimental evaluation of the simulator. We open source the code of the simulator in [START_REF]LIP6-MPTCP open source project repository[END_REF].

Multipath TCP

MPTCP is a TCP extension formalized in RFC 6824 [START_REF] Ford | RFC6824 -TCP Extensions for Multipath Operation with Multiple Addresses[END_REF]; the MPTCP working group at the Internet Engineering Task Force (IETF) was formed in october 2009; since the beginning, it emphasizes backwards compatibility with the network and the applications. This is an aspect to keep in mind when looking at some design decisions that may appear counter-intuitive at first (for instance the creation of an additional sequence number space or the requirement to wait for two levels of acknowledgements before being authorized to free the buffers).

As a result, TCP applications can run unmodified with MPTCP. This differs from the Stream Control Transmission Protocol (SCTP) [START_REF] Stewart | Stream Control Transmission Protocol[END_REF], a previous IETF effort, that provides more features but whose deployment is impeded by the many middleboxes on the Internet, blocking unknown protocols. 1 MPTCP should be pareto optimal, i.e., it should not harm any TCP user while improving the situation for MPTCP users. Achieving pareto optimality is still a problem for MPTCP [START_REF] Ferlin | Multi-path transport over heterogeneous wireless networks: Does it really pay off?[END_REF] though improvements have been made [START_REF] Khalili | MPTCP is not pareto-optimal: Performance issues and a possible solution[END_REF]. Several techniques exist in the literature, such as watching the loss correlation between subflows to infer if they shared a bottleneck, but such methods make assumptions about the network that prevent them from being holistic. The conservative approach is to consider that all subflows share the same bottleneck: this is the so-called resource pooling principle [START_REF] Wischik | The resource pooling principle[END_REF]. Fairness violation and outof-order packet delivery are two problems that any multipath protocol shall to solve.

High level design of MPTCP

MPTCP consists in a shim layer, as represented in Figure 1. It is built between the application and the TCP stack that unifies several TCP connections, called "subflows" in the MPTCP context. A subflow is a TCP connection characterized by a tuple (IP source , TCP port source , IP destination , TCP port destination ) and is assigned a unique subflow id generated by the MPTCP stack. MPTCP uses such a subflow identifier to convey subflow related advertisements; it does not use the IP addresses as identifiers because they can be rewritten by external middleboxes. One can alternatively define an MPTCP connection as a set of one or many subflows aggregated to feature at least the same set of services as a singlepath TCP communication. The RFC 6182 [START_REF] Ford | Architectural guidelines for Multipath TCP Development[END_REF] lists a few functional goals that are deemed mandatory for a wide deployment of the protocol:

1. MPTCP must support the concurrent use of multiple paths. The resulting throughput should be no worse than the throughput of a single TCP connection over the best among these paths. 2. MPTCP must allow to (re)send unacknowledged segments on any path to provide resiliency in case of failure. It is advised to support "break-beforemake" scenarii, e.g., buffer the data when a (mobile) user loses temporarily 1 SCTP is now deployed mainly thanks to the WebRTC protocol but is tunneled over UDP packets [START_REF] Jesup | WebRTC Data Channels[END_REF]. SCTP proposed to opt-out some TCP services on a per connection basis such as in-order delivery. Ordering is indeed unnecessary when downloading an archive, because head-of-line blocking may slow down the connection. all connectivity, to allow resuming the communication as soon as a new subflow gets available.

[8] also lists three compatibility goals:

• The applications must be able to work with MPTCP without being changed, for instance via an operating system upgrade. It also implies that MPTCP keeps the in-order, reliable, and byte-oriented delivery. 2• MPTCP should work with the Internet as it is composed today, that is with middleboxes blocking unusual payloads or even modifying the payload such as internet accelerators, Network Address Translator (NAT) etc.

The best way to achieve this is to appear as a singlepath TCP flow to the middleboxes. Hence MPTCP relies on TCP options for signaling. TCP option space is scarce (40 bytes maximum per packet).

• MPTCP should be fair to single path TCP flows at shared bottlenecks, i.e., not be greedier. At the same time, MPTCP still shall perform better.

As part of the network compatibility goal, MPTCP should provide an automatic way to negotiate its use, and upon failure of such a negotiation, fall back to legacy TCP. This fall back is also possible even after successful completion of the MPTCP handshake, in case no data ack is received during a certain time, or checksums are invalid.

Connection process

Initiation. Supposing that the MPTCP extension is not disabled, and that the application remained unchanged, the MPTCP connection is initiated through the TCP socket interface via the connect system call. As per the MPTCP Linux system nomenclature, we call this first TCP connection the master connection. This call must generate a random key to be used during the TCP handshake as can be seen in Figure 2. This key is later hashed and used by MPTCP to authenticate additional subflows.

Once other subflows are established, the master subflow can be removed as any other and holds no specificity. Upon SYN reception, the server generates also a key which is reflected by the client in the final TCP handshake ack. This allows the server to operate in a stateless mode. Indeed an MPTCP stack needs to allocate more data structures than a legacy TCP connection to save the key, the list of subflows, their identifiers etc. For the sake of efficiency, the allocation of these data structures can be deferred until the moment the MPTCP negotiation succeeds.

Addition of other subflows. The host can open a new subflow as soon as a DSS option with a data ack is received, which requires at least two RTTs since the very first handshake. Hence the choice of the initial subflow can have an impact on the throughput, especially for short connections. Both the client and the server can create new subflows. Either the host initiates the new connection, or it advertises a couple (IP, port) that the peer can choose to connect to. The policies are local; for instance, in the Linux implementation, the server advertises its ports, but it lets the subflow creation initiative to the client because of NATs that could invalidate the client-advertised addresses. It is worth noting that several subflows can be created from the same IP address with different ports. This may prove worthwhile to exploit the network path diversity, in case the network runs load-balancing [START_REF] Coudron | Cross-layer cooperation to boost multipath TCP performance in cloud networks[END_REF]. There is no standard procedure and the subflow opening/closing strategy depends on local policies. It may be wiser to let clients initiating the connection though, due to the presence of NATs.

Subflow control can also be delegated to a third party controller [START_REF] Coudron | Cross-layer cooperation to boost multipath TCP performance in cloud networks[END_REF] [START_REF] Van Der Pol | Multipathing with MPTCP and openflow[END_REF].

Congestion control

TCP fairness can be a controversial topic: a malicious TCP user who wants more bandwidth can create additional TCP connections (as many download accelerators do) to increase its share at the bottleneck. In the following, we consider well-behaved hosts since this is the usual framework priori to any congestion control reasoning.

Without specific congestion control algorithm, a multipath transport protocol would adopt a similar behavior at the bottleneck since being an end-to-end technology, it has no information over the topology. TCP users would see their bandwidth decrease and MPTCP deployement hindered. Under these conditions, how to achieve both fairness and higher throughput? Knowing if two subflows share a same resource (e.g., a link or a router) would allow to run a congestion control on sets of subflows. Clustering techniques, e.g., [START_REF] Hassayoun | Dynamic window coupling for multipath congestion control[END_REF] and [START_REF] Ferlin | Revisiting Congestion Control for Multipath TCP with Shared Bottleneck Detection[END_REF], have been developed to detect bottlenecks based on delay and loss patterns.

Such techniques need to be foolproof as false negatives generate bandwidth stealing. This is a difficult task without the help from the network, as the heuristics need to work across a wide range of configurations, such as the router buffering policies. Their efficiency is also difficult to evaluate for the same reasons but even if a perfect scheme existed, relying on it depends on the fairness notion.

MPTCP embraces the resource pooling principle, which makes a collection of resources behave like a single pooled resource. This conservative approach considers that all subflows share a bottleneck and that their additive component should be coupled.

MPTCP congestion control algorithms modify the congestion avoidance phase of the TCP congestion control only: the decrease phase remains the same as in TCP. Several congestion control algorithms have been proposed such as Linked-Increase Algorithm (LIA [START_REF] Oda | Design and evaluation of hybrid congestion control mechanism for video streaming[END_REF]) or Opportunistic LIA [START_REF] Khalili | MPTCP is not pareto-optimal: Performance issues and a possible solution[END_REF] (OLIA). They couple the increase MPTCP congestion window with the congestion window of its subflows:

• w i = w i + min( a wi , 1
wr ) per acknowledgement on path i.

• w i = wi 2 per congestion event on path i.

with a being an aggressiveness factor updated once in a while (per window a priori) and equal to:

a = max r ( wi rtt 2 i ) wi rtti 2 * i w i 6
with :

w i the window size on path i rtt i the round trip time on path i

The min in the first equation ensures that MPTCP is never more aggressive than TCP on a single path. It is important to remember that the advertised receive window is shared between subflows. As such, there may be cases where a subflow is capable of sending data, i.e., it has a free transmission window but there is no more space in the receive window -phenomenon known as Headof-Line (HoL) blocking. This may happen when a feature called opportunistic retransmission is implemented [START_REF] Paasch | Improving Multipath TCP[END_REF], which in such cases retransmits data hoping to solve the HoL issue. Opportunistic retransmission can be used in conjunction with slow subflow penalization: if a subflow holds up the advancement of the window, MPTCP can reduce forcefully its congestion window along with its slow start threshold.

Scheduling

. The scheduler chooses when and on which subflow to send which packets.

A good scheduler should attempt to reduce the probability of HoL blocking. For instance, opportunistic retransmission and penalization are reactive mechanisms that waste bandwidth. The Linux implementation currently includes two schedulers:

• The 'default' scheduler sorts subflows according to their RTT and sends packets on the first subflow with free window.

• A round robin scheduler that forwards packets in a cyclic manner on the first subflow with free window available.

Retransmission timeouts (RTO and delayed acks) need to be chosen with great care since a subflow RTO or out of order arrivals can provoke HoL blocking faster than in the single path case, as also explained in [START_REF] Li | The delayed ack evolution in MPTCP[END_REF]. For instance, some of the state of the art schedulers propose to send packets out of order so that they can arrive in order [START_REF] Mirani | Evaluation of forward prediction scheduling in heterogeneous access networks[END_REF].

MPTCP state machine

As a preliminary step before implementing MPTCP in ns3, we needed to formalize the current status of the standard to have a precise specification.

In particular, we had to extend the connection closure Finite State Machine (FSM) described in [START_REF] Ford | RFC6824 -TCP Extensions for Multipath Operation with Multiple Addresses[END_REF] to cover the whole protocol, i.e., while the active and passive close are presented as a diagram in [START_REF] Ford | RFC6824 -TCP Extensions for Multipath Operation with Multiple Addresses[END_REF], we extended the visual description to our interpretation of the standard. The result is depicted in Figure 3, which represents what appears to be the single full representation of the finite state machine of MPTCP.

While being similar to TCP, we chose to split the ESTABLISHED state into the M ESTA WAIT and M ESTA MP states to distinguish between a state where MPTCP waits for a first Data acknowledgement (DACK) and a state where MPTCP can create additional subflows. We also mapped for each MPTCP state the states in which TCP subflows can be, as well as which MPTCP options could possibly be sent. The tabulated study report is available online [START_REF]LIP6-MPTCP open source project repository[END_REF].

Associated challenges

We already mentioned a few challenges in the previous sections. Our stance is that MPTCP is already robust enough by design to fulfill the network and application compatibility goals (as confirmed by the commercialization of successful MPTCP-based products developed by several large corporations such as OVH, Apple, Citrix).

About the requirements described in Section 2.1, the current specification and implementations adequately meet the resiliency requirement; when one link fails, retransmission of the packets is straightforwardly done on another subflow as per the basic scheduler behavior. The main obstacle to MPTCP deployment today remains the throughput and fairness goals. While there are examples of increased throughput through the use of MPTCP (e.g., the fastest TCP connection was done with MPTCP [START_REF] Paasch | The fastest TCP connection with Multipath TCP[END_REF]), this requires specific conditions such as enough buffer and homogeneous paths; there are also cases, as in [START_REF] Ferlin | Multi-path transport over heterogeneous wireless networks: Does it really pay off?[END_REF], where MPTCP performs worse than TCP on the best available path. This does not comply with the objective of doing always better than TCP. MPTCP must acquire the intelligence to distinguish when and which subflows to use to perform well. Reaching this goal is made even harder with the throughput goal since MPTCP is less aggressive than TCP on every subflow.

Path management is also a problem -though less studied -since creating many subflows with the hope of exploiting path diversity can hurt the performance (due to competition between subflows [START_REF] Coudron | Cross-layer cooperation to boost multipath TCP performance in cloud networks[END_REF]). The problem is two-fold:

1. transport protocols being end-to-end, hosts do not know the topology; 2. even if the hosts knew the topology, they cannot enforce a forwarding path. Segmented routing may provide a partial solution in this regard.

As for wide area networks topologies, there usually is more than one path between source and destination. It can be because of intra-domain redundancy or because several ISPs compete on the same path. In this direction, there is ongoing work to exchange topology information between nodes that could solve point 1) above, for instance Path Computation Elements or at the ALTO (Application Layer Traffic Optimization) working group [START_REF]Application Layer Traffic Optimization (ALTO) IETF working group[END_REF].

Topology is a critical information that operators may not be fond of leaking, hence some approaches look at how to provide an overview of the topology through sparsification techniques [START_REF] Scharf | Sparsifying network topologies for application guidance[END_REF]. From the previous technologies, a host can deduce an optimal number of subflows, but this may prove pointless if the forwarding problem (point 2) above) is not solved. As such, solutions in locally controlled environments such as an SDN (Software Defined Network) datacenter seem appropriate.

Thus it is advised to use the correct number of subflows (MPTCP can create more subflows but mark them as backup subflows), no more no less, to reach the optimal throughput. The path management problem also explains why many of the commercial products embed MPTCP into proxy middleboxes (Gigapath3 , OVH4 , Tessares5 ); certainly they grant the benefits of MPTCP to legacy clients, but the middleboxes can also be better informed of the available path diversity thanks to their topological position.

Multipath transport incentives are not limited to throughput aggregation or reliability goals, and as such one could imagine modes where the cost of an interface can affect packet scheduling over interfaces as suggested in [START_REF] Secci | Performance cost trade-off strategic evaluation of multipath tcp communications[END_REF]. The cost could be given by the energy consumption of the interface or depending on its fare rate. The user could even set trade-off levels such as losing 30% of the optimal throughput if it allows for a fairer distribution between subflows.

LEDBAT-multipath [START_REF] Adhari | Ledbat-mp -on the application of lower-than-best-effort for concurrent multipath transfer[END_REF] is one of such alternative modes. Information that used to be of little interest with one path are now helpful in a multipath context. For instance, if the MPTCP layer is aware of the data emission profile, it can adapt the scheduling to favor throughput (bulk transfer) or schedule packets so that they arrive early at the receiver (at the end of a burst).

An MPTCP implementation in ns3

A few MPTCP implementations already exist, some of which already used in production environments such as Apple's voice recognition system Siri. Among the implementations, the Linux one 6 is the oldest one with some impressive achievements (Fastest TCP connection [START_REF] Paasch | The fastest TCP connection with Multipath TCP[END_REF]) and likely used in all the commercial products presented in Section 2.6. Work is also done to improve the MPTCP support on other operating systems such as Solaris7 and FreeBSD8 . Hence asking why developing a MPTCP simulator is a legitimate question. In this section we describe our motivations and the technical aspects of our implementation. We also present a few tools we developed to ease testing and analysis of related MPTCP traces.

Presentation of ns3 and Direct Code Execution

Ns3 [START_REF]Ns3 official website[END_REF] is a popular network simulator in the networking research community as is confirmed by the two previous implementations. Its success is likely due to its General Public License and also because the technical base as well and the support team are trustworthy. It is best described as a C++ discrete time simulator, i.e., events are scheduled in the simulator time and once all events at the specific time are processed, the simulator updates the current time with the time of the next scheduled events. It allows the simulator clock to be independent from the wall clock, most of the times faster. Direct-Code Execution (DCE) is an ns3 extension that allows to load applications compiled with specific options (as well as a fork of the Linux kernel [START_REF] Hajime | Library Operating System with Mainline Linux Network Stack[END_REF]) within the ns3 environment. The advantage is that the simulation runs in discrete time and thus provides results independently of the host CPU. As a comparison, the fidelity of mininet9 , a container-based simulator, decreases inversely with the processing load [START_REF] Tazaki | Direct Code Execution: Revisiting Library OS Architecture for Reproducible Network Experiments[END_REF].

Why an MPTCP simulator?

Simulation traditionally comes handy to (i) run experiments faster, and to (ii) focus the research efforts on the algorithmic part rather than implementation complexity.

Experimenting with MPTCP in the real world can be complex depending on the scenario. Mobility is a major use case and usually requires access to cellular (4G) and WiFi interfaces. Not only does it have a cost but 4G is not ubiquitous and experiments involving wireless channels are time consuming because of the variability and care their setup require. Other experiments may want to assess the behavior under realistic circumstances in terms of subflow latencies, and one way to do so is to rely on accurate path time and latency measurements (e.g., to measure one-way delays as in [START_REF] Coudron | Differentiated pacing on multiple paths to improve one-way delay estimations[END_REF]). Exploiting such traces can prove very challenging in real setups, but are straightforward in discrete time simulators.

Besides the obvious huge time gain in both experiments design and execution time, focusing the research effort on the algorithmic details, e.g., the congestion control algorithm, the scheduler, the buffer dimensioning, is also an important factor when deciding whether using a simulator or a real operating system implementation, especially when looking back at the number of use cases described in Section 2.6. Implementing such solutions into current operating systems usually means adding the features into the kernel. While simulation results may lose fidelity compared to a reasonable kernel implementation, we argue that kernel development complexity can generate bad implementations that can not be easily verified and may not be representative of expected results/analytical models. In those cases, using a simulator model beforehand is reasonably faster.

The usage of an MPTCP simulator can ease reproducibility and can help realize problems ahead of time.

Last but not least, we also think the implementation can serve for education purposes since the model only deals with MPTCP essentials, thus reducing the learning complexity.

Related work

We have been able to access two previous MPTCP implementations, [START_REF] Chihani | A multipath TCP model for ns-3 simulator[END_REF] and [START_REF] Kheirkhah | Multipath tcp in ns-3[END_REF], both done using ns3 as well. These two implementations are similar in many aspects and are compared with ours in Table 1.

Recent developments in ns3 such as TCP option support and generic packet serialization in a wire format made it possible for ns3 to communicate with real stacks. Contrary to previous ns3 implementations that support a subset of the options, ours support full (de)serialization of MPTCP options, which means it can handle a higher variety in options (e.g., 32 and 64 bits encoding for DSNs).

To allow the communication with an external stack such as the linux one, we also implemented standard compliant connection and closing phases, which is another differentiating point from [START_REF] Chihani | A multipath TCP model for ns-3 simulator[END_REF] & [START_REF] Kheirkhah | Multipath tcp in ns-3[END_REF]. Thus our implementation is capable of generating valid tokens based on the (sha1) hash of a random key, and closing a connection requires the sending and acknowledgement of a DSS with the data FIN bit. While the implementation is not robust enough yet to handle all cases, it managed to exchange a file with an external linux MPTCP stack with the use of DCE as reported hereafter.

Contrary to [START_REF] Chihani | A multipath TCP model for ns-3 simulator[END_REF] & [START_REF] Kheirkhah | Multipath tcp in ns-3[END_REF], our implementation is backward compatible with existing ns-3 TCP scripts, following the MPTCP standardization spirit. Thus in our implementation, the connection phase starts with a legacy TCP socket (more precisely a 'TcpSocketBase' see Figure 4) and only once an MPTCP option is received it evolves into an MPTCP socket (see 'MPTCPTcpSocketBase' in Figure 4). This allows for better integration with the general framework, and adds the additional benefit of allowing the MPTCP connection to fall back to TCP. Our hope is to be able to upstream this implementation so that improvements can then be added incrementally.

We also respected an aspect of the specification that could affect the simulation fidelity, i.e., data can not be removed from the subflow sockets until it is acknowledged at both the TCP and MPTCP levels.

Finally, our implementation is also the first to our knowledge to be evaluated against an operating system stack in comparable conditions as described later in Section 4.

Supported and missing features

It is worth noting that Table 1 does compare the three implementations with respect to high-level aspects, without delving in a precise list of features.

It is however worth mentioning the lack of support in [START_REF] Chihani | A multipath TCP model for ns-3 simulator[END_REF][START_REF] Kheirkhah | Multipath tcp in ns-3[END_REF] of many key features needed to draw realistic settings, such as asymmetric routing, subflowlevel buffer management, the possibility to select single-path TCP congestion control algorithms, and the existence of an interface for the scheduler. All these features are supported by our implementation.

The implementation was developed in ns-3.23 while giving care to performance and algorithmic aspects. As such, the fallback capabilities (MP FAIL option, infinite mapping and checksums) of the protocol have not been implemented with the exception of the initial fallback, when the server does not answer with an MP CAPABLE option, i.e., it does not support MPTCP and the client falls back to legacy TCP. This was made possible by extending the existing ns3 code infrastructure; for instance in Figure 4, only the structures starting with "MpTcp" were added. It also spares some resources during the simulation. Indeed the ability to enable dynamically MPTCP on a per connection basis means that our implementation works with all the other TCP scripts.

This obviously implies that we inherit the legacy behavior of TCP in ns3, including desirable features such as the possibility to configure asymmetric link and routing properties. Moreover, one can infer from Figure 4 that new schedulers can be easily interfaced to the simulator and that MPTCP-level buffers can be reconfigured too.

We focused our work on implementing the aspects that could have an impact on the performance such as how data is freed from the buffers: MPTCP requires the full mapping to be received before being able to free the buffer. We detail and describe a list of supported key features of our implementation in Table 2.

Compared to the linux implementation, a major shortcoming of the Network Simulator 3 (NS-3) MPTCP implementation is the lack of the penalization mechanism, which reduces the window of a subflow that blocks the MPTCP window and the opportunistic retransmission feature. Also contrary to the linux implementation that generates DSS mappings just in time to be able to adapt to network conditions, we designed the scheduler to be able to delay the decision until the last minute or to create mappings

SHA1 support

We added an optional SHA1 support in ns3 to generate valid MPTCP tokens and initial DSNs. This allows to communicate with a real stack and also proved necessary for wireshark to be able to analyze the communication.

Scheduling

The fastest RTT and round robin schedulers are available. Congestion control Subflows can be configured to run TCP ones such as NewReno or LIA.

Mappings

As in the standard, data is kept in-buffer as long as the full mapping is received. This is necessary when checksums are used, otherwise this can be disabled to forward the data faster.

Subflow handling

It is done directly by the application that can choose to advertise/remove/initiate/close a subflow at anytime if it is permitted by the protocol. Packet (de)serialization Packets generated along with MPTCP options can be read/written to a wire, allowing an ns3 MPTCP stack to interact with other MPTCP stacks, such as a linux one.

Fallback

If the server does not answer with an MP CAPABLE option, the client falls back to legacy TCP. Other failures are not handled, e.g., infinite mapping or MP FAIL handling as simulating these features is of little interest. Buffer space Buffer space is not shared between subflows, data is replicated between the subflow and the meta send/receive buffers rather than moved.

Path management

We drifted away from the specifications in order to be able to identify a subflow specifically, i.e., we associate a subflow id to the combination of the IP and the TCP port. Nevertheless the implementation is modular so it is possible to replace the subflow id allocation with a standard scheme. in advance. Creating mappings in advance has the advantage of being able to generate mappings that cover several packets. While the throughput gain is negligible, it can spare some of the scarce TCP option space.

Evaluation

We present a simple use case where we compare the linux MPTCP implementation to our NS-3 stack. We chose not to run quantitative tests with the previous NS-3 implementations since they are based on NS-3 versions that date back from late 2009 for [START_REF] Chihani | A multipath TCP model for ns-3 simulator[END_REF] (ns-3.6) to late 2013 for [START_REF] Kheirkhah | Multipath tcp in ns-3[END_REF] (ns-3. [START_REF] Paasch | The fastest TCP connection with Multipath TCP[END_REF]). This gap in versions make the practical evaluation a challenge as well as the interpretation of results, because the ns-3 TCP implementation significantly evolved in the meantime. Hence we tried to choose tools that would allow for seamless testing and analysis between the kernel and ns3 stacks to lighten the burden analysis. We had to do some more development to unify the linux and ns3 evaluation, leveraging on the standardized "pcap "format.

Used tools

As far as MPTCP signaling and data analysis is concerned, there is currently little choice, with only one tool we are aware of: mptcptrace [START_REF] Hesmans | Tracing multipath TCP connections[END_REF]. Mptcptrace is interesting for bulk analysis but we wanted to be able to look at the packet level to ease debugging. Thus we chose to improve the MPTCP support of wireshark [START_REF]LIP6-MPTCP open source project repository[END_REF], which specializes in packet-level network protocol analysis. A capture is on Figure 5. We mainly added the following features:

• MPTCP connection identification: ability to map TCP subflows together based on the key and tokens respectively sent in the MP CAPABLE and MP JOIN options.

• Verification of the initial DSN based on the MPTCP key.

• Display relative DSN, i.e., the first MPTCP sequence number sent being considered as 0.

• Computation of the latency between the arrival of new data throughout all subflows.

• Detection of DSS mappings spanning several packets.

• Detected retransmissions across subflows.

We wrote a tool called mptcpanalyzer [START_REF] Coudron | mptcpanalyzer: a multipath TCP analysis tool[END_REF][START_REF]LIP6-MPTCP open source project repository[END_REF] that leverages these results to produce the plots presented in the next section.

We present in the following a few simulations to compare the linux kernel implementation to our NS-3 implementation. In order to minimize the differences due to the environment and for the ease of reproducibility, we chose to compare the linux and ns3 MPTCP implementations within the DCE 1.7 framework. This means that nodes, routers and links are created by ns3. Every node can be configured with a specific network stack. We always install linux stacks in the routers.

Comparison with linux MPTCP implementation on a 2-link topology

The BDP refers to the number of unacknowledged bytes that can be inflight. It is generally advised to set the BDP higher than RT T * bottleneck capacity to account for queuing delays in both the networks and the hosts. Note that in this case, as DCE runs in discrete time, kernel operations are virtually instantaneous if not programmed otherwise, so only the network latency impacts the RTT. On one path with a bottleneck of 2 Mbps and a RTT of 60 ms, the BDP is about 120 kbits. We run the experiments with libos [START_REF] Hajime | Library Operating System with Mainline Linux Network Stack[END_REF] applied against the linux MPTCP kernel v0.89.

Moreover:

• The scheduler is set to the round robin one.

• The number of paths is set to one (Figure 7a), then two (Figure 7b).

• The forward and backward one-way delays are set to 30 ms on each path.

• We execute using different receiver windows.

We ran 5-second iperf210 sessions between the two hosts without any background traffic on the topology of Figure 6. The size of the router buffers is the default linux one. In Figure 7a, we notice that both stacks make the maximum use of the paths except when it is window limited as for the 10 KB case. We can also notice that the throughput is a little more than the maximum throughput, which is likely due to iperf2. Compared to the one path case, in the two paths case in Figure 7b we get the expected doubling in throughput when the window is big enough. It also seems that the ns3 version is greedier, namely in the 30 KB window case.

In order to check the behavior of the scheduler and thanks to mptcpanalyzer, we were able to plot the relative MPTCP sequence numbers transmitted on every subflow for a 40 KB setup. We establish that DSNs are indeed sent in a round robin manner in both both the linux (Figure 8b) and the ns3 cases (Figure 8a). There are more sequence number for the ns3 case because the throughput was higher for that setup.

Open Problems

Limitations of the current simulations. The current buffer handling in ns3 currently copies data back and forth between the subflows and the meta socket instead of sharing a pool of memory. This is the main difference with other implementations, which could impact the simulation fidelity in tight buffer simulations. One promising solution is Non-Renegotiable Selective Acknowledgements (NR-SACK) [START_REF] Yang | Non-renegable selective acknowledgments (nr-sacks) for mptcp[END_REF]; but sadly the source is not available and this would require ns3 to implement SACK first.

Future work. Authors of [START_REF] Paasch | On the benefits of applying experimental design to improve multipath TCP[END_REF] made an important contribution in applying experimental design to test the Linux stack over a large combination of configurations (buffer size, delay, loss, etc): we hope the experiment could be ported to work with DCE, which would remove the CPU bias for high loads.

Moreover, another interesting usage of our simulator may be on network coding usage within MPTCP. Network coding is an active area of research, which could improve MPTCP characteristics [START_REF] Li | Network coding based multipath tcp[END_REF]. While operating system seem to remain oblivious to network coding, there exists a detailed library for ns311 .

Conclusion

We presented the MPTCP protocol and its new implementation we developed in the network simulator ns3. We described the MPTCP state machine we implemented and how our implementation conforms to many of the features described by the standard. We qualitatively compared our implementation to previous ns3 available implementations. We quantitatively compared it to the linux kernel implementation.

We hope our effort will allow to develop and experiment new schemes and features in an easier way, in order to improve or find new ways of using a multipath transport communication. Indeed MPTCP represents a subset of how multipath protocols could improve our future communications; it may represent a turning point between TCP and SCTP for instance. Relaxing some constraints such as the ordered delivery makes sense for bulk transfers and hopefully network programming interfaces will evolve to provide a smooth transition to multipath protocols.

We open source the code of the simulator in [START_REF]LIP6-MPTCP open source project repository[END_REF].

  MPTCP signals information with its peer through the use of TCP options. To reorder traffic striped on several subflows, MPTCP adds a global Data Sequence Number (DSN) namespace shared among subflows and exchanged through TCP options. The DSN are then mapped to relative Subflow Sequence Number (SSN), i.e., the TCP subflow sequence numbers, through the Data Sequence Signal (DSS) (Data Sequence Signaling), and are acknowledged with what we refer to as Data Ack in the rest of this paper, exchanged through the same DSS option.

Figure 1 :

 1 Figure 1: MPTCP: a shim layer in the stack. Subflows can share the IP address (using a different port) or have different IPs.

Figure 2 :

 2 Figure 2: Illustration of used notations for two subflows.

Figure 3 :

 3 Figure 3: MPTCP state machine.

Figure 4 :

 4 Figure 4: Implementation structure in ns3 code.

Figure 5 :

 5 Figure 5: The wireshark MPTCP analysis section. Framed in red some of our additions.

Figure 6 :

 6 Figure 6: The topology used for the simulations.

Figure 7 :

 7 Figure 7: MPTCP linux kernel and ns3 throughput comparison using iperf2. Each boxplot indicates the min, 1st quartile, median, 3rd quartile and maximum. The x-label indicates the system used and the window size in KB.

Figure 8 :

 8 Figure 8: Repartition of sequence numbers across two subflows with the round robin scheduler.

Table 1 :

 1 Comparison between ns3 MPTCP simulators.

		Chihani	Kheirkhah	Our
	Features	et al. [28]	et al. [29]	implement.
	Option	Partial	Partial	Full
	serialization
	Standard	Connection Connection	Full
	compliance	phase	phase
	Backward	No	No	Yes
	Compatibility
	Ack-aware	No	No	Yes
	buffer mgnt
	Comparison	No	No	Yes
	to OS implem.

Table 2 :

 2 List of supported and missing features.

Preprint submitted to Computer NetworksDecember 30, 2016

Nevertheless an extended API is being standardized in[START_REF] Scharf | Multipath TCP Application Interface Considerations[END_REF] for applications to squeeze more out of MPTCP.

https://www.ietf.org/proceedings/91/slides/slides-91-mptcp-5.pdf

https://www.ovhtelecom.fr/overthebox/

http://www.tessares.net

http://multipath-tcp.org

https://mailarchive.ietf.org/arch/msg/multipathtcp/ugMIu566McQMn8YCju-CTjW9beY

http://caia.swin.edu.au/urp/newtcp/mptcp

http://mininet.org/

http://iperf.sourceforge.net

http://kodo-ns3-examples.readthedocs.org

Acknowledgments

Thanks to M. Kheirkhah for open sourcing his MPTCP source code, Tom

Henderson, Hajime Takizaki for the ns3 and DCE support. Thanks to Lynne Salameh for finding and fixing bugs. Thanks also to Olivier Bonaventure for answering our many questions on the MPTCP standard.


Barbara Hemforth
email: barbara.hemforth@lpl.univ-aix.fr

Lars Konieczny

Proximity in agreement errors

Across languages subject-verb agreement errors have been established when subjects are producing complex (NP PP) noun-phrases (see Bock, 1995, for an overview). Very recently, Haskell & MacDonalds (2002) proposed a locality-based principle, the principle of proximity, to explain a variety of agreement errors in production. They base they argument partly on preferences in verb number marking in sentences with disjunctive noun phrases (e.g., "the hat and the gloves" vs. "the gloves and the hat"), where they found a preference for number marking that matched the local noun. We will present a series of five written production experiments on German constructions with disjunctive Subjects, NP PP Subjects and Subject-Object-verb subordinate clauses. We will show that -although comparable effects can be established for German sentences with disjunctive Subjects -a proximity based principle fails to cover major portions of the results. We propose an account that highlights the dynamics of plural-feature activation and percolation.

Introduction

It is well known by now that occasionally subjects erroneously produce plural verbs following a plural modifier in constructions like (1; quoted form [START_REF] Bock | Broken agreement[END_REF].

(1) The readiness of our conventional forces are at an all-time low.

The mechanism underlying this error is attributed to the marked plural feature percolating up the tree too far [START_REF] Vigliocco | Separating hierarchical relations and word order in language production: Is proximity concord syntactic or linear?[END_REF]. This account is substantiated by the fact that no comparable singular/plural mismatch effect for constructions with marked plural heads has been established so far.

Very recently, [START_REF] Haskell | Proximity does matter[END_REF] proposed a principle of proximity as an alternative explanation. They showed that in disjunctions like (2), subjects have a strong preference to match the number marking on the verb with the more local noun. In addition to distributional evidence, this was taken to indicate that the classical attraction error at least partially and at least in English is caused by number marking on a close interfering noun.

(2) a. The hat or the gloves is/are red. b. Is/are the hat or the gloves red?

We ran a series of five written production experiments to test the proposed mechanisms in German. The logic of the argument is that if we can replicate the mismatch effect (Experiment I) as well as the effect of order in disjunctions (Experiment II) a proximity based explanation should work in German as in English. However, proximity should also work in a case that is special for German, i.e. verb final subordinate clauses where the number marking on an object NP might interfere with number marking on the Subject (Experiments III, IV, and V). Since number marking on the object cannot percolate to the Subject in any way, no effect of an interfering object NP is expected from a "feature-percolating"-approach.

Experiment I

In Experiment I we tried to replicate the well-known mismatch effect in NP PP constructions. Materials were tested for plausibility (all four conditions were approximately equally plausible).

Design

Two factors were varied in this first experiment: The factor "Match": matching (1,4) or mismatching (2,3) number marking on head noun and local noun, and the factors "Number of the head noun": singular (1,2) or plural (3,4) head noun.

(1)Die Farbe auf der Leinwand __________ trocken.

The color on the canvas __________ dry. (2) Die Farbe auf den Leinwänden _________ trocken.

The color on the canvasses _________ dry. (3) Die Farben auf der Leinwand _________ trocken.

The colors on the canvas _________ dry. (4)Die Farben auf den Leinwänden _________ trocken.

The colors on the canvasses _________ dry.

Materials

Sixteen sentence sets (four per condition) were constructed following the pattern in (1) to (4). The materials were pre-tested such that all four NP PP combinations were equally plausible, since effects of plausibility on production errors have been established in earlier experiments [START_REF] Branigan | Language processing and the mental representation of syntactic structure[END_REF][START_REF] Hölscher | Subject-verb agreement in German[END_REF]Vigliocco et al., 1995Vigliocco et al., , 1996)).

Methods

In Experiments I to IV, 62 subjects (all native speakers of German) received a booklet with constructions missing an auxiliary which they had to fill in. All materials were part of the same booklet. Materials were individually randomized. Participants were paid a small amount or received course credits for participation.

Results

Number marking on the head noun clearly affected the percentage of agreement errors (Factor "Number of head noun": F1(1,61) = 22,5; p < 0.001). Neither the factor "Match" nor the number * match interaction reached significance. However, whereas no difference in matching versus mismatching local nouns could be established for sentences with plural marked head nouns (F1, F2 < .5), planned comparisons showed a marginal effect with singular marked head nouns (F1(1,61) = 3.88, p < 0.06; F2(1, 14) = 3.71; p < 0.08). Matching the literature, more agreement errors can be found for singular-plural ordering than for plural singular (e.g. [START_REF] Vigliocco | Separating hierarchical relations and word order in language production: Is proximity concord syntactic or linear?[END_REF].

Discussion

In Experiment I we replicated the well-known mismatch effect (e.g. [START_REF] Bock | Broken agreement[END_REF]. In those cases, where the local mismatching noun was marked for plural, the number of agreement errors increased. In line with earlier experiments on written production (e.g., [START_REF] Branigan | Language processing and the mental representation of syntactic structure[END_REF][START_REF] Fayol | Cognitive overload and orthographic errors: When cognitive overload enhances subject-verb agreement errors. A study in French written language[END_REF][START_REF] Hölscher | Subject-verb agreement in German[END_REF], we found a considerably high number of agreement errors for plural marked head nouns, presumably reflecting a tendency to produce singular marked verb.

Experiment II

Experiment II closely follows the design by Haskell & MacDonalds (2002), trying to replicate the effect of number marking of a local noun on the (written) production of German finite auxiliaries.

Design

In Experiment II, the two experimental factors were "number marking on the local noun: singular (6,7 ) vs. plural (5,8), and "position of the auxiliary: auxiliary following disjunctive NP (5,6) vs. auxiliary preceding disjunctive NP (7,8).

(5) Der Hut oder die Handschuhe _________ rot.

The hat or the gloves _________ red. ( 6) Die Handschuhe oder der Hut _________ rot.

The gloves or the hat _________ red. ( 7) _________ der Hut oder die Handschuhe rot?

_________ the hat or the gloves red? (8) _________ die Handschuhe oder der Hut rot? _________ the gloves or the hat red.

Materials

Twenty sentence sets following the pattern exemplified in ( 5) to (8) were constructed.

Results

As can be seen from Figure 2, number marking on the verb was strongly influenced by the number marking on the local noun (F1(1, 61) = 60,88; p < 0.001; F2(1, 19) = 42,3; p < 0.001). Moreover, more singular marked verbs were produced when the auxiliary preceded the disjunctive NP. However, this effect was mainly due to the particularly high number of singular marked auxiliaries preceding a singular local noun, which shows up in a reliable interaction (local noun * position: F1(1,61) = 19,79; p < 0.001; F2(1,19) = 37,38; p < 0.001).

24

Discussion

Experiment II clearly shows that proximity does have an effect on verb number marking for sentences with disjunctive Subjects. This is fully compatible with data on English number marking presented by Haskell and MacDonalds (2002). However, for disjunctive Subject NPs, there does not exist a clear grammatical rule for number marking. Intuitively, singular as well as plural marking are acceptable when the local noun is singular marked. Experiments III to V will investigate in how far the proximity effect extends to more strongly constrained domains.

Experiment III

A proximity based explanation of the mismatch effect should result in a comparable pattern of errors in German subject-object-verb clauses. This was investigated in Experiment III.

Design

The experimental factors varied in Experiment III were "Match": matching (9,12) or mismatching (10,11) number marking on Subject NP and local object NP, and "Number of Subject": singular (9,10) or plural (11,12) Subject NP.

(9)

Ich habe gehört, dass der Mann die Frau besucht _________. I have heard that the man(masc,nom) the woman visited _________. (10) Ich habe gehört, dass der Mann die Frauen besucht _________.

I have heard that the man(masc,nom) the women visited _________. (11) Ich habe gehört, dass die Frauen den Mann besucht _________.

I have heard that the women the man (masc, acc) visited _________. (12) Ich habe gehört, dass die Frauen die Männer besucht _________.

I have heard that the men the women visited _________.

Materials

Sixteen sets of sentences were constructed, following the pattern in ( 9) to (12). To be sure that the first noun phrase was interpreted as the subject of the sentence, either NP1 (9, 10) or NP2 (11) were unambiguously case marked (nominative Subject in 9,10; accusative Object in 11).

Only the plural-Subject/plural-Object condition (12) did not allow for unambiguous case marking.

Results

Number marking on the Subject had a strong effect on the number of agreement errors: more errors were produced following a plural Subject (F1(1,61) = 17.04, p < 0.001; F2(1,14) = 14,65; p < 0.001). For these sentences, planned comparisons also showed a marginal mismatch effect, in that more errors were produced when the local Object-NP was singular marked (F(1,61)=3.83; p < 0.06; (F2(1,14)=3,46, p < 0.09).

Discussion

With respect to the proximity principle, the results from Experiment III are rather mixed and somewhat surprising. The typical singular/plural mismatch effect that we established in Experiment I for NP-PP-Subjects did not show up here. However, a mismatch effect was found for sentences with plural marked Subjects followed by singular marked objects. Before we discuss this result in more detail, we want to make sure, that in particular the lack of a mismatch effect in sentences with singular marked Subjects is not due to the use of masculine NPs (9,10) as Subjects. [START_REF] Schriefers | Syntaktische Prozesse bei der Sprachproduktion: Zur Numerus-Kongruenz zwischen Subjekt und Verb[END_REF] only found agreement errors in German in constructions with feminine head nouns.

Experiment IV

Experiment IV replicates Experiment III with the only difference that subject-object ordering is marked by semantic plausibility instead of case marking.

Design

As in Experiment III the two experimental factors varied in this experiment were "Match": matching (13,16) or mismatching (14,15) number marking on Subject NP and local object NP, and "Number": singular (13,14) or plural (15,16) Subject NP.

(13) Es ist unwahrscheinlich, dass die Krankenschwester die Spritze vergessen _________.

It is not probable that the nurse the injection forgotten _________. ( 14) Es ist unwahrscheinlich, dass die Krankenschwester die Spritzen vergessen _________.

It is not probable that the nurse the injections forgotten _________. (15) Es ist unwahrscheinlich, dass die Krankenschwestern die Spritze vergessen _________.

It is not probable that the nurses the injection forgotten _________. ( 16) Es ist unwahrscheinlich, dass die Krankenschwestern die Spritzen vergessen _________.

It is not probable that the nurses the injections forgotten _________.

Materials

Twenty sentence sets following the pattern in (13) to (16) were constructed. Whereas in Experiment III case marking was applied to assure that NP1 was interpreted as the Subject and NP2 as the Object of the sentence, sentences in Experiment IV were disambiguated by semantic plausibility.

Results

As in Experiment III, we found a clear effect of number marking on the Subject: More errors were produced in sentences with plural marked Subjects. (F1(1,61)=13,72; p < 0.001; F2(1,19)=14.84; p < 0.001). Again, we did not find a mismatch effect for sentences with singular subjects (all Fs < 0.5). However, the number of errors increased, when a plural Subject was followed by a singular Object (F1(1,61) = 3.90; p < 0.06; F2(1,19) = 3,28; p < 0.09)

Discussion

The pattern of results is strikingly similar to that in Experiment III. Therefore the lack of a mismatch effect in sentences with a singular marked Subject-NP cannot be due to the use of masculine NPs. Admittedly, we only found marginal effects in both experiments. However, marginal effects that reliably reappear in every experiment should be taken seriously.

Experiment V

One of the reasons why attraction errors occur in NP PP verb constructions may be that the local noun is erroneously taken as the Subject of the sentence (Hartsuiker, pers. comm.). So maybe we did not find object attraction in Experiments III and IV because explicit case marking in Experiment III and semantic plausibility in Experiment IV prevented the object from being mistakenly interpreted as the Subject of the sentence. We therefore ran a further study derived from the materials in Experiment III, where case marking could not be used to assign functional roles. Although there is a very strong preference to interpret these sentences as subject-objectverb orderings, they are, strictly speaking, ambiguous. Therefore, we ran a pre-test in order to take care that subjects understood the first noun phrase as the Subject and the second noun phrase as the object of the sentence.

Design

The design was identical to that in Experiment III:

Materials

Materials in Experiment V were identical to those from Experiment III with the only difference that masculine NPs were replaced by feminine NPs, so that neither case marking nor semantic plausibility could be used as a cue for Subject selection.

Methods

In Experiment V, 32 subjects (all native speakers of German) received the same booklet as in the previous experiments. The only difference was that the materials for Experiment III were replaced by those from Experiment V.

Results

A reliable effect of the number marking on the Subject-NP could be established as in the earlier experiments (F1(1,31)=37,73; p < 0.001; F2(1,19) = 50,03, p < 0.001). Although the pattern looks very similar to Experiments III and IV, there was no reliable mismatch effect for sentences with plural head nouns. However -though only across subjects -the interaction match by Subject number marking was marginally reliable (F1(1,31) = 3,61, p < 0.06; F2 ns).

Discussion

Although the results are not as clear as in the earlier experiments with respect to the mismatch effects for sentences with plural marked Subjects, the pattern is very similar. Very clearly, the lack of a mismatch effects for sentences with singular marked subjects is not due to the fact that the Object-NP could not be interpreted as the Subject in Experiments III and IV.

General Discussion

In Experiment I, we established the usual asymmetry between singular and plural head nouns with a mismatch effect showing up for singular head nouns but not for plural head nouns (though only marginally). Similar to [START_REF] Branigan | Language processing and the mental representation of syntactic structure[END_REF] and [START_REF] Hölscher | Subject-verb agreement in German[END_REF], more errors were found following plural head nouns but there was no effect of the number marking on the modifier.

In Experiment II we could show that our subjects were highly sensitive to the number marking on the local noun in disjunctions, although there was a general tendency for plural verbs. The proximity principle assumed by Haskell and MacDonald clearly seems to be at work in disjunctions in German as well. However, this result stands in contrast to Experiment I, where we found an asymmetry between singular and plural local nouns: only plural local nouns modulate the number of mismatch errors in Experiment I.

In Experiments III and IV, we wanted to find out in how far the proximity effect extends to different structures. In German sub-clauses the unmarked ordering of constituents is subject < object < verb. We presented our subjects with unambiguous orderings, disambiguated by case marking in Experiment III and by plausibility in Experiment IV. If a close plural marked noun has an effect on number marking on the verb, there should be an increased number of errors in sentences like ( 10) or ( 14) where a singular subject is followed by a plural object. However, no effect of the number marking on the object is expected if the "percolation-approach" is assumed.

There is no way the number marking on the Object could percolate to the Subject of the sentence, which is a VP-external argument.

The results of experiments III an IV rule out surface proximity: No mismatch effect was established for sentences with singular Subjects. This part of the data is consistent with Vigliocco and Nicol's approach as well as with evidence for syntactic proximity effects shown by [START_REF] Franck | Subject-verb agreement errors in French and English : The role of syntactic hierarchy[END_REF]. However, in contrast to Experiment I, we found a marginal locality effect for sentences with plural subjects both in Experiment III, IV (and V). There were more errors (incorrectly produced singular verbs) following a singular object noun phrase than after a plural object noun phrase. While this part of the data appears to support proximity (more erroneous singular verb productions with singular objects), the earlier half of the results on singular Subjects does not; plural Objects did not increase the number of erroneous plural verb productions. Furthermore, Experiment I on NP-PP-V constructions lacks a proximity effect with plural Subjects, comprising a mirror image of the results obtained on SOV constructions. Apart from Experiment II, there is hence no consistent support for the proximity hypothesis. A plausible conclusion from these experiments is that proximity only shows (very strong) effects on number marking if syntactic constraints are very weak, as in the disjunctions employed in Experiment II. The question remaining is why we do find a mismatch effect on singular Subjects in Experiment I, but on plural Subjects in Experiments III, IV and V? There are at least two possible explanations. Both presume a general tendency to produce singular (unmarked) verbs.

1. When Subjects in SOV constructions are marked for plural, the plural feature becomes activated, but its activation decays so that it eventually gets lost by the time the agreeing verb must be produced. More errors (singulars) will hence be produced with plural Subjects because the reason to depart from the base tendency, the plural marking, gets lost in some cases. This is true for both Subject-PP (Experiment 1) and Subject-Object constructions (Experiments 3, 4, 5) followed by a verb. An intervening plural-Object, however, can reactivate the plural feature, so that it can be retrieved at the verb more easily. Errors in plural-plural-verb constructions are hence reduced compared to pluralsingular-verb constructions. We assume that the reactivation of the plural feature is restricted to verb arguments like Objects. Objects are directly integrated with the verb, so that its features can interfere with those of other verb arguments. In contrast, modifiers of Subject NPs, like genitives or PPs, are not directly integrated with the verb, hence no reactivation of the plural marking of the head noun. The only way to interfere with the head noun is by percolation of the plural feature across the head, increasing the number of erroneous plural productions. 2. An alternative explanation is the use of a rather late monitoring stage, where the basic tendency to produce a singular verb even with plural subjects is inhibited by the plural marking on the object noun phrase. Because an object is a more salient referent than a noun modifier, it is more effective that the latter in inhibiting the singular preference.

It must be noted that our results seem to stand in contrast to those of [START_REF] Hartsuiker | Object-attraction in subject-verb agreement construction[END_REF], who did find an object attraction effect in Dutch SOV constructions. His study differs from ours in two important respects though. Firstly, Hartsuiker employed a different paradigm, a spoken production task, where subjects were forced to respond very quickly, yielding a much larger amount of overall errors. The increased cognitive load in these experiments may have enhanced the probability for agreement errors (for evidence on the role of cognitive load see [START_REF] Fayol | Cognitive overload and orthographic errors: When cognitive overload enhances subject-verb agreement errors. A study in French written language[END_REF]. Secondly, there is evidence that mismatch errors are generally much more frequent in Dutch than in German [START_REF] Schriefers | Syntaktische Prozesse bei der Sprachproduktion: Zur Numerus-Kongruenz zwischen Subjekt und Verb[END_REF]. A reason for this might be that German morphology is much richer than Dutch morphology, so that morphological cues are used more effectively in German. The lack of a mismatch effect in experiments III, IV and V could thus be due to a floor effect in those conditions where the error frequency is already extremely low. However, the floor explanation cannot be applied to experiment I, since the error frequency with plural Subjects is much higher than with singular Subjects and nevertheless no mismatch effect for plurals was found.

Conclusion

A plausible conclusion from these experiments is that proximity effects on number marking are restricted to constructions where syntactic constraints are very weak. Otherwise erroneous number marking appears to depend on the dynamics of plural feature activation and percolation and maybe late pragmatic processing stages.

Figure 1 :

 1 Figure 1: Agreement errors for NP PP constructions

Figure 2 :

 2 Figure 2: Number marking for disjunctive Subjects

Figure 3 :

 3 Figure 3: Agreement errors in SOV-constructions

Figure 4 :

 4 Figure 4: Agreement errors in SOV-constructions

Figure 5 :

 5 Figure 5: Agreement errors in SOV-errors

Acknowledgments

This research has partly been sponsored by the German Research Foundation (He 2310/3). We would like to thank Nicole Büche for running the experiments and Rob Hartsuiker for helpful comments on earlier versions of this work.


Michel Pitermann
email: mpiter@lpl.univ-aix.fr

DYNAMIC VERSUS STATIC SPECIFICATION FOR THE PERCEPTUAL IDENTITY OF A COARTICULATED VOWEL

. However, this conclusion must be confirmed by further experiments.

INTRODUCTION

The nature of information perceptually processed to identify a vowel in continuous speech is still debated at length (see [START_REF] Nearey | Static, dynamic, and relational properties in vowel perception[END_REF] and [START_REF] Van Son | Vowel perception: a closer look at the literature[END_REF] for two discussions). Three kinds of information are often analyzed: (i) vowel intrinsic information contained in its nucleus [START_REF] Assmann | Vowel identification: Orthographic, perceptual and acoustic aspects[END_REF]); (ii) the acoustical contrast between the vowel nucleus and other stationary parts of the speech signal [START_REF] Ainsworth | Intrinsic and extrinsic factors in vowel judgments[END_REF]); (iii) and dynamic information contained in the transitions linking these stable parts [START_REF] Strange | Dynamic specification of coarticulated vowels[END_REF][START_REF] Strange | Dynamic specification of coarticulated vowels spoken in sentence context[END_REF]. Although these three kinds of information seem to contribute to the perceptual identity of a vowel, it is not clear which one is predominant in continuous speech [START_REF] Nearey | Static, dynamic, and relational properties in vowel perception[END_REF].

Some perceptual experiments on speech signals synthesized by means of a vocal tract model were presented in an ASA meeting [START_REF] Carré | On the perceptual caracteristics of "speech gestures[END_REF]. One of them consisted in comparing the vowel identification scores measured for sustained isolated vocods and for stimuli containing only intervocalic transitions. The synthetic vocods containing dynamic information were better categorized. Hence, the authors' conclusion was that the subjects had used articulatory gesture information encoded in the transitions. However, some evidence that a static context can modify the perceptual categorization of a sustained vocod had been shown [START_REF] Nearey | Static, dynamic, and relational properties in vowel perception[END_REF]). As a consequence, the vowel context might suffice to explain the higher identification scores measured for the vocods containing transitions in the [START_REF] Carré | On the perceptual caracteristics of "speech gestures[END_REF] investigation.

Therefore, we extended their experiment to analyze this hypothesis.

METHOD

The method consisted in synthesizing vocods in a vowel continuum by means of a vocal tract area function model. The stimuli contained either static or dynamic information. Nine naive subjects were asked to categorize them in a perceptual assignment. The position in the formant space of the perceptual boundary separating two vowel categories was analyzed as a function of the type of stimuli synthesized. It indicates which kind of information was predominant for the perceptual identity of the synthetic coarticulated vocods.

The vocal tract area function model was a sixtube Kelly-Lochbaum model (Schoentgen and Ciocea 1995b). Five section areas out of six and the total length were the model parameters.

Time series of the model parameters were estimated from a natural speech signal [iai] by means of an acoustic-to-geometric inversion (Schoentgen and Ciocea 1995a). Three types of stimuli were built from these time series: (i) isolated sustained vocods ([V] signals); (ii) the same sustained vocods presented between two sustained [i] ([i#V#i] signals, where # stands for a 20-ms silence); (iii) and vocods containing only [ia] and [ai] transition segments ([iVi] signals). The details are described in Figure 1.

The complete [ia] transition contained 12 samples of the model parameters. Therefore, three sets of 12 stimuli were built. Each of them was replicated six times in order to create a 72-item list of isolated sustained vocods [V] and a 144-item list of mixed [i#V#i] and [iVi] stimuli.

To synthesize an acoustic signal from the time series of the six model parameters, the corresponding values of the first three formants were calculated for x t 12 stimuli containing only 12 stimuli containing only static information each time coordinate (Schoentgen and Ciocea 1995b). The values of the fourth and fifth formant frequencies were kept constant respectively at 3250 and 3700 Hz. Then, the acoustic signal was synthesized on the version 3.04 implementation of the Klatt synthesizer with a sampling rate of 16 kHz [START_REF] Klatt | Software for a cascade/parallel formant synthesizer[END_REF][START_REF] Klatt | Analysis, synthesis and perception of voice quality variations among female and male talkers[END_REF]). To avoid onset and offset noise, the signal intensity was multiplied by a 12.5-ms linear slope at the beginning and end of each stimulus.

sustained [i] dynamic information [a] [i] [i]
Nine French speaking naive subjects, aged between 22 and 30, listened to the two stimulus lists. None reported suffering from impaired hearing. The synthetic signals were shuffled for each participant in order to avoid biased identifications due to the stimulus order of presentation. Five listeners started with the [V] list, the other four with the second list. Two successive items were separated by a 3-second silence. Before listening to his list, each subject could hear 20 items to adjust the signal intensity to a comfortable level and to become familiar with the assignment.

The task was to write down each vowel heard for the [V] list or each vowel identified between the two [i] for the other list. When the sound was not deemed a vowel, the listener could leave a blank or choose the closest vowel. No information was given about the vowels synthesized or phonetic transcription to use, therefore it was a test with open responses.

The signals were played back on BEYER Beyerdynamic dt325 headphones connected to a Sparc 20 SUN workstation containing a 16-bit linear digital to analog converter.

RESULTS

The subjects identified the vocods of the [a]-[i] continuum as [a], [], [ ], [e] or [i]. Some stimuli were la-beled [] because the [ia] transition passed through the point (500, 1650, 2470) Hz in the (F 1 , F 2 , F 3 ) space. However, some participants reported that the [] quality was particularly poor.

Figure 2 shows the [a] identification score as a function of the first formant. The first formant value of an [iVi] stimulus was defined as the highest value used in the synthesis, i.e. the value used to synthesize the corresponding sustained vocod (see Figure 1).

The results were homogeneous with respect to the nine subjects. The only exception was the set of the three sustained isolated vocods [V] corresponding to the three highest values of the first formant (the three right ' * ' signs of Figure 2). For these stimuli, the listeners were divided into two groups: five participants systematically classified the three vocods as [], the other four often labeled them [a] producing approximately the same identification scores for the [V] and [i#V#i] signals.

Figure 3 shows in the (F 1 , F 2 ) space the natural [iai] speech signal used to build all the synthetic stimuli.

DISCUSSION

The results presented in Figure 2 show that the isolated sustained vocods [V] were poorly categorized as [a]. Hence, the nucleus of the coarticulated [a] did not correspond to a good sustained [a]. The values of its first three formants were 630, 1500 and 2400 Hz.

Figure 2 shows also that the static [i# #i] context modified the perception of the synthetic sustained vocods. The same conclusion was found in [START_REF] Nearey | Static, dynamic, and relational properties in vowel perception[END_REF] for [i# #V] stimuli, when two different pairs of [i, ] were used as two similar but different contexts.

The best identification scores were obtained here for the [iVi] stimuli. Six scores out of 12 were higher The mean difference between the identification scores measured for two kinds of stimuli was estimated by:

1/12 12 i=1 (y i -x i ) 2 , (1)
where y i stands for the identification scores measured for the first type of stimuli and x i for the other ones. This estimate led to 0.27 for the difference between the scores measured for the [i#V#i] and [V] stimuli and to 0.54 for the [i#V#i] and [iVi] signals. It shows that the vocods in the middle of the [i#V#i] stimuli were perceptually closer to the [V] than [iVi] signals.

Hence, the vocod context can explain only a small part of the difference between the scores measured for the [iVi] and [V] signals. Therefore, the perceptual identity of the synthetic coarticulated vocods depended mainly on the dynamic of the model parameters.

In the (F 1 , F 2 ) space, the perceptual boundary between the [a] and [] categories was estimated at (340,1800) Hz for the [iVi] stimuli and (580,1560) Hz for the [i#V#i] (their positions are shown on Figure 3). Therefore, the boundary shifts from the [iVi] to [i#V#i] stimuli were +240 Hz for F 1 and -240 Hz for F 2 . It amounts to 340 Hz in the (F 1 , F 2 ) space. A boundary shift can be interpreted as a perceptual overshoot, i.e. a perceptual extrapolation of a for-mant transition beyond the value actually reached [START_REF] Lindblom | On the role of formant transitions on vowel recognition[END_REF]. Therefore, our results bring support to the perceptual overshoot model.

In van [START_REF] Van Son | Vowel perception: a closer look at the literature[END_REF], the author made the hypothesis that a perceptual overshoot occurs when the vowel context has been identified. With an unidentified context, the listener would categorize a vowel token by means of a weighted formant average. Our results are compatible with this hypothesis because a perceptual overshoot was observed for the [iVi] stimuli and the subjects were told what the vowel context was, so it was identified. However, our experiment cannot really back or contradict van Son's hypothesis because the vowel context of the [iVi] stimuli was always identified. To study the hypothesis, we should add vocods with the same transitions but an unidentifiable context. The comparison between the perceptual boundaries between the vowel categories estimated for these signals, the [iVi], [i#V#i] and [V] stimuli would indicate if a perceptual overshoot, or a weighted formant average or a third possibility would have occured.

We have argued so far that our synthetic vocods were better identified by dynamic than static information. These results also bear out the perceptual overshoot hypothesis. However, they are the fruit of one experiment involving a single vowel continuum with one vocalic context. As a consequence, the conclusion must not be generalized.

We have not specified yet the nature of dynamic information perceptually involved to categorize the synthetic vocods. This experiment was not designed to answer that question. As previously stated, the time series of the model parameters were estimated by means of an acoustic-to-geometric inversion applied to a natural speech signal. Thereby, no assumption was made about the dynamic control of the model parameters. To study that issue, we should define and perceptually compare several kinds of dynamic control.

CONCLUSION

The contributions of dynamic and static information to the perceptual identity of a coarticulated vowel were compared in an experiment carried out with stimuli synthesized by means of a vocal tract model. The results show that the perceptual identity of the synthetic coarticulated vocods depended mainly on the dynamic of the model parameters, but the nature of the dynamic involved is still unknown. These results bear out the perceptual overshoot hypothesis. However, owing to the smallness of the corpus, the conclusion must not be generalized.

Figure 1 :

 1 Figure 1: Vocod construction. The graphic shows a fictitious feature taking a high or low value respectively for a [a] or [i] production. To synthesize a sustained vocod, the values of the model parameters estimated at a time coordinate were duplicated for a 300-ms period (stimuli shown on the right-hand side of the graphic). The sustained [i] used in the [i#V#i] stimuli was synthesized in the same way, i.e. copying the first vector of the model parameters estimated in the [ia] transition. To build a symmetric [iVi] signal containing only transitions, a mirror image of a [ia] transition segment was appended to the ordinary one (stimuli shown on the left-hand side of the graphic). The dotted horizontal line shows a pair of corresponding [iVi] and [V] stimuli.

Figure 2 :

 2 Figure 2: [a] identification score as a function of the first formant. The '2', '×' and ' * ' signs represent the results respectively for the [iVi], [i#V#i] and [V] stimuli. Each perceptual boundary between the [a] and [] categories was estimated by means of a linear interpolation between the two scores bracketing the 0.5 value as shown by the dotted horizontal and vertical lines.

Figure 3 :

 3 Figure 3: Representation in the (F 1 , F 2 ) space of the original [iai] speech signal used to build the synthetic ones. The thick and thin ellipses show the perceptual boundaries between the [a] and [] categories respectively for the [iVi] and [i#V#i] stimuli. The thick line is the formant excursion of the synthetic [iVi] stimulus needed to reach the 0.5 identification score.

ACKNOWLEDGMENTS

This research was carried out in the Institute of Modern Languages and Phonetic in Bruxelles. Thanks are due to Sorin Ciocea for carrying out the acoustic-to-geometric inversion used in this work.