Subject: Re: [P2PSIP] proposal for reload congestion control, fragmentation, and retransmission

From: Michael Chen <[email-masked]>
Date: Mon, 02 Mar 2009 21:28:11 -0800

Bruce,

I have 2 suggestions for section "5.5.2.1. Framed Message Format" in the 
current Reload draft relevant to UDP fragmentation and retransmission.  
This section defined framed message as:

         enum {data (128), ack (129), (255)} FramedMessageType;
         struct {
           FramedMessageType       type;
           select (type) {
             case data:
               uint24              sequence;
               opaque              message<0..2^24-1>;
             case ack:
               uint24              ack_sequence;
               uint32              received;
           };

Suggestion 1:
The 24-bit length for the message payload is unnecessary and should be 
removed.  The message is DTLS record, which has its own size and 
integrity check scheme. Also, the UDP packet carries its own packet size 
which is returned with the recvfrom() function on the UDP socket.

Suggestion 2:
Add a third message type "truncated (130)", which can be sent back by 
the receiver to indicate that the UDP packet was truncated, most likely 
due to a smaller MTU in either side.  The receiver can easily detect 
this error state by verifying the DTLS record length against the UDP 
packet size.

             case truncated:
               uint24              ack_sequence;
               uint32              packet_size;

The ack_sequence in a truncated reply is identical to a ack reply, 
except that the sender MUST retransmit this same sequence with a smaller 
packet size, which is hinted by the second value packet_size;  The 
sender can also initiate a MTU discovery.

If MTU discovery (before the first payload is sent) is mandated by later 
revision of this draft, then suggestion 2 can be ignored.

Thanks

--Michael

Bruce Lowekamp wrote:
> There has been a bunch of discussion about the reassembly of
> fragmented packets.  Because fragmentation and hop-by-hop reliability
> are related, we've been considering them both together. Here is a
> proposal for how to address these and other related issues.  Although
> some of this is in normative text, much of it is descriptive and
> normative text will need to be written for the draft.
>
> Bruce
>
> Topics that need to be addressed include:
>
> * Via List changes
> * hop-by-hop fragmenting, end-to-end-reassembly of fragmented messages
> * MTU discovery
> * TFRC and semi-reliable retransmission for unreliable links
> * framing for stream-based links (TLS/TCP)
> * queueing overlay messages
> * link failure detection
> * end-to-end retransmission
> * removal of route-logging
> * negotiating new overlay link protocols
>
>
> * Via List changes
>
> The current via-list structure will be changed.  The shortest via
> list entry (other than for the origination and destination) is a
> 15-bit opaque identifier with meaning only to the forwarding peer.
> This 15-bit information is encoded in only 16 bits to minimize the
> size of the via list.  We have chosen to go with this very tight
> encoding because the entire forwarding header must be present in each
> fragment, and the protocol must work well over links with very small
> MTUs.
>
> The remainder of the encoding will remain as it is now, although a
> variable-length opaque identifier will also be allowed for situations
> where the implementer or deployer knows that more than 15 bits of
> information is required.  An implementation SHOULD use the shortest
> possible entry for its application.
>
> If the first bit is 0, then the Destination is 16 bits long, and the
> destination_data is an opaque 15-bit identifier.
>
> (these structure definitions are conceptual only and intended for
> discussion.  the final representation may be different.)
>
> struct {
>  uint8 isLong:1; // =0
>  uint16 dest_info:15;
> }
>
> struct {
>  uint8 isLong:1; // =1
>  uint8 length:7
>  DestinationType type;
>  DestinationData destination_data;
> }
>
> add a DestinationType for opaque id;
>
>
> One possible encoding of the dest_info opaque identifier is to encode
> an index into a connection table.  To avoid misrouting responses in
> the event a response is delayed and the connection table entry has
> changed, the identifier should be split between an index and a
> generation counter for that index.  At startup, the generation
> counters should be initialized to random values.  An implementation
> could use 12 bits for the connection table index and 3 bits for the
> generation counter.  (Note that this does not suggest a 4096 entry
> connection table for every node, only the ability to encode for a
> larger connection table.)  When a connection table slot is used for a
> new connection, the generation counter is incremented (with wrapping).
> Connection table slots are used on a rotating basis to maximize the
> time interval between using the same slot for different connections.
> When routing a message to an entry in the destination list encoding a
> connection table entry, the node confirms that the generation counter
> matches the current generation counter of that index before forwarding
> the message.  If it does not match, the message is silently dropped.
>
> Regardless of how the dest_info field or opaque DestinationType is
> used, the encoding MUST include a generation counter designed to
> prevent misrouting of responses due to the connection table entry
> having changed since the request message was originally forwarded.
>
>
> * hop-by-hop fragmenting, end-to-end-reassembly of fragmented messages
>
>
> Any node along the path can fragment the message but only the final
> destination reassembles the fragments. When a node takes a packet and
> fragments it, each fragment has a full copy of the Forwarding Header
> but the data after the Forwarding Header is broken up in appropriate
> sized chunks. The size of the payload chunks needs to take into
> account space to allow the via and lists to grow.  Each fragment MUST
> contain a full copy of the via and destination list and MUST contain
> at least 256 bytes of the message body.  If the via and destination
> list are so large that this is not possible, RELOAD fragmentation is
> not performed and IP-layer fragmentation is allowed to occur.  When a
> message must be fragmented, it SHOULD be split into equal-sized
> fragments that are no larger than the PMTU of the next overlay link
> minus 32 bytes.  This is to allow the via list to grow before further
> fragmentation is required.
>
> Note that this fragmentation is not optimal for the end-to-end
> path---a message may be refragmented multiple times as it traverses
> the overlay.  This option has been chosen as it is far easier to
> implement than e2e PMTU discovery across an ever-changing overlay, and
> effectively addresses the reliability issues of relying on IP-layer
> fragmentation.  However, PING will be extended to allow e2e PMTU to be
> implemented if desired.
>
> The final node that was receiving the data would need to reassemble
> it. Any fragment older than 15 seconds SHOULD be discarded. However,
> it does need to store all the fragments it receives and once it has
> all the fragments for a messages.  The amount of buffer space it needs
> for this is proportional to whatever bit rate it is wiling to precess
> messages at.  Will have to specify something allowing excess fragments
> to be dropped in case of attack.
>
>
> * MTU discovery
>
> MTU discovery is required both at the overlay link level and
> end-to-end across the overlay (being the minimum of the overlay link
> MTUs along the path).  We will refer to these as overlay link MTU and
> end-to-end MTU.
>
> PING is used for overlay link MTU discovery.  After establishing a new
> connection, a node uses PING sent to this neighbor with the DF bit set
> and a NULL (need to define) forwarding option header that extends the
> message to the desired length.  A series of these probes is used to
> identify the overlay link MTU for this connection.  See RFC4821 for
> more details on this algorithm.
>
> If a node choses not to perform overlay link MTU discovery, or before
> it has determined a larger overlay link MTU via a PING, it SHOULD use
> a default overlay link MTU of the overlay link of 576 bytes for IPv4
> and 1280 bytes for IPv6 (RFC5405).
>
> For end-to-end MTU discovery, the PING response will have an
> attribute added indicating the largest fragment of the PING request
> that was received.  Calculating this value is OPTIONAL and if not
> implemented, 0 should be reported in this field.  Note that use of
> this field measures a lower-bound, and not an upper bound on the
> end-to-end MTU.  It also does not ensure that each hop along the path
> did not use IP-layer fragmentation.  End-to-end MTU discovery is not
> required nor specified by this document.
>
> * TFRC and semi-reliable retransmission for unreliable links
>
> Goal of algorithm specified in document is:
>
> - provide a stop and wait algorithm that is as simple to implement as
>  possible
> - provide a somewhat more complicated AIMD algorithm that is also more
>  conservative than TFRC and allows pipelining
> - allow TFRC to be implemented
> - do this with a single simple receiver, so all changes to allow more
>  complicated congestion control are done on the sender side.
>
> Much of this is the same as what is in the current draft, but there
> are some clarifications here.
>
> Each packet sent has a sequence number.  A sequence number is never
> reused (until wraparound), if a retransmission occurs it receives a
> new sequence number.  It is up to the sender to keep track of that.
>
> When the receiver sends an ACK, it ACKs a particular sequence number
> and sets bits in the mask for recently received packets that it has a
> record of.  A bit not being set in the mask is not a NACK.  Nodes
> SHOULD remember the previous 32 sequence numbers.  A receiver MUST NOT
> use any form of delayed ACKs.
>
> A receiver does not implement any form of a buffer or memory of which
> packets it has or has not received outside of the most recent 32.  It
> is purely the job for the sender to implement semi-reliability.
>
> The hop-by-hop link retransmission is intended to provide
> semi-reliable service.  (good-effort service.)  It does not, and
> cannot, provide total reliability. Among other problems, an overlay
> network may experience congestion or stability problems, so attempts
> to achieve perfect hop-by-hop reliability will not achieve the desired
> effect of perfect message reliability.
>
> Now details of the sender algorithms:
>
> stop-and-wait:
>
> Stop and wait allows only one fragment to be in transit per DTLS
> connection.  It has abysmal performance for WAN connections, but is
> typically acceptable for LAN performance (for low-bandwidth overlays).
>
> A peer SHOULD retransmit a fragment if it has not received an ACK for
> that fragment starting with an interval of RTO ("Retransmission
> TimeOut"), doubling after each retransmission. In each retransmission,
> the sequence number is incremented. The RTO is an estimate of the
> round-trip time (RTT), and is computed as described in RFC 2988
> [RFC2988], with two exceptions. First, the initial value for RTO
> SHOULD be calculated from the STUN connectivity checks used to
> establish the connection.  If that is not possible, the initial value
> for RTO SHOULD be configurable (rather than the 3 s recommended in RFC
> 2988) and SHOULD be greater than 500 ms.  In fixed-line access links,
> a value of 500 ms is RECOMMENDED. Second, the value of RTO SHOULD NOT
> be rounded up to the nearest second. Rather, a 1 ms accuracy SHOULD be
> maintained. As with TCP, the usage of Karn's algorithm is RECOMMENDED
> [TODO REF KARN87] which means that RTT estimates SHOULD NOT be
> computed from transactions that result in the retransmission of a
> request. The value for RTO is calculated separately for each DTLS
> session.
>
> Retransmissions continue until a response is received, or until a
> total of Rc requests have been sent or there has been a hard ICMP
> error [RFC1122]. The RECOMMENDED value of Rc is 5 and it MUST be at
> least 3.  The receiver knows a responses was received by receiving and
> ACK with a sequence number that indicates it is a response to one of
> the transmissions of this fragment. For example, assuming an RTO of
> 500 ms and Rc of 5, requests would be sent at times 0 ms, 500 ms, 1500
> ms, 3500 ms, and 7500 ms. If all retransmissions for a fragment fail,
> the DTLS connection SHOULD be closed.
>
> Once an ACK has been received for a fragment, the next fragment can be
> sent but the peer SHOULD ensure that there is at least 10 ms between
> sending any two fragments.
>
>
> AIMD:
>
> A sender can implement TCP or TCP-like algorithms provided that they
> meet the aggressiveness requirement.  The algorithm here is only the
> AIMD portion of TCP.  All other features are restricted to simplify
> the implementation, i.e. no slow start (initial window is 1), no fast
> retransmission, and no fast recovery.  An implementation may use one
> timer per fragment or a single timer for only the oldest outstanding
> fragment.
>
> AIMD extends stop and wait by allowing multiple fragments to be
> pending at the same time.  The sender allows w unacknowledged
> fragments to be outstanding at any given time.  w is initially set to
> one.  Every RTO interval that no retransmissions occur, w is increased
> by one.  When a loss occurs, w is halved.  After halving w, if there
> are more than w fragments for which an ACK is pending, no further
> retransmissions of the most recently initiated fragments are performed
> until they fit in the window w, at which point they begin the
> retransmission algorithm again.  w is held fixed for one RTO.  After that
> point, if additional retransmissions occur, it will be halved again,
> otherwise it may be incremented after an additional RTO without loss.
>
> If w drops to one and the one pending fragment is not ACKed by the
> other side after 5 requests are sent, the link is considered to have
> failed.  Otherwise, unACKed fragments are simply dropped.
>
> TFRC:
>
> TFRC (RFC5348) can be implemented in the Sender-Based Variant format
> with the same receiver algorithm.  This implementation requires the
> sender to maintain precise timestamps in ms of the transmission time
> of each sequence number as well as the segment sizes.  That, combined
> with the ACKs (and that the ACKs are not delayed) allows the sender to
> calculate the performance required by TFRC, including information
> calculated by the receiver in the conventional form of TFRC.
>
> TFRC is used for congestion control.  For reliability, an individual
> fragment is retransmitted up to twice at RTO intervals, pending the
> availability of room in the congestion window.  If it is not
> ACKed after another RTO following its last retransmission, it is dropped.
>
>
> * framing for stream-based links (TLS/TCP)
>
> A framing header is specified for TCP links.  The framing headers are
> used to calculate RTT and detect when the TCP link has failed.
>
>
> * queueing overlay messages
>
> For all link types, a peer MUST implement an appropriate queueing
> discipline for determining which messages are forwarded.  For all link
> types, the peer MUST queue at least 5 messages.  For overlay link
> algorithms that implement a congestion window, the peer SHOULD queue
> the greater of 5 messages or the current size of the congestion
> window.  For overlay link algorithms that rely on an underlying
> buffer, such as TCP, the peer SHOULD queue 5 messages beyond what fits
> in the socket buffer.  Tuning for performance of the overlay link
> SHOULD be accomplished by adjusting the size of the socket buffer
> appropriately (ref).  In no case should a message be queued longer than
> 500ms.
>
> A node MAY implement a separate queue for internally originated
> messages, but when operating in a congestion-limited mode, the node
> MUST NOT allow its internally originated traffic to dominate the link.
>
> * link failure detection
>
> Links are detected to have failed under these conditions:
>
> - periodic STUN keepalive fails (need to specify when these are used)
> - no new TCP or UDP framing acknowledgements are received for 10RTT
>
> (Note that ICE and ICE-TCP both require the use of keepalives.  A node
> MAY elect to substitute receiving framing acknowledgements for
> separate active STUN keepalives.)
>
> * end-to-end retransmission
>
> End-to-end retransmission will be accomplished using exponential
> backoff.  An implementation SHOULD track round-trip times of messages
> sent on the overlay and use set end-to-end RTO to 1.5 times the
> average RTT.  An implementation MAY track RTTs and set RTOs on a
> per-destination basis.  If an implementation does not track end-to-end
> RTT, then RTO SHOULD default to 3000ms.
>
> * removal of route-logging
>
> route log will be removed from the forwarding header
>
> * negotiating new overlay link protocols
>
> a protocol ID will be added to the ICE negotiation to specify what
> link protocol is being run between nodes, analogous to how media is
> negotiated in SDP.  To avoid offer/answer headaches, we will not
> import the concept of an offer-less attach, and there will be a
> mandatory protocol that must be included in each offer so there cannot
> be a failure to share a protocol.  (optionally include "better" base
> option in overlay config?)
> _______________________________________________
> P2PSIP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/p2psip
>

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 02 Mar 2009 22:31:23 -0800

At Mon, 02 Mar 2009 21:28:11 -0800,
> which is returned with the recvfrom() function on the UDP socket.

This framing is also going to be used with TLS, so you do need
the length there. I'd rather have a consistent framing than
save 3 bytes.

> revision of this draft, then suggestion 2 can be ignored.

What sort of IP network element do you think would truncate UDP
datagrams? AFAIK, either they should be (1) sent intact (2) fragmented
or (3) dropped.

-Ekr

---

From: Salman Abdul Baset <[email-masked]>
Date: Mon, 16 Mar 2009 15:36:11 -0400 (EDT)

I have tried to summarize the solution space for addressing fragmentation, 
congestion control and reliability issues when using an unreliable 
transport. This includes the proposal by Bruce. I think that the WG needs 
to contrast their complexity with the use of a reliable transport (TCP), 
and consider whether to specify these mechanisms in a separate document 
or the base document.

Fragmentation
-------------

*Hop-by-hop fragmentation, hop-by-hop complete reassembly

*Hop-by-hop fragmentation and end-to-end reassembly
   -When RELOAD header exceeds MTU --> do IP fragmentation
   -When RELOAD header does not exceed MTU --> do RELOAD fragmentation

Congestion control and hop-by-hop reliability of a message fragment
------------------

*Stop-and-wait
  -send a packet and wait for a response before transmitting next packet.
  -retransmit lost packets at RTO.
  -introduce gap of 10ms btw packet transmissions.

*AIMD-like
  -transmit packets as permitted by a congestion window.
  -No slow start, fast retransmit, or recovery.
  -always in congestion avoidance, at every loss, reduce window by half.
  -retransmit at RTO if permitted by congestion window.

*TFRC
  -TFRC for congestion control
  -retransmission at RTO intervals
  -needs careful consideration whether TFRC can be implemented using
   existing message parameters.

(The above methods require RTO estimation with some caveats. See Bruce's 
email:
http://www.ietf.org/mail-archive/web/p2psip/current/msg04697.html)

*Use TCP
  -use TCP if expecting fragmentation, otherwise use UDP
  -issue: TCP may not work behind some NATs for setting up
   direct connections, however:
   --UDP may also be blocked by firewalls--
   --and nodes behind restrictive NATs can act as clients.

-salman

---

From: Henning Schulzrinne <[email-masked]>
Date: Mon, 16 Mar 2009 17:32:28 -0400

Another related option: Use TCP-tunneled-over-UDP for those cases  
where "native" TCP fails. There are plenty of UDP tunneling protocols  
around to choose from, so the amount of stuff to be invented or  
standardized may be relatively small.

On Mar 16, 2009, at 3:36 PM, Salman Abdul Baset wrote:

> I have tried to summarize the solution space for addressing  
> fragmentation, congestion control and reliability issues when using  
> an unreliable transport. This includes the proposal by Bruce. I  
> think that the WG needs to contrast their complexity with the use of  
> a reliable transport (TCP), and consider whether to specify these  
> mechanisms in a separate document or the base document.
>
>
>
> Fragmentation
> -------------
>
> (The above methods require RTO estimation with some caveats. See  
> Bruce's email:

---

From: Bruce Lowekamp <[email-masked]>
Date: Tue, 17 Mar 2009 06:25:32 -0400

Salman,

Unfortunately, the conversation is dominated by the need to work in
the real Internet, where the dominant situation is that UDP will work
and TCP won't.

We do have the advantage that we don't have to match TCP in
performance, although the exact requirement will of course vary by the
particular deployment.

Also, a TCP overlay link will also need to estimate RTO to determine
when the link has failed.

Bruce

On Mon, Mar 16, 2009 at 3:36 PM, Salman Abdul Baset <[email-masked]> wrote:
> transport. This includes the proposal by Bruce. I think that the WG needs to
> contrast their complexity with the use of a reliable transport (TCP), and
> consider whether to specify these mechanisms in a separate document or the
> base document.
>
>
>
> Fragmentation
> -------------
>

---

From: Bruce Lowekamp <[email-masked]>
Date: Tue, 17 Mar 2009 06:26:32 -0400

Henning,

I agree.  My recollection is that TSV wasn't too fond of this idea the
last time it came up at an area meeting, so I wouldn't expect it to
happen quickly, but maybe I'm wrong.  Would certainly be an easy
drop-in if it were available.

Bruce

On Mon, Mar 16, 2009 at 5:32 PM, Henning Schulzrinne
<[email-masked]> wrote:
> Another related option: Use TCP-tunneled-over-UDP for those cases where
> "native" TCP fails. There are plenty of UDP tunneling protocols around to
> choose from, so the amount of stuff to be invented or standardized may be
> relatively small.
>

---

From: Henning Schulzrinne <[email-masked]>
Date: Tue, 17 Mar 2009 08:10:40 -0400

> the real Internet, where the dominant situation is that UDP will work

I'm curious: Is there data indicating the problem? I've heard of  
problems with *inbound* connections via NATs, but the likelihood that  
outbound TCP from behind a NAT doesn't work seems low, given that this  
would essentially kill all consumer applications, from shiny web 2.0  
to dusty IMAP.

Henning

---

From: Bruce Lowekamp <[email-masked]>
Date: Tue, 17 Mar 2009 22:36:19 -0400

You're right, I'm referring to inbound connections, which are
necessary to support peers behind NATs, as we're required to do.  One
could certainly set up an overlay  where NATed nodes cannot be peers,
and so I'm happy to say an overlay should be able to specify such a
configuration, but we can't restrict ourselves to that solution.

Bruce

On Tue, Mar 17, 2009 at 8:10 AM, Henning Schulzrinne
<[email-masked]> wrote:
> I'm curious: Is there data indicating the problem? I've heard of problems
> with *inbound* connections via NATs, but the likelihood that outbound TCP
> from behind a NAT doesn't work seems low, given that this would essentially
> kill all consumer applications, from shiny web 2.0 to dusty IMAP.
>
> Henning
>

---

From: Henning Schulzrinne <[email-masked]>
Date: Wed, 18 Mar 2009 08:17:47 -0400

True peers (not clients) behind NATs won't work unless they initiate  
the connection anyway, so I'm a bit confused by the model you have in  
mind.

On Mar 17, 2009, at 10:36 PM, Bruce Lowekamp wrote:

>> problems

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 18 Mar 2009 09:56:18 -0700

At Wed, 18 Mar 2009 08:17:47 -0400,
> the connection anyway, so I'm a bit confused by the model you have in  

I'm not Bruce, but the model *I* had in mind was that
you would use your existing connections to route rendezvous
messages through the overlay and then use ICE to set up the
connections, thus avoiding the "initiate" issue. Obviously
this in principle works for TCP, except that the future 
(and effectiveness) of ICE-TCP are uncertain at best.

-Ekr

---

From: Dean Willis <[email-masked]>
Date: Wed, 18 Mar 2009 14:12:54 -0500

On Mar 18, 2009, at 7:17 AM, Henning Schulzrinne wrote:

> the connection anyway, so I'm a bit confused by the model you have  
> in mind.
>

A signal comes over an existing connection, causing the peer to send  
UDP out to a node that can report the address/port number in use. This  
address/port set is exchanged with the other peer via the existing  
connection, then the peers contact each other directly using the  
discovered address/ports. Doesn't work for all NATs, but does for  
many. And we don't have a trick for doing that with TCP yet, although  
I'm working on one.

And if this doesn't work, we can fall back to using a relay.

Barring elimination of NATs, the next best trick would be to build ICE  
directly into the TCP stack. That would be interesting. But talk about  
a forklift upgrade! OTOH, it might be possible to do this in such a  
way that it is backward compatible with TCP; that is, a node using  
iced-TCP could talk to one using standard TCP. Additional behavior  
would be required in the NAT, but that's not entirely out of the  
question. More thought required to keep from reinventing RSIP.

--
Dean

---

From: Salman Abdul Baset <[email-masked]>
Date: Wed, 18 Mar 2009 16:32:44 -0400 (EDT)

On Wed, 18 Mar 2009, Dean Willis wrote:

>> True peers (not clients) behind NATs won't work unless they initiate the 
>> connection anyway, so I'm a bit confused by the model you have in mind.
>> 
>
> A signal comes over an existing connection, causing the peer to send UDP out 
> to a node that can report the address/port number in use. This address/port 
> set is exchanged with the other peer via the existing connection, then the 
> peers contact each other directly using the discovered address/ports. Doesn't 
> work for all NATs, but does for many. And we don't have a trick for doing 
> that with TCP yet, although I'm working on one.

A related question is what is the percentage of deployed NATs that
support direct TCP connection establishment using techniques such as 
Simultaneous-TCP-open?

According to "Characterization and Measurement of TCP Traversal through 
NATs and Firewalls", (IMC'05), 88% of the deployed NATs support direct TCP 
connection, and 100% for certain common types of NATs. It will be 
interesting to see a more recent data on this.

When NATs are cascaded, the direct TCP connections are a problem as 
hairpinning support is needed. However, this problem also occurs for 
UDP (Section 4, RFC 5128).

The reliability and congestion control discussion for RELOAD revolves 
around the notion that direct connection establishment using TCP is orders 
of magnitude worse than UDP. It is not clear to me if this is the case, 
unless there is data indicating otherwise. It is also not clear to me 
whether building a TCP-over-UDP solution will solve the problem of direct 
connection establishment, as direct 'connection establishment' over 
UDP does not always work.

-salman

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 18 Mar 2009 14:12:47 -0700

At Wed, 18 Mar 2009 16:32:44 -0400 (EDT),
Salman Abdul Baset wrote:
> of magnitude worse than UDP.

No, it does not. If UDP was 99% and TCP was 50% (<< 1 order),
then this would pretty clearly require UDP support.

-Ekr

---

From: Salman Abdul Baset <[email-masked]>
Date: Wed, 18 Mar 2009 17:19:25 -0400 (EDT)

> then this would pretty clearly require UDP support.

Sure. This is why it is helpful to have data indicating the problem. The 
paper I cited indicates that direct TCP connection can be established for 
88 percent of deployed NATs and 100% for common NAT types.

-s

---

From: Bruce Lowekamp <[email-masked]>
Date: Wed, 18 Mar 2009 22:58:51 -0400

That paper in particular, and the reasons UDP connections are more
reliably formed than TCP, have been discussed numerous times in
MMUSIC, and I really don't think we should be repeating the whole
conversation here.  But the summary is that it's not nearly as
universal a solution as indicated in that paper.

Bruce

On Wed, Mar 18, 2009 at 5:19 PM, Salman  Abdul Baset
<[email-masked]> wrote:
> paper I cited indicates that direct TCP connection can be established for 88
> percent of deployed NATs and 100% for common NAT types.
>
> -s

---

From: Salman Abdul Baset <[email-masked]>
Date: Thu, 19 Mar 2009 00:13:28 -0400 (EDT)

> universal a solution as indicated in that paper.

Sure. I have already mentioned that this is a IMC'05 paper and more 
recent data, if available, is helpful and needed.

There are at least four solutions to the hop-by-hop reliability problem:

(1) Clients
Nodes behind TCP *un*friendly NATs can always act as clients and establish a 
TCP connection(s) with reachable node(s). The reachable nodes can be behind 
friendly NATs or they can have a public IP address.

(2) Full peer but use relay peer(s)
A node participates as a peer. It establishes TCP connection with 
reachable peers, which inturn establish a TCP connection with the nodes' 
connection table entries.

(3) Full peer with techniques for direct TCP connection establishment
A node participates as a peer and uses TCP traversal techniques for 
establishing direct connection (including Dean's upcoming ones:)

(4) Full peer with TCP-over-UDP
Since TCP traversal may fail, design/reuse a reliable congestion control 
protocol over UDP.

Note that:
(1) and (2) always work.

(3) and (4) do not work well behind cascaded NATs. 
(4) fails behind UDP-blocking firewalls.

(4) is feasible over (3) since UDP has a better chance of connection 
establishment when NATs are not cascaded. However, UDP blocking firewalls 
need to be factored in this feasible discussion. Again, any recent data is 
helpful.

For (4), the TCP-over-UDP protocol needs to be well-designed and 
well-implemented. Otherwise, peers doing TCP-over-UDP may be the weakest 
link in the routing chain. Approaches which recover every loss using 
timeout may not be the most feasible ones.

-salman

---

From: Bruce Lowekamp <[email-masked]>
Date: Wed, 25 Mar 2009 07:48:18 -0400

Salman,

Based on your list, I'm going to assume you agree with the current
proposal.  RELOAD supports (and prefers) a TCP overlay link protocol,
and it offers a UDP-based protocol when that doesn't work.  I'd fully
support a simple use RFCXXXX for a TCP-over-UDP protocol, but since
there isn't one, we have a goal of something that should work, even if
it doesn't reach "ideal" (TCP-like) performance.  If you believe more
needs to be done to specify a real TCP over UDP, I fully support you
advancing that in TSV.

Bruce

On Thu, Mar 19, 2009 at 12:13 AM, Salman  Abdul Baset
<[email-masked]> wrote:
> Sure. I have already mentioned that this is a IMC'05 paper and more recent
> data, if available, is helpful and needed.
>
> A node participates as a peer. It establishes TCP connection with reachable
> peers, which inturn establish a TCP connection with the nodes' connection
> table entries.
>
> (3) and (4) do not work well behind cascaded NATs. (4) fails behind
> UDP-blocking firewalls.
>
> link in the routing chain. Approaches which recover every loss using timeout
> may not be the most feasible ones.
>
>
> -salman
>

---

From: Salman Abdul Baset <[email-masked]>
Date: Wed, 25 Mar 2009 11:23:13 -0400 (EDT)

There are two proposals, one in the draft and one in your email. The 
general assumption behind these proposals is that a node participates in 
the overlay as a full peer and uses these solutions for achieving hop-by-hop 
reliability.

I do not agree with the proposals in the draft or in your email. For 
simplicity, lets refer to these solutions as Lesser-reliability-over-UDP 
(LROU). The reasons, some of which I have stated in the earlier posts, are:

1) LSROU or even TCP-over-UDP is not a universal solution. It is 
well-known that TURN server use is necessary for UDP, especially when 
using cascaded NATs, or NATs with end-point dependent filtering.

2) Base draft has tried to incorporate solutions that work in all 
scenarios. This is why we have recursive routing. LSROU does not work in 
all scenarios. A combination of LSROU and TCP also does not work in all 
scenarios. Bottom line: relaying is unavoidable. Clearly, lesser the 
relaying the better, and LROU is considered to be one way. However, see 
(3) and (5).

3) TCP inbound connections through NAT are considered more problematic 
than UDP. The available data I am aware of (Characterizing paper, IMC'05) 
suggests that for 100% of common type of deployed NATs, it is possible to 
establish direct TCP connections. You noted that this is not as universal 
as discussed in the paper, but how much less? Can we put a number? Do we 
have data?

4) We cannot make any assumptions on the size of the data sent over LSROU.

5) LSROU only relies on *timeouts* to recover each loss. TCP recovers loss 
using *TDACK* and *timeout*. A node participating in the overlay as a full 
peer that uses LSROU to recover losses using *timeouts* is the weakest link 
in the routing chain.

5) Lets suppose that TCP inbound connections were much more problematic 
than UDP and so a lot of peers will run LSROU. Imagine that the only way 
these peers running LSROU recover losses is using timeouts. Can we 
imagine the poor routing performance of this system? Shall we standardize 
it?

