Transcript Slides

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
Network
Bandwidth
Incremental
Growth
(Flexible)
FatTree
No shortest Good
paths.
No
[SIGCOMM’
08] multipath well.
Does
not support
SWDC
Fair
YesGreedy
[SOCC’11]
Jellyfish
Better than
Random
Interconnection
Yes
[NSDI’12]
FatTree & SWDC
K-shortest path routing is inefficient.
Big forwarding state.
Forwarding
State per
switch
(Scalability)
Fixed
Routing
Constant
Large and
grows fast
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
•
• 𝑋𝑆 = 𝑥𝑠1 , 𝑥𝑠2 , … , 𝑥𝑠𝐿 •
Switch ID Coor. 1
Coor. 2
•
•
A
0.05 0.17
B
C
D
E
F
G
H
I
0.13
0.23
0.36
0.42
0.51
0.63
0.78
0.91
0.62
0.91
0.42
0.53
0.58
0.73
0.26
0.97
𝐿 Virtual Spaces
A Virtual Space is a ring
Range of coordinate: [0,1)
𝑥𝑠𝑖 : The position of Switch S in
the 𝑖-th space
0
0
A
I
H
C G
Space 1
G
F
C
B
E
D
I
A
Space 2
B
F
E
D
H
S2 Topology Construction:
-Connect the switches
C
I
A
G
H
B
F
E
A
I
B
D
I
H A B
C
I
C
A
• A switch is physically
H
connected to switches
C G
Space 1
Space 2
DH
that are adjacent to itself G
in at least one space G
B
D
F
D
E
E
F
F
E
S2 Topology Construction:
-Connect the switches
• Switches with free inter-switch ports are connected
randomly
• Each switch
A
has 2𝐿 neighbors.
I
B
H
C
D
G
F
E
S2 Topology Construction:
-Deploy-as-a-whole Construction
Step 1
• Assign
hosts / switches
Step 2
• Generate coordinates
(randomly)
Step 3
• Wire the network
according to the
coordinates.
S2 Topology Construction:
-Incremental Construction
• Add a new switch T into existing S2 network
• Assign coordinate for T.
• For each space:
• Place T on the circle
• Find the switch SL and SR on the left/right side of T
• Disconnect SL,SR
SR
• Connect T,SL; Connect T,SR
SL
T
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 ….)
Step 1
Step 2
• Greedily route to the switch with coordinate 𝑋ℎ
• The switch forward to the host with identifier 𝐼𝐷ℎ
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.
Switch Coor. 1 Coor. 2
A
C
0.05
0.23
0.17
0.91
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
0
A
S2 uses 𝑀𝐶𝐷 for routing
C
C
A
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
MCD to the destination
The switch
H with minimum
0.35 MCD to the destination gets the packet
A
0.18
D
0.13
Minimum
of Minimum CD: Greediest
G
0.19
I
0.06
Routing Protocol in S2
-Multipath
• Next-hop candidates: all neighbor switch with
smaller MCD to the destination than current.
Switch
MCD to the destination
Current
0.3
Neighbor 1
0.5
Neighbor
2 goes to the destination
0.1
the packet
Neighbor
0.2
as 3long as MCD decreases
Neighbor 4
0.4
• 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
Bisection bandwidth
S2 and Jellyfish: Flexible
FatTree: Fixed
# 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 near-Jellyfish
path diversity.
S2
achieves
S2 & Jellyfish
throughput.
both outperform SWDC
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!
Comparing S2 with Jellyfish
Construction
Routing
S2
Coordinates
Ring
Topology
Greediest
Jellyfish
Generate ‘Almost’
Random Regular
Graph
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