I show here one way to mux and demux a mux-stream into its component streams using the Keykos kernel messaging primitives.
This was the initial bare design of the Tymnet interface.
It grew much hair.
These schemes are too simple but it is important to see how simple schemes fail before proceeding to complex schemes.
First there is the flow control issue.
No software system design will process an arbitrarily high bandwidth input stream with fixed compute hardware.
The input stream will be inhibited or some system load-shedding (data triage) will be in place.
There are these regimes:
- The software will discard data at its convenience, but with downstream notification.
- Some counterflow signals serve to invite additional traffic on a stream.
It is necessary only to process invited traffic.
Invitations accumulate and are overlapped.
This is the familiar window scheme used in many common protocols such as X25 and HDLC.
Demultiplexing Input
We do regime 1 first.
We describe the input demultiplexer but the output mux is highly analogous.
The input demultiplexer comprises two domains:
- The M domain holds the key to fetch from the mux-stream source.
- The S domain responds to the sub-stream keys.
S remains prompt and never waits by calling other keys.
S keeps a bit array, b, and a capability array, c, each with an entry per sub-stream.
If b[j] = 1 then c[j] holds a return key to a consumer of sub-stream j.
M waits on its mux-stream key which returns at least when there is data for some sub-stream.
Data in the mux-stream identifies the sub-stream.
M calls S when new data arrives.
S may return to M immediately if has room for another hunk of mux-input.
S may alternatively stash the return key and return when it has room.
When S is called by M it identifies new portions of sub-streams that have become deliverable.
S forks any waiting return keys that correspond to deliverable stream segments.
The fork is done via the returner.
This is prompt by nature of the returner; the returner is prompt even if the key from c is not a resume key.
S may be stuck holding stagnant data for sub-streams with sluggish consumers.
It may choose to discard such data.
With Backpressure
For regime 2 we propose that sub-stream consumers call S only when they are ready for more input.
M is then in a position to generate invitations, presumably in advance of calls from sub-stream consumers.
Advance invitations are presumably for some fixed amount of data and this amount depends on the bandwidth and latency of the upstream system.
Our practice is to handle full-duplex traffic with separate domains for each direction.
The input domains must express these invitations to the output domain M which generates the multiplexed output stream which includes the invitations.
This signaling, I think, is done best with an eventual channel.
This is a familiar CS construct but I don’t know a name for it.
An eventual channel between cells X and Y in two address spaces, probably in different machines, has the following properties-
No one but the channel stores into Y.
- The channel reads X from time to time.
- The value in Y now is the same as some value that X held sometime in the last few seconds.
The channel does this by simply copying X to Y whenever it is both convenient and possible.
Retransmission on error is not required.
No flow control is necessary.
Eventual channels are easily concatenated to form longer eventual channels.
Invitations can flow thru eventual channels.
The main input domain can send the invitations thru shared RAM to the main output domain.
This also results in the requirement that both main domains run periodically even when there is no traffic; they each handle the other’s invitations.
Multiplexing Output
We have the same two domains, M and S.
M holds a key it uses to send the output stream.
This key may be sluggish if there is more data to send than can be accepted.
S responds to calls on writes to sub-sreams.
When M regains control from the mux output stream it calls S waiting for more multiplexed stream to send, whereupon S may send what it has or stash M’s return key until later and become ready.
S assembles segments from output streams that are ready.
There may be policy here if there is competition for output bandwidth.
As space becomes available for S, it returns to resume keys it holds to sub-stream producers.
Backpressure
Flow control signals arrive via the mux input stream.
They are processed first by S on the input side.
They are made available thru shared memory for the output S.
S holds back output for particular streams by holding onto the resume key in its c array.
Logic of Invitations
This is a pattern from Tymnet adopted by X.25 and other ISO standards.
Each error controlled block would include its serial number and also the serial number of the block in the other direction such that all blocks up to there had been correctly received.
Bits were dear and three bit counts were used except satellite links whose latency demanded 7 bits.
The magic of this scheme is that lost acknowledgments merely delay things — they do not corrupt the stream.
Such acknowledgments can travel via eventual channels.
Mapping this to Internet
TCP has backpressure.
It is end to end, which means that retransmissions further congest the net when it is already congested.
The packet reassembly can be done by S on the input side which can also deliver TCP style flow control.