6) The present text in the draft uses TFRC-SP. TFRC-SP mandates a gap of 
10ms between each transmission. Imagine 4 packets traversing 5 hops, and 
each transmission delayed by 10ms. Even if there are no losses, the last 
packet will leave the fourth hop after 120ms.

My proposal (a rough text) is as follows.

"RELOAD uses TCP for achieving hop-by-hop reliability and relies on 
existing techniques to solve inbound TCP connection problem. When direct 
connection fails, the node (a) only participates as a client or (b) 
particpates as a peer and uses a TCP TURN server to achieve a 1-hop 
connection with its connection table entries.

Alternatively, a peer can use a TCP-over-UDP protocol to establish 
direct connections and to achieve reliability. However, we do not specify 
such a protocol."

-s

---

From: Salman Abdul Baset <[email-masked]>
Date: Wed, 25 Mar 2009 21:13:11 -0400 (EDT)

It is necessary to clarify the scope of the problems that are being 
addressed and to precisly define what 'diagnostics' mean. Currently, it is 
very open ended and includes:

-routing diagnostics
-detecting malfunctioning or badly behaving peers
-checking the health of overlay

Overlay maintenance is central to any p2p system. How is that different 
from diagnostics?

The suggested solution incorporates two new methods. I think we need a 
bit more clarity on what is that existing methods cannot achieve, for 
which new methods are required. As an example, one can easily implement 
Path_Track using RouteQuery and [Node]Fetch.

