Daniel Zaragoza
email: daniel.zaragoza@laposte.net

Modeling TCP Throughput with Random Packet Drops

Keywords: TCP performance, long connections, random packet drops

The present report deals with the modeling of the long-term throughput, a.k.a., send rate, of the Transmission Control Protocol (TCP) under the following assumptions. (i) We consider a single 'infinite source' using a network path from sender to receiver. (ii) Each TCP packet is randomly dropped with probability ; independently of previous drops or any other event/parameter. (iii) The -never changing -receiver window limits the amount of outstanding data. (iv) The receiver acknowledges every packet. (v) The TCP modeled here conforms to the publicly available standards (RFCs) as concerns congestion control. We validate and determine the limits of the different models proposed here using packet-level simulations. The contributions of the present work are the following: (a) We determine three regimes, and their conditions of applicability, depending on : Linear law regime, square root law regime, and timeout regime. (b) As concerns the relationship between the linear and square root regimes, we give additional insights relatively to previously published work. (c) We give the exact equations governing the TCP send rate in any regime. (d) From the exact equation and under the further condition that the path is not saturated, we give and discuss approximations for the send rate of the NewReno variant of TCP. A by-product of these calculations is the distribution of the sender window, independently of any timing or saturation consideration. (e) These approximations give results that are accurate to a few percent when compared to simulation results. Detailed comparison and sources of errors between theory and simulations are also discussed.

Introduction

Introduction

The present report deals with the modeling of the long-term throughput, a.k.a., send rate, of the Transmission Control Protocol (TCP) under the following assumptions. (i) We consider a single 'infinite source' using a network path from sender to receiver. (ii) Each TCP packet is randomly dropped with probability ; independently of previous drops or any other event/parameter. (iii) The -never changingreceiver window limits the amount of outstanding data. (iv) The receiver acknowledges every packet. (v)

The TCP modeled here conforms to the publicly available standards (RFCs) as concerns congestion control; the (many) other aspects of the TCP protocol are left aside. We validate and determine the limits of the different models proposed here using packet-level simulations.

The contributions of the present work are: (i) We determine three regimes, and their conditions of applicability, depending on : Linear law regime, square root law regime, and timeout regime. Except for the timeout regime, expressions are simple enough to allow back-of-an-envelope calculations. Details are given in section 4. (ii) As concerns the relationship between the linear and square root regimes, we give additional insights relatively to our previously published work. See section 4 also. (iii) We give the exact equation governing the TCP send rate in any regime. The model requires the calculation of 16 quantities. These quantities depend on the TCP version considered and some can be simple to obtain. Details are given in section 5. (iv)

From the exact equation and under the further condition that the path is not saturated (definition in section 3.2), we give and discuss approximations for the send rate of the NewReno variant of TCP. A by-product of these calculations is the distribution of the sender window, independently of any timing or saturation consideration. See section 5 also. (v)

These approximations give results that are accurate to a few percent when compared to simulation results. Detailed comparison and sources of errors between theory and simulations are discussed in section 6.

Besides the above mentioned sections, in the next section we discuss related modeling work. In section 3, we give definitions. In particular, in section 3.1, we provide TCP background information and in section 3.2, we give the network-related definitions and the settings used for the simulations. The conclusion and discussion are given in section 7.

In the remainder of the report, we use the following abbreviations and notations.

Mathis et al. [START_REF] Mathis | The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm[END_REF], proposed and discussed the applicability of the -famous -square root law. To quote the paper: "The model applies when TCP performance is determined solely by the congestion avoidance algorithm." In the paper, is the ratio of the number of congestion avoidance events to the number of acknowledged packets. RTT is the average value as measured at the sender and includes possible queuing delays. The receiver window is never a limiting factor. Here, is the -externally given -packet drop probability and RTT is a constant independent of possible queuing created by the connection. We extend to the lower end the domain of applicability of the law by giving a . The high end, where the timeout regime starts, is the same for above 1%. We take into account the receiver window and give a linear law (in ) together with a limit below which the linear law is applicable. We also study the case where the link (path) is saturated with a limited but packet drops are never due to buffer overflow. The result of our study is the determination of three regimes as discussed in section 4.3 and illustrated in Figure 5.

Padhye et al. [START_REF] Padhye | Modeling TCP Reno Performance: A Simple Model and Its Empirical Validation[END_REF] extend the square root model by taking timeouts into account for the Reno variant of TCP. The model is known as the PFTK model. They provide analytic expressions, which are also used in TCP-friendly protocols. They compare the results of their model to recorded and analyzed transfers performed on the Internet with an implementation using the Reno variant. They define loss indications as TDs and TOs. The ratio of the number of loss indications over the number of packet sent is taken as an approximation of . They also discuss the different assumption used in their model. Not included in the model are the subtleties of FR and the time spent in slow-start. In their model, the path is never saturated. For sufficiently small their model recovers the square root law. The packet loss process is simplified so that if one packet is lost in a 'round' (a RTT) the following packets in the round are also lost. The first loss in a round (with probability ) is i.i.d. from round to round. The RTT is independent of . The technique used in the PFTK model is that of Markov regenerative process with rewards. In less technical terms, the send rate is obtained by calculating the average window during a cycle divided by the average duration of a cycle. A cycle includes TD and TOs events. The PFTK model is revisited by Dunaytsev et al. in [START_REF] Dunaytsev | The PFTK-model revised[END_REF] to include fast retransmit and the slow-start after a timeout. Altman et al. [START_REF] Altman | A Stochastic Model of TCP/IP With Stationary Random Losses[END_REF] and Barakat [5] use a different mathematical technique to obtain the send rate for long connection. The model accounts for "any correlation and any distribution of inter-loss times." When timeouts have no or little influence, the square root law is improved to account for the variance and correlation function of the inter-loss event process. To quote the paper, "the classical square root formula is generalized to the case of stationary ergodic losses." In that paper also, is the ratio of the number of loss events to the number packets sent (equation ( 8) in [START_REF] Dunaytsev | The PFTK-model revised[END_REF]). Both papers use the results of [START_REF] Mathis | The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm[END_REF] to account for timeouts. Both papers emphasize the importance of separate modeling of the TCP window evolution (dependence between RTT and window, window limitation, fluid vs. discrete models) and the modeling of the network (diversity of loss event processes). Similarly to [START_REF] Mathis | The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm[END_REF], model and assumptions are validated against analyzed traces of transfers over the Internet with an actual implementation of NewReno.

A number of other mathematical techniques have been used for modeling the throughput of TCP. An example of technique is Markov chains [START_REF] Fortin-Parisi | A Markov model of TCP throughput, goodput and slow start[END_REF].

Using the same technique as [START_REF] Mathis | The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm[END_REF], Parvez et al. [START_REF] Parvez | An Analytic Throughput Model for TCP NewReno[END_REF] model the send rate of TCP NewReno. They model the fast recovery of NewReno, the timeout behavior, and they use a two-parameter , loss model to capture the frequency and burstiness of the loss process. is the packet drop probability and is the probability of drop of the following packets in the same RTT as the first drop ( 1 in the PFTK model). Their model is analytic and gives an expression for the send rate of NewReno in their equation (29). Surprisingly, the equation shows a 1/ , rather than a 1/ , term in the numerator, which indicates a faster growth to infinity with decreasing . They validate the model using various simulation scenarios and "All the losses in a single window of data are counted as one loss event. The loss event rate p is taken to be the ratio of the total number of loss events to the total number of segment transmissions, in the period of interest. The average round-trip time R was measured at the sender, and RTO was approximated as 4R."

From a high point of view, in the present work, we are interested in obtaining insights, through modeling, on the performance obtainable with the flow and congestion control algorithms used in TCP. For that purpose, we let the receiver window, which governs flow control, be fixed throughout the connection. We also let the receiver acknowledge every packet instead of using delayed acks. The delayed acks strategy is known to degrade the send rate; besides the fact that the relationship RTT/delay timer introduce complications for a correct modeling. As concerns the congestion control part, which effect is to reduce the send rate when a loss is detected, we use the simplest -and easiest to implement -drop policy; that is, i.i.d. random packet drops. When a packet appears, it is dropped with probability and passes with probability 1 , independently of previous events or any parameter. In previous work, we have used a less simple renewal error process in which errors occur according to a renewal process independently of whether a packet is present or not. We have not seen much difference compared to the simple random drop policy. Additionally, following [START_REF] Altman | A Stochastic Model of TCP/IP With Stationary Random Losses[END_REF] and [START_REF] Barakat | TCP/IP Modeling and Validation[END_REF], performance in CA is better when the loss process -seen by the sender -has high variance and/or shows correlation. As a final general remark, the parameters (the loss event rate) and used in the literature are those measured at the sender. Here, our point of view is that (the drop probability or drop rate) and are externally given.

Turning to details, the full model approach developed in section 5 is exact. Under the further assumption that the connection does not saturate the path we develop approximations for the NewReno variant of TCP, which follows the AIMD (additive increase multiplicative decrease) congestion control principle.

That assumption may be relaxed under conditions discussed in section 6. In the present approach, the operation of TCP is decomposed in 5 basic elements. For a given TCP version, the determination of the send rate requires the calculation of 16 quantities, a number of which are simple to obtain. Our approach does not require to take into account the slow-start phase after a timeout. It does not require sophisticated stochastic process machinery (at least, in the approximations we give); however, it requires a microscopic (packet-level) analysis of TCP operation and subtleties.

To conclude this section, we note that the number of TCP variants in operation on the Internet has greatly increased between the measurements performed by Medina et al. [START_REF] Medina | Measuring the Evolution of Transport Protocols in the Internet[END_REF] in 2005 and those performed by Yang et al. [START_REF] Yang | TCP Congestion Avoidance Algorithm Identification[END_REF] in 2011 (their figure 1 presents a nice synthetic overview of TCP congestion controls). From Rewaskar et al. [START_REF] Rewaskar | A Performance Study of Loss Detection/Recovery in Real-world TCP Implementations[END_REF] we learn that implementations in the popular operating systems Linux and Windows have a of 200 ms instead of the 1 second specified in the standard (see next section). The 'vagaries' of real world transfers using TCP are analyzed by Qian et al. [START_REF] Qian | TCP Revisited: A Fresh Look at TCP in the Wild[END_REF]. Finally, Mathis [START_REF] Mathis | Reflections on the TCP Macroscopic Model[END_REF] (as of 2009) note that as ISPs (Internet Service Providers) exert more control on the traffic traversing their networks a paradigm shift (from TCP-friendly to something else) is needed. To quote his words: "Needless to say our time tested model (the square root law) will no longer generally apply. C'est la vie". Overall, the papers mentioned here tend to indicate that the job of modeling the performance of TCP will be a tough one.

