Grigore Burloiu
email: gburloiu@gmail.com

Arshia Cont
email: cont@ircam.fr

Non-overlapping, Time-coherent Visualisation of Action Commands in the AscoGraph Interactive Music User Interface

Integrated authoring and performing of mixed music scores, where musicians interact dynamically with computer-controlled electronics, is enabled by the Antescofo state-of-the-art software package. Composers are able to plan computerised actions through a dedicated programming language, and performances are then synchronised in real time. AscoGraph is the dedicated graphical interface that allows users to configure Antescofo behaviours and visualise their layout over a mixed music score. This paper presents developments in the direction of increased clarity and coherence of AscoGraph's visualisation of computerised action scores. Algorithms for efficient automatic stacking of time-overlapping action blocks are presented, as well as a simplified model for displaying atomic actions. The paper presents the improvements in score readability achieved, as well as the challenges faced towards a complete representation of dynamic mixed scores in the Asco-Graph visual environment.

INTRODUCTION

This paper describes a model of interactive visualisation for composition and performance of mixed music repertoire. Mixed music is commonly referred to as the live association of human musicians with interactive software/hardware during live music performance; as well as the authoring (composition) within this mixed medium. Among common practices of mixed music, score following has been an active line of research where the computer is equipped with a real-time machine listener that dynamically aligns a musician's performance to a pre-written music score and decodes performance parameters, which can be used to interpret and evaluate computerised actions. One can think of such a compositional paradigm as an extension of musical automatic accompaniment application, where accompaniment playback is replaced by programs acting on various aspects of sound and music computing.

Visualisation for mixed music is a challenging task for several reasons. The score is a joint combination of two main components: one that describes expected events from human musicians as extensions of classical musical notation; and one that describes computerised, or electronic actions. The two components are strongly-timed and most often aligned during authoring and synched dynamically during performance. Computerised actions in turn have heterogeneous time models: they can be discrete message passing, or continuous curves, or dynamic calculations. Their temporal ordering can be described as sequences of delays expressed in absolute or relative time; actions can be hooked sequentially (through delays inside a single sequence) or vertically (to an external event, condition or synchronisation pivot). Composers and performers are proficient at dealing with authoring and interpreting a variety of such parameters.

Enabling this level of expressivity in mixed music composition and performance is the goal of the Antescofo software, a state-of-the-art system for mixed music composition which integrates a score following engine [START_REF] Cont | Antescofo: Anticipatory Synchronization and Control of Interactive Parameters in Computer Music[END_REF] and a synchronous reactive programming language [START_REF] Echeveste | Operational semantics of a domain specific language for real time musician-computer interaction[END_REF]. The user/composer is able to plan complex dynamic electronic actions which the system launches and controls during the performance, in sync with the live musicians' tempo. First described in [START_REF] Coffy | AscoGraph: A User Interface for Sequencing and Score Following for Interactive Music[END_REF], AscoGraph is the dedicated graphic development environment which enables visual feedback for authoring and performing Antescofo mixed scores.

The AscoGraph workspace consists of two main sections: the textual score editor and the graphical editor, which in turn is split into an instrumental section and an electronic actions section. The instrumental view and electronic view are coupled in musical time along a common horizontal timeline. During a performance, Antescofo's score follower determines the position of AscoGraph's graphical cursor along the timeline.

This paper presents updates to AscoGraph's electronic action view, developed with two directions in mind: (1) a clearer and more time-coherent visualization of Antescofo scores, and (2) a step towards a complete, self-contained visual notation format for mixed music scores. Section 2 presents the problem of overlapping action blocks, recast as a subset of the two-dimensional strip packing problem. The following section shows the three proposed algorithms for re-arranging action blocks. Section 4 tackles the issue of coherence between block width and musical time. We conclude the paper with an evaluation of the present model and future perspectives.

PROBLEM DEFINITION

We distinguish between physical time (measured in seconds) and musical time (measured in beats). The amount of physical time elapsed between actions depends on the tempo detected during performance, and on the active synchronisation strategies [START_REF] Echeveste | Operational semantics of a domain specific language for real time musician-computer interaction[END_REF]. Meanwhile, Antescofo scores are specified in musical time. Since AscoGraph was primarily designed as a score visualisation tool, it employs a musical timeline. When a physical time unit is specified in a score (e.g. "after 2 seconds"), in order to display it Asco-Graph must first translate it to an ideal musical time (e.g. "after 4 beats at 120bpm").