What is indeed required is a mechanism to obtain the state 
[routing/storage] of a node. This can be done using NodeFetch and may also 
be accomplished using Fetch.

-salman

---

From: Bruce Lowekamp <[email-masked]>
Date: Wed, 25 Mar 2009 22:16:31 -0400

On Wed, Mar 25, 2009 at 11:23 AM, Salman Abdul Baset
<[email-masked]> wrote:

> "RELOAD uses TCP for achieving hop-by-hop reliability and relies on existing
> techniques to solve inbound TCP connection problem. When direct connection
> fails, the node (a) only participates as a client or (b) particpates as a
> peer and uses a TCP TURN server to achieve a 1-hop connection with its
> Alternatively, a peer can use a TCP-over-UDP protocol to establish direct
> connections and to achieve reliability. However, we do not specify such a
> protocol."
>

Salman,

Simply refusing to admit that use cases exist where TCP can't be used
between all peers does not make them go away.

Bruce

>>> recent
>>> reachable

---

From: Salman Abdul Baset <[email-masked]>
Date: Thu, 26 Mar 2009 05:36:06 -0400 (EDT)

> Salman

I think I have been pretty clear that there are scenarios where TCP cannot 
be used; however, it is still an open question whether they are dominant 
ones, and if they are, an adhoc approach with poor performance is not 
the answer. Further, direct connections for both UDP and TCP do not work 
for cascaded NATs.

