### Dragonfly Topology for networks

```Dragonfly Topology for networks
Presented by：Long Bao
Netwrok
Topology
Topology
Topology
Topology
Perfect?
Topology
•
•
•
•
Bandwidth
Latency
Cost
Scalability
Outlet
• Dragonfly Topology Description
• Dragonfly Topology Routing
• Cost analysis
• Conclusion
Dragonfly Topology Description
• Hierarchical Network
– Router, Group and System
Figure 1. High-level block diagram of a dragonfly topology
Dragonfly Topology Description
• (a, p, h) network
O0, O1,…, Oh-1
Oh, O1+h,…, O2h-1
Ok1-h, O1+k1-h,…, Ok1
Inter-Group
Interconnection
Network
Router 0
•
•
•
•
K=p+a+h-1
K’=a(p+h)
K’>>K
N=ap(ah+1)
I0, I1,…, Ip-1
Router 1
Ip, I1+p,…, I2p-1
...
Router a-1
Ik1-p, I1+k1-p,…, Ik1
Dragonfly Topology Description
• A simple example—(4,2,2) Network
R1
R0
R0
R3
R2
R1
R2
R3
R3
R0
R2
R1
R1
R2
R
R0
3
R1
R2
R2
R1
R3
R0
R0
R3
R0
R3
R1
R2
R2
R1
R3
R0
R0
R1
R2
R3
R0
R1
R2
R3
Dragonfly Topology Description
• Topology Variations
R0
R0
R1
R2
2
R1
R3
R2
R4
2
R3
R5
R6
R7
Dragonfly Topology Routing
• Existing routing algorithm
– Minimal (Min)
– Valiant (Max)
• UGAL-L
• UGAL-G
Dragonfly Topology Routing
• Minimal and Valiant method
1
2
2
1
R0
R1
5
4
R2
3
R1
R0
R3
3
R0
R1
R2
R3
Non-mininal
route
R2
R3
mininal route
Dragonfly Topology Routing
• UGAL
– Problems
• Limited throughput
R0
R1
R2
R3
R0
R1
R2
Group 0
R3
Group 1
O0, O1 O2, O3
O4, O5 O7, O8
Non-mininal
route
R0
R1
R2
R3
mininal route
Group 2
I0, I1
I2, I3
I4, I5
I7, I8
Dragonfly Topology Routing
• UGAL
– Problems
• High intermediate latency
R0
R1
R2
R3
R0
Q1
Group 0
Q0
R0
Group 2
Q2
R1
R2
R1
Q3
R3
R2
R3
Group 1
Cost analysis
Dimension 3
channels
15
Dimension 2
channels
15
15
Dimension 1
Router
channels
16
30
Router
15
Flattened Butterfly
Global
Inter-group channels
15
Dragonfly
• (15+15)/(15+15+15+15)=50%
• 16/(16+15+15+15)=25%
Inter-group
channels
Local
Conclusion
• Less diameter
• Low cost
• Small latency
Future Work
• Routing Strategy Research