Fig. 1 shows an example of the original AscoGraph action block arrangement style. Here, each of the four notes (drawn in red in the instrumental view's piano roll) has one corresponding action group block. Durations can -and often do -differ between the length of a note and that of its associated electronic actions. While actions within a single group (e.g. Group FOUR) are stacked consecutively downwards, when two different action groups are partially concurrent, the second group is drawn over of the first. Consequently, the first group's duration is no longer clearly shown; things become even more confusing when overlapping automation curves (e.g. the one in Group ONE) are involved.

In order to rectify this loss of coherence and clarity, the need arises to stack action groups in downward non-overlapping order, similarly to how elements within groups are arranged. As the challenge becomes one of efficient management of 2D space, it is useful to describe it as a twodimensional strip packing problem. A subset of bin packing, strip packing is used in areas ranging from optimizing cloth fabric usage to multiprocessor scheduling [START_REF] Thöle | Approximation algorithms for packing and scheduling problems[END_REF]. Algorithms seek to arrange a set of rectangles within a 2D space of fixed width and bottom base, and of infinite height. In our present case, the width of the strip corresponds to the total duration of the piece, and the rectangles to be placed are the action group blocks.

A particular constraint separates our problem from the rest of the bin packing literature. Unlike in existing bin packing problems, all AscoGraph action blocks must retain their X coordinate along the time axis. Since we are not allowed to "nudge" blocks horizontally, relying on existing packing algorithms becomes impractical.

PACKING ALGORITHMS

We introduce three new algorithms for stacked action group display in AscoGraph's graphical editor. The user can switch between one of them and the original display style through the application's View menu. The appropriate option will depend on score complexity and the user's personal taste.

Please note: following bin packing convention, we shall consider the rectangles as being placed on top of the strip base. Naturally, in the AscoGraph environment the situation is mirrored and we build downwards starting from the upper border.

First Fit (FF)

The first option is the trivial solution of placing the blocks in the first space they will fit, starting from the base. The benefits of this option are speed and predictability: blocks are placed in the order in which they appear in the source code text, which is also their scheduled temporal order.

The downside can be intuited from Fig. 2a andb. We propose a worst-case scenario: a set of blocks with increasing heights and, for simplicity, all equal widths. While FF would stack them on top of each other (Fig. 2a), the optimal method would stack them two by two (Fig. 2b), so that the maximum height is given just by the final two elements.

First Fit Decreasing (FFD)

Note that in the previous case, the optimal configuration can be reached by simply reordering the blocks by height. This insight lies at the root of the classic FFDH strip packing algorithm [START_REF] Coffman | Performance bounds for level-oriented two-dimensional packing algorithms[END_REF]. In our case, the FFD algorithm orders the blocks by non-increasing height, after which the First Fit process is applied.1 Fig. 3a shows an FFD arrangement, along with the optimal solution at Fig. 3b.

First Fit Decreasing Towers (FFDT)

Again, the optimal configuration in the previous example points towards the next algorithm. We propose a greedy heuristic that builds upon FFD while tackling AscoGraphspecific situations like one action block sharing time with several blocks on both sides of it. The basic goal is to minimise gaps, such as the one between blocks 2 and 3 in Fig. 3a.

The FFDT algorithm first orders all blocks as in FFD. Then, action group towers are defined at the time-axis inbetween two or more group blocks. Their height is equal to the sum of the heights of their component blocks. For instance, in Fig. 3a andd The entire width being now split along these virtual vertical strips (towers), we are able to refine the ordering of the blocks. The first criterion is the decreasing maximum height among the towers each block is a member of. If this maximum tower height is equal for two blocks, then the second criterion is decreasing number of towers each block is a member of. If this number is equal as well, we leave the FFD ordering (non-increasing block height) untouched. By definition, the maximum tower height is a definite lower bound of any AscoGraph strip packing configuration. Therefore, in the FFDT heuristic the tallest tower will always be placed first, in an attempt not to overshoot this lower bound. Among its component blocks, the ones that are shared with many other towers are dropped closer to the base -the intention again being to maintain tower integrity as much as possible. Lastly, as with FFD, tall blocks are prioritised so as to fill gaps efficiently. An AscoGraph use-case comparison of the three algorithms can be seen in Fig. 4. In it, we illustrate the orderliness of FF and the compactness of FFDT, with FFD a potentially useful compromise between the two.

TIME COHERENCE OF ATOMIC ACTIONS

A basic element in Antescofo's reactive language is the atomic action. Atomic actions can be part of larger dynamic constructs, but often they are simple messages to be triggered at a specific point in time. Since they are instantaneous, their visual representation taking up horizontal space on the action timeline is discordant. Moreover, as figures 1 and 4 show, they often clutter the workspace unnecessarily.

Our solution to more accurately represent action messages is to group all instances from a specific hierarchical level and display them on a single line as small circles, or conceptual points. When the mouse hovers over such a point, a list of the messages it contains is shown. Fig. 5 shows the expanded list for Group THREE; the messages are set at 3 different points in time, which is why 3 points are present in the message line.

Our new model is fully time coherent and considerably clearer than before. The user experience improvement over the classic model becomes most obvious when dealing with complex scores with many messages -see Fig. 6. With the timeline fully zoomed out, the old model offers a less accurate overview of the activity in the electronic score. Action durations are impossible to estimate; the most egregious problem being at the final note of the score, where, with

CONCLUSIONS AND FUTURE WORK

We have shown an improved layout mechanism for electronic action groups over a musical timeline in AscoGraph. By stacking action group blocks we ensure information integrity and coherence, while expanding the vertical real estate used. The most basic stacking method, First Fit, is also the most easily readable option for scores of moderate depth. We also proposed two increasingly efficient stacking algorithms, FFD and FFDT, for scores containing larger concentrations of actions per time unit. While superior algorithms are technically conceivable (possibly a metaheuristic scheme built on top of FFDT), the present options were deemed appropriate for the practical use and the processing overhead of the AscoGraph software.

Finally, we have introduced a method of displaying related messages on a single line which preserves group hierarchy. The main advantages are time coherence and vertical compactness. Still, this model can be seen as a compromise in our quest for a completely specified, self-contained visual notation format which we proposed in the introduction. Dynamic constructs from the Antescofo language are in a similar situation. For instance, a Curve whose duration is a dynamic variable: in this case, AscoGraph cannot know its exact plot over time before execution.

Therefore, one direction of future research is a performance simulation mode, decoupled from the compositional display described thus far, in which all messages, Loops and other dynamic constructs are represented as they "happen" in an offline simulation. This function is currently in prototype form, having been first described in [START_REF] Coffy | AscoGraph: A User Interface for Sequencing and Score Following for Interactive Music[END_REF].

However, the need remains for a graphic compositional model that clearly describes dynamic behaviour and action results. With the growing crystallisation of Antescofo's language into a mature, stable package, the path is now open for research in this direction.

Figure 1 :

 1 Figure 1: The "classic" action block display in Asco-Graph. The musical timespans of Groups ONE, TWO and THREE are not represented clearly because of the overlapping of group blocks.

Figure 2 :

 2 Figure 2: Horizontally constrained strip packing. Boxes are numbered in temporal (horizontal) order. This layout is arranged by FF in (a) and optimised by FFD in (b).

Figure 3 :

 3 Figure 3: Horizontally constrained strip packing. Boxes are numbered in temporal (horizontal) order. This layout is arranged by FFD in (a) and optimised by FFDT in (b).

  the rectangle 2 is part of four towers: T a {r 1 , r 2 }, T b {r 2 } 2 , T c {r 2 , r 3 } and T d {r 2 , r 3 , r 4 }.

Figure 4 :

 4 Figure 4: The three AscoGraph packing options.

Figure 5 :

 5 Figure 5: Time-coherent message circles display

Figure 6 :

 6 Figure 6: Comparison of old and new AscoGraph models over a complex score.

The difference to the classic FFDH algorithm is the absence of horizontal levels. New blocks are stacked at the minimum possible altitude rather than a common level.

A minimal tower only contains one action block.(a) FF -action blocks are placed as close to the baseline as possible, in the order in which they appear in the code. (b) FFD -blocks are ordered by height before being placed. (c) FFDT -blocks are ordered according to a gapminimisation heuristic before being placed.

This project was partially funded by the French ANR INEDIT Project.


Hitoshi Asaeda
email: asaeda@nict.go.jp

Kazuhisa Matsuzono

Thierry Turletti

Contrace: A Tool for Measuring and Tracing Content-Centric Networks

Keywords: CCN, NDN, ICN, Contrace, In-network cache, Measurements I

Content-Centric Networks (CCNs) are fundamental evolutionary technologies that promise to form the cornerstone of the future Internet. The information flow in these networks is based on named data requesting, in-network caching, and forwarding --which are unique and can be independent of IP routing. As a result, common IP-based network tools such as ping and traceroute can neither trace a forwarding path in CCNs nor feasibly evaluate CCN performance. We propose "contrace," a network tool for CCNs (particularly, CCNx implementation running on top of IP) that can be used to investigate 1) the Round-Trip Time (RTT) between content forwarder and consumer, 2) the states of in-network cache per name prefix, and 3) the forwarding path information per name prefix. We report a series of experiments conducted using contrace on a CCN topology created on a local testbed and the GEANT network topology emulated by the Mini-CCNx emulator. The results confirm that contrace is not only a useful tool for monitoring and operating a network, but also a helpful analysis tool for enhancing the design of CCNs. Further, contrace can report the number of received interests per cache or per chunk on the forwarding routers. This enables us to estimate the content popularity and design more effective cache control mechanisms in experimental networks.

