Explore Posterous

Best music tracker, Period.

Some standout points:

• Music has become social
• Unheard music is unbought music - enter a use for P2P and streaming
• 75% prefer downloading

From Wikipedia, the free encyclopedia

  (Redirected from Nagle algorithm)

Jump to: navigation, search

Nagle's algorithm, named after John Nagle, is a means of improving the efficiency of TCP/IP networks by reducing the number of packets that need to be sent over the network.

Nagle's document, Congestion Control in IP/TCP Internetworks (RFC896) describes what he called the 'small packet problem', where an application repeatedly emits data in small chunks, frequently only 1 byte in size. Since TCP packets have a 40 byte header (20 bytes for TCP, 20 bytes for IPv4), this results in a 41 byte packet for 1 byte of useful information, a huge overhead. This situation often occurs in Telnet sessions, where most keypresses generate a single byte of data which is transmitted immediately. Worse, over slow links, many such packets can be in transit at the same time, potentially leading to congestion collapse.

Nagle's algorithm works by coalescing a number of small outgoing messages, and sending them all at once. Specifically, as long as there is a sent packet for which the sender has received no acknowledgment, the sender should keep buffering its output until it has a full packet's worth of output, so that output can be sent all at once.

Contents [hide] 1 Algorithm 2 Interactions with real-time systems 3 References 4 External links

[edit] Algorithm

if there is new data to send
  if the window size >= MSS and available data is >= MSS
    send complete MSS segment now
  else
    if there is unconfirmed data still in the pipe
      enqueue data in the buffer until an acknowledge is received
    else
      send data immediately
    end if
  end if
end if

where MSS = maximum segment size.

This algorithm interacts badly with TCP delayed acknowledgments, a feature introduced into TCP at roughly the same time in the early 1980s, but by a different group. With both algorithms enabled, applications which do two successive writes to a TCP connection, followed by a read which will not be fulfilled until after the data from the second write has reached the destination, experience a constant delay of up to 500 milliseconds, the "ACK delay". For this reason, TCP implementations usually provide applications with an interface to disable the Nagle algorithm. This is typically called the TCP_NODELAY option. It is however not recommended to disable this. A solution recommended by Nagle himself, is to keep from sending small single writes and buffer up application writes then send.

"The user-level solution is to avoid write-write-read sequences on sockets. write-read-write-read is fine. write-write-write is fine. But write-write-read is a killer. So, if you can, buffer up your little writes to TCP and send them all at once. Using the standard UNIX I/O package and flushing write before each read usually works."^[1]

The tinygram problem and silly window syndrome are sometimes confused. The tinygram problem occurs when the window is almost empty. Silly window syndrome occurs when the window is almost full.

[edit] Interactions with real-time systems

Applications that expect real time responses can react poorly with Nagle's algorithm. Applications such as networked multiplayer video games expect that actions in the game are sent immediately, while the algorithm purposefully delays transmission, increasing bandwidth at the expense of latency. For this reason applications with low-bandwidth time-sensitive transmissions typically use TCP_NODELAY to bypass the Nagle delay.^[2]

[edit] References

• Larry L. Peterson, Bruce S. Davie (2007). Computer Networks: A Systems Approach (4 ed.). p. 402–403. ISBN 0123740134. http://books.google.com/books?id=fknMX18T40cC&pg=PA402&dq=Nagle%27s+algorithm#PPA402,M1. 

[edit] External links

• Nagle's algorithm
• TCP Performance problems caused by interaction between Nagle's Algorithm and Delayed ACK

1. ^ http://developers.slashdot.org/comments.pl?sid=174457&threshold=1&commentsort=0&mode=thread&cid=14515105
2. ^ https://bugs.freedesktop.org/show_bug.cgi?id=17868

Retrieved from "http://en.wikipedia.org/wiki/Nagle%27s_algorithm"

Categories: Networking algorithms | TCP/IP

From AzureusWiki

Jump to: navigation, search

