WIXLIB

11 INTRODUCTIONDistributed real-time & embedded (DRE) systems are composed of many components, which perform various tasks by interchanging data with each other over anetwork [1]. Although there are many data interchange protocols available on themarket today, DRE system designers use the protocol provided by the architecturethey use for the system. For example, Common Data Representation (CDR) [2] isa binary data interchange syntax defined by the Object Management Group (OMG)that maps OMG’s Interface Definition Language (IDL) data types into a low-levelbinary representation. CDR is the default format used in the Common Object Request Broker Architecture (CORBA) [2] and Data Distribution Services (DDS) [3].Binary JSON (BSON) [4] is a binary discovery interchange format, that enables “onthe fly” discovery of elements when the sender and receiver have not agreed uponthe elements in a message. BSON is popularly used in architectures that are basedon MongoDB [5]. FIX Adapted for Streaming (FAST) [6] is a binary compressioninterchange format, developed by FIX Protocol Ltd. (FPL), and is widely used in thefinancial stock markets to interchange data with high throughput and low latency.Instead of choosing the default formats specified by the architectures, DRE systemdesigners and developers must gain in-depth knowledge about the available formats,do a quantitative evaluation of their performance, and be able to choose from thembased on the requirements for their system. If given a choice, DRE system designerschoose simple formats like CDR or Google’s ProtoBuf [7], which append new datato a buffer and send it across the network. This popular choice is based on theassumption that such protocols will consume less CPU processing time and latencyby simply collecting the data “as-is” and sending it. DRE system designers are notaware of frameworks that can let components choose from different formats at runtime.

2To date, there exists no quantitative studies to determine whether binary datacompression formats, such as FAST, or binary discovery formats, such as BSON, canperform better than traditional formats, such as CDR, and provide better processingtimes, throughput, and/or latency. With this understanding, the contributions ofthis thesis are: It details how to engineer a framework that allows DRE system designers toflexibly and seamlessly integrate different data interchange formats so that components can choose what format to use at configuration time. It evaluates and compares traditional formats, like CDR, against binary compression formats, like FAST, and binary discovery formats, like BSON, (1) toanalyze if it is possible to minimize the data usage without compromising CPUprocessing times, data throughput, and data latency; and (2) to answer thequestion if a compression technique, like FAST, will make any difference in today’s high speed Internet,which is in the range of Gigabits per second (Gbps).We perform the quantitative evaluation in the context of an Open Source Architecture for Software Instrumentation of Systems (OASIS) [8]. OASIS is a frameworkthat instruments distributed software systems without a priori knowledge of the instrumentation data transmitted over the network. To support our work, we modifiedthe OASIS framework to enable seamless integration of either data exchange format.Lastly, our experiments show that with increase in the data size, the throughputof FAST decreases only by 84.41%, whereas for CDR and BSON it is 96.16% and97.23% respectively. The latency to send each packet increases by 2510.73% forCDR, 3522.69% for BSON, and 541.3% for FAST. The increase in packaging andun-packaging times are 1985.12% and 1642.28% for FAST, compared to 3158.96%and 2312.50% for CDR, and 5077.98% and 3686.48% for BSON. Our results thereforesuggest using compression algorithms like FAST decreases memory usage while notcompromising on CPU and network times.

31.1 Thesis OrganizationThe rest of this thesis is organized as follows: Chapter 2 discusses some similar works that were done to compare different data interchange formats. Chapter 3provides a brief introduction to OASIS, and the CDR, BSON and FAST data marshalling formats. Chapter 4 gives a detail description of how we re-engineered OASISto support interchange of different data exchange formats. Chapter 5 discusses ourexperimental results. Lastly, Chapter 6 concludes this thesis with a brief summaryand a future research directions.