Definitions

TCP background

In this section we develop the aspects of TCP that are the most relevant to our purpose. (i) TCP is a window-based transport protocol. (ii) It provides flow-control. (iii) It provides congestion control. (iv) Retransmission timeouts are important for its performance.

RFC4614 [START_REF] Rfc | A Roadmap for Transmission Control Protocol (TCP) Specification Documents[END_REF] provides a roadmap to TCP-related documents, as of 2006. Documents of interest here that update previous ones cited in RFC4614 are: RFC5681 [START_REF] Rfc5681 | TCP congestion Control[END_REF], -TCP congestion control -, RFC6582 [START_REF] Rfc6582 | The NewReno Modification to TCP's Fast Recovery Algorithm[END_REF] -TCP NewReno -, and RFC6298 [START_REF] Rfc6298 | Computing TCP's Retransmission Timer[END_REF] -TCP RTO calculation.

TCP is first specified in RFC793 [START_REF]Transmission Control Protocol[END_REF]; further details are clarified in RFC1122 [START_REF] Braden | Requirements for Internet Hosts --Communication Layers[END_REF].

TCP is a window-based protocol that provides a reliable, byte-oriented, data transfer between processes which, most commonly, run on different computers (hosts) themselves located on different networks. In the original specification, TCP can send and receive variable-length "segments". However, most implementations refrain from sending variable length segments unless some conditions are met, e.g., sending a segment empties the send buffer or the Nagle's algorithm is disabled [START_REF] Wright | TCP/IP Illustrated, The Implementation[END_REF]. TCP provides reliability "by assigning a sequence number to each octet transmitted, and requiring a positive acknowledgment (ACK) from the receiving TCP. If the ACK is not received within a timeout interval, the data is retransmitted." Further, "The sequence number of the first octet of data in a segment is transmitted with that segment and is called the segment sequence number. Segments also carry an acknowledgment number which is the sequence number of the next expected data octet of transmissions in the reverse direction." How the timeout is calculated is specified in RFC6298 and is discussed below. In the present work, we use a TCP that is packet-oriented; that is the basic unit of transmission is the packet rather that the octet.

TCP is a window-based protocol which provides flow control to avoid a sender overwhelming a receiver. For that purpose, "The receiving TCP reports a "window" to the sending TCP. This window specifies the number of octets, starting with the acknowledgment number, that the receiving TCP is currently prepared to receive." At the sender and at any time, the amount of data outstanding and not yet acknowledgeda.k.a. the "flight size" -is , where , is the sequence number of the next unit to send and is the sequence number of the still unacknowledged unit. Under no circumstances and at no time , where is the receiver window, a.k.a. . is not necessarily fixed and varies according to the speed at which the application "reads" the received data during the course of a connection. Note that changes only with advancing acks while increases when sending new data and decreases back to when retransmitting missing data.

A form of indirect/implicit flow control may also exist at the sender. RFC793 states: "When the TCP transmits a segment containing data, it puts a copy on a retransmission queue and starts a timer; when the acknowledgment for that data is received, the segment is deleted from the queue. If the acknowledgment is not received before the timer runs out, the segment is retransmitted. In practice, implementations [START_REF] Wright | TCP/IP Illustrated, The Implementation[END_REF], maintain a "send buffer" (a.k.a. the socket buffer) which contains the unacknowledged data and which is fed with data from the user buffer. The size of this buffer may have impact on the TCP performance. In the present work we do not deal with this matter and assume ideal operation at the sender.

TCP also provides congestion control (RFC5681) by way of the slow-start and congestion avoidance algorithms. For that purpose two new variables are used: the congestion window, and the slow-start threshold, , noted here. A TCP switches between slow-start and congestion avoidance according to the relative values of and . More precisely, "The slow start algorithm is used when cwnd < ssthresh, while the congestion avoidance algorithm is used when cwnd > ssthresh. When cwnd and ssthresh are equal, the sender may use either slow start or congestion avoidance." Further, "The initial value of ssthresh SHOULD be set arbitrarily high (e.g.,to the size of the largest possible advertised window), but ssthresh MUST be reduced in response to congestion." Here, we use congestion avoidance when meaning that 1. Rephrasing RFC5681, during slow-start is increased by one for each increasing ack received; during congestion avoidance is increased by one for each of increasing acks received. To improve performance when the receiver acknowledges every other segment and to discourage misbehaving receivers, a TCP may use Appropriate Byte Counting as per RFC3465 [START_REF] Allman | TCP Congestion Control with Appropriate Byte Counting (ABC)[END_REF]. In our TCP, the receiver acknowledges every segment received and the sender counts the increasing arriving acks before increasing the congestion window in congestion avoidance; this is to avoid numerical rounding errors.

The sending of data (new or retransmission) by TCP is governed by the following equations.

Where is the amount outstanding ("FlightSize") when the sending TCP function (e.g., tcp_output()) is called, is the amount to send, starting from . Such mode of operation has implications on the burstiness of the traffic produced by a TCP. These implications are well-known and recommendations in RFC6582 are made to limit the possible bursts of packets sent at once, for example, using an additional variable . In the present report, , and are in unit of packets (segments). Further, as never changes, we set ( * ). No attempt is made to limit the data bursts.

TCP uses two methods to detect missing data: retransmission timeout and duplicate acks.

When the retransmission timer fires, a timeout occurs and 1, , thus 1 and the missing packet is retransmitted. If this is the first retransmission of the packet, min /2 , 2 . is left unchanged in case of multiple retransmissions of the same packet. The connection proceeds in slowstart mode. As a consequence, duplicate packets can be sent after a timeout; duplicates can also be lost, though.

The second method is via duplicate acks, typically three, which means that four consecutive acks request the same sequence number. From RFC5681, "After receiving 3 duplicate ACKs, TCP performs a retransmission of what appears to be the missing segment, without waiting for the retransmission timer to expire." This is called fast retransmit. We abbreviate this event as TD, for Triple Duplicate acks. "After the fast retransmit algorithm sends what appears to be the missing segment, the "fast recovery" algorithm governs the transmission of new data until a non-duplicate ACK arrives." With a small abuse, we abbreviate a successful fast recovery as FR. When a TD occurs, min /2 , 2 (same as for timeouts), and the missing packet is retransmitted. The previous value of is restored to allow the sending of new data with further arriving DAs and 3. Note that no new data is sent here even if it were possible (specifically, when 4). For each subsequent duplicate ack received, 1 and new data may be sent. Finally, "When the next ACK arrives that acknowledges previously unacknowledged data, a TCP MUST set cwnd to ssthresh (the value set in step 2). This is termed "deflating" the window." At this point, depending on the TCP version used, FR occurs or not, more details are given below. Assume FR occurs; thus, . "Normal" operation resumes, that is, is increased either to 1/ if or to 1 if 1 and new data is sent depending on being positive. In both cases, the connection proceeds in congestion avoidance mode.

If any one of the retransmissions is also lost then FR does not occur, instead, a timeout follows. We do not address this matter here.

For TCP Reno, FR occurs on receipt of the first ack requesting unacknowledged data. The loss of only one packet in the previous window of data has no further consequence. If there were drops, then another TD or a timeout follows. Under the assumption 1, let be the window at which drops occur, let be the distance, in packets, between the first two drops, if then a timeout follows; otherwise, a TD follows if, in turn, enough acks return from the new packets sent during the TD-FR period.

For TCP NewReno (RFC6582), FR occurs when all data outstanding at the time TD occurred is acknowledged. Note that the loss of the new data sent between TD and FR lead to a new congestion event. Because NewReno is the focus of the present report, we give an example of operation in Figure 1. Without loss of generality for the present purpose, we renumber the first loss as "1" and resynchronize time. When TD occurs (on the arrival of the ack from "5"), the missing packet is retransmitted, 6, and both and are adjusted. is large enough and does not change so that . The flag . On receipt of the subsequent ack (from "6"), new data is sent. When the first loss is recovered, FR is not yet over for NewReno. Following RFC6582, the missing packet is retransmitted and a new data packet is sent. Further new data is sent on receipt of the ack from "7", which was new also. FR is over on the receipt of the acknowledgement 7 ; , 1

; normal operation resumes and new data is sent. In the same RTT, the receipt of the ack from "8" will lead to 1/ as it must in congestion avoidance. For the purpose of collecting further statistical data on timeouts and TD, we record the highest sequence number sent during the TD-FR period in the variable _ ; if one or more of these new packets is lost a TD or a timeout will follow FR.

The example also leads to the following remarks.

(i) On FR, the amount outstanding is , if , no packet is sent. With 1/ on FR, it will catch up on receipt of the ack from "9" in the same RTT; this requires that neither "8" nor "9" are lost. (ii)

The loss of any of the retransmissions will lead to a timeout in standard TCP. (iii) In congestion avoidance (with proper time resynchronization and a receiver acknowledging every packet), the window increase is one per RTT but the increase can occur almost any time in the RTT until the next packet drop. That remark is important for the analysis of section 5.

As concerns timeouts, RFC6582 states the following: "After a retransmit timeout, record the highest sequence number transmitted in the variable recover, and exit the fast recovery procedure if applicable." Subsequent TD events are ignored if they do not cover more than . This is to avoid spurious TDs. Our TCP follows RFC6582 only for the first retransmission after a timeout. For subsequent retransmissions of the same packet 0, thus enabling all TD events. Further, a flag is used for the purpose of collecting timeout statistics.

