Random Regular Graph & Generalized De Bruijn Graph With K .

2y ago
16 Views
3 Downloads
2.19 MB
23 Pages
Last View : 1m ago
Last Download : 2m ago
Upload by : Mara Blakely
Transcription

Random Regular Graph &Generalized De Bruijn Graphwith k-shortest Path RoutingPeyman Faizian, Md Atiqul Mollah, Xin YuanScott Pakin, Michael LangFlorida State UniversityLos Alamos National Laboratory

Where it All Started Random Regular topologies(Jellyfish) have been proposed for datacenters and HPC clusters They are known to have some good topological properties They achieve higher performance in compare to Fat Tree undercertain traffic patterns

We are Going to do this the Hard Way Derive theoretical bounds for the following key metrics on any DRG Diameter Average k-shortest path length Load balancing property Evaluate RRG based on these criteria Introduce a near-optimal DRG and compare it to RRG throughsimulation

What is a Random Regular Topology Random graph between ToR switches Each switch has k portsr ports connected to other switchesk-r ports connected to processing nodesr-regular random interconnecttopology(RRG)[Singla et al; NSDI’12]

What We Know About RRG High bisection bandwidth High network capacity Sufficient short path diversity k-shortest path routing is preferred[Singla et al; NSDI’12]

What is Needed for K-Path Routing High bisection bandwidth Minimal resource usage Low diameter Low average k-shortest path length Good load balancing Even distribution of paths over SD pairs Even distribution of load over all network links

What Should We Compare RRG to RRG has been compared to one of the best available designs Fat Tree We want to compare it to the best possible design Random Regular Graphs are a special case of Directed Regular Graphs We derived the optimal bounds for all discussed properties on Regular Graphs4 Lemmas. Some Graph Theory!

Diameter33%π·π‘–π‘Žπ‘šπ‘’π‘‘π‘’π‘Ÿ π‘œπ‘“ 𝐷𝑅𝐺(𝑁, π‘Ÿ) π‘™π‘œπ‘”π‘Ÿ 𝑁 π‘Ÿ 1 1 166%

Average Shortest Path Length14%π΄π‘£π‘’π‘Ÿπ‘Žπ‘”π‘’ π‘˜ π‘ β„Žπ‘œπ‘Ÿπ‘‘π‘’π‘ π‘‘ π‘π‘Žπ‘‘β„Ž π‘™π‘’π‘›π‘”π‘‘β„Ž π‘“π‘œπ‘Ÿ 𝐷𝑅𝐺(𝑁, π‘Ÿ) β„Ž 1 𝑗𝑗 1 π‘—π‘Ÿ β„Žπ‘…π‘˜(𝑁 1)

Average k-Shortest Path Lengthπ΄π‘£π‘’π‘Ÿπ‘Žπ‘”π‘’ π‘˜ π‘ β„Žπ‘œπ‘Ÿπ‘‘π‘’π‘ π‘‘ π‘π‘Žπ‘‘β„Ž π‘™π‘’π‘›π‘”π‘‘β„Ž π‘“π‘œπ‘Ÿ 𝐷𝑅𝐺 𝑁, π‘Ÿ 𝐿𝐾(𝑁, π‘Ÿ, π‘˜) β„Ž 1 𝑗𝑗 1 π‘—π‘Ÿ β„Žπ‘…π‘˜(𝑁 1)

Path DistributionNetwork Degree 30, N 901min π‘›π‘’π‘šπ‘π‘’π‘Ÿ π‘œπ‘“ π‘π‘Žπ‘‘β„Žπ‘  π‘œπ‘“ π‘™π‘’π‘›π‘”π‘‘β„Ž 𝐻 π‘Ÿ π‘Ÿ2 π‘Ÿπ»π‘ 1

Load Balancing All-to-All communication pattern Use K-shortest paths between each SD pair Monitor the number of flows passing each link Pick the load value on the most loaded link in the network

Load Balancing𝐿𝐾 𝑁, π‘Ÿ, π‘˜ (𝑁 1)max π‘™π‘–π‘›π‘˜ π‘™π‘œπ‘Žπ‘‘ π‘“π‘œπ‘Ÿ 𝐷𝑅𝐺 𝑁, π‘Ÿ 𝑀𝐿(𝑁, π‘Ÿ) π‘Ÿ

A Quick Recap We compared these topological properties of Jellyfish with optimal: DiameterAverage k-shortest path lengthPath distributionLoad distribution In some of the cases Jellyfish is far from theoretical bounds But is there any near optimal r-regular topology?

