Low Bandwidth Call Trace Loggingfor Sensor NetworksRoy Shea, Young Cho, and Mani SrivastavaUniversity of Los Angeles, California, [email protected], [email protected], [email protected]. Call traces can provide detailed insight into the operation ofdistributed embedded systems. Developers inspect traces to understandand debug systems using manual and automatic techniques such as datamining. Correlation of traces between nodes provides a network levelview of system. These traces are typically gathered by logging a globallyunique identifier for each called function. Unfortunately, this naive calltrace gathering technique results in excessive consumption of the limitedmemory, bandwidth, and energy resources available in wireless sensornetworks.This paper proposes three new call trace gathering techniques that aredesigned specifically for the computing platforms with extreme resourceconstraints. The first technique uses local name spaces and caller sidelogging to significantly reduce the bit size of function identifiers. Thesecond technique reconstructs call traces from a log of the runtime con-trol flow decisions made by a program. The third technique performs anovel reduction over a program’s control flow graph to limit logging tocontrol flow nodes effecting runtime call decisions. Our work automate sthe insertion of logging statements into source code for all the techniquesdescrib ed above.Our experimental results show promising outlook where two of the tech-niques reduced the size of the log to less than 15% of traces producedby traditional methods. These savings make the new call trace capturingtechniques attractive additions to the toolbox employed by developersand users of wireless sensor networks.1 IntroductionEvent traces are emerging as a powerful technique that allow developers andsystem maintainers to peer into the too often obscured operation of sensor net-works [1–7]. Function call traces are one of the most flexible and useful formof event traces. Function call traces are intuitive to developers who already di-vide functionality in their program into individual functions. Such traces arealready established in debugging through the ubiquitous appearance of functionback traces in debuggers. More complicated event abstractions can be capturedby call traces. Examples includ: interrupts handlers implemented as an asyn-chronous function calls, network message send events triggered by a correspond-ing network send functions, and context switches controlled by a kernel schedulerfunction.Sensor network and general system tools that gather function call tracesalready exist. These tools tend to focus on trace processing and not the efficiencyof call trace generation. This paper acknowledges the value of call traces andmoves forward with a new question. How can function call traces best b e gatheredin sensor networks systems?Implementations for gathering system call traces that we’ve encountered in-strument functions to log a globally unique identifier (ID) when the functionis called. This technique is simple to implement and easy to understand, butwasteful in its creation of excessively verbose logs.This paper attacks the waste created by unique function ID logging with asingle observation: from a given point in a program only a subset of functionsmay next be called. This observation is critical because the overhead from calltrace logging is directly related to the bit width of logged IDs. Globally uniqueIDs require log2(n) bits, where n is the number of functions in the program.Fewer bits can be used if a smaller set of functions can be considered.We begin reducing call trace log sizes by using functionally scoped identifiername spaces. Only a set of functions are reachable from a given function. Usingthis reduced set to generate an ID unique to the caller provides immediate gainsover the global identifier approach. In a sense we transition away from using asingle “global dictionary” requiring a greater number of bits to encode uniquefunction IDs. Instead we propose using multiple “locally scoped” dictionariesthat are each customized to contain only the functions reachable from within agiven function. These locally scoped dictionaries create more compact identifiers.The first contribution of this paper is the description and evaluation of loggingvia local name spaces.We continue by pushing the initial observation, that only a s ubset of functionsare reachable from a given program point, to an extreme using “statement level”dictionaries. Where locally scoped dictionaries consider only functions reachablewithin a given function, statement level dictionaries consider only functions im-mediately reachable from a given program statement. A statement level dictio-nary needs at most a single entry for non-control flow statements since at mostone subsequent call may be reached (ignoring interrupts, an issue described indetail in section 3). Control flow statements with n branches require at most nentries, one entry to describe the first call along each branch. In this extremeview the logged data becomes the path taken through the control flow graph(CFG) of a program. Function call traces can then be inferred from the recordedcontrol flow path. The second contribution of this paper is a discussion andevaluation of inferring call traces from runtime CFG path logs.CFG path logging overshoots the original goal of capturing function calltraces. CFG path logs provide significantly more information than simple func-tion call traces. Unfortunately, this additional information comes at a log sizeincrease that reduces the benefits of using extremely concise statement leveldictionaries. The third contribution of this paper is the description and evalu-ation of an algorithm to reduces a program’s CFG without hindering functioncall trace inference. The reduction prevents logging at CFG nodes that don’tdirectly effect subsequent function calls.In summary this paper describes in detail three call trace gathering tech-niques: using local functionally scoped identifiers, using logs of runtime CFGdecisions, and using reduced CFG. The call trace gathering techniques are com-pared to each other and to the baseline obtained from global ID logging. Thisevaluation guides developers in adding efficient call trace logging frameworks totheir systems.Emerging tools to provide insight into the workings of sensor networks andmore traditional systems are described in section 2.