extfieldsofstudy:
Computer Science
Engineering

s2fieldsofstudy:
Computer Science
Engineering

text:
DVS for On-Chip Bus Designs Based on Timing Error Correction

On-chip buses are typically designed to meet performance constraints at worst-case conditions, including process corner, temperature, IR-drop, and neighboring net switching pattern. This can result in significant performance slack at more typical operating conditions. In this paper, we propose a dynamic voltage scaling (DVS) technique for buses, based on a double sampling latch which can detect and correct for delay errors without the need for retransmission. The proposed approach recovers the available slack at non-worst-case operating points through more aggressive voltage scaling and tracks changing conditions by monitoring the error recovery rate. Voltage margins needed in traditional designs to accommodate worst-case performance conditions are therefore eliminated, resulting in a significant improvement in energy efficiency. The approach was implemented for a 6mm memory read bus operating at 1.5GHz (0.13 $\mu$m technology node) and was simulated for a number of benchmark programs. Even at the worst-case process and environment conditions, energy gains of up to 17% are achieved, with error recovery rates under 2.3%. At more typical process and environment conditions, energy gains range from 35% to 45%, with a performance degradation under 2%. An analysis of optimum interconnect architectures for maximizing energy gains with this approach shows that the proposed approach performs well with technology scaling.

Introduction
On-chip buses can contribute a significant portion of the total power consumption. This is especially true for high performance and communication-centric designs, where the buses are long and are heavily buffered to meet aggressive delay targets. Due to increased wire delays and longer wire lengths, on-chip communication is often performance critical and directly impacts the processor cycle time. The design parameters of a bus (pitch, number and size of repeaters, shield wires, etc.) must be chosen to meet the timing constraints under worst-case conditions, including switching behavior of neighboring wires, process corner and environment (IR-drop and temperature) conditions. The probability of all worst-case conditions occurring simultaneously is usually small and hence, the bus is faster than it needs to be for more common case operating conditions. In this paper, we propose a method for dynamically scaling down the supply voltage for typical case conditions, resulting in significant energy reduction while still meeting delay constraints.
Various layout [1,2], repeater sizing [3,4] and encoding [5,6] solutions have been proposed for reducing power consumption in on-chip buses. However, these approaches are focused on improving energy efficiency at the worst-case conditions and do not take advantage of the potential energy reduction at more typical operating conditions. Hence, they are orthogonal to the approach proposed in this paper. Also, supply voltage scaling is a more powerful method for energy reduction, since it can ideally result in a quadratic savings in energy, without any routing area overhead. Dynamic voltage scaling (DVS) for energy reduction is not a new concept in general, but its application for on-chip buses operating in non-worst-case conditions has not been explored previously.
The traditional approach to DVS exploits fluctuations in the computational requirement of an application and scales down the frequency and voltage during periods of low performance utilization [7,8]. However, this approach does not exploit the variation in operating conditions and therefore still incorporates substantial margins to accommodate worst-case conditions. In this paper, we formulate the problem as reducing energy while maintaining the same clock frequency, noting that this approach can be combined with traditional DVS as well. A number of approaches were proposed that embed self-tuning circuits to provide dynamic reduction of the supply voltage and/or clock frequency.
The so called Correlating VCO [9,10] and Delay Line Speed Detector [11] schemes use a circuit under test that mimics the critical path delay on the chip and the voltage for the chip is changed based on the speed of this test circuit. Duplicating a bus would result in a huge area overhead, making such techniques impractical for designs with buses as the critical path. In a different tuning approach, the actual circuit performance is tested periodically with worst-case latency vectors using a so-called Triple-Latch Monitor [12]. Though this approach can adjust to more local performance conditions, it cannot take advantage of typical latency vectors. Also the power overhead can be substantial for bus designs since worst-case vectors need to be propagated through the bus for evaluating the operating condition at regular intervals. Finally, IR-drop at repeater blocks in a bus are strongly dependent on the input vectors due to the large size of repeaters and their influence on IR-drop. In this case, the Triple Latch Monitor cannot take advantage of typical delays and IRdrop on a bus.
A key characteristic of the previous approaches is that they ensure correct operation at all times, and hence require additional safety margins which reduce their power efficiency. This paper proposes a more aggressive voltage scaling technique that is based on dynamic detection and correction of delay errors. Error recovery is incorporated in the bus architecture by employing a modified flip-flop that samples its input at the normal clock as well as at a delayed clock and was previously proposed for use in logic pipeline designs in [13]. If a difference between the 2 samples is detected, a control signal from the flop indicates that the data captured by the normal clock is incorrect and an error recovery mechanism ensures that the correct data value (that was sampled by the delayed clock) is propagated, while also ensuring that the incorrect data from the previous cycle is flushed out from the next stage.
A major advantage with the proposed approach is that error recovery does not require a failing vector to be retransmitted on the bus, providing great potential for energy reduction on the bus with a smaller energy overhead for error recovery. At the same time, all local performance conditions, including IR-drop and neighboring switching patterns, are accounted for by the approach, allowing for the removal of all voltage safety margins. In the proposed approach, the voltage is increased only when not doing so would result in an unacceptable number of delay error corrections, thereby significantly improving the energy efficiency.
We implemented the proposed approach for a memory read bus of an Alpha processor design. Fig. 1 shows the schematic of the system level implementation that would be required for this approach. The bus feeds into the memory unit of the execution core, where load data is typically held in a buffer before being committed to an architectural state. The original flip-flops that hold the load data can be replaced by the double-sampling flipsflops and timing errors can be handled in a manner similar to cache misses and speculative loads, with a one cycle penalty for error recovery. A similar mechanism will be required for handling the non-deterministic latency (in cycles) with this approach for other types of buses.
The remainder of this paper is organized as follows. The delay error detection and correction flip-flop is discussed in Section 2, along with its implications on the bus design. The simulation framework is discussed in Section 3. The impact of statically scaled supply voltage on error-rates and energy reductions for a range of benchmark programs is presented across a range of possible process, voltage drop and temperature (PVT) corners in Section 4. In Section 5, a simple voltage regulation system in conjunction with the proposed bus design is simulated for gauging the energy savings possible by dynamically scaling supply voltages to take advantage of the difference in switching activities across programs. Interconnect architectures that favor increased voltage scaling for a bus with the proposed approach are discussed and quantitatively analyzed in Section 6. The implication of this is discussed in the context of the efficacy of the proposed bus design for scaled technologies. Section 7 presents some concluding remarks.

Double sampling flip-flop Design
The proposed approach to DVS is based on the usage of a double sampling flip-flop ( Fig. 2) for error detection and correction. In the absence of timing errors, the flop operates as a traditional master-slave flip-flop. When the input of the flop does not meet the setup time for error-free operation, the correct input is captured by the shadow latch since it is controlled by a delayed clock (with respect to the main flip-flop). The presence of a timing error in the previous cycle is signaled by the Error_L signal, which is an XOR function of the data in the slave latch and the shadow latch. Upon assertion of the Error_L signal, the correct data is restored in the flop through the multiplexer placed in the feed back path of the master latch. The design approach does need to be conservative to allow for data to be captured correctly by the shadow latch at the minimum allowable voltage under worst-case operating conditions. The local error signals (Error_L) of all the individual flip-flops in a bank that lie between two pipeline stages are ORed to produce an error signal that indicates a timing error in the previous pipeline stage. This signal is polled by the control system to measure error rates and is also used for triggering the error recovery mechanism in the architecture. Error correction requires at least a one cycle penalty since the incorrect data that was sent to the next stage needs to be flushed out before the correct data from the shadow latch is re-transmitted. The extra cycle penalty for timing errors could be accommodated by the processor in similar ways that cache misses are handled and the performance (IPC) may not necessarily degrade by the same amount as the error-rate (especially for out-of-order execution).
This error detection and correction capability comes at the cost of a much increased hold-time constraint with the flip-flop. As a result it needs to be ensured that the delays of short paths that feed into a shadow latch never violate the increased hold-time constraint. This hold constraint limits the amount of clock delay that can be accommodated on the shadow latch and hence the degree of voltage scaling below the point of first failure that can be exploited in the DVS scheme. In bus structures, however, the difference between short and long path delays is much less than that in logic circuits, making bus structures highly suitable for this approach of error detection and correction. In our analysis, it was found that the shadow latch clock could be delayed by as much as 33% of the clock cycle without violating the short-path constraint.
With each error recovery in the flop, a performance and energy penalty is incurred. The energy penalty with error-recovery stems from the energy consumed in the error detection/recovery logic and the re-execution of instructions when recovering from an error. As supply voltage is lowered the energy savings increase at the cost of increased error-rates. The trade-off between bus energy reduction and the energy penalty associated with increasing error rates as supply voltage is scaled down implies an optimal supply voltage exists at which the total energy with the DVS approach is optimal. Hence, the voltage must be controlled such that the energy optimal error rate is not exceeded. In addition, the performance impact of error recovery places limits on the acceptable error rate. In our experiments, a maximum average error rate of 2% was used, and was found to provide substantial energy savings while incurring negligible performance impact.