Note: This is the Message Stream Encryption specification, see Avoid traffic shaping for Azureus specific setup instructions and documentation.

[edit]

Protocol Objectives

The following encapsulation protocol is designed to provide a completely random-looking header and (optionally) payload to avoid passive protocol identification and traffic shaping. When it is used with the stronger encryption mode (RC4) it also provides reasonable security for the encapsulated content against passive eavesdroppers.

It is a 3-way handshake where the initiating client can directly append its payload after his 2nd step (which globally is the 3rd). The responding client has to send one step (globally the 2nd) of the handshake and then wait until the initiating client has completed its 2nd step to send payload.

To achieve complete randomness from the first byte on the protocol uses a D-H key exchange which uses large random Integers by design. The 2nd phase - the payload encryption negotiation - is itself encrypted and thus approximately random too. To avoid simple length-pattern detections various paddings have been added to each phase.

This encapsulation protocol is independent of the encapsulated content, but is intended to be used with the BitTorrent Protocol, the Azureus messaging protocol (running ontop of the former) or the Enhanced messaging protocol in the near future. Since there are no guarantees about the content additional protocol detection is mandatory when the first payload arrives.

The 2 different payload encryption methods plaintext transmission and RC4 provide a different degree of protocol obfuscation, security and speed. Where the plaintext mode only provides basic anti-shaping obscurity, no security and low CPU usage the RC4 encryption obfuscates the entire stream and not only the header and adds some cryptographic security at the price of spent CPU cycles.

It is worth restating the aim - that of message stream obfuscation by the application of fairly simple cryptographic techniques, not a full blown transport level security mechanism like SSL. In the future, if the latter is required, this will be addressed by a separate activity.

Contents [hide] 1 Protocol Objectives 2 Message Stream Encryption (aka PHE) format specification 3 Implementation Notes for BitTorrent Clients 4 Tracker Extension 5 Notes about the current Azureus implementation 6 See also

 

[edit]

Message Stream Encryption (aka PHE) format specification

Version 1.0
As of now the specification is frozen. Clarifications or spelling fixes may still occur.

 

######################################################
### ----- Message Stream Encryption protocol ----- ###
### specification by Ludde/uau/The_8472/Parg/Nolar ###
######################################################

The following protocol describes a transparent wrapper for bidirectional
data streams (e.g. TCP transports) that prevents passive eavesdroping
and thus protocol or content identification.

It is also designed to provide limited protection against active MITM attacks
and portscanning by requiring a weak shared secret to complete the handshake.
You should note that the major design goal was payload and protocol obfuscation,
not peer authentication and data integrity verification. Thus it does not offer
protection against adversaries which already know the necessary data to establish
connections (that is IP/Port/Shared Secret/Payload protocol).

To minimize the load on systems that employ this protocol fast cryptographic
methods have been chosen over maximum-security algorithms.


----------------
- Declarations -
----------------

The entire handshake is in big-endian.
The crypto handshake is transparent to the next upper protocol,
thus the payload endianness doesn't matter.


A is the initiator of the underlying transport (e.g. a TCP connection)
B is the receiver

##### DH Parameters

Prime P is a 768 bit safe prime, "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A63A36210000000000090563"
Generator G is "2"

Xa and Xb are a variable size random integers. 
They are the private key for each side and have to be discarded after
the DH handshake is done. Minimum length is 128 bit. Anything beyond 180 bit
is not believed to add any further security and only increases the necessary
calculation time. You should use a length of 160bits whenever possible, lower
values may be used when CPU time is scarce.

Pubkey of A: Ya = (G^Xa) mod P
Pubkey of B: Yb = (G^Xb) mod P

DH secret: S = (Ya^Xb) mod P = (Yb^Xa) mod P

P, S, Ya and Yb are 768bits long

##### Constants/Variables


PadA, PadB: Random data with a random length of 0 to 512 bytes each

