close

Вход

Забыли?

вход по аккаунту

?

huan_damon

код для вставкиСкачать
Memory Management Algorithms
for DSM Switches
Huan Liu, Damon Mosk-Aoyama
High Performance
Switching and Routing
Telecom Center Workshop: Sept 4, 1997.
Spring 2004
EE384Y project
1
Distributed Shared Memory Switch
пЃ¶
What is known (for FIFO)
пѓ�
пѓ�
пЃ¶
2N is necessary
3N-1 is sufficient
Questions:
пѓ�
пѓ�
Spring 2004
Can we close the gap?
Possible to have an implementable algorithm?
EE384Y project
2
Our main results
пЃ¶
On the gap
пѓ�
пѓ�
пЃ¶
Counter example to show 2.25N is necessary
A heuristic that uses 2.5N memories
On practical algorithms
пѓ�
Spring 2004
Simulation results on simple algorithms under
Bernoulli i.i.d. traffic
EE384Y project
3
The counter example
Consider 4x4 switch
пЃ¶ Can generalize to arbitrary N
пЃ¶
11
5
2
6
?3
3
7
7
?4
4
8
8
22
Spring 2004
…
1
EE384Y project
5
…
Output 1
6
Output 4
4
If we have N/4 more
11
6
2
7
35
3
8
8
24
4
9
9
52
Spring 2004
…
1
EE384Y project
6
…
Output 1
7
Output 4
5
Observation
Greedily minimizing the number of memories
used can lead to trouble
пЃ¶ Need to reuse memories later as time slot fills up
пЃ¶
1 1 1 1
2222
3333
7654
Spring 2004
EE384Y project
1
2
3
4
6
Heuristics with 2.5N memories
пЃ¶
пЃ¶
пЃ¶
пЃ¶
Minimize intersection between adjacent time slots
Minimize intersection between neighboring pairs
After N/2 cells arrived in a time slot, reuse memories
already assigned to the adjacent time slot.
Simulation has been running for 100M+ cycles with no
problem
Minimize intersection
5 1 31 1
6 242 2
1 624 3
4
Spring 2004
EE384Y project
7
Random algorithm
Assign memories to arriving cells randomly
пЃ¶ Drop if another cell using the memory is
пЃ¶
пѓ�
пѓ�
departing now
departing in the future in the same time slot
Si
Spring 2004
……
EE384Y project
S2 S
1
8
Upper bound on Drop Rate
пЃ¶
Suppose there are пЃ§ N memories. The drop probability is
s1 N пЂ« si пЂ« 1 N пЂ­
P ( drop | Q пЂЅ i ) пЂЅ
пЃ¶
s1 N
пЃ§N
пЂЅ
пЃ§N
пЃ§
пЃ§
The drop rate can now be computed as:
п‚Ґ
P ( drop ) пЂЅ
 P (Q
п‚Ґ
пЂЅ i ) P ( drop | Q пЂЅ i ) пЂЅ
iпЂЅ0
пЃ¶
s1 пЂ« si пЂ« 1 пЂ­
si пЂ« 1 N
s1si пЂ« 1
 (s
iпЂЅ0
i
пЂ­ s i пЂ« 1)
пѓ¦
s1si пЂ« 1 пѓ¶
пѓ§пѓ§ s 1 пЂ« s i пЂ« 1 пЂ­
пѓ·пѓ·
пЃ§ пѓё
пѓЁ
пЃ§
Use Si distribution from M/M/1
пѓ¶
пЃ¬пѓ¦
1
пЃ¬
пѓ·пѓ·
P ( drop ) п‚Ј пѓ§пѓ§ 1 пЂ«
пЂ­
пЃ§ пѓЁ 1 пЂ« пЃ¬ пЃ§ (1 пЂ« пЃ¬ ) пѓё
Spring 2004
EE384Y project
9
Fixed Arrival Rate
Spring 2004
EE384Y project
10
Fixed Number of Memories
Spring 2004
EE384Y project
11
Distributed random algorithm
пЃ¶
пЃ¶
Each packet makes independent decision
Pick a random memory that is NOT
пѓ�
пѓ�
пЃ¶
departing now
departing in the same time slot in the future
If two arriving packets pick the same memory, we drop one
Spring 2004
EE384Y project
12
Distributed random algorithm - simulation
lambda = 0.5
lambda = 0.7
drop rate
40.00%
lambda = 1
20.00%
0.00%
1.5
2
2.5
3
number of memories
Spring 2004
EE384Y project
13
Centralized random algorithm
пЃ¶
пЃ¶
Assign each packet in turn
Randomly pick a memory that is NOT
пѓ�
пѓ�
пѓ�
Spring 2004
departing now
departing in the same time slot in the future
assigned for other packets arriving at the same time
EE384Y project
14
Centralized random algorithm - simulation
30.00%
lambda = 0.8
lambda = 0.85
lambda = 0.9
drop rate
lambda = 0.95
lambda = 1
15.00%
0.00%
1.5
1.6
1.7
1.8
1.9
2
number of memories
Spring 2004
EE384Y project
15
Conclusion
пЃ¶
Still gap пѓЁ more work
пѓ�
пѓ�
пЃ¶
Better counter example?
Prove 2.5N is sufficient
Also gap between theory and practical algorithm
Spring 2004
EE384Y project
16
Документ
Категория
Презентации
Просмотров
3
Размер файла
126 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа