Internet Engineering Task Force (IETF)                         M. Allman
Request for Comments: 5827                                          ICSI
Category: Experimental                                    K. Avrachenkov
ISSN: 2070-1721                                                    INRIA
                                                               U. Ayesta
                                           BCAM-IKERBASQUE and LAAS-CNRS
                                                              J. Blanton
                                                         Ohio University
                                                               P. Hurtig
                                                     Karlstad University
                                                              April 2010
        
Internet Engineering Task Force (IETF)                         M. Allman
Request for Comments: 5827                                          ICSI
Category: Experimental                                    K. Avrachenkov
ISSN: 2070-1721                                                    INRIA
                                                               U. Ayesta
                                           BCAM-IKERBASQUE and LAAS-CNRS
                                                              J. Blanton
                                                         Ohio University
                                                               P. Hurtig
                                                     Karlstad University
                                                              April 2010
        

Early Retransmit for TCP and Stream Control Transmission Protocol (SCTP)

TCP和流控制传输协议(SCTP)的早期重传

Abstract

摘要

This document proposes a new mechanism for TCP and Stream Control Transmission Protocol (SCTP) that can be used to recover lost segments when a connection's congestion window is small. The "Early Retransmit" mechanism allows the transport to reduce, in certain special circumstances, the number of duplicate acknowledgments required to trigger a fast retransmission. This allows the transport to use fast retransmit to recover segment losses that would otherwise require a lengthy retransmission timeout.

本文档提出了一种新的TCP和流控制传输协议(SCTP)机制,可用于在连接拥塞窗口较小时恢复丢失的段。“早期重传”机制允许传输在某些特殊情况下减少触发快速重传所需的重复确认数。这允许传输使用快速重传来恢复段丢失,否则将需要较长的重传超时。

Status of This Memo

关于下段备忘

This document is not an Internet Standards Track specification; it is published for examination, experimental implementation, and evaluation.

本文件不是互联网标准跟踪规范;它是为检查、实验实施和评估而发布的。

This document defines an Experimental Protocol for the Internet community. This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Not all documents approved by the IESG are a candidate for any level of Internet Standard; see Section 2 of RFC 5741.

本文档为互联网社区定义了一个实验协议。本文件是互联网工程任务组(IETF)的产品。它代表了IETF社区的共识。它已经接受了公众审查,并已被互联网工程指导小组(IESG)批准出版。并非IESG批准的所有文件都适用于任何级别的互联网标准;见RFC 5741第2节。

Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc5827.

有关本文件当前状态、任何勘误表以及如何提供反馈的信息,请访问http://www.rfc-editor.org/info/rfc5827.

Copyright Notice

版权公告

Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved.

版权所有(c)2010 IETF信托基金和确定为文件作者的人员。版权所有。

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