PadC, PadD: Arbitrary data with a length of 0 to 512 bytes, can be
used to extend the crypto handshake in future versions.
Current implementations may choose to set them to 0-length.
For padding-only usage in the current version they should be zeroed.


VC is a verification constant that is used to verify whether the other
side knows S and SKEY and thus defeats replay attacks of the SKEY hash.
As of this version VC is a String of 8 bytes set to 0x00.


crypto_provide and crypto_select are a 32bit bitfields.
As of now 0x01 means plaintext, 0x02 means RC4. (see Functions)
The remaining bits are reserved for future use.

The initiating peer A should provide all methods he supports in the bitfield,
but he may choose only to provide higher encryption levels e.g. if  plaintext
isn't sufficient for it's security needs.
The responding peer B should set a bit corresponding to the single method
which he selected from the provided ones.

Bits with an unknown meaning in crypto_provide and crypto_select
should be ignored as they might be used in future versions.





SKEY = Stream Identifier/Shared secret used to drop connections early if we
don't have a matching stream. It's additionally used to harden the protocol
against MITM attacks and portscanning.
Protocols w/o unique stream properties may use a constant.
 Note: For BitTorrent, the SKEY should be the torrent info hash.


IA = initial payload data from A
may be 0-sized if you want to wait for the encryption negotation.

Peer A may buffer up to 65535 bytes before or during the DH handshake to append
it to the 3rd step. IA is considered as atomic and thus an implementation may
not expect that anything is handed to the upper layer before IA is completely
transmitted. Thus there must be no blocking operations within IA.

Note, Example for Bittorrent:
 After \19Bittorrent protocol + the BT handshake a block occurs since A waits
 for B to send his handshake before A continues to send his bitfield,
 thus IA can only include the prefix + the bt handshake but not the bitfield


###### Functions

len(X) specifies the length of X in 2 bytes.
Thus the maximum length that can be specified is 65535 bytes, this is
important for the IA block.


ENCRYPT() is RC4, that uses one of the following keys to send data:
"HASH('keyA', S, SKEY)" if you're A
"HASH('keyB', S, SKEY)" if you're B
The first 1024 bytes of the RC4 output are discarded.
consecutive calls to ENCRYPT() by one side continue the encryption
stream (no reinitialization, no keychange). They are only used to distinguish
semantically seperate content. 


ENCRYPT2() is the negotiated crypto method.
Current options are:
 0x01 Plaintext. After the specified length (see IA/IB) each side sends unencrypted payload
 0x02 RC4-160. The ENCRYPT() RC4 encoding is continued (no reinitialization, no keychange)


HASH() is SHA1 binary output (20 bytes)


###### The handshake "packet" format


The handshake is seperated into 5 blocking steps.

1 A->B: Diffie Hellman Ya, PadA
2 B->A: Diffie Hellman Yb, PadB
3 A->B: HASH('req1', S), HASH('req2', SKEY) xor HASH('req3', S), ENCRYPT(VC, crypto_provide, len(PadC), PadC, len(IA)), ENCRYPT(IA)
4 B->A: ENCRYPT(VC, crypto_select, len(padD), padD), ENCRYPT2(Payload Stream)
5 A->B: ENCRYPT2(Payload Stream)


Since the length of PadA and PadB are unknown
B will be able to resynchronize on HASH('req1', S)
A will be able to resynchronize on ENCRYPT(VC)


##### Optional early termination conditions
(should verified before the indicated step is started).

If a fail-fast behavior is prefered the following conditions can be used to
disconnect the peer immediately. If less recognizable patterns are preferred
a peer may wait and disconnect at a later point. If any of these conditions
are met the handshake can be considered as invalid.

2 (termination by B)
if A sent less than 96 Bytes within 30 seconds
if A sent more than 608 bytes 

3 (termination by A)
if B sent less than 96 Bytes within 30 seconds
if B sent more than 608 bytes

