Packets are 'too hot' to drop.
Routing data packets from acquisition to display is an important aspect in the real-time visualization process. Optimizing the packet routing mechanism will improve the scalability of the design should new instrumentation need to be added or data rates increased. This chapter proposes a new packet routing mechanism and discusses its improvements over the original method. The new method utilizes concurrent threads for asynchronous communication between the visualization and acquisition systems and provides message queues as packet buffers.
During data acquisition in the field many packets were not visualized. They are dropped somewhere between the spool process acquiring them and the RTQC process displaying them. The original packet routing scheme, currently used by SOAR during data acquisition in Antarctica, has no mechanism for keeping track of dropped data packets or for adjusting the flow of data packets to the visualization computers. The original design also does not measure or monitor packet acquisition rates or network throughput for the different data streams accepted by the acquisition machine. Concurrent programming (e.g. threads programming) was not used to facilitate a smooth flow of data to the display processes. As a result, real-time visualizations ran irregularly, and it would be difficult to extend the system to accommodate additional instrumentation or higher data rates. Because the original system was created very quickly, no formal documentation existed describing the packet routing design, making the code difficult to understand and complicated to adjust. (See Figure 4.1 and Figure 4.2 for graphical representations and explanations of the original packet routing scheme. Each packet routing processes is individually diagrammed and pseudo-coded in Appendix B).
A new packet routing system was developed to overcome the shortcomings of the original system. The basic design goal of the new system was to increase network throughput without compromising the data acquisition and storage processes. To achieve this goal, separate child processes are created for writing data packets to storage and for passing that data on to the visualization displays, utilizing multiple independent threads for sending the data packets over the Ethernet. Multiple threads and independent processes for recording and routing packets allow for greater concurrency during program execution, resulting in more data for visualization, accommodating faster acquisition rates and providing for additional instrumentation.
An efficient packet routing mechanism starts with a design illustrating the structure, relationship, and interaction of elements within the system. The design should be modular to preserve flexibility. The design should be clearly drawn so as to be understandable by the people using the system, not just the person writing the code. Each design element should be associated with a specific task. Each task should support advancement toward the final goals. The program code should then be written using this design as a template.
The primary goals of the data acquisition system are to timestamp all data received, write out the data in a common format packet, and record this time-stamped data packet to permanent storage. Secondary to the main goals is to make the recorded data available to display programs for real-time visualization and equipment monitoring. These are the basic system goals for the new packet routing scheme.
Two routing objectives drive this new packet routing scheme. One objective involves overlapping the operation of data packet storage with data packet routing. A computer hardware design technique, pipelining, allows multiple simple instructions to execute concurrently but within different pathways, or pipes, resulting in the development of fast CPU chips. Just as pipelining allows multiple simple computer instructions to execute in parallel and speed up the operation of CPU's, overlapping, in time, the operations of writing packets to storage and routing packets to visualization stations will result in less delay and greater throughput at the display end. Visualizations will proceed more smoothly and more in step with data acquisition.
The second objective requires keeping process blocking to a minimum and creating sufficient points of yield within the running code that relinquish the CPU to concurrently executing processes. Program blocking occurs during a Send() operation, and persists until the sending process receives a reply from the receiving process. A process also blocks during a Receive() operation, until the receiving process receives an acknowledgement from the sending process. Blocking ensures complete data transmissions and retrievals by the sending and receiving processes. Without blocking, the memory used to hold the in-transit data could be overwritten before data transmission is completed, resulting in data loss. Nevertheless, a process does not perform any useful work while it is in a blocked state. Within the new packet routing design blocking occurs for very short time intervals, while a new packet is transferred from the acquiring process to the recording process, and by those processes actually waiting for more data (i.e. a disk-writing process waits for packets to write to storage, display processes wait for data to visualize, threads wait for data requests from executing display processes).
Three cooperating processes are needed to route packets from the acquisition computer to the visualization stations in the new design (Figure 4.3 and Figure 4.4).
One process receives packets from the data acquisition processes, another process writes data packets to permanent storage, and a third process routes packets to the visualization stations, preserving time-acquired order and keeping up with current data acquisition rates. The new packet routing design tries to maintain a basic similarity with the original system.
The new Disk-Writer process was created by separating packet acquisition from packet storage within the original Spool process (Figure 4.5). Disk-Writer continually waits for packets and records all data packets it receives to two permanent storage disks. This is the time-limiting step within the packet routing scheme. Data can be visualized only as fast as Disk-Writer can record the data to disk.
The Spool process begins by spawning the Disk-Writer process then going into a receive-blocked state while waiting for new data packets from the data acquiring/packet creating processes, hipac and dsa, described in Chapter 2. When a new packet is received, Spool becomes unblocked, but returns to a send-blocked state while passing the newly acquired packet to Disk-Writer for storage. Once acknowledgement arrives from Disk-Writer, Spool unblocks and writes the data packet to a mailbox (i.e. a message queue), where the packet is later retrieved by the Coordinator process, described in the following section. Spool then sends Coordinator a non-blocking notification message called a proxy to announce the arrival of the new packet entry within the mailbox. This notification is necessary to prevent Coordinator from wasting CPU cycles polling the mailbox for new packets and to help Coordinator keep track of the new packet arrivals.
Triggering a proxy is a non-blocking message-passing technique used primarily for event notification. The proxy's message is created ahead of time and remains constant so there is no chance of it being overwritten; this is the reason it can be sent without blocking. A proxy message is received like any other passed message and can be handled within a receive loop.
The original Spool process performs three functions (Figure 4.6): (i) packet acquisition, (ii writing packets to storage, (iii) packet transfer to the grouper process. The time consuming- step is the external disk access. The new design has separated out the disk writing phase so that it can proceed in parallel with the remaining packet routing operations. The new Spool uses a blocking Send() operation to pass packets to Disk-Writer. The only time Disk-Writer will not be ready to receive a packet is when a previous packet is being recorded to disk, so blocking is acceptable at this time.
The Coordinator process is the main packet routing process. Coordinator begins by spawning a Spool process for packet retrieval and by creating the mailbox for Spool-to-Coordinator packet transmissions. The mailbox replaces the original grouper process (Figures 4.1 and 4.2). Coordinator continuously waits for new packet notifications from Spool and registration requests from visualization processes. New packets are routed to display computers via an Ethernet link in response to their packet requests. The Coordinator becomes multi-threaded to asynchronously route data packets across the Ethernet link to the awaiting displays. The Coordinator process maintains much of the functionality found within the original router process such as retaining a list of registered clients, and retrieving newly acquired packets for dispersal to these clients (Figure 4.7).
Creating multiple threads facilitates the progress of data packets from Spool to the data visualization computers. Coordinator creates a Communication-thread for each registered display process. When a display process is ready to receive packets it registers with the Coordinator using a 'SETUP' message. Encoded in this message is a process name and a list of data stream types the process wishes to visualize. This list of data streams is encoded within an unsigned long integer variable. Each bit of this long integer refers to a different data stream. A bit value of 1 indicates that a display wishes to receive data packets of that stream type. A bit value of zero specifies a stream type not required. Coordinator maintains a linked-list of registered clients with the data packets that each wishes to receive (Figure 4.8). A Communication-thread only sends data packets to a single client and a display process requests data packets only through its private Communication-thread. Blocking between a Communication-thread and a display process during message passing will not affect the operation of the other running processes.
Message queues were chosen as the IPC (inter-process communication) method for packet transmission between processes. Since data visualization is occurring asynchronously among the various display systems, message queues allow asynchronous data retrieval and provide an ideal program location for implementing packet-dropping algorithms should data visualization fall behind data acquisition. For example, if a mailbox is full when a new packet is ready to be written, that new packet can be discarded.
After Coordinator reads a new data packet from its mailbox, the list of registered clients is examined for those visualizing the current data stream type. The current packet is then copied to individual mailboxes associated with each of those display processes and the corresponding threads are notified via proxy messages. Each time a display process is ready to visualize more data it Sends() a 'PING' message across the Ethernet to its Communication-thread. The reply is the next available data packet from within its mailbox.
Each mailbox maintains packets in received order so that a display can be assured of getting its data sequentially.
Data requests from the visualization computers and new packet notifications from the Coordinator are received asynchronously by the Communication-threads. A packet can only be sent to a display process in reply to a 'PING' message, and a 'PING' message can only be replied to when a new packet is available. Four process states are possible based on the receipt of these two messages (Figure 4.9). Each Communication-thread maintains the current state by specifying the current PING-PACKET status.
New packets are sent to a visualization computer when a thread achieves the current state of 'PING-PACKET'. A 'PING' message from a display sets the 'PING' half of the current state and a new packet notification from the coordinator sets the 'PACKET' half of the current state. After transmitting packet data a thread checks its mailbox. If full, a new packet is retrieved to free up a mailbox slot and make the thread ready to Reply() should a new packet notification not arrive before the next 'PING'. In this case, the current state advances to 'NoPING-PACKET'. If the mailbox is not full, the current state advances to 'NoPACKET-NoPING', the program's initial waiting state.
Since the data acquisition instrumentation is only available in the field during actual geophysical surveying, packet-driver programs were needed to drive both the old and new packet routing schemes for testing and program analysis. Initially, this was accomplished by reading previously collected data files and sending packets to a spool process (new Spool or original spool) just as the acquisition processes, hipac and dsa, do. This technique also allows previous surveys to be rerun and reexamined. Two drawbacks with this technique emerged during performance analyses. Data files are quite large (i.e. ~1G) and are not easily stored on the acquisition computer. Storing the data elsewhere causes extra Ethernet traffic that interferes with testing. Also, timing the sending of data to reflect actual acquisition rates is more difficult to maintain since data has to be read in and examined before being sent.
Data transmission rates are more accurately simulated during testing using a system of packet drivers. This system was designed with three processes: (i) a radar packet driver, (ii) a serial packet driver, and (iii) a timer. The radar packet driver replaces dsa, the process acquiring radar data and creating radar packets, the serial packet driver replaces hipac, the process creating packets from acquired serial stream data, and the timer allows both drivers to run for a specified length of time, concurrently. Upon expiring, the timer sends a 'QUIT' message to the currently running spool process. When a spool process receives a 'QUIT' message it stops waiting for messages and passes the 'QUIT' message on to the other running processes. A process receiving a 'QUIT' message writes out timing statistics and stops running.
The radar packet driver holds one radar packet in memory and Send()'s this packet to the currently executing spool process each time the radar timer expires. The serial packet driver holds one serial packet of each type in memory and associates an individual timer with each packet type. Each timer expires at the acquisition rate of its associated data and the driver Send()'s the respective data packet to the executing spool process which Reply()'s with an empty acknowledgement message, to complete the message-passing routine, and then time-stamps the data packet. Packet timers can be set to expire at any rate. When a spool process is no longer receiving messages, the packet drivers break from their packet sending loops and stop executing. A real-time Posix-compliant clock is used both for timers and time stamping, with resolution to 20 nanoseconds.
A packet enters the packet routing system via a spool process and exits by way of a display program (Figure 4.10). For performance testing, a display program needs to ask for packets quickly with as short a turn-around time as possible. If a display program is too CPU intensive, packet delivery, by the Coordinator, will proceed at a greater rate than packet retrieval by a display program, and packets will be dropped before being visualized. The generic display program runs continually, 'PINGing' its Communication-thread for new data, recording each packet's arrival time and travel interval, and exiting when a 'QUIT' message is received.