Scafida

Scafida. is a scale-free data center architecture inspired network generation algorithm. This algorithm was invented by László Gyarmati and Tuan Anh Trinh from Budapest University of Technology and Economics and it is based on the original scale-free network generation algorithm of Barabási - Albert

Figure 1: Scafida network topology with 4 different types of switches and m = 3

Description

This structure follows the asymmetric structure (inspired by biological networks) as a contrast to the known symmetric structures commonly used as Fat-tree, DCell or BCube. To avoid the disadvantages of these network architectures, biological networks proved that these structures have preferable properties as they survived the evolutionary competition.

Scale-free networks follow Power-law distribution, they are represented by ultra-small diameter and high error tolerance and easily scalable. Scafida retains these properties and allows to have large node degrees due to the Power-law property.

Algorithm

Description

The network structure is generated iteratively by adding a new node to an existing node with a probability proportional to the node’s degree, putting a constraint on the number of links that a node can have, in order to meet the port number of network routers and switches, which are determined at the beginning of the algorithm.

The algorithm initialises a graph with m initial nodes and a list R used to implement the preferential attachment to store the indices of the network. A new node is added to the network and linked to the initially added nodes; the list R is updated, adding the initial nodes once and the new one m-times.

The nodes, indexed by b, are added to the graph one-by-one until the network has the required number of network devices:

1. Each new node receives m links based on the preferential attachment principle.
2. The target node selection procedure is executed until m different nodes are selected.
3. Check if the picked target node has empty ports and the number of ports can be increased.
4. After picking m nodes the list R is updated before adding the next node to the network.

The created network is a logical network and so it can be realized only at the end of the algorithm, when it turns out which nodes will be servers and which will be switches.

Pseudocode

Input:

nt0 — number of servers
pt0 — number of servers’ ports
nt1,...,ntk — number of ti type switches
pt1,...,ptk — number of ports of ti type switches
ati — number of ti type switches already allocated
dv — degree of the node v ∈ V
m — number of links a newly added node has

Algorithm:

G = (V, E)                      // an empty graph
V = V ∪ {0,1,...,m−1}           // add initial nodes
ati = 0; i = 0,...,k            // initialization
R = {}                          // used for preferential attachment

// add initial links to the network
E= E ∪ {(m, 0),(m, 1),...,(m, m−1)}
R = R ∪ {0,...,m−1}             // update the index list
R = R ∪ {m,...,m}               // m times
b = m + 1                       // the index of the next vertex

for b in devices do
    V = V ∪ {b}                 // add the node to the graph
    T = {}                      // store the selected target nodes

    while |T| < m do
      repeat
        vt = random(R)          // a random item of R
      until vt !∈ T

      if dvt !∈ {pt0,...,ptk} then
          T = T ∪ {vt}
          E = E ∪ {(b, vt)}     // add the edge
      else
        // let dvt = pti w.l.o.g.
        // determine whether the switch can be extended
        nasw = 0                // number of allocated larger switches
        ntsw = 0                // total number of larger switches

        for j = 0,...,k do
          if ptj > pti then
            nasw += atj
            ntsw += ntj
          if nasw < ntsw then
            // the target switch can have more ports
            ati = ati − 1
            ati+1 = ati+1 + 1
            T = T ∪ {vt}
            E = E ∪ {(b, vt)}
          else
            R = R - {vt}        // remove vt instances from node pool R

// update the index list
R = R ∪ T

for i = 1,...,m do
  R = R ∪ {b}

Expansion algorithm

An expansion algorithm was proposed to upgrade an existing Scafida Data center, replacing existing devices with fewer ports in a bottom-up manner without altering the performance of the original one.

Figure 2: Average shortest path length for different node classes

Properties

The maximal degree of the nodes in the Scafida network does not alter the properties of scale-free networks for both shortest path and throughput capability.

Shortest path

The average length of the paths can impact the performance of the network, but in the Scafida topology, independently of the size of the network, it increases moderately with the constraint of the degree.

Throughput capability

Figure 3: CDF of bisection bandwidths (5000 nodes)

The bisection bandwidth, used to measure the throughput of a network, is not impacted by the limitation of the degree, consequently the Scafida network is an optimal network to run distributed applications (e.g MapReduce), which need an intensive communication among servers.

Flexibility

Scafida topology is extremely scalable and flexible. The network created this way can have even 50000 servers without a problem.