4 (termination by B)
if A didn't send the correct S hash within 628 bytes after the connection start (synchronisation point)
if A didn't send a supported SKEY hash after the S hash
if VC can't be decoded correctly after the SKEY hash
if none of the crypto_provide options are supported or the bitfield is zeroed
from here on it's up to the next protocol layer to terminate the connection

5 (termination by A)
if VC can't be decoded correctly within 616 bytes after the connection start (synchronisation point)
if the selected crypto method wasn't provided
from here on it's up to the next protocol layer to terminate the connection

[edit]

Implementation Notes for BitTorrent Clients

Since not all BT clients will support this protocol there are 3 possible modes of operation:

1. Support incoming connections with the Obfuscation Header and legacy BT headers but always try establish classic BT streams for outgoing connections
   This method ensures compatibility but only allows incoming obfuscated connections from traffic-shaped peers, obfuscated connections are never established to them, leading to a similar situation as if the shaped client was firewalled or NATed.
2. Support incoming connections for both protocols but try to establish connections with the Obfuscation Header first and retry with BT headers if that fails
   Compatibility is still ensured and allows obfuscated connections to shaped peers but might not be suitable for shaped peers and requires reconnect attempts when an obfuscated handshake fails for any reason.
3. Only support obfuscated streams and treat any incoming connection like a DH key exchange attempt.
   This method doesn't provide backwards compatibility but ensures obfuscation. The CPU load can still be adjusted by choosing and providing different encryption methods

Any peer A in mode #1 or #2 should avoid unneccessary non-crypto connections to a peer B that uses crypto-only (mode #3) whenever possible.

 

[edit]

Tracker Extension

A client may append the following parameters to a HTTP GET:

• supportcrypto=1 which means a peer can create and recieve crypto connections
• requirecrypto=1 which means a peer only accepts/creates crypto connections
• cryptoport=X in combination with port=0 which tells the tracker the port X on which the client is listening on as usual, but prevents the tracker from handing out a valid IP/Port combination if he doesn't support the crypto extension. This is only valid in combination with requirecrypto=1. cryptoport is not mandatory, a client may choose to use the port parameter as usual if it accepts legacy connections as a fallback measure.

A tracker response when neither flag is set: The tracker will return IPs/Ports as usual but omit peers that signaled requirecrypto

A tracker response when the supportcrypto flag is set: In addition to the normal peers list (or string in the compact=1 case) an additional crypto_flags string which contains a bytearray in the same order as the peers list is sent. 1 means the corresponding peer requires crypto connections 0 means the peer supports and prefers classic BT

A tracker response when the requirecrypto flag is set: In addition to the normal peers list (or string in the compact=1 case) an additional crypto_flags string which contains a bytearray in the same order as the peers list is sent. 1 means the corresponding peer requires crypto connections 0 means the peer supports and prefers classic BT. The tracker should try to achieve the numwant limit with peers that flagged requirecrypto or supportcrypto first and only add non-supporting peers if no others are available.

Azureus supports this from 2403 B55+.

[edit]

Notes about the current Azureus implementation

Azureus tries to avoid unnecessary non-crypto connections through obfuscation-header aware Peer Exchanges, advanced messaging handshakes and Distributed tracker announces. Peer A tells its preferred connection mode in the handshake to peer B and then B adds additional flags to the PEX messages when it propagates A's address/port. This does not work in combination with Secure Torrents since they disable PEX and the DHT.

Azureus currently allows its users either to specify fallback support for incoming and outgoing connections seperately when the encryption is enabled or passive support only instead. Specified encryption methods aren't preferences but minimum requirements, for both incoming and outgoing connections, i.e. if a peer doesn't support the minimum (or possibly higher levels in the future) then the connection will can't be established. And Azureus will only offer minimum or higher level methods.

[edit]

See also

• Avoid traffic shaping
• Bad ISPs
• Wikipedia Article

Retrieved from "http://wiki.vuze.com/index.php/Message_Stream_Encryption"

Category: Technical Information

消息流加密协议的规范，对研究BitTorrent客户端加密大有裨益。