INTRODUCTION

Content-Centric Networks (CCNs) [START_REF] Jacobson | Networking Named Content[END_REF] or Named-Data Networks (NDNs) [START_REF]Named Data Networking[END_REF] are promising approaches towards the future Internet. In a CCN, publishers provide content through the network, and receivers retrieve content by name. In this network architecture, routers forward content requests by means of their Forwarding Information Bases (FIBs), which are populated by "name-based routing protocols." A CCN enables receivers to retrieve content from an "in-network cache": if a router receiving a content request has the requested named data in its cache, it forwards the data toward the receiver without forwarding the content request to the publisher. As such, implementing this new communication technology requires innovative ideas and research in terms of "naming," "routing," and "caching." To evaluate the architectures and protocols, researchers validate their proposals by running actual implementations, such as the CCN prototype CCNx [START_REF] Ccnx | [END_REF], on testbeds such as PlanetLab [4]. However, because requesting and transmitting named data is unique and can be independent of IP routing, common IP-based network tools such as ping [START_REF] Postel | Internet Control Message Protocol[END_REF] and traceroute [START_REF] Malkin | Traceroute Using an IP Option[END_REF] are unable to evaluate CCN protocols and architectures. Furthermore, these tools do not allow the state of the in-network cache to be discovered. Hence, we need a network tool that can assist troubleshooting activities in CCNs while helping the design of in-network caching and name-based routing mechanisms.

In this paper, we discuss the design and implementation of contrace, an active network measurement tool for investigating the path and caching condition in CCNs. We assume that such a CCN is formed by a CCNx implementation running on top of IP. Contrace consists of a user program and a forwarding daemon implementation. Contrace "Query" messages are invoked by the contrace user and forwarded by CCN routers toward a specified source or caching routers. Contrace "Response" messages are initiated by a router holding the requested content (i.e., cache) or the publisher, and forwarded toward the contrace user. Thus, contrace facilitates the tracing of a routing path and provides additional information such as the Round-Trip Time (RTT) between routers along the path. In addition, contrace identifies the state of the cache, such as the access count and lifetime of cached content, on a router. Obtaining such information allows us to estimate content popularity as a means of optimizing in-network caching. Furthermore, contrace implements policy-based information provisioning that enables administrators to "hide" secure or private information, but does not disrupt the forwarding of messages. This policy-based information provisioning reduces the deployment barrier faced by operators in installing and running contrace on their routers. We developed and implemented contrace and conducted experiments in a CCN topology created on a local testbed and the GEANT network topology emulated by the Mini-CCNx [START_REF] Cabral | Mini-CCNx Fast Prototyping for Named Data Networking[END_REF]. The results show that contrace provides the forwarding path information per name prefix, and facilitates investigation of the content popularity and the potential cache capacity in the network.

II. MEASURING PERFORMANCE IN CCNS

A. Overview

CCNs enable consumers (i.e., receivers) to obtain information or content without continuous end-to-end communication channels between hosts. CCNs focus on information dissemination in the network --how consumers retrieve content by name using "interest" packets, and how publishers (i.e., content owners) provide content through the network using "content object" packets. CCNs advocate receiver-driven communication using name prefixes for routing. In this paradigm, consumers initiate communication by sending a request (interest) for specific content, and CCN routers forward the interest toward the content publisher responsible for the requested content. A FIB is a lookup table that is used to determine the incoming interfaces (called incoming Faces) for all content. The FIB entries comprise a name prefix and incoming Face pairs. Each CCN router also maintains a Pending Interest Table (PIT), a lookup table containing name prefixes, and outgoing Faces used to forward received content.

When a CCN router receives an interest, the router examines the content to determine whether it is cached in its local Content Store (CS). If the named content is in the router's CS, the router forwards the cached content out via the Face on which it arrived. If the named content is not in the router's CS, it searches its PIT to determine whether an interest for the same named content has already been processed. If the same named content is in the router's PIT but the Face receiving the interest has not been set, the router updates the PIT entry by adding the Face as the outgoing Face and discards the interest. If the named content is not in the router's PIT, the router creates a new PIT entry, and forwards the interest via the incoming Faces specified in its FIB.

If any router along the path toward the publisher does not have the requested content in its cache, the interest packet will finally reach the publisher. On receiving an interest, the publisher forwards the content object to its downstream router. Each CCN router on the path that receives the interest forwards the data via the outgoing Faces, stores the forwarded content in its CS if needed, and deletes the corresponding PIT entry.

B. Motivation

CCN technology changes the data retrieval mechanism from a host-centric model to a content-centric model.

