1.2.3.5.The Data Link Layer and SDS
The Data Link Layer is generally concerned with the transmission of "frames" between two directly connected Interface Message Processors (IMP's) [Tanenbaum 1989]. MIDI is a character based transmission system and framing bits (start and stop bits) are put in place in the physical layer (by serial communication controllers). This multi-layer model for networking is known as the Open Systems Interconnection (OSI) Reference Model [Tang and Scoggins].
Figure 1.2.3.5-1. Interface Message Processors and Hosts
The IMP, for MIDI, can be in implemented in hardware, software or both.
Figure 1.2.3.5-1 shows the host and IMP as different devices. This is often not the case. The IMP may be implemented in software, hardware, or both. In the 68HC11A8P1 control voltage to MIDI converter (shown later in this chapter) we show an implementation of the IMP in software. This is possible because the microcontroller is running a single real-time task. In the section on MIDI Merging (which appears later) we discuss how the serial communication controller deals with implementing part of the IMP in hardware.
The data link layer doesn't address inter-IMP routing issues, this is a network layer problem. The data link layer doesn't address bit transmission issues, this is a physical layer problem. In terms of the OSI reference model, a frame is a block of data, with sync bits, header, information field and error checking. The header contains data about the sequence number, classification and an acknowledgment used in two way communications. An SDS packet is a data link layer frame. It is often the case that real networks do not follow the OSI reference model, both in jargon and in number of layers.
Figure 1.2.3.5-2 Lower 3 Layers in the OSI Reference Model
The Masters' Data Link Layer (DLL) gets packets from the network layer (using a procedure called getp). It sends frames to the other DLL (using sendf). The slaves' DLL gets the frames (recf) and returns them to the higher net layer (givep). The slave has a procedure called wait. which can be ignored by the transmitter. If wait is un-implemented, the SDS dump is performed in "open-loop" mode. That is, without feedback from the slave. This is shown in Figure 1.2.3.5-3.
Figure 1.2.3.5-3. Open-Loop Transmission
MIDI does not require the implementation of the Wait message, so open loop transmissions are possible. This is called unrestricted simplex protocol (protocol 1).
A problem with the unrestricted simplex protocol (protocol 1) is that the master can swamp the slave. If this occurs the slave will loose data. If the wait message is recognized, the flow of data to the slave will stop. The wait message contains the channel number and the packet number. The transmitter may not send any more packets on that channel until told to do so. This technique, along with open-loop mode transmission, has no error recovery. Either the wait message could be lost, or the transmitted frame could have a class 1 error. In either case, there would be some advantage for implementing an Automatic Retransmission reQuest (ARQ) protocol. One ARQ protocol is called simplex stop-and-wait. A simplex stop-and-wait protocol (protocol 2) involves getting a packet from the network layer, transmitting it and then waiting for an ACK. Recall that the ACK (in MIDI) contains both packet number being acknowledged and channel number.
Figure 1.2.3.5-4. MIDI Simplex Stop-and-Wait
In this protocol, the master sets a timer and waits for the slaves ACK.
The problem with simplex stop and wait is that the return channel may have an error which causes an ACK to be delayed or destroyed. This could cause a duplication error. For example, suppose the following sequence of events occur:
master, sends a frame to slave.
slave sends an ACK to master but it is not received by master.
master times out and retransmits
slave obtains 2nd copy of the frameThe designers of the SDS specification numbered both the SDS data packets and the ACKs. These numbers can be used to stop duplication errors. If we use the numbers 0 and 1 we have a "positive acknowledgment/retransmission protocol (par)" [Tanenbaum 89], or sometimes called "complete stop and wait". This allows data to be transmitted in one direction (half duplex) over a noisy communication channel that garbles and looses frames. If the SDS packet is lost or damaged, the slave will not send an ACK and the master can keep trying (it times out). If the slave gets the wrong packet number, it is rejected as a duplicate. The master must wait for an ACK before advancing to the next SDS packet. It requires the time-out to be long enough to prevent premature times outs which will cause a duplication error.
The only ambiguity is between frame m and m+1. If the master times out too early, while an ACK is on the way, a duplicate frame will be sent. The ACK arrives and the master is fooled into thinking the ACK is for the frame just sent (not the duplicate). If the next frame is lost, the master will not try to retransmit and the protocol fails. PAR can deadlock if the master times out too early.
Figure 1.2.3.5-5. Protocol 3, Positive ACK/retransmit Protocol (PAR).
PAR requires that the Master time each frame and that a time-out interval be designed into the system.
Since SDS packets provide for numbering of both packets and ACKs, it is possible to transmit several packets without getting any ACKs. This is called a sliding window protocol and can lead to a performance improvement, since the act of waiting for an ACK or its time-out can take a non-trivial amount of time. Other protocols use this technique too. For example, Trivial File Transfer Protocol (TFTP) [Stevens] has both frames and ACKs numbered. Time-outs occur for any frame and frames are transmitted continuously. No deadlocks can occur. Sliding window protocols remain synchronized in the face of garbled or lost frames. They can handle premature time-outs.
The draw-back to the sliding window protocol is the increased implementation complexity for both the master and the slave. The master must time each packet. The slave must reorder the packets to present them to the network layer.
In TFTP a separate ACK is always sent when a frame arrives. This is a half-duplex transmission. If transmission were full-duplex, we could improve throughput via a technique called piggy backing. Piggy backing involves adding a frame ACK code to the next outgoing frame. This means hold up the transmission of the ACK till the next frame is ready. If we wait beyond the time-out, the re-transmission occurs. Piggy backing would require an extension to the Specification, before it can be implemented.
Figure 1.2.3.5-6. Sliding Window Protocol with Time-Outs
The number of outstanding frames must be limited by the header size.
Figure 1.2.3.5-6 shows a sliding window protocol with a time-out occurring before the ACK for packet n reached the master. The greater complexity of a sliding window protocol can be shown by TFTP which takes (with comments and command line processing) 2000 lines of C code.
The maximum sequence number is 
, where n = length of the ACK field. For MIDI SDS packets, n = 7 and the maximum sequence number is 127. Numbered SDS data packets enable the Go Back N Protocol.
Suppose the transmission time required for a frame to arrive at the slave plus the transmission time for the ACK to come back is non-trivial. For example, a 31.25 KBaud MIDI channel can transmit not more than 25 kbps because of framing bits. The SDS data packet is 1016 bits (as shown in section 1.2.3.1). To transmit the 1016 bit SDS data packet at 25 kbps takes 40 ms. The time is takes to transmit a 48 bit ACK is 2 ms. Propagation delay is equal to the amount of time it takes a bit to traverse the 15 meter maximum length cable (at about 2/3 the speed of light, this is trivial). If the SDS data packet is being written to floppy disk, the slave could take a long time to transmit the ACK. If the slave takes 500 ms to transmit the ACK, then the master does not get an ACK for 548 ms and so is blocked 500/548 = 91% of the time.
Suppose stop-and-wait has fixed-length frames and no piggybacking like Protocol 3 (par) positive ACK/retransmit protocol. The following discussion follows Tanenbaum with the exception of some notational changes and that it has been tailored to the MIDI SDS standard [Tanenbaum 1989].
NOTATION
If we assume that the channel is perfect, then t takes F/C seconds to transmit a frame and F/C + I seconds for the frame to arrive and get serviced. In F/C + A/C + 2I seconds the master has finished processing the ACK. In addition, only D data bits were sent in 2I + (F + A)/C seconds. So, for a perfect channel,
Therefore H + A + 2CI bits in the protocol overhead (which contribute nothing if the channel is error free). Channels have errors, however. If the master times-out in F/C + T seconds it will use F + CT bits of bandwidth. Total channel capacity for R bad frames and 1 good one is R(F +CT) + (F + A + 2CI).
To compute R we need to compute the probability of a successful transmission. This is given by
Therefore
We also need the probability of k attempts
Equation (31) can yield the average number of attempts if we take an expectation (average), 
. The average number of transmissions per frame is therefore:
proof:
subst. (33) into (32)
Q.E.D.
The average number of retransmissions per frame is one less, or:
using (35) and the fact that: Total channel cap. for R (= average number of bad frames) and 1 good one is R(F + CT) + (F + A + 2CI)
At this stage, Tanenbaum makes the assumption that the variance of the service time, I, is low. It is not clear that this assumption is warranted for every MIDI device. Certainly, it may be true for some device and for those devices:
subst (37) into (36) gives:
subst
into (36) yields:
where 
represents loss due to the header, 
represents loss due to the errors, 
and represents loss due to the stop-and-wait.
To proceed further we need to make more assumptions.
Assume that the prob. of a bit error is independent and that it is 
.
Then channel utilization is:
We are given header size (H), raw bandwidth (C), and number of data bits (D). We do not know the bit error rate, , or the service time I. Once these parameters are known, we can compute U for stop-and-wait.
Performance of the sliding window protocol
Assume that interrupt processing time is negligible so that I = 
= one -way propagation delay.
If < > 0 and the window is big enough to allow continuous transmission, 
then:
Therefore, as a function of , we can compute U. For MIDI this is given by Figure 1.2.3.5-7.
Figure 1.2.3.5-7. Utilization as a Function of .
We assume that the window size is big enough.
In fact, for a large enough window size, using the SDS data packet parameters, we compute utilization as using MAPLE:
D:=868:H:=148:C:=25000:A:=48:F:=D+H:
R:= L/(1-L):
L:=1-(1-Pd)*(1-Pa):
Pd:=1-(1-Pb)^F:
Pa:=1-(1-Pb)^A:
U:=(D/(H+D))*(1-L)-R*A/C;
Where the last term in (43) is adjusted for the reverse ACK traffic (which is two orders of magnitude smaller than the forward traffic).
In fact, given a window size of 127 packets, packet size of 1016 bits and a channel capacity of 25 kbps, equation (43) will hold for I < 2.5 seconds. After this time sequence number starvation will occur. Since this seems improbable, we leave this case unaddressed.
[ Index | Main Paragraph ]