Scafida is also flexible in the way it can accommodate heterogeneous devices (e.g. servers and switches with different port capacity). With its flexible property, Scafida network can be created out of the parts of state-of-the-art structures.

Error tolerance

Figure 4: The impact of node failures on the number of disjoint paths

The topology behavior to stochastic failures of network equipments is one important factor to consider while making evaluation of any network topology. Scafida network seems to perform relatively well with less error tolerance for such fault even with the constraints on the node degrees.

Observing the number of disjoint shortest paths between servers after a failure event is a good measure of network's tolerance to such failure.

Subjecting the network under a range of failure rates, the Scafida network tends to have a negligible proportion of disconnected servers, and also retains a considerable percentage of nodes with a number of disjoint paths close to the minimum node degree m.

Scafida performs better than the original scale-free networks when comparing the resilience to network device failures particularly because of the absence of nodes with very high degree with significant impact on network connectivity.

Efficient Source Routing (ESR)

Routing on traditional IP addresses is inefficient for Scafida networks, because they have a stochastically heterogeneous topology, so the routing table sizes would be too large.

Therefore, the bloom filters are used to implement an efficient source routing, so unique identifiers, called Bloom IDs, are generated for every link in the topology.

Addressing

Every target server has a Bloom address, given by the logical sum of every link identifiers from the source to the target and containing routing information for the packet.

Bloom addresses have a local validity, because a specific demand can be routed only from the source where the Bloom address was generated.

Forwarding

Any switch compares the address of the packet with the ID’s of their outgoing interface and then the packet will be sent on the matching links.

Path computation

An extended version of the efficient routing algorithm, implemented in the Barabási–Albert method is used as a mechanism for the path computation.

Figure 5: Illustration of the Efficient Source Routing (ESR)

Failure Handling

At the routing level the failure of a network link is detected by the two neighbouring nodes, whereas the failure of a switch/server is detected by all neighbouring nodes. When a failure is detected, a Network Failure (NF) control packet is broadcasted by a node in the network through its active links so all servers are aware of the failure.

The NF control message has a Bloom address of 11...1 and the source of the packet is set as the Bloom ID of the unavailable network link. The source addresses are stored in each switch for a short time period.

An incoming NF packet is forwarded if it is not in the failed links table; otherwise, it is dropped. When a network failure is corrected, a Network Recovery (NR) control packet is broadcasted in the network, notifying the servers about the availability of the restored network equipment.

Cost considerations

Customizing for a set budget

Since Scafida is a scale-free topology, stakeholders can freely choose the amount spent for servers vs switches instead of choosing a specific topology.

Scafida DC can be built with a usage of cheap commodity switches. Cabling cost of Scafida DC does not affect the final cost, but it requires more human effort.

Power consumption

Scafida data centers are energy efficient due to their scalable and flexible structure, indeed the power consumptions can be specified, in advance, by the operator of the system, therefore it consumes only as much power as required for the given data center size.

Scafida can be used to realize structures of any set of network switches, therefore the resulting data center will be energy proportional, meaning that the power consumption is proportional to the number of servers, in contrast to the power consumption of state-of-the-art data center architectures which is not energy proportional.

Implementation

An implementation of a prototype of Scafida is done in OpenFlow using a virtual test network with several hundreds of nodes.

Related topologies

Many data center structures are based on the symmetric property. Fat -tree topologies are using commodity switches arranged in three layers (known as Clos topology).

BCube data center architecture uses a recursive approach algorithm. BCube is intended to use in modular data centers with a few thousands of servers.

DCell is also built recursively, but on the other hand has a small structural level.

Differences between these structures are not only in the number of servers or shortest path, but also in the power consumption.

Scafida topologies comparison with state-of-the-art topologies

Topology	Number of servers	Average path length	Diameter	Average bisection bandwith
BCube	4096	7.00	8	5953.85
Scafida BCube	4096	5.80	8	5796.45
DCell	2352	4.84	5	1628.05
Scafida DCell	2352	4.72	12	1600.02
Fat-tree	3456	5.91	6	1728.00
Scafida Fat-tree	3456	4.74	7	1718.60
Balanced tree	2304	3.96	4	1039.98
Scafida Balanced tree	2304	6.14	11	1041.12

See also

• Scale-free network
• Data Center
• Network topology
• Barabási–Albert model
• Random graph
• Power-law distribution
• Biological network

This article "Scafida" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Scafida. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---