We now give further useful details on the TD event until the receipt of all duplicate acks (DA) that elicited the TD. Assume that and that the number of losses in the window of size is 1 3. After the TD event and the retransmission of the missing packet, the window increases with the arrival of DAs from 3 up to , where no packets are sent ( is used here to avoid confusion with ). Subsequent DAs allow the sending of new packets, the number of which is noted , provided the receiver window allows. Almost immediately we have the following results, whether queuing occurs or not.

.

(

is the window when all "first" DAs have been received, and comes from

3 3. , , . (3)
is the number of new data packets sent with the receipt of 'first" DAs.

Although of secondary importance for our purpose, we also have 3 0, where is the number of DAs without sending (because ). Finally, , where is the amount outstanding when all "first" DAs have been received.

The number of packets sent during this period is 1

, including the retransmission.

The above results lead to the following comments.

(i) Assume is large enough; for 1, the number of packets sent is /2 in the RTT between TD and FR. (ii) If , is not large enough, then, only new packets are sent. In particular, for a TD at a burst of /2 1 packets is sent on FR. (iii) For 1, the number sent increases by one for each RTT corresponding to the retransmission and acknowledgement of a lost packet; provided no retransmission is lost again. (iv)

As concerns , the worst case is for ∆ 1 packet, which frees only one place in the receive buffer. Thus the sending of new packets may stop due to receive buffer limitation. As a consequence, a burst of packets will be sent on the subsequent FR.

(v)

The retransmission timer is set only at the time of TD; thus, up to / previous losses can be retransmitted before a timeout occurs.

(vi)

With TDFR events only, the time of window increase in a RTT in normal operation depends on the previously sent packets. Thus the sentence: "the window increases 'sometimes' in a RTT".

The final point of this section is the calculation of the retransmission timeout, which depends on the RTT of the connection, as defined in RFC6298. There are four points to consider: (i) Setting of the initial RTO (ii) Computing a proper RTO. (iii) RTT measurement. (iv) Setting the RTO for multiple retransmissions of the same packet.

(i). The initial RTO, when no RTT measurement has been made yet, is set to 1 second (it was previously 3 seconds). The "backing off" discussed below applies.

(ii). When RTT measurements, , say, are available, the RTO is computed in the following two steps; assuming precise timing (zero clock granularity).

(a) First measurement: , /2, max 1 s, 4

). (b) Subsequent measurements:

1 1/4 1/4 | |, 1 1/8 1/8 , max 1 s, 4 ).
With constant, the first measurement gives max 1 s, 3

). On the tenth measurement, max 1 s, 1.113

), and on the twentieth, max 1 s, 1.006 ), etc. Therefore, for a large connection, if 1 second . A number of popular implementations use a of 200 ms instead of 1 second for the setting of the RTO value.

(iii). RTT measurements are performed, at least, once per RTT outside of any loss event, and using new data. This means that retransmissions are not timed and measurements are not performed during TD-FR periods. On FR, normal operation resumes and the first segment sent is timed. Generally speaking, RTT measurements are taken once per "flight" at the beginning of the flight. This has no particular implication for the present work; however, spurious timeouts can occur with too large (in relative terms) and router buffers over slow links.

It is important not to confuse timed segments for the purpose of measuring the RTT and setting the retransmission timer on segments. Under normal operation, on retransmission after a timeout, and on FR, the timer must be set on each packet sent (timed or not) -in practice, when a burst of packets is sent, the timer is set on the first of the group. During a TD-FR period, the timer is set only on the first retransmission.