Name-based routing paths for forwarding interests and data are organized based on the name prefixes of the content and do not depend on IP routing. The content forwarder is not always the publisher (i.e., content owner) --any router or node along the path may become the content forwarder if it has the requested content in its cache. Conceptually, CCN also has high affinity with multipath routing, as it can perform packet-by-packet forwarding, although there are optimization difficulties [START_REF] Carofiglio | Optimal Multipath Congestion Control and Request Forwarding in Information-Centric Networks[END_REF]. The forwarding paths can be determined by the unique CCN strategy and/or routing layer [START_REF] Braun | An Empirical Study of Receiver-based AIMD Flow-Control Strategies for CCN[END_REF]. Although there are standard methods for measuring the performance of IP networks [START_REF] Paxson | Framework for IP Performance Metrics[END_REF] and common IP-based network tools such as ping [START_REF] Postel | Internet Control Message Protocol[END_REF] and traceroute [START_REF] Malkin | Traceroute Using an IP Option[END_REF], they cannot be directly used to measure or trace the forwarding path in CCNs. Moreover, in-network caching is an innovative core function of CCNs, whereas there are currently no mechanisms to investigative the cache state in routers and the content distribution in the networks.

A network tool for CCNs could be used as an analytical tool to investigate fine-grained cache information such as the number of interests received per cache, and to design forwarding and caching strategies as well as new routing protocols in CCNs.

C. Performance Metrics and Forwarding Path Information

First, it is necessary to identify which performance metrics should be measured in CCNs. According to Pentikousis et al. [START_REF] Pentikousis | Information-centric Networking: Evaluation Methodology[END_REF], CCN performance metrics can be subdivided into "traffic" and "system" metrics. The most important traffic metrics for consumers are the throughput and the RTT between content forwarder (i.e., forwarding router or publisher) and consumer. Although throughput depends on the transport protocol, RTT is the natural metric for ascertaining the end-to-end network conditions, because it has no application or transport protocol dependency.

In general, although traffic metrics are important for consumers, while publishers and researchers are more interested in system metrics such as memory usage and signaling overhead, as these allow the efficiency of each networking protocol or architecture to be evaluated. In CCNs, however, system metrics that are firmly linked to in-network caching are important to all parties. This is because in-network caching affects the overall content retrieval performance, and the use of a large amount of cache may affect the memory usage of the caching router, which would reduce the forwarding performance.

Furthermore, unlike IP-based routing, both the publisher and the routers are capable of forwarding content in CCN. While the consumer does not generally need to know which content forwarder is transmitting the content to the consumer, operators need to identify the content forwarder and observe the forwarding path information per name prefix for troubleshooting and monitoring networks.

D. Related Work

Current CCNx components [START_REF] Ccnx | [END_REF] incorporate a command called ccndstatus. Ccndstatus shows information about Faces and Content Store (CS) information, such as neighbor routers addresses, cache list, lifetime, and expiration time per cache in a CCN router. However, ccndstatus does not provide any information about transmission delay or other traffic metrics. Ccndstatus also requires the user to access all routers along the path to examine the in-network cache. Examining all potential forwarding routers for some specific content by accessing each router is not a practical solution for troubleshooting or monitoring networks.

In addition, network tools should allow researchers to investigate the performance of content retrieval or design algorithms/mechanisms for in-network cache or name-based routing in CCNs. Unfortunately, in many cases, researchers are forced to use simulators for their experiments because there are no tools to satisfy their needs. For instance, Rossi and Rossini [START_REF] Rossi | On Sizing CCN Content Stores by Exploiting Topological Information[END_REF] were forced to use simulations to analyze the caching performances of: 1) homogeneous cache sizing (in which the CS spaces of all routers are the same) and 2) heterogeneous cache sizing (in which a given amount of memory resources are allocated across routers by considering graph-related centrality metrics). It is preferable to investigate such strategies using the actual running codes on a real (or emulated) network.

III. DESIGN AND IMPLEMENTATION

A. Design

Traceroute is a useful tool for analyzing the routing conditions in IP networks as it provides intermediate router addresses along the path between source and destination and the RTT for the path. However, as outlined in Section II.B, this IP-based network tool cannot trace the name prefix paths used in CCNs. Furthermore, given a source-rooted forwarding path per name prefix, tracing from a source (i.e., forwarding router or publisher) to a consumer is difficult, because we do not know which branch of the source tree the consumer is on. Additionally, it is not feasible to flood the entire source-rooted tree to find the path from a source to a consumer. Conversely, walking up the tree from a consumer toward a source is feasible because CCN routing protocols know the upstream router for a given source. Tracing from a receiver to a source can involve only the routers on the direct path. This idea is inspired from the design of the IP multicast traceroute facility [START_REF] Asaeda | Mtrace Version 2: Traceroute Facility for IP Multicast[END_REF].