I have earlier outlined solutions for scenarios where TCP cannot be used 
(see 1-3 below) that do not require a TCP-over-UDP or a similar approach. 
They are a full peer with connections established over TCP through a relay 
peer, developing techniques for direct TCP connection establishment (in 
BEHAVE WG), or downgrading a peer to a client.

-salman

---

From: Bruce Lowekamp <[email-masked]>
Date: Thu, 26 Mar 2009 14:05:09 -0400

On Thu, Mar 26, 2009 at 5:36 AM, Salman  Abdul Baset
<[email-masked]> wrote:
> ones, and if they are, an adhoc approach with poor performance is not the
> answer. Further, direct connections for both UDP and TCP do not work for
> cascaded NATs.
>

- There are still people who want to run UDP between peers.  Yes there
are other options for some of those scenarios, but not all. Your
solutions simply don't address all of the problem space.  Feel free to
submit a draft proposing to limit the problem space the protocol is
trying to solve.

- You have not demonstrated that any of the proposed UDP protocols
have performance inadequate to the requirements of the scenarios in
which they are likely to be needed.  Sure they're not up to TCP's
performance.  That's not the goal.

- I don't understand why you keep bringing up cascaded NATs.  Yes,
it's possible to come up with a NAT/Firewall configuration that will
block any given solution.  The point is not that there may exist
systems where a particular solution won't work, it's trying to develop
a solution that solves the vast majority of common cases.