(iv). Backing off the RTO. When a packet is retransmitted the RTO is multiplied by two. When the same packet is retransmitted multiple times the RTO is multiplied again by two, up to four times ( 264 or up to the maximum RTO of 60 seconds. According to Windows implementation public documents, the retransmission of the same packet is limited to five times, at which point the connection is aborted. We do not consider this case here. Our full model (as other models) does not consider the maximum time, only the doubling up to five times.

Our TCP follows the above cited RFCs with the following specifics. The receiver acknowledges every packet received. The send buffer is "infinite". The initial window is 2 packets. The RTO value and RTT measurements are set with precise timing; that is, the of RFC6298 is zero. For TD events, the retransmit timer is set for the first retransmission only. Our TCP does not send new data on the first two duplicate acks before TD occurs (no "limited transmit"). We use 1, which give better performance than the alternative. More precisely, the throughput is better by 4%, 14%, 15%, 13%, and 10% for 1%, 5%, 10%, 15%, and 20%, respectively. Clearly, the choice of is not without consequence, everything else being the same.

Network settings

The network setting used in this report is illustrated in Figure 2. There is a single long TCP connection using the links. Packets are dropped by the drop module on the receiver side. Acknowledgements are never lost. The router node has sufficient buffer so that no packets are dropped due to buffer overflow. A traffic module collects traffic information -arrivals and departures -at the entry and exit of the router for cross-checking purposes. The TCP sender and receiver are also instrumented to collect data for further checking and model validation. In order to collect data for the model developed here, each of the TCP packets includes additional information such as window, window change flag, type of retransmission; this information is put in the packet at the time it is sent. Obviously, such information is not included in a real TCP packet. In a simulator it is easily done for the purpose of modeling and evaluation.

With reference to Figure 2, we note ∆ ⁄ and ∆ / , the transmission times of data packets The round-trip time -not counting queuing -is 1/ 1/ , where is theconstant -round-trip propagation delay. RTT is the time required to send a packet and receive its acknowledgement. By linearity, RTT is the same from any point of view; sender output, node input, etc. In the present work, RTT is a constant and does not include possible queuing. We let /∆.

gives the number of packets that can "fit" in the link of capacity . is similar to the well-known / .

We let .

1, means that, in the long term, the link (path) is not saturated; 1 means that the link (path) is saturated.

When the link is saturated, the long-term queue content is 1. The "1" accounts for the packet in transmission. The number of packets outstanding is , are 'in the link', thus the difference is in the waiting queue and one in transmission. In order to be complete, we would have ∆, the RTT measured when queuing occurs. We do not use this observation here.

A second observation is that when the link is saturated, the number of packets in the link is per RTT. is also the number of returning acks per RTT. Therefore, for , the window increase is less than one per RTT. For example, at , , it requires ∆ seconds to increase the window by one. Further note that each window increase adds one packet to the queue. Table 1 gives the data for the different simulation scenarios we consider (with ∆ / 120 μs fixed). The approaches and models developed below, as well as the various approximations, are compared with packet-level simulations according to the network parameters of Table 1. For each simulation, the connection transfers 10 millions packets when 0.5% and 20 millions packets otherwise (to increase the number of useful events). We verified that with such numbers there is negligible variability (within +/-0.2%) in the results of various simulations with the same parameters; we therefore compare our calculations with the results of one simulation only. Our implementation follows the details given in section 3.1. In particular, is calculated from the amount outstanding rather than the congestion window. Fortunately, although there are differences observed in our simulations, these differences are so small and rare that we can continue to use the congestion window as a substitute for the amount outstanding in models.

Simple send rate models

In this section we develop 'simple' send rate model that take into account only the TD-FR events. We further study their domains of applicability. Finally, we compare the theoretical results with simulations.

Square root law

The square root law [START_REF] Mathis | The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm[END_REF], is widely used for obtaining the throughput of a long TCP connection in congestion avoidance.

In congestion avoidance and assuming a receiver window large enough, the sender window repeats cycles of increases between /2 and and instantaneous decrease to /2 when a drop occurs. Further, the window increases at the rate of one per RTT. The sender window gives the number of packets sent; the number sent in a cycle is thus Besides the congestion avoidance assumption, the above reasoning requires that the window increase is one per RTT (recall that RTT is a constant independent of queuing) and a receiver acknowledging every packet. This further requires that the connection path is not saturated; otherwise, only acks return per RTT and the increase is not one per RTT. With our notations, eq 1 that is, min / , which relates min to the 'BDP' of the path.

We do not develop here the case of a saturated path.

In summary, for a receiver acknowledging every packet and no limitation on , the square root law is:

/ , with eff / , for min / . ( 4
)
It is clear from the expressions above that the square root model is to be used with caution below min ; the send rate grows without bounds when gets small. On the other hand, the domain of validity of the law extends quickly to small as .

Linear law

The results presented in this section have been previously published in [START_REF] Zaragoza | Challenging the Square-Root Model for TCP Send-rate[END_REF]; here, we develop a bit more on the matter.

Under the assumption that the receiver acknowledges every packet, that the sender window is limited to , and that the path is not saturated, the linear law (in ) is: The argument is illustrated in Figure 3.

1 1 , with eff 1 1 , for max . (5)
To simplify notations, let . Let be the average time between drops. Similarly to the case of the square root law, the number of packets sent in congestion avoidance until is reached for the first time is 1 in the time , with 1 . After that, the number of packets sent is in the time . The send rate is thus . It remains to calculate . Now, is the average number of RTTs between drops and 1/ is the average number of packets between drops. During the congestion avoidance phase the average number of packets sent is per RTT, which we round up to . With that approximation, the number of packets sent is . Letting 1/ gives 1/ .

Plugging the expression for into the equation gives / / . The result above follows after a little algebra.

The result applies under the condition that ; otherwise the window does not return to . The condition is rewritten as 1, which is approximated as . For completeness, when the path is saturated (recall, no buffer overflow only random drops), we have the following linear law (here, time is not counted in units of RTT but in units of ∆ / ):

1
The above conditions mean that the link does not go idle before the retransmission of the missing packet and that the link does not become saturated on FR; that is, 1 /2 1, and that many packets are sent back to back because none are outstanding.

Domains of validity

For convenience, we summarize the previous results. Under the conditions that the receiver acknowledges every packet and that the path (link) is not saturated, we have: Remarks:

-The maximum long term send rate is , which gives effmax .

-If we let , that is, at the onset of path saturation, we have that max min . .

-A path not saturated means that . Therefore, max min for 1 4/3 1.15.

The following Table 2 gives the network parameters used for the validation, the conditions of applicability of the simple models, and the settings for which timeout statistics are discussed below.

The comparison between the eff calculated and measured from simulations is illustrated in Figure 4.

From Figure 4 [(c) is a zoom of (a)], it can be seen that both the square root and the linear models are accurate in their respective domain of validity and up to 1 2%. The linear model is accurate up to max . The case (2MR200W44), where 33.3, is shown in Figure 4 (b) as an illustration that when the path can be saturated, the linear model without saturation does not apply; rather the more complicated linear model under saturation must be used. We make the following observation. From Figure 4 (b) and (d), it can be seen that eff 12 for 1%, and eff 8 for 2%, whatever large is R . On the other hand, from Figure 4 (c), it can be seen that the linear model is accurate up to about 2%. The error is slightly above 2% at 0.5% ( eff 10.7) and 1% ( eff 9.5), and 6% at 2%, ( eff 7). This suggests that using parallel connections with a R 12 each to transfer a large file can increase the throughput as well as increase

SQRT 2M-R100-W12 2M-R100-W24(*) 2M-R200-W24 2M-R200-W44(*) 10M-R40-W32 10M-R50-W44(*) 10M-R100-W44 (d)
the link utilization for 0.5 2%. Under random packet drops, connections will see the same drop probability; thus, each connection will have the same eff , which in turn, add up to link capacity.

The above discussion lead to consider three regimes for the TCP send rate under random packet drops: linear regime, "sqrt" regime, and timeout regime, depending on . This is illustrated by the following Figure 5. The "sqrt" regime is not always present as exemplified by the case for R 12. On the other hand, the linear regime may not be "visible" for large R and . In this case, the "sqrt" regime applies for a wide range of up to the timeout regime.

We split the analysis of simulation results in two parts: below 1% and above.

In Figure 6 we give the average simulation results (using NewReno) for four network settings and for up to 1%. "LE" stands for 'loss events' as measured at the sender, the labels "%rxtFR(n)" indicate the percentage of retransmitted packets on successful FRs. We make the following comments. Loss events are essentially made of TDs. For up to 0.1 %, there is essentially one packet dropped and retransmitted. Starting from 0.5%, double packet drops cannot be ignored. At 1% and above, timeouts cannot be ignored although they constitute only about 1% of the loss events; this is because is 1 second. This gives us a first indication that the timeout regime may start at 1%. Turning to the second part of the analysis, in Figure 7, we give more details for ranging from 1% to 10%. The results represent the averages for the five settings mentioned in Table 2 as 'TO stats'. From Figure 7 (a) we see that the loss events (TD + TO) rate greatly underestimates the packet drop rate.

As increases, the importance of TDs decreases (approximately linearly) from 98.6% down to less than 70% of the loss events while the importance of timeouts increase (approximately as . ) from 1.4% up to 43%. At 2%, the proportion of TOs is 3%, at 3% that proportion is 5.5%. Thus, we set at three percent the threshold [TO/(TD + TO)] for the timeout regime, which, in turn, correspond to 2%.

Figure 7 (b) shows that the proportion of TDs followed by FRs is high, slightly smaller than 1 . The label 'TOFRxtd' indicates timeout occurring after a successful FR due to the loss of new packets sent in the TD-FR period. Not counting the unexplained peak at 5%, the contribution of this type of TO is up to 10%. Below 5%, the major contribution to timeouts comes from TDTO, that is, the loss of retransmissions in TD-FR periods. Above 5%, the major contribution to timeouts comes from timeouts at low window, 2 or 3, that is, the loss of one packet leads to a timeout.

To conclude this section, we investigated the case where retransmissions are never dropped, which is possible with a simulator. The results are shown in Figure 8.

Figure 8 (a) suggest that the possible improvements of the send rate are not clearly visible. Thus, timeouts due to low window still govern the performance of TCP under high packet drop rates. Figure 8 (b), gives the percent improvement when either the retransmissions in TD-FR periods (flag rtxTD) or all types of retransmissions (flag rtxALL, meaning rtxTD and rtxTO) are not lost. When TD-FR retransmissions are not lost, the improvement is only up to 12%. While it seems possible to develop algorithms to detect and retransmit lost retransmissions during TD-FR events (e.g., using the SACK version or by analyzing the return of acks in NewReno), it remains to decide whether the improvement is worth the effort. On the other hand, the detection of lost retransmissions after timeout is impossible as only one packet is sent and lost. The time spent without sending anything is 2, 4, 8, etc., seconds. TCP implementations that use a of 200 ms instead of 1 s certainly fare better than those following strictly the standards, although, with a constant RTT of 200 ms, spurious timeouts must occur frequently in TD-FR. Another possibility is to use "limited transmit". Yet another possibility is to use an adaptive depending on the current window instead of the fixed 1 second value. It is not in the scope of the present work to develop further that matter.

We now turn to the full model.

Full send rate model

In this section, we first give the exact equations governing the send rate of a TCP connection. We then give approximations for the NewReno TCP variant under the assumption that the path is not saturated.

Exact model

The TCP throughput or send rate is defined by the following equation [START_REF] Padhye | Modeling TCP Reno Performance: A Simple Model and Its Empirical Validation[END_REF]:

lim
, where is the amount sent until time .

Let .

Note that this decomposition is exhaustive. We note the total number of packets sent and the total time spent up to time in each of the 5 basic elements (see Figure 9 below): RTT, TD, TDFR, TDTO, and TO. RTT means "normal operation" in a RTT. There may be none (under saturation) or more than one window change in the RTT -in slow-start there may be several window changes in the same RTT, we use the last one. TD means Triple Duplicate acknowledgement. TDFR means TD followed by a successful fast recovery. TDTO means TD followed by a timeout due to the loss of a retransmission. TO means "direct timeout".

Let us index the totals above by the sender window, , and let ∑ . is the number of times the sender window changes to , not counting the changes between TD (excluded) and FR (included) events.

gives the number of changes to either from 1 or after receiving acks.

1 means that a timeout occurred; therefore, 1 gives the number of timeouts. In the limit ∞, 1 1 / gives the probability of timeout. The indexing by is also exhaustive.

To simplify the discussion, we consider the case where the path is not saturated and give indications relative to the case where it is saturated.

Write ∑ ∑ , which, in the limit, will give (with an abuse of notation)

∑ . (9)
NOTE: When the link is saturated, that is, , , independent of (recall that is a constant). We may relax the assumption in a probabilistic manner after the calculation of , i.e., with as a function of , so that the possible saturation has little impact on the results of the model; see also section 6.

Similarly, ∑ ∑ . Whether the link is saturated or not, we have, by definition, , a constant independent of ; in the limit (with an abuse of notation),

∑ , that is, . (10)
For TD events, ∑ ∑ , which will give (with an abuse of notation)

∑ . ( 11
) ∑ . (12)
NOTE: With our network settings, the quantities that depend on the path being saturated or not are and .

For TDFR events, ∑ ∑ ; in the limit (with an abuse of notation),

∑ . (13)
∑ . ( 14
)
For TDTO events,

∑ . (15)
∑ .

Finally, for timeouts, TO events,

∑ . ( 17
)
1 1 1 ∑ . Letting 1 1 gives 1 ∑ . ( 18
)
The approach is illustrated in Figure 9. It remains to calculate the 16 quantities, ,

, .

NOTES:

• The calculation of is for a TCP version such that on TD and 1.

• For a version such that 1/ (still a window change on FR) one must replace 2 2 by 2 and 2 1 by 2 1.

•

does not depend on whether the link is saturated or not.

•

does not depend on timing considerations such as the RTT.

•

does not depend on the packet size (but may).

Example with

.

The following Figure 10, Figure 11, and Figure 12 show the comparison between calculations and simulations.

For 1%, calculations and simulations are almost indiscernible for 12, 24, 32, 44. Note the modes at the respective receiver window size.

For

5%, calculations and simulations are almost indiscernible for 12. However, differences in the tail (below about 1% and 12) begin to appear at 24 and are more marked for 32 and 44. These differences remain unexplained; they are not due to using the congestion window (in calculations) as a surrogate for the amount outstanding (in simulations). Note that for a given the calculated distributions are the same up to the common .

For

10%, the difference between calculations and simulation are still small for 24. Differences are more marked for 32 and 44, below about 1% and 10.

Fortunately, for larger , this discrepancy and its effects are reduced due to the fact that the sender window does not grow high. NOTE: In the following sections, we explicitly assume that the link is not saturated at any .

Calculation of α RTT (W) and τ RTT (W)

We have already calculated above as .

This expression does not take into account the possibility of a TD occurring in the same RTT as a window change (see Figure 9). For we use the following approximation,

∑ . (20)
This is an approximation because TCP can send less than packets in a RTT; see the example in the next section. It can also send more; see the example in section 5.6, which also shows that a TD can occur at 3. The more and the less do not compensate.

NOTE: All approximations below assume that a TD can occur only with 4.

Calculation of P TD (W), α TD (W), and τ TD (W)

A TD occurs whenever between 1 and 3 packets are dropped in a series of ; these packets are not necessarily in the same RTT, see Figure 13 For i.i.d. packet drops, we use the following approximation, which gives the probability of 1 or 2 drops among packets.

.

For and we use the following approximations: and ∆, with ∆ / .

First, there are equally likely cases for the loss of one packet in a window of in the same RTT. The total for the number of packets sent in the next RTT and until TD occurs is 0 1 1 1 /2. The total for the time elapsed until TD is 3 0 1 1 ∆ 3 1 ∆/2. The average number sent is 1 /2 and the average time is 3 / 1 ∆/2. However, there are other cases to consider. For example, consider a loss at 6 or at 7. On TD, 3 for both cases. Let 9. With duplicate acknowledgements, 2 new packets, 1 and 2, say, are sent before FR occurs. On FR, 4, the amount outstanding is 2 packets and 2 new packets are sent, 3 and 4, say. If neither 1 nor 2 are dropped, 2 more packets will follow in the same RTT, 5 and 6, say. We thus fall back to the case above if a drop occurs on 3, or 4, or 5, or 6. In this case, 4 packets are sent in the RTT; the same as . However, if 1 is dropped, a new TD will occur triggered by the receipt of the acknowledgement of 4, the time to count is ∆ . Note that only 2 packets were sent in the RTT at 4. A similar reasoning applies to the loss of 2; we note also that only 3 packets are sent in the RTT at 4. Returning to our approximation, we see that there are 4 2 2 2 cases to consider. These cases are clearly not equally likely; letting them being so is also part of the approximation. We have not attempted to perform an exact analysis at all windows. In particular, there are not always 2 cases.

Calculation of P TDFR (W), α TDFR (W), and τ TDFR (W)

After a TD occurred, it is necessary that all retransmissions are not lost in order for a FR to occur. New data packets sent between TD and FR may be dropped, though. We calculated in section 4.1, but here we know that a TD occurred.

Note that this expression accounts for one drop only. For NewReno and two drops, the expression is somewhat more complicated and does not add much to the precision of the global result. Note also that the leading "1" accounts for the retransmission.

As concerns , we use

1 . ( 25
)
In this case, we take into account the possibility of two drops for increased precision and little more complication. Note also that drops drop .

Calculation of P TDTO (W), α TDTO (W), and τ TDTO (W)

For we use the following

1 . (26)
The 'average' probability of TDTO is larger than when there is more than one drop to recover.

For we use the following

min 1/ , 2, / . (27)
If 0, which occurs if the TD occurs at 4 or , no packets are sent between TD and TO.

If

0, new packets are sent until the retransmission timer fires or the amount outstanding reaches or because packets are dropped and no ack returns to the sender.

For large ( 32 and 44) the above approximation gives a result that is too small compared with simulations. However, as discussed in section 6, the influence of the number sent during this event is of secondary importance.

We only consider the TCP version that sets the retransmission timer on the first retransmission (on TD) therefore, .

NOTE: We have experimented with a version that sets the timer on each retransmission and observed only very minor influence (within +/-0.2%, the same as simulation variability) on the global results. We now give an example where after a TDTO TCP can send 4 packets at 3 or 5 packets at 4. Suppose that after a TD packet 0 is lost again, thus a timeout occurs. Suppose that packets 1, 2, 3, 4, and 5 were also sent with packets 1, 2, and 4 dropped. On TO 0 is retransmitted and 2; if 6 was also previously sent, , which corresponds to the fifth doubling. The doubling stops now and the time spent remains at this value for any subsequent timeout on the same packet.

The average time is given by

2 1 3 7 15 31 ∑ ∑ .
The sum is elementary and we have

2 1 3 7 15
Finally, the proportion of time spent in multiple retransmissions of the same packet can be rewritten as

1 1 2 1 2 4 8 16 .
However, simulations indicate that a better approximation is given by:

1 1 2 1 2 4 8 16 . (34)
Notes: (i) The packet retransmitted multiple times is included in . (ii) The RTT has been accounted for in given above; therefore, it must be removed from the time spent in retransmitting the same packet. (iii) The above reasoning is valid for an implementation that limits the number of doubling to five independently of the time spent.

The model is summarized in Table 3.

Exact approach

Approximations for NewReno TCP with on TD and 1.

Notes: -TD can occur only when 4. -, path not saturated.

is numerically calculated as per section 5.2. In order to cross-check results, the send rate is measured in four different manners: via the traffic analysis module, via the sender TCP, via the number measured in the five basic elements, and via the measurements through the sender window indexing. All four ways give the same results.

∑ ∑ ∑ ∑ ∆ ∑ ∑ 1 1 , 1 1 , 1
∑ ∑ 1 min 1/ , 2, / 1 ∑ 2 , 2 0, 2 .
The following Figure 14 shows the percent error between simulations and the model as a function of the packet drop probability from 0.5% to 20%. (The label xM means C=xMbps, Ry means RTT=y ms, and Wz means W R =z packets). For the cases where the link is never saturated, the error is between 0 and 5%. For the three cases where the link can be saturated, the model still does a good job for small but large enough. For the settings (10M, R50, W44), for =0.1%, we calculate 41 40.8%, while for 0.5%, 41 0.9%, which represent a drastic drop, thus the link is hardly saturated. For the settings (2M, R100, W24), for =1%, we calculate 16 24.2%; the model works nicely. We leave for future work the determination of the threshold , above which the model can be applicable even when the link can be saturated at lower . We now turn to a more detailed analysis of the results along the line of the basic elements. Table 4 below gives the details for the worst case (10M, R50, W44) for 5, 10 , 15, and 20%.

For each of the basic elements, the table gives the number of packets sent and the sum, the associated time, in ms, and the sum. The first row gives the results of calculations. The second row the measured values. The third row gives the percent proportion of the measured values. The fourth row gives the percent error of the sums between calculation and measurements. The fifth row gives the weighted percent error between calculations and measurements. The send rate (SR) is obtained by multiplying the number sent by the packet size (1500B).

Several remarks are in order.

% send-rate error - (*) the link is saturated for p=0 • The model gives results that are always larger than measurements. The error is up to 6% for the numbers sent and up to 10% for the time spent. The send rate being a ratio the errors subtract. Yet the model is still reliable as indicated by the actual values and the weighted error row.

• As concerns the number sent, the major contribution comes from the number sent per RTT in "normal" operation. • As concerns the time spent, the relative importance of timeouts, either direct or by lost retransmission, grows as increases, from a total of 19% at 5% to 46% and 35%, respectively, at 20%. Note that the is set to 1 second here. Some modern implementations set this value at 200 ms.

• The importance of the TDTO events, either in the number sent or the time spent, although not negligible, is minimal with respect to the other timeout events. Thus the exact modeling of this event is of secondary importance.

Conclusion

In the present work, we have analyzed and modeled the send rate of long connections that use standard TCP.

Our goal was to obtain models for the performance that can be obtained with TCP under the main assumptions of random packet drops (with probability ), and limited receiver window ( ). We have delimited three regimes depending on and , as illustrated in Figure 5. Following common knowledge, the timeout regime starts at 1%. We experimentally determined that this threshold corresponds to timeouts constituting about 3% of the loss events. In the timeout regime, models used for congestion avoidance do not apply (for a compliant TCP). For 1%, where congestion avoidance dominates the performance of TCP, we have revisited the square root law and shown that it is applicable for above a threshold which depends on the BDP. Further, when taking into account the finiteness of the receiver window, we have shown that a linear law in applies up to a max , which we also calculate for both cases of an unsaturated and saturated path. When the linear and square root regimes overlap, the linear regime is to be applied. As shown in this report, simple expressions for the send rate and conditions of applicability allow the easy calculation of TCP performance in congestion avoidance.

In section 5, we have developed an exact approach for the calculation of TCP send rate usable in any regime. This exact approach requires the calculation of 16 quantities, which depend on the TCP version used. Fortunately, some of these quantities can be simple to obtain.

We have then provided and discussed approximations for the send rate of TCP NewReno. A by-product of these calculations is the distribution of the sender window, which turns out to be independent of any timing (RTT) and saturation considerations. Unfortunately, the full model does not yield analytic expressions although it does not require sophisticated numerical methods. Its use is therefore reserved to the timeout regime and off-line use.

A detailed comparison and discussion of the full model results for NewReno with simulation results has been provided in section 6.

Figure 1 .

 1 Figure 1. Example of TD-FR with TCP NewReno from the sender perspective.

Figure 2 .

 2 Figure 2. Network setting.

Figure 3 .

 3 Figure 3. Illustration of the approach for the linear law.

2 Δ

 2 1 'sometimes' in the RTT. The number sent in the RTT is W. sent ≅ S=W/2, time ≅ RTT Notes. * W=W R , N DA =0 * α TD ≅ W/2 * τ TD ≅ 3RTT/W + (W-1)Δ/Replacing back by in both the send rate expression and the condition gives the result given at the beginning.

Figure 4 .

 4 Figure 4. Comparison of simulations and calculations for the simple models.

Figure 5 .

 5 Figure 5. Domain of validity for the different TCP throughput models.

Figure 6 .

 6 Figure 6. Simulation results for p up to 1%.

Figure 7 .

 7 Figure 7. Timeouts analysis for p between 1 and 10 percent .

Figure 8 .

 8 Figure 8. W eff when retransmissions are not dropped.

Figure 9 .

 9 Figure 9. Illustration of the basic elements of the model.

  counted in n RTT[START_REF] Mathis | The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm[END_REF]. t RTT[START_REF] Mathis | The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm[END_REF] includes the case for normal RTT operation => RTT must be subtracted from t TOTO qN(1) go to w = 2 pN(1) go back to w = 1 with a RTO doubled. (W,W R ) TD n TD (W)=0, t TD (W)=0. time is re-sync @ TD Special case: TD occurs in the same RTT as a window change … FR TD n TDFR (W),t TDFR (W) Incl. RTX(es) Excl. # sent @ FR Time is re-sync @ TD & FR TDFR window changes not counted in P(W) Window change @ FR … TO TD Incl. RTX(es) Excl. 1 sent @ TO RTO is set @ first rtx. Time is re-sync @ TD & TO Window change @ TO (W =1) n TD (W), t TD (W). time is re-sync @ TD n RTT (W), t RTT (W) = RTT NOTE: On saturation, only packets per RTT. Window changes on later RTTs.Finally, ,

Figure 10 .Figure 11 .

 1011 Figure 10. Comparison between calculated and measured for %.

Figure 12 .

 12 Figure 12. Comparison between calculated and measured for %.

  .

Figure 13 .

 13 Figure 13. W packets may appear in contiguous RTTs.

6 .

 6 Validation of the full modelThe simulations performed confirm that both the number of packets sent and the time spent in sending them follow (a) the decomposition in the five basic elements of the exact model. (b) The further indexing with the sender window of the exact model.

Figure 14 .

 14 Figure 14. Comparison between simulations and calculations of the TCP throughput.

Table 1 . Network parameters used in the report.

 1

	C (Mbps)	Δ (ms)	RTT (ms)	β (pkts)	W R (pkts)	r	Condition under	0
			100	16.7	12	1.33	Link not saturated
	2	6	100 200	16.7 33.3	24 24	0.67 1.38	Link saturated, Link not saturated	9
			200	33.3	44	0.75	Link saturated,	12
			40	33.3	32	1.03	Link not saturated
	10	1.2	50	41.7	44	0.93	Link saturated,	4
			100	83.3	44	1.89	Link not saturated

Table 2 . Network setting for the evaluation of the simple TCP throughput models.

 2

	C (Mbps) Δ (ms)	RTT (ms) β (pkts)	W R (pkts) p min (%)	p max (%)	Comments
				(= W eff max)		sqrt	linear
			100	16.7	12	1.04	1.39	No sqrt.
								TO stats.
			100	16.7	24	1.04	0.35 (not sat)	sqrt after
							0.64 (sat)	linear.
	2	6	200	33.3	24	0.24	0.35	sqrt after
								linear.
								TO stats.
			200	33.3	44	0.24	0.10 (not sat)	sqrt after
							0.20 (sat)	linear.
			40	33.3	32	0.24	0.20	sqrt after
								linear.
								TO stats
			50	41.7	44	0.16	0.10 (not sat) sqrt after
	10	1.2						linear.
								TO stats
			100	83.3	44	0.039	0.10	sqrt after
								linear.
								TO stats

Table 3 . Summary of exact approach and approximations for TCP send rate.

 3

Table 4 . Detailed comparison of model and simulations.

 4

* It is not advisable to do so when W R can change during the course of a connection.

We leave for future work the detailed analysis for the case where saturation occurs. We also leave for the future the application to the case of non standard TCP implementations.

The calculation of these quantities depends on the TCP version considered.

The version considered here is TCP NewReno with 1, meaning that slow start continues until . In particular, on FR, 1.

Calculation of P(W)

We assume pure random i.i.d. packet drops meaning that an arriving packet is dropped with probability and is not dropped with probability 1 , independently of previous events or other parameters. Nothing happens if no packet appears. Note also that drops are only random, not due to buffer overflow.

We start by writing

1 , which means that none of the packets sent at are dropped, that is, acks are received. Another possibility is that no drop occur at 1, i.e., 1 acks are received thus increasing the window to .

Next,

is the indicator function of the condition . There are 3 ways to reach : From 1 and no drops. From a TD at 2

1 , or at 2 1 1 in which cases 1 and on the following FR, 1 .

2 1 . That is, the retransmission after a timeout is not lost.

1 is given by 1 1 2 .

After this first step, we write, ,

, .

For such that 2 2 , , .

For such that 2

For such that 2 .

We use , meaning that we consider only one or two drops in a sequence of packets, and none or the retransmission is lost. Under random i.i.d. packet drops we found this approximation sufficient. of 4 at 3. With 3, the total would be 5 at 4. Note that acks are always increasing here. Further, if one of the 4 packets sent is dropped, we would have a TD at 3 with 4.

Calculation of P TO (W), α TO (W), and τ TO (W)

In this section we only consider the cases 2 up to 5 for which 1, 2, or 3 drops lead to a TO.

If the first packet of the group of 2 is dropped -whatever happens to the second packet -a TO occurs. For , note that the timer was set when sending this first packet; the first RTT is counted as normal operation.

The expressions are more complicated for 3. To first order in p, i.e., with only one drop.

3 can be reached from 2, where two packets are sent. The first packet must not be dropped (to reach 3 but the second must. Only up to two acks are received thus a TO follows. Now, assume the two packets sent at 2 are not dropped. If 2, then 4 on receipt of the second ack and we are not concerned here. If 2, two packets are sent at 3, on receipt of the second ack (from 2 , 3 1/3. To have a TO event, either the first packet must be dropped or, if it passes, the second must be dropped. If none are dropped, 3 1/3 1/3 1/3 4; again, we are not concerned.

3 can be also be reached from a TDFR at 4. On FR, 2 1 3 and three packets are sent because none are outstanding. To have a TO, either the first, or the second, or the third must be dropped.

Finally,

3 can be also be reached from a TDFR at 5. In this case 1. Two packets are sent on FR. Again, there are only two possibilities to consider for this case. This makes a total of 8 cases, not equally likely. See below the approximations for 3 , and 3 .

To have a TO at 4, requires, at least, two packet drops. We use the following approximation. To have a TO at 5, requires, at least, three packet drops. We use the following approximation:


Eugen Dedu

Grégory Bise

Julien Bourgeois

An analysis of congestion controls in centralized control systems

Keywords: congestion control, transport protocols, control systems, real-time systems

This article studies different congestion control methods applied to a centralized control system, consisting in several sensors/actuators and one controller. Sensors/actuators are linked to the controller through an IP network. Depending on the data exchanged, the network can be congested. In such case, the congestion control used by data exchange becomes important. We evaluate four congestion control methods used by three classical transport protocols, UDP, TCP and DCCP. This evaluation uses ns2 network simulator. Results on a centralised control system show that TCP and DCCP offer a good tradeoff on reliability vs. throughput, whereas UDP has best results provided that the network is well configured.

I. INTRODUCTION

Control systems are devices which manage the behaviour of systems. Closed-loop control systems consist of sensor(s) which gather data from the environment, actuator(s) which act on the environment, and controller(s) which receive data from sensor(s) and give commands to actuator(s). In our case, we are interested in Distributed Intelligent MEMS (DiMEMS) systems [START_REF] Bourgeois | Distributed intelligent mems: Progresses and perspectives[END_REF] which comprise all these elements but at a microscale. The Smart Blocks 1 and the Claytronics 2 projects are good examples of DiMEMS systems.

Control systems can be as simple as a sensor, an actuator and a controller. They can be centralized, consisting of several sensors and actuators but a single controller. They are distributed if there are several controllers too.

A networked control system (NCS) is a control system where the components are connected together through a network, and which has real-time constraints. The network is shared among the components either because it allows to reduce system costs or because the interconnection is wireless. NCSs have therefore a broad range of applications such as mobile robotic systems, ground-based like in RoboCup or unmanned aerial vehicle (UAV) [START_REF] Chaumette | Scual, swarm of communicating uavs at labri: An open uavnet testbed[END_REF].

Having real-time constraints means that information generated has deadlines to arrive, so the time when the information arrives to destination is important. They can be divided in soft, firm and hard [START_REF] Laplante | Real-Time Systems Design and Analysis: Tools for the Practitioner[END_REF]. In soft systems a deadline miss means that the information has a reduced usefulness, such as in sensor networks. In firm systems a miss means its information is useless, but infrequent misses are tolerable, such as in a live video/audio conversation. In hard systems, deadline misses generate system failure, such as in most robotic systems.

The network is shared among the components. Designing the network capacity so that congestion never appears is not always feasible, for example when data generated is not known in advance or when network has no fixed bandwidth such as the wireless networks subject to interference. So congestion can occur if data transmitted exceeds in size the network capacity. Congestion control is a mechanism to regulate sending rate so that data is sent at the fastest rate that still avoids congestion. This can be thought as network resource optimisation. When congestion occurs in network, data is lost. It is therefore important to analyse congestion control impact on data transmission.

In NCS research, data transfer is generally treated with lowlevel protocols, such as Ethernet and TDMA. Very few papers deal with congestion control in IP-based systems, yet this is a known challenge: "These challenges [for NCS] involve the optimization of performance in the face of constraints on communication bandwidth, congestion, and contention for communication resources, delay, jitter [...]" and "When communication channels in a data network are shared resources among multiple user nodes, network congestion and contention for bandwidth pose challenges for control implementations in which there are hard real-time requirements" [START_REF] Baillieul | Control and communication challenges in networked real-time systems[END_REF]. [START_REF] Rajesh | Implementation of networked control systems using TCP/IP[END_REF] for example notices that different types of data exist in an NCS, hence different protocols or different priorities for packets can be used. In this context, [START_REF] Dedu | A study on the benefit of TCP packet prioritisation[END_REF] shows promising results for packet prioritisation, results which are even more appropriate to control systems since the network is under the control of one organization.

The contribution of this article is to discuss the interest of having congestion control in NCS. We analyze simulation results of classical congestion controls used above IP-based networks.

II. RELATED WORKS A. Networked Control of Systems

Networked Control of Systems (NCS) lies at the intersection of control and communication theories and it is therefore relevant to compare this study to NCS ones. A NCS has four main characteristics [START_REF] Hespanha | A survey of recent results in networked control systems[END_REF], [START_REF] Yang | Networked control system: a brief survey[END_REF] that have to be taken into account in order to control the whole system, bandwidth-limited communication channels, sampling and delay, packet dropout and system architecture. If the first three characteristics match our concerns which is network transmission, the last one only deals with the architecture of the system i.e. centralization vs decentralization of the control. Nevertheless, studies and modeling of quantization effect [START_REF] Heemels | Networked and quantized control systems with communication delays[END_REF], [START_REF] Nesic | A unified framework for design and analysis of networked and quantized control systems[END_REF], packet drop out [START_REF] Wu | Design of networked control systems with packet dropouts[END_REF] or consensus problems [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF] are important and must be taken into account together with the congestion control.

B. Decentralized and distributed control

The topic of decentralized and distributed control of systems has been active for many years [START_REF] Sandell | Survey of decentralized control methods for large scale systems[END_REF]. Decentralized control limits its study to special systems like spatially invariant ones [START_REF] Bamieh | Distributed control of spatially invariant systems[END_REF] or nested, chained or symmetric systems [START_REF] Voulgaris | A convex characterization of classes of problems in control with specific interaction and communication structures[END_REF], whereas distributed control makes less assumptions about the system [START_REF] Massioni | Distributed control for identical dynamically coupled systems: A decomposition approach[END_REF]. Linear matrix inequalities (LMI) can be used either for decentralized [START_REF] Borrelli | Hybrid decentralized control of large scale systems[END_REF] or for distributed systems [START_REF] Dullerud | Distributed control design for spatially interconnected systems[END_REF]. LMI has proven to be efficient when dealing with linear systems whose physical topology is represented by an arbitrary graph [START_REF] Langbort | Distributed control design for systems interconnected over an arbitrary graph[END_REF] but these results have not been extended to the nonlinear systems. It has also to be noticed that these methods propose only to control large distributed system but do not help to program it. If some problems require algorithmic solutions, these methods won't be used.

III. BACKGROUND

A. Congestion control

The IP protocol, used also by Internet, does no attempt to optimise network usage when sending data, because it does not take into account availability of network resources. Network optimisation use has been leaved on/to the upper transport protocol. The classical transport protocols on Internet are TCP [START_REF] Postel | Transmission control protocol[END_REF] and UDP [START_REF]User Datagram Protocol[END_REF], and recently DCCP was standardised too [START_REF] Kohler | Datagram Congestion Control Protocol (DCCP)[END_REF]. The way resource usage is taken into account is through a congestion control. Among the transport protocols presented, UDP has no congestion control with no data reliability, TCP has a window-based congestion control with 100% data reliability through retransmission (all data arrives to destination), and DCCP allows to choose a congestion control among currently two standardised controls: TCP-like [START_REF] Floyd | Profile for Datagram Congestion Control Protocol (DCCP) congestion control ID 2: TCP-like congestion control[END_REF], similar to TCP, and TFRC [START_REF] Floyd | Profile for Datagram Congestion Control Protocol (DCCP) congestion control ID 3: TCP-friendly rate control (TFRC)[END_REF], an equation-based control, with no data reliability either.

When UDP receives a packet to be sent to network, it sends it immediately, no matter the network state. This intuitively leads to the highest sending rate, with the drawback that packets can be lost if the network is congested.

When TCP or DCCP receives a packet to be sent to network, it checks whether network is able to transport it. If yes, it is sent immediately, otherwise it is stored in a temporary buffer until network conditions allow to send it. The role of congestion control is to take care of the timings when packets are sent to the network. TCP congestion control works as follows. At the beginning of a transmission, sender uses a slow start phase, where data sending rate increases exponentially. When data rate exceeds network bandwidth, packets are lost and sender enters to congestion avoidance phase, a network-friendly phase where data sending rate increases linearly; this is the phase used most of the time for long enough transmissions. Upon a lost packet detection, sender sends it immediately, known as fast retransmit phase, and enters a temporary fast recovery phase where it sends data at a smaller rate until it recovers from the loss, at which time it reduces by two the data rate and goes back to the congestion avoidance phase. This congestion control is used by DCCP/TCP-like too.

On the contrary, TFRC uses a sending rate equation whose parameters are filled with transmission parameters, most notable with the number of lost packets. Each RTT (Round Trip Time, the time for a packet go and back), the equation parameters are updated and data sending rate changes. This leads to a smoother changing in sending data rate, which is a useful property for some applications.

B. Simulators

Control and network research communities usually use simulators to validate algorithms. Two such simulators are TrueTime and ns2, respectively.

TrueTime is based on Matlab/Simulink and targets real-time and embedded systems. The simulation model is based on three blocs:

• TrueTime kernel, for logical controls and data processing;

• TrueTime network, for packet exchange in a local network such as Ethernet, CAN, TDMA and FDMA; • a controller. A fourth optional block can be used, TrueTime battery. This simulator focuses on low-level simulations. Instead, we are interested in high-level protocol simulations, where congestion control is implemented.

Network simulator version 2 (ns2) is usually used in the network research community. It provides low-level and highlevel protocols. Several transport protocols are supported, and for some time we even maintained the DCCP implementation, used in the current article, in the simulator 3 . The accuracy of results for low-level protocols is low, but for high-level protocols, as in our case, it is high.

Given the support for various congestion controls, we choose ns2 for our simulations.

IV. CONGESTION CONTROL ANALYSIS

A. Network topology used

The network used for carrying out tests is presented in Fig. 1. Three agents are connected through a router to a controller. Agents are both sensors and actuators. The sensor sampling period is 50ms; they gather information about the environment and send to the controller sensor data through the form of a packet of 1kB (1024 bytes) of application data each 50ms. Note that this gives slightly different packet sizes, since UDP, TCP and DCCP headers have different sizes. The first sensor starts sending at t=0, the second at t=100ms and the third at t=200ms. Upon reception of a sensor data (sensor packet), the controller answers by sending it an order through the form of a packet of 200 bytes. The topology is set so that there is a small congestion on router-controller link, whose bandwidth is a bit smaller than total sent data. The reason for this choice is that if a network is not congested, a congestion control brings of course no benefit, whereas we are interested to know if congestion control is useful.

The router uses a DropTail queue management, which means that an incoming packet is rejected if and only if the buffer is full. The buffer size is set to 50 packets, the default value on the simulator.

Each simulation is run for 360 seconds. The total number of packets generated by each sensor is 20 packets/sec * 360 sec = 7200 packets (in reality, between 7195 and 7199, since some sensors start a bit later).

Note that sending and receiving are done on different "cables", so they do not share the 256kb/s link. As controller answers are small, they do not provoke congestion, hence we are not interested by controller answers.

The figure accompanying each method shows the delays of each packet generated by each sensor, with the time on x-axis. A 0 delay means the packet is lost.

B. Results

The layer which takes care of network congestion and is responsible for packet delays is transport layer. We tested three transport protocols, the classical TCP and UDP, and a relatively new standardised protocol, DCCP. The latter can choose its congestion control, and we tested the two currently standardised: TCP-like and TFRC. Some applications in control systems are interested by delay (time for the sensor data to arrive to controller), others by losses. On some applications values are cumulative, i.e. the value of one parameter at one time removes the need to know the value of the parameter before (e.g. the current temperature of a system or the current position of an object), which means that losses are tolerated. On others, such as videoconferencing, the delay is an important parameter, while the reliability is important for audio and not so important for video. Therefore, we have to analyse both delays and losses in simulations.

1) For UDP protocol: Fig. 2 shows that the shapes of the delays of the three sensor data packets are very different: starting from second 2, one sensor has a constant delay of 1.5s, another one a varying delay from 0s to 1.5s, and a third has 0 delay, meaning that all its packets are lost. What happens is a timing issue: each time a packet from the latter sensor arrives at the router, its buffer is full and the packet gets rejected. Such synchronisation is a known characteristic of a DropTail queuing discipline, as set at the router, exacerbated by the fact that UDP does not use a congestion control.

10996 packets are lost, and all of them are lost by the network. No packet is retransmitted, according to UDP specification [START_REF]User Datagram Protocol[END_REF]. In the figure, packets start to be lost at time 1.95s. This agrees with theoretical results: During that time, about 1.95 s * 20 packets/s * 3 sensors = 120 packets have been sent, and 1.95 s * 32 = 64 packets have been forwarded by the router. This gives a difference of 56 packets, approximately equal to the buffer size on the router, set to 50 packets, as written above.

The highest delay is 1.61s, while the average delay for received packets is 1.35s. The highest delay appears for a packet which arrives at the router while its buffer is full less one packet size, hence it takes the greatest time to be processed by the router. This explanation on the highest delay stands for the whole this section, for all the protocols below.

2) For TCP protocol: Fig. 3 presents the results. The figure shows that the shapes of delays are similar, which is not surprising given that TCP uses a fair congestion control. This saw teeth-like curve is also classical for throughput of TCP protocol. At the beginning of the transmission, TCP increases very fast the data rate, and as a result the router buffer fills up and delay increases. Afterwards, TCP enters a loop where it increases slowly the data rate until a loss is detected, and reduces it by two when it arrives [START_REF] Postel | Transmission control protocol[END_REF], which leads to similar changing in packet delay.

63 packets are lost by network, and according to TCP specification they have all been retransmitted and eventually received. 10382 packets are lost on the sensor itself, without entering the network. The explanation is that the built-in congestion control of TCP delays packets until network resources are available, and as a consequence TCP buffer fills up and eventually simply discards packets coming from the sensor.

The highest delay is 1.68s and the average is 1.38s. 3) For DCCP/TCP-like protocol: Fig. 4 presents the results. As for TCP, it shows that the shapes of the transfer time of the three sensor data packets are similar. This is not a surprising result, since TCP-like congestion control uses the same law for sending rate as TCP. 339 packets are lost by the network, which is a bit greater than for TCP. None of them has been retransmitted, since DCCP does not retransmit them (even if the exact number of each lost packets is known by the sender). 7021 packets are lost on the sensor for the same reason as for TCP.

