How to improve TCP/IP for an interplanetary WAN?

Question

Background

It is the near future. After a major world war and limited nuclear exchange, the nations of Earth have consolidated into a few blocs. The threat of further war and the cumulative damage to the planet spur enormous private investment in colonization of space. Floating colonies surround Earth and near-Earth orbits of Sol. The terraforming of Mars has begun. A great demand for resources off-Earth has spread asteroid mining operations throughout the solar system.

A great number of factions have developed in space. No one faction has enough resources to build a communications system spanning the entire inner solar system, especially considering that deployment cost of communications nodes is high (rockets are expensive). The competing factions settle on developing a collaborative communications system modeled on the Internet, where no one faction can be dominant.

Problem

The Internet Protocol Suite (with Link, Internet, and Transport layers) works well on Earth, where static computers are connected to each other by cables. The cables allow near-instantaneous communication, and the hardwired connections are rarely changed. On an interplanetary scale, two major problems arrive.

• Sparse connections: Cables on earth are cheap, but satellite dishes that work over AU distances cost a lot of money, so there are a limited number of connections each node can have. Also, connections can be blocked, based on position relative to planets and the sun. Two nodes may be unable to communicate for hours or days at a time. Importantly, much of the disruption is scheduled, due to easily predicted rotation and orbital characteristics. A good protocol suite will have a built in ability to optimize the physical transfer path from node to node to ensure data gets to where it is going as quickly as possible, and so that two way communications are not interrupted needlessly.

• Latency - Message travel time from one side of the asteroid belt to the other take about 45 minutes. From Earth to mars at closest approach is about 3 minutes. This is a significant when it comes to a TCP/IP or SSL handshake. Protocols should minimize the need for two way communications without sacrificing security. Also, if packets in the same TCP session took two different routes from point A to point B; on Earth this is negligible time difference, but in space they could arrive minutes, or even hours, apart.

Statement of Work

What is the smallest set of changes you can make to the TCP/IP protocol suite to optimize its performance over interplanetary networks?

The goal is to optimize reliability, throughput, and to minimize unnecessary latency.

Notes

• Currently, humanity is limited to the inner solar system (out to the Asteroid Belt). However, the developed protocol should be extensible at least to the Kuiper Belt, with latency times of up to 10 hours.
• This question is focused on the Data Link, IP, and Transport layers; assume the physical layer works just fine.
• Here is a report on Space Communications Protocols, though this is for near-Earth space. Here is a discussion of some problems with interplanetary communications.

Answer 1

The obvious answer to delay-tolerant networking is store-and-forward.

With TCP, when a router receives a packet, it immediately sends it on to the next hop—or, if it can't, rejects it and sends back an error.

With a store-and-forward protocol, when a router receives a packet, it looks up the next time it expects to be able to talk to the next hop (possibly choosing from among multiple possibilities based on how big the packet is, what its QoS tags say, etc.) and stores it until then.

Store-and-forward goes back to SMTP, NNTP, UUCP, and other protocols from before the public internet. Before 1994, if your company wanted to have external email, that usually meant your server connecting to your provider twice/day via UUCP and sending and receiving all the outgoing and incoming messages. But modern DTNs need something more granular than "send everything to one host twice/day". (Also, these protocols are designed for infrequently-connected but low-latency-while-connected networks, so they do a lot more noisy handshaking than your want for often-connected but high-latency.)

Meanwhile, store-and-forward on the level of tiny IP packets isn't all that useful, so you add a way for applications to define bundles of multiple packets. You can then route, and QoS, and congestion-manage, entire bundles (so ideally, when you accidentally send home a 4K video instead of an SD one, it times out on your local router instead of wasting all your bandwidth and half your ISP's before getting dropped). As a side benefit, bundles can be large enough that you can afford security features like identity-based routing, which might also be important for a DTN.

The obvious way to do this all is to define a routing overlay network on top of UDP, much like the way (post-BitTorrent) P2P meshes work as an overlay on top of UDP. (Except that, unlike a typical P2P mesh, you want some intelligence so you don’t just retry the UDP packets with exponential backoff and automatically mesh adjustment, but instead store programmable schedules in your routing table, because a lot of things will be predictable—don’t bounce off that lunar satellite for the next 3 hours because it’s blocked by the moon…)

Last I looked at this was about a decade ago, and the state of the art was the experimental protocol in RFC 5050. There have probably been advances since then, and I may not be remembering everything perfectly.

