I started this mod in response to my previous thread which, unfortunately did not yield any solutions. Therefore, I decide to tackle the problem myself. This thread is to share updates and information with everyone regarding this mod. As well as for everyone to post suggestions, advice, opinions and anything else they feel like writing about this mod.
Status: At this time there is only some standalone prototyping code. Nothing is available yet for release.
First some explanations, one cannot expect everyone to know everything :smile.gif:
Minecraft uses TCP for communication between a server and its clients.
TCP is designed to transmit a stream of data reliably. It has error detection, flow control, congestion control and so forth to accomplish this. Packets are guaranteed to arrive unharmed and in the same order as they were sent. TCP deals with transmission errors by itself, without requiring the application to lift a finger.
Everything has its limits however and when there are considerable problems TCP will give up and either time out during an operation or reset the connection.
UDP is different. It was designed to a lightweight and fast way to pass messages. There are no control mechanisms. Packets are not guaranteed to arrive in order, without errors or at all!
So why UDP? It is frequently used in situations where it is not required for data to be accurate, but it is required that there will be very little latency. A good example would be First Person Shooters. Low latency is a must as the game progresses in real time. Movement updates are sent at a high frequency, losing a few of these updates along the way is not important as there will always be another update arriving that will invalidate all previous updates.
The application is in full control and is able to set its own boundaries as under what conditions a connection is considered lost. This control does come with responsibilities. The application must (if deemed necessary) check all packets to see whether they are damaged or obsolete.
With this mod I plan to make it possible to play minecraft on congested or lossy connections. (Poor dialup, spotty wifi, family members torrenting, etc). I also want to try and reduce the bandwidth requirements for servers and clients, allowing people on slower connections to set up servers and join existing ones.
The "How" part was (and still is) a bit problematic. Thanks to the wonderful guys that made the Minecraft Coder Pack Ive been able to decipher and understand most of the official networking code (Honestly, I've torn open a reallllly big can of worms lol :biggrin.gif:)
Since I'll be using UDP instead of TCP, every single client and server (custom or legitimate) code is completely irrelevant. So I basically started from scratch and started designing an entirely new protocol. Currently I am mostly experimenting, implementing and refining. Quite a lot of work needs to be done... Around 67 classes in the minecraft.jar source will be completely dropped, another 9 will require (heavy) modifications. I have not yet had time to look at minecraft_server.jar so most likely these numbers will increase.
I don't know how much you really know of the protocol and how the client and server works, but I do, and I know the pro's and con's of both protocols. In Minecraft's case though, UDP doesn't really work without sending large amounts of additional data, or keeping a lot of extra data stored serverside, and well the server already uses enough ram. You're biggest problem will be block changes. I'm not sure if you are aware of this but when a client sends a block change, it actually puts the block on screen, but it waits 500ms-1000ms for the block change packet from the server, if it doesn't see that it takes the block out. If the packet comes in late saying to a put a block there then it does put it back, you can easily notice this behaviour when the server is getting bummed up with requests and what not. So in UDP if you place a block and it gets lost somewhere between the client->server or it's way back, you will have problems. So without constantly updating the chunks (which is kinda counter-productive on the bandwidth side of things), or some other voodoo magic. Another thing is if a chunk data gets corrupted, either not there, or screwed up visually. Example, one client will see a random floating piece of obsidian, nobody else will see, and as far as the server knows the packet got there okay. And one more thing is that on a unreliable network/connection, whether it be slow, just clogged up with other traffic, UDP becomes even more unreliable. I'm not trying to discourage you, hell go for it, maybe learn more things. Maybe even pull it off, and prove me completely wrong, but just saying.
Thanks for your reply and your insights! :smile.gif:
Yes, UDP will require some bookkeeping but I disagree on the volume... What minecraft calls Packets, I call them Fragments. Each fragment has minimal bookkeeping of 3 to 9 bytes each. Several fragments (up to 1400 bytes worth of payload) are stuffed in a single UDP packet with a 2 byte header consisting of only a checksum.
Looking at Packet11PlayerPosition reveals that it its payload is 4 doubles, but also extends Packet10Flying which adds another byte to the payload. This adds up to a total of 33 bytes. The fragment encoder would consider this a non-critical fragment and add a 3 byte header to it... 11% overhead is not much :smile.gif:
I do plan to overhaul most, if not all of the networking code. Minecraft really does not require double precision. I would probably split up Packet11PlayerPosition into two packets. One will use 3 ints for the position, the second will use 3 longs which defines a location offset as it is unlikely that players move massive distances without teleporting. Stance and flying could be encoded as a single byte (or int, if it holds both yaw and pitch), rather than a double and a byte. It would bring the side of this packet down from 33 to 13-14 bytes. Reducing the size of high-frequency packets will make the added size of bookkeeping irrelevant. There are most likely more areas that allow potential improvements.
Yes, I have in fact noticed this "remove block, revert changes, break block, spawn drop" behavior quite frequently. Due to my horrible connection, I could mine 20-50 blocks in a row, see them all reappear (and suffocate if I stood in the wrong spot) and then see most of them finally break after 5-30 seconds.
I plan to use a NAK-only system. Which means that important data such as block updates, inventory changes, entity spawns and so forth will be flagged and marked with a sequence number (much like TCP does) and temporarily cached by the sender for retransmission if deemed necessary. When the receiver finds a sequence number missing, it will consider the fragment with that sequence number lost and will perform a NAK when its timeout expires (timeout in this case being the round trip time) to allow for out-of-order packets.
To defend against corrupted or truncated packets, I add a simple CRC16 checksum for the entire packet. When the receiver detects many damaged packets, it switches to adding a checksum for each fragment. This increases bookkeeping overhead but allows for partial recovery of corrupted packets which in turn reduces the number of retransmissions required.
I think this mod will help many others like me. Ive tried to play with 20-50% packet loss but it is near impossible. My experience is to connect to a server, fall into the void for a good 30 seconds, then the first chunk appears, some nearby players frozen in time. Usually by then either I get kicked by the server or a java exception is thrown. With such an unstable connection, TCP is completely not usable. It switches to a high-reliability mode with a window size of 1 (very slow) until finally giving up after too many packets are lost (connection reset) or the connection times out (no response from server). Other than changing the timeout or changing some socket flags, I have no control over the window size or what is considered "too many" dropped packets.
UDP also has a special ability to punch holes in firewalls which means that people wont even have to set up port forwarding. This technique is used by applications such as Skype. Only downside is that an external server is needed (minecraft.net perhaps? Or stunserver.org).
No, you are not discouraging me :smile.gif: I was actually hoping for some constructive critisism so I could refine my protocol further, find corner cases and squish bugs before the appear.
Its been.. what... 2-3 weeks? Figure an update would be nice.
No, this mod isnt dead. Had some really hard problems to solve and doing this in very limited free time.
Ive made quite a bit of progress. Currently I have a test client and server able to communicate with each other without problems. Will soon be doing stability and performance testing! It is very hard to make this mod as efficient as possible.
To accomplish this goal, it only uses a single static buffer for transmission (no creation of millions of buffers!). Receive buffers are pooled, created on-demand, reused and discarded when memory drops low (SoftReference'd).
Client and server code is considerably more shared than vanilla code, making code maintenance much easier.
A plug-in architecture has been put in place to allow other mods to hook in their own custom networking packets. Basically all a thats required is to implement a single interface containing a single method and register the implementation upon initialization. No more hacking base classes :smile.gif:
Reading and writing data is extremely easy. It exposes an interface similar as DataInputStream and DataOutputStream. All the complexities are completely hidden from user code. In fact, all networking code is completely self-contained which is a big change from the original Minecraft.
All the Packet* classes have been dropped in favor of simple class methods. Might not be very Object Oriented, but it will prevent a lot of instances with extremely limited use and lifetime from being created.
One thing that is bothering me is the DataWatcher ... its a hack really to synchronize state changes for entities (sheep color, creeper detonation and so forth) between the server and clients. It has no place in single-player code and state changes should really be packaged separately and transmitted like everything else. However, it touches a LOT of base classes and will break most if not all other mods if I were to mess with it. Your thoughts?
Other thing... absolutely hate-hate-hate the fact that java has no unsigned integers! It makes writing low-level networking code very tedious and error-prone. Have considered going native and just doing it in C... but that wouldnt make this mod very portable now would it?
Another update in... 3 weeks? Sorry, busy life :smile.gif:
Ive changed the implementation a bit... Ive made it multithreaded. It now uses 3 threads (Listener, Writer, Processor) to make sure user code will never block. Its also completely devoid of locks (no synchronize keyword). Performance numbers while profiling on this Intel E5300 at work max out at 260.000 1-byte packets per second. Or around 170.000 1400-byte packets... which is almost 2 gb/s! The profiling trace below shows it spends most of the time either blocked waiting (good thing) or in native Java code (also good thing).
Status: At this time there is only some standalone prototyping code. Nothing is available yet for release.
First some explanations, one cannot expect everyone to know everything :smile.gif:
Minecraft uses TCP for communication between a server and its clients.
TCP is designed to transmit a stream of data reliably. It has error detection, flow control, congestion control and so forth to accomplish this. Packets are guaranteed to arrive unharmed and in the same order as they were sent. TCP deals with transmission errors by itself, without requiring the application to lift a finger.
Everything has its limits however and when there are considerable problems TCP will give up and either time out during an operation or reset the connection.
UDP is different. It was designed to a lightweight and fast way to pass messages. There are no control mechanisms. Packets are not guaranteed to arrive in order, without errors or at all!
So why UDP? It is frequently used in situations where it is not required for data to be accurate, but it is required that there will be very little latency. A good example would be First Person Shooters. Low latency is a must as the game progresses in real time. Movement updates are sent at a high frequency, losing a few of these updates along the way is not important as there will always be another update arriving that will invalidate all previous updates.
The application is in full control and is able to set its own boundaries as under what conditions a connection is considered lost. This control does come with responsibilities. The application must (if deemed necessary) check all packets to see whether they are damaged or obsolete.
With this mod I plan to make it possible to play minecraft on congested or lossy connections. (Poor dialup, spotty wifi, family members torrenting, etc). I also want to try and reduce the bandwidth requirements for servers and clients, allowing people on slower connections to set up servers and join existing ones.
The "How" part was (and still is) a bit problematic. Thanks to the wonderful guys that made the Minecraft Coder Pack Ive been able to decipher and understand most of the official networking code (Honestly, I've torn open a reallllly big can of worms lol :biggrin.gif:)
Since I'll be using UDP instead of TCP, every single client and server (custom or legitimate) code is completely irrelevant. So I basically started from scratch and started designing an entirely new protocol. Currently I am mostly experimenting, implementing and refining. Quite a lot of work needs to be done... Around 67 classes in the minecraft.jar source will be completely dropped, another 9 will require (heavy) modifications. I have not yet had time to look at minecraft_server.jar so most likely these numbers will increase.
Yes, UDP will require some bookkeeping but I disagree on the volume... What minecraft calls Packets, I call them Fragments. Each fragment has minimal bookkeeping of 3 to 9 bytes each. Several fragments (up to 1400 bytes worth of payload) are stuffed in a single UDP packet with a 2 byte header consisting of only a checksum.
Looking at Packet11PlayerPosition reveals that it its payload is 4 doubles, but also extends Packet10Flying which adds another byte to the payload. This adds up to a total of 33 bytes. The fragment encoder would consider this a non-critical fragment and add a 3 byte header to it... 11% overhead is not much :smile.gif:
I do plan to overhaul most, if not all of the networking code. Minecraft really does not require double precision. I would probably split up Packet11PlayerPosition into two packets. One will use 3 ints for the position, the second will use 3 longs which defines a location offset as it is unlikely that players move massive distances without teleporting. Stance and flying could be encoded as a single byte (or int, if it holds both yaw and pitch), rather than a double and a byte. It would bring the side of this packet down from 33 to 13-14 bytes. Reducing the size of high-frequency packets will make the added size of bookkeeping irrelevant. There are most likely more areas that allow potential improvements.
Yes, I have in fact noticed this "remove block, revert changes, break block, spawn drop" behavior quite frequently. Due to my horrible connection, I could mine 20-50 blocks in a row, see them all reappear (and suffocate if I stood in the wrong spot) and then see most of them finally break after 5-30 seconds.
I plan to use a NAK-only system. Which means that important data such as block updates, inventory changes, entity spawns and so forth will be flagged and marked with a sequence number (much like TCP does) and temporarily cached by the sender for retransmission if deemed necessary. When the receiver finds a sequence number missing, it will consider the fragment with that sequence number lost and will perform a NAK when its timeout expires (timeout in this case being the round trip time) to allow for out-of-order packets.
To defend against corrupted or truncated packets, I add a simple CRC16 checksum for the entire packet. When the receiver detects many damaged packets, it switches to adding a checksum for each fragment. This increases bookkeeping overhead but allows for partial recovery of corrupted packets which in turn reduces the number of retransmissions required.
I think this mod will help many others like me. Ive tried to play with 20-50% packet loss but it is near impossible. My experience is to connect to a server, fall into the void for a good 30 seconds, then the first chunk appears, some nearby players frozen in time. Usually by then either I get kicked by the server or a java exception is thrown. With such an unstable connection, TCP is completely not usable. It switches to a high-reliability mode with a window size of 1 (very slow) until finally giving up after too many packets are lost (connection reset) or the connection times out (no response from server). Other than changing the timeout or changing some socket flags, I have no control over the window size or what is considered "too many" dropped packets.
UDP also has a special ability to punch holes in firewalls which means that people wont even have to set up port forwarding. This technique is used by applications such as Skype. Only downside is that an external server is needed (minecraft.net perhaps? Or stunserver.org).
No, you are not discouraging me :smile.gif: I was actually hoping for some constructive critisism so I could refine my protocol further, find corner cases and squish bugs before the appear.
No, this mod isnt dead. Had some really hard problems to solve and doing this in very limited free time.
Ive made quite a bit of progress. Currently I have a test client and server able to communicate with each other without problems. Will soon be doing stability and performance testing! It is very hard to make this mod as efficient as possible.
To accomplish this goal, it only uses a single static buffer for transmission (no creation of millions of buffers!). Receive buffers are pooled, created on-demand, reused and discarded when memory drops low (SoftReference'd).
Client and server code is considerably more shared than vanilla code, making code maintenance much easier.
A plug-in architecture has been put in place to allow other mods to hook in their own custom networking packets. Basically all a thats required is to implement a single interface containing a single method and register the implementation upon initialization. No more hacking base classes :smile.gif:
Reading and writing data is extremely easy. It exposes an interface similar as DataInputStream and DataOutputStream. All the complexities are completely hidden from user code. In fact, all networking code is completely self-contained which is a big change from the original Minecraft.
All the Packet* classes have been dropped in favor of simple class methods. Might not be very Object Oriented, but it will prevent a lot of instances with extremely limited use and lifetime from being created.
One thing that is bothering me is the DataWatcher ... its a hack really to synchronize state changes for entities (sheep color, creeper detonation and so forth) between the server and clients. It has no place in single-player code and state changes should really be packaged separately and transmitted like everything else. However, it touches a LOT of base classes and will break most if not all other mods if I were to mess with it. Your thoughts?
Other thing... absolutely hate-hate-hate the fact that java has no unsigned integers! It makes writing low-level networking code very tedious and error-prone. Have considered going native and just doing it in C... but that wouldnt make this mod very portable now would it?
Ive changed the implementation a bit... Ive made it multithreaded. It now uses 3 threads (Listener, Writer, Processor) to make sure user code will never block. Its also completely devoid of locks (no synchronize keyword). Performance numbers while profiling on this Intel E5300 at work max out at 260.000 1-byte packets per second. Or around 170.000 1400-byte packets... which is almost 2 gb/s! The profiling trace below shows it spends most of the time either blocked waiting (good thing) or in native Java code (also good thing).