The highest delay is 1.53s and the average is 1.09s. 4) For DCCP/TFRC protocol: Fig. 5 presents the results. Like TCP, TFRC is a fair congestion control, so the shapes of the transfer time of the three sensor data packets are similar.

174 packets are lost by the network, which is a bit greater than for TCP. None of them has been retransmitted, since as written above DCCP does not retransmit them. 9873 packets are lost on the sensor for the same reason as for TCP.

The highest delay is 1.63s, and the average is 1.41s.

C. Discussion

Table I presents a numerical overview of the simulation results (the delay columns show results for all the sensors). Several conclusions can be inferred. Using UDP means that some sensors can be almost completely muted by synchronisation issues, as given by the first sensor. Also, UDP has by far the most losses on the network, while the protocols with congestion controls avoid it and lose almost all their packets on the sensor itself. DCCP/TCP-like has the highest number of packets received, with the three others a bit behind it.

The highest delay is more or less comparable, since it is obtained when the router buffer is filled, and this case appears for all the protocols. Note that packets can wait on sensor buffer too, but this buffer is drained much faster since the link is much greater than the bottleneck link (1 Mb/s vs. 256 kb/s). On the other hand, the average delay is very favorable to DCCP/TCP-like (1.09 secs).

These results are not surprising, as explained in the following.