To determine the state of in-network caching under CCN, the efficiency and performance of in-network caching can be measured by the following metrics for CS in the router: 1) size of the cached content, 2) number of chunks for the content, 3) number of accesses (i.e., received interests) per cache or chunk, and 4) lifetime and expiration time per cache or chunk. A fifth metric of the forwarding router or publisher's IP address is included among the states of in-network caching.

We propose "contrace," a network tool for active measurement in CCNx-based CCNs. Contrace provides:

1) the RTT between content forwarder (i.e., forwarding router or publisher) and consumer, 2) the states of in-network cache per name prefix, and 3) the forwarding path information per name prefix. Contrace is also a useful analysis tool to aid in the future design of CCNs. It can report the number of received interests per cache or chunk on the forwarding routers, indicating the popularity of the content. By comparing this number across all forwarding routers with contrace, we can illustrate the content popularity and evaluate potential cache controls in experimental networks.

The contrace implementation consists of the contrace command and the contraced daemon implementation running on a CCNx router (ccnd). Figure 1 shows the socket communications between the contrace command, contraced, and ccnd. Ccnd, which is a component of CCNx, is a daemon that forwards and caches content objects. The contrace command is invoked by specifying the name prefix of the content and/or the publisher or forwarding router. It initiates the request (i.e., creates the Query message described in Section III.D) to obtain forwarding path and cache information. Contraced running on the contrace user receives the request and communicates with local ccnd. Contraced retrieves cache and other information from local ccnd via a UNIX domain socket, and forwards the request to the neighbor contraced running on the upstream neighbor router (if it is not the content forwarder or the specified end point). When the request reaches the content forwarder, contraced on the forwarder transmits the reply (by sending the response message described in Section III.D) to contraced running on the downstream neighbor router, and the reply is forwarded back to the contrace user.

B. Contrace Command

The contrace command enables the contrace user to investigate the forwarding path based on the name prefix of the content (e.g., ccnx:/news/today/). The usage of contrace is as follows (the descriptions of all the options are shown in Table 1):

Usage: contrace [-R] name_prefix [--nocache] [-h content_forwarder] [-g gateway [-g gateway ...]] [-s skip_node [-s skip_node ...]] [-p port] [-w wait_time]
The name prefix is a mandatory option for the contrace command. If the contrace user does not know the name prefix of the content should be specified, s/he can specify "ccnx:/," the default name prefix. If this default name prefix is given, the user will receive all cache information from the upstream neighbor (adjacent) router(s).

It is also possible to specify both the name prefix of the content and use the "-h" option with the content forwarder, which could be the publisher or forwarding router for the content (e.g., ccnx:/news/today/ -h pub.example.com). If both name prefix and content forwarder are specified, the query message is forwarded in accordance with the IP routes, which could be independent of the CCN FIBs. The contrace user would then obtain the forwarding path information and cache information for the specified name prefix from the specified content forwarder. If the default name prefix and content forwarder are specified, the contrace user obtains all cache information from the specified content forwarder.

In addition to the RTT between content forwarder and consumer, when the contrace command specifies the "-h" option and the IP address of the content forwarder (or "-g" option and the IP address of gateway), the RTTs of other alternative paths for the specified name prefix are measured. This is useful for troubleshooting and in the design and evaluation of routing protocols, because the output potentially indicates a better path for the named content.

When the contrace user only wants to check the forwarding path information (i.e., without cache information) and the RTT between content forwarder and consumer, s/he can utilize the "--nocache" option.

After the contrace command is invoked, it waits for the reply from the upstream router, extracts the returned response messages, and shows the information on the standard output. To cancel the request when the message packets are lost during transmission, or if there is no route for the specified name prefix or publisher/router, contrace forces the session to close after the timeout. Following the timeout, even if the contrace user receives a response, it is discarded. The "-w" option specifies the timeout value (in seconds) that the contrace user will wait for the response. The default timeout value is 4 s.

C. Contraced Forwarding Daemon

Contraced is a daemon that transmits query and response messages. As seen in Fig. 1, when contraced receives a query message from a contrace program, it communicates with local ccnd via a UNIX domain socket to retrieve information about the upstream router(s) from its FIB. For ccnd to communicate with contraced, a small patch must be applied to ccnd. If the local ccnd is not the content forwarder for the request, contraced forwards the query message to the neighbor contraced running on its upstream neighbor ccnd over TCP (currently using 9696 port). When the request reaches the content forwarder, contraced on the router or publisher retrieves the cache information from its CS. The response message is then transmitted back to the neighbor contraced that had forwarded the query message. The response message is forwarded toward the contrace user in a hop-by-hop manner.

Contraced can transmit messages to any node running contraced without referring to the CCN FIB. When contraced receives a query message including the "-h" option record (mentioned in the previous section), it forwards the query message to the specified address in accordance with the IP routes. This implementation enables the contrace user to investigate the alternative route or cache information for the specified name prefix.