Answer 2

NASA as already put some thought into this and has developed a concept called "DTN" or Delay-Tolerant-Networking. Basically it checks if the connection is possible to the next "hop" or station, then sends the data. If it's not available it stores it in the local memory until the connection goes up again. This can operate together or separately from traditional TCP/IP

In terms of infrastructure, I'm imagining a large-scale solution involving a series of large dishes spaced around the planet so that at least one always has a connection to a given location or planet. These dishes act as bridges to the rest of the solar system, beaming out huge quantities of data to their recipients as the connections become available. By networking them together, they can automatically transfer it from one dish to the next as needed.

Answer 3

You probably want to switch away from TCP/IP which is packet based to something that is content addressable. TCP/IP is built on the assumption you can signal congestion to the people using the network by dropping packets. If your round trip time is high that becomes a very expensive signaling method.

What you would like to do is telling the network you would like a certain piece of information and download it from the nearest node that has that information. That way you can get your information faster if someone else already used that information earlier. An example of a current implementation of this is IPFS (InterPlanetary File System).

It kind of functions like on gigantic bittorrent swarm in that it downloads the needed information from nearby peers that have the information. This reduces duplicate traffic over congested / expensive links and decreases the amount of time it takes to get the information you need.

Answer 4

What is the smallest set of changes you can make to the TCP/IP protocol suite to optimize its performance over interplanetary networks?

I'm a little surprised that no-one has said this yet, but you would use neither TCP nor UDP. It's not workable. The idea of any level of live connection beyond Earth orbit is not reasonable. Round trip to the Moon is 2.6s. We've got a hard-wired internet connection here that gets quite dodgy in severe weather so I've actually experienced internet speeds where ICMP packets have required over 2s for a round-trip and I can tell you that the internet is practically unusable under those conditions.

The best round-trip you can hope for between either Mars or Mercury 6m24s and 6m, respectively. The next most interesting place to be beyond Mars is Jupiter, and your best round-trip time there is well over an hour (69m47s).

The Disruption/Delay Tolerant Network was mentioned. DTN may be suitable for orbital or possibly even Earth-Lunar live network connections, but beyond that you'd use something else.

Interplanetary networking connections would not be live. In fact, you would not have a persistent connection, much less a direct connection to any planetary internet beyond your own. You would send a packet requesting very specific information, and you would receive your return transmission a few or more minutes later, within the limits of having to share the radio spectrum with everyone else in the Solar system. The transmission would be broken up into "packets", but not packets in the TCP sense -- more like packets in the old Fidonet sense. Rather than re-request data, you would simply repeat your request, specifying only those blocks of data which were lost or garbled; protocols would be designed in such as way as to have predictable framing of the data just so that you could request only the bad data.

Some data would be continuously transmitted, some would be available via transponder, and some would be transmitted on some kind of schedule.

There would be some localized synchronization, though not the entire internet. Wikipedia and other large databases, for example, would synchronize locally. Updates would be requested as of a specified timestamp so that only current sync data would be transmitted.

Communication on the interplanetary network would better resemble the old teletype system than it would the old BBS system.

I'm reminded by @Hobbamok that microwave transmission would be used for the point-to-point connections between settlements, outposts, and Earth. Quite possibly laser would also be used where appropriate. That would negate the problem of having to share bandwidth among the rest of the Solar system.

Answer 5

The smallest set of changes you could do, would be to switch from TCP/IP to UDP/IP. The biggest issue with TCP is that it needs to check back with the sender to ensure the packet has arrived. If it takes 10 hours one way, then its going to take 20 hours to know that the message you sent has arrived and if you need to resend packets.

With UDP this verification step is ignored. If I want to send a message, I can sent it in a fraction of a second. If it doesn't make it, the person who requests the data will simply request for it again. I don't need to maintain a connection for 20 odd hours, just to make sure the message has arrived.

You would also need to authenticate and encrypt your data with a shared key that will need to be determined before hand, similar to a SSH key because it would be too inefficient to encrypt things dynamically.

Added -Edit: The question asks for reliability, throughput and low latency. You simply can't have all of them. If you want reliability and high throughput, your not going to get low latency and if you want high throughput and low latency, its not going to be reliable. Its the triangle thingy where you can only really maximize two out of the three. If your physical layer is assumed to work just fine, then using UDP and pushing the rest of the logic into the application layer will provide you better results. The lack of handshaking and verification means your going to have the lowest latency possible, and throughput and reliability are going to end up being dependent on your hardware. An application designed to request for lost packets is still going to end up better than TCP because you only need to request for lost packets and skip the verification and initial handshake.

