Space Shuffle: A Scalable, Flexible, and High-Bandwidth Data Center Network
Motivation behind the innovative Space Shuffle data center architecture, addressing goals of high-throughput and scalability with a unique approach to random interconnection and greedy routing. The architecture's outline, key elements, challenges, and evaluation are discussed alongside the construction of S2 topology using virtual coordinates and spaces.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Space Shuffle: A Scalable, Flexible, and High-Bandwidth Data Center Network
Motivation: Goals of Data Center Design High-bandwidth Data center applications generates high internal & external communication Flexibility Adding servers and expanding network bandwidth incrementally. Scalability Routing and Forwarding should rely on small forwarding state.
Motivation: Existing Data Center Architectures Forwarding State per switch (Scalability) Incremental Growth (Flexible) Network Bandwidth FatTree [SIGCOMM 08]Good Does not support multipath well. No shortest paths. No Fixed SWDC [SOCC 11] Greedy Routing Fair Yes Constant Jellyfish [NSDI 12] Better than FatTree & SWDC Random Interconnection K-shortest path routing is inefficient. Big forwarding state. Large and grows fast Yes
Motivation: Goal of Space Shuffle (S2) How to build a flexible data center architecture that achieves high-throughput and scalability ? Approach: Greedy routing on random interconnection. Challenges: How to build a random interconnection that enables greedy routing? How does the greedy routing protocol achieve high-throughput and near-optimal path length?
Outline Motivation Space Shuffle Data Center Topology The Routing Protocol in Space Shuffle Data Center Discussion & Evaluation
S2 Topology Construction -Assign Servers Servers and Top-Of-Rack switches. Uniformly assign servers to switches. Connect servers to switches. The rest ports are used for inter-switch connections.
S2 Topology Construction: -Virtual Coordinates Each Top-Of-Rack switch S is assigned with a set of Virtual Coordinate ?? Used for topology construction and routing. ??= ??1,??2, ,??? (? -dimensional vector) 0 ??1,??2, ,???< 1
S2 Topology Construction: -Virtual Spaces ? Virtual Spaces A Virtual Space is a ring Range of coordinate: [0,1) ???: The position of Switch S in the ?-th space ??= ??1,??2, ,??? Switch ID A B C D E F G H I Coor. 1 0.05 0.13 0.23 0.36 0.42 0.51 0.63 0.78 0.91 Coor. 2 0.17 0.62 0.91 0.42 0.53 0.58 0.73 0.26 0.97 0 0 I A C I B A H C G Space 1 Space 2 H B G D F D E E F
S2 Topology Construction: -Connect the switches I C A G A H I B B F D E I A H C I C B A A switch is physically connected to switches that are adjacent to itself in at least one space H C G Space 1 G Space 2 H D B G D F D E E E F F
S2 Topology Construction: -Connect the switches Switches with free inter-switch ports are connected randomly Each switch has 2? neighbors. A I B H C D G F E
S2 Topology Construction: -Deploy-as-a-whole Construction Assign hosts / switches Step 1 Generate coordinates (randomly) Step 2 Wire the network according to the coordinates. Step 3
S2 Topology Construction: -Incremental Construction Add a new switch T into existing S2 network Assign coordinate for T. For each space: PlaceT on the circle Find the switch SL and SR on the left/right side of T Disconnect SL,SR Connect T,SL; Connect T,SR SR T SL
Outline Motivation Space Shuffle Data Center Topology The Routing Protocol in Space Shuffle Data Center Discussion & Evaluation
Routing Protocol in S2: -Routable Address Greedy Routing / Forwarding Estimate the distance between next-hop and destination. Routable address of a packet to host h: ? ,?? ? : Coordinate of the access switch of ?? : The Identifier of . (IP, MAC .) Greedily route to the switch with coordinate ? Step 1 The switch forward to the host with identifier ?? Step 2
Routing Protocol in S2 -Definition of Distance Circular Distance: ??(?,?) distance between circular coordinate x and y. Minimum Circular Distance: ????(??,??) the Minimum ?? of switch A and B, measured on each of the ? spaces. CD(0.05,0.23) = |0.23-0.05| = 0.18 CD(0.17,0.91) = 0.17+(1-0.91) = 0.28 MCD2(A,C) = min(0.18,0.28)= 0.18 0 Switch Coor. 1 Coor. 2 A 0.05 C 0.23 0.17 0.91 0 A C S2 uses ??? for routing A C
Routing Protocol in S2 -Forwarding Decision using MCD When a switch receives a packet with address : ? ,?? If ? is its own coordinate, Forward the packet to host with ?? Otherwise, select a neighbor switch that minimizes the MCD to the destination Switch H A D G I MCD to the destination 0.35 0.18 0.13 0.19 0.06 The switch with minimum MCD to the destination gets the packet Minimum of Minimum CD: Greediest
Routing Protocol in S2 -Multipath Next-hop candidates: all neighbor switch with smaller MCDto the destination than current. Switch MCD to the destination Current Neighbor 1 Neighbor 2 Neighbor 3 Neighbor 4 0.3 0.5 0.1 0.2 0.4 the packet goes to the destination as long as MCD decreases It provides enough path diversity by doing such selection only on the first switch of the path.
Routing Protocol in S2: -Balanced Random Coordinates More traffic on links with small end-to-end MCD values. Uniformly distributed coordinates improves load balancing.
Outline Motivation Space Shuffle Data Center Topology The Routing Protocol in Space Shuffle Data Center Discussion & Evaluation
Evaluation Topology property Routing efficiency Practical throughput
Evaluation -Topology Property S2 and Jellyfish: Flexible FatTree: Fixed Bisection bandwidth # of switches S2 & Jellyfish topologies share similar theoretical throughput, better than FatTree.
Evaluation -Routing Table Length Jellyfish: Grows in ?(??log?) S2 : Constant 10 inter-switch ports
Evaluation -Routing Path Length SWDC: long routing paths, lower throughput. S2: near-optimal routing paths Jellyfish: optimal paths , expensive 12 inter-switch ports
Evaluation -Practical Throughput Greedy routing of S2 exploits the path diversity. S2 achieves near-Jellyfish S2 & Jellyfish both outperform SWDC throughput. 250-switch 500-host network
Summary High-bandwidth S2 demonstrate high-bandwidth and high network throughput. Flexibility S2 supports incremental construction. Scalability Greedy routing in S2 only requires constant size of routing state.
Thank you! Q & A
Comparing S2 with Jellyfish S2 Jellyfish Construction Coordinates Ring Topology Greediest Generate Almost Random Regular Graph Routing K-shortest path Hard to fit a Jellyfish topology into a routable coordinate space
Key-based Routing: -Definition Key-value stores https://www.facebook.com/photo.php?fbid= 677700648959984 Key-based Routing: route to the destination using the key of the content. (Not necessarily to know the IP) IP-based Routing: IP of the destination.
Key-based Routing: -Delivery Guarantee For any destination coordinate X, greediest routing will route the packet to a switch S, S is closest to X in at least one space. Solution: Keep one replica in each of fist r spaces and route using MCDr , r <=L For data a with key Ka, use global hash function H to calculate the destination coordinate X=H(Ka) In each of the r spaces, the access switch of the server for a is selected using global hash function H(Ka)
S2 Topology Construction- -Overview H servers and N Top-Of-Rack switches. Uniformly assign switches to servers. Generate Virtual Coordinates of switches. Connect the switches according to the coordinates, using the rest ports. (x1,x2, ) ? ?or ? ?+ 1 servers per switch The rest ports are used for inter-switch connections
