Evan has disappeared so I have had to review zidel's branch. Here is my summary
and thoughts on what needs to be fixed, what needs to be done, etc. Hopefully
Google will let me fill in the evaluation form for zidel and thus zidel
continue with this work; this is good stuff which will make a significant
difference once completed and debugged.
zidel/packetFormat branch reviewed up to
bc67c3e4370ef584c58166cc4f6d326030dc83f2
MAJOR REMAINING CHALLENGES AFAICS:
- How to make message ID re-use safe, or how to not re-use message ID's and
still not use unreasonable numbers of bytes.
- Memory DoS protection. May be related to the old debate about sender
initiated vs recipient initiated.
- Seriously consider only allowing 2 bytes for length for messages; if allow 3,
set an arbitrary maximum.
- Acceptable length of an HMAC.
- Implement an IV based on CTR mode (i.e. encrypt the packet number) using a
separate key derived during key setup (we will need several: one for each
direction, one for the IV, and one for the HMAC - we will need to use a proper
HMAC; JFK gives a very simple procedure for deriving them, hash the generated
key with a constant).
- CPU DoS: Predict the next N encrypted seqno's and watch for them.
- Block transfers - eventually, after we don't need to worry too much about
back compatibility; translating from one form of block transfer to another
isn't worth the effort.
- Bulk transfers and maximum message size - Eventually we will want to
integrate bulk transfers (which can be huge, and don't want to keep everything
in RAM); for now, they will work fine as-is, although inefficiently.
- Appropriate window size for message counters. IMHO 8192 may not be enough for
high bandwidth moderate latency, at least not in the medium term.
- Appropriate window size for packet numbers.
- New interface PacketFormat. Includes maybeSendPacket() and
handleReceivedPacket(). Will implement everything related to the packet format.
- New class FNPWrapper: Move mustSendNotificationNow(), maybeSendPacket().
Implements old FNP.
- Separate IncomingPacketFilterImpl from FNPPacketMangler, very simple class to
lookup address and feed through PeerNode to FNPPacketMangler.
- New FNP format is implemented through NewPacketFormat.
- NewPacketFormat supports message fragmentation. This is *the* big change in
the new format. It allows dramatic improvements in many areas: In particular,
we can send small packets, we need very little padding, we can deal with any
MTU, future transports with small packets are much more feasible.
- Messages can be either small (0-255 bytes) or big (0-16MB). Currently these
are both initiated by the sender, allowing for many fun DoS possibilities. THIS
WILL NEED FUTURE WORK.
- We still ack individual packets. Which automatically acks all the ranges
included in the packet.
- Use first 4 bytes of SHA256 as HMAC. ********* TOO SHORT ???? Maybe should be
variable depending on packet size? RESEARCH THIS!
- PCFB encrypt the hash, then the packet itself. *********** NO IV! This is
*BAD*! IV should be generated in CTR mode by encrypting the sequence number
with a session key (other than the main crypto session key). We already ensure
that sequence numbers don't wrap around for regular FNP. Also we should change
the API so it's impossible to use PCFB mode with no IV, since it's suicidal.
- We still use one 4 byte ack and then 1 byte deltas. ****** We should compress
each ack relative to the preceding ack, not relative to the first ack (and sort
them, of course) ****** Also, we should provide an escape mechanism to deal
with acks which are out of range i.e. to send a full 4 bytes where necessary;
this sort of arbitrary limit can cause chaos in error handling later. I suggest
overriding the top bit in the byte count to indicate there is another set of
acks. *******
- Add PeerMessageQueue.grabQueuedMessageItem() to get a single MessageItem.
- Message ID allocation can fail, in which case we just send in-flight
messages. ******* This will result in busy-looping, does the
don't-try-till-can-send mechanism we use in old FNP work with new FNP?
- It is not yet clear how many packets can be in flight???? Looks like the 256
limit will be lifted? **************
- We allow up to 8192 messages in flight. We use the top few bits for flags. We
recycle message ID's. ********* Is it safe to recycle message ID's - even in
the presence of replays and delayed packets?
- If we receive a message and don't have the length yet (because we don't have
the first packet), we buffer the data anyway. This is essential to avoid
unnecessary resends, but it does allow for memory DoS, especially the way it's
been implemented. ************
- Add SparseBitmap class to contain range tracking logic. Similar code was in
ReceivedPacketNumbers and temporarily in MessageWrapper.
- Fully integrated, receive and send code is wired in.
- We allocate a sequence number for ack-only packets, but don't expect or send
an ack. ***** Is this a good idea? The old code uses -1, since we want to
conserve sequence numbers especially if we end up running into the window
limit? otoh but we may want to use the sequence number for crypto; if so we
could just have a parallel sequence for ack only?
- TODO: ******* Key DoS protection: Predict the encrypted sequence numbers and
watch for them. Ignore everything else. Don't try to decrypt if the sequence
number isn't in the expected window.
- TODO: ******* Memory DoS protection. This was discussed extensively, the
strategies are fairly simple.
- TODO: ******* Block transfers. Obviously we should deal with this *after* the
rest is deployed; we can use the existing code for some time.
- TODO: ******* Bulk transfers and reconsider size limits. IMHO anything over
64K should be a bulk transfer (which doesn't have to be buffered in RAM), we
will need to keep the bulk transfer data code for quite some time anyway to
deal with UOM. Long term it'd be good to not have to fragment it in fixed
inappropriate sized blocks though. In any case I suspect 2 bytes would be
enough for length for any message that we are happy to buffer in RAM? If we
don't do this we need a maximum of less than 16MB!
- Various classes e.g. NPFPacket etc, splitting the logic up into manageable
sized chunks.
- Indenting.
- Add some unit tests, including both low level and high level.
- Resending logic: When we send a packet, we resend any packets which have been
sent more than 2 round-trips ago and haven't been acked yet. ****** Resending
requires allocating a packet number. This can fail if the window of in flight
packets is too big. The current workaround for FNP in general (dunno if it
applies to new FNP but it looks like it should) is to not send anything until
we get acks... I don't think that applies to resends and acks, but here it
would????
- ********** IIRC TCP resends immediately if it sees a later sequence number?
This reduces latency but will occasionally result in unnecessary resends? I
think what TCP does is this: If a packet hasn't been acked after 4 RTT's (you
can get this from PeerNode.fourRTTs()), we resend it; and if we get an ack for
a packet, we assume those before it haven't arrived and resend them. I may be
remembering wrong, there's something about 1.5 RTTs somewhere? Look it up,
maybe on the wiki page? What the old FNP code does is hideous, of course.
- Only call onSent() once for any message.
- Lots of sanity checks.
- We try the old and new keys just like old FNP.
- Messages are sent by priority. ******** This interacts with anti-memory-DoS;
we have to tradeoff between sending high priority stuff and completing existing
sends.
- Message seqno's are reused. ********* We need to seriously consider this, I'm
not sure it's safe, even with a packet-level window. How can it be made safe?
Safe = we get a somewhat delayed packet, it contains a chunk from message 1, we
can be confident that wasn't from the previous message 1.
- ********** Is a hard limit of 8192 messages in flight acceptable medium term?
It may become an obstacle.
- Hacks to ignore fragments of a given message segnum on incoming packets for a
while after it was used. Which reduce performance, and still ack the packet, so
probably cause data loss. *******
44012f14126e2364fb57ce0a4f879eccfb332ce9
- *4 byte* HMAC?????? You need more than this, certainly on larger packets, or
you need higher level authentication somehow.
- Need a better scheme for ack's - the current code is limited to a window of
256 packets but this is definitely not sustainable long term.
52715da7efc832a8c6a1767f771b6459bd909cd4
- Did we decide that we should only include the message length on the first
packet? IIRC there were complicated discussions related to sender initiated vs
recipient initiated...
11567fbd96c11f387f415717a7ef376e6c397273
- We may want to support including more than one fragment from the same message
for jumbo frames or for fragmented retransmission where we've lost something in
the middle. But we should probably round-robin, so we need to re-run the add
started messages loop until there is no more to add or we finish.
aea9a7a63af7ff779398c09afaf353401df07ece
- Consider and document policy re which fragments to send first. It may be best
to send the earliest fragment first? Since there are no message level hashes,
the recipient may be able to process a partial message, in which case earliest
fragment first makes sense.
866a2aa9ee74434d6ad4328dc8c5edaa75b779f6
- synchronize when allocating a sequence number!!
fee4eeb53c0d3c953e50fb9cca1c0491c37798ac
- SHA256 is not an HMAC because it's not keyed. If we encrypt it afterwards
that sort of serves the same function but it would be better just to use a real
HMAC.
- 4 bytes is not enough, certainly not for larger messages. We can't hash the
messages either - except maybe the big ones. How to deal with this is a big
open challenge - higher level hashes will be troublesome one way or another...
d70deac8cd005bc4b1af3b89d585bf51b28adc66
- Not sure there's any point, you could store them as ints and cast them to
longs, or just require them to be positive? If you are going to use longs and
restrict their range you probably need some asserts.
59e7088ca13761253eb1729b9e4c9f73af6ae205
- Here and elsewhere sign extension on bytes can trip you up. You need to do &
0xff on the byte values, or use one of our provided methods for decoding, or
mask the whole thing afterwards e.g. value = value | 0xffffff.
78aced73420599f544cf6aefca188ca9963b28d4
- assertTrue(s.contains(3, 2));
- this should throw!
f32ee7587ce8a3fa80574b35505aa66a080ef084
+ //TODO: If the other side resends a packet
after we have gotten all the data, we will
+ //never ack the resent packet
- The standard solution to this is to ack resent packets. If we have processed
a packet and we get a resend for it, ack it.
cd7d374b7823906a46a46a417fdface43bbe188a
- I'm not sure this is wise - if we use a full HMAC on big packets, that might
kick the encrypted sequence number into the second block, thus becoming
unpredictable? OTOH if we use an HMAC of the encrypted data (keyed from a key
other than the encryption key), and don't encrypt it itself, it won't be a
problem.
0a92c3f7a14d1f44f1f25013d045fbbeb2ff867b
- Can isFragmented() be bogus here with border cases? It is calculated based on
the maximum header length - if it returns false and then we discover that with
the actual header length we don't need to fragment, what happens?
- If we ever send packets from the same queue on separate threads, we will want
to sync on the MessageWrapper during insertFragment.
349ba4b57cad858541039f5bcfe140019edbfb9c
- You may want to try setting the config node.testingDropPacketsEvery to
simulate random packet loss.
5b3d6b32a0a7c1fb593df3c915d16a29a3d12790
- Do you need to copy the data for MessageFragment?
17096df5098e53881db1a6957c41b6c83e0ad4ec
- If frag == null, do we lose the message from the queue here?
5c537e76f15e8ef9e4ed974e5a41a31fd720f3b1
- Doesn't item itself have a method to call all the acks? it should...
bc1eb2fa33c0b2063992df3fb9b207c8c7b66f0c
- The unit test doesn't test what it says. The bytes should each be different
to be sure about this.
1f893a30d456d04eca59e8eeca209c94d9769df4
- ********* We should try the previous key as well as unverified key.
7a316c720fcaed368d7ad35f8a1262aa4f91dce7
- it shouldn't be added if it's bad
43471bf6d7e59295c6a2e5a992eba49838830ff2
- acked ranges can be lost too, can't they? at least with some buffering/DoS
protection schemes? I guess that would be a different function / a parameter;
it's not the normal case, it would only happen if they explicitly tell us.
4a7586992a743c55a9ebcdb15567a746fd0f6314
- if you are confident that the packet has been processed already, you should
ack it. if you're not you should process it. no??? otoh the fact that we resend
at the level of messages means that it's not critical ... so maybe just dumping
it is the right answer?
- we can use ranges to track efficiently which packets we have received, but
there must be a limit... beyond which we might want an explicit nak?
- how does the window for acks relate to the window for setting up packet
numbers?
- how does this interact with reusing message sequence numbers? if we have lots
of small messages then it is possible to burn through 8192 messages in less
than 128 packets (especially if half of those packet seqno's were allocated for
ack-only packets i.e. are pointless)
b58aa213ed98f814eaab2c9893d1b12d4578c04e
- remove the sentPacket when returning due to no key???
a1acd68b51cc124a11ed1d496c82f82ce279da3a
- Don't count the RTT slots that haven't been filled in!
8f561a3ce585170c55a678e0cc0d62b6ab639a25
- Use entrySet() and Map.Entry<>.
899528d44d43b42d2ca8a304d9ecfe4847a5c50b
Use maximum not average of last 10 RTTs
- Is this a good idea?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part.
URL:
<https://emu.freenetproject.org/pipermail/devl/attachments/20100717/36569c5a/attachment.pgp>