The Truth of the matter is no one protocol will be used. Protocols guarantee different things and serve different purposes. If you have a remote base/probe that takes 10 hours to communicate to, you don't want to wait 20+ hours to see the live video feed (Handshake, packet transfer and order guarantee will eat up all your time). Your going to use UDP to ensure that you have the video as quickly as possible (10 hours). Like wise, if your transmitting a file, you want reliability, and this can be added at the protocol level (There are many variations of UDP or just plain TCP) or application level. Finally if you want to transmit huge amounts of data, you want to deliver it physically, because you can almost always delivery huge amount of data faster if you physically move it (if you think data transfer over a line is faster your not thinking big enough).

Answer 6

Caching

The first person download the new Game of Thrones takes 20 hours. After that a copy is stored on the caching server and it only takes seconds for the second person.

Caching keeps the results of requests locally so it's slow the first time while it gets the information but much faster as it already has it for further requests. The server only hold X amount of data so the oldest requests drop off the end of the queue as it fills up.

The end result is the most common requests are stored locally and are much quicker and data transmitted is much less.

Answer 7

Bandwidth

You haven't specified how much bandwidth you have.

You can broadcast absolutely tons of additional information if you have extra bandwidth. For example, interplanetary netflix you could broadcast 15 minutes of the 30 most similar films alongside the film you are watching when it comes to an end, so you can select another film to watch and begin watching it immediately. The same can apply to all kinds of data.

Prediction

You can add prediction to this, much like how Chrome works, to follow likely links to speed up loading should the user click on them. You'd have to add all of this data to the packet. Instead of loading wikipedia's home page, a request to wikipedia could predict what you're likely to look at and broadcast the entire site, or a summary of each page.

Datablasting

You could also do something akin to a datablast from the 90s, where information would be displayed at high speed and the public would videotape it and replay it in slow motion to read it. Constantly be broadcasting all kinds of information continously and caching it, in case it is needed. Even with low bandwidth, any spare 'cycles' could be used to cram in additional information.

Remote Executability

Remote executability would be the ability to send a small program that can be executed on earth.

For example, you want to play interstellar chess with someone on Jupiter's moon Io. Instead of sending a move, only to find out 45 minutes later it was an illegal move because you forgot you were in check, it would be faster if a small chess program was uploaded and executed on both earth and Io. Then when an illegal move is made it can be validated or modified without the need to send it on.

This is similar to client side validation in Javascript, whereby you try to submit a form to sign up to something and forget to fill in your e-mail address, it will ask you to complete it before sending the form instead of sending it and getting an error back.

Another example of this is if a client requests information about the position of earth on a certain date. Rather than them send the request and 45 minutes later receive a response, they could instead receive a small executable program that will calculate this for them.

Caching

Obviously, caching data for re-use locally but on a wider scale, putting servers onto various planets/satellites and caching it in each of them. For example, the big News sites would be popular daily so this would be distributed and cached between all of the locations. Other data would also be cached, and kept based on views. This is very similar to how Amazon's warehouse system operated - items people are likely to buy are automatically distributed to warehouses using algorithms that predict people will buy the items, thus saving on shipping time.

---

I guess that one of the key things to note is the paradigm shift required in terms of developing the internet. It's not really a question of How do we deliver web pages and the current internet experience, it's more a question of How would the world wide web look if latency was crazy high?. You'd retrain your software engineers and rewrite all of your tools, and the internet would be mostly application based, you'd probably download the BBC News app and have it updated automatically every morning from a local cache, either downloading the entire site, or just browsing the entire site locally from a cache.

Answer 8

You need to change the way your internet architecture is set up to have caching of entire websites

There's no reason to bother with lengthy downtimes on the internet, except in the form of messages sent from planet to planet. If the internet has a downtime of 20 hours just to load a list of webpages and another 20 hours to load one page, people just won't do it.

If you want people to use the internet, each colony needs their own servers to hold the contents of the web that they want to be able to see. When a colonist goes online, they are only really communicating with the local server. Local servers communicate through the satellite network by PUSHing updates to other colonies who download the updates. This way, browsing the web takes seconds, even though the news might be a few hours old, which can't be helped anyway. This update pushing process means the network is decentralized, and because local computers don't communicate directly access the internet, traffic is significantly reduced. If computers communicate directly with the internet, routers will not be able to handle all the traffic, especially if they are storing packets during downtime.

