# Capacity Allocation Paradox Isaac Keslassy Joint Work with

Capacity Allocation Paradox Isaac Keslassy Joint Work with Asaf Baron and Ran Ginosar EE Department, Technion, Haifa, Israel The Capacity Allocation Paradox Node A CA RA Node B RB Router CR Node C CB Finite (small) buffers Unlimited queues Capacity Allocation Paradox: Adding Capacity Can Destabilize the Network 2 Marakana Soccer Stadium UnStable Stable Safety Check Brazillian Line Enter the stadium Fast Security Check Argentinian Line Fast Swipe Ticket Entrance Fast Security Check Slow Security Check 3

Motivation Small buffer networks are widely used Network On-Chip SpaceWire Interconnection of Computers When QoS not met: add capacity [Guz et al., 06] May destabilize the network 4 Previous Work: Selfish Routing Braesss Paradox (1968) Difference: We assume fixed routing 5 Previous Work: Cyclic Dependency Kumar & Seidman (1990) Dai, Hasenbein & Vande Vate (1998) Instability even though capacity > data rate Adding capacity may destabilize a network

Differences: No cycles in dependency graph Single router Each packet visits router only once Several simple arbitration policies Independent of initial conditions New fundamental reason: Finite buffers 6 A General Phenomenon Finite (small) buffers Arrivals: Periodic, Poisson Node A CA RA Node B RB Router CR Node C CB Unlimited queues When buffer is full:

1. Blocking: Wormhole Routing 2. Dropping (with retransmission): Store And Forward 7 Intuition Assume A has priority: Node A Router CCA=2 A=1 1 [pkt/T] Node B 1 [pkt/T] CR=2 Node C CB=1 Buffer of 1 bit Share of CR 2 (a) CA=1 1 A1 A2 A3 B1 B2 B3

T Share of CR 3T 2T (a) 2 (b) CA=2 1 A1 B1 (1) T/2 T A2 B1 (2) 3T/2 (b) 2T A3 B2 (1) 5T/2 3T 8 What are the conditions for stability? Necessary conditions: Node A C A RA Node C

CR RA RB Node B CB CB RB Stability Regions, CR =0.273Mflits/sec 0.5 0.45 0.4 CR is constant RA = R B 0.35 0.3 CB [Mflit/sec] 0.25 0.2 0.15 0.1 0.05 0.05 0.1 0.15 0.2 0.25 0.3 CA [Mflit/sec]

0.35 0.4 0.45 0.5 CA 9 Stability Regions, CR =0.273Mflits/sec 0.5 Case #1:C A CB CR 0.45 0.4 0.35 Buffers in the router hold no more than one data unit CB [Mflit/sec] 0.3 0.25 0.2 0.15 ? 0.1 Queue A 0.05

Buffer A 0.05 0.1 0.15 0.2 0.25 0.3 CA [Mflit/sec] 0.35 0.4 0.45 0.5 CA CR Node C Queue B CB Buffer B Necessary conditions are also sufficient. 10 Example 1: Analysis Stability Picture CR = 273[Kf/s] (Constant) EPRR 500

450 2 400 4 350 CB [Kf/s] CB [Kf/s] 300 R A = RB = 100[Kf/s] 0 250 2 3 200 150 1 100 0 50 50 100 150 200 CA [Kf/s] 250

CA [Kf/s] 300 350 400 450 500 11 Example #1 Capacity Allocations Analytic Stability regions, CRC =0.273Mflits/sec 0.5 0.45 0.4 2 4 3 2 0.35 CBR [Mflit/sec] 0.3 0.25 0.2 0.15 UnStable Stable 1

0.1 Case #3 #1 #2 0.05 0.05 0.1 0.15 0.2 0.25 0.3 CAR [Mflit/sec] 0.35 0.4 0.45 0.5 Node A =300 =190 CA=110 RA = 100 Node C CR=273 Node B RB = 100 CB=150 =110

1000 [flits/pckt] Buffer Size: 16 Flits Exhaustive Round Robin, Wormhole 12 Results Simulation Stability Regions C = 273[Kf/s] (Constant) Analytic+Simulation Stability regions for CR =0.273Mf/s R 325 4 2 300 275 CB [Kf/s] 250 R A = RB = 100[Kf/s] 225 3 200 2 175 150 125 1 125