42 RELATED WORKSWe discuss related works that compare different data interchange formats in thischapter.2.1 Native Data RepresentationBustamante et. al. [9] propose a flexible messaging format called the Native DataRepresentation (NDR). In this format, a sender places the data on the wire in theformat that it maintains, i.e., it provides a record like structure, and provides thenames, the data types, the sizes, and the position of the elements in the record.The receiver too specifies such a structure, and compares the incoming message withits own structure by the element names, without giving much importance to thesize or position of the element. Their implementation of NDR, Portable Binary I/O(PBIO), can perform translation if there are differences in byte ordering, size of datarepresentations, or the compiler’s structure layout.They compare PBIO with traditional message passing formats used in high performance computing, such as Message Passing Interfaces (MPI) [10], Remote ProcedureCall (RPC) [11], and XML-based marshalling. They make MPI as their baseline, andshow that the encoding time of PBIO is better by three times, decoding by one time,than MPI and also show a 45% reduction in the round-trip time from the sender tothe receiver.However, the record format of PBIO is very similar to a FAST message, exceptthe field names and types are exchanged before hand by the sender and receiver.FAST also contains a field presence map in its message that is very similar to NDR.Therefore, the size of message produced by FAST and the time taken to package andsend it, will be less than PBIO.

52.2 Lightweight Communication & MarshallingHuang et. al. [12] describe a lightweight communication and marshalling (LCM),a publisher-subscriber message passing system, which can simplify sending low latency messages in real-time robotics applications. LCM decouples message implementation from its description by providing a platform and language independenttype-specification language. It provides easy to use and highly efficient tools for analyzing, marshalling and communicating data. An LCM encoded message begins witha message header, that contains a magic number, the version of the encoding protocol,sequence number, channel number that denotes the channel on which the messagearrived, and a 8 byte hash value computed for all the field names, and field typetuples for validating on the receiver side to decide whether the message was correctlyreceived.In their paper, Huang et. al also examine the bandwidth, latency and messageloss of the C and Java implementations of LCM, Inter-Process Communication (IPC)and the TCP transport of Robotic Operating System (ROS) [13]. They also comparethe efficiency of the data interchange computations in these three formats, by sendingdata from a laser scanner, a grayscale image from a camera, a list of 50 points in apath.Their results show that LCM performs better when both the amount of trafficand the number of subscribers are more. With only one subscriber, IPC performswell, but doesn’t scale well when the number of subscribers increase. ROS has highthroughput when its maximum queue length is infinity, but this costs message latency.Their encoding experiments showed that LCM C implementation performed betterfor messages that describe a path and images, whereas ROS C implementationwas the best for sending data from a laser scanner.LCM encoding is very similar to CDR encoding in the way it sends the headerinformation. Although this research is very specific to robotics applciations, theyprovide very good performance comparisons. However, this is different form our

6research because they are benchmarking LCM while comparing it to other messagepassing formats, whereas we are comparing only binary data interchange formats tosuggest which one is better to use.2.3 Self adaptive data marshallingAndrade et. al. [14] perform a systematic evaluation of Google’s Protobuf, LCM,and their own self-adaptive data marshalling approach. Their self adaptive datamarshalling approaches uses a delta comparison to monitor two consecutive packetsthat are sent and only sends the difference. Their research goals were to find howmarshalling formats can be systematically evaluated, and to know the performanceof these formats under different application-independent contexts.They perform a quantitative analysis of the three formats for integer and doublefields to compare the data sizes of the three protocols. They suggest Google ProtoBuf is a better choice when using all integer fields. When the number of messagefields increase LCM sends more compact data. Their self adaptive approach tends toperform better when there are large number of non-integer (double) fields because itassumes that the difference between two consecutive messages sent in a short span oftime is very small.However, Andrade et. al. do not provide any evaluation of performance, networkdelays, etc., only evaluating based on data sizes. An interesting observation fromthis research is that their self adaptive approach is very similar to field operators inFAST, which can perform delta, increment, or other operations on data.Although these related works compare different data interchange formats, theypropose a new data interchange format and benchmark them by comparing it withother formats. This is different from this thesis because we show how componentscan choose a data interchange format at run-time and quantitatively evaluate threeexisting formats to suggest when to use which format.

