16.13 Exercises 397 parentage, one can only invent the Internet once. Reinventing the Internet is even harder, if one follows the fate of the next-generation Internet proposal. But there will always be new ways to understand and measure the Internet, especially using techniques that depend on minimal cooperation. The first part of the chapter focused on the problems of the most basic measurement issue at high speeds: packet counting. This is a real problem faced by every high-speed-router vendor as they deal, on the one hand, with increasing ISP demands for for observability, and, on the other hand, with hardware limitations. Algorithmics can help by clever uses of memories (P5c), by changing the specification to focus only on large counters or flow counts (P3), by unusual uses of sampling (P3a), and finally by determining real user needs to reduce the space of counters required by aggregation for accounting or traffic matrices (P7). Figure 16.1 presents a summary of the techniques used in this chapter together with the major principles involved. The chapter concluded with a small excursion into the field of passive measurement. Unlike all the other schemes described in this chapter, passive measurement schemes do not require implementation or protocol changes and hence are likely to continue to be a useful source of measurement data. Thus it seems fitting to end this chapter with Savage's summary of the main idea behind Sting: "Stop thinking of a protocol as a protocol. Think of it as ... an opportunity." 16.13 EXERCISES 1. Using DRAM-Backed Up Counters: This chapter only described the implementation of packet counting, not byte counting. Suggest extensions to byte counting. 2. Finding the First Set Bit: Using the techniques and assumptions stated in Chapter 2, find a fast parallel implementation of the find-first-bit-set operation for a large (say, of length 1 million) bit vector in the context of the counter-management algorithm described in