Bruce

---

From: Salman Abdul Baset <[email-masked]>
Date: Thu, 26 Mar 2009 16:10:52 -0400 (EDT)

> submit a draft proposing to limit the problem space the protocol is

Perhaps, people who *only* want to run UDP between peers should submit a 
seperate draft. It is not something that should be in the base draft when 
there are alternate solutions.

It is incorrect to say that my solutions don't address these scenarios. 
Establishing TCP connections through mutually reachable peers always work. 
Downgrading a node to a client, and establishing a TCP connection with a 
reachable peer always work. Again, please see (1) and (2) below. Also, 
people are working on techniques for establishing direct TCP connection.

> performance.  That's not the goal.

I have said it repeatedly that the proposed UDP protocols only recover 
losses using *timeouts*. It is well known that recovering losses using 
timeouts is a big performance hit. Any TSV person should say this.

> a solution that solves the vast majority of common cases.

I am curious if you have data indicating that for common cases, TCP 
connections don't work and UDP do? You don't agree with the assertions in 
the 'Characterizing IMC'05' paper and that's fine. But can you point to 
the latest data?

--

I am not religiously against running UDP between peers :). However, based 
on reasons stated earlier, I think that RELOAD base draft of the P2PSIP WG 
is the *not* right place to insert a reliable congestion control protocol. 
It is easy to get these protocols wrong than right. We should not abandon 
well designed TCP stacks so easily.