As introduced in Section II.B, if it is difficult to optimize the transmission timing or select the best route, the CCN strategy or routing layer can use different Faces defined in multipath routes to transmit a request for specific content. To compare the performance of content fetch from the different paths, contraced immediately and simultaneously transmits the query message to these Faces, whenever multipath routes are configured for the name prefix.

D. Messages and Records

Contrace uses two message types: Query and Response. Both messages are encoded in Type, Length, and Value (TLV) format. The Type field is eight bits long, the Length field is 16 bits long, and the length of the Value field is variable. The Query and Response Type values are 0x01 and 0x02, respectively. The Query message is forwarded in a hop-by-hop manner. When it reaches the content forwarder, the content forwarder turns the Query message into a Response message by changing the Type field value from 0x01 to 0x02.

When Query or Response messages are transmitted, contraced appends one or more "records" to the Response message. The following eight records are defined and transmitted with the same TLV format: 1) contrace user address, 2) name prefix, 3) -h option, 4) -g option, 5) -s option, 6) timestamp, 7) responder address, and 8) cache status. Records 2) --5) are appended by the contrace command only if specified, the timestamp record is appended by every contraced along the path upon receiving the Query, and the responder address (and cache status records if requested) are appended by the content forwarder. The contrace user address and responder address records are appended to the Query and Response, respectively. A timestamp record that specifies the forwarding router or consumer's IP address and UNIX time on the local machine is mandatory for the content forwarder.

E. Response Policy and Configuration

Although contrace gives excellent troubleshooting cues, some network administrators or operators may not want to disclose everything about their network to the public, or may wish to securely transmit private information to specific members of their networks. Contrace provides policy-based information provisioning allowing network administrators to specify their response policy in a configuration file, contrace.conf, for each router.

We define the following three options that can be specified in the contrace.conf file for when the router receives a Query message: 1) whether "-h" option is allowed or rejected, 2) whether "-g" option is allowed or rejected, and 3) whether cache information is disclosed, partially disclosed (i.e., except the request specifying the default name prefix (i.e., ccnx:/)), or not disclosed at all.

On the other hand, we entail that each router runs contraced and does not disrupt forwarding contrace Query and Response messages. When a Query message is received, the router appends the timestamp record and forwards the request to the upstream router toward the content forwarder, but can hide other information according to the policy configuration.

Cases will arise in which a router along the path does not support contraced. In such cases, a downstream router that supports contrace will reply to the contrace client with a message indicating that the upstream router does not support contrace. Further, when an upstream router rejects a Query messages, its downstream router will reply to the contrace client with a message indicating that contrace Query is prohibited.

IV. CONTRACE IN ACTION

First, we deployed seven VMs on two physical PCs. Both the VMs and the PCs ran the Linux operating system (Ubuntu Desktop 12.04 LTS 64-bit version). The VMs communicated with each other via a fast ethernet switch, as shown in Fig. 2(a). CCNx 0.8.2 and contrace components (contrace command and contraced) were installed on each VM. The ccnds on the VMs formed the logical CCN topology shown in Fig.

2(b).

Figure 3 shows the output of contrace commands input by a consumer (descriptions of all outputs are listed in Table 2). We verified that contrace messages were forwarded in a hop-by-hop manner, and that each forwarding router appended its own timestamp record. Further, when the contrace Response message returned to the contrace user, the contrace program calculated the One-Way Delays (OWDs) between each router and the RTT from the contrace user to the content forwarder initiating the Response. To ensure the OWDs shown in the output were correct, the Network Time Protocol (NTP) [START_REF] Mills | Network Time Protocol (Version 3) Specification, Implementation and Analysis[END_REF] was installed on each router to synchronize their internal clocks. Note that even if the routers' internal clocks are not synchronized, the RTT measured between the contrace user and the content forwarder (yellow oval in Fig. 3) is always correct because both start and end times are given by the contrace user.

In this experiment, router B was configured as a multipath for receiving the content of ccnx:/news/today/. As shown in Fig. 3 Next, we investigated the caching performance of CCNx using contrace with a realistic topology on an emulator. Rossi and Rossini [START_REF] Rossi | On Sizing CCN Content Stores by Exploiting Topological Information[END_REF] assessed the cache hit probability and path stretch d / |P| ∈ [0, 1], where d is the hop count of the data and |P| is the hop count from the consumer to the publisher (i.e., without caching). We built the GEANT network topology, which consists of 27 nodes, using Rocketfuel [START_REF] Spring | Measuring ISP Topologies with Rocketfuel[END_REF] on top of the Mini-CCNx emulator [START_REF] Cabral | Mini-CCNx Fast Prototyping for Named Data Networking[END_REF]. The publisher was assumed to have 100 contents. These were characterized by a Zipf probability distribution with the value of the Zipf exponent α = 1.25. Each consumer sends 2500 interests in total, based on the Zipf popularity setting. Under the homogeneous cache sizing approach, each router has equal CS space to satisfy received interests with a probability of about 50%. In the heterogeneous approach, the Degree Centrality (DC) metric was adopted (DC(n) is defined as the number of links incident upon a router n) for its simplicity and good allocation criterion (i.e., the greater the DC of a router becomes, the more CS space the router should have) [START_REF] Rossi | On Sizing CCN Content Stores by Exploiting Topological Information[END_REF]. We allocated a CS space that can satisfy the received interests with a probability of about 80% to each router with DC ≥ 4.