Simulation framework
A 6mm 32-bit bus (Fig. 3) routed on a global metal layer of a 0.13 m CMOS process at minimum pitch (0.8 m) is used for analyzing the impact of the DVS approach on a memory read bus. A nominal supply of 1.2V is used. Capacitance extraction is performed with a 2D field-solver. A 1.5mm inter-repeater in [1] in [2] in [3] in [  distance is used with shield wires inserted after every 4 wires. Such a shield insertion interval (in terms of wires) is a typical design practice for limiting noise and inductive effects for wide buses [14]. The receiver end of the bus feeds into the input of a flip-flop (not shown in the figure). A fixed clock frequency of 1.5GHz is assumed. The repeaters are sized so that the maximum delay (measured from node in to node out) on the bus is 600ps (allowing 10% cycle time slack for set-up time and clock skew). The maximum delay is measured under worst-case conditions of neighbor switching activity and the PVT conditions, i.e., slow process corner, temperature of 100C and a voltage (IR) drop of 10%. This sizing approach reflects a typical design philosophy to ensure that the performance target is achieved even under worstcase conditions with a fixed supply voltage.
The bus is analyzed for performance and energy with the DVS approach over millions of cycles of program execution. In order to reduce the simulation complexity, while maintaining SPICE-level accuracy, the delays (for every wire) and energy consumption on the bus are tabulated for all possible data input combinations using HSPICE. Such look-up tables are created for individual supply voltages (in increments of 20mV) over a range of supply voltages and also for different combinations of process corner and temperature. Leakage current through the repeaters is also tabulated for the different supply voltages and environment conditions so as to include the contribution of leakage energy to the total bus energy.
For evaluation purposes we use the data trace on the memory read bus from 10 of the SPEC2000 benchmarks. The data trace for each benchmark is obtained by modifying the sim-safe simulator in the SimpleScalar/Alpha version 3.0 toolset [15]. The simulations were run using the SPEC reference inputs. We used the SimPoint toolset's Early SimPoints to pinpoint 10 million instruction trace sequences that were highly representative of the entire program execution [16]. Each instruction is assumed to represent a single clock cycle (IPC=1). All error-rate analysis is based on the number of resulting bus timing errors (with correct data captured by the shadow latch) during a window of program instructions. A single bus timing error represents the assertion of the error signal by one or more error detecting flip-flops in the bank in a single cycle. The number of errors based on clock cycles for the actual system architecture will yield lower error-rates since the same number of errors will occur in a larger time window due to the fact that IPC in a pipeline is typically less than 1. Therefore, the error rates reported in the paper are pessimistic. From a performance perspective, the reduction in IPC for a particular error rate is highly dependent on the architecture and the specific program. For the sake of simplicity, we assume a 1 cycle penalty for error recovery and translate this to a reduction in performance (IPC) that is the same as the error-rate.

Voltage scaling and PVT corner impact on error rate
Since the proposed approach relies on error correction at aggressively scaled supply voltages, it is necessary to gauge the effect of scaling supply voltages under different PVT corners on the resulting error rates since it can determine the performance degradation and the energy overhead from error correction. The different process corners used are slow, typical and fast. For local voltage conditions on the repeaters/drivers, either no IR drop is assumed or a 10% droop in supply voltage is assumed for any particular supply voltage when delay is calculated. The temperature conditions assumed are either 25C or 100C. For different combinations of process, IR drop and temperature, the benchmark programs were simulated over a range of supply voltages for all PVT corners.
The effect of scaled supply voltages for 2 different PVT corners is shown in Fig. 4. Every point on the energy and errorrate curves represents combined energy and error rates of running all the benchmark programs (with each one being run for 10 million cycles) at the specific supply voltage. The supply voltage is scaled only up to the point where the longest bus delay can still meet the setup time of the shadow latch for the specific PVT corner. Since the bus was designed to operate error-free for the worst case condition (same as that used for Fig. 4a), the error rates increase as soon as the supply voltage is lowered below the nominal 1.2V supply. For a faster PVT corner, the same performance can be maintained while supply voltage can be scaled. This is evident in Fig. 4b, where no errors are introduced up to a 980mV supply.
For every error, there is an energy overhead involved in retransmitting the correct data to the processor pipeline. Since only a small fraction of the flops in a bank typically result in errors, most of the extra energy consumption usually comes from clocking all the flip-flops for an extra cycle. The effect of this over head is also shown in Fig. 4 and is very small compared to the energy savings on the bus. The error-correction overhead will be higher when the entire pipeline is considered and would also depend on the architecture. Since we are examining the bus in isolation, we choose error rates from the perspective of performance degradation, which closely tracks the error-rates.
The effect of 3 different target error rates (0%, 2% and 5%) is examined. If a PVT corner results in a faster bus, the supply voltage can be scaled further to achieve the same error rate under the delay constraint. In Fig. 5 the delay spread on the normal bus (at VDD=1.2V) from the various PVT corners is shown on the X-axis. The energy gains achievable by operating the bus at the lowest supply voltage that does not result in exceeding the target error rate for the PVT corner are shown on the Y-axis. As expected, the energy gains for a target error rate increase as the PVT corner results in a faster bus, with gains of 35% for the typical process corner with no performance degradation. Also, if the higher error rate of 5% can be tolerated, the gains are higher. The gains from 0% and 2% error rates are indistinguishable. This results from the fact that the error rates jump directly from 0 to above 2% for the used supply voltage discretizations (of 20mV).
Though we treat each of the performance dictating factors independently (for the sake of simplicity), the process corner is the only true independent variable while the IR drop and temperature can also be functions of the specific program. Incorporating such dependencies would involve complex models. The goal of the analysis is to show the range of energy gains possible for the range of performance dictating conditions.

Energy Reduction with Proposed DVS Scheme
The bus switching activity can vary from one program to another and even during a single program execution. The results of the previous section do not reflect the energy gains possible if the supply voltage is scaled during program execution while still maintaining a target error rate. The in-situ error rate measurement capability of the proposed approach can allow further energy gains (on top of those available from PVT corners) for individual programs by taking advantage of the bus switching activity.
To illustrate the dependence of dynamic supply scaling on program behavior we first examine the optimal supply voltage selection (with the knowledge of future program switching behavior) over time while maintaining a fixed error rate. For different target error rates, the percentage of time that the bus spends over various supply voltages during the execution of 3 different programs is shown in Fig. 6. When no errors are tolerated (not shown in figure), all the programs run at the supply voltage that the specific PVT corner allows for zero error operation -the energy gains being dictated only by the PVT corner. If a small percentage of error rates can be tolerated, the optimal supply voltages during program execution can vary widely from one program to another. For a target error rate of 2% crafty can run at 900mV during most of the program execution, while the supply cannot be reduced below 980mV even with a target error rate of 5% for mgrid.
In an actual system, it is not possible to guarantee a target error rate since there is delay involved in changing the supply voltage with a regulator and the switching activity for a block of time in the future cannot be known a priori. A simple voltage supply control system (Fig. 7) is simulated with the bus during program execution. The system calculates errors generated by the bus in 10,000 cycles using an error counter that is incremented by the Error signal from the bank of flip-flops. The counter is reset after every 10,000 cycles. The voltage controller changes the voltage based on the error rate in the last 10,000 cycles. The system tries to maintain error rates between 1% and 2% (which is a reasonable trade-off of performance for energy gains). If the error rate is less than 1%, the supply voltage is reduced by 20mV and if it is greater than 2%, supply voltage is increased by 20mV. A more sophisticated proportional control system could have been used that results in voltage changes proportional to the magnitude of error difference between the target and sampled error rates. Since the error-rate of the bus is a non-linear function of supply voltage, it is not possible to calculate the transfer function for the bus. Calculation of the proportionality constant for such a system would not be trivial. Also, the simpler system that we have simulated is shown to work reasonably well without the hardware overhead of a more sophisticated system. Since the voltage regulators take time to adjust the voltage (typically around 1 s/10mV), the supply voltage on the bus is changed by 20mV only after a delay of 2 s (3000 cycles at 1.5Ghz operation) after the decision to change the supply voltage is taken by the regulator. The minimum voltage allowed by the regulator is chosen conservatively for the bus to meet the setup time of the shadow latch. The only factor that we have used for tuning (the minimum allowable voltage by the regulator) is the process corner since that does not change with time. Otherwise, worst case conditions of temperature and IR drop are assumed. For example, if the PVT corner is typical, 100C and no IR drop, minimum voltage allowed   is such that shadow latch setup time is met for typical process, 100C and 10% IR drop. Table 1 lists the energy reductions possible with two voltage scaling schemes. The fixed voltage scaling (VS) scheme is a generic representation of other voltage scaling schemes that can only account for global process variations and have conservativeness built into them since they cannot handle timing errors. The proposed DVS scheme is as discussed earlier in the section. For the worst-case PVT corner (slow process, 100C, 10% IR drop), no energy gains are possible with zero error rates (fixed VS), while the implemented DVS results in 1% to 17% energy gains across the benchmarks. Any energy gains at this PVT corner with the proposed DVS are possible only by taking advantage of the unique program switching activities on the bus. Though the combined error-rate for all the programs with the implemented DVS system is less than 2%, 2 programs result in average error rates that are slightly higher than the target. Note however, that while the error rate cannot be guaranteed, correct operation using error recovery is always ensured. At the faster PVT corner (typical process, 100C, no IR drop), the difference between fixed VS and implemented DVS is even higher because the fixed VS scheme can lower supply voltage only up to the point where error-free operation is guaranteed with 10% VDD drop. The fixed VS scheme cannot take advantage of the fact that there may not be any VDD drops in the actual design. At the faster PVT corner all programs finish with individual average error rates within 2% and overall energy gains of 38.6%, while individual programs show gains from 35% to 45%.
The variation in supply voltage and instantaneous (i.e., over a time period of 10000 cycles) error rates for the faster PVT corner of Table 1 are plotted in Fig. 8. The supply voltage is assumed to start from the nominal 1.2V. The programs are run consecutively (each one running for 10 million cycles) and the region of individual program executions is demarcated by the same numerical ordering as in Table 1. For the error rates, each dot represents the error-rate over the period of 10000 cycles. It is evident that the proposed DVS control system can adjust for the PVT corner as well as the switching activity that is unique to every program. The supply voltage and error-rates exhibit unique patterns for each program and the switch from one program to another is clear. As mentioned above, though the average errorrates (from the execution of 10 million instructions of a program) for the programs are within the 2% target, the instantaneous errorrates can be well over the target (reaching as high as 6% in Fig. 8) during execution. The main reason for this is the delay involved in ramping up the voltage by the controller when high error rates are observed.

Interconnect Architecture and Technology Scaling
The proposed approach to DVS provides advantages similar to that of asynchronous design -maximize gains for typical case operation rather than worst-case. The maximum amount of supply lowering with the proposed approach is primarily limited by the error rates. For a particular error-rate constraint, a design that does not change the worst-case delay while improving the typical case delay allows the supply voltage to be lowered further before the error rate constraint is reached.
The electrical equivalent of an interconnect wire is shown in Fig. 9. The line of interest has a signal V while A0 and A1 serve as neighboring aggressors. Switching pattern I results in worst-case delays on the wire. The Elmore delay for such a switching pattern is : t D = R ( Cg + 4 Cc) (1) This switching pattern is responsible for the initial (and acceptable) increase in error rates as supply voltages are reduced. When the supply voltage is reduced to a point where delay (for error-free operation) cannot be met with switching pattern II, the error rates immediately jump to a higher, and often unacceptable level (>10%). The difference in Elmore delays between pattern I and pattern II is:  Table 1. Error rates may appear overlapped in time due to resolution limitations. Wire layout geometries that increase this difference between these delays (by increasing the Cc/Cg ratio) allow the bus to operate at lower supply voltages with the proposed DVS method for the same non-zero error rate constraint, provided the worst case delay remains unchanged. Since the fastest delay on the bus reduces with this approach, the delay to the shadow latch clock would need to be reduced. This limits the minimum voltage that the bus can operate at. Since the power savings with this approach are limited more by the acceptable error-rate rather than the absolute minimum supply voltage that can be operated, this is a reasonable trade-off.
We alter the wire parasitics of the bus so that the Cc/Cg ratio is 1.95X that of the original bus while ensuring that the wire resistance and total effective capacitance (Cg + 4Cc) for worstcase delay does not change. Repeater sizes are unchanged since the worst-case delay does not change. The worst-case switching delay remains unchanged across all PVT corners. Static voltage scaling at various PVT corners confirmed that the voltage could be scaled by a further 20mV (than original bus) for almost all PVT corners before reaching the error-rate constraint. The results for energy gains across PVT corners are shown in Fig. 10. The curve for zero error rates does not change since the maximum delay does not change. The 2% and 5% error-rate curves show slightly higher energy gains. Simulations with the proposed voltage control system of the previous section also showed increased energy gains for all programs, with the average energy gain for the worst-case PVT corner (slow process, 100C, 10%IR drop) increasing from 6.3% (in Table 1) to 8.2%. The error rate for all the programs with the proposed DVS bus is still within the target of 2%.
With scaled technologies, the wire capacitance does not change appreciably [17], while the wire resistance increases. As a result, the delay spread on wires due to neighbor switching activity increases (since the R Cc term in (2) increases). The proposed bus design results in a higher energy savings with an increased difference in delay between worst-case and more typical switching activities and, therefore, can be expected to scale well with technology.

Conclusions
A DVS approach for energy reduction in on-chip buses with double sampling flip-flops has been proposed. The proposed bus design allows aggressive voltage scaling since it provides recovery from timing errors without retransmission of failed data on a bus. A 6mm memory read bus that was designed to operate at 1.5Ghz (for a 0.13 m CMOS technology) under worst-case conditions was analyzed using this approach. An extensive analysis of the effect of static voltage scaling across a range of PVT corners showed that if voltage is scaled down to reduce any available slack (while maintaining the same clock frequency) at a particular PVT corner, energy gains up to 48% are possible even with no error rates. The gains increase if slightly higher error-rates can be tolerated. A voltage regulation system to allow dynamic voltage scaling and take advantage of typical switching activities during program execution was also tested. Even at the worst-case process and environment conditions, energy gains up to 17% were achieved for individual programs, while at more typical process and environment conditions, the energy gains range from 35% to 45%. These energy gains were achieved with less than 2% impact on performance. The effect of interconnect geometries that favor increased voltage scaling for a bus with the proposed approach was analyzed and the results indicate that the approach should scale favorably with interconnect scaling.


ILR-Based MT Comprehension Test with Multi-Level Questions

We present results from a new Interagency Language Roundtable (ILR) based comprehension test. This new test design presents questions at multiple ILR difficulty levels within each document. We incorporated Arabic machine translation (MT) output from three independent research sites, arbitrarily merging these materials into one MT condition. We contrast the MT condition, for both text and audio data types, with high quality human reference Gold Standard (GS) translations. Overall, subjects achieved 95% comprehension for GS and 74% for MT, across 4 genres and 3 difficulty levels. Surprisingly, comprehension rates do not correlate highly with translation error rates, suggesting that we are measuring an additional dimension of MT quality. We observed that it takes 15% more time overall to read MT than GS.

Introduction
The official Defense Language Proficiency Test (DLPT) is constructed according to rigorous and well-established principles that have been developed to measure the foreign language proficiency of human language learners in U.S. Department of Defense settings. In 2004, a variant of that test type was constructed, following the general DLPT design principles, but modified to measure the quality of machine translation. This test, known as the DLPTstar (Jones et al, 2005), was based on authentic Arabic materials at ILR text difficulty levels 1, 2, and 3, accompanied by constructedresponse questions at matching levels. The ILR level descriptors, used throughout the U.S. government, can be found at the website cited in the list of references. The text documents were pre-sented in two conditions in English translation: (1) professionally translated into English, and (2) machine translated with state-of-the art MT systems, often quite garbled. Results showed that native readers of English could generally pass the Levels 1 and 2 questions on the test, but not those at Level 3. Also, Level 1 comprehension was less than expected, given the low level of the original material. It was not known whether the weak Level 1 performance was due to systematic deficits in MT performance at Level 1, or whether the materials were simply mismatched to the MT capabilities.
In this paper, we present a new variant of the test, using materials specifically created to test the capabilities of the MT systems. To guarantee that the MT systems were up to the task of processing the documents, we used the DARPA GALE 2006 evaluation data sets, against which several research sites were testing MT algorithms. We arbitrarily merged the MT output from three sites. The ILR difficulty of the documents ranged from Level 2 to Level 3, but the test did not contain any true Level 1 documents. To compensate for this lack, we constructed questions about Level 1 elements (e.g., personal and place names) in Level 2 and 3 documents. A standard DLPT would have more variation at Level 1.

Related and Previous Work
Earlier work in MT evaluation incorporated an informativeness measure, based on comprehension test answers, in addition to fluency, a measure of output readability without reference to a gold standard, and adequacy, a measure of accuracy with reference to a gold standard translation (White and O'Connell, 1994). Later MT evaluation found fluency and adequacy to correlate well enough with automatic measures (BLEU), and since comprehension tests are relatively more expensive to create, the informativeness test was not used in later MT evaluations, such as the ones performed by NIST from 2001NIST from -2006. In other work, task-based evaluation has been used for MT evaluation (Voss and Tate, 2006), which measures human performance on exhaustively extracting 'who', 'when', and 'where' type elements in MT output. The DLPTstar also uses this type of factual question, particularly for Level 2 documents, but not exhaustively. Instead, the test focuses on text elements most characteristic of the levels as defined in the ILR scale. At Level 3, for example, questions may concern abstract concepts or hypotheses found in the documents. Applying the ILR construct provides Defense Department decision makers with test scores that are readily interpretable.

Test Construction and Administration
In this paper, we present a new test, based entirely on the DARPA GALE 2006 evaluation data, selecting approximately half of the material for our test. We selected twenty-four test documents, with balanced coverage across four genres: newswire, newsgroups, broadcast news and talk radio. Our target was to have at least 2500 words for each genre, which we exceeded slightly with approximately 12,200 words in total for the test. We began with a random selection of documents and adjusted it for better topic coverage. We constructed an exhaustive set of questions for each document, approximately 200 questions in total. The questions ranged in ILR difficulty, from "0+, 1,1+, 2, 2+ and 3, with Levels 0+, 1 and 1+ combined to a pseudo-level we called L1~, providing four levels of difficulty to be measured. We divided the questions into two sets, and each individual subject answered questions for one of the sets. The test itself was constructed by a DLPT testing expert and a senior native-speaking Arabic language instructor, using only the original Arabic documents and the Gold Standard translations. They had no access to any machine translation output during the test construction or scoring.
In August 2006, we administered the test at MIT to 49 test subjects who responded to announcements for paid experimental subjects. The subjects read the documents in a Latin square design, meaning that each subject saw each document, but only in one of the two conditions, randomly assigned. Subjects were allowed 5 hours to complete the test. Since the questions were divided into two sets for each document, the actual set of 49 subjects yielded approximately 25 "virtual subjects" reading the full list of 228 questions. The mean time spent on testing, not counting breaks or subject orientation, was 2.5 hours; fastest was 1.1 hours, slowest was 3.4 hours.
The subject responses were hand-graded by the two testing experts, following the pre-established answers in the test protocol. There was no preassessment of whether information was preserved or garbled in the MT when designing questions or responses in the test protocol. The testing experts were provided the reference translations and the original Arabic documents, but not the MT during scoring. Moreover, test conditions were masked in order to provide a blind assessment. The two testing experts provided both preliminary and final scores; multiple passes provided an opportunity to clarify the correct answers and to normalize scoring. The scoring agreement rate was 96% for the final scores.

Overall Results
The overall result for comprehension accuracy was 95% for subjects reading the Gold Standard translation and 74% for reading Machine Translation, across each of the genres and difficulty levels. The comprehension accuracy for each genre is shown in Figure 1. The two text genres score better than the audio genres, which is to be expected because the audio MT condition has more opportunities for error. Within each modality, the more standard, more structured genre fares better: newswire results are better than newsgroup results, and the more structured genre of broadcast news scores better than the less constrained, less structured conversations present in the talk radio shows.  The break-down by ILR level of difficulty for each question is shown in Figure 2. The general trend is consistent with what has been observed previously (Jones et al. 2005). The best results are at Level 2; Level 1 does well but not as well as expected.
Thus the test has provided a key finding, which is that MT systems perform more poorly on Level 1, even when the data is matched to their capabilities. Level 3 is very challenging for the MT condition, and also more difficult in the GS condition. Using a standard 70 percent passing threshold, responses to questions on all MT documents, except for Level 3, received a passing grade.

Figure 2. Comprehension Accuracy per Level.
To provide a snapshot of the ILR levels: L1 indicates sentence-level comprehensibility, and may include factual local announcements, etc.; L2 indicates paragraph-level comprehensibility; factual/ concrete, covering a wide spectrum of topics (politics, economy, society, culture, security, science); L3 involves extended discourse comprehensibility; the ability to understand hypotheses, supported opinion, implications, and abstract linguistic formulations, etc.
It was not possible to balance Level 3 documents across genres within the GALE evaluation data; except for those taken from Talk Radio, most documents did not reach that level of complexity. Hence, genre and difficulty level were not completely independent in this test.

Comprehension and Translation Error
We expect to see a relationship between comprehension rates and translation error. In an idealized case, we may expect a precise inverse correlation. We then compared comprehension rates with Human Translation Error Rate (HTER), an error measure for machine translation that counts the number of human edits required to change system MT output so that it contains all and only the information present in a Gold Standard reference (NIST, 2006). The linear regression line in Figure  3 shows the kind of inverse correlation we might expect. Subjects lose about 12% in comprehension for every 10% of translation error. The R 2 value is 33%. The low correlation suggests that the comprehension results are measuring a somewhat independent aspect of MT quality, which we feel is important. HTER does not directly address the facts that not all MT errors are equally important and that the texts contain inherent redundancy that the readers use to answer the questions. For exploratory purposes, we divide the graph of Figure 3 into four quadrants. Quadrant I and IV contain expected behavior: 122 data points of good translations and good comprehension results versus 43 points of bad translations and poor comprehension. Q-II has 24 robust points: the translations have high error, but somehow managed to contain enough well-translated words that people can answer the questions. Q-III has 28 fragile points: the few translation errors impaired comprehension. We point out that there is a 1-to-1 mapping between comprehension questions and individual sub-passages of the documents in the data. Each point in Figure 3 plots the HTER of a single segment versus the average comprehension score on the corresponding question. The good and bad items are essentially a sanity-check on the experimental design. We expect to see good comprehension when translations are good, and we expect to see poor comprehension when translations are bad. Next we will examine the two other types: fragile and robust translations. A fragile translation is one that has a good HTER score but a bad comprehension score. A sample fragile translation is one from a broadcast news which asks for a particular name: the HTER was a respectable 24%, but the MT comprehension accuracy was a flat 0%, since the name was missing. Everyone reading GS answered correctly.
A robust translation is one that has a bad HTER score but still manages to get a good comprehension score. A sample robust translation is one drawn from a posting providing instructions for foot massage. The text was quite garbled, with an HTER score of 48%, but the MT comprehension accuracy was a perfect 100%. Everyone reading the GS condition also answered the question correctly, which was that one should start a foot massage with oil. We note in passing that the highest error rate for a question with 100% comprehension is about 50%, shown with the up-arrow in Figure  3. We should be surprised to see any items with 100% comprehension for HTER rates above 50%, considering Shannon's estimate that written English is about 50% redundant. We expect that MT readers are making use of their general world knowledge to interpret the garbled MT output. A challenge is to identify robust translations, which are useful despite their high translation error rate.

Detailed Discussion
In this section we will discuss several aspects of the test in more detail: the scoring methodology, including a discussion of partial credit and interrater agreement; timing information; questions about personal names.
Each correct answer was assigned a score of 1, and each incorrect answer was assigned a score of 0. Partial credit was assigned on an ad-hoc basis, but normalized for scoring by assigning all noninteger scores to 0.5. This method yielded scores that were generally at the midpoint between binary scoring, in which non-integer scored were uniformly mapped either harshly to 0 or leniently to 1, the average difference between harsh and lenient scoring being approximately 11%. Inter-rater agreement was 96%.
The testing infrastructure we used recorded the amount of time spent on each document. The general trend is that people spend longer on MT than on GS. The mean percentage of time spent on MT compared with GS is 115% per item, meaning that it takes 15% more time to read MT than GS. The standard error was 4%. The median is 111%; minimum is 89% and maximum is 159%. In future analysis and experimentation we will conduct more fine-grained temporal estimates.
As we have seen in previous experiments, the performance for personal names is lower than for non-names. We observed that the name questions have 71% comprehension accuracy, compared with the 83% for questions about things other than personal names.

Conclusions and Future Work
We have long felt that Level 2 is the natural and successful level for machine translation. The ability to present concrete factual information that can be retrieved by the reader, without requirements for understanding the style, tone, or organizational pattern used by the writer seemed to be present in the previous work. It is worth pointing out that though we have many Level 1 questions, we are still not really testing Level 1 because the test does not contain true Level 1 documents. In future tests we wish to include Level 1 documents and questions.
Continuing along these lines, we are currently creating two new tests. We are constructing a new Arabic DLPT-star test, tailoring the document selection more specifically for comprehension testing and ensuring texts and tasks are at the intended ILR levels. We are also constructing a Mandarin Chinese test with similar design specifications. We intend for both of these tests to be available for a public machine translation evaluation to be conducted in 2007.


extfieldsofstudy:
Physics
Computer Science

text:
Dynamic Exploration of Networks: from general principles to the traceroute process

Dynamical processes taking place on real networks define on them evolving subnetworks whose topology is not necessarily the same of the underlying one. We investigate the problem of determining the emerging degree distribution, focusing on a class of tree-like processes, such as those used to explore the Internet's topology. A general theory based on mean-field arguments is proposed, both for single-source and multiple-source cases, and applied to the specific example of the traceroute exploration of networks. Our results provide a qualitative improvement in the understanding of dynamical sampling and of the interplay between dynamics and topology in large networks like the Internet.

I. INTRODUCTION
The theory of complex networks is a primary tool in the interdisciplinary research in complex systems. It provides a simple (coarse-grained) description of natural as well as social and technological complex systems, by means of mapping their elements and interactions on the vertices and the edges of a graph [1]. Different systems correspond to microscopically different networks, but their general statistical properties may display similarities. Using the tools of statistical physics in analyzing experimental data, researchers have obtained important insights on the structure of these complex networks, discovering universal properties that are common to very different systems. In particular, most of real networks seem to be sparse, with a very small diameter (small-world property), and to present large fluctuations in the connectivity (degree) of the nodes. The theoretical models pretending to explain the origins of these universal properties can be roughly divided in two classes: static models, in which the network structure is the result of some precise combinatorial assignment, and growing models, in which new nodes attach to a pre-existing network by means of a given number of links [2,3]. Much less attention was instead devoted to the other very important issue concerning the relation between networks structure and the processes used to collect the experimental data. Some questions arise naturally: are the experimental data really reliable? can the ubiquity of some properties be the result of systematic biases introduced by the sampling process itself? These questions have been recently addressed in a series of works [4,5,6,7,8] that study the sampling of networks from both static and dynamical points of view. Among them, the work by Petermann and De Los Rios [4] is the first in which the idea that different generation algorithms may lead to different topological properties is exploited to show analytically that the observed power-law degree distributions can be an artifact of biases affecting the sampling techniques. This issue is particularly relevant for the physical Internet, that is the prototype of a complex network: a huge number of computers are connected together to form a continuously evolving, self-organizing network, on which a large variety of dynamical processes take place [9]. As the robustness and performances of large technological networks strongly depend on their topology, an accurate, unbiased knowledge of the Internet is necessary to support the work of practitioners in improving its structure and functioning. Motivated by the importance of correctly knowing network's topology, the present work is devoted to clarify the mechanisms governing the main techniques used in the dynamical sampling of complex networks. In order to accomplish this task, we first present the general framework that applies to a large class of tree-like dynamical processes, then we focus on the traceroute sampling of networks with homogeneous and heterogeneous degree profiles. We show that the role played by the dynamics is very different in homogeneous and heterogeneous networks. In the latter case, that should correspond to the case of the Internet, the sampling process introduces some level of inhomogeneity that paradoxically increases the sampling accuracy of the tail of the degree distribution. Our results are in agreement with previous analytical and numerical achievements, but allow a more unitary view of the problem. Dynamical sampling techniques are examples of the interplay between networks topology and the dynamics occurring on it. Therefore the dynamical approach presented in this paper could be considered as a theoretical improvement with respect to previous analytical studies based on nodes exposure methods [10,11], that are essentially static algorithms. Moreover, our method can be easily adapted to study other sampling algorithms expressly designed to acquire egocentric views of a network, such as network's tomography [12,13] and crawling algorithms in community networks (the WWW, P2P networks, etc.) [14]. Similar dynamical patterns are observed also in network processes that are not directly related to sampling, such as epidemics [15], rumors spreading [16], diffusion of innovations [17] and threshold models [18].
In summary, we provide a unified description of a class of dynamical phenomena in terms of tree-like evolving structures on networks, and explain how the dynamical rules influence the emerging topological properties, by focusing on the degree distribution.
The paper is organized as follows. In Section II, we present the general theoretical formalism that can be used to study the degree distribution generated by tree-like processes on networks. The important application to the traceroute problem is discussed in Section III. Some conclusions are presented in Section IV together with examples of other possible applications.

II. GENERAL FORMALISM FOR TREE-LIKE PROCESSES
Among the various types of algorithms and dynamical models evolving on networks, we take into account those corresponding to the following general dynamical picture, that is also valid for the special case of traceroute-like explorations. Let us assume the process starts from a single node and propagates iteratively throughout the network. At each temporal step, some nodes at the interface of the growing cluster are selected and some of their still unreached neighbors are visited. The latter ones become part of the interface, while the former interfacial nodes are moved to the bulk of the cluster (a sketch of the dynamics is reported in Fig. 1). During the dynamics we can always identify three distinct classes of nodes: bulk, interfacial, and unreached nodes. When the above process takes place on a random network, in the limit of large network's size N , the overall dynamics is well represented by the temporal evolution of some mean-field quantities, the densities of bulk nodes b(t), interfacial nodes i(t), and unreached nodes u(t). Obviously, u(t) + i(t) + b(t) = 1 always during the dynamics. On a generic random network, however, the degree is not fixed, the nodes being divided in degree classes. The global densities are replaced by degree-dependent partial densities b k (t), i k (t), and u k (t). The partial density for unreached nodes of degree k is defined as the fraction of nodes of degree k that are still unreached at time t. The normalization relation is k P (k)u k (t) = u(t), where P (k) is the degree distribution of the underlying network. The other quantities are defined similarly. More in general, one may be interested in situations in which the network is still maximally random (with degree distribution P (k)) but with some degree correlations, expressed by the conditional probability P (k|h) that a node of degree k is linked to a node of degree h. One can also consider the nodes divided in types α, i.e. discrete or continuous states defined on the nodes. Types are used to create multi-partite networks and to encode some non-topological feature. Another way to account for non-topological properties is that of putting weights on the links, that depend only on the degrees and the types of the extremities. Link weights may account for dynamical properties of the process, such as the transmissibility of a disease [19]. The internal structure of the population is taken into account defining degree-dependent and type-dependent partial densities of u α k (t), i α k (t), and b α k (t). The global densities are recovered by averaging over all distributions, i.e. u(t) = α P(α) k P (k)u α k (t). In order to simplify the formalism, here on we limit our analysis to single-type undirected random markovian networks [20], that are maximally random graphs completely defined by the degree distribution P (k) and the degree correlations P (k|h). According to this mean-field approximated description of the processes, the temporal evolution of the partial densities satisfies a system of differential equations of the type, where the arguments of the functions f x (·) depend on the general form of the dynamics described above. For instance, f b is not expected to depend on unreached nodes, f u on the bulk nodes, etc. The system is generally coupled and non-linear, and admits an explicit solution only in very special cases. In statistical physics and theoretical biology, continuous mean-field dynamical equations are commonly used to study models of population dynamics. The dynamical picture emerging from these mean-field models allows to understand the qualitative behavior of complex phenomena occurring in real systems. At the same time, it is worth noting that the rigorous derivation of differential equations for random processes on random graphs has been introduced in the mathematic literature only recently, by Wormald [21], and then applied to several problems, including algorithms for the generation of random graphs with a given degree sequence [22] and random k-SAT problems [23]. Wormald's differential equations method provides a powerful tool to prove rigorous bounds for interesting quantities (e.g. distribution's moments) in discrete-time combinatorial processes. Here we limit our analysis to a qualitative topological characterization of the emerging degree distribution obtained within a purely mean-field statistical physics approach. However, a rigorous formalization of the present approach is desirable as well.

A. Single-source processes
The degree distributionP (k) of a subnetwork is related to the degree distribution P (k) of the underlying one bỹ where P (ℓ) is the degree distribution, that defines the probability of picking up a node of degree ℓ in the original network, and Q(k|ℓ) is the conditional probability of observing a node of degree k in the subnetwork if its real degree in the complete network is ℓ. In a dynamical framework, the sampling probability depends on the temporal evolution of the overall process. At the beginning, the neighborhood of interfacial nodes is mainly composed of unreached ones, whereas in the final stage of the dynamics most of the nodes have already been visited. The probabilities P (ℓ) and Q(k|ℓ) are thus replaced by time-dependent quantities P t (ℓ) and Q t (k|ℓ), that are defined by the evolution rule of the dynamical processes itself. Using the properties of the dynamics, P t (ℓ) can be expressed as the probability of picking up a node of degree ℓ among the interfacial nodes of the growing cluster at a time t, i.e. P t (ℓ) = P (ℓ)i ℓ (t)/i(t). Then, the way in which the neighbors of this node are selected and visited depends strictly on the details of the dynamical model. When the growing cluster has a tree-like structure, a node of degree ℓ has only one incoming edge, and the remaining ℓ − 1 links are used to propagate towards unreached neighbors. Let us call ρ h the probability to visit a neighbor of degree h of an interfacial node of degree ℓ (it is a function of u h (t)), the conditional probability Q t (k|ℓ) becomes Putting together these two terms and recalling that the global topology is given by averaging over the whole temporal spectrum, we obtain the following expression for the degree distributionP 1 (k) of the tree-like structure emerging from the dynamics, where T is the maximum sampling time. In the above equation we have also introduced the joint degree distributioñ P 1 (k, ℓ) (of observing a node of degree k with real degree ℓ), that will be useful in the following. The generalizations to multi-type and weighted networks are straightforward once one has correctly considered the evolution equations for the partial densities of bulk, interfacial and unreached nodes. Again, the use of the Bernoulli sampling technique (binomial probability) in selecting neighboring nodes is justified by the spreading like character of the dynamics considered here. For different classes of dynamical processes, e.g. threshold processes [18], the selection mechanism should be modified.

B. Multi-source processes
It frequently happens that several processes are running at the same time, so that the overall measure is obtained merging several single-source structures. This is indeed the case of Internet's mapping projects, in which single (spanning) trees from different source nodes are merged together in order to get more accurate mappings of the underlying topology. A completely different example is provided by the overall infection profile in a population that is object of multiple non-interacting disease spreadings (e.g. e-viruses and worms in P2P communities), each one generating a sort of causal tree. In order to study multi-source processes, and the emerging degree distribution, we put forward an approximated method based on a simple mean-field argument for the overlap probability of uncorrelated trees. A direct generalization of the single source method presented above is somewhat tricky, since in any node one edge per process is used as an incoming edge and is not available for spreading. Increasing the number of sources one should take care of all possible combinations of these incoming links, that becomes rapidly very complicated. Nonetheless, this approach leads to some valuable approximation. Let us consider a process with two sources, and a node of degree ℓ + 1 for which we fix the incoming edge, so that both trees reach the node from such an edge. Moreover, we assume that the two sampling processes are completely independent and uncorrelated. With these hypotheses, the observed degree distribution, obtained merging two trees is and δ(x) is the Kronecker's symbol. Reordering the terms in Eq. 5, and using the result for single-source processes, we get in which B(ℓ, m, n, r) is the hypergeometric distribution The case in which both trees reach a node through the same edge is obviously very special, as well as Eq. 5 that does not hold in general. However, one can exploit the picture emerging from Eq. 6 and generalize it to be valid whatever the choice of the incoming edges. Unlabeling the incoming edges and considering them like the other edges discovered during single-source processes, we get the following approximation for the observed degree distribution in a process with two sources,P the sums over m and n start from 1 since we assume that all nodes are discovered, thus the minimum observed degree is 1. Note that even if two consecutive processes are dynamically uncorrelated, the topological and functional properties of the underlying system always introduce some correlations. For instance, in real networks there are very central nodes that bear a large fraction of the traffic, the so-called backbone nodes. Depending on the process it may be easier or more difficult to traverse these nodes. Again, in the Internet there are administrative policies governing local routing systems, therefore in some cases it is impossible to visit the entire neighborhood of a node. This kind of correlations cannot be easily included in the above mean-field analysis. On the other hand, Internet's local correlations may rapidly change in time, as they are affected by traffic congestions and routers' failures; therefore the average qualitative behavior of real processes should be close to the uncorrelated one.
and the merging process can be easily generalized to any number ν of sources exploiting the recursion relation, The degree distribution of the network obtained merging ν trees is then given byP ν (k) = ℓ P (ℓ)R ν (k, ℓ). Note that Eq. 9 is general and holds, within the validity of the approximation, for any type of process in the class under study, while the explicit expression ofR 1 (k, ℓ) as well as the correct form of B(ℓ, m, n, r) depend on the details of the dynamics.
In the next section, we show how these methods can be applied to the traceroute model that describes the experiments used to determine the topology of the Internet.

III. APPLICATION TO THE INTERNET'S MAPPING TECHNIQUES
The Internet's topology can be studied at different levels. The most detailed Internet's descriptions are obtained at the level of single routers, but coarse grained representations are usually preferred for the possibility of obtaining a more reliable picture of the system (see Ref. [9] for a simple introduction to the networked representations of the Internet). Routers sharing the same administrative policies are divided into Autonomous Systems (AS), that define the most important coarse-grained level of the Internet's topology. The first maps of the Internet were collected mainly at the AS level, using empirical data extracted from BGP tables together with those obtained by dynamical sampling methods based on traceroute measurements from single source [24,25,26]. According to these maps, that collect partial views of the net from some favored points, the Internet should be a very heterogeneous network with approximately power-law degree distribution P (k) ∝ k −γ , and γ ≃ 2.1 ÷ 2.4 [25,26]. Because of the peculiar properties of scale-free networks, this discovery motivated a series of theoretical works in which toy-models of the Internet's mapping process were proposed and analysed in order to justify or question this empirical evidence [6,8,27,28]. In a traceroute experiment, a given number of probes are sent from a source to a set of target nodes, tracing back the path followed during the exploration. These probes are data packets that follow the same paths normally used by information to flow throughout the Internet. Although traffic congestions and local network's policies may cause unpredictable path's inflation, the traceroute paths are optimized in order to be the shortest ones between the source and the target nodes. Therefore, standard theoretical models of traceroute's explorations assume that the probes follow one of the possible shortest paths between the source and the destination. More precisely, we can include in the path only one shortest path among all equivalent ones (either a priori fixed or randomly chosen), or all of them. All strategies can occur in realistic processes, that is probably a mixture of them, but people usually give special attention to the one with a unique choice of the shortest path between nodes, that clearly brings to the worst overall sampling. We will also consider this case.
A one-to-all traceroute process is thus represented by an iterative algorithm running on a given network, that starting from a single source generates a spanning tree to all other nodes. Multi-source processes consist in merging different single-source spanning trees. In general, the reliability of traceroute-like sampling methods strongly depends on both the number of sources deployed on the network and the level of degree heterogeneity [8]. In fact, Lakhina et al. [27] first showed numerically that sampling from single sources introduces uncontrolled biases and the observed statistical properties may sharply differ from the original ones. More recently, Clauset and coworkers [6,10] have pointed out that, because of the particular search procedure, a one-to-all traceroute tree has a power-law degree distributionP 1 (k) ∝ k −α even if the underlying network is not scale-free. Actually, this was analytically proved only for homogeneous random graphs with fixed or Poisson degree distribution. In this case, the traceroute tree presents a power-law distribution with exponent α = 1 up to a cut-off equal to the average degree z. For networks with power-law degree distributions P (k) ∝ k −γ , they suggested that the observed one should still be power-law but with a different exponent α < γ. Within the same framework, but in partial contrast with this thesis, Cohen et al. [11] have rigorously showed that in case of power-law networks, the bias on the exponent γ is negligible. Other recent studies, based on mean-field approaches corroborated by numerical simulations, confirm the overall reliability of these mapping techniques on scale-free graphs [8,28]. Nevertheless, the debate on the traceroute process is still open, the main issues concerning the relevance of the biases in single-source processes and the improvements obtained using multiple sources. In the following, we try to address both these subjects using the theoretical approach developed in the previous section. The analytical results mentioned above are actually based on approximated models that partially overlook the dynamical character of the process. The method used in Ref. [6] to study one-to-all traceroutes is based on differential equations, but node sampling is essentially static. It assumes that a node of a given degree can appear with the same probability at any temporal step of the process. This is approximately true on homogeneous networks since the term i k (t) i(t) in Eq. 4 is ≃ 1, but it cannot be extended to the case of heterogeneous networks. The formal approach introduced in Ref. [10] is more general, but it is still based on a uniformly random process, the so-called "exposure on the fly" technique. It implicitly assumes a fitness-like variable homogeneously distributed on the "stubs" of a network, that plays the role of the time at which a node is explored. We improve this approximation using the dynamical method exposed in Section II for both single-source and multi-source processes. Obviously the framework becomes more complex and calculations can be performed analytically only in some special cases.

A. Homogeneous Networks
Let us consider the one-to-all traceroute exploration of an homogeneous random graph with Poisson degree distribution P (k) = e −z z k /k!. The original traceroute dynamics is discrete in time: at each temporal step, an interfacial node ℓ is randomly selected to spread out probes towards all its unknown neighbors; then all reached nodes are included in the interface, whereas node ℓ is moved to the bulk. A continuous-time approximation is defined grouping together N discrete steps and passing to differential equations in the limit of large size N . As the degree distribution is peaked around the average value z, one can safely do the further approximation that all nodes behave identically, that is their temporal evolution is described by the mean-field densities u(t), i(t), b(t) [6]. A selected interfacial node is connected to a unreached node with probability p = z/N , therefore in a temporal step, p u(t) unreached nodes are visited and one node passes from the interface to the bulk. This process translates in the following system of equations [6] The solution gives u(t) = exp(−zt), i(t) = 1 − t − exp(−zt) and b(t) = 1 − t, with t going from zero to a maximum value T , that is the first root of i(t) = 0. Moreover, since in the traceroute sampling the probes emerging from the interfacial nodes visit all unreached neighbors, the mean-field probability to reach a node is just ρ[u(t)] ≃ u(t). The network's homogeneity implies that the internal degree profile of interfacial nodes is approximately the same of the underlying network at all times. According to this approximation, for a traceroute spanning tree on an homogeneous Poisson graph Eq. 4 reduces tõ that is exactly the result obtained by Clauset and Moore [6]. The integral in Eq. 11 can be carried out noting that T ≃ 1 (for z ≫ 1) and passing to the variable u = u(t) = e −zt , with du = −zudt. Then, we can also easily perform the sum over ℓ, where F 2,1 is the hypergeometric function, and the term proportional to e −kz is negligible for sufficiently large values of k. As in Ref. [6], we get an observed power-law degree distributionP 1 (k) ∼ k −1 [6], with a cut-off at k ≃ z. (It is worth to remark that Poisson random networks with average degree large enough to generate a power-law under sampling are extremely unlike in realistic systems, i.e. the Internet, community networks, etc. [8].) The results obtained simulating the traceroute model from a single source on a Poisson random graph (e.g. using the unique shortest path algorithm proposed in Ref. [8]), confirm the k −1 behavior of the observed degree distribution (see Fig. 2-A).
In Fig 2-A, we also report the observed degree distribution obtained sampling from two or more sources, that clearly depart from a purely power-law shape. The observed weird behavior, neither power-law nor poissonian, in which a peak appears at low degree values and moves forward for increasing number of sources, can be easily understood, at a qualitative level, using the theory presented in Section II. These peaks are due just to the superposition of power-law behaviors. In single-source experiments, most visited nodes have observed degree one, as they are discovered at the end of the process. The majority of them is rediscovered again in the same fashion during the second one-to-all process. Thus merging two spanning trees the overall distribution presents a peak at degree 2 instead of 1. The same happens for three sources, with a peak at degree 3, and for increasing number of sources. In general, the position of the peak k p is not strictly equal to the number of sources ν, but it usually hold k p ≤ ν. Solving numerically the recursive Eq. 9, we get the results reported in Fig. 2-B. The curves have the same behavior as in the simulations, characterized by a peak at increasing degree values, then a decrease up to a cut-off about k ≈ z. Strikingly, the assumption of complete uncorrelation of successive spanning trees seems to be approximately correct for homogeneous random graphs. This is true up to a certain amount of sources (about 20 in Fig. 2-B), above which the "metric" correlations between shortest paths are not negligible. At this point, a peak at the original average degree z is developed. Our theoretical approach shows that the observed power-laws in one-to-all traceroutes on homogeneous random graphs are the result of a kind of convolution over a family of peaked symmetric distributions. This convolution process can be naturally "inverted" by increasing the number of observation points. For a large number of sources the tree merging process corresponds to another kind of convolution on the power-laws emerging from single-source experiments and produces an unbiased sampling of the original degree distribution. However, the minimal number ν * of sources required to obtain an unbiased degree distribution is considerably large in homogeneous networks: from simple arguments and numerical evidences, ν * ∼ O(z).
In general the mean-field approximation on networks can be improved considering degree-dependent mean-field quantities, therefore we consider the system of differential equations describing the dynamics for degree-dependent partial densities of bulk, interfacial and unreached nodes. In uncorrelated networks, it reads P (k|h) is the probability that emerging from an interfacial node of degree h we reach a node of degree k still unreached at time t. Note that the above system reduces to Eqs. 10 when the network is a regular random network of degree distribution P (k) = δ k,z . For poissonian networks, the exact time-depending behavior of the partial densities is quite complicated, as evidenced by the curves reported in Fig. 3 obtained solving numerically the system in Eq. 13. In the numerical solution we take initial conditions i h (0) = C 0 δ h,z with C 0 ≃ ∆t, since both the initial condition and the temporal step ∆t should be of order 1/N in a system of size N . The general behavior can be explained with simple arguments. At the beginning of the process, the probability of having a node of degree k at the interface is purely topological, i.e. i k (0 + ) i(0 + ) ≃ k z . The late times behavior for t ≫ 0, can instead be computed knowing that the corresponding behavior of i(t) is approximately linear, i.e. i(t) ≃ 1 − t, and that u k (t) decreases exponentially fast in time. These results, obtained plugging the short times approximation For sufficiently large k, the first term at the r.h.s. can be neglected, thus after integration we get i k (t) ≃ 1 − t. Therefore, the quantity i k (t) i(t) is expected to approach the unity for sufficiently large t ≫ t * k , where t * k is the time at which the maximum value of i k (t) is reached. From the previous arguments one expects t * k ∝ 1/k. These simple calculations, and the numerical results reported in Fig. 3, show that the short time behavior of the sampling process is not trivial at all. Nonetheless, the degree distributions obtained solving numerically the system in Eq. 13 and plugging the corresponding partial densities in Eqs. 4 and 9 are in perfect agreement with the analytical results based on the approximation of complete homogeneity (not shown).

B. Heterogeneous Networks
The degree inhomogeneity is instead expected to play an important role in the exploration of networks with skew and fat-tailed degree distributions, in which the dynamical sampling of nodes is far from being a uniform process. Though to obtain the exact form of partial and global densities it is necessary to solve the evolution equations explicitly, that is in general very difficult, the qualitative behavior of these quantities for large degree values (ℓ ≫ z) can be deduced with some approximate argument. We will show that the tail of the degree distribution of a power-law random graph is sampled with negligible bias, even in single-source experiments. This is mainly due to the fact that high degree nodes arrive at the interface of the process almost immediately, and their neighbors are fairly sampled with a probability that depends only weakly on the dynamics. At the beginning of the process, nodes with large degree are preferentially sampled, i.e. i ℓ (t)/i(t) ≃ ℓ/z, implying that the number of unreached hubs rapidly decays to zero. At this point, almost all high degree nodes are at the interface of the process, i ℓ (t) varies slowly, and the sampling among high degree nodes inside the interface becomes almost uniformly random (i.e. hubs of degree ℓ are picked with probability P (ℓ)). Hence, for sufficiently large times and degrees ℓ ≫ z, the quantity i ℓ (t) i(t) is expected to become independent of the degree ℓ. Solving numerically Eqs. 13, we find that, for t ≫ 0, i ℓ (t) i(t) ∝ t −β , with a cut-off close to the final sampling time T and the exponent β depending on the details of the degree distribution (not only on γ). The numerical results presented in Fig. 5 suggest a scaling function for i ℓ (t) i(t) of the type with F (x) ∝ x −β when x ≫ 1 and F (x) ≈ 1 when x ≪ 1. The scaling form is correct up to a time T ℓ ∼ T (ℓ/z) −1/β , at which the quantity vanishes. Note that for a system of size N , and power-law degree distribution of exponent γ, the maximum degree scales as ℓ max ∼ N 1/(γ−1) . Since the temporal step of the dynamics (integration step) is ∆t ∼ 1/N , a realistic minimum observation time for the above curves is ∆t 1/(1−γ) , that is traced in Fig. 5-A with a dotted vertical line. It is clear that for high-degree nodes the power-law scaling behavior dominates the most of the dynamics. The result is surprising since one would expect that, in a power-law network, i ℓ (t)/i(t) ≃ ℓ/z during the whole dynamics. We will see that this behavior is crucial to get an unbiased estimate of the exponent. The other interesting time-dependent quantity is the probability to visit an unreached node,ū(t) = ℓ ℓ z P (ℓ)u ℓ (t). At long times and high degrees ℓ, the quantity u ℓ (t) is non zero only for low degree nodes, so the temporal behavior of u(t) is similar to that of u(t). Actually, it seems to decay from 1 with a law that is clearly slower than an exponential one, but faster than a power-law. Indeed, if i ℓ (t)/i(t) follows a power-law behavior, formally integrating Eqs. 13 one getsū(t) ∼ e −at α , with α < 1. However, numerical integration does not clarify the possible relation existing between α and β. Plugging the above results into the sampling integral (Eq. 4), it is actually possible to show numerically that the observed degree distribution maintains the same functional form of the original one, at least for high degree nodes. The comparison between observed degree distribution obtained from simulations and by solving numerically the sampling equations are reported in Fig. 6. The qualitative behavior is the same: the traceroute sampling on powerlaw random graphs reproduces the original degree distribution without any significative bias. Some further insights on the reason of this result can be obtained with the following rough argument. Let us consider the sampling formulaP and approximate it for ℓ ≫ z considering that 1) during most of the dynamics the quantity i k (t)/i(t) assumes the scaling form t −β , and 2) the binomial probability can be approximated by a gaussian peaked around its maximum, i.e.ū * ∼ k/ℓ. A rough estimate can be done performing the gaussian integral at the saddle-point or, in an equivalent way, recalling a property of Dirac delta functions, i.e. f (t)δ(g(t))dt ≈ i f (t i )/|g ′ (t i )|, where t i are the zeros of g(t) and g ′ (t i ) is the derivative of the function g in these points. For large k and ℓ, g(t) ≈ ℓū(t) − k, thus |g ′ (t)| ∝ ℓ| dū dt | t ℓ (in which t ℓ is the time at whichū(t ℓ ) ≃ u * ≃ k/ℓ for given values of k and ℓ). Putting all ingredients together, the sampling formula becomesP Sinceū(t) ∼ e −at α , the derivative is proportional to k/ℓ times some power-law in time, we get For large degree we can neglect the logarithmic contributions in the sum over ℓ, findingP 1 (k) ∝ k −γ . According to this result, the degree distribution of the spanning tree emerging from one-to-all traceroute samplings of a scale-free graph (with exponent between 2 and 3) is qualitatively the same of that of the underlying network, at least for high degree nodes. The result is in agreement with a recent analysis by Cohen and coworkers [11], in which some rigorous bounds for the traceroute biases in power-law networks are obtained using the exposure technique. We believe that the general picture describing the behavior of traceroute-like processes could be extracted from the present approach in a much easier way than from the "exposure on the fly" method. Moreover, the framework can be straightforwardly extended to study, at least numerically, the effects of other relevant parameters, and correlations. In these perspective our approach can be considered as a benchmark that could be useful in the problem of network inference [30] and bias reduction [31].

IV. CONCLUSIONS
The study of the interplay between topological and dynamical properties of networks is of primary interest in the current research on complex systems. With the present work, we introduce in this framework a general method to investigate the topological properties of growing clusters that are dynamically defined by a given class of spreading processes and algorithms. These are processes that starting from a single source span the whole network, traversing all nodes only once. The temporal evolution is defined by means of a system of differential equations for the (partial) densities of bulk, interfacial, and unreached nodes. Our approach, that allows to compute analytically or numerically the degree distribution of the emerging tree-like structure, is based on the idea that during its evolution the dynamics performs a sampling of the local structure of the underlying network. As the sampling rate depends on the dynamical properties themselves, the degree distribution of the emerging subnetwork may differ considerably from that of the original network. The generalization to study multiple-source processes is also discussed, at least in the approximation that the overall structure is obtained merging together collections of independent single-source processes. A natural application of the method presented here consists in the analysis of the dynamical sampling of networks. We have provided a deeper insight in the qualitative behavior of traceroute-like processes, shedding light on the dynamical mechanism at the origin of the observed topology. The reasons for the different sampling accuracy observed in homogeneous and heterogeneous networks should be now clear. In particular, we have shown that on homogeneous networks, • in a single source sampling, the network is observed to have a power-law degree distribution with exponent −1 up to a cut-off about the original average degree z; • increasing the number of sources destroys the power-law behavior, but a fair sampling requires about O(z) sources; • "metric" correlations (that can be associated to the betweenness centrality of nodes) favor a better sampling of the local topology for increasing number of sources.
In contrast, on heterogeneous networks, • high-degree nodes are preferentially sampled at the beginning of the process, and with higher accuracy (in this case high-degree nodes are essentially those with highest betweenness); • in single-source experiments, power-law degree distributions are sampled with negligible biases; • the overall sampling of the degree distribution becomes very accurate with just few sources.
We believe that a good understanding of these kind of processes is fundamental in order to improve the performances of current dynamical sampling techniques applied to technological networks such as the Internet and the Web. As mentioned in the Introduction, there are other dynamical processes that can be described using the present approach, from the epidemic spreading, to broadcast trees and search techniques. We just mention a couple of cases that may find further developments. One consists in a recently proposed model of search in social networks, in which the search efficiency decays with the distance [32]. Let us consider an uncorrelated homogeneous random network, on which we perform a distance dependent snowball search such that the probability to visit a still unreached neighbor of an interfacial node is θ(t) ∝ (t + A) −β , with β ∈ [0, 1). The corresponding global density is obtained solving the equation du(t) dt = −zθ(t)u(t). The limit in which β → 1 is particularly instructive, since the global density decreases much slower than an exponential. Performing the calculations, u(t) ∼ A/(A + t) and the emerging tree presents a degree distributionP 1 (k) ≈ k −2 up to a cut-off around z. The example shows how easy can be to find processes that generate power-law degree distributions out of exponential networks. The second relevant example concerns epidemic-like spreading phenomena. Here the system of differential equations governing the dynamics is the celebrated susceptible-infected-removed (SIR) model [33], in which unreached nodes are identified with susceptible nodes, interfacial nodes with infected ones and the bulk nodes correspond to removed individuals. In analogy with the traceroute dynamics, we can write a system of first-order differential equations governing the temporal evolution of partial densities [34]. The fundamental difference between the two dynamics is that in the traceroute model at each time step the algorithm chooses an interfacial node to sample its neighbors, while in the SIR model all infected nodes have a fixed probability to spread the virus to their neighbors (with spreading rate λ). However, for small values of λ (above the percolation threshold) the topological structure is still tree-like and can be analyzed as in Section II. When different transmission properties (e.g. degree-dependent and distance-dependent rates λ) are taken into account, the growing infection region might display very non-trivial topologies. At the same time, the knowledge of the topological structure of an infection's outbreak may be relevant for the design of more appropriate immunization strategies. From a general point of view, the present formalism can be extended to study (at least numerically) the effect of degree-degree correlations or quenched disorder, that have not been considered here but play an important role in all real experiments.
In conclusion, we expect that analyses like the one performed in this paper will allow to get a better understanding of the functional interplay between a network and the dynamical processes evolving on it.