As a practical insight, Skype application will not connect to the Skype 
network if it cannot establish a TCP connection with a Skype super node.

For those who want to run UDP, I totally agree with your idea of use 
RFC-XXXX for a TCP-over-UDP protocol.

I want to keep our focus on the issues of P2PSIP protocol such as 
configuration, security, and overlay maintenance.

Regards,
Salman

---

From: Henning Schulzrinne <[email-masked]>
Date: Thu, 26 Mar 2009 21:31:33 -0400

For what (little) it's worth, there are existing implementation of TCP- 
over-UDP. I found

http://thebends.org/~allen/utunnel/
http://www.jankratochvil.net/project/tcpoverudp/
http://www.vergenet.net/linux/iproxy/iproxy_paper/stuff/iproxy_paper.pdf
http://code.google.com/p/tcpoverudp/

So we have several implementations *before* an Internet draft :-)

Henning

On Mar 26, 2009, at 4:10 PM, Salman Abdul Baset wrote:
>
> I am not religiously against running UDP between peers :). However,  
> based on reasons stated earlier, I think that RELOAD base draft of  
> the P2PSIP WG is the *not* right place to insert a reliable  
> congestion control protocol. It is easy to get these protocols wrong  
> than right. We should not abandon well designed TCP stacks so easily.
>
> As a practical insight, Skype application will not connect to the  
> Skype network if it cannot establish a TCP connection with a Skype  
> super node.
>

