Report

Author: Nan Hua, Bill Lin, Jun (Jim) Xu, Haiquan (Chuck) Zhao Publisher: ANCS’08 Presenter: Yun-Yan Chang Date:2011/02/23 1 Introduction Design of BRICK ◦ ◦ ◦ ◦ Basic idea Rank indexing Handling increment Handling overflow Performance evaluation Conclusion 2 Present a novel active statistics counter architecture called BRICK (Bucketized Bank Indexed Counter). BRICK ◦ Store variable width counters entirely in SRAM while supporting fast access. ◦ Exploit statistical multiplexing technique. Group a fixed number of randomly selected counters into a bucket by an indexing scheme. 3 ◦ Figure 1 shows the effect of statistical multiplexing Each horizontal layer of bricks corresponds to a bucket The length of bricks corresponds to the real counter widths. Figure 1: BRICK wall (conceptual baseline scheme) 4 Randomly bundle N counters into h buckets, B1, B2, ..., Bh, where each bucket holds k counters and N = hk. Figure2: (b) Bucket structure 5 When access the yth counter, apply the index y to permuted index i by a permutation function π : {1...N} →{1. . .N}. The corresponding counter Ci can then be found in the lth i bucket Bl , where l = . k Figure2:(a) index permutation 6 Each bucket contains p sub-counter arrays A1, A2, ..., Ap to store the 1st, 2nd, ..., pth sub-counters. ◦ Assume the worst-case counter width is divided into p parts, which refer to as “sub-counters". Figure 3: (a) Within a bucket, segmentation of variable-width counters into sub-counter arrays. 7 For each counter, use indexing scheme to identify locations of sub-counters across the different subcounter arrays. Figure3: (b) Compact representation of variable-width counters. 8 Algorithm for get the value of ith counter. ※ rank(Ij, a): return the number of 1 in bit-string Ij, count form Ij[1] to Ij[a]. 9 Increment algorithm ※ varshift(s, j, c): bit-string s, start from jth bit, shift right c times. 10 32 ※ varshift(s, j, c): bit-string s, start from jth bit, shift right c times. 11 Extend data structure with full-size buckets F1, F2, ... , FJ , each bucket Ft is organized as k fullsize counters. ◦ When a bucket overflow occurs for some Bl , the next available full-size bucket Ft is allocated to store its k counters, where t is just +1 of the last allocated full-size bucket. ◦ Use a flag fl to set to indicate the overflowed buckets. ◦ The index of the full-size bucket Ft is stored in a field labeled t, which is associated with Bl . 12 Memory costs and lower bounds Sl :memory cost of each bucket S : total memory cost ◦ Lower bound of memory (1) lg M N (2) iN1 Ci M Ci: denote counter and counter value M: sum of counter values N: number of counters 13 Numerical results with various configurations The number of entries decreases exponentially as we go to the higher sub-counter arrays. (main compression) 14 Numerical results with various configurations The amount of extra storage only decreases slightly with additional levels in the BRICK implementation. 15 16 Results for real Internet trace USC: around 18.9 million packets, 1.1 million flows. UNC: around 32.6 million packets, 1.24 million flows. Worst-case counter width Total storage requirement USC UNC Naïve 25 bits/counter 3.85 MB 4.40 MB BRICK 10 bits/counter 1.39 MB 1.63 MB 17 BRICK is SRAM-efficient yet allows for fast counter lookup and increment. Index filed only requires small number of extra bits per bucket. 18