When servers communicate, all of the packages are pushed at once, and the connection is not kept alive. This protocol works with the packet storage idea proposed by other answers.

If you have multiple routing paths that the messages can be sent through, each router on the path sends the packets through all of the pathways available and the receiving computer takes the first one it gets and ignores duplicates. If the package is corrupted, it waits for a duplicate to arrive. If after a couple hours it has only gotten corrupted packets or no packets have arrived, it requests the packets again.

Messages can use a different protocol. Messages are sent from one colony's server directly to the destination server, not to any other servers on the network. When the receiving server gets the message, they push the message to the computer that receives it.

With these methods, servers can't afford the luxury of opening and closing ports. They always have to be listening for updates so they don't miss anything.

Benefits of this design:

Less computers sending packets over the interplanetary routers, dramatically reduces round trips, server always receives the message as fast as possible, no handshake necessary, multiple routing paths means the network can stand the loss of a few satellites, almost instant communication with the local server, ability to push updates instead of client requesting them, separate messaging protocol (no other colonies see your message to a different colony).

Answer 9

IPTP (Interplanetary Transmission Protocol)

IPTP is a bi-directional, point-to-point, store-and-forward protocol, designed to be highly fault-tolerant.

IPTP Links are defined between planets such that at any given time there is exactly one transmitter on or in orbit around one planet streaming data to any given array of receivers on the other. (The active transmitter will change as the planet rotates and satellites revolve about it.) This stream must be able to multiplex a large number of different sub-streams of data (coming from many different sources on the originating planetary internet), which will themselves be queued up in buffers for actual transmission.

The overall stream will be broken up into "blocks" of a size appropriate to the quality of the link that are each individually encoded using Reed-Solomon error-correction, and additional "parity" blocks will be transmitted periodically, allowing reconstruction of blocks that exceeded the error-correction threshold of the RS code in use for that block. (IPTP allows for this block size to be changed as conditions warrant) Each block must be retained on the sending end until a Block ACKnowledgement (BACK) is received from the receiver.

For additional robustness, after a series of "rows" (N data blocks plus an XOR parity block of those data blocks) are transmitted, a "parity row" (constructed by XORing together corresponding blocks in M consecutive rows) is then transmitted. At the end of a group (called a "chapter") of L pages of M rows and N columns is a "parity page" (constructed by XORing together the corresponding blocks in all the pages). The entire chapter of (L+1)(M+1)(N+1) blocks must use the same block size and R-S encoding, but subsequent chapters can change the block size, as well as the values of L, M, and N, as conditions warrant. In general, L, M, and N will be larger when fewer blocks need to be re-sent.

Within a chapter, the sub-streams should be assembled in priority order to minimize the number of blocks that carry data of two or more different priorities. A block's transmission priority is equal to the highest priority level sub-stream it contains.

Prior to each chapter is a header defining those parameters. [The InterPlanetary Transmission Task Force says that future versions of IPTP may extend the parity system to "books" of K such chapters, incorporating (K+1)(L+1)(M+1)(N+1) blocks each. IPTPv1 defines K=1 with no parity, so a book has only one chapter.]

"BACK" metadata must be sent back from receiver to transmitter to acknowledge entire chapters as well as ranges of blocks within a chapter. Any blocks not BACKed that fall before the last block BACKed will have to be re-transmitted. The determination to re-transmit must not be made until the entire "book" has been received and decoded, as the parity blocks, lines, pages (and chapters) to allow a BACK to be fully reconstructed will not have been processed yet. Because a BACK itself occupies one or more blocks to be BACKed, there will always be something to BACK, creating an implicit "keepalive" between the nodes.

Metadata (including but not limited to the above BACKs) is the highest priority level for substreams, and therefore should always be the first thing in a book/chapter after the protocol header. The details of other QoS considerations are still being defined by the IPTTF.

Once the data stream is reconstructed on the receiving end, it can be de-multiplexed into sub-streams, each sent to its desired destination on the planetary internet.

Answer 10

As an old fart in the IT industry, I'd like to point out that you almost certainly cannot use TCP/IP for interplanetary communication. While it can function on extremely long latency connections, you really don't want it to for two very simple reasons: SYN/ACK and retransmission.

SYN/ACK