First, if a network is not congested, a congestion control brings of course no benefit. So in the following we are interested what happens when data size is greater than network capacity.

Internet is a network where flows appear and disappear generally irregularly, because user behaviour for creating flows is unpredictable and sometimes interactive. In contrast, control systems use sensors which usually send data regularly. Such regularity sometimes appears in Internet too, for example for constant video transmission such as television broadcasting. For such cases, where data is sent at a regular pace, the sending rate smoothing done by congestion control is of no help. It should also be noted that when there are several destinations with various bandwidths, congestion control can avoid useless packet losses, situation known as network collapse, an example of which is given in [START_REF] Floyd | Congestion control principles[END_REF]. This is however not the case in a centralized control system which is the focus of the current article.

The delay is affected too by the congestion control. A congestion control usually delays packet sending on sender, waiting for network availability or for acknowledgement reception (also known as TCP pacing), which increases delay on sender. On the other hand, a congestion control keeps router buffers smaller, hence reducing packet delay on routers. UDP too has a limitation, because in conjunction with the simple DropTail queuing mechanism it leads to global synchronisation, preventing some sensors to send their data.

Given the discussion above, it turns out that more analysis is needed to infer what is the best congestion control. What is certain is that, in order to avoid synchronisation issues, UDP must be used together with a more sophisticated queuing mechanism, such as RED [START_REF] Floyd | Random early detection gateways for congestion avoidance[END_REF], [START_REF] Braden | Recommandations on queue management and congestion avoidance in the internet[END_REF], which rejects packets randomly before the queue is full.

