Application of Bloom Filters for Longest Prefix Matching and ...

Application of Bloom Filters for Longest Prefix Matching and ...

Designing Packet Buffers for Router Linecards Sundar Iyer, Ramana Kompella, Nick McKeown Reviewed by: Sarang Dharmapurikar Background Routers need to buffer packets during congestion Thumb rule : Buffer size should be RTT x R With RTT = 0.25s and R = 40 Gbps, Buffer size = 10 Gbits o o Sarang Dharmapurikar Cant use SRAM, they are small and consume too much power Only SDRAM provides the required density 2 Problems..

SDRAM is slow, hence less memory bandwidth Why not use a big data bus to get more memory bandwidth? Sarang Dharmapurikar 3 Answer 320 bytes Packet A Packet B Packet C underutilized bandwidth Sarang Dharmapurikar 4

Parallel Memory Banks 320 bytes However, packet departure order is not known Scheduler might request for the packets which happen to be stored in the same bank Hence one bank will be busy and others idle, degrading the throughput Sarang Dharmapurikar 5 Alternative Cache packets and write them in SDRAM as one word at a time for one queue 320 bytes A2

A1 Likewise, read packets from DRAM, one word for a queue at a time, give out the necessary data and cache the rest B1 B2 C1 C2 Sarang Dharmapurikar 6 Architecture of the Hybrid SRAM-SDRAM buffer Sarang Dharmapurikar 7

Head SRAM buffer w b bytes arrive in b time slots all for the same queue 1 D(i,t) X(i,t) i Q Objective : Put a bound on w Sarang Dharmapurikar 8 Scheduler

2 b bytes leave in b time slots Of these b bytes, any byte can be from any queue Lower Bound on the Head-SRAM size Theorem 1: Additional b-1 bytes w > (b-1)(2 + lnQ) Example: Let b = 3

Q=9 Bytes required = (b-1) + (b-1) + under run Under run Sarang Dharmapurikar 9 starting b-1 bytes Lower bound on the Head-SRAM size Proof of theorem 1: First iteration : read one byte from each FIFO Q/b FIFOs will be replenished with b bytes each Q(1-1/b) FIFOs will have a deficit of D(i,Q) = 1 Second iteration : read one byte from each of Q(1-1/b) FIFOs

having D(i,Q) = 1 Q(1-1/b)/b will be replenished with b bytes each Q(1-1/b)2 will have a deficit of D(i,Q) = 2 Xth iteration : Q(1-1/b)x FIFOs will have a deficit of D(i,Q) = x Solve for Q(1-1/b)x = 1 X > (b-1)lnQ Hence, buffer rquirement is : w > (b-1)(2 + lnQ) Sarang Dharmapurikar 10

A Memory Management Algorithm Objective: Give an Algorithm that is closer to this bound Most Deficit Queue First (MDQF) Service (replenish) the SRAM FIFO with most deficit first Sarang Dharmapurikar 11 Some Terminology 1 1 2 2

3 3 4 4 Q Q i F (i, t ) D ( k , t ) F (i ) Max{F (i, t )} 1 Sarang Dharmapurikar 12

MDQF analysis F(2, t-b) Lemma1 : F(1) < b[2+lnQ] F(1) D ( 1 ) j D( j , t b) D(i, t b) F (1) b D ( 2 ) D ( 3 ) i F (2) F (2, t b) D(i, t b) D( j , t b) D ( 4 )

i +b F (2) F (1) b F (1) b D ( Q ) t -b Sarang Dharmapurikar 13 t MDQF Analysis F(3, t-b) F(2) D ( p, t b) D(m, t b) D(n, t b) F (2) b 2 2

F (3) F (3, t b) D(m, t b) D(n, t b) D( p, t b) F (3) F (2) b F ( 2) b 2 D ( 1 ) p m D ( 2 ) D ( 3 ) m n n

D ( 4 ) D ( Q ) t -b Sarang Dharmapurikar +b 14 t MDQF Analysis F(i+1, t-b) F(i) D ( 1 ) F (i ) b F (i 1) F (i ) b i D ( 2 )