---

From: Bruce Lowekamp <[email-masked]>
Date: Thu, 26 Mar 2009 22:49:35 -0400

Yeah, my recollection from the last time this was discussed in TSV
gives me little hope that one would be standardized, but I would like
to discover I'm wrong here.

Bruce

On Thu, Mar 26, 2009 at 9:31 PM, Henning Schulzrinne
<[email-masked]> wrote:
> For what (little) it's worth, there are existing implementation of
> TCP-over-UDP. I found
>

---

From: Bruce Lowekamp <[email-masked]>
Date: Thu, 26 Mar 2009 23:25:48 -0400

> people are working on techniques for establishing direct TCP connection.

Your alternate solution is an assumption that the overlay will contain
enough TCP open-access nodes that are able to identify themselves as
open-access nodes and willing to bear the burden of their role on
behalf of all the other peers.   What I've seen is that UDP actually
works, and TCP doesn't.

> timeouts is a big performance hit. Any TSV person should say this.

This is a bit of an oversimplification.

- it's not a stream based protocol.  So a timeout of one fragment
doesn't have any affect on the others, like it does in TCP
- Having timeout based retransmission was purely a way of simplifying
the protocols to be easier to implement (correctly)
- Once again, the goal isn't to achieve equal performance to TCP.  The
goal is to provide sufficient performance and not destroy the Internet
- If you read the TFRC spec, it includes dupack calculation, which can
be used to determine loss.  The receiver algorithm was simplified a
little bit to make this impossible, and I see the value of that
simplification as more important than the lost performance, given that
this isn't a stream-based protocol in the first place.

The difference between an ideal overlay link protocol and a
stream-based protocol (such as how the TFRC version only retransmits
an individual fragment twice) is actually an important point to keep
in mind, and probably means that TCP over UDP is not actually the
ideal protocol.  (But I don't necessarily believe it would be
worthwhile to work out an appropriate spec to that level of detail.  I
think it's more important to have easily implementable protocols that
work, and would prefer a TCP over UDP that can be included by
reference.)

> the 'Characterizing IMC'05' paper and that's fine. But can you point to the
> latest data?
>

Once again, I don't believe it's worth rehashing years of conversation
in MMUSIC here.  But if nothing else, observe that ICE-UDP is a lot
further along (finished) than ICE-TCP (trying to get restarted).

Bruce