V. CONCLUSIONS

This article presented a comparison among several congestion controls used by currently-used transport protocols for a centralized control system, based on simulation.

Results show that UDP in conjunction with a simple queue management mechanism has some crucial issues, but a more sophisticated mechanism should solve them. Aside that, given that the network is slightly congestion, no protocol or congestion control is definitely better than the others in terms of number of packets received. This is because in a control system data is generated at regular intervals, and the smoothing effect of congestion control has no effect. On the other hand, in terms of delay, DCCP/TCP-like gives best results. What parameter is more important depends on the control system.

Future works will use a different queue mechanism for the router, and most importantly will use congestion control to adapt sensor sending rate to network conditions, such as reducing sampling rate, which allows to have a control over data losses. We will also focus on distributed control systems, consisting of several controllers connected through a potentially complex network.

Figure 1 .

 1 Figure 1. Network used for simulations.

Figure 2 .

 2 Figure 2. Results for UDP protocol for the first 5 seconds.

Figure 3 .Figure 4 .

 34 Figure 3. Results for TCP protocol for the whole simulation.

Figure 5 .

 5 Figure 5. Results for DCCP/TFRC protocol for the whole simulation.

Table I NUMERICAL

 I RESULTS FOR THE FOUR CONGESTION CONTROLS, SAMPLING IS 50MS AND SIMULATION RUNS FOR 360 SECS.

	Protocol	Sensor			Packets			Delay
			generated lost on sensor lost on network received highest average
	UDP	1	7199	0	7163	36	1.61	1.35
		2	7197	0	3432	3765
		3	7195	0	0	7195
	TCP	1	7199	4425	0 (26 retr)	2774	1.68	1.38
		2	7197	4380	0 (26 retr)	2817
		3	7195	1577	0 (11 retr)	5618
	DCCP/TCP-like 1	7199	2276	115	4808	1.53	1.09
		2	7197	2510	108	4579
		3	7195	2235	124	4836
	DCCP/TFRC	1	7199	3496	60	3643	1.63	1.41
		2	7197	3184	54	3959
		3	7195	3193	60	3942