F (Q) Qb D ( i ) +b F (1) b[2 ln Q] D ( Q ) t -b t Theorem 2: For MDQF to guarantee that a requested byte is in SRAM, it is sufficient to hold b(3 + lnQ) bytes in each Head-FIFO Sarang Dharmapurikar 15 MMA that tolerates bounded pipeline delay

Pre-compute some of the memory requests to find out which queue under-runs Critical Queue : A queue with more requests in the look ahead buffer than bytes to give Earliest Critical Queue : A queue that turns critical the earliest Sarang Dharmapurikar 16 Most Deficit Queue First with Pipeline Delay (MDQFP) Algorithm: Replenish the earliest critical queue first If no critical queues then replenish the one that will most likely become critical in the future Lemma3:

F (i ) Fx (1) Max{ i i x b b i b 1} Theorem 3: w = Fx(1) + b Corollary 1 : x Qb , w 2b Sarang Dharmapurikar 17 Tradeoff between SRAM size and pipeline delay

QFx(1), total SRAM Q = 1000, b=10 d 1 Fx (1) dx x F (i ) x b Fx (1) Max{ b 1} i b i i x, pipeline delay

Sarang Dharmapurikar 18 Dynamic SRAM allocation So far all the queues had the same length which was static SRAM can allocated dynamically to the queues depending on the requirement further reduction in SRAM size The amount of SRAM can be reduced to Q(b-1) for a Look ahead buffer of Q(b-1) + 1 Sarang Dharmapurikar 19 Conclusions High capacity and high throughput packet buffers are needed in any router line card Packet buffers made out of only SRAMs are impractical,

SDRAMs are used SDRAM buffer memory used with SRAM cache memory can give the required throughput performance Without any pipeline delay the SRAM requirement scales as QblnQ With With tolerable delay of Qb time slots, the requirement scales as Qb Sarang Dharmapurikar 20

Recently Viewed Presentations

  • Summer Reading Grade 9 -

    Summer Reading Grade 9 -

    "You don't forget the face of the person who was your last hope." Katniss Everdeen, Pg 85. I think the emphasis is on the word "last". This person is your last hope- you're putting everything into them, in the hopes...
  • E-Commerce: Selling Online E-Commerce: Selling Online  Online Auctions

    E-Commerce: Selling Online E-Commerce: Selling Online Online Auctions

    E-Commerce: Selling Online Online Auctions How to Sell on Ebay . . . Register Sign Up to Accept PayPal (optional) How to Sell on Ebay . . .
  • Présentation PowerPoint - Alpine Space

    Présentation PowerPoint - Alpine Space

    these are the results from the StressTest for all participating regions, a report of strategic Alpine Space topics for interregional cooperation, a joint transnational cluster action plan and a tool kit for dissemination on stress testing and entrepreneurial workshops.
  • Building Your Own Docker Container Cloud on IBM

    Building Your Own Docker Container Cloud on IBM

    Java and Node.js Applications. Shift to a DevOps Methodology. Shift to a Microservices style Architecture to gain flexible and dynamic scalability to rapidly respond to changes in Website Patterns. Move to a Scale-Out Hardware Infrastructure. Chose Docker Containers on Linux...
  • English 299C: Film as Narrative Art -

    English 299C: Film as Narrative Art -

    English 299B: Film as Narrative Art Mr. Kelley The Seventh Seal (Ingmar Bergman, 1956) In my film, the crusader returns from the Crusades as the soldier returns from war today.
  • UML Diagrams - Learngroup

    UML Diagrams - Learngroup

    UML Diagrams. Class Diagram. Class diagrams. ... Class diagrams are used for a wide variety of purposes, including both conceptual/domain modeling and detailed design modeling. Class diagrams elements. Class. Attribute. ... you would only model one class, called ...
  • BEOWULF - Loudoun County Public Schools

    BEOWULF - Loudoun County Public Schools

    Poem treats universal themes (ex: life and death; good and evil) Major characters often deliver long, serious speeches. ... What controversial topic did the Wife of Bath's Tale discuss? Why/How is this still relevant today? Symbolism.
  • Ux PowerPoint Name

    Ux PowerPoint Name

    Isometric Pictorial. Isometric means equal measure. Three adjacent faces on a cube will share a single point. Edges converge at one point will appear as 120 degree angles or 30 degrees from the horizon line. Isometric and Oblique Pictorials. Introduction...