Generalized de Bruijn Graph We proved that GDBG has: Near optimal diameter Near optimal averagek-shortest path length Near optimal path distribution Near optimal load distribution𝐺𝐷𝐡𝐺(6,2)7 Lemmas. Some More Math!π‘›π‘œπ‘‘π‘’ 𝑖 π‘π‘œπ‘›π‘›π‘’π‘π‘‘π‘  π‘‘π‘œ π‘›π‘œπ‘‘π‘’π‘ :𝑖 𝑑, 𝑖 𝑑 1, , 𝑖 1 𝑑 1 π‘šπ‘œπ‘‘ 𝑁

GDBG: A Near Optimal r-Regular Topology

GDBG: A Near Optimal r-Regular Topology

There is more GDBG is a near optimal r-regular topology It can be used as a simulation benchmark to evaluate othertopologies in this family We are going to evaluate RRG

Simulation Topology Generalized de Bruijn Graph(almost optimal) Jellyfish Routing Hop limited all path routing (GDBG) k-shortest path routing (Jellyfish) Traffic Pattern Node level random permutationNode level shiftSwitch level random permutationSwitch level shift Metric Aggregate throughput

Node Level ThroughputN 150, Network Degree 8

Switch Level Throughput

Conclusion Derived theoretical bounds for the following key metrics on any DRG Average k-shortest path length Load balancing property RRG is near optimal in terms of average k-shortest path length RRG is far from optimal for all other metrics GDBG was found near optimal for all metrics GDBG was used as a simulation benchmark to evaluate RRG Depending on traffic pattern, RRG is not always near optimal

Thanks for your timeQuestions

Average k-shortest path length Load balancing property RRG is near optimal in terms of average k-shortest path length RRG is far from optimal for all other metrics GDBG was found near optimal for all metrics GDBG was used as a simulation benchmark to evaluate RRG Depending on traffic pattern, RRG is not always near optimal

Related Documents:

The totality of these behaviors is the graph schema. Drawing a graph schema . The best way to represent a graph schema is, of course, a graph. This is how the graph schema looks for the classic Tinkerpop graph. Figure 2: Example graph schema shown as a property graph . The graph schema is pretty much a property-graph.

Oracle Database Spatial and Graph In-memory parallel graph analytics server (PGX) Load graph into memory for analysis . Command-line submission of graph queries Graph visualization tool APIs to update graph store : Graph Store In-Memory Graph Graph Analytics : Oracle Database Application : Shell, Zeppelin : Viz .

Start by finding out how Python generates random numbers. Type ?random to find out about scipy's random number generators. Try typing 'random.random()' a few times. Try calling it with an integer argument. Use 'hist' (really pylab.hist) to make a histogram of 1000 numbers generated by random.random. Is th

Start by finding out how Python generates random numbers. Type ?random to find out about scipy's random number generators. Try typing 'random.random()' a few times. Try calling it with an integer argument. Use 'hist' (really pylab.hist) to make a histogram of 1000 numbers generated by random.random. Is the distribution Gaussian, uniform, or .

a graph database framework. The proposed approach targets two kinds of graph models: - IFC Meta Graph (IMG) based on the IFC EXPRESS schema - IFC Objects Graph (IOG) based on STEP Physical File (SPF) format. Beside the automatic conversation of IFC models into graph database this paper aims to demonstrate the potential of using graph databases .

1.14 About Oracle Graph Server and Client Accessibility 1-57. 2 . Quick Starts for Using Oracle Property Graph. 2.1 Using Sample Data for Graph Analysis 2-1 2.1.1 Importing Data from CSV Files 2-1 2.2 Quick Start: Interactively Analyze Graph Data 2-3 2.2.1 Quick Start: Create and Query a Graph in the Database, Load into Graph Server (PGX) for .

1.14 About Oracle Graph Server and Client Accessibility 1-46. 2 . Quick Starts for Using Oracle Property Graph. 2.1 Using Sample Data for Graph Analysis 2-1 2.1.1 Importing Data from CSV Files 2-1 2.2 Quick Start: Interactively Analyze Graph Data 2-3 2.2.1 Quick Start: Create and Query a Graph in the Database, Load into Graph Server (PGX) for .

1.8 The complete graph, the \Petersen Graph" and the Dodecahedron. All Platonic solids are three-dimensional representations of regular graphs, but not all regular graphs are Platonic solids. These gures were generated with Maple.10 1.9 The Petersen Graph is shown (a) with a sub-graph highlighted (b) and that sub-graph displayed on its own (c).