http://eugen.dedu.free.fr/ns2

This work was supported by the Smart Blocks NRA (French National Research Agency) project (ANR-2011-BS03-005).

1 http://smartblocks.univ-fcomte.fr 2


Nicolas Friot
email: nicolas.friot@lifc.univ-fcomte.fr

Christophe Guyeux
email: christophe.guyeux@univ-fcomte.fr

Jacques M Bahi
email: jacques.bahi@univ-fcomte.fr

A new secure process for steganography: CI 2 Stego-security and topological-security

Keywords: Steganography, Topology, Security, Chaotic Iterations

In this paper is proposed a novel steganographic scheme based on chaotic iterations which offer a solution facing the main limitation of the previous one. This research work takes place into the information hiding security fields. We show that the proposed scheme is stego-secure, which is the highest level of security in a well defined and studied category of attack called "watermark-only attack". Additionally, we prove that this scheme presents topological properties so that it is one of the firsts able to face, at least partially, an adversary when considering the others categories of attacks defined in the literature.

Introduction

Security is one of major concerns in the information hiding field. The security is defined in [START_REF] Kalker | Considerations on watermarking security[END_REF] as follows: "watermarking security refers to the inability by unauthorized users to have access to the raw watermarking channel. [...] to remove, detect and estimate, write or modify the raw watermarking bits."

In this field, it has been realized in [START_REF] Cayre | Watermarking security: theory and practice[END_REF] a classification of attacks into categories, according to the type of information the attacker has access to. One of the well known class is called Watermark Only Attack (WOA). Several levels of security have been recently defined in these setups. The highest level of security in this framework is called stego-security [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF], whereas topological-security tends to improve the ability to withstand attacks in other setups [START_REF] Guyeux | Chaotic iterations versus spread-spectrum: chaos and stego security[END_REF].

To the best of our knowledge, there exist only two information hiding schemes that are both stego-secure and chaos-secure [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF][START_REF] Guyeux | Chaotic iterations versus spread-spectrum: chaos and stego security[END_REF] in some conditions. The first one called Natural Watermarking is based on a spread spectrum technique. Unfortunately, this scheme is neither robust, nor able to face an attacker in other setups than WOA, due to its lack of a topological properties [START_REF] Guyeux | Chaotic iterations versus spread-spectrum: chaos and stego security[END_REF]. The second one is based on chaotic iterations [START_REF] Bahi | A new chaos-based watermarking algorithm[END_REF]. However, it allows to embed securely only one bit per host content, which constitute the main limitation of this scheme. This is a one-bit-watermarking process.

This document has for main objective to present the interest of our research works accepted in the conference on Security and Cryptography Secrypt 2011 in Sevilla in Spain. Its main aim is to present a new process based on chaotic iterations which is stego-secure and topologically-secure too, and offer a solution to bypass the limitation of the previous one and so allow to embed securely more than one bit. This will be a real steganographic process.

The rest of this document is organized in the following way: in Section 2 it is down a reminder information hiding security. In Section 3 the new algorithm is presented. This documents ends by a conclusion section 4 where our contribution is summarized and intended future researches are presented.

2 Data hiding security

Classification of Attacks

In the steganography framework, attacks have been classified in [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF] in several classes: Watermark-Only Attack (WOA) when an attacker has only access to several watermarked contents, Known-Message Attack (KMA) when an attacker has access to several pairs of watermarked contents and corresponding hidden messages, Known-Original Attack (KOA) when an attacker has access to several pairs of watermarked contents and their corresponding original versions, and Constant-Message Attack (CMA) when the attacker observes several watermarked contents and only knows that the unknown hidden message is the same in all contents.

Stego-Security

The stego-security is defined in the framework of the Simmons' [START_REF] Simmons | The prisoners' problem and the subliminal channel[END_REF] prisoner problem. It is the highest security level in WOA setup [START_REF] Cayre | Kerckhoffs-based embedding security classes for woa data hiding[END_REF]. To remind it, we need the following notations: K is the set of embedding keys, p(X) is the probabilistic model of N 0 initial host contents, and p(Y |K 1 ) is the probabilistic model of N 0 watermarked contents. Furthermore, it is supposed in this context that each host content has been watermarked with the same secret key K 1 and the same embedding function e.

Definition 1 (Stego-Security). The embedding function e is stego-secure if and only iff:

∀K 1 ∈ K, p(Y |K 1 ) = p(X).

Topological-Security

To check whether an information hiding scheme S is topological-secure or not, S must be written as an iterate process x n+1 = f (x n ) on a metric space (X , d). This formulation is always possible [START_REF] Bahi | A chaos-based approach for information hiding security[END_REF]. So, Definition 2 (Topological-Security). An information hiding scheme S is said to be topological-secure on (X , d) if its iterative process f check the three following topological properties:

-Transitivity: iff, for any pair of open sets U, V ⊂ X , there exists k > 0 such that f k (U ) ∩ V = ∅. -Regularity: iff the set of periodic points of f is dense in X .

-Sensitivity: iff there exists δ > 0 such that, for any x ∈ X and any neighborhood V of x, there exist y ∈ V and n 0 such that d (f n (x), f n (y)) > δ.

(δ is called the constant of sensitivity of f ).

In the approach presented by Guyeux et al., a data hiding scheme is secure if it is unpredictable. Its iterative process must satisfy the three topological properties and its level of topological-security increases with the number of other topological properties satisfied by it.

This new concept of security for data hiding schemes has been proposed in [START_REF] Bahi | A chaos-based approach for information hiding security[END_REF] as a complementary approach to the existing framework. It contributes to the reinforcement of confidence into existing secure data hiding schemes. Additionally, the study of security in KMA, KOA, and CMA setups is realizable in this context. Finally, this framework can replace stego-security in situations that are not encompassed by it. In particular, this framework is more relevant to give evaluation of data hiding schemes claimed as chaotic.

The improved algorithm: CI 2

To describe CI 2 we need the following notations: x 0 ∈ B N is the N LSCs (as defined in Figure 1 on the following page) of a given cover media C, m 0 ∈ B P is the watermark to embed into x 0 , S p ∈ S N is a strategy called place strategy, S c ∈ S P is a strategy called choice strategy, and S m ∈ S P is a strategy called mixing strategy. So our information hiding scheme denoted by CI 2 is defined by:

x n i =    x n-1 i if S n p = i m S n c if S n p = i. and m n j =    m n-1 j if S n m = j m n-1 j if S n m = j. with    n ∈ N * i ∈ 0; N -1 j ∈ 0; P -1 where m n-1 j
is the boolean negation of m n-1 j , and the stego-content is y = x P .

It has been described in details in [START_REF] Friot | Chaotic iterations for steganography -stego-security and chaos-security[END_REF] how to model the new process CI 2 as a discreet dynamical system (an iterative process) G f0 in a topological space, and in the same work it has been proven that: Theorem 1. CI 2 is stego-secure and topologically-secure.

Conclusion and future works

In this research work, a new information hiding scheme has been introduced. It is topological-secure and stego-secure, and thus is able to withstand attacks in Watermark-Only Attack (WOA) and Constant-Message Attack (CMA) setups. These results have been obtained after having studied the topological behavior of this data hiding scheme. To the best of our knowledge, this algorithm is the third scheme that has been proven to be secure, according to the information hiding security field. In future work, we intend to study the robustness of this scheme, and to compare it with the two other secure algorithms. Additionally, we will investigate the topological properties of our scheme, to see whether it is secure in KOA and KMA setups.

  (a) MSCs of Lena. The richest part of Lena. (b) Original Lena. (c) LSCs of Lena (×17) Details of Lena. Can be altered without damages.

Fig. 1 :

 1 Fig. 1: Most and least significant coefficients of Lena. (MSCs and LSCs)