73 BACKGROUNDWe provide a brief overview of OASIS, and the CDR, BSON and FAST data interchange formats that we used to perform this quantitative analysis.3.1 Open Source Architecture for Software Instrumentation of SystemsOpen Source Architecture for Software Instrumentation of Systems (OASIS) is aservice-oriented architecture that instruments DRE systems without a-priori knowledge about them. Figure 3.1 gives a high-level overview of the different componentsin OASIS.A Software Probe collects metrics of interest from DRE systems at the applica-mana gesEINodeDataChannel interface providesSoftwareProbe interface usestion or system level, such as processor or memory or network information, and E Application ContextusesProcessorProbeT&E ManagerlistsDataHandler interface OASIS ContextFigure 3.1.: High level overview of OASIS.

8it to an Embedded Instrumentation Node (EINode). A probe definition language(PDL) compiler generates the stubs and skeletons required for marshalling the dataand sending it across the network.An Embedded Instrumentation Node (EINode) manages all the softwareprobes in an application context. An EINode is identified by a Universally UniqueIdentifier (UUID), and a human readable name. In the current OASIS framework,the EINode provides the software probes with a CDR packager to marshall the data.We changed this framework to flexibly integrate other data interchange formats, andthis is discussed in details in chapter 4.A Local Data Channel is an abstraction that sends instrumentation data, locally from the different software probes to the EINode in their context. This abstraction allows implementation to strategize the data locally before sending it across thenetwork, such as collecting the packets in a queue or speculating them.A Data Channel abstraction allows the EINode to send instrumentation data tothe Data and Acquisition Controller (DAC) over the network. DACs can choose fromdifferent middleware technologies, such as CORBA or DDS, to send the instrumenteddata. The TAODataChannel implementation shown in the Figure 3.1, is the CORBAimplementation of the data channel.The DAC receives the instrumented data from various EINodes, and controlsaccess to it. External clients can connect to the DAC to get the collected instrumentation data. The DAC also manages various data handlers that un-package the dataand store it in a file or database. JavaScript Object Notation (JSON) [15] data handler, Websocket [16] data handler, SQLite data handler are some of the data handlersthat currently exist in OASIS.Test and Execution Manager (TnE) is the main entry point for externalclients to access the data from the DAC. It acts as naming service to list all theexisting DACs.

93.2 Binary JSONJSON is a data interchange format that transmits human-readable data in theform of attribute-value pairs. It has largely replaced XML in asynchronous communication systems, and enables humans to read and write data easily while also makingit easy for machines to parse and generate it. A JSON documents consist of eitherattribute/value pairs of data or a collection of data, such as arrays or vectors, otherembedded JSON documents, or a combination of them. The elements in a JSONdocument are differentiated by braces or brackets.BSON is a lightweight binary-encoded data interchange format that serializesJSON documents, and is the primary storage and transfer format in MongoDB. UnlikeJSON, elements in a BSON document are stored in an ordered list, consisting of itsnames, types and values and not differentiated by brackets. Table 3.1 [4] showselement types of various basic data types in BSON.Element typeData type0x01Double - 64-bit binary floating point0x02String0x05Binary data0x08Boolean0x09UTC datetime0x1032-bit integer0x11Timestamp0x1264-bit integer0x0ANull value0x03Embedded Document0x04ArrayTable 3.1.: Element types in BSON for standard data types