本文件受BCP 78和IETF信托有关IETF文件的法律规定的约束(http://trustee.ietf.org/license-info)自本文件出版之日起生效。请仔细阅读这些文件,因为它们描述了您对本文件的权利和限制。从本文件中提取的代码组件必须包括信托法律条款第4.e节中所述的简化BSD许可证文本,并提供简化BSD许可证中所述的无担保。

This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English.

本文件可能包含2008年11月10日之前发布或公开的IETF文件或IETF贡献中的材料。控制某些材料版权的人员可能未授予IETF信托允许在IETF标准流程之外修改此类材料的权利。在未从控制此类材料版权的人员处获得充分许可的情况下,不得在IETF标准流程之外修改本文件,也不得在IETF标准流程之外创建其衍生作品,除了将其格式化以RFC形式发布或将其翻译成英语以外的其他语言。

1. Introduction
1. 介绍
   Many researchers have studied the problems with TCP's loss recovery
   [RFC793, RFC5681] when the congestion window is small, and they have
   outlined possible mechanisms to mitigate these problems
   [Mor97, BPS+98, Bal98, LK98, RFC3150, AA02].  SCTP's [RFC4960] loss
   recovery and congestion control mechanisms are based on TCP, and
   therefore the same problems impact the performance of SCTP
   connections.  When the transport detects a missing segment, the
   connection enters a loss recovery phase.  There are several variants
   of the loss recovery phase depending on the TCP implementation.  TCP
   can use slow-start-based recovery or fast recovery [RFC5681], NewReno
   [RFC3782], and loss recovery, based on selective acknowledgments
   (SACKs) [RFC2018, FF96, RFC3517].  SCTP's loss recovery is not as
   varied due to the built-in selective acknowledgments.
        
   Many researchers have studied the problems with TCP's loss recovery
   [RFC793, RFC5681] when the congestion window is small, and they have
   outlined possible mechanisms to mitigate these problems
   [Mor97, BPS+98, Bal98, LK98, RFC3150, AA02].  SCTP's [RFC4960] loss
   recovery and congestion control mechanisms are based on TCP, and
   therefore the same problems impact the performance of SCTP
   connections.  When the transport detects a missing segment, the
   connection enters a loss recovery phase.  There are several variants
   of the loss recovery phase depending on the TCP implementation.  TCP
   can use slow-start-based recovery or fast recovery [RFC5681], NewReno
   [RFC3782], and loss recovery, based on selective acknowledgments
   (SACKs) [RFC2018, FF96, RFC3517].  SCTP's loss recovery is not as
   varied due to the built-in selective acknowledgments.
        

All of the above variants have two methods for invoking loss recovery. First, if an acknowledgment (ACK) for a given segment is not received in a certain amount of time, a retransmission timer fires, and the segment is resent [RFC2988, RFC4960]. Second, the "fast retransmit" algorithm resends a segment when three duplicate

上述所有变体都有两种调用损失恢复的方法。首先,如果在一定时间内未收到给定段的确认(ACK),则会触发重传计时器,并重新发送该段[RFC2988,RFC4960]。第二,“快速重传”算法在三次重复时重新发送一段

ACKs arrive at the sender [Jac88, RFC5681]. Duplicate ACKs are triggered by out-of-order arrivals at the receiver. However, because duplicate ACKs from the receiver are triggered by both segment loss and segment reordering in the network path, the sender waits for three duplicate ACKs in an attempt to disambiguate segment loss from segment reordering. When the congestion window is small, it may not be possible to generate the required number of duplicate ACKs to trigger fast retransmit when a loss does happen.

确认到达发送方[Jac88,RFC5681]。重复确认由接收端的无序到达触发。但是,由于来自接收方的重复确认是由网络路径中的段丢失和段重新排序触发的,因此发送方等待三个重复确认,以消除段丢失和段重新排序之间的歧义。当拥塞窗口很小时,可能无法生成所需数量的重复ack以在确实发生丢失时触发快速重传。

Small congestion windows can occur in a number of situations, such as:

在许多情况下都可能出现小拥塞窗口,例如:

(1) The connection is constrained by end-to-end congestion control when the connection's share of the path is small, the path has a small bandwidth-delay product, or the transport is ascertaining the available bandwidth in the first few round-trip times of slow start.

(1) 当连接在路径中所占的份额较小、路径具有较小的带宽延迟积或传输正在确定慢启动的前几个往返时间内的可用带宽时,连接受到端到端拥塞控制的约束。

(2) The connection is "application limited" and has only a limited amount of data to send. This can happen any time the application does not produce enough data to fill the congestion window. A particular case when all connections become application limited is as the connection ends.

(2) 该连接是“应用程序受限”的,只能发送有限的数据量。当应用程序无法生成足够的数据来填充拥塞窗口时,就会发生这种情况。当所有连接都受到应用程序限制时,一种特殊情况是当连接结束时。

(3) The connection is limited by the receiver's advertised window.

(3) 连接受接收器的播发窗口的限制。

The transport's retransmission timeout (RTO) is based on measured round-trip times (RTT) between the sender and receiver, as specified in [RFC2988] (for TCP) and [RFC4960] (for SCTP). To prevent spurious retransmissions of segments that are only delayed and not lost, the minimum RTO is conservatively chosen to be 1 second. Therefore, it behooves TCP senders to detect and recover from as many losses as possible without incurring a lengthy timeout during which the connection remains idle. However, if not enough duplicate ACKs arrive from the receiver, the fast retransmit algorithm is never triggered -- this situation occurs when the congestion window is small, if a large number of segments in a window are lost, or at the end of a transfer as data drains from the network. For instance, consider a congestion window of three segments' worth of data. If one segment is dropped by the network, then at most two duplicate ACKs will arrive at the sender. Since three duplicate ACKs are required to trigger fast retransmit, a timeout will be required to resend the dropped segment. Note that delayed ACKs [RFC5681] may further reduce the number of duplicate ACKs a receiver sends. However, we assume that receivers send immediate ACKs when there is a gap in the received sequence space per [RFC5681].

传输的重传超时(RTO)基于发送方和接收方之间测量的往返时间(RTT),如[RFC2988](TCP)和[RFC4960](SCTP)中所述。为了防止仅延迟且未丢失的段的伪重传,保守地选择最小RTO为1秒。因此,TCP发送方应该检测到尽可能多的丢失并从中恢复,而不会导致连接保持空闲的长时间超时。但是,如果没有足够的重复ACK从接收器到达,则不会触发快速重传算法——这种情况发生在拥塞窗口较小、窗口中大量段丢失或传输结束时,因为数据从网络中流失。例如,考虑三个区段的数据的拥塞窗口。如果一个段被网络丢弃,那么最多会有两个重复的ACK到达发送方。由于触发快速重传需要三个重复的ACK,因此重新发送丢弃的段需要超时。注意,延迟ack[RFC5681]可进一步减少接收器发送的重复ack的数量。然而,我们假设当接收到的序列空间中存在间隔时,接收器会根据[RFC5681]立即发送ACK。

[BPS+98] shows that roughly 56% of retransmissions sent by a busy Web server are sent after the RTO timer expires, while only 44% are handled by fast retransmit. In addition, only 4% of the RTO timer-based retransmissions could have been avoided with SACK, which has to continue to disambiguate reordering from genuine loss. Furthermore, [All00] shows that for one particular Web server, the median number of bytes carried by a connection is less than four segments, indicating that more than half of the connections will be forced to rely on the RTO timer to recover from any losses that occur. Thus, loss recovery that does not rely on the conservative RTO is likely to be beneficial for short TCP transfers.

[BPS+98]显示,在繁忙的Web服务器发送的重传中,大约56%是在RTO计时器过期后发送的,而只有44%是通过快速重传处理的。此外,只有4%的基于RTO定时器的重传可以通过SACK避免,SACK必须继续消除重新排序与真正丢失之间的歧义。此外,[All00]表明,对于一个特定的Web服务器,连接所承载的字节数中值小于四个段,这表明超过一半的连接将被迫依赖RTO计时器从发生的任何丢失中恢复。因此,不依赖于保守RTO的丢失恢复可能有利于短TCP传输。

The limited transmit mechanism introduced in [RFC3042] and currently codified in [RFC5681] allows a TCP sender to transmit previously unsent data upon receipt of each of the two duplicate ACKs that precede a fast retransmit. SCTP [RFC4960] uses SACK information to calculate the number of outstanding segments in the network. Hence, when the first two duplicate ACKs arrive at the sender, they will indicate that data has left the network, and they will allow the sender to transmit new data (if available), similar to TCP's limited transmit algorithm. In the remainder of this document, we use "limited transmit" to include both TCP and SCTP mechanisms for sending in response to the first two duplicate ACKs. By sending these two new segments, the sender is attempting to induce additional duplicate ACKs (if appropriate), so that fast retransmit will be triggered before the retransmission timeout expires. The sender-side "Early Retransmit" mechanism outlined in this document covers the case when previously unsent data is not available for transmission (case (2) above) or cannot be transmitted due to an advertised window limitation (case (3) above).

[RFC3042]中引入的有限传输机制,目前编入[RFC5681]中,允许TCP发送方在收到快速重新传输之前的两个重复ACK中的每一个后,传输先前未发送的数据。SCTP[RFC4960]使用SACK信息计算网络中未完成段的数量。因此,当前两个重复的ACK到达发送方时,它们将指示数据已离开网络,并允许发送方传输新数据(如果可用),类似于TCP的有限传输算法。在本文档的其余部分中,我们使用“有限传输”来包括TCP和SCTP机制,用于响应前两个重复的ACK进行发送。通过发送这两个新段,发送方试图诱导额外的重复ACK(如果合适),以便在重传超时到期之前触发快速重传。本文档中概述的发送方“早期重传”机制涵盖了先前未发送的数据不可用于传输(上述情况(2)或由于广告窗口限制而无法传输(上述情况(3))的情况。

Note: This document is being published as an experimental RFC, as part of the process for the TCPM working group and the IETF to assess whether the proposed change is useful and safe in the heterogeneous environments, including which variants of the mechanism are the most effective. In the future, this specification may be updated and put on the standards track if its safeness and efficacy can be demonstrated.

注:本文件作为实验性RFC发布,作为TCPM工作组和IETF评估拟议变更在异构环境中是否有用和安全的过程的一部分,包括机制的哪些变体最有效。将来,如果能够证明本规范的安全性和有效性,则可以对其进行更新,并将其纳入标准轨道。

2. Terminology
2. 术语

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].

本文件中的关键词“必须”、“不得”、“要求”、“应”、“不应”、“应”、“不应”、“建议”、“可”和“可选”应按照RFC 2119[RFC2119]中所述进行解释。

The reader is expected to be familiar with the definitions given in [RFC5681].

读者应熟悉[RFC5681]中给出的定义。

3. Early Retransmit Algorithm
3. 早期重传算法

The Early Retransmit algorithm calls for lowering the threshold for triggering fast retransmit when the amount of outstanding data is small and when no previously unsent data can be transmitted (such that limited transmit could be used). Duplicate ACKs are triggered by each arriving out-of-order segment. Therefore, fast retransmit will not be invoked when there are less than four outstanding segments (assuming only one segment loss in the window). However, TCP and SCTP are not required to track the number of outstanding segments, but rather the number of outstanding bytes or messages. (Note that SCTP's message boundaries do not necessarily correspond to segment boundaries.) Therefore, applying the intuitive notion of a transport with less than four segments outstanding is more complicated than it first appears. In Section 3.1, we describe a "byte-based" variant of Early Retransmit that attempts to roughly map the number of outstanding bytes to a number of outstanding segments that is then used when deciding whether to trigger Early Retransmit. In Section 3.2, we describe a "segment-based" variant that represents a more precise algorithm for triggering Early Retransmit. This precision comes at the cost of requiring additional state to be kept by the TCP sender. In both cases, we describe SACK-based and non-SACK-based versions of the scheme (of course, the non-SACK version will not apply to SCTP). This document explicitly does not prefer one variant over the other, but leaves the choice to the implementer.

早期重传算法要求在未发送数据量很小且无法传输之前未发送的数据时(例如,可以使用有限的传输),降低触发快速重传的阈值。每个到达的无序段都会触发重复确认。因此,如果未完成的段少于四个(假设窗口中只有一个段丢失),则不会调用快速重传。但是,TCP和SCTP不需要跟踪未完成段的数量,而是跟踪未完成字节或消息的数量。(请注意,SCTP的消息边界不一定对应于段边界。)因此,应用未完成段少于四段的传输的直观概念比最初出现的更复杂。在第3.1节中,我们描述了早期重传的一种“基于字节”的变体,该变体试图将未完成字节的数量大致映射到一些未完成段,然后在决定是否触发早期重传时使用这些未完成段。在第3.2节中,我们描述了一种“基于段”的变体,它代表了触发早期重传的更精确算法。这种精度的代价是要求TCP发送方保留额外的状态。在这两种情况下,我们描述了基于SACK和非SACK的方案版本(当然,非SACK版本不适用于SCTP)。本文档明确表示不喜欢一种变体而不喜欢另一种变体,而是将选择权留给实现者。

3.1. Byte-Based Early Retransmit
3.1. 基于字节的早期重传

A TCP or SCTP sender MAY use byte-based Early Retransmit.

TCP或SCTP发送方可以使用基于字节的早期重传。

Upon the arrival of an ACK, a sender employing byte-based Early Retransmit MUST use the following two conditions to determine when an Early Retransmit is sent:

在ACK到达时,采用基于字节的早期重传的发送方必须使用以下两个条件来确定何时发送早期重传:

(2.a) The amount of outstanding data (ownd) -- data sent but not yet acknowledged -- is less than 4*SMSS bytes (as defined in [RFC5681]).

(2.a)未完成数据量(ownd)——已发送但尚未确认的数据——小于4*SMSS字节(如[RFC5681]中所定义)。

Note that in the byte-based variant of Early Retransmit, "ownd" is equivalent to "FlightSize" (defined in [RFC5681]). We use different notation, because "ownd" is not consistent with FlightSize throughout this document.

注意,在早期重传的基于字节的变体中,“ownd”等同于“FlightSize”(在[RFC5681]中定义)。我们使用不同的符号,因为“ownd”与本文档中的FlightSize不一致。

Also note that in SCTP, messages will have to be converted to bytes to make this variant of Early Retransmit work.

还请注意,在SCTP中,必须将消息转换为字节,以使这种早期重传的变体能够工作。

(2.b) There is either no unsent data ready for transmission at the sender, or the advertised receive window does not permit new segments to be transmitted.

(2.b)发送方没有准备好传输的未发送数据,或者播发的接收窗口不允许传输新的段。

When the above two conditions hold and a TCP connection does not support SACK, the duplicate ACK threshold used to trigger a retransmission MUST be reduced to:

当上述两个条件保持且TCP连接不支持SACK时,用于触发重传的重复ACK阈值必须降低为:

                ER_thresh = ceiling (ownd/SMSS) - 1                 (1)
        
                ER_thresh = ceiling (ownd/SMSS) - 1                 (1)
        

duplicate ACKs, where ownd is expressed in terms of bytes. We call this reduced ACK threshold enabling "Early Retransmission".

重复的ACK,其中ownd以字节表示。我们将此降低的ACK阈值称为“早期重传”。

When conditions (2.a) and (2.b) hold and a TCP connection does support SACK or SCTP is in use, Early Retransmit MUST be used only when "ownd - SMSS" bytes have been SACKed.

当条件(2.a)和(2.b)保持且TCP连接不支持SACK或SCTP正在使用时,只有在“ownd-SMSS”字节已被SACK时,才必须使用早期重传。

If either (or both) condition (2.a) and/or (2.b) does not hold, the transport MUST NOT use Early Retransmit, but rather prefer the standard mechanisms, including fast retransmit and limited transmit.

如果条件(2.a)和/或(2.b)中的任何一个(或两者)不成立,则传输不得使用早期重传,而是更喜欢标准机制,包括快速重传和有限传输。

As noted above, the drawback of this byte-based variant is precision [HB08]. We illustrate this with two examples:

如上所述,这种基于字节的变体的缺点是精度[HB08]。我们用两个例子来说明这一点:

+ Consider a non-SACK TCP sender that uses an SMSS of 1460 bytes and transmits three segments, each with 400 bytes of payload. This is a case where Early Retransmit could aid loss recovery if one segment is lost. However, in this case, ER_thresh will become zero, per Equation (1), because the number of outstanding bytes is a poor estimate of the number of outstanding segments. A similar problem occurs for senders that employ SACK, as the expression "ownd - SMSS" will become negative.

+ 考虑一个非SACK TCP发送器,它使用1460字节的SMSS,并发送三个段,每个段具有400字节的有效载荷。在这种情况下,如果一段丢失,早期重传可以帮助恢复丢失。然而,在这种情况下,根据等式(1),ER_thresh将变为零,因为未完成字节的数量对未完成段的数量估计不佳。使用SACK的发送者也会遇到类似的问题,因为表达式“ownd-SMSS”将变为负值。

+ Next, consider a non-SACK TCP sender that uses an SMSS of 1460 bytes and transmits 10 segments, each with 400 bytes of payload. In this case, ER_thresh will be 2 per Equation (1). Thus, even though there are enough segments outstanding to trigger fast retransmit with the standard duplicate ACK threshold, Early Retransmit will be triggered. This could cause or exacerbate performance problems caused by segment reordering in the network.

+ 接下来,考虑一个非SACK TCP发送器,它使用1460字节的SMSS,并发送10个段,每个段具有400字节的有效载荷。在这种情况下,ER_thresh将为等式(1)中的2。因此,即使有足够多的未完成段触发具有标准重复ACK阈值的快速重传,也将触发早期重传。这可能会导致或加剧由网络中的段重新排序引起的性能问题。

3.2. Segment-Based Early Retransmit
3.2. 基于段的早期重传

A TCP or SCTP sender MAY use segment-based Early Retransmit.

TCP或SCTP发送方可以使用基于段的早期重传。

Upon the arrival of an ACK, a sender employing segment-based Early Retransmit MUST use the following two conditions to determine when an Early Retransmit is sent:

在ACK到达时,采用基于段的早期重传的发送方必须使用以下两个条件来确定何时发送早期重传:

(3.a) The number of outstanding segments (oseg) -- segments sent but not yet acknowledged -- is less than four.

(3.a)未完成段(oseg)的数量(已发送但尚未确认的段)少于四个。

(3.b) There is either no unsent data ready for transmission at the sender, or the advertised receive window does not permit new segments to be transmitted.

(3.b)发送方没有准备好传输的未发送数据,或者播发的接收窗口不允许传输新的段。

When the above two conditions hold and a TCP connection does not support SACK, the duplicate ACK threshold used to trigger a retransmission MUST be reduced to:

当上述两个条件保持且TCP连接不支持SACK时,用于触发重传的重复ACK阈值必须降低为:

ER_thresh = oseg - 1 (2)

ER_thresh=oseg-1(2)

duplicate ACKs, where oseg represents the number of outstanding segments. (We discuss tracking the number of outstanding segments below.) We call this reduced ACK threshold enabling "Early Retransmission".

重复ACK,其中oseg表示未完成段的数量。(我们将在下面讨论跟踪未完成段的数量。)我们将此降低的ACK阈值称为“早期重传”。

When conditions (3.a) and (3.b) hold and a TCP connection does support SACK or SCTP is in use, Early Retransmit MUST be used only when "oseg - 1" segments have been SACKed. A segment is considered to be SACKed when all of its data bytes (TCP) or data chunks (SCTP) have been indicated as arrived by the receiver.

当条件(3.a)和(3.b)保持且TCP连接确实支持SACK或SCTP正在使用时,只有在“oseg-1”段已被SACK时才必须使用早期重传。当一个段的所有数据字节(TCP)或数据块(SCTP)都被接收方指示为已到达时,该段被视为已被丢弃。

If either (or both) condition (3.a) and/or (3.b) does not hold, the transport MUST NOT use Early Retransmit, but rather prefer the standard mechanisms, including fast retransmit and limited transmit.

如果条件(3.a)和/或(3.b)中的任何一个(或两者)不成立,则传输不得使用早期重传,而是更喜欢标准机制,包括快速重传和有限传输。

This version of Early Retransmit solves the precision issues discussed in the previous section. As noted previously, the cost is that the implementation will have to track segment boundaries to form an understanding as to how many actual segments have been transmitted, but not acknowledged. This can be done by the sender tracking the boundaries of the three segments on the right side of the current window (which involves tracking four sequence numbers in TCP). This could be done by keeping a circular list of the segment boundaries, for instance. Cumulative ACKs that do not fall within this region indicate that at least four segments are outstanding, and therefore Early Retransmit MUST NOT be used. When the outstanding window becomes small enough that Early Retransmit can be invoked, a

此版本的早期重传解决了上一节讨论的精度问题。如前所述,成本是实施必须跟踪段边界,以了解有多少实际段已传输,但未确认。这可以通过发送方跟踪当前窗口右侧三个段的边界来完成(这涉及跟踪TCP中的四个序列号)。例如,这可以通过保持一个线段边界的循环列表来实现。不属于该区域的累积ack表明至少有四个段未完成,因此不得使用早期重传。当未完成的窗口变得足够小,可以调用早期重传时

full understanding of the number of outstanding segments will be available from the four sequence numbers retained. (Note: the implicit sequence number consumed by the TCP FIN bit can also be included in the tracking of segment boundaries.)

通过保留的四个序列号,可以充分了解未完成段的数量。(注意:TCP FIN位使用的隐式序列号也可以包含在段边界的跟踪中。)

4. Discussion
4. 讨论

In this section, we discuss a number of issues surrounding the Early Retransmit algorithm.

在本节中,我们将讨论围绕早期重传算法的一些问题。

4.1. SACK vs. Non-SACK
4.1. 解雇与非解雇

The SACK variant of the Early Retransmit algorithm is preferred to the non-SACK variant in TCP due to its robustness in the face of ACK loss (since SACKs are sent redundantly), and due to interactions with the delayed ACK timer (SCTP does not have a non-SACK mode and therefore naturally supports SACK-based Early Retransmit). Consider a flight of three segments, S1...S3, with S2 being dropped by the network. When S1 arrives, it is in order, and so the receiver may or may not delay the ACK, leading to two scenarios:

早期重传算法的SACK变体优于TCP中的非SACK变体,因为其在ACK丢失时具有鲁棒性(因为SACK是冗余发送的),并且由于与延迟ACK计时器的交互(SCTP没有非SACK模式,因此自然支持基于SACK的早期重传)。考虑一个三段的飞行,S1…S3,S2被网络丢弃。当S1到达时,它是有序的,因此接收机可能延迟ACK,也可能不延迟ACK,导致两种情况:

(A) The ACK for S1 is delayed: In this case, the arrival of S3 will trigger an ACK to be transmitted, covering S1 (which was previously unacknowledged). In this case, Early Retransmit without SACK will not prevent an RTO because no duplicate ACKs will arrive. However, with SACK, the ACK for S1 will also include SACK information indicating that S3 has arrived at the receiver. The sender can then invoke Early Retransmit on this ACK because only one segment remains outstanding.

(A) S1的ACK被延迟:在这种情况下,S3的到达将触发要发送的ACK,覆盖S1(之前未确认)。在这种情况下,没有SACK的早期重传不会阻止RTO,因为不会出现重复的ACK。然而,对于SACK,S1的ACK还将包括指示S3已到达接收器的SACK信息。然后,发送方可以在此ACK上调用早期重传,因为只有一个段仍然未完成。

(B) The ACK for S1 is not delayed: In this case, the arrival of S1 triggers an ACK of previously unacknowledged data. The arrival of S3 triggers a duplicate ACK (because it is out of order). Both ACKs will cover the same segment (S1). Therefore, regardless of whether SACK is used, Early Retransmit can be performed by the sender (assuming no ACK loss).

(B) S1的确认没有延迟:在这种情况下,S1的到达触发先前未确认数据的确认。S3的到达触发了一个重复的ACK(因为它是无序的)。两个ACK将覆盖同一段(S1)。因此,无论是否使用SACK,发送方都可以执行早期重传(假设没有ACK丢失)。

4.2. Segment Reordering
4.2. 段重新排序

Early Retransmit is less robust in the face of reordered segments than when using the standard fast retransmit threshold. Research shows that a general reduction in the number of duplicate ACKs required to trigger fast retransmit to two (rather than three) leads to a reduction in the ratio of good to bad retransmits by a factor of three [Pax97]. However, this analysis did not include the additional conditioning on the event that the ownd was smaller than four segments and that no new data was available for transmission.

与使用标准的快速重传阈值相比,在面对重新排序的段时,早期重传的鲁棒性较差。研究表明,触发快速重传所需的重复ACK数量一般减少到两个(而不是三个),导致良好与不良重传的比率减少三倍[Pax97]。然而,该分析并未包括ownd小于四段且无新数据可供传输的事件的附加条件。

A number of studies have shown that network reordering is not a rare event across some network paths. Various measurement studies have shown that reordering along most paths is negligible, but along certain paths can be quite prevalent [Pax97, BPS99, BS02, Pir05]. Evaluating Early Retransmit in the face of real segment reordering is part of the experiment we hope to instigate with this document.

大量研究表明,在某些网络路径上,网络重新排序并非罕见事件。各种测量研究表明,沿大多数路径重新排序可以忽略不计,但沿某些路径重新排序可能非常普遍[Pax97、BPS99、BS02、Pir05]。在面对真实的段重新排序时评估早期重传是我们希望通过本文档发起的实验的一部分。

4.3. Worst Case
4.3. 最坏情况

Next, we note two "worst case" scenarios for Early Retransmit:

接下来,我们注意到早期重传的两个“最坏情况”场景:

(1) Persistent reordering of segments coupled with an application that does not constantly send data can result in large numbers of needless retransmissions when using Early Retransmit. For instance, consider an application that sends data two segments at a time, followed by an idle period when no data is queued for delivery. If the network consistently reorders the two segments, the sender will needlessly retransmit one out of every two unique segments transmitted when using the above algorithm (meaning that one-third of all segments sent are needless retransmissions). However, this would only be a problem for long-lived connections from applications that transmit in spurts.

(1) 当使用早期重传时,段的持续重新排序加上不经常发送数据的应用程序可能会导致大量不必要的重传。例如,考虑一次一次发送数据两个段的应用程序,然后在没有数据排队的情况下发送一个空闲周期。如果网络一致地对这两个段重新排序,则发送方将在使用上述算法时不必要地重新传输每两个传输的唯一段中的一个(这意味着所有发送的段中有三分之一是不必要的重新传输)。然而,这只会是来自以突发方式传输的应用程序的长寿命连接的问题。

(2) Similar to the above, consider the case of that consist of two segment each and always experience reordering. Just as in (1) above, one out of every two unique data segments will be retransmitted needlessly; therefore, one-third of the traffic will be spurious.

(2) 与上述类似,考虑每两个部分组成的情况,并且总是经历重新排序。正如上面(1)中所述,每两个唯一数据段中就有一个将被不必要地重新传输;因此,三分之一的流量是虚假的。

Currently, this document offers no suggestion on how to mitigate the above problems. However, the worst cases are likely pathological. Part of the experiments that this document hopes to trigger would involve better understanding of whether such theoretical worst-case scenarios are prevalent in the network, and in general, to explore the trade-off between spurious fast retransmits and the delay imposed by the RTO. Appendix A does offer a survey of possible mitigations that call for curtailing the use of Early Retransmit when it is making poor retransmission decisions.

目前,本文件未提供如何缓解上述问题的建议。然而,最坏的情况可能是病理性的。本文件希望触发的部分实验将涉及更好地理解这种理论上的最坏情况场景是否在网络中普遍存在,并总体上探索虚假快速重传和RTO施加的延迟之间的权衡。附录A确实提供了可能的缓解措施调查,这些措施要求在做出错误的重传决策时减少早期重传的使用。

5. Related Work
5. 相关工作

There are a number of similar proposals in the literature that attempt to mitigate the same problem that Early Retransmit addresses.

文献中有许多类似的建议试图缓解早期重传所解决的相同问题。

Deployment of Explicit Congestion Notification (ECN) [Flo94, RFC3168] may benefit connections with small congestion window sizes [RFC2884]. ECN provides a method for indicating congestion to the end-host without dropping segments. While some segment drops may still occur,

部署显式拥塞通知(ECN)[Flo94,RFC3168]可能有利于拥塞窗口较小的连接[RFC2884]。ECN提供了一种在不删除段的情况下向终端主机指示拥塞的方法。尽管仍有可能出现某些细分市场下跌,

ECN may allow a transport to perform better with small congestion window sizes because the sender will be required to detect less segment loss [RFC2884].

ECN允许传输在拥塞窗口较小的情况下执行得更好,因为发送方需要检测较少的段丢失[RFC2884]。

[Bal98] outlines another solution to the problem of having no new segments to transmit into the network when the first two duplicate ACKs arrive. In response to these duplicate ACKs, a TCP sender transmits zero-byte segments to induce additional duplicate ACKs. This method preserves the robustness of the standard fast retransmit algorithm at the cost of injecting segments into the network that do not deliver any data, and therefore are potentially wasting network resources (at a time when there is a reasonable chance that the resources are scarce).

[Bal98]概述了当前两个重复ACK到达时,没有新段传输到网络的问题的另一种解决方案。为了响应这些重复的ack,TCP发送方传输零字节段以诱导额外的重复ack。该方法保持了标准快速重传算法的健壮性,但代价是将不传递任何数据的段注入网络,因此可能会浪费网络资源(在资源合理稀缺的情况下)。

[RFC4653] also defines an orthogonal method for altering the duplicate ACK threshold. The mechanisms proposed in this document decrease the duplicate ACK threshold when a small amount of data is outstanding. Meanwhile, the mechanisms in [RFC4653] increase the duplicate ACK threshold (over the standard of 3) when the congestion window is large in an effort to increase robustness to segment reordering.

[RFC4653]还定义了用于改变重复ACK阈值的正交方法。当少量数据未完成时,本文中提出的机制降低了重复ACK阈值。同时,[RFC4653]中的机制在拥塞窗口较大时增加重复ACK阈值(超过标准3),以增强对段重新排序的鲁棒性。

6. Security Considerations
6. 安全考虑

The security considerations found in [RFC5681] apply to this document. No additional security problems have been identified with Early Retransmit at this time.

[RFC5681]中的安全注意事项适用于本文档。目前尚未发现早期重新传输的其他安全问题。

7. Acknowledgments
7. 致谢

We thank Sally Floyd for her feedback in discussions about Early Retransmit. The notion of Early Retransmit was originally sketched in an Internet-Draft co-authored by Sally Floyd and Hari Balakrishnan. Armando Caro, Joe Touch, Alexander Zimmermann, and many members of the TSVWG and TCPM working groups provided good discussions that helped shape this document. Our thanks to all!

我们感谢Sally Floyd在关于早期再传输的讨论中提供的反馈。早期重发的概念最初是在萨利·弗洛伊德和哈里·巴拉克里希南合著的互联网草稿中勾勒出来的。Armando Caro、Joe Touch、Alexander Zimmermann以及TSVWG和TCPM工作组的许多成员进行了良好的讨论,帮助形成了本文件。我们感谢大家!

8. References
8. 工具书类
8.1. Normative References
8.1. 规范性引用文件

[RFC793] Postel, J., "Transmission Control Protocol", STD 7, RFC 793, September 1981.

[RFC793]Postel,J.,“传输控制协议”,标准7,RFC 793,1981年9月。

[RFC2018] Mathis, M., Mahdavi, J., Floyd, S., and A. Romanow, "TCP Selective Acknowledgment Options", RFC 2018, October 1996.

[RFC2018]Mathis,M.,Mahdavi,J.,Floyd,S.,和A.Romanow,“TCP选择性确认选项”,RFC 2018,1996年10月。

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.

[RFC2119]Bradner,S.,“RFC中用于表示需求水平的关键词”,BCP 14,RFC 2119,1997年3月。

[RFC2883] Floyd, S., Mahdavi, J., Mathis, M., and M. Podolsky, "An Extension to the Selective Acknowledgement (SACK) Option for TCP", RFC 2883, July 2000.

[RFC2883]Floyd,S.,Mahdavi,J.,Mathis,M.,和M.Podolsky,“TCP选择性确认(SACK)选项的扩展”,RFC 28832000年7月。

[RFC2988] Paxson, V. and M. Allman, "Computing TCP's Retransmission Timer", RFC 2988, November 2000.

[RFC2988]Paxson,V.和M.Allman,“计算TCP的重传计时器”,RFC 2988,2000年11月。

[RFC3042] Allman, M., Balakrishnan, H., and S. Floyd, "Enhancing TCP's Loss Recovery Using Limited Transmit", RFC 3042, January 2001.

[RFC3042]Allman,M.,Balakrishnan,H.,和S.Floyd,“使用有限传输增强TCP的丢失恢复”,RFC 3042,2001年1月。

[RFC4960] Stewart, R., Ed., "Stream Control Transmission Protocol", RFC 4960, September 2007.

[RFC4960]Stewart,R.,Ed.“流控制传输协议”,RFC 49602007年9月。

[RFC5681] Allman, M., Paxson, V., and E. Blanton, "TCP Congestion Control", RFC 5681, September 2009.

[RFC5681]Allman,M.,Paxson,V.和E.Blanton,“TCP拥塞控制”,RFC 56812009年9月。

8.2. Informative References
8.2. 资料性引用

[AA02] Urtzi Ayesta, Konstantin Avrachenkov, "The Effect of the Initial Window Size and Limited Transmit Algorithm on the Transient Behavior of TCP Transfers", In Proc. of the 15th ITC Internet Specialist Seminar, Wurzburg, July 2002.

[AA02]Urtzi Ayesta,Konstantin Avrachenkov,“初始窗口大小和有限传输算法对TCP传输瞬态行为的影响”,在Proc。2002年7月在伍尔茨堡举行的国际贸易中心第十五届互联网专家研讨会。

[All00] Mark Allman. A Web Server's View of the Transport Layer. ACM Computer Communication Review, October 2000.

马克·奥尔曼。Web服务器的传输层视图。ACM计算机通信评论,2000年10月。

[Bal98] Hari Balakrishnan. Challenges to Reliable Data Transport over Heterogeneous Wireless Networks. Ph.D. Thesis, University of California at Berkeley, August 1998.

哈里巴拉克里希南。异构无线网络上可靠数据传输的挑战。博士。毕业论文,加州大学伯克利分校,1998年8月。

[BPS+98] Hari Balakrishnan, Venkata Padmanabhan, Srinivasan Seshan, Mark Stemm, and Randy Katz. TCP Behavior of a Busy Web Server: Analysis and Improvements. Proc. IEEE INFOCOM Conf., San Francisco, CA, March 1998.

[BPS+98]Hari Balakrishnan、Venkata Padmanabhan、Srinivasan Seshan、Mark Stemm和Randy Katz。繁忙Web服务器的TCP行为:分析和改进。过程。IEEE ICOFCOM,旧金山,CA,1998年3月。

[BPS99] Jon Bennett, Craig Partridge, Nicholas Shectman. Packet Reordering is Not Pathological Network Behavior. IEEE/ACM Transactions on Networking, December 1999.

Jon Bennett Craig Partridge Nicholas Shectman。数据包重新排序不是病态的网络行为。IEEE/ACM网络交易,1999年12月。

[BS02] John Bellardo, Stefan Savage. Measuring Packet Reordering, ACM/USENIX Internet Measurement Workshop, November 2002.

[BS02]约翰·贝拉多,斯蒂芬·萨维奇。测量数据包重新排序,ACM/USENIX互联网测量研讨会,2002年11月。

[FF96] Kevin Fall, Sally Floyd. Simulation-based Comparisons of Tahoe, Reno, and SACK TCP. ACM Computer Communication Review, July 1996.

[FF96]凯文·法尔,萨利·弗洛伊德。基于模拟的Tahoe、Reno和SACK TCP比较。ACM计算机通信评论,1996年7月。

[Flo94] Sally Floyd. TCP and Explicit Congestion Notification. ACM Computer Communication Review, October 1994.

萨莉·弗洛伊德。TCP和显式拥塞通知。ACM计算机通信评论,1994年10月。

[HB08] Per Hurtig, Anna Brunstrom. Enhancing SCTP Loss Recovery: An Experimental Evaluation of Early Retransmit. Elsevier Computer Communications, Vol. 31(16), October 2008, pp. 3778-3788.

[HB08]Per Hurtig,Anna Brunstrom。增强SCTP丢失恢复:早期重传的实验评估。爱思唯尔计算机通信,第31卷(16),2008年10月,第3778-3788页。

[Jac88] Van Jacobson. Congestion Avoidance and Control. ACM SIGCOMM 1988.

范雅各布森。拥塞避免和控制。ACM SIGCOMM 1988。

[LK98] Dong Lin, H.T. Kung. TCP Fast Recovery Strategies: Analysis and Improvements. Proc. IEEE INFOCOM Conf., San Francisco, CA, March 1998.

[LK98]董林,龚H.T。TCP快速恢复策略:分析和改进。过程。IEEE ICOFCOM,旧金山,CA,1998年3月。

[Mor97] Robert Morris. TCP Behavior with Many Flows. Proc. Fifth IEEE International Conference on Network Protocols, October 1997.

罗伯特·莫里斯。具有多个流的TCP行为。过程。第五届IEEE网络协议国际会议,1997年10月。

[Pax97] Vern Paxson. End-to-End Internet Packet Dynamics. ACM SIGCOMM, September 1997.

[Pax97]弗恩·帕克森。端到端Internet数据包动态。ACM SIGCOMM,1997年9月。

[Pir05] N. M. Piratla, "A Theoretical Foundation, Metrics and Modeling of Packet Reordering and Methodology of Delay Modeling using Inter-packet Gaps," Ph.D. Dissertation, Department of Electrical and Computer Engineering, Colorado State University, Fort Collins, CO, Fall 2005.

[Prim05] N.M.PiRATLA,“理论基础、包重新排序的度量和建模和使用包间间隙的延迟建模方法”,Ph.D.科罗拉多州立大学电气与计算机工程系毕业论文,科罗拉多州柯林斯堡,2005年秋季。

[RFC2884] Hadi Salim, J. and U. Ahmed, "Performance Evaluation of Explicit Congestion Notification (ECN) in IP Networks", RFC 2884, July 2000.

[RFC2884]Hadi Salim,J.和U.Ahmed,“IP网络中显式拥塞通知(ECN)的性能评估”,RFC 2884,2000年7月。

[RFC3150] Dawkins, S., Montenegro, G., Kojo, M., and V. Magret, "End-to-end Performance Implications of Slow Links", BCP 48, RFC 3150, July 2001.

[RFC3150]Dawkins,S.,黑山,G.,Kojo,M.,和V.Magret,“慢链路的端到端性能影响”,BCP 48,RFC 3150,2001年7月。

[RFC3168] Ramakrishnan, K., Floyd, S., and D. Black, "The Addition of Explicit Congestion Notification (ECN) to IP", RFC 3168, September 2001.

[RFC3168]Ramakrishnan,K.,Floyd,S.,和D.Black,“向IP添加显式拥塞通知(ECN)”,RFC 3168,2001年9月。

[RFC3517] Blanton, E., Allman, M., Fall, K., and L. Wang, "A Conservative Selective Acknowledgment (SACK)-based Loss Recovery Algorithm for TCP", RFC 3517, April 2003.

[RFC3517]Blanton,E.,Allman,M.,Fall,K.,和L.Wang,“基于保守选择确认(SACK)的TCP丢失恢复算法”,RFC 3517,2003年4月。

[RFC3522] Ludwig, R. and M. Meyer, "The Eifel Detection Algorithm for TCP", RFC 3522, April 2003.

[RFC3522]Ludwig,R.和M.Meyer,“TCP的Eifel检测算法”,RFC 3522,2003年4月。

[RFC3782] Floyd, S., Henderson, T., and A. Gurtov, "The NewReno Modification to TCP's Fast Recovery Algorithm", RFC 3782, April 2004.

[RFC3782]Floyd,S.,Henderson,T.,和A.Gurtov,“TCP快速恢复算法的NewReno修改”,RFC 3782,2004年4月。

[RFC4653] Bhandarkar, S., Reddy, A., Allman, M., and E. Blanton, "Improving the Robustness of TCP to Non-Congestion Events", RFC 4653, August 2006.

[RFC4653]Bhandarkar,S.,Reddy,A.,Allman,M.,和E.Blanton,“提高TCP对非拥塞事件的鲁棒性”,RFC 46532006年8月。

Appendix A. Research Issues in Adjusting the Duplicate ACK Threshold
附录A.调整重复确认阈值的研究问题

Decreasing the number of duplicate ACKs required to trigger fast retransmit, as suggested in Section 3, has the drawback of making fast retransmit less robust in the face of minor network reordering. Two egregious examples of problems caused by reordering are given in Section 4. This appendix outlines several schemes that have been suggested to mitigate the problems caused by Early Retransmit in the face of segment reordering. These methods need further research before they are suggested for general use (and current consensus is that the cases that make Early Retransmit unnecessarily retransmit a large amount of data are pathological, and therefore, these mitigations are not generally required).

如第3节所建议的那样,减少触发快速重传所需的重复ack的数量,有一个缺点,即在面对较小的网络重新排序时,快速重传的健壮性会降低。第4节给出了两个由重新排序引起的问题的惊人例子。本附录概述了为缓解在面临段重新排序时早期重传造成的问题而建议的几种方案。这些方法在建议普遍使用之前需要进一步研究(目前的共识是,导致早期重新传输不必要地重新传输大量数据的情况是病理性的,因此,通常不需要这些缓解措施)。

MITIGATION A.1: Allow a connection to use Early Retransmit as long as the algorithm is not injecting "too much" spurious data into the network. For instance, using the information provided by TCP's D-SACK option [RFC2883] or SCTP's Duplicate Transmission Sequence Number (Duplicate-TSN) notification, a sender can determine when segments sent via Early Retransmit are needless. Likewise, using Eifel [RFC3522], the sender can detect spurious Early Retransmits. Once spurious Early Retransmits are detected, the sender can either eliminate the use of Early Retransmit, or limit the use of the algorithm to ensure that an acceptably small fraction of the connection's transmissions are not spurious. For example, a connection could stop using Early Retransmit after the first spurious retransmit is detected.

缓解措施A.1:只要算法没有向网络中注入“太多”虚假数据,就允许连接使用早期重传。例如,使用TCP的D-SACK选项[RFC2883]或SCTP的重复传输序列号(Duplicate Transmission Sequence Number,重复TSN)通知提供的信息,发送方可以确定何时不需要通过早期重传发送的段。同样,使用Eifel[RFC3522],发送方可以检测到虚假的早期重传。一旦检测到虚假的早期重传,发送方可以消除早期重传的使用,或者限制算法的使用,以确保可接受的一小部分连接传输不是虚假的。例如,在检测到第一次虚假重传后,连接可能会停止使用早期重传。

MITIGATION A.2: If a sender cannot reliably determine whether an Early-Retransmitted segment is spurious or not, the sender could simply limit Early Retransmits, either to some fixed number per connection (e.g., Early Retransmit is allowed only once per connection), or to some small percentage of the total traffic being transmitted.

缓解措施A.2:如果发送方无法可靠地确定提前重传的段是否为伪段,则发送方可以简单地将提前重传限制在每个连接的某个固定数量(例如,每个连接只允许提前重传一次)或传输的总流量的某个小百分比。

MITIGATION A.3: Allow a connection to trigger Early Retransmit using the criteria given in Section 3, in addition to a "small" timeout [Pax97]. For instance, a sender may have to wait for two duplicate ACKs and then T msec before Early Retransmit is invoked. The added time gives reordered acknowledgments time to arrive at the sender and avoid a needless retransmit. Designing a method for choosing an appropriate timeout is part of the research that would need to be involved in this scheme.

缓解措施A.3:除“小”超时外,允许连接使用第3节中给出的标准触发早期重传[Pax97]。例如,在调用早期重传之前,发送方可能必须等待两个重复的ack,然后等待T毫秒。增加的时间为重新排序的确认提供了到达发送方并避免不必要的重新传输的时间。设计一种选择适当超时的方法是该方案需要涉及的研究的一部分。

Authors' Addresses

作者地址

Mark Allman International Computer Science Institute 1947 Center Street, Suite 600 Berkeley, CA 94704-1198 USA Phone: 440-235-1792 EMail: mallman@icir.org http://www.icir.org/mallman/

美国加利福尼亚州伯克利中心街1947号中心街600室马克·奥尔曼国际计算机科学研究所94704-1198电话:440-235-1792电子邮件:mallman@icir.org http://www.icir.org/mallman/

Konstantin Avrachenkov INRIA 2004 route des Lucioles, B.P.93 06902, Sophia Antipolis France Phone: 00 33 492 38 7751 EMail: k.avrachenkov@sophia.inria.fr http://www-sop.inria.fr/members/Konstantin.Avratchenkov/me.html

Konstantin Avrachenkov INRIA 2004路des Lucioles,B.P.93 06902,索菲亚安提波利斯法国电话:00 33 492 38 7751电子邮件:k。avrachenkov@sophia.inria.fr http://www-sop.inria.fr/members/Konstantin.Avratchenkov/me.html

Urtzi Ayesta BCAM-IKERBASQUE LAAS-CNRS Bizkaia Technology Park, Building 500 7 Avenue Colonel Roche 48160 Derio 31077, Toulouse Spain France EMail: urtzi@laas.fr http://www.laas.fr/~urtzi

Urtzi Ayesta BCAM-IKERBASQUE LAAS-CNRS Bizkaia科技园,地址:西班牙图卢兹7大道500号Colonel Roche 48160 Derio 31077法国电子邮件:urtzi@laas.fr http://www.laas.fr/~z~乌尔茨

Josh Blanton Ohio University 301 Stocker Center Athens, OH 45701 USA EMail: jblanton@irg.cs.ohiou.edu

Josh Blanton俄亥俄大学301斯托克中心俄亥俄州雅典市45701美国电子邮件:jblanton@irg.cs.ohiou.edu

Per Hurtig Karlstad University Department of Computer Science Universitetsgatan 2 651 88 Karlstad Sweden EMail: per.hurtig@kau.se

Per Hurtig Karlstad大学计算机科学系加坦2 651 88 Karlstad瑞典电子邮件:Per。hurtig@kau.se