> --
>
> I am not religiously against running UDP between peers :). However, based on
> reasons stated earlier, I think that RELOAD base draft of the P2PSIP WG is
> the *not* right place to insert a reliable congestion control protocol. It
> is easy to get these protocols wrong than right. We should not abandon well
> designed TCP stacks so easily.
>
>>>>>>> need to be factored in this feasible discussion. Again, any recent
>>>>>>> data
>>>>>>> is
>>>>>>> helpful.
>>>>>>>
>>>>>>>

---

From: Salman Abdul Baset <[email-masked]>
Date: Thu, 26 Mar 2009 23:53:48 -0400 (EDT)

> behalf of all the other peers.   What I've seen is that UDP actually

Skype works. It has enough nodes that can provide relay services.

There are papers which suggest that a machine can handle thousands of 
concurrent TCP connections.

> doesn't have any affect on the others, like it does in TCP

You are missing inorder delivery here. Unless the lost fragment is 
retransmitted and received, all the other segments in the receive 
buffer are useless.

I think the following questions should be discussed in the WG meeting.

1) Is designing a reliable congestion protocol within scope of P2PSIP WG?
2) If yes,
  a) shall it be specified in the base document?
  b) what should be its performance if a large number of peers were to run it?
  c) what is the impact on routing performance?

regards,
salman

---

From: Bruce Lowekamp <[email-masked]>
Date: Fri, 27 Mar 2009 06:18:44 -0400

> Skype works. It has enough nodes that can provide relay services.

Once again, I'm not saying your scenario doesn't exist. I'm just
saying that there are other scenarios.

> concurrent TCP connections.

The ability of a machine to handle thousands of mostly idle
connections is not really relevant to whether people would participate
in an overlay where they wind up consuming half of their broadband
link while idle (for example).

> retransmitted and received, all the other segments in the receive buffer are
> useless.
>

No, I'm not missing it, I'm deliberately excluding it.  That's not a
service the Internet guarantees, and the complexities required to
guarantee it on an overlay network are too high.

>  c) what is the impact on routing performance?

It's a semi-reliable congestion control protocol, but yes, that's a
perfectly good topic for the wg to consider.  However, so far I'm not
aware of anyone but you who believes we should exclude UDP from the
protocol.

Bruce

>>> on
>>>>>>>>> TCP connection(s) with reachable node(s). The reachable nodes can
>>>>>>>>> be
>>>>>>>>> behind

---

From: Salman Abdul Baset <[email-masked]>
Date: Fri, 27 Mar 2009 08:41:04 -0400 (EDT)

> saying that there are other scenarios.

Sure there are other scenarios, but the justification for including your 
TCP-over-UDP solutions in the base protocol has to be based on solid data, 
whether they are the *only* viable option, whether they have any 
performance issues, and whether P2PSIP WG is the right place for them.

You have agreed in the earlier posts that there are scenarios where direct 
connections are not possible. Maybe, RELOAD should not be run in those 
scenarios, right?

> guarantee it on an overlay network are too high.

Unless a packet is deemed loss using a *timeout*, and retransmitted, and 
received at the receive buffer, all other packets are useless. Isn't this 
a big performance hit?

> aware of anyone but you who believes we should exclude UDP from the

It is a jump in the thought to say that I am excluding UDP. I am not. UDP 
is perfectly suitable for messages that do not exceed MTU such as 
keep-alives.

I will let WG discuss these questions :)

-salman

---

From: Bruce Lowekamp <[email-masked]>
Date: Fri, 27 Mar 2009 09:35:28 -0400

On Fri, Mar 27, 2009 at 8:41 AM, Salman  Abdul Baset
<[email-masked]> wrote:
> whether they are the *only* viable option, whether they have any performance
> issues, and whether P2PSIP WG is the right place for them.
>

The charter says:

"The working group will assume that NATs and firewalls exist in the
Internet, and will ensure that the protocols produced work in their
presence as much as possible."

I interpret that to mean that we should support UDP, and as long as we
do so within the framework of RFC5405, which specifies guidelines for
congestion control, reliability, etc., we are doing what our charter
and usage scenarios require in compatibility with TSV's current view
on the requirements.

> received at the receive buffer, all other packets are useless. Isn't this a
> big performance hit?
>

Depends on how many fragments the typical message has, and how long
the reassembly buffer is preserved on the receiver to receive the
retransmission.  Obviously this was a major problem for early poor ATM
implementations.

Going back a bit, my initial argument was that each hop should do
reassembly.  Numerous other people on the mailing list argued that
this was too expensive, and that we should adopt a simpler approach.
I tried to balance performance and simplicity in the more recent
email.   But there are a lot of different perspectives on what the
most important features to be optimized are.  I certainly consider
whether such overlay link protocols must include behaviors such as
dupack loss detection and fragment/message dropping to be open issues.

> It is a jump in the thought to say that I am excluding UDP. I am not. UDP is
> perfectly suitable for messages that do not exceed MTU such as keep-alives.
>

keep-alives have to be run over the same channel as the main messages.
 (keep-alives in the NAT/firewall maintenance sense, you're right that
a peer liveness check could run in a different flow.)

Bruce

---

From: songhaibin 64081 <[email-masked]>
Date: Sat, 28 Mar 2009 01:39:25 +0800

Hi Salman,

> -checking the health of overlay

Yes, the draft now has the consideration of routing diagnostics and detecting malfunctioning peers. However, checking the health of the overlay has not been considered in the draft at present, although we have some thought on it.
 
> Overlay maintenance is central to any p2p system. How is that 

I am not quite sure about that. But I think the diagnostic information can be used for overlay maintenance. They are a little different.

> be accomplished using Fetch.

The draft now is lack of consideration for storage state. It is a good suggestion to add that as one type of diagnostic information. It is very helpful in the enviroment where the peer storage is limited or hot spot. 

Haibin