150 175 200 225 CA [Kf/s] 250 275 300 325 13 Example #2 Wormhole Routing GPS GPS Round-Robin RRPF 500 450 450 450 400 400 400 350 350 350 300

500 CB [Kf/s] 500 CB [Kf/s] CB [Kf/s] ExhaustiveEPRR Round Robin 300 300 250 250 250 200 200 200 150 150 150 550 600 CA [Kf/s] 650 700 550

600 CA [Kf/s] 650 700 550 600 CA [Kf/s] 650 700 1000 [flits/pckt], Buffer Size: 16 Flits, RA = 500kf/s, RB = 100kf/s 14 Example #3 Store and forward 2.5 2.5 2.25 2.25 2 2 CBR [Mbit/sec] CBR [Mbit/sec] Priority, CRCC =2.1Mbit/sec Exhastive, C =2.1Mbit/sec Strict Priority, R = 2.1[Mbit/s] Exhaustive RR,RCCR = 2.1[Mbit/s] 1.75 1.5

1.25 1.75 1.5 1.25 1.25 1.5 1.75 2 CAR [Mbit/sec] (a) 2.25 2.5 1.25 1.5 1.75 2 CAR [Mbit/sec] 2.25 2.5 (b) Poisson Arrivals with Parameters: A = 100, B = 100 Packet Length 10^4 bit Buffer Size 3-4 packets 15 Example #3 Store and forward Round-Robin, C =6.1Mbit/sec Exhastive, C =6.1Mbit/sec RR, C R = 6.1[Mbit/s]Exhaustive RR, CR = 6.1[Mbit/s

RC RC 3.5 2.5 2.5 3 CBR [Mbit/sec] All packets need to arrive sometime CBR [Mbit/sec] Poisson Arrivals: A = 500 B = 100 3 Packet = 10^4 bit Buffer 3 packets 3.5 2 2 1.5 1.5 5.25 5.5 5.75 6 CAR [Mbit/sec] (c) 6.25

6.5 5.25 5.5 5.75 6 CAR [Mbit/sec] 6.25 6.5 (d) 16 Summary Adding capacity may destabilize even a simple network The scheduling algorithm affects the stability of the network (even if workconserving) GPS arbitration: always stable 17 Thank you. 18

## Recently Viewed Presentations

• kilogram . of feathers or a . kilogram . of sand? Unit 13 Lesson 1 What Are Solids, Liquids, and Gases? More Properties. Which plate has more volume? Which ball has more mass? Unit 13 Lesson 1 What Are Solids,...
• The Multiple Choice Section of the Dreadful AP Exam. By: Caroline Pugh, 3rd Hour. After this presentation, students will have a better understanding of the multiple choice section of the AP Language and Composition exam. Objective: Reading the passages really...
• www.mymajors.com NextStepU www.collegeprowler.com www.zinch.com See Mrs. Donati for log-in info See pg. 9 in the planning guide for a guide to college selection Education Pays Learn to Earn Ready to LEARN when you enter Kindergarten and ready to EARN with...
• Firefly. Website. MyEd. MyEd is a free parent app that gives you a multitude of communication and information features to stay in touch with what is happening at school. The app gives you direct access to your child's attendance record,...
• Major Circulation Patterns. Earth's oceans and atmosphere move heat from the equator (and cold from the poles). Warm air (less dense) rises at the equator and sinks as it cools (at the poles)
• Chinese IAB (IA +IB) 11 Weather and Internet Module (L21-L22) Weather and Internet test review Step 1 Step 2 Please click on page 6 to find Module Learning Guide in the right panel under Handouts in the first module.
• Randall Price, in his book, The Stones Cry Out, suggested that the nail apparently hit a knot in the olive stake upon which this man was crucified, causing the nail and heel to be removed together, due to the difficulty...
• There are a variety of verbal and non-verbal forms of communication. These include body language, eye contact, sign language, haptic communication, and chronemics. Other examples are media content such as pictures, graphics, sound, and writing.