By running contrace at the consumer, we assessed path stretch, because contrace traces the path from the consumer to the router/publisher having the requested data. Figure 4(a) shows the measured path stretch, and compares the homogeneous and heterogeneous approaches at four consumers randomly selected. These results illustrate the improvement in path stretch in the heterogeneous case. Furthermore, because contrace can show the number of received interests per cache or chunk on a router, the content popularity (i.e., the access number of accesses for each content) can be measured (as shown in Fig. 4(b) for the publisher). It is also clear that, under the heterogeneous approach, the access number of popular content (e.g., content-index 1, 2, and 3) decreases with the improvement in path stretch. We conclude that contrace facilitates investigation of the performance of the CCNx protocol, routing/caching strategy in testbeds and/or emulated networks, and the design of future CCN architectures.

V. CONCLUSION AND OUTLOOK

The novel features introduced by the content-centric communication model necessitate specialized network tools that do not currently exist. In this article, we proposed "contrace," a network tool for CCNs that can be used to investigate: 1) the RTT between content forwarder (i.e., forwarding router or publisher) and consumer, 2) the state of an in-network cache per name prefix, and 3) forwarding path information per name prefix.

Contrace facilitates troubleshooting of CCNs and can help in the design and the optimization of routing protocols and routing/caching strategies.

We implemented contrace on a CCNx router, and showcased this tool on a testbed and on a large emulated network. Our experiments demonstrated that contrace provides forwarding path information per name prefix, and enables the measurement of CCN traffic and system performance metrics. We also investigated cache information for each name prefix, the content popularity, and the potential cache capacity in experimental networks.

In future work, we plan to add new functionalities to contrace, to obtain the cache hit probability at routers along a path, and to visualize characteristics of the dispersal of target content (i.e., where/when requests for target content are concentrated). This will promote the extensive analysis of caching/routing strategies, and may engender a fundamentally new design approach. VI. ACKNOWLEDGEMENT . This option must be used with the -h option (an error is returned if this is not specified).

-s skip_node [-s skip_node] … Node name or IP address of the forwarding router to be skipped. If the specified router receives a Query, it forwards the Query to the upstream router regardless of its cache contents. This option must not be used with the -h option (an error is returned if both are specified).

-p port TCP port number for Query/Response. Default: 9697.

-w wait_time Timeout value (in seconds) that the contrace user waits for a Response. After the timeout, the contrace user silently discards the Response. Default: 4 s.

  (a), the Query message was transmitted from router B in two directions (to routers C and E) simultaneously. Two Response messages (transmitted from router C and the publisher) were then received by the contrace user. Another observation from Fig. 3(a) is that router C obtained the cache of ccnx:/news/today/ from router D, not the publisher. From Fig. 3(b), we can observe that the publisher (with IP address 172.16.6.196) cached four contents, while the output of Fig 3(c) indicates only ccnx:/news/today/ as its cache information, because the contrace command explicitly specified the prefix.

Fig. 1 .

 1 Fig. 1. Socket communications among contrace command, contraced, and ccnd.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Experimental configuration of the local testbed: (a) configuration of seven VMs on two PCs, (b) CCN topology formed by the VMs.

Fig. 4 .

 4 Fig. 4. (a) Average path stretch measured at the four consumers and (b) content popularity measured at the publisher in the homogeneous approach and the heterogeneous approach measured with contrace running on the GEANT topology emulated by Mini-CCNx.

Table 1 .

 1 Description of contrace command options.

	Option

-g gateway [-g gateway] …

Node name or IP address of gateway router(s) to be passed through. Similar to source routing. If this is specified, Query is forwarded in accordance with IP routing path (without looking up CCN FIB)

Table 2 .

 2 Description of contrace command outputs. Sum of one-way delays from contrace user to this node.If this node is contrace user, this value indicates the RTT between contrace user and the content forwarder.

	Category

This research is partially supported by the Japan Society for the Promotion of Science (JSPS) through the Bilateral Joint Research Program and INRIA through the AYAME Program in the context of the Designet/Simulbed associated team.