10BSON provides a wider range of data types than JSON, and also supports embedded documents and arrays. Custom data types can also be represented using BSONextensions. The “schema-less” property of BSON makes it more flexible when compared to formats such as Protobuf [7]. BSON minimizes the spatial overhead and theelement scan speed considerably when compared to JSON—making it lightweight andeasily traversable. Because it uses C-like data types, it performs efficient encodingand de-coding of data.For example, to encode the value system time:1345, where system time is thekey, and 1345 is the value, the BSON document would look as shown in Listing 3.1.( 0 x16 0 x00 0 x00 0 x00 ) 0 x10 ( s y s t e mt i m e 0 x00 )( 0 x05 0 x41 0 x00 0 x00 ) 0 x00Listing 3.1: Data marshalled using BSONIn Listing 3.1, the parenthesis are for illustration purposes only. The first set ofparenthesis represent the size of the document, which is 22. The next byte representsthe element type, which is 32-bit integer. The second set of parenthesis represent thenull-terminated key system time. The third set of parenthesis represent the value1345 in hexadecimal. Finally, the document terminates with the null-byte 0x00.The corresponding JSON document will look as shown in Listing 3.2.{ s y s t e m t i m e : 1345}Listing 3.2: Data marshalled using JSONIn Listing 3.2, the braces are part of the format. The BSON implementation thatwe integrated into OASIS is BiSON [17].3.3 Common Data RepresentationCDR is a data interchange format specified by the OMG that maps OMG’s Interface Definition Language (IDL) data types into an octet stream for transfer betweendifferent Object Request Brokers (ORBs) and Inter-ORBs. Octets are defined as

118-bit values, and an octet stream is a memory buffer that can to be sent over thenetwork. Octet streams have a well-defined beginning, are arbitrarily long, but finiteand contain n octets, indexed from 0 to n-1.CDR defines two kinds of octet streams: messages and encapuslations. The basicunits of information exchange in General Inter ORB Protocol (GIOP) are messages.A message contains a message header followed by the message data. A message headercontains the following fields: Magic that identifies GIOP messages, whose value is always the four uppercasecharacters “GIOP” encoded in ISO Latin-1 (8859.1). Version specifies the major and minor versions of GIOP that is being used. Byte Ordering specifies if the rest of the message follows big-endian representation, denoted by 0, or little-endian representation, denoted by 1. Message type: specifies the message type such as request, reply, etc. as anenum value. Message size: specifies the number of octets in the data that follows theheader. This is also encoded by the byte ordering specified above.Octet streams that are marshalled independently from any particular messagecontext are called encapsulations. An encapsulated octet stream can be representedas the OMG IDL’s opaque data type sequence octet , which can be included inanother message or encapsulation for subsequent marshaling without changing thedata or the byte ordering in the encapsulation’s octet stream.CDR moves values of primitive data types in and out of octet streams by aligningthem at the size of their type. If necessary, the value of a primitive data type willbe preceded by an alignment gap, i.e., an unknown value of octets. The alignmentgap is equal to the minimum size required to align the primitive that is being followed. Table 3.2 [?] shows the alignment requirements for the OMG IDL primitive

12Primitive typeOctet Alignmentchar1wchar1octet1short2unsigned short2long4unsigned long4long long8unsigned long long8float4double8long double8boolean1enum4Table 3.2.: Octet Alignment requirements of primitive data types in CDR.types. Alignment permits efficient data handling by different architectures, since noinformation of the underlying types is given in the message and assumes that thesender and receiver have prior agreement on the types. However, CDR can enablecommunication between machines that have different byte ordering because it cantranslate from big-endian to little-endian or vice versa.For constructed types, such as structures, unions, arrays, sequences, etc. thereis no alignment specified except for those of the primitive types of which they arecomposed.

13To send the message idle time:1234, system time:3451, user time:2341, wherethe values are long (4-byte integer) values in CDR, it would be encoded in big-endianformat as shown in Listing 3.3.( 0 0 0 0 0 0 0 0 00000000 00000100 1 1 0 1 0 0 1 0 )( 0 0 0 0 0 0 0 0 00000000 00001101 0 1 1 1 1 0 1 1 )( 0 0 0 0 0 0 0 0 00000000 00001001 0 0 1 0 0 1 0 1 )Listing 3.3: Data marshalled using CDRThe parenthesis are for illustration purpo

Graduate School Form 30 Updated 12/26/2015 PURDUE UNIVERSITY GRADUATE SCHOOL . Thesis/Dissertation Acceptance . This is to certify that the thesis/dissertation prepared . By Entitled . For the degree of Is approved by the final examining committee: To the best of my knowledge and as understood by the student in the Thesis/Dissertation