When you open a TCP connection there's a handshake that has to happen to get the connection started. A set of 3 packets are required: C>S:SYN, S>C:SYN-ACK, C>S:ACK. It takes a complete round-trip to start the connection. If that connection is going to, for example, Mars at opposition then you're looking at 6.5 minutes before you can send a single byte of actual data.

Retransmission

TCP/IP is a reliable protocol, which means that corrupt data and dropped packets have to be re-sent. When there's a checksum error or a dropped packet the end detecting the error sends a Dup-ACK packet and throws everything away until the new copy of the bad packet arrives. Another 6.5 minutes later.

(And that's the best-case timing for Mars by the way. Worst case is you have to route through relays at the Mars and Earth Lagrange points to get a clear line of sight to Mars when it's in conjunction. So we're looking at something like an hour and a half for connection and the same delay for retransmission.)

---

So no, you're not going to have TCP connections in space. At best you're going to have a store-and-forward system where entire chunks of data are blasted between routers via maser or laser, with a redundant self-correcting transmission protocol to reduce the delays waiting for retransmission. You'll request a data block via a light-weight data burst, wait for the data to be uploaded to each node in the network as it makes its way to you, then get it all at once.

How will this work? No clue, honestly.

OK, I might have some ideas.

Sol-Net

Let's start by placing router nodes at each of the stable Lagrange points (L4 & L5) for Earth, Mars and Venus. At 60 degrees orbital separation they're a long way away, but they're relatively stable and always visible from their respective planets. When the destination is at conjunction you can see their L4/5, or they can see your L4/5, so you always have a way to get your data through.

Each node connects to as many other nodes as we can reasonably engineer. This means that we'll need a fixed tranceiver for their home planet (L4 -> Earth for instance) and a set of transceivers mounted on rotating arms that can track their dedicated relay. Add a bunch of standard radio transceivers for local traffic - ships and probes passing through their patch - and we're good to go. Oh, add a bunch of terabytes (or tebibytes if you're that kind of weirdo) of storage to buffer data in and some processing to handle codecs for the data.

Nodes bounce pings back and forth to confirm that their connection is good, that the other node is working as expected and that nobody has parked a battle station between them. It also gives you some measurement of connection quality, which we'll need later. Since inner system distances are potentially measured in hours this saves time when messages need to be forwarded between nodes as you don't have to wait for confirmation that the other node exists. These constant ping packets can also serve as the transport channel for control messages and other low-volume traffic.

When a node has to deliver a block of data it runs it through an encoder that adds redundancy and self-correction codes, then it gets sent across to the next node in chunky packets. The receiving node acknowledges each block as it arrives, buffers it and requests retransmission of blocks that can't be salvaged. Once the entire block of data (let's hope it's not too huge) is received the receiving node sends back an acknowledgement and the sending node can then delete the data block. Repeat until the data has been shuffled over to the final destination.

Since we know well ahead of time about the geometry of the network it's not difficult to plot direct(-ish) routes to our destination. Sometimes the direct path isn't necessarily the fastest though, so it's probably a good idea to send the data through at least two links as a backup. While this could add another couple of hours to the final trip time, it helps deal with unexpected transmission breaks on the way to the target. Sending directly from Earth to Mars may be backed up by sending via Earth-L4 or Earth-L5 depending on the position of Mars. Or maybe we need to send Earth -> E-L4 -> Mars because we can't send direct, and as a backup we send Earth -> M-L5 -> Mars, or maybe it'll be quicker to send Earth -> Venus-L4 -> V-L5 -> Mars. Whatever works. And if sunspots are high, maybe we send by multiple routes.

Designing a system like this sounds like fun.

Answer 11

A complete overhaul is the smallest sane change

• With a latency of 10 hours, you surely don't want to establish any connection as it alone needs three packets, which means 30 hours wasted.
• TCP-like congestion control makes no sense. For maximum efficiency, you want to direct your dishes exactly to the party you communicate with. That's true for both the sender and the receiver (there'll be either a fixed setting like "this dish communicates with Pluto" or a pre-arranged schedule). This eliminates any congestion on the link itself. The link will always work with a fixed speed, unless broken.
• As the transmission cost is much higher than the storage cost, every sent packet will get also stored until acknowledged (many hours later).

I guess, reliable UDP comes closer to what's needed. Anyway, you can forget about using the network for browsing or alike. It will look more like SMTP. You send a message and it'll get delivered, possibly delayed by many hours due to retransmissions. You can have some client-server communication, but it'll